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

/p/moul/x/merkle/v0

Directory · 5 Files
README.md Open

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.