123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219 |
- // Copyright 2015 The go-ethereum Authors
- // This file is part of the go-ethereum library.
- //
- // The go-ethereum library is free software: you can redistribute it and/or modify
- // it under the terms of the GNU Lesser General Public License as published by
- // the Free Software Foundation, either version 3 of the License, or
- // (at your option) any later version.
- //
- // The go-ethereum library is distributed in the hope that it will be useful,
- // but WITHOUT ANY WARRANTY; without even the implied warranty of
- // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- // GNU Lesser General Public License for more details.
- //
- // You should have received a copy of the GNU Lesser General Public License
- // along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
- package trie
- import (
- "bytes"
- crand "crypto/rand"
- mrand "math/rand"
- "testing"
- "time"
- "github.com/ethereum/go-ethereum/common"
- "github.com/ethereum/go-ethereum/crypto"
- "github.com/ethereum/go-ethereum/ethdb"
- )
- func init() {
- mrand.Seed(time.Now().Unix())
- }
- // makeProvers creates Merkle trie provers based on different implementations to
- // test all variations.
- func makeProvers(trie *Trie) []func(key []byte) *ethdb.MemDatabase {
- var provers []func(key []byte) *ethdb.MemDatabase
- // Create a direct trie based Merkle prover
- provers = append(provers, func(key []byte) *ethdb.MemDatabase {
- proof := ethdb.NewMemDatabase()
- trie.Prove(key, 0, proof)
- return proof
- })
- // Create a leaf iterator based Merkle prover
- provers = append(provers, func(key []byte) *ethdb.MemDatabase {
- proof := ethdb.NewMemDatabase()
- if it := NewIterator(trie.NodeIterator(key)); it.Next() && bytes.Equal(key, it.Key) {
- for _, p := range it.Prove() {
- proof.Put(crypto.Keccak256(p), p)
- }
- }
- return proof
- })
- return provers
- }
- func TestProof(t *testing.T) {
- trie, vals := randomTrie(500)
- root := trie.Hash()
- for i, prover := range makeProvers(trie) {
- for _, kv := range vals {
- proof := prover(kv.k)
- if proof == nil {
- t.Fatalf("prover %d: missing key %x while constructing proof", i, kv.k)
- }
- val, _, err := VerifyProof(root, kv.k, proof)
- if err != nil {
- t.Fatalf("prover %d: failed to verify proof for key %x: %v\nraw proof: %x", i, kv.k, err, proof)
- }
- if !bytes.Equal(val, kv.v) {
- t.Fatalf("prover %d: verified value mismatch for key %x: have %x, want %x", i, kv.k, val, kv.v)
- }
- }
- }
- }
- func TestOneElementProof(t *testing.T) {
- trie := new(Trie)
- updateString(trie, "k", "v")
- for i, prover := range makeProvers(trie) {
- proof := prover([]byte("k"))
- if proof == nil {
- t.Fatalf("prover %d: nil proof", i)
- }
- if proof.Len() != 1 {
- t.Errorf("prover %d: proof should have one element", i)
- }
- val, _, err := VerifyProof(trie.Hash(), []byte("k"), proof)
- if err != nil {
- t.Fatalf("prover %d: failed to verify proof: %v\nraw proof: %x", i, err, proof)
- }
- if !bytes.Equal(val, []byte("v")) {
- t.Fatalf("prover %d: verified value mismatch: have %x, want 'k'", i, val)
- }
- }
- }
- func TestBadProof(t *testing.T) {
- trie, vals := randomTrie(800)
- root := trie.Hash()
- for i, prover := range makeProvers(trie) {
- for _, kv := range vals {
- proof := prover(kv.k)
- if proof == nil {
- t.Fatalf("prover %d: nil proof", i)
- }
- key := proof.Keys()[mrand.Intn(proof.Len())]
- val, _ := proof.Get(key)
- proof.Delete(key)
- mutateByte(val)
- proof.Put(crypto.Keccak256(val), val)
- if _, _, err := VerifyProof(root, kv.k, proof); err == nil {
- t.Fatalf("prover %d: expected proof to fail for key %x", i, kv.k)
- }
- }
- }
- }
- // Tests that missing keys can also be proven. The test explicitly uses a single
- // entry trie and checks for missing keys both before and after the single entry.
- func TestMissingKeyProof(t *testing.T) {
- trie := new(Trie)
- updateString(trie, "k", "v")
- for i, key := range []string{"a", "j", "l", "z"} {
- proof := ethdb.NewMemDatabase()
- trie.Prove([]byte(key), 0, proof)
- if proof.Len() != 1 {
- t.Errorf("test %d: proof should have one element", i)
- }
- val, _, err := VerifyProof(trie.Hash(), []byte(key), proof)
- if err != nil {
- t.Fatalf("test %d: failed to verify proof: %v\nraw proof: %x", i, err, proof)
- }
- if val != nil {
- t.Fatalf("test %d: verified value mismatch: have %x, want nil", i, val)
- }
- }
- }
- // mutateByte changes one byte in b.
- func mutateByte(b []byte) {
- for r := mrand.Intn(len(b)); ; {
- new := byte(mrand.Intn(255))
- if new != b[r] {
- b[r] = new
- break
- }
- }
- }
- func BenchmarkProve(b *testing.B) {
- trie, vals := randomTrie(100)
- var keys []string
- for k := range vals {
- keys = append(keys, k)
- }
- b.ResetTimer()
- for i := 0; i < b.N; i++ {
- kv := vals[keys[i%len(keys)]]
- proofs := ethdb.NewMemDatabase()
- if trie.Prove(kv.k, 0, proofs); len(proofs.Keys()) == 0 {
- b.Fatalf("zero length proof for %x", kv.k)
- }
- }
- }
- func BenchmarkVerifyProof(b *testing.B) {
- trie, vals := randomTrie(100)
- root := trie.Hash()
- var keys []string
- var proofs []*ethdb.MemDatabase
- for k := range vals {
- keys = append(keys, k)
- proof := ethdb.NewMemDatabase()
- trie.Prove([]byte(k), 0, proof)
- proofs = append(proofs, proof)
- }
- b.ResetTimer()
- for i := 0; i < b.N; i++ {
- im := i % len(keys)
- if _, _, err := VerifyProof(root, []byte(keys[im]), proofs[im]); err != nil {
- b.Fatalf("key %x: %v", keys[im], err)
- }
- }
- }
- func randomTrie(n int) (*Trie, map[string]*kv) {
- trie := new(Trie)
- vals := make(map[string]*kv)
- for i := byte(0); i < 100; i++ {
- value := &kv{common.LeftPadBytes([]byte{i}, 32), []byte{i}, false}
- value2 := &kv{common.LeftPadBytes([]byte{i + 10}, 32), []byte{i}, false}
- trie.Update(value.k, value.v)
- trie.Update(value2.k, value2.v)
- vals[string(value.k)] = value
- vals[string(value2.k)] = value2
- }
- for i := 0; i < n; i++ {
- value := &kv{randBytes(32), randBytes(20), false}
- trie.Update(value.k, value.v)
- vals[string(value.k)] = value
- }
- return trie, vals
- }
- func randBytes(n int) []byte {
- r := make([]byte, n)
- crand.Read(r)
- return r
- }
|