asmt/trie_merkle_proof.go
trie_merkle_proof.goRaw
1/**
2 * @file
3 * @copyright defined in aergo/LICENSE.txt
4 */
5
6package trie
7
8import (
9 "bytes"
10)
11
12// MerkleProof generates a Merke proof of inclusion or non-inclusion
13// for the current trie root
14// returns the audit path, bool (key included), key, value, error
15// (key,value) can be 1- (nil, value), value of the included key, 2- the kv of a LeafNode
16// on the path of the non-included key, 3- (nil, nil) for a non-included key
17// with a DefaultLeaf on the path
18func (s *Trie) MerkleProof(key []byte) ([][]byte, bool, []byte, []byte, error) {
19 s.lock.RLock()
20 defer s.lock.RUnlock()
21 s.atomicUpdate = false // so loadChildren doesnt return a copy
22 return s.merkleProof(s.Root, key, nil, s.TrieHeight, 0)
23}
24
25// MerkleProofPast generates a Merke proof of inclusion or non-inclusion
26// for a given past trie root
27// returns the audit path, bool (key included), key, value, error
28// (key,value) can be 1- (nil, value), value of the included key, 2- the kv of a LeafNode
29// on the path of the non-included key, 3- (nil, nil) for a non-included key
30// with a DefaultLeaf on the path
31func (s *Trie) MerkleProofR(key, root []byte) ([][]byte, bool, []byte, []byte, error) {
32 s.lock.RLock()
33 defer s.lock.RUnlock()
34 s.atomicUpdate = false // so loadChildren doesnt return a copy
35 return s.merkleProof(root, key, nil, s.TrieHeight, 0)
36}
37
38// MerkleProofCompressed returns a compressed merkle proof in the given trie
39func (s *Trie) MerkleProofCompressedR(key, root []byte) ([]byte, [][]byte, int, bool, []byte, []byte, error) {
40 return s.merkleProofCompressed(key, root)
41}
42
43// MerkleProofCompressed returns a compressed merkle proof
44func (s *Trie) MerkleProofCompressed(key []byte) ([]byte, [][]byte, int, bool, []byte, []byte, error) {
45 return s.merkleProofCompressed(key, s.Root)
46}
47
48func (s *Trie) merkleProofCompressed(key, root []byte) ([]byte, [][]byte, int, bool, []byte, []byte, error) {
49 s.lock.RLock()
50 defer s.lock.RUnlock()
51 s.atomicUpdate = false // so loadChildren doesnt return a copy
52 // create a regular merkle proof and then compress it
53 mpFull, included, proofKey, proofVal, err := s.merkleProof(root, key, nil, s.TrieHeight, 0)
54 if err != nil {
55 return nil, nil, 0, true, nil, nil, err
56 }
57 // the height of the shortcut in the tree will be needed for the proof verification
58 height := len(mpFull)
59 var mp [][]byte
60 bitmap := make([]byte, len(mpFull)/8+1)
61 for i, node := range mpFull {
62 if !bytes.Equal(node, DefaultLeaf) {
63 bitSet(bitmap, i)
64 mp = append(mp, node)
65 }
66 }
67 return bitmap, mp, height, included, proofKey, proofVal, nil
68}
69
70// merkleProof generates a Merke proof of inclusion or non-inclusion
71// for a given trie root.
72// returns the audit path, bool (key included), key, value, error
73// (key,value) can be 1- (nil, value), value of the included key, 2- the kv of a LeafNode
74// on the path of the non-included key, 3- (nil, nil) for a non-included key
75// with a DefaultLeaf on the path
76func (s *Trie) merkleProof(root, key []byte, batch [][]byte, height, iBatch int) ([][]byte, bool, []byte, []byte, error) {
77 if len(root) == 0 {
78 // proove that an empty subtree is on the path of the key
79 return nil, false, nil, nil, nil
80 }
81 // Fetch the children of the node
82 batch, iBatch, lnode, rnode, isShortcut, err := s.loadChildren(root, height, iBatch, batch)
83 if err != nil {
84 return nil, false, nil, nil, err
85 }
86 if isShortcut || height == 0 {
87 if bytes.Equal(lnode[:HashLength], key) {
88 // return the value so a call to trie.Get() is not needed.
89 return nil, true, nil, rnode[:HashLength], nil
90 }
91 // Return the proof of the leaf key that is on the path of the non included key
92 return nil, false, lnode[:HashLength], rnode[:HashLength], nil
93 }
94
95 // append the left or right node to the proof
96 if bitIsSet(key, s.TrieHeight-height) {
97 mp, included, proofKey, proofValue, err := s.merkleProof(rnode, key, batch, height-1, 2*iBatch+2)
98 if err != nil {
99 return nil, false, nil, nil, err
100 }
101 if len(lnode) != 0 {
102 return append(mp, lnode[:HashLength]), included, proofKey, proofValue, nil
103 } else {
104 return append(mp, DefaultLeaf), included, proofKey, proofValue, nil
105 }
106
107 }
108 mp, included, proofKey, proofValue, err := s.merkleProof(lnode, key, batch, height-1, 2*iBatch+1)
109 if err != nil {
110 return nil, false, nil, nil, err
111 }
112 if len(rnode) != 0 {
113 return append(mp, rnode[:HashLength]), included, proofKey, proofValue, nil
114 } else {
115 return append(mp, DefaultLeaf), included, proofKey, proofValue, nil
116 }
117}
118
119// VerifyInclusion verifies that key/value is included in the trie with latest root
120func (s *Trie) VerifyInclusion(ap [][]byte, key, value []byte) bool {
121 leafHash := s.hash(key, value, []byte{byte(s.TrieHeight - len(ap))})
122 return bytes.Equal(s.Root, s.verifyInclusion(ap, 0, key, leafHash))
123}
124
125// VerifyInclusionWithRoot verifies that key/value is included in the trie with provided root
126func (s *Trie) VerifyInclusionWithRoot(root []byte, ap [][]byte, key, value []byte) bool {
127 leafHash := s.hash(key, value, []byte{byte(s.TrieHeight - len(ap))})
128 return bytes.Equal(root, s.verifyInclusion(ap, 0, key, leafHash))
129}
130
131// verifyInclusion returns the merkle root by hashing the merkle proof items
132func (s *Trie) verifyInclusion(ap [][]byte, keyIndex int, key, leafHash []byte) []byte {
133 if keyIndex == len(ap) {
134 return leafHash
135 }
136 if bitIsSet(key, keyIndex) {
137 return s.hash(ap[len(ap)-keyIndex-1], s.verifyInclusion(ap, keyIndex+1, key, leafHash))
138 }
139 return s.hash(s.verifyInclusion(ap, keyIndex+1, key, leafHash), ap[len(ap)-keyIndex-1])
140}
141
142// VerifyNonInclusion verifies a proof of non inclusion,
143// Returns true if the non-inclusion is verified
144func (s *Trie) VerifyNonInclusion(ap [][]byte, key, value, proofKey []byte) bool {
145 // Check if an empty subtree is on the key path
146 if len(proofKey) == 0 {
147 // return true if a DefaultLeaf in the key path is included in the trie
148 return bytes.Equal(s.Root, s.verifyInclusion(ap, 0, key, DefaultLeaf))
149 }
150 // Check if another kv leaf is on the key path in 2 steps
151 // 1- Check the proof leaf exists
152 if !s.VerifyInclusion(ap, proofKey, value) {
153 // the proof leaf is not included in the trie
154 return false
155 }
156 // 2- Check the proof leaf is on the key path
157 var b int
158 for b = 0; b < len(ap); b++ {
159 if bitIsSet(key, b) != bitIsSet(proofKey, b) {
160 // the proofKey leaf node is not on the path of the key
161 return false
162 }
163 }
164 // return true because we verified another leaf is on the key path
165 return true
166}
167
168// VerifyInclusionC verifies that key/value is included in the trie with latest root
169func (s *Trie) VerifyInclusionC(bitmap, key, value []byte, ap [][]byte, length int) bool {
170 leafHash := s.hash(key, value, []byte{byte(s.TrieHeight - length)})
171 return bytes.Equal(s.Root, s.verifyInclusionC(bitmap, key, leafHash, ap, length, 0, 0))
172}
173
174// VerifyInclusionWithRootC verifies that key/value is included in the trie with latest root
175func (s *Trie) VerifyInclusionWithRootC(root, bitmap, key, value []byte, ap [][]byte, length int) bool {
176 leafHash := s.hash(key, value, []byte{byte(s.TrieHeight - length)})
177 return bytes.Equal(root, s.verifyInclusionC(bitmap, key, leafHash, ap, length, 0, 0))
178}
179
180// verifyInclusionC returns the merkle root by hashing the merkle proof items
181func (s *Trie) verifyInclusionC(bitmap, key, leafHash []byte, ap [][]byte, length, keyIndex, apIndex int) []byte {
182 if keyIndex == length {
183 return leafHash
184 }
185 if bitIsSet(key, keyIndex) {
186 if bitIsSet(bitmap, length-keyIndex-1) {
187 return s.hash(ap[len(ap)-apIndex-1], s.verifyInclusionC(bitmap, key, leafHash, ap, length, keyIndex+1, apIndex+1))
188 }
189 return s.hash(DefaultLeaf, s.verifyInclusionC(bitmap, key, leafHash, ap, length, keyIndex+1, apIndex))
190
191 }
192 if bitIsSet(bitmap, length-keyIndex-1) {
193 return s.hash(s.verifyInclusionC(bitmap, key, leafHash, ap, length, keyIndex+1, apIndex+1), ap[len(ap)-apIndex-1])
194 }
195 return s.hash(s.verifyInclusionC(bitmap, key, leafHash, ap, length, keyIndex+1, apIndex), DefaultLeaf)
196}
197
198// VerifyNonInclusionC verifies a proof of non inclusion,
199// Returns true if the non-inclusion is verified
200func (s *Trie) VerifyNonInclusionC(ap [][]byte, length int, bitmap, key, value, proofKey []byte) bool {
201 // Check if an empty subtree is on the key path
202 if len(proofKey) == 0 {
203 // return true if a DefaultLeaf in the key path is included in the trie
204 return bytes.Equal(s.Root, s.verifyInclusionC(bitmap, key, DefaultLeaf, ap, length, 0, 0))
205 }
206 // Check if another kv leaf is on the key path in 2 steps
207 // 1- Check the proof leaf exists
208 if !s.VerifyInclusionC(bitmap, proofKey, value, ap, length) {
209 // the proof leaf is not included in the trie
210 return false
211 }
212 // 2- Check the proof leaf is on the key path
213 var b int
214 for b = 0; b < length; b++ {
215 if bitIsSet(key, b) != bitIsSet(proofKey, b) {
216 // the proofKey leaf node is not on the path of the key
217 return false
218 }
219 }
220 // return true because we verified another leaf is on the key path
221 return true
222}