Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

v0 source pure

Package merkle builds and verifies Merkle inclusion proofs on gno.land.

Readme View source

merkle

Merkle inclusion proofs on gno.land, built on the native crypto/merkle stdlib.

That stdlib landed with the IBC crypto batch (gnolang/gno#5725) and is live on mainnet. Before this package it had zero callers anywhere: not in gnolang/gno's examples/, not here. Meanwhile the only userland Merkle tree in the ecosystem, p/demo/merkle, is quarantined and not deployed on any chain.

The scheme

The Tendermint simple tree, byte for byte the one tm2 uses for block headers. Proofs produced here verify against any Tendermint tooling and vice versa. The tests pin golden roots and sibling lists generated by tm2's own merkle.SimpleProofsFromByteSlices, so a divergence fails CI rather than shipping.

Two properties, neither optional:

Domain separation. A leaf is SHA256(0x00 || leaf), an inner node is SHA256(0x01 || left || right). Without those tags an inner node hash is also a valid leaf hash, so anyone able to choose a 64-byte leaf preimage can prove membership of a leaf that was never in the tree. TestSecondPreimageForgery performs exactly that attack against the commutative scheme and then shows the tagged scheme refuse it.

Index binding. A proof carries its leaf index and the total leaf count, and the verifier rebuilds the tree shape from them. A proof for index i cannot be replayed at index j, and a proof of the wrong length is rejected rather than folded.

The tree is not padded to a power of two. Following Tendermint, an n-leaf tree splits at the largest power of two below n, so the shape is a function of n alone. Duplicating or promoting an odd trailing leaf, as Bitcoin and merkletreejs do, lets two different leaf sets produce one root.

Usage

 1import "gno.land/p/moul/x/merkle/v0"
 2
 3tree := merkle.New([][]byte{[]byte("alice:100"), []byte("bob:250"), []byte("carol:500")})
 4root := tree.RootHex()          // commit this
 5p, _ := tree.Proof(1)           // hand p.Index, p.Total, p.Hex() to the user
 6
 7// later, in a realm, against a root it already committed to:
 8p, err := merkle.ParseProof(index, total, hexSiblings)
 9if err == nil && p.Verify(committedRoot, []byte("bob:250")) {
10    // bob really is in the committed set, at position 1
11}

Verification is a single native call. Measured at depth 20 it costs roughly a seventh of the equivalent hand-rolled fold in Gno, and a third of calling InnerHash twenty times, because per-native-call overhead dominates. (Gas figures are directional: the calibration table in native_gas.go fits the crypto/merkle rows on a different CPU from the crypto/sha256 rows.)

Verify refuses proofs deeper than MaxDepth (64). An unbounded sibling list is a loop whose length an untrusted caller picks.

VerifySorted: interop only

VerifySorted folds the commutative sorted-pair scheme that OpenZeppelin's MerkleProof and merkletreejs produce, for verifying trees built by existing Solidity tooling. It is strictly weaker: no domain separation, no index binding. Pass an already-hashed leaf, and double-hash it if the producer does. Prefer Proof.Verify for anything new.

What this package cannot do

It verifies a leaf against a root you supply. A realm has no access to the block header or the app hash (chain/runtime exposes only ChainID, ChainDomain, ChainHeight and GetSessionInfo), so no realm can check that a root is the chain's own. Anything built on this is trust-minimised relative to a committed root, never trustless.

Worse, and less obvious: gno.land cannot prove its own realm state to anyone. Realm objects live in a store that is explicitly not merkleized. See r/moul/x/provable/v0 for the full picture.

Gno gotcha found while building this

A native function returning Go nil for a []byte hands gno back a non-nil, zero-length slice. merkle.HashFromByteSlices(malformed) == nil is therefore always false. Test len(x) == 0, never x == nil, on anything that crossed the native boundary.

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.

Overview

Package merkle builds and verifies Merkle inclusion proofs on gno.land.

It wraps the `crypto/merkle` stdlib, which is native (implemented in Go, gas-metered) and shipped with the chain, and which had no callers anywhere before this package. Verification is a single native call, so it costs about a seventh of the equivalent hand-rolled loop in Gno.

The scheme

The tree is the Tendermint simple tree, byte-for-byte the one tm2 uses for block headers, so a proof produced here verifies against any Tendermint tooling and vice versa. Two properties matter and neither is optional:

  • Leaves and inner nodes are DOMAIN SEPARATED. A leaf hashes as SHA256(0x00 || leaf), an inner node as SHA256(0x01 || left || right). Without that tag an attacker who can choose a 64-byte leaf preimage can present an inner node as if it were a leaf: the second-preimage attack. Schemes that hash leaves bare (OpenZeppelin's `MerkleProof`, merkletreejs defaults, `p/demo/merkle`) are safe only as long as no leaf preimage can be exactly 64 bytes, which is an accident of encoding rather than a property of the design.
  • Proofs are INDEX BOUND. A proof carries its leaf index and the total leaf count, and the verifier recomputes the tree shape from them. A proof for index i cannot be replayed at index j, and a proof of the wrong length is rejected rather than folded.

The tree is NOT padded to a power of two. Following Tendermint, a tree of n leaves splits at the largest power of two below n, which makes the shape a function of n alone. Duplicating or promoting an odd trailing leaf, as Bitcoin and merkletreejs do, lets two different leaf sets produce one root.

Bounds

Verify refuses proofs deeper than MaxDepth. An unbounded sibling list is a loop whose length an untrusted caller picks; the caller pays the gas, but there is no reason to accept 10,000 siblings for a tree that cannot hold more than 2^64 leaves.

Reproducing a tree off chain

Any Tendermint implementation agrees with this one. In Go:

Example
1import "github.com/gnolang/gno/tm2/pkg/crypto/merkle"
2root, proofs := merkle.SimpleProofsFromByteSlices(leaves)

What this package cannot do

It verifies a leaf against a root YOU SUPPLY. A realm has no access to the block header or the app hash (`chain/runtime` exposes only ChainID, ChainDomain, ChainHeight and GetSessionInfo), so no realm can check that a root is the chain's own. Anything built on this is trust-minimised relative to a committed root, never trustless. See `r/moul/x/provable/v0` for what gno.land can and cannot prove about itself.

Live demo: gno.land/r/moul/x/provable/v0

Constants 2

const HashSize 

1const HashSize = 32
source

HashSize is the length in bytes of every node hash (SHA256).

const MaxDepth 

1const MaxDepth = 64
source

MaxDepth caps the sibling count Verify will fold. A tree of 2^64 leaves has depth 64, so nothing legitimate ever exceeds it.

Variables 1

Functions 5

func InnerHash 

1func InnerHash(left, right []byte) []byte
source

InnerHash returns SHA256(0x01 || left || right), the Tendermint inner hash.

func LeafHash 

1func LeafHash(leaf []byte) []byte
source

LeafHash returns SHA256(0x00 || leaf), the Tendermint leaf hash.

func VerifySorted 

1func VerifySorted(root, leafHash []byte, siblings [][]byte) bool
source

VerifySorted folds a commutative, sorted-pair proof: node = SHA256(min || max) at every step, which is what OpenZeppelin's MerkleProof and merkletreejs produce. Provided for verifying trees built by existing Solidity tooling.

PREFER Proof.Verify. This scheme is strictly weaker:

  • It is not domain separated, so it is sound only while no leaf preimage can be 64 bytes long. Pass an ALREADY HASHED leaf, and double-hash it if the producer does (OpenZeppelin's StandardMerkleTree does).
  • It is not index bound, so a proof carries no position and the fold accepts any depth up to MaxDepth.

leafHash must be the 32-byte hash of the leaf, not the leaf.

func ParseProof 

1func ParseProof(index, total int, hexSiblings string) (Proof, error)
source

ParseProof rebuilds a Proof from the arguments of a realm call. An empty or whitespace-only sibling list is valid: it is the proof for a one-leaf tree.

func New 

1func New(leaves [][]byte) *Tree
source

New builds a tree over leaves, in the order given. The order is part of the commitment: the same set in a different order is a different root.

Types 2

type Proof

struct 
1type Proof struct {
2	Index    int
3	Total    int
4	Siblings [][]byte
5}
source

Proof is an inclusion proof for one leaf of a tree of Total leaves.

Siblings are ordered leaf first, root last: Siblings[0] is the leaf's immediate sibling and the final entry is the other child of the root. This is Tendermint's "aunts" order.

Methods on Proof

func Hex

method on Proof 
1func (p Proof) Hex() string
source

Hex renders the siblings as a comma-separated hex list, the form a user pastes into a transaction. Index and Total travel as their own arguments.

func Verify

method on Proof 
1func (p Proof) Verify(root, leaf []byte) bool
source

Verify reports whether leaf really sits at p.Index of a tree of p.Total leaves whose root is root. It is one native call plus the bounds checks.

Every failure is a false rather than a panic, so a realm can decide whether a bad proof is a revert or a branch.

type Tree

struct 
1type Tree struct {
2	leaves [][]byte
3	root   []byte
4}
source

Tree is an immutable Merkle tree over a fixed list of leaves.

It holds the leaves, so it is meant to be built inside one call (from arguments, or from a bounded realm collection) rather than kept in realm storage. For an append-only log that stores only O(log n) state, use gno.land/p/moul/x/mmr/v0 instead.

Methods on Tree

func Proof

method on Tree 
1func (t *Tree) Proof(index int) (Proof, error)
source

Proof returns the inclusion proof for the leaf at index.

func Root

method on Tree 
1func (t *Tree) Root() []byte
source

Root returns the tree root. It is nil for an empty tree, matching Tendermint, where the root of nothing is nothing rather than a hash of nothing.

The nil is produced here rather than passed through: a native that returns Go nil hands gno back a NON-NIL zero-length slice, so `== nil` on a value straight out of crypto/merkle never fires. Test len(), not nil, on anything that crossed that boundary.

func RootHex

method on Tree 
1func (t *Tree) RootHex() string
source

RootHex returns Root hex-encoded, the form to paste into a realm call.

func Size

method on Tree 
1func (t *Tree) Size() int
source

Size returns the number of leaves.

Imports 5

  • crypto/merkle stdlib
  • crypto/sha256 stdlib
  • encoding/hex stdlib
  • errors stdlib
  • strings stdlib

Source Files 5