mpt.gno
6.19 Kb · 284 lines
1package mpt
2
3import (
4 "bytes"
5 "crypto/keccak256"
6 "errors"
7
8 "gno.land/p/onbloc/encoding/rlp"
9)
10
11var (
12 ErrEmptyProof = errors.New("mpt: empty proof")
13 ErrInvalidRoot = errors.New("mpt: invalid root length")
14 ErrUnexpectedNode = errors.New("mpt: unexpected node shape")
15 ErrInvalidReference = errors.New("mpt: invalid child reference")
16 ErrPathMismatch = errors.New("mpt: path mismatch")
17 ErrValueMismatch = errors.New("mpt: value mismatch")
18 ErrKeyPresent = errors.New("mpt: key present")
19 ErrKeyAbsent = errors.New("mpt: key absent")
20 ErrUnusedProof = errors.New("mpt: unused proof nodes")
21)
22
23// EmptyRoot is keccak256(rlp("")), the root of an empty Ethereum MPT.
24func EmptyRoot() [32]byte {
25 return keccak256.Sum256(rlp.EncodeBytes(nil))
26}
27
28// Verify verifies an Ethereum Merkle Patricia Trie existence proof.
29//
30// root is the 32-byte trie root. key is expanded to nibbles and matched against
31// the proof path. proof contains raw RLP-encoded nodes, ordered from root to
32// leaf. value is the RLP string payload stored at the leaf or branch value slot.
33func Verify(root []byte, key []byte, value []byte, proof [][]byte) error {
34 result, err := walk(root, keybytesToNibbles(key), proof)
35 if err != nil {
36 return err
37 }
38
39 if !result.found {
40 return ErrKeyAbsent
41 }
42
43 if !bytes.Equal(result.value, value) {
44 return ErrValueMismatch
45 }
46
47 return nil
48}
49
50// VerifyAbsence verifies that key is absent from the trie under root.
51func VerifyAbsence(root []byte, key []byte, proof [][]byte) error {
52 result, err := walk(root, keybytesToNibbles(key), proof)
53 if err != nil {
54 return err
55 }
56
57 if result.found {
58 return ErrKeyPresent
59 }
60
61 return nil
62}
63
64type walkResult struct {
65 found bool
66 value []byte
67}
68
69// isBytesNode reports whether an RLP value carries a byte payload (a string or
70// single byte) rather than a nested list.
71func isBytesNode(v rlp.Value) bool {
72 return v.Kind == rlp.KindString || v.Kind == rlp.KindByte
73}
74
75func walk(root []byte, path []byte, proof [][]byte) (walkResult, error) {
76 if len(root) != keccak256.Size {
77 return walkResult{}, ErrInvalidRoot
78 }
79
80 if len(proof) == 0 {
81 emptyRoot := EmptyRoot()
82 if bytes.Equal(root, emptyRoot[:]) {
83 return walkResult{found: false}, nil
84 }
85
86 return walkResult{}, ErrEmptyProof
87 }
88
89 if err := matchHash(root, proof[0]); err != nil {
90 return walkResult{}, err
91 }
92
93 proofIndex := 0
94 node := proof[0]
95 pos := 0
96
97 for {
98 v, err := rlp.DecodeValue(node)
99 if err != nil {
100 return walkResult{}, err
101 }
102
103 if v.Kind != rlp.KindList {
104 return walkResult{}, ErrUnexpectedNode
105 }
106
107 switch len(v.List) {
108 case 17:
109 if pos == len(path) {
110 value := v.List[16]
111 if !isBytesNode(value) {
112 return walkResult{}, ErrUnexpectedNode
113 }
114
115 if len(value.Bytes) == 0 {
116 return finishWalk(walkResult{found: false}, proofIndex, proof)
117 }
118
119 return finishWalk(walkResult{found: true, value: value.Bytes}, proofIndex, proof)
120 }
121
122 child := v.List[path[pos]]
123 if !isBytesNode(child) {
124 return walkResult{}, ErrUnexpectedNode
125 }
126
127 if len(child.Bytes) == 0 {
128 return finishWalk(walkResult{found: false}, proofIndex, proof)
129 }
130
131 next, nextIndex, err := resolveReference(child.Bytes, proof, proofIndex)
132 if err != nil {
133 return walkResult{}, err
134 }
135
136 proofIndex = nextIndex
137 node = next
138 pos++
139
140 case 2:
141 if !isBytesNode(v.List[0]) {
142 return walkResult{}, ErrUnexpectedNode
143 }
144
145 leaf, partial, err := compactDecode(v.List[0].Bytes)
146 if err != nil {
147 return walkResult{}, err
148 }
149
150 if !hasPrefix(path[pos:], partial) {
151 return finishWalk(walkResult{found: false}, proofIndex, proof)
152 }
153
154 pos += len(partial)
155
156 if leaf {
157 if pos != len(path) {
158 return finishWalk(walkResult{found: false}, proofIndex, proof)
159 }
160
161 value := v.List[1]
162 if !isBytesNode(value) {
163 return walkResult{}, ErrUnexpectedNode
164 }
165
166 return finishWalk(walkResult{found: true, value: value.Bytes}, proofIndex, proof)
167 }
168
169 child := v.List[1]
170 if !isBytesNode(child) {
171 return walkResult{}, ErrUnexpectedNode
172 }
173
174 next, nextIndex, err := resolveReference(child.Bytes, proof, proofIndex)
175 if err != nil {
176 return walkResult{}, err
177 }
178
179 proofIndex = nextIndex
180 node = next
181
182 default:
183 return walkResult{}, ErrUnexpectedNode
184 }
185 }
186}
187
188func finishWalk(result walkResult, proofIndex int, proof [][]byte) (walkResult, error) {
189 if proofIndex != len(proof)-1 {
190 return walkResult{}, ErrUnusedProof
191 }
192
193 return result, nil
194}
195
196func resolveReference(ref []byte, proof [][]byte, proofIndex int) ([]byte, int, error) {
197 if len(ref) == 0 {
198 return nil, proofIndex, ErrInvalidReference
199 }
200
201 if len(ref) < keccak256.Size {
202 return ref, proofIndex, nil
203 }
204
205 if len(ref) != keccak256.Size {
206 return nil, proofIndex, ErrInvalidReference
207 }
208
209 nextIndex := proofIndex + 1
210 if nextIndex >= len(proof) {
211 return nil, proofIndex, ErrEmptyProof
212 }
213
214 if err := matchHash(ref, proof[nextIndex]); err != nil {
215 return nil, proofIndex, err
216 }
217
218 return proof[nextIndex], nextIndex, nil
219}
220
221func matchHash(expected []byte, encodedNode []byte) error {
222 h := keccak256.Sum256(encodedNode)
223 if !bytes.Equal(expected, h[:]) {
224 return ErrInvalidReference
225 }
226
227 return nil
228}
229
230func keybytesToNibbles(key []byte) []byte {
231 out := make([]byte, 0, len(key)*2)
232 for _, b := range key {
233 out = append(out, b>>4, b&0x0f)
234 }
235
236 return out
237}
238
239func compactDecode(encoded []byte) (bool, []byte, error) {
240 if len(encoded) == 0 {
241 return false, nil, ErrPathMismatch
242 }
243
244 flag := encoded[0] >> 4
245 if flag > 3 {
246 return false, nil, ErrPathMismatch
247 }
248
249 leaf := (flag & 2) != 0
250 odd := (flag & 1) != 0
251
252 out := make([]byte, 0, len(encoded)*2)
253 if odd {
254 out = append(out, encoded[0]&0x0f)
255 } else if encoded[0]&0x0f != 0 {
256 return false, nil, ErrPathMismatch
257 }
258
259 for i := 1; i < len(encoded); i++ {
260 out = append(out, encoded[i]>>4, encoded[i]&0x0f)
261 }
262 // extensions nodes must contain at least one path nibble.
263 // empty extension paths are non-canonical because they admit
264 // alternative proof encoding.
265 if !leaf && len(out) == 0 {
266 return false, nil, ErrPathMismatch
267 }
268
269 return leaf, out, nil
270}
271
272func hasPrefix(path []byte, prefix []byte) bool {
273 if len(prefix) > len(path) {
274 return false
275 }
276
277 for i := range prefix {
278 if path[i] != prefix[i] {
279 return false
280 }
281 }
282
283 return true
284}
