-
Notifications
You must be signed in to change notification settings - Fork 17
/
smt_merkle_proof.go
221 lines (202 loc) · 8.76 KB
/
smt_merkle_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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
/**
* @file
* @copyright defined in aergo/LICENSE.txt
*/
package trie
import (
"bytes"
"github.com/MadBase/MadNet/constants"
"github.com/dgraph-io/badger/v2"
)
// MerkleProof generates a Merkle proof of inclusion or non-inclusion
// for the current trie root
// returns the audit path, bool (key included), key, value, error
// (key,value) can be 1- (nil, value), value of the included key, 2- the kv of a LeafNode
// on the path of the non-included key, 3- (nil, nil) for a non-included key
// with a DefaultLeaf on the path
func (s *SMT) MerkleProof(txn *badger.Txn, key []byte) ([][]byte, bool, []byte, []byte, error) {
s.lock.RLock()
defer s.lock.RUnlock()
return s.merkleProof(txn, s.Root, key, nil, s.TrieHeight, 0)
}
// MerkleProofR generates a Merkle proof of inclusion or non-inclusion
// for a given past trie root
// returns the audit path, bool (key included), key, value, error
// (key,value) can be 1- (nil, value), value of the included key, 2- the kv of a LeafNode
// on the path of the non-included key, 3- (nil, nil) for a non-included key
// with a DefaultLeaf on the path
func (s *SMT) MerkleProofR(txn *badger.Txn, key, root []byte) ([][]byte, bool, []byte, []byte, error) {
s.lock.RLock()
defer s.lock.RUnlock()
return s.merkleProof(txn, root, key, nil, s.TrieHeight, 0)
}
// MerkleProofCompressedR returns a compressed merkle proof in the given trie
func (s *SMT) MerkleProofCompressedR(txn *badger.Txn, key, root []byte) ([]byte, [][]byte, int, bool, []byte, []byte, error) {
return s.merkleProofCompressed(txn, key, root)
//bm, mp, h, enc, _, pv, err := s.merkleProofCompressed(txn, key, root)
//return bm, mp, h, enc, key, pv, err
}
// MerkleProofCompressed returns a compressed merkle proof
func (s *SMT) MerkleProofCompressed(txn *badger.Txn, key []byte) ([]byte, [][]byte, int, bool, []byte, []byte, error) {
return s.merkleProofCompressed(txn, key, s.Root) //todo this is broken in library
// bm, mp, h, enc, _, pv, err := s.merkleProofCompressed(txn, key, s.Root) //todo this is broken in library
// return bm, mp, h, enc, key, pv, err
}
func (s *SMT) merkleProofCompressed(txn *badger.Txn, key, root []byte) ([]byte, [][]byte, int, bool, []byte, []byte, error) {
s.lock.RLock()
defer s.lock.RUnlock()
// create a regular merkle proof and then compress it
mpFull, included, proofKey, proofVal, err := s.merkleProof(txn, root, key, nil, s.TrieHeight, 0)
if err != nil {
return nil, nil, 0, true, nil, nil, err
}
// the height of the shortcut in the tree will be needed for the proof verification
height := len(mpFull)
var mp [][]byte
bitmap := make([]byte, len(mpFull)/8+1)
for i, node := range mpFull {
if !bytes.Equal(node, DefaultLeaf) {
bitSet(bitmap, i)
mp = append(mp, node)
}
}
return bitmap, mp, height, included, proofKey, proofVal, nil
}
// merkleProof generates a Merkle proof of inclusion or non-inclusion
// for a given trie root.
// returns the audit path, bool (key included), key, value, error
// (key,value) can be 1- (nil, value), value of the included key, 2- the kv of a LeafNode
// on the path of the non-included key, 3- (nil, nil) for a non-included key
// with a DefaultLeaf on the path
func (s *SMT) merkleProof(txn *badger.Txn, root, key []byte, batch [][]byte, height, iBatch int) ([][]byte, bool, []byte, []byte, error) {
if len(root) == 0 {
// prove that an empty subtree is on the path of the key
return nil, false, nil, nil, nil
}
// Fetch the children of the node
batch, iBatch, lnode, rnode, isShortcut, err := s.loadChildren(txn, root, height, iBatch, batch)
if err != nil {
return nil, false, nil, nil, err
}
if isShortcut || height == 0 {
if bytes.Equal(lnode[:constants.HashLen], key) {
// return the value so a call to trie.Get() is not needed.
return nil, true, nil, rnode[:constants.HashLen], nil
}
// Return the proof of the leaf key that is on the path of the non included key
return nil, false, lnode[:constants.HashLen], rnode[:constants.HashLen], nil
}
// append the left or right node to the proof
if bitIsSet(key, s.TrieHeight-height) {
mp, included, proofKey, proofValue, err := s.merkleProof(txn, rnode, key, batch, height-1, 2*iBatch+2)
if err != nil {
return nil, false, nil, nil, err
}
if len(lnode) != 0 {
return append(mp, lnode[:constants.HashLen]), included, proofKey, proofValue, nil
} else {
return append(mp, DefaultLeaf), included, proofKey, proofValue, nil
}
}
mp, included, proofKey, proofValue, err := s.merkleProof(txn, lnode, key, batch, height-1, 2*iBatch+1)
if err != nil {
return nil, false, nil, nil, err
}
if len(rnode) != 0 {
return append(mp, rnode[:constants.HashLen]), included, proofKey, proofValue, nil
} else {
return append(mp, DefaultLeaf), included, proofKey, proofValue, nil
}
}
// VerifyInclusion verifies that key/value is included in the trie with latest root
func (s *SMT) VerifyInclusion(ap [][]byte, key, value []byte) bool {
leafHash := s.hash(key, value, []byte{byte(s.TrieHeight - len(ap))})
return bytes.Equal(s.Root, s.verifyInclusion(ap, 0, key, leafHash))
}
// verifyInclusion returns the merkle root by hashing the merkle proof items
func (s *SMT) verifyInclusion(ap [][]byte, keyIndex int, key, leafHash []byte) []byte {
if keyIndex == len(ap) {
return leafHash
}
if bitIsSet(key, keyIndex) {
return s.hash(ap[len(ap)-keyIndex-1], s.verifyInclusion(ap, keyIndex+1, key, leafHash))
}
return s.hash(s.verifyInclusion(ap, keyIndex+1, key, leafHash), ap[len(ap)-keyIndex-1])
}
// VerifyNonInclusion verifies a proof of non inclusion,
// Returns true if the non-inclusion is verified
func (s *SMT) VerifyNonInclusion(ap [][]byte, key, value, proofKey []byte) bool {
// Check if an empty subtree is on the key path
if len(proofKey) == 0 {
// return true if a DefaultLeaf in the key path is included in the trie
return bytes.Equal(s.Root, s.verifyInclusion(ap, 0, key, DefaultLeaf))
}
// Check if another kv leaf is on the key path in 2 steps
// 1- Check the proof leaf exists
if !s.VerifyInclusion(ap, proofKey, value) {
// the proof leaf is not included in the trie
return false
}
// 2- Check the proof leaf is on the key path
var b int
for b = 0; b < len(ap); b++ {
if bitIsSet(key, b) != bitIsSet(proofKey, b) {
// the proofKey leaf node is not on the path of the key
return false
}
}
// return true because we verified another leaf is on the key path
return true
}
// VerifyInclusionCR verifies that key/value is included in the trie with latest root
func (s *SMT) VerifyInclusionCR(root []byte, bitmap, key, value []byte, ap [][]byte, length int) bool {
leafHash := s.hash(key, value, []byte{byte(s.TrieHeight - length)})
// fmt.Printf("leafhash %x\n", leafHash)
return bytes.Equal(root, s.verifyInclusionC(bitmap, key, leafHash, ap, length, 0, 0))
}
// VerifyInclusionC verifies that key/value is included in the trie with latest root
func (s *SMT) VerifyInclusionC(bitmap, key, value []byte, ap [][]byte, length int) bool {
leafHash := s.hash(key, value, []byte{byte(s.TrieHeight - length)})
return bytes.Equal(s.Root, s.verifyInclusionC(bitmap, key, leafHash, ap, length, 0, 0))
}
// verifyInclusionC returns the merkle root by hashing the merkle proof items
func (s *SMT) verifyInclusionC(bitmap, key, leafHash []byte, ap [][]byte, length, keyIndex, apIndex int) []byte {
if keyIndex == length {
return leafHash
}
if bitIsSet(key, keyIndex) {
if bitIsSet(bitmap, length-keyIndex-1) {
return s.hash(ap[len(ap)-apIndex-1], s.verifyInclusionC(bitmap, key, leafHash, ap, length, keyIndex+1, apIndex+1))
}
return s.hash(DefaultLeaf, s.verifyInclusionC(bitmap, key, leafHash, ap, length, keyIndex+1, apIndex))
}
if bitIsSet(bitmap, length-keyIndex-1) {
return s.hash(s.verifyInclusionC(bitmap, key, leafHash, ap, length, keyIndex+1, apIndex+1), ap[len(ap)-apIndex-1])
}
return s.hash(s.verifyInclusionC(bitmap, key, leafHash, ap, length, keyIndex+1, apIndex), DefaultLeaf)
}
// VerifyNonInclusionC verifies a proof of non inclusion,
// Returns true if the non-inclusion is verified
func (s *SMT) VerifyNonInclusionC(ap [][]byte, length int, bitmap, key, value, proofKey []byte) bool {
// Check if an empty subtree is on the key path
if len(proofKey) == 0 {
// return true if a DefaultLeaf in the key path is included in the trie
return bytes.Equal(s.Root, s.verifyInclusionC(bitmap, key, DefaultLeaf, ap, length, 0, 0))
}
// Check if another kv leaf is on the key path in 2 steps
// 1- Check the proof leaf exists
if !s.VerifyInclusionC(bitmap, proofKey, value, ap, length) {
// the proof leaf is not included in the trie
return false
}
// 2- Check the proof leaf is on the key path
var b int
for b = 0; b < length; b++ {
if bitIsSet(key, b) != bitIsSet(proofKey, b) {
// the proofKey leaf node is not on the path of the key
return false
}
}
// return true because we verified another leaf is on the key path
return true
}