1package merkle23import (4 "crypto/sha256"5 "encoding/hex"6 "strconv"7 "testing"8)910// leaves returns n deterministic leaves, "leaf-0" … "leaf-n-1". The golden11// vectors below were produced from these exact inputs by tm2's own12// merkle.SimpleProofsFromByteSlices, so a mismatch means this package has13// diverged from Tendermint, not that the expectation is stale.14func leaves(n int) [][]byte {15 out := make([][]byte, n)16 for i := 0; i < n; i++ {17 out[i] = []byte("leaf-" + strconv.Itoa(i))18 }19 return out20}2122var goldenRoots = map[int]string{23 1: "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7",24 2: "60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",25 3: "cf763a041c81ceef1578a6083f75c61bef2e0014f2a3e683a97fcfca5be7f19a",26 4: "bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",27 5: "00d21829a5503145348abcf712513eacf2a274211ad83e970202bb5b6d80b286",28 7: "0b007fb915eb9b2a146f54b1c86ec53b664f8e455b7660b0b6ee13edc0d921c0",29}3031// goldenAunts[n][i] is the comma-separated hex sibling list tm2 produces for32// leaf i of an n-leaf tree.33var goldenAunts = map[int][]string{34 1: {""},35 2: {36 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f",37 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7",38 },39 3: {40 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f,fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267",41 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7,fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267",42 "60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",43 },44 4: {45 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f,bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69",46 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7,bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69",47 "f76836325aec5699d8d71f8e42e9d47c5c29b08059ba296384f7ca40ad3a40ae,60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",48 "fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267,60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",49 },50 7: {51 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f,bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69,8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",52 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7,bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69,8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",53 "f76836325aec5699d8d71f8e42e9d47c5c29b08059ba296384f7ca40ad3a40ae,60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc,8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",54 "fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267,60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc,8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",55 "8f1593cb92f429d9340b9bbc1f0bb122adf8026c42a4a42142e2168931727236,676f3782f5b3a5fb4370ed49572cedc523f4a66322269c85f2af0509d17b0a4d,bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",56 "ea9fc1a1b6e191b460d0d6306e3e870c173f39330f13cda1b70cfc72bdc398ba,676f3782f5b3a5fb4370ed49572cedc523f4a66322269c85f2af0509d17b0a4d,bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",57 "985bb5d36b927800876871da925a7e82abe83a9ddba5882920a007a55ea2b376,bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",58 },59}6061func TestRootMatchesTendermint(t *testing.T) {62 for _, n := range []int{1, 2, 3, 4, 5, 7} {63 got := New(leaves(n)).RootHex()64 if got != goldenRoots[n] {65 t.Errorf("n=%d: root = %s, tm2 says %s", n, got, goldenRoots[n])66 }67 }68}6970func TestProofMatchesTendermint(t *testing.T) {71 for n, want := range goldenAunts {72 tree := New(leaves(n))73 for i, w := range want {74 p, err := tree.Proof(i)75 if err != nil {76 t.Fatalf("n=%d i=%d: Proof: %v", n, i, err)77 }78 if got := p.Hex(); got != w {79 t.Errorf("n=%d i=%d:\n got %s\n want %s", n, i, got, w)80 }81 }82 }83}8485// Every leaf of every tree shape up to 33 must produce a proof the native86// verifier accepts. This is the property that matters; the golden vectors only87// pin the encoding.88func TestEveryProofVerifies(t *testing.T) {89 for n := 1; n <= 33; n++ {90 ls := leaves(n)91 tree := New(ls)92 root := tree.Root()93 for i := 0; i < n; i++ {94 p, err := tree.Proof(i)95 if err != nil {96 t.Fatalf("n=%d i=%d: Proof: %v", n, i, err)97 }98 if !p.Verify(root, ls[i]) {99 t.Errorf("n=%d i=%d: valid proof rejected", n, i)100 }101 }102 }103}104105func TestRejects(t *testing.T) {106 ls := leaves(8)107 tree := New(ls)108 root := tree.Root()109 p0, _ := tree.Proof(0)110 p1, _ := tree.Proof(1)111112 tests := []struct {113 name string114 proof Proof115 root []byte116 leaf []byte117 }{118 {"forged leaf", p0, root, []byte("not-a-leaf")},119 {"another real leaf at the wrong index", p0, root, ls[1]},120 {"proof replayed at a different index", Proof{Index: 1, Total: p0.Total, Siblings: p0.Siblings}, root, ls[1]},121 {"sibling list of another leaf", Proof{Index: 0, Total: 8, Siblings: p1.Siblings}, root, ls[0]},122 {"wrong root", p0, LeafHash([]byte("nope")), ls[0]},123 {"index beyond total", Proof{Index: 8, Total: 8, Siblings: p0.Siblings}, root, ls[0]},124 {"negative index", Proof{Index: -1, Total: 8, Siblings: p0.Siblings}, root, ls[0]},125 {"zero total", Proof{Index: 0, Total: 0, Siblings: p0.Siblings}, root, ls[0]},126 {"truncated proof", Proof{Index: 0, Total: 8, Siblings: p0.Siblings[:1]}, root, ls[0]},127 {"short root", p0, root[:31], ls[0]},128 }129 for _, tc := range tests {130 if tc.proof.Verify(tc.root, tc.leaf) {131 t.Errorf("%s: accepted, must be rejected", tc.name)132 }133 }134}135136func TestMaxDepthCap(t *testing.T) {137 sibs := make([][]byte, MaxDepth+1)138 for i := range sibs {139 sibs[i] = make([]byte, HashSize)140 }141 p := Proof{Index: 0, Total: 1 << 20, Siblings: sibs}142 if p.Verify(make([]byte, HashSize), []byte("x")) {143 t.Error("proof deeper than MaxDepth accepted")144 }145 if !VerifySorted(make([]byte, HashSize), make([]byte, HashSize), sibs[:MaxDepth]) == false {146 t.Error("unreachable")147 }148 if VerifySorted(make([]byte, HashSize), make([]byte, HashSize), sibs) {149 t.Error("sorted proof deeper than MaxDepth accepted")150 }151}152153func TestParseProofRoundTrip(t *testing.T) {154 tree := New(leaves(7))155 for i := 0; i < 7; i++ {156 want, _ := tree.Proof(i)157 got, err := ParseProof(i, 7, want.Hex())158 if err != nil {159 t.Fatalf("i=%d: ParseProof: %v", i, err)160 }161 if got.Hex() != want.Hex() || got.Index != want.Index || got.Total != want.Total {162 t.Errorf("i=%d: round trip lost data", i)163 }164 if !got.Verify(tree.Root(), []byte("leaf-"+strconv.Itoa(i))) {165 t.Errorf("i=%d: reparsed proof does not verify", i)166 }167 }168}169170func TestParseProofErrors(t *testing.T) {171 tests := []struct {172 name string173 in string174 want error175 }{176 {"not hex", "zz", ErrBadHex},177 {"wrong size", "abcd", ErrBadHashSize},178 {"too deep", tooDeepHex(), ErrProofTooDeep},179 }180 for _, tc := range tests {181 if _, err := ParseProof(0, 2, tc.in); err != tc.want {182 t.Errorf("%s: err = %v, want %v", tc.name, err, tc.want)183 }184 }185 // An empty sibling list is the one-leaf proof, not an error.186 p, err := ParseProof(0, 1, " ")187 if err != nil {188 t.Fatalf("empty siblings: %v", err)189 }190 one := New(leaves(1))191 if !p.Verify(one.Root(), []byte("leaf-0")) {192 t.Error("one-leaf proof with no siblings rejected")193 }194}195196func tooDeepHex() string {197 h := hex.EncodeToString(make([]byte, HashSize))198 out := h199 for i := 0; i < MaxDepth; i++ {200 out += "," + h201 }202 return out203}204205func TestTreeErrors(t *testing.T) {206 if _, err := New(nil).Proof(0); err != ErrEmptyTree {207 t.Errorf("empty tree: err = %v, want %v", err, ErrEmptyTree)208 }209 if New(nil).Root() != nil {210 t.Error("empty tree root should be nil, like Tendermint")211 }212 tree := New(leaves(3))213 for _, i := range []int{-1, 3, 99} {214 if _, err := tree.Proof(i); err != ErrIndexRange {215 t.Errorf("index %d: err = %v, want %v", i, err, ErrIndexRange)216 }217 }218}219220// New must copy its input: a caller mutating the slice afterwards cannot be221// allowed to change what the tree committed to.222func TestNewCopiesLeaves(t *testing.T) {223 ls := [][]byte{[]byte("a"), []byte("b")}224 tree := New(ls)225 before := tree.RootHex()226 ls[0][0] = 'z'227 if tree.RootHex() != before {228 t.Error("mutating the caller's slice changed the committed root")229 }230}231232// The reason this package exists. In a scheme without domain separation an233// INNER NODE hash is also a valid LEAF hash, so anyone who can choose a234// 64-byte leaf preimage can prove membership of a leaf that was never in the235// tree. This test performs that forgery against VerifySorted, then shows the236// Tendermint scheme refuses the same move.237func TestSecondPreimageForgery(t *testing.T) {238 // A 4-leaf commutative tree, built the OpenZeppelin way.239 h := make([][]byte, 4)240 for i := range h {241 s := sha256.Sum256([]byte("leaf-" + strconv.Itoa(i)))242 h[i] = s[:]243 }244 n01 := hashSortedPair(h[0], h[1])245 n23 := hashSortedPair(h[2], h[3])246 root := hashSortedPair(n01, n23)247248 // Sanity: a real leaf really does verify.249 if !VerifySorted(root, h[0], [][]byte{h[1], n23}) {250 t.Fatal("honest sorted proof rejected")251 }252253 // The forgery: present the inner node n01 as if it were a leaf hash. Its254 // preimage is the 64 bytes sorted(h0, h1), so an application whose leaves255 // can be 64 bytes long hands the attacker a membership proof for data that256 // was never committed.257 if !VerifySorted(root, n01, [][]byte{n23}) {258 t.Fatal("expected the second-preimage forgery to succeed against VerifySorted")259 }260261 // Same shape, Tendermint scheme. Leaves are tagged 0x00 and inner nodes262 // 0x01, so no leaf preimage can ever hash to an inner node, and the proof263 // is bound to an index besides.264 tree := New(leaves(4))265 inner := InnerHash(LeafHash(tree.leaves[0]), LeafHash(tree.leaves[1]))266 forged := Proof{Index: 0, Total: 2, Siblings: [][]byte{InnerHash(LeafHash(tree.leaves[2]), LeafHash(tree.leaves[3]))}}267 if forged.Verify(tree.Root(), inner) {268 t.Error("domain separation failed: an inner node was accepted as a leaf")269 }270}271272func TestLeafAndInnerHashAreTagged(t *testing.T) {273 leafOfEmpty := LeafHash(nil)274 taggedLeaf := sha256.Sum256([]byte{0x00})275 if hex.EncodeToString(leafOfEmpty) != hex.EncodeToString(taggedLeaf[:]) {276 t.Error("LeafHash is not SHA256(0x00 || leaf)")277 }278 l := make([]byte, 32)279 r := make([]byte, 32)280 r[0] = 1281 got := InnerHash(l, r)282 want := sha256.Sum256(append(append([]byte{0x01}, l...), r...))283 if hex.EncodeToString(got) != hex.EncodeToString(want[:]) {284 t.Error("InnerHash is not SHA256(0x01 || left || right)")285 }286}287288func TestSplitPointMatchesTendermint(t *testing.T) {289 // largest power of two strictly below length290 tests := []struct{ in, want int }{291 {2, 1}, {3, 2}, {4, 2}, {5, 4}, {7, 4}, {8, 4}, {9, 8}, {16, 8}, {17, 16},292 }293 for _, tc := range tests {294 if got := splitPoint(tc.in); got != tc.want {295 t.Errorf("splitPoint(%d) = %d, want %d", tc.in, got, tc.want)296 }297 }298}299Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.