-
Notifications
You must be signed in to change notification settings - Fork 20
/
zk_trie_proof.go
100 lines (84 loc) · 2.18 KB
/
zk_trie_proof.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package trie
import (
"bytes"
"fmt"
zkt "github.com/scroll-tech/zktrie/types"
)
var magicSMTBytes []byte
func init() {
magicSMTBytes = []byte("THIS IS SOME MAGIC BYTES FOR SMT m1rRXgP2xpDI")
}
func ProofMagicBytes() []byte { return magicSMTBytes }
// DecodeProof try to decode a node bytes, return can be nil for any non-node data (magic code)
func DecodeSMTProof(data []byte) (*Node, error) {
if bytes.Equal(magicSMTBytes, data) {
//skip magic bytes node
return nil, nil
}
return NewNodeFromBytes(data)
}
// Prove constructs a merkle proof for SMT, it respect the protocol used by the ethereum-trie
// but save the node data with a compact form
func (mt *ZkTrieImpl) Prove(kHash *zkt.Hash, fromLevel uint, writeNode func(*Node) error) error {
// force root hash calculation if needed
if _, err := mt.Root(); err != nil {
return err
}
mt.lock.RLock()
defer mt.lock.RUnlock()
path := getPath(mt.maxLevels, kHash[:])
var nodes []*Node
var lastN *Node
tn := mt.rootKey
for i := 0; i < mt.maxLevels; i++ {
n, err := mt.getNode(tn)
if err != nil {
fmt.Println("get node fail", err, tn.Hex(),
lastN.ChildL.Hex(),
lastN.ChildR.Hex(),
path,
i,
)
return err
}
nodeHash := tn
lastN = n
finished := true
switch n.Type {
case NodeTypeEmpty_New:
case NodeTypeLeaf_New:
// notice even we found a leaf whose entry didn't match the expected k,
// we still include it as the proof of absence
case NodeTypeBranch_0, NodeTypeBranch_1, NodeTypeBranch_2, NodeTypeBranch_3:
finished = false
if path[i] {
tn = n.ChildR
} else {
tn = n.ChildL
}
case NodeTypeEmpty, NodeTypeLeaf, NodeTypeParent:
panic("encounter deprecated node types")
default:
return ErrInvalidNodeFound
}
nCopy := n.Copy()
nCopy.nodeHash = nodeHash
nodes = append(nodes, nCopy)
if finished {
break
}
}
for _, n := range nodes {
if fromLevel > 0 {
fromLevel--
continue
}
// TODO: notice here we may have broken some implicit on the proofDb:
// the key is not kecca(value) and it even can not be derived from
// the value by any means without a actually decoding
if err := writeNode(n); err != nil {
return err
}
}
return nil
}