Merkle Proofs

A merkle root commits to a list of any size in a single hash. A contract that stores only the root can check that an element is in the list when a spender provides the element and a proof, without the list being on-chain. NexScript does this with merkleRoot(), which compiles to Nexa's OP_MERKLEROOT, and the SDK builds the trees and proofs.

Trees and proofs

A tree's leaves are hashes of its elements. Pairs of leaves are hashed together, then pairs of those, up to the root. A proof gives the hashes needed to rebuild the root from some of the leaves, so it grows with the logarithm of the tree size.

Trees built by @nexscript/utils have a power of two leaves. Missing leaves are empty (MERKLE_EMPTY), and an empty subtree hashes to empty. A proof can show up to 256 leaves at once, which must be given to merkleRoot() in the order of their positions in the tree.

import { merkleLeaf, merkleTreeRoot, merkleProof } from '@nexscript/utils';

const elements = [alicePub, bobPub, carolPub];
const leaves = elements.map((element) => merkleLeaf(element)); // SHA256 of each element
const root = merkleTreeRoot(leaves);

const proofForBob = merkleProof(leaves, [1]);       // one leaf
const proofForBoth = merkleProof(leaves, [0, 2]);   // several leaves at once

merkleLeaf, merkleTreeRoot and merkleProof take an optional MerkleHash (SHA256, HASH256, RIPEMD160 or HASH160), which must match the contract's options. verifyMerkleProof(root, leaves, proof) checks a proof off-chain the same way the node does.

The rest of the API, for building trees by hand:

Export
merkleNode(left, right, hash?)	The hash of two child nodes; two empty children give an empty node
merkleHashSize(hash)	32, or 20 for RIPEMD160 and HASH160
computeMerkleRoot(leaves, proof, hash?)	The root OP_MERKLEROOT computes, or undefined where the opcode fails
MERKLE_EMPTY	The empty element (0x00): an empty leaf, or the hash of an empty subtree
MerkleHash, MerkleProofStep	The hash algorithms, and the proof's command bytes

Example: an allowlist

This contract lets anyone whose public key is in the tree claim its funds. MERKLE_HASH_ELEMENTS makes the opcode hash the key into its leaf, so the spender passes the key itself, and checkSig makes sure they own it. A key that checkSig accepts is never empty or 64 bytes, which rules out the elements in Choosing elements that would prove more than they should.

contract Allowlist(bytes32 root) {
    function claim(bytes proof, pubkey pk, sig s) {
        require(merkleRoot(proof, [pk], MERKLE_HASH_ELEMENTS) == root);
        require(checkSig(s, pk));
    }
}

const contract = new Contract(artifact, [binToHex(root)], { provider });

await contract.functions
  .claim(merkleProof(leaves, [1]), bobPub, new SignatureTemplate(bobPriv))
  .to(bobAddress, 10000n)
  .send();

Choosing elements

The leaves and the inner nodes are hashed the same way, so the tree cannot tell a leaf from a node. Some elements therefore prove more than the one they stand for:

• Leaf hashes. Without MERKLE_HASH_ELEMENTS, merkleRoot() takes leaf hashes. Only pass leaf hashes that the contract has checked are hashes of real elements: otherwise a spender could pass an inner node of the tree as if it were a leaf.
• An empty element. With MERKLE_HASH_ELEMENTS, an empty element hashes to the empty leaf, so it proves any empty slot whose sibling is also empty (slot 6 of a 5-leaf tree, for example).
• An element twice the hash size. With MERKLE_HASH_ELEMENTS, a 64-byte element (40 bytes with MERKLE_RIPEMD160 or MERKLE_HASH160) that is two child hashes put together hashes to their parent, so with the proof from that level up it passes as a leaf.

Use elements of a fixed size that is not twice the hash size, such as 33-byte public keys or 20-byte hashes, or check the element first:

require(element.length > 0 && element.length != 64);
require(merkleRoot(proof, [element], MERKLE_HASH_ELEMENTS) == root);

merkleRoot() returns the 1-byte empty element 0x00 when every node the proof reaches is empty. It cannot equal a real root, so comparing with one is safe.

caution

Proving that a transaction is in a block this way also needs proof that the block is in the chain. To check that a UTXO exists, use a read-only input instead.