# 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

```go
import "gno.land/p/moul/x/merkle/v0"

tree := merkle.New([][]byte{[]byte("alice:100"), []byte("bob:250"), []byte("carol:500")})
root := tree.RootHex()          // commit this
p, _ := tree.Proof(1)           // hand p.Index, p.Total, p.Hex() to the user

// later, in a realm, against a root it already committed to:
p, err := merkle.ParseProof(index, total, hexSiblings)
if err == nil && p.Verify(committedRoot, []byte("bob:250")) {
    // bob really is in the committed set, at position 1
}
```

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`](../../../../../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.

## Related

- Append-only log with O(log n) state: [`p/moul/x/mmr/v0`](../../mmr/v0)
- Live demo: [`r/moul/x/provable/v0`](../../../../../r/moul/x/provable/v0)

<!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) -->

---

Part of **[moul/gno-contracts](https://github.com/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](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md).

<!-- END GNOCONTRACTS FOOTER -->