merkle.gno

  1// Package merkle builds and verifies Merkle inclusion proofs on gno.land.
  2//
  3// It wraps the `crypto/merkle` stdlib, which is native (implemented in Go,
  4// gas-metered) and shipped with the chain, and which had no callers anywhere
  5// before this package. Verification is a single native call, so it costs about
  6// a seventh of the equivalent hand-rolled loop in Gno.
  7//
  8// # The scheme
  9//
 10// The tree is the Tendermint simple tree, byte-for-byte the one tm2 uses for
 11// block headers, so a proof produced here verifies against any Tendermint
 12// tooling and vice versa. Two properties matter and neither is optional:
 13//
 14//   - Leaves and inner nodes are DOMAIN SEPARATED. A leaf hashes as
 15//     SHA256(0x00 || leaf), an inner node as SHA256(0x01 || left || right).
 16//     Without that tag an attacker who can choose a 64-byte leaf preimage can
 17//     present an inner node as if it were a leaf: the second-preimage attack.
 18//     Schemes that hash leaves bare (OpenZeppelin's `MerkleProof`,
 19//     merkletreejs defaults, `p/demo/merkle`) are safe only as long as no leaf
 20//     preimage can be exactly 64 bytes, which is an accident of encoding
 21//     rather than a property of the design.
 22//   - Proofs are INDEX BOUND. A proof carries its leaf index and the total
 23//     leaf count, and the verifier recomputes the tree shape from them. A
 24//     proof for index i cannot be replayed at index j, and a proof of the
 25//     wrong length is rejected rather than folded.
 26//
 27// The tree is NOT padded to a power of two. Following Tendermint, a tree of n
 28// leaves splits at the largest power of two below n, which makes the shape a
 29// function of n alone. Duplicating or promoting an odd trailing leaf, as
 30// Bitcoin and merkletreejs do, lets two different leaf sets produce one root.
 31//
 32// # Bounds
 33//
 34// Verify refuses proofs deeper than MaxDepth. An unbounded sibling list is a
 35// loop whose length an untrusted caller picks; the caller pays the gas, but
 36// there is no reason to accept 10,000 siblings for a tree that cannot hold
 37// more than 2^64 leaves.
 38//
 39// # Reproducing a tree off chain
 40//
 41// Any Tendermint implementation agrees with this one. In Go:
 42//
 43//	import "github.com/gnolang/gno/tm2/pkg/crypto/merkle"
 44//	root, proofs := merkle.SimpleProofsFromByteSlices(leaves)
 45//
 46// # What this package cannot do
 47//
 48// It verifies a leaf against a root YOU SUPPLY. A realm has no access to the
 49// block header or the app hash (`chain/runtime` exposes only ChainID,
 50// ChainDomain, ChainHeight and GetSessionInfo), so no realm can check that a
 51// root is the chain's own. Anything built on this is trust-minimised relative
 52// to a committed root, never trustless. See `r/moul/x/provable/v0` for what
 53// gno.land can and cannot prove about itself.
 54//
 55// Live demo: gno.land/r/moul/x/provable/v0
 56package merkle
 57
 58import (
 59	"crypto/merkle"
 60	"encoding/hex"
 61	"errors"
 62	"strings"
 63)
 64
 65// HashSize is the length in bytes of every node hash (SHA256).
 66const HashSize = 32
 67
 68// MaxDepth caps the sibling count Verify will fold. A tree of 2^64 leaves has
 69// depth 64, so nothing legitimate ever exceeds it.
 70const MaxDepth = 64
 71
 72var (
 73	ErrEmptyTree    = errors.New("merkle: tree has no leaves")
 74	ErrIndexRange   = errors.New("merkle: leaf index out of range")
 75	ErrProofTooDeep = errors.New("merkle: proof deeper than MaxDepth")
 76	ErrBadHex       = errors.New("merkle: sibling is not valid hex")
 77	ErrBadHashSize  = errors.New("merkle: sibling is not 32 bytes")
 78)
 79
 80// LeafHash returns SHA256(0x00 || leaf), the Tendermint leaf hash.
 81func LeafHash(leaf []byte) []byte { return merkle.LeafHash(leaf) }
 82
 83// InnerHash returns SHA256(0x01 || left || right), the Tendermint inner hash.
 84func InnerHash(left, right []byte) []byte { return merkle.InnerHash(left, right) }
 85
 86// Proof is an inclusion proof for one leaf of a tree of Total leaves.
 87//
 88// Siblings are ordered leaf first, root last: Siblings[0] is the leaf's
 89// immediate sibling and the final entry is the other child of the root. This
 90// is Tendermint's "aunts" order.
 91type Proof struct {
 92	Index    int
 93	Total    int
 94	Siblings [][]byte
 95}
 96
 97// Tree is an immutable Merkle tree over a fixed list of leaves.
 98//
 99// It holds the leaves, so it is meant to be built inside one call (from
