gno.land/p/moul/x/mmr/v0⧉

1// Package mmr implements a Merkle Mountain Range: an append-only log with a2// root that updates in O(log n) and inclusion proofs of O(log n) size.3//4// # Why not a plain Merkle tree5//6// gno.land/p/moul/x/merkle/v0 commits to a FIXED list. Adding a leaf means7// rebuilding from every leaf, which on chain means re-reading the whole set8// and re-hashing it, every time. An MMR never rebuilds: an append hashes at9// most log2(n) times and touches nothing else.10//11// That is the shape any on-chain log wants. A wiki committing to its revision12// history, a forge committing to its objects, an agent realm committing to the13// receipts it issued: all append, none rewrite.14//15// # The structure16//17// An MMR is a list of perfect binary trees ("mountains") of strictly18// decreasing height, one per set bit of the leaf count. Eleven leaves is19// 8 + 2 + 1, so three mountains of height 3, 1 and 0. Appending a leaf pushes20// a height-0 mountain and merges equal-height neighbours, exactly like21// incrementing a binary counter.22//23// The root is the peaks "bagged" right to left:24//25//	root = InnerHash(p0, InnerHash(p1, InnerHash(p2, …)))26//27// Hashing is gno.land/p/moul/x/merkle/v0's, which is Tendermint's: leaves are28// tagged 0x00 and inner nodes 0x01. Leaf and inner preimages therefore cannot29// collide, so the second-preimage forgery that works against untagged schemes30// does not apply here. See that package for the worked attack.31//32// # This IS the Tendermint tree33//34// The root above equals the Tendermint simple-tree root over the same leaves,35// at every size and not merely at powers of two. Tendermint splits an n-leaf36// tree at the largest power of two below n: that left half is exactly the37// first mountain, and the right half recurses through the remaining set bits,38// which is exactly the bagging. The two constructions coincide.39//40// So this package is a drop-in INCREMENTAL BUILDER for Tendermint roots.41// Append in O(log n) on chain and hand out a root that any Tendermint verifier42// accepts; proofs cross over in both directions, which43// TestMerkleProofVerifiesAgainstMMRRoot pins. Use merkle.New when the leaf set44// is fixed and you want the simpler proof encoding, use this when the log45// grows.46//47// # Proofs are bound to position and to size48//49// A Proof carries the leaf index and the leaf count the MMR had when it was50// issued. The verifier recomputes the whole peak structure from that count,51// which fixes the number of peaks, which mountain holds the leaf, the local52// index inside it, and therefore the exact expected length of every component53// of the proof. A proof cannot be replayed at another index, against another54// size, or padded.55//56// Because the root changes on every append, a proof is valid against the root57// at its own Total and no other. A realm that wants old proofs to keep58// verifying must keep the historical roots; Roots grow by one 32-byte hash per59// append, which is the price of an auditable log.60//61// # Storage62//63// Append stores one node per leaf plus one per merge, so 2n-popcount(n) hashes64// for n leaves, under 64 bytes per leaf amortised. That is what on-chain proof65// generation costs. A realm that only ever needs to VERIFY proofs, with the66// tree living off chain, should store the root alone and use67// gno.land/p/moul/x/merkle/v0's Verify instead.68//69// Live demo: gno.land/r/moul/x/provable/v070package mmr7172import (73	"encoding/hex"74	"errors"7576	"gno.land/p/moul/x/merkle/v0"77)7879// HashSize is the length in bytes of every node hash.80const HashSize = merkle.HashSize8182// MaxPeaks caps the peak count a Proof may claim. A 64-peak MMR would hold83// more than 2^64 leaves.84const MaxPeaks = 648586var (87	ErrEmpty      = errors.New("mmr: log is empty")88	ErrIndexRange = errors.New("mmr: leaf index out of range")89	ErrBadHex     = errors.New("mmr: hash is not valid hex")90	ErrBadSize    = errors.New("mmr: hash is not 32 bytes")91	ErrTooManyPeaks = errors.New("mmr: more peaks than MaxPeaks")92)9394// peak is one mountain: the position of its root in nodes, and its height.95type peak struct {96	pos    int97	height int98}99100// MMR is an append-only Merkle mountain range.101//102// The zero value is an empty, ready-to-use log.103type MMR struct {104	nodes  [][]byte // every node, in postorder: [left subtree][right subtree][root]105	peaks  []peak106	leaves int107}108109// New returns an empty MMR.110func New() *MMR { return &MMR{} }111112// Size returns the number of leaves appended so far.113func (m *MMR) Size() int { return m.leaves }114115// Nodes returns the number of stored hashes, leaves and merges together. Use116// it to reason about storage growth.117func (m *MMR) Nodes() int { return len(m.nodes) }118119// Append adds a leaf and returns its index. O(log n) hashes, no rebuild.120func (m *MMR) Append(leaf []byte) int {121	index := m.leaves122	m.nodes = append(m.nodes, merkle.LeafHash(leaf))123	m.peaks = append(m.peaks, peak{pos: len(m.nodes) - 1, height: 0})124	for len(m.peaks) >= 2 {125		right := m.peaks[len(m.peaks)-1]126		left := m.peaks[len(m.peaks)-2]127		if left.height != right.height {128			break129		}130		m.nodes = append(m.nodes, merkle.InnerHash(m.nodes[left.pos], m.nodes[right.pos]))131		m.peaks = m.peaks[:len(m.peaks)-2]132		m.peaks = append(m.peaks, peak{pos: len(m.nodes) - 1, height: left.height + 1})133	}134	m.leaves++135	return index136}137138// Root returns the current root, nil while the log is empty.139func (m *MMR) Root() []byte {140	if len(m.peaks) == 0 {141		return nil142	}143	return bag(m.peakHashes())144}145146// RootHex returns Root hex-encoded.147func (m *MMR) RootHex() string { return hex.EncodeToString(m.Root()) }148149// PeakHashes returns the current peak hashes, left to right. This is the whole150// state a verifier needs, and it is O(log n).151func (m *MMR) PeakHashes() [][]byte { return m.peakHashes() }152153func (m *MMR) peakHashes() [][]byte {154	out := make([][]byte, len(m.peaks))155	for i, p := range m.peaks {156		out[i] = m.nodes[p.pos]157	}158	return out159}160161// bag folds peaks right to left: InnerHash(p0, InnerHash(p1, …)).162func bag(peaks [][]byte) []byte {163	if len(peaks) == 0 {164		return nil165	}166	acc := peaks[len(peaks)-1]167	for i := len(peaks) - 2; i >= 0; i-- {168		acc = merkle.InnerHash(peaks[i], acc)169	}170	return acc171}172173// Proof is an inclusion proof for one leaf of a log that held Total leaves.174//175// Path holds the sibling hashes inside the leaf's own mountain, leaf first.176// Before and After hold the other peak hashes, in left-to-right order.177type Proof struct {178	Index  int179	Total  int180	Path   [][]byte181	Before [][]byte182	After  [][]byte183}184185// Proof returns the inclusion proof for the leaf at index, against the current186// root.187func (m *MMR) Proof(index int) (Proof, error) {188	if m.leaves == 0 {189		return Proof{}, ErrEmpty190	}191	if index < 0 || index >= m.leaves {192		return Proof{}, ErrIndexRange193	}194	j, local := locate(m.leaves, index)195	hashes := m.peakHashes()196	return Proof{197		Index:  index,198		Total:  m.leaves,199		Path:   m.pathIn(m.peaks[j], local),200		Before: hashes[:j],201		After:  hashes[j+1:],202	}, nil203}204205// pathIn walks down the perfect tree rooted at p, collecting the sibling at206// each level, and returns them leaf first.207//208// The layout is postorder, so for a node at position pos and height h the209// right child root sits at pos-1 and the left child root at pos-1-(2^h - 1),210// a perfect subtree of height h-1 holding 2^h - 1 nodes.211func (m *MMR) pathIn(p peak, local int) [][]byte {212	var out [][]byte213	pos, h := p.pos, p.height214	for h > 0 {215		rightRoot := pos - 1216		leftRoot := pos - 1 - ((1 << uint(h)) - 1)217		half := 1 << uint(h-1)218		if local < half {219			out = append([][]byte{m.nodes[rightRoot]}, out...)220			pos = leftRoot221		} else {222			out = append([][]byte{m.nodes[leftRoot]}, out...)223			pos = rightRoot224			local -= half225		}226		h--227	}228	return out229}230