aboutsummaryrefslogtreecommitdiffstats
path: root/trie
diff options
context:
space:
mode:
Diffstat (limited to 'trie')
-rw-r--r--trie/proof.go53
-rw-r--r--trie/proof_test.go52
2 files changed, 54 insertions, 51 deletions
diff --git a/trie/proof.go b/trie/proof.go
index 298f648c4..5e886a259 100644
--- a/trie/proof.go
+++ b/trie/proof.go
@@ -18,11 +18,10 @@ package trie
import (
"bytes"
- "errors"
"fmt"
"github.com/ethereum/go-ethereum/common"
- "github.com/ethereum/go-ethereum/crypto/sha3"
+ "github.com/ethereum/go-ethereum/crypto"
"github.com/ethereum/go-ethereum/log"
"github.com/ethereum/go-ethereum/rlp"
)
@@ -36,7 +35,7 @@ import (
// contains all nodes of the longest existing prefix of the key
// (at least the root node), ending with the node that proves the
// absence of the key.
-func (t *Trie) Prove(key []byte) []rlp.RawValue {
+func (t *Trie) Prove(key []byte, fromLevel uint, proofDb DatabaseWriter) error {
// Collect all nodes on the path to key.
key = keybytesToHex(key)
nodes := []node{}
@@ -61,67 +60,63 @@ func (t *Trie) Prove(key []byte) []rlp.RawValue {
tn, err = t.resolveHash(n, nil)
if err != nil {
log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
- return nil
+ return err
}
default:
panic(fmt.Sprintf("%T: invalid node: %v", tn, tn))
}
}
hasher := newHasher(0, 0)
- proof := make([]rlp.RawValue, 0, len(nodes))
for i, n := range nodes {
// Don't bother checking for errors here since hasher panics
// if encoding doesn't work and we're not writing to any database.
n, _, _ = hasher.hashChildren(n, nil)
hn, _ := hasher.store(n, nil, false)
- if _, ok := hn.(hashNode); ok || i == 0 {
+ if hash, ok := hn.(hashNode); ok || i == 0 {
// If the node's database encoding is a hash (or is the
// root node), it becomes a proof element.
- enc, _ := rlp.EncodeToBytes(n)
- proof = append(proof, enc)
+ if fromLevel > 0 {
+ fromLevel--
+ } else {
+ enc, _ := rlp.EncodeToBytes(n)
+ if !ok {
+ hash = crypto.Keccak256(enc)
+ }
+ proofDb.Put(hash, enc)
+ }
}
}
- return proof
+ return nil
}
// VerifyProof checks merkle proofs. The given proof must contain the
// value for key in a trie with the given root hash. VerifyProof
// returns an error if the proof contains invalid trie nodes or the
// wrong value.
-func VerifyProof(rootHash common.Hash, key []byte, proof []rlp.RawValue) (value []byte, err error) {
+func VerifyProof(rootHash common.Hash, key []byte, proofDb DatabaseReader) (value []byte, err error, nodes int) {
key = keybytesToHex(key)
- sha := sha3.NewKeccak256()
- wantHash := rootHash.Bytes()
- for i, buf := range proof {
- sha.Reset()
- sha.Write(buf)
- if !bytes.Equal(sha.Sum(nil), wantHash) {
- return nil, fmt.Errorf("bad proof node %d: hash mismatch", i)
+ wantHash := rootHash[:]
+ for i := 0; ; i++ {
+ buf, _ := proofDb.Get(wantHash)
+ if buf == nil {
+ return nil, fmt.Errorf("proof node %d (hash %064x) missing", i, wantHash[:]), i
}
n, err := decodeNode(wantHash, buf, 0)
if err != nil {
- return nil, fmt.Errorf("bad proof node %d: %v", i, err)
+ return nil, fmt.Errorf("bad proof node %d: %v", i, err), i
}
keyrest, cld := get(n, key)
switch cld := cld.(type) {
case nil:
- if i != len(proof)-1 {
- return nil, fmt.Errorf("key mismatch at proof node %d", i)
- } else {
- // The trie doesn't contain the key.
- return nil, nil
- }
+ // The trie doesn't contain the key.
+ return nil, nil, i
case hashNode:
key = keyrest
wantHash = cld
case valueNode:
- if i != len(proof)-1 {
- return nil, errors.New("additional nodes at end of proof")
- }
- return cld, nil
+ return cld, nil, i + 1
}
}
- return nil, errors.New("unexpected end of proof")
}
func get(tn node, key []byte) ([]byte, node) {
diff --git a/trie/proof_test.go b/trie/proof_test.go
index 91ebcd4a5..fff313d7f 100644
--- a/trie/proof_test.go
+++ b/trie/proof_test.go
@@ -24,7 +24,8 @@ import (
"time"
"github.com/ethereum/go-ethereum/common"
- "github.com/ethereum/go-ethereum/rlp"
+ "github.com/ethereum/go-ethereum/crypto"
+ "github.com/ethereum/go-ethereum/ethdb"
)
func init() {
@@ -35,13 +36,13 @@ func TestProof(t *testing.T) {
trie, vals := randomTrie(500)
root := trie.Hash()
for _, kv := range vals {
- proof := trie.Prove(kv.k)
- if proof == nil {
+ proofs, _ := ethdb.NewMemDatabase()
+ if trie.Prove(kv.k, 0, proofs) != nil {
t.Fatalf("missing key %x while constructing proof", kv.k)
}
- val, err := VerifyProof(root, kv.k, proof)
+ val, err, _ := VerifyProof(root, kv.k, proofs)
if err != nil {
- t.Fatalf("VerifyProof error for key %x: %v\nraw proof: %x", kv.k, err, proof)
+ t.Fatalf("VerifyProof error for key %x: %v\nraw proof: %v", kv.k, err, proofs)
}
if !bytes.Equal(val, kv.v) {
t.Fatalf("VerifyProof returned wrong value for key %x: got %x, want %x", kv.k, val, kv.v)
@@ -52,16 +53,14 @@ func TestProof(t *testing.T) {
func TestOneElementProof(t *testing.T) {
trie := new(Trie)
updateString(trie, "k", "v")
- proof := trie.Prove([]byte("k"))
- if proof == nil {
- t.Fatal("nil proof")
- }
- if len(proof) != 1 {
+ proofs, _ := ethdb.NewMemDatabase()
+ trie.Prove([]byte("k"), 0, proofs)
+ if len(proofs.Keys()) != 1 {
t.Error("proof should have one element")
}
- val, err := VerifyProof(trie.Hash(), []byte("k"), proof)
+ val, err, _ := VerifyProof(trie.Hash(), []byte("k"), proofs)
if err != nil {
- t.Fatalf("VerifyProof error: %v\nraw proof: %x", err, proof)
+ t.Fatalf("VerifyProof error: %v\nproof hashes: %v", err, proofs.Keys())
}
if !bytes.Equal(val, []byte("v")) {
t.Fatalf("VerifyProof returned wrong value: got %x, want 'k'", val)
@@ -72,12 +71,18 @@ func TestVerifyBadProof(t *testing.T) {
trie, vals := randomTrie(800)
root := trie.Hash()
for _, kv := range vals {
- proof := trie.Prove(kv.k)
- if proof == nil {
- t.Fatal("nil proof")
+ proofs, _ := ethdb.NewMemDatabase()
+ trie.Prove(kv.k, 0, proofs)
+ if len(proofs.Keys()) == 0 {
+ t.Fatal("zero length proof")
}
- mutateByte(proof[mrand.Intn(len(proof))])
- if _, err := VerifyProof(root, kv.k, proof); err == nil {
+ keys := proofs.Keys()
+ key := keys[mrand.Intn(len(keys))]
+ node, _ := proofs.Get(key)
+ proofs.Delete(key)
+ mutateByte(node)
+ proofs.Put(crypto.Keccak256(node), node)
+ if _, err, _ := VerifyProof(root, kv.k, proofs); err == nil {
t.Fatalf("expected proof to fail for key %x", kv.k)
}
}
@@ -104,8 +109,9 @@ func BenchmarkProve(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
kv := vals[keys[i%len(keys)]]
- if trie.Prove(kv.k) == nil {
- b.Fatalf("nil proof for %x", kv.k)
+ proofs, _ := ethdb.NewMemDatabase()
+ if trie.Prove(kv.k, 0, proofs); len(proofs.Keys()) == 0 {
+ b.Fatalf("zero length proof for %x", kv.k)
}
}
}
@@ -114,16 +120,18 @@ func BenchmarkVerifyProof(b *testing.B) {
trie, vals := randomTrie(100)
root := trie.Hash()
var keys []string
- var proofs [][]rlp.RawValue
+ var proofs []*ethdb.MemDatabase
for k := range vals {
keys = append(keys, k)
- proofs = append(proofs, trie.Prove([]byte(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 {
+ if _, err, _ := VerifyProof(root, []byte(keys[im]), proofs[im]); err != nil {
b.Fatalf("key %x: %v", keys[im], err)
}
}
generated by cgit (git 2.34.1) at 2024-11-12 16:30:51 +0800