100// arguments, or from a bounded realm collection) rather than kept in realm
101// storage. For an append-only log that stores only O(log n) state, use
102// gno.land/p/moul/x/mmr/v0 instead.
103type Tree struct {
104	leaves [][]byte
105	root   []byte
106}
107
108// New builds a tree over leaves, in the order given. The order is part of the
109// commitment: the same set in a different order is a different root.
110func New(leaves [][]byte) *Tree {
111	cp := make([][]byte, len(leaves))
112	for i, l := range leaves {
113		b := make([]byte, len(l))
114		copy(b, l)
115		cp[i] = b
116	}
117	t := &Tree{leaves: cp}
118	if len(cp) > 0 {
119		t.root = merkle.HashFromByteSlices(encodeSlices(cp))
120	}
121	return t
122}
123
124// Size returns the number of leaves.
125func (t *Tree) Size() int { return len(t.leaves) }
126
127// Root returns the tree root. It is nil for an empty tree, matching
128// Tendermint, where the root of nothing is nothing rather than a hash of
129// nothing.
130//
131// The nil is produced here rather than passed through: a native that returns
132// Go nil hands gno back a NON-NIL zero-length slice, so `== nil` on a value
133// straight out of crypto/merkle never fires. Test len(), not nil, on anything
134// that crossed that boundary.
135func (t *Tree) Root() []byte { return t.root }
136
137// RootHex returns Root hex-encoded, the form to paste into a realm call.
138func (t *Tree) RootHex() string { return hex.EncodeToString(t.root) }
139
140// Proof returns the inclusion proof for the leaf at index.
141func (t *Tree) Proof(index int) (Proof, error) {
142	if len(t.leaves) == 0 {
143		return Proof{}, ErrEmptyTree
144	}
145	if index < 0 || index >= len(t.leaves) {
146		return Proof{}, ErrIndexRange
147	}
148	return Proof{
149		Index:    index,
150		Total:    len(t.leaves),
151		Siblings: aunts(t.leaves, index),
152	}, nil
153}
154
155// aunts collects the sibling hashes on the path from leaves[index] to the
156// root, leaf first. It mirrors Tendermint's split-point recursion exactly; any
157// divergence here produces proofs the native verifier rejects.
158func aunts(leaves [][]byte, index int) [][]byte {
159	if len(leaves) <= 1 {
160		return nil
161	}
162	k := splitPoint(len(leaves))
163	if index < k {
164		sub := aunts(leaves[:k], index)
165		return append(sub, subtreeRoot(leaves[k:]))
166	}
167	sub := aunts(leaves[k:], index-k)
168	return append(sub, subtreeRoot(leaves[:k]))
169}
170
171func subtreeRoot(leaves [][]byte) []byte {
172	return merkle.HashFromByteSlices(encodeSlices(leaves))
173}
174
175// splitPoint returns the largest power of two strictly less than length.
176func splitPoint(length int) int {
177	if length < 2 {
178		return 0
179	}
180	k := 1
181	for k<<1 < length {
182		k <<= 1
183	}
184	return k
185}
186
187// Verify reports whether leaf really sits at p.Index of a tree of p.Total
188// leaves whose root is root. It is one native call plus the bounds checks.
189//
190// Every failure is a false rather than a panic, so a realm can decide whether
191// a bad proof is a revert or a branch.
192func (p Proof) Verify(root, leaf []byte) bool {
193	if len(root) != HashSize || p.Total <= 0 || p.Index < 0 || p.Index >= p.Total {
194		return false
195	}
196	if len(p.Siblings) > MaxDepth {
197		return false
198	}
199	flat := make([]byte, 0, len(p.Siblings)*HashSize)
200	for _, s := range p.Siblings {
201		if len(s) != HashSize {
202			return false
203		}
204		flat = append(flat, s...)
205	}
206	return merkle.VerifySimpleProof(root, leaf, p.Index, p.Total, flat)
207}
208
209// Hex renders the siblings as a comma-separated hex list, the form a user
210// pastes into a transaction. Index and Total travel as their own arguments.
211func (p Proof) Hex() string {
212	parts := make([]string, len(p.Siblings))
213	for i, s := range p.Siblings {
214		parts[i] = hex.EncodeToString(s)
215	}
216	return strings.Join(parts, ",")
217}
218
219// ParseProof rebuilds a Proof from the arguments of a realm call. An empty or
220// whitespace-only sibling list is valid: it is the proof for a one-leaf tree.
221func ParseProof(index, total int, hexSiblings string) (Proof, error) {
222	p := Proof{Index: index, Total: total}
223	s := strings.TrimSpace(hexSiblings)
224	if s == "" {
225		return p, nil
226	}
227	parts := strings.Split(s, ",")
228	if len(parts) > MaxDepth {
229		return Proof{}, ErrProofTooDeep
230	}
231	for _, raw := range parts {
232		raw = strings.TrimSpace(raw)
233		if raw == "" {
234			continue
235		}
236		b, err := hex.DecodeString(raw)
237		if err != nil {
238			return Proof{}, ErrBadHex
239		}
240		if len(b) != HashSize {
241			return Proof{}, ErrBadHashSize
242		}
243		p.Siblings = append(p.Siblings, b)
244	}
245	return p, nil
246}
247
248// VerifySorted folds a commutative, sorted-pair proof: node = SHA256(min || max)
249// at every step, which is what OpenZeppelin's MerkleProof and merkletreejs
250// produce. Provided for verifying trees built by existing Solidity tooling.
251//
252// PREFER Proof.Verify. This scheme is strictly weaker:
253//
254//   - It is not domain separated, so it is sound only while no leaf preimage
255//     can be 64 bytes long. Pass an ALREADY HASHED leaf, and double-hash it if
256//     the producer does (OpenZeppelin's StandardMerkleTree does).
257//   - It is not index bound, so a proof carries no position and the fold
258//     accepts any depth up to MaxDepth.
259//
260// leafHash must be the 32-byte hash of the leaf, not the leaf.
261func VerifySorted(root, leafHash []byte, siblings [][]byte) bool {
262	if len(root) != HashSize || len(leafHash) != HashSize {
263		return false
264	}
265	if len(siblings) > MaxDepth {
266		return false
267	}
268	node := leafHash
269	for _, s := range siblings {
270		if len(s) != HashSize {
271			return false
272		}
273		node = hashSortedPair(node, s)
274	}
275	return equal(node, root)
276}