1package mmr23import (4 "strconv"5 "testing"67 "gno.land/p/moul/x/merkle/v0"8)910func leafAt(i int) []byte { return []byte("entry-" + strconv.Itoa(i)) }1112func build(n int) *MMR {13 m := New()14 for i := 0; i < n; i++ {15 if got := m.Append(leafAt(i)); got != i {16 panic("Append returned the wrong index")17 }18 }19 return m20}2122// The property that matters: for every log size up to 40, every leaf ever23// appended has a proof that verifies against the root at that size.24func TestEveryProofVerifies(t *testing.T) {25 for n := 1; n <= 40; n++ {26 m := build(n)27 root := m.Root()28 for i := 0; i < n; i++ {29 p, err := m.Proof(i)30 if err != nil {31 t.Fatalf("n=%d i=%d: Proof: %v", n, i, err)32 }33 if !Verify(root, leafAt(i), p) {34 t.Errorf("n=%d i=%d: valid proof rejected", n, i)35 }36 }37 }38}3940// A one-leaf MMR is a single height-0 mountain, so its root is just the41// tagged leaf hash and the proof is empty.42func TestSingleLeaf(t *testing.T) {43 m := build(1)44 if string(m.Root()) != string(merkle.LeafHash(leafAt(0))) {45 t.Error("one-leaf root is not the leaf hash")46 }47 p, err := m.Proof(0)48 if err != nil {49 t.Fatal(err)50 }51 if len(p.Path) != 0 || len(p.Before) != 0 || len(p.After) != 0 {52 t.Error("one-leaf proof should be empty")53 }54}5556// The Tendermint simple tree and a right-bagged MMR are the SAME tree, at57// every size and not only at powers of two. Tendermint splits an n-leaf tree58// at the largest power of two below n: that left half is exactly the first59// mountain, and the right half recurses into the remaining set bits, which is60// exactly the bagging. So an MMR is a drop-in incremental builder for61// Tendermint roots: append in O(log n) on chain, hand out a root any62// Tendermint verifier accepts.63func TestRootMatchesTendermintTreeAtEverySize(t *testing.T) {64 for n := 1; n <= 40; n++ {65 ls := make([][]byte, n)66 for i := range ls {67 ls[i] = leafAt(i)68 }69 if got, want := build(n).RootHex(), merkle.New(ls).RootHex(); got != want {70 t.Errorf("n=%d: MMR root %s, Tendermint tree root %s", n, got, want)71 }72 }73}7475// The consequence of the equality above: a proof produced by the fixed-list76// Tendermint tree verifies against the root an MMR maintained incrementally,77// and both packages agree leaf by leaf.78func TestMerkleProofVerifiesAgainstMMRRoot(t *testing.T) {79 for _, n := range []int{1, 2, 3, 5, 7, 11, 16, 23} {80 ls := make([][]byte, n)81 for i := range ls {82 ls[i] = leafAt(i)83 }84 m := build(n)85 tree := merkle.New(ls)86 for i := 0; i < n; i++ {87 tp, err := tree.Proof(i)88 if err != nil {89 t.Fatalf("n=%d i=%d: %v", n, i, err)90 }91 if !tp.Verify(m.Root(), leafAt(i)) {92 t.Errorf("n=%d i=%d: Tendermint proof rejected by the MMR root", n, i)93 }94 mp, err := m.Proof(i)95 if err != nil {96 t.Fatalf("n=%d i=%d: %v", n, i, err)97 }98 if !Verify(tree.Root(), leafAt(i), mp) {99 t.Errorf("n=%d i=%d: MMR proof rejected by the tree root", n, i)100 }101 }102 }103}104105func TestPeakStructure(t *testing.T) {106 tests := []struct {107 leaves int108 want []int109 }{110 {1, []int{0}},111 {2, []int{1}},112 {3, []int{1, 0}},113 {4, []int{2}},114 {7, []int{2, 1, 0}},115 {11, []int{3, 1, 0}},116 {16, []int{4}},117 }118 for _, tc := range tests {119 if got := len(peakHeights(tc.leaves)); got != len(tc.want) {120 t.Errorf("n=%d: %d peaks, want %d", tc.leaves, got, len(tc.want))121 continue122 }123 for i, h := range peakHeights(tc.leaves) {124 if h != tc.want[i] {125 t.Errorf("n=%d: peak %d height %d, want %d", tc.leaves, i, h, tc.want[i])126 }127 }128 if got := len(build(tc.leaves).peaks); got != len(tc.want) {129 t.Errorf("n=%d: MMR built %d peaks, want %d", tc.leaves, got, len(tc.want))130 }131 }132}133134func TestRejects(t *testing.T) {135 m := build(11)136 root := m.Root()137 p3, _ := m.Proof(3)138 p7, _ := m.Proof(7)139140 tests := []struct {141 name string142 root []byte143 leaf []byte144 proof Proof145 }{146 {"forged leaf", root, []byte("never-appended"), p3},147 {"another real leaf", root, leafAt(4), p3},148 {"proof replayed at another index", root, leafAt(3), Proof{Index: 4, Total: p3.Total, Path: p3.Path, Before: p3.Before, After: p3.After}},149 {"another leaf's proof", root, leafAt(3), p7},150 {"wrong total", root, leafAt(3), Proof{Index: 3, Total: 10, Path: p3.Path, Before: p3.Before, After: p3.After}},151 {"padded path", root, leafAt(3), Proof{Index: 3, Total: 11, Path: append(append([][]byte{}, p3.Path...), make([]byte, HashSize)), Before: p3.Before, After: p3.After}},152 {"truncated path", root, leafAt(3), Proof{Index: 3, Total: 11, Path: p3.Path[:len(p3.Path)-1], Before: p3.Before, After: p3.After}},153 {"peaks swapped", root, leafAt(3), Proof{Index: 3, Total: 11, Path: p3.Path, Before: p3.After, After: p3.Before}},154 {"index beyond total", root, leafAt(3), Proof{Index: 11, Total: 11, Path: p3.Path, Before: p3.Before, After: p3.After}},155 {"negative index", root, leafAt(3), Proof{Index: -1, Total: 11, Path: p3.Path, Before: p3.Before, After: p3.After}},156 {"zero total", root, leafAt(3), Proof{Index: 0, Total: 0}},157 {"short root", root[:31], leafAt(3), p3},158 {"short hash in path", root, leafAt(3), Proof{Index: 3, Total: 11, Path: [][]byte{{1, 2, 3}, p3.Path[1]}, Before: p3.Before, After: p3.After}},159 }160 for _, tc := range tests {161 if Verify(tc.root, tc.leaf, tc.proof) {162 t.Errorf("%s: accepted, must be rejected", tc.name)163 }164 }165}166167// A proof is issued against one size. Appending moves the root, and the old168// proof must stop verifying against the new one rather than quietly pass.169func TestProofIsBoundToItsSize(t *testing.T) {170 m := build(5)171 old, _ := m.Proof(2)172 oldRoot := m.Root()173 if !Verify(oldRoot, leafAt(2), old) {174 t.Fatal("proof does not verify against its own root")175 }176 m.Append(leafAt(5))177 if Verify(m.Root(), leafAt(2), old) {178 t.Error("a stale proof verified against the new root")179 }180 fresh, _ := m.Proof(2)181 if !Verify(m.Root(), leafAt(2), fresh) {182 t.Error("a reissued proof does not verify")183 }184 if !Verify(oldRoot, leafAt(2), old) {185 t.Error("the old proof stopped verifying against the old root")186 }187}188189func TestEmptyAndRange(t *testing.T) {190 m := New()191 if m.Size() != 0 || m.Root() != nil || m.Nodes() != 0 {192 t.Error("a fresh MMR is not empty")193 }194 if _, err := m.Proof(0); err != ErrEmpty {195 t.Errorf("empty Proof: err = %v, want %v", err, ErrEmpty)196 }197 m.Append(leafAt(0))198 for _, i := range []int{-1, 1, 99} {199 if _, err := m.Proof(i); err != ErrIndexRange {200 t.Errorf("index %d: err = %v, want %v", i, err, ErrIndexRange)201 }202 }203}204205// Storage claim from the package doc: 2n - popcount(n) stored hashes.206func TestNodeCount(t *testing.T) {207 for n := 1; n <= 40; n++ {208 want := 2*n - popcount(n)209 if got := build(n).Nodes(); got != want {210 t.Errorf("n=%d: %d nodes, want 2n-popcount(n) = %d", n, got, want)211 }212 }213}214215func popcount(n int) int {216 c := 0217 for n != 0 {218 c += n & 1219 n >>= 1220 }221 return c222}223224func TestParseProofRoundTrip(t *testing.T) {225 m := build(11)226 for i := 0; i < 11; i++ {227 want, _ := m.Proof(i)228 path, before, after := want.Hex()229 got, err := ParseProof(i, 11, path, before, after)230 if err != nil {231 t.Fatalf("i=%d: ParseProof: %v", i, err)232 }233 if !Verify(m.Root(), leafAt(i), got) {234 t.Errorf("i=%d: reparsed proof does not verify", i)235 }236 }237}238239func TestParseProofErrors(t *testing.T) {240 if _, err := ParseProof(0, 2, "zz", "", ""); err != ErrBadHex {241 t.Errorf("bad hex: err = %v", err)242 }243 if _, err := ParseProof(0, 2, "abcd", "", ""); err != ErrBadSize {244 t.Errorf("bad size: err = %v", err)245 }246}247248// PeakHashes is the whole verifier-side state, and it must stay logarithmic.249func TestPeakCountIsLogarithmic(t *testing.T) {250 m := build(1023)251 if got := len(m.PeakHashes()); got != 10 {252 t.Errorf("1023 leaves: %d peaks, want 10", got)253 }254 if got := len(build(1024).PeakHashes()); got != 1 {255 t.Errorf("1024 leaves: %d peaks, want 1", got)256 }257}258Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.