cards.gno
8.47 Kb · 340 lines
1// Package cards implements the byte-level primitives of the gno poker protocol
2// (docs/protocol.md sections 1 to 4): the group prime, seed derivations, the
3// seed permutation, deck parsing and validation, deck Merkle trees and the
4// derivation of official cards from revealed seeds. It does no modular
5// exponentiation; callers that need it use crypto/modexp.
6package cards
7
8import (
9 "bytes"
10 "crypto/sha256"
11 "encoding/base64"
12 "encoding/hex"
13 "errors"
14)
15
16const (
17 CardLen = 256
18 DeckSize = 52
19 DeckLen = CardLen * DeckSize
20 ProofLen = 6 * 32
21
22 // PHex is the RFC 3526 2048-bit MODP group (group 14) prime.
23 PHex = "ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74" +
24 "020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f1437" +
25 "4fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7ed" +
26 "ee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf05" +
27 "98da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb" +
28 "9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3b" +
29 "e39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf695581718" +
30 "3995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff"
31
32 // CanonRootHex is the Merkle root of the canonical deck [m_0 .. m_51].
33 // TestCanonRoot recomputes it with crypto/modexp.
34 CanonRootHex = "cbbd0f99d1b6d995ea84edbcf80a62c245ea59240ccee3fde85b87bd35077030"
35
36 tagCard = "gno-poker/card/v1"
37 tagCommit = "gno-poker/commit/v1"
38 tagShufKey = "gno-poker/shufkey/v1"
39 tagCardKey = "gno-poker/cardkey/v1"
40 tagPerm = "gno-poker/perm/v1"
41)
42
43var pBytes = mustHex(PHex)
44
45func mustHex(s string) []byte {
46 b, err := hex.DecodeString(s)
47 if err != nil {
48 panic(err)
49 }
50 return b
51}
52
53// P returns a copy of the prime as 256 big-endian bytes.
54func P() []byte {
55 var out [CardLen]byte
56 copy(out[:], pBytes)
57 return out[:]
58}
59
60// CanonRoot returns the hardcoded canonical deck root.
61func CanonRoot() []byte {
62 return mustHex(CanonRootHex)
63}
64
65func hashParts(parts ...[]byte) []byte {
66 n := 0
67 for _, p := range parts {
68 n += len(p)
69 }
70 buf := make([]byte, 0, n)
71 for _, p := range parts {
72 buf = append(buf, p...)
73 }
74 h := sha256.Sum256(buf)
75 return h[:]
76}
77
78func tweak(k []byte) []byte {
79 k[0] |= 0x80
80 k[31] |= 0x01
81 return k
82}
83
84// Commit returns H("gno-poker/commit/v1" || seed).
85func Commit(seed []byte) []byte {
86 return hashParts([]byte(tagCommit), seed)
87}
88
89// ShuffleKey returns the shuffle exponent e derived from seed.
90func ShuffleKey(seed []byte) []byte {
91 return tweak(hashParts([]byte(tagShufKey), seed))
92}
93
94// CardKey returns the card key k_i derived from seed for deck position i.
95func CardKey(seed []byte, i int) []byte {
96 return tweak(hashParts([]byte(tagCardKey), seed, []byte{byte(i)}))
97}
98
99// CardPreimage returns the 256-byte value x of card c; the plaintext card is
100// m_c = x^2 mod P.
101func CardPreimage(c int) []byte {
102 out := make([]byte, 0, CardLen)
103 for k := 0; k < 8; k++ {
104 out = append(out, hashParts([]byte(tagCard), []byte{byte(c), byte(k)})...)
105 }
106 return out
107}
108
109// Permutation returns the Fisher-Yates permutation of 0..51 determined by seed.
110func Permutation(seed []byte) []int {
111 var arr [DeckSize]int
112 a := arr[:]
113 for i := range a {
114 a[i] = i
115 }
116 prefix := make([]byte, 0, len(tagPerm)+len(seed)+4)
117 prefix = append(prefix, []byte(tagPerm)...)
118 prefix = append(prefix, seed...)
119 var block []byte
120 pos := 32
121 ctr := uint32(0)
122 next := func() uint64 {
123 if pos >= 32 {
124 ctrB := []byte{byte(ctr >> 24), byte(ctr >> 16), byte(ctr >> 8), byte(ctr)}
125 block = hashParts(prefix, ctrB)
126 ctr++
127 pos = 0
128 }
129 w := uint64(block[pos])<<24 | uint64(block[pos+1])<<16 | uint64(block[pos+2])<<8 | uint64(block[pos+3])
130 pos += 4
131 return w
132 }
133 for i := DeckSize - 1; i >= 1; i-- {
134 n := uint64(i + 1)
135 limit := ((uint64(1) << 32) / n) * n
136 x := next()
137 for x >= limit {
138 x = next()
139 }
140 j := int(x % n)
141 a[i], a[j] = a[j], a[i]
142 }
143 return a
144}
145
146// IsValidElement reports whether 1 < v < P for a 256-byte big-endian v.
147func IsValidElement(v []byte) bool {
148 if len(v) != CardLen {
149 return false
150 }
151 if bytes.Compare(v, pBytes) >= 0 {
152 return false
153 }
154 for i := 0; i < CardLen-1; i++ {
155 if v[i] != 0 {
156 return true
157 }
158 }
159 return v[CardLen-1] > 1
160}
161
162// DecodeElement decodes one base64 deck element and checks its range.
163func DecodeElement(b64 string) ([]byte, error) {
164 v, err := DecodeBase64(b64)
165 if err != nil {
166 return nil, errors.New("invalid base64 element")
167 }
168 if len(v) != CardLen {
169 return nil, errors.New("element must be 256 bytes")
170 }
171 if !IsValidElement(v) {
172 return nil, errors.New("element out of range")
173 }
174 return v, nil
175}
176
177// ParseDeck decodes a base64 deck, validates every element (1 < v < P, no
178// duplicates) and returns the raw deck bytes and its Merkle root.
179func ParseDeck(b64 string) ([]byte, []byte, error) {
180 deck, err := DecodeBase64(b64)
181 if err != nil {
182 return nil, nil, errors.New("invalid base64 deck")
183 }
184 if len(deck) != DeckLen {
185 return nil, nil, errors.New("deck must be 13312 bytes")
186 }
187 leaves := make([][]byte, 64)
188 seen := make(map[string]bool, DeckSize)
189 for i := 0; i < DeckSize; i++ {
190 el := deck[i*CardLen : (i+1)*CardLen]
191 if !IsValidElement(el) {
192 return nil, nil, errors.New("deck element out of range")
193 }
194 leaf := LeafHash(el)
195 if seen[string(leaf)] {
196 return nil, nil, errors.New("duplicate deck element")
197 }
198 seen[string(leaf)] = true
199 leaves[i] = leaf
200 }
201 return deck, rootFromLeaves(leaves), nil
202}
203
204// EncodeDeck returns the standard base64 encoding of raw deck bytes.
205func EncodeDeck(deck []byte) string {
206 return base64.StdEncoding.EncodeToString(deck)
207}
208
209// LeafHash returns H(0x00 || element).
210func LeafHash(el []byte) []byte {
211 return hashParts([]byte{0}, el)
212}
213
214func nodeHash(l, r []byte) []byte {
215 return hashParts([]byte{1}, l, r)
216}
217
218func rootFromLeaves(leaves [][]byte) []byte {
219 level := make([][]byte, 64)
220 zero := make([]byte, 32)
221 for i := 0; i < 64; i++ {
222 if i < DeckSize {
223 level[i] = leaves[i]
224 } else {
225 level[i] = zero
226 }
227 }
228 for len(level) > 1 {
229 next := make([][]byte, len(level)/2)
230 for i := range next {
231 next[i] = nodeHash(level[2*i], level[2*i+1])
232 }
233 level = next
234 }
235 return level[0]
236}
237
238func deckLeaves(deck []byte) [][]byte {
239 leaves := make([][]byte, 64)
240 for i := 0; i < DeckSize; i++ {
241 leaves[i] = LeafHash(deck[i*CardLen : (i+1)*CardLen])
242 }
243 return leaves
244}
245
246// MerkleRoot returns the root of a raw 13312-byte deck.
247func MerkleRoot(deck []byte) []byte {
248 if len(deck) != DeckLen {
249 panic("deck must be 13312 bytes")
250 }
251 return rootFromLeaves(deckLeaves(deck))
252}
253
254// MerkleProof returns the 192-byte proof for position i of a raw deck.
255func MerkleProof(deck []byte, i int) []byte {
256 if len(deck) != DeckLen || i < 0 || i >= DeckSize {
257 panic("invalid proof request")
258 }
259 level := make([][]byte, 64)
260 leaves := deckLeaves(deck)
261 zero := make([]byte, 32)
262 for k := 0; k < 64; k++ {
263 if k < DeckSize {
264 level[k] = leaves[k]
265 } else {
266 level[k] = zero
267 }
268 }
269 proof := make([]byte, 0, ProofLen)
270 idx := i
271 for len(level) > 1 {
272 proof = append(proof, level[idx^1]...)
273 next := make([][]byte, len(level)/2)
274 for k := range next {
275 next[k] = nodeHash(level[2*k], level[2*k+1])
276 }
277 level = next
278 idx >>= 1
279 }
280 return proof
281}
282
283// VerifyProof checks that el sits at position i under root.
284func VerifyProof(root, el []byte, i int, proof []byte) bool {
285 if len(root) != 32 || len(el) != CardLen || len(proof) != ProofLen || i < 0 || i >= DeckSize {
286 return false
287 }
288 h := LeafHash(el)
289 for l := 0; l < 6; l++ {
290 sib := proof[l*32 : (l+1)*32]
291 if (i>>uint(l))&1 == 0 {
292 h = nodeHash(h, sib)
293 } else {
294 h = nodeHash(sib, h)
295 }
296 }
297 return bytes.Equal(h, root)
298}
299
300// OfficialCards maps every deck position to its card index given the
301// permutations of hand players 0..n-1.
302func OfficialCards(perms [][]int) []int {
303 var arr [DeckSize]int
304 out := arr[:]
305 for i := 0; i < DeckSize; i++ {
306 idx := i
307 for j := len(perms) - 1; j >= 0; j-- {
308 idx = perms[j][idx]
309 }
310 out[i] = idx
311 }
312 return out
313}
314
315// DecodeHex decodes lowercase hex of exactly n bytes.
316func DecodeHex(s string, n int) ([]byte, error) {
317 if len(s) != 2*n {
318 return nil, errors.New("hex value has wrong length")
319 }
320 for i := 0; i < len(s); i++ {
321 c := s[i]
322 if !((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f')) {
323 return nil, errors.New("hex must be lowercase")
324 }
325 }
326 return hex.DecodeString(s)
327}
328
329// EncodeHex returns lowercase hex.
330func EncodeHex(b []byte) string {
331 return hex.EncodeToString(b)
332}
333
334// CardString renders card index c as e.g. "As", "Td", "2c".
335func CardString(c int) string {
336 if c < 0 || c >= DeckSize {
337 return "??"
338 }
339 return string("23456789TJQKA"[c%13]) + string("cdhs"[c/13])
340}