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 anywhere5// before this package. Verification is a single native call, so it costs about6// a seventh of the equivalent hand-rolled loop in Gno.7//8// # The scheme9//10// The tree is the Tendermint simple tree, byte-for-byte the one tm2 uses for11// block headers, so a proof produced here verifies against any Tendermint12// tooling and vice versa. Two properties matter and neither is optional:13//14// - Leaves and inner nodes are DOMAIN SEPARATED. A leaf hashes as15// 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 can17// 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 leaf20// preimage can be exactly 64 bytes, which is an accident of encoding21// rather than a property of the design.22// - Proofs are INDEX BOUND. A proof carries its leaf index and the total23// leaf count, and the verifier recomputes the tree shape from them. A24// proof for index i cannot be replayed at index j, and a proof of the25// wrong length is rejected rather than folded.26//27// The tree is NOT padded to a power of two. Following Tendermint, a tree of n28// leaves splits at the largest power of two below n, which makes the shape a29// function of n alone. Duplicating or promoting an odd trailing leaf, as30// Bitcoin and merkletreejs do, lets two different leaf sets produce one root.31//32// # Bounds33//34// Verify refuses proofs deeper than MaxDepth. An unbounded sibling list is a35// loop whose length an untrusted caller picks; the caller pays the gas, but36// there is no reason to accept 10,000 siblings for a tree that cannot hold37// more than 2^64 leaves.38//39// # Reproducing a tree off chain40//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 do47//48// It verifies a leaf against a root YOU SUPPLY. A realm has no access to the49// block header or the app hash (`chain/runtime` exposes only ChainID,50// ChainDomain, ChainHeight and GetSessionInfo), so no realm can check that a51// root is the chain's own. Anything built on this is trust-minimised relative52// to a committed root, never trustless. See `r/moul/x/provable/v0` for what53// gno.land can and cannot prove about itself.54//55// Live demo: gno.land/r/moul/x/provable/v056package merkle5758import (59 "crypto/merkle"60 "encoding/hex"61 "errors"62 "strings"63)6465// HashSize is the length in bytes of every node hash (SHA256).66const HashSize = 326768// MaxDepth caps the sibling count Verify will fold. A tree of 2^64 leaves has69// depth 64, so nothing legitimate ever exceeds it.70const MaxDepth = 647172var (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)7980// LeafHash returns SHA256(0x00 || leaf), the Tendermint leaf hash.81func LeafHash(leaf []byte) []byte { return merkle.LeafHash(leaf) }8283// InnerHash returns SHA256(0x01 || left || right), the Tendermint inner hash.84func InnerHash(left, right []byte) []byte { return merkle.InnerHash(left, right) }8586// 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's89// immediate sibling and the final entry is the other child of the root. This90// is Tendermint's "aunts" order.91type Proof struct {92 Index int93 Total int94 Siblings [][]byte95}9697// 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 (from100// arguments, or from a bounded realm collection) rather than kept in realm101// storage. For an append-only log that stores only O(log n) state, use102// gno.land/p/moul/x/mmr/v0 instead.103type Tree struct {104 leaves [][]byte105 root []byte106}107108// New builds a tree over leaves, in the order given. The order is part of the109// 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] = b116 }117 t := &Tree{leaves: cp}118 if len(cp) > 0 {119 t.root = merkle.HashFromByteSlices(encodeSlices(cp))120 }121 return t122}123124// Size returns the number of leaves.125func (t *Tree) Size() int { return len(t.leaves) }126127// Root returns the tree root. It is nil for an empty tree, matching128// Tendermint, where the root of nothing is nothing rather than a hash of129// nothing.130//131// The nil is produced here rather than passed through: a native that returns132// Go nil hands gno back a NON-NIL zero-length slice, so `== nil` on a value133// straight out of crypto/merkle never fires. Test len(), not nil, on anything134// that crossed that boundary.135func (t *Tree) Root() []byte { return t.root }136137// RootHex returns Root hex-encoded, the form to paste into a realm call.138func (t *Tree) RootHex() string { return hex.EncodeToString(t.root) }139140// 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{}, ErrEmptyTree144 }145 if index < 0 || index >= len(t.leaves) {146 return Proof{}, ErrIndexRange147 }148 return Proof{149 Index: index,150 Total: len(t.leaves),151 Siblings: aunts(t.leaves, index),152 }, nil153}154155// aunts collects the sibling hashes on the path from leaves[index] to the156// root, leaf first. It mirrors Tendermint's split-point recursion exactly; any157// divergence here produces proofs the native verifier rejects.158func aunts(leaves [][]byte, index int) [][]byte {159 if len(leaves) <= 1 {160 return nil161 }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}170171func subtreeRoot(leaves [][]byte) []byte {172 return merkle.HashFromByteSlices(encodeSlices(leaves))173}174175// splitPoint returns the largest power of two strictly less than length.176func splitPoint(length int) int {177 if length < 2 {178 return 0179 }180 k := 1181 for k<<1 < length {182 k <<= 1183 }184 return k185}186187// Verify reports whether leaf really sits at p.Index of a tree of p.Total188// 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 whether191// 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 false195 }196 if len(p.Siblings) > MaxDepth {197 return false198 }199 flat := make([]byte, 0, len(p.Siblings)*HashSize)200 for _, s := range p.Siblings {201 if len(s) != HashSize {202 return false203 }204 flat = append(flat, s...)205 }206 return merkle.VerifySimpleProof(root, leaf, p.Index, p.Total, flat)207}208209// Hex renders the siblings as a comma-separated hex list, the form a user210// 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}218219// ParseProof rebuilds a Proof from the arguments of a realm call. An empty or220// 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, nil226 }227 parts := strings.Split(s, ",")228 if len(parts) > MaxDepth {229 return Proof{}, ErrProofTooDeep230 }231 for _, raw := range parts {232 raw = strings.TrimSpace(raw)233 if raw == "" {234 continue235 }236 b, err := hex.DecodeString(raw)237 if err != nil {238 return Proof{}, ErrBadHex239 }240 if len(b) != HashSize {241 return Proof{}, ErrBadHashSize242 }243 p.Siblings = append(p.Siblings, b)244 }245 return p, nil246}247248// VerifySorted folds a commutative, sorted-pair proof: node = SHA256(min || max)249// at every step, which is what OpenZeppelin's MerkleProof and merkletreejs250// 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 preimage255// can be 64 bytes long. Pass an ALREADY HASHED leaf, and double-hash it if256// the producer does (OpenZeppelin's StandardMerkleTree does).257// - It is not index bound, so a proof carries no position and the fold258// 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 false264 }265 if len(siblings) > MaxDepth {266 return false267 }268 node := leafHash269 for _, s := range siblings {270 if len(s) != HashSize {271 return false272 }273 node = hashSortedPair(node, s)274 }275 return equal(node, root)276}277Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.