merkle.gno
9.37 Kb · 276 lines
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/nym-moultest123/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/nym-moultest123/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}
