Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

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}