proof.gno
19.48 Kb · 654 lines
1package ics23
2
3import (
4 "bytes"
5 "errors"
6
7 "gno.land/p/nt/ufmt/v0"
8)
9
10type CommitmentProof interface {
11 GetExist() *ExistenceProof
12 GetNonexist() *NonExistenceProof
13}
14
15type CommitmentProof_Exist struct {
16 Exist *ExistenceProof
17}
18
19var _ CommitmentProof = CommitmentProof_Exist{}
20
21func (c CommitmentProof_Exist) GetExist() *ExistenceProof { return c.Exist }
22func (c CommitmentProof_Exist) GetNonexist() *NonExistenceProof { return nil }
23
24// ExistenceProof takes a key and a value and a set of steps to perform on it.
25// The result of peforming all these steps will provide a "root hash", which can
26// be compared to the value in a header.
27//
28// Since it is computationally infeasible to produce a hash collission for any of the used
29// cryptographic hash functions, if someone can provide a series of operations to transform
30// a given key and value into a root hash that matches some trusted root, these key and values
31// must be in the referenced merkle tree.
32//
33// The only possible issue is maliablity in LeafOp, such as providing extra prefix data,
34// which should be controlled by a spec. Eg. with lengthOp as NONE,
35// prefix = FOO, key = BAR, value = CHOICE
36// and
37// prefix = F, key = OOBAR, value = CHOICE
38// would produce the same value.
39//
40// With LengthOp this is tricker but not impossible. Which is why the "leafPrefixEqual" field
41// in the ProofSpec is valuable to prevent this mutability. And why all trees should
42// length-prefix the data before hashing it.
43type ExistenceProof struct {
44 Key []byte
45 Value []byte
46 Leaf *LeafOp
47 Path []*InnerOp
48}
49
50// LeafOp represents the raw key-value data we wish to prove, and
51// must be flexible to represent the internal transformation from
52// the original key-value pairs into the basis hash, for many existing
53// merkle trees.
54//
55// key and value are passed in. So that the signature of this operation is:
56// leafOp(key, value) -> output
57//
58// To process this, first prehash the keys and values if needed (ANY means no hash in this case):
59// hkey = prehashKey(key)
60// hvalue = prehashValue(value)
61//
62// Then combine the bytes, and hash it
63// output = hash(prefix || length(hkey) || hkey || length(hvalue) || hvalue)
64type LeafOp struct {
65 Hash HashOp
66 PrehashKey HashOp
67 PrehashValue HashOp
68 Length LengthOp
69 // prefix is a fixed bytes that may optionally be included at the beginning to differentiate
70 // a leaf node from an inner node.
71 Prefix []byte
72}
73
74func (m *LeafOp) GetHash() HashOp {
75 if m != nil {
76 return m.Hash
77 }
78 return HashOp_NO_HASH
79}
80
81func (m *LeafOp) GetPrefix() []byte {
82 return m.Prefix
83}
84
85// InnerOp represents a merkle-proof step that is not a leaf.
86// It represents concatenating two children and hashing them to provide the next result.
87//
88// The result of the previous step is passed in, so the signature of this op is:
89// innerOp(child) -> output
90//
91// The result of applying InnerOp should be:
92// output = op.hash(op.prefix || child || op.suffix)
93//
94// where the || operator is concatenation of binary data,
95// and child is the result of hashing all the tree below this step.
96//
97// Any special data, like prepending child with the length, or prepending the entire operation with
98// some value to differentiate from leaf nodes, should be included in prefix and suffix.
99// If either of prefix or suffix is empty, we just treat it as an empty string
100type InnerOp struct {
101 Hash HashOp
102 Prefix []byte
103 Suffix []byte
104}
105
106func (m *InnerOp) GetHash() HashOp {
107 if m != nil {
108 return m.Hash
109 }
110 return HashOp_NO_HASH
111}
112
113func (m *InnerOp) GetPrefix() []byte {
114 return m.Prefix
115}
116
117// Verify does all checks to ensure this proof proves this key, value -> root
118// and matches the spec.
119func (p *ExistenceProof) Verify(spec *ProofSpec, root, key, value []byte) error {
120 if err := p.CheckAgainstSpec(spec); err != nil {
121 return err
122 }
123
124 if !bytes.Equal(key, p.Key) {
125 return ufmt.Errorf("provided key doesn't match proof")
126 }
127 if !bytes.Equal(value, p.Value) {
128 return ufmt.Errorf("provided value doesn't match proof")
129 }
130
131 calc, err := p.calculate(spec)
132 if err != nil {
133 return ufmt.Errorf("error calculating root, %v", err)
134 }
135 if !bytes.Equal(root, calc) {
136 return ufmt.Errorf("calculated root doesn't match provided root")
137 }
138
139 return nil
140}
141
142// Calculate determines the root hash that matches the given proof.
143// You must validate the result is what you have in a header.
144// Returns error if the calculations cannot be performed.
145func (p *ExistenceProof) Calculate() ([]byte, error) {
146 return p.calculate(nil)
147}
148
149func (p *ExistenceProof) calculate(spec *ProofSpec) ([]byte, error) {
150 if p.Leaf == nil {
151 return nil, errors.New("existence Proof needs defined LeafOp")
152 }
153
154 // leaf step takes the key and value as input
155 res, err := p.Leaf.Apply(p.Key, p.Value)
156 if err != nil {
157 return nil, ufmt.Errorf("leaf, %v", err)
158 }
159
160 // the rest just take the output of the last step (reducing it)
161 for _, step := range p.Path {
162 res, err = step.Apply(res)
163 if err != nil {
164 return nil, ufmt.Errorf("inner, %v", err)
165 }
166 if spec != nil {
167 if len(res) > int(spec.InnerSpec.ChildSize) && int(spec.InnerSpec.ChildSize) >= 32 {
168 return nil, ufmt.Errorf("inner, %v", err)
169 }
170 }
171 }
172 return res, nil
173}
174
175type CommitmentProof_Nonexist struct {
176 Nonexist *NonExistenceProof
177}
178
179var _ CommitmentProof = CommitmentProof_Nonexist{}
180
181func (c CommitmentProof_Nonexist) GetExist() *ExistenceProof { return nil }
182func (c CommitmentProof_Nonexist) GetNonexist() *NonExistenceProof { return c.Nonexist }
183
184// NonExistenceProof takes a proof of two neighbors, one left of the desired key,
185// one right of the desired key. If both proofs are valid AND they are neighbors,
186// then there is no valid proof for the given key.
187type NonExistenceProof struct {
188 Key []byte
189 Left *ExistenceProof
190 Right *ExistenceProof
191}
192
193// Calculate determines the root hash that matches the given nonexistence proof.
194// You must validate the result is what you have in a header.
195// Returns error if the calculations cannot be performed.
196func (p *NonExistenceProof) Calculate() ([]byte, error) {
197 // A Nonexist proof may have left or right proof nil
198 switch {
199 case p.Left != nil:
200 return p.Left.Calculate()
201 case p.Right != nil:
202 return p.Right.Calculate()
203 default:
204 return nil, errors.New("nonexistence proof has empty Left and Right proof")
205 }
206}
207
208// CheckAgainstSpec will verify the leaf and all path steps are in the format defined in spec
209func (p *ExistenceProof) CheckAgainstSpec(spec *ProofSpec) error {
210 leaf := p.Leaf
211 if leaf == nil {
212 return errors.New("existence Proof needs defined LeafOp")
213 }
214 if err := leaf.CheckAgainstSpec(spec); err != nil {
215 return ufmt.Errorf("leaf, %v", err)
216 }
217 if spec.MinDepth > 0 && len(p.Path) < int(spec.MinDepth) {
218 return ufmt.Errorf("innerOps depth too short: %d", len(p.Path))
219 }
220
221 maxDepth := spec.MaxDepth
222 if maxDepth == 0 {
223 maxDepth = 128
224 }
225
226 if len(p.Path) > int(maxDepth) {
227 return ufmt.Errorf("innerOps depth too long: %d", len(p.Path))
228 }
229
230 layerNum := 1
231
232 for _, inner := range p.Path {
233 if err := inner.CheckAgainstSpec(spec, layerNum); err != nil {
234 return ufmt.Errorf("inner, %v", err)
235 }
236 layerNum++
237 }
238 return nil
239}
240
241// If we should prehash the key before comparison, do so; otherwise, return the key. Prehashing
242// changes lexical comparison, so we do so before comparison if the spec sets
243// `PrehashKeyBeforeComparison`.
244func keyForComparison(spec *ProofSpec, key []byte) []byte {
245 if !spec.PrehashKeyBeforeComparison {
246 return key
247 }
248 hash, _ := doHashOrNoop(spec.LeafSpec.PrehashKey, key)
249 return hash
250}
251
252// Verify does all checks to ensure the proof has valid non-existence proofs,
253// and they ensure the given key is not in the CommitmentState
254func (p *NonExistenceProof) Verify(spec *ProofSpec, root, key []byte) error {
255 // ensure the existence proofs are valid
256 var leftKey, rightKey []byte
257 if p.Left != nil {
258 if err := p.Left.Verify(spec, root, p.Left.Key, p.Left.Value); err != nil {
259 return ufmt.Errorf("left proof, %v", err)
260 }
261 leftKey = p.Left.Key
262 }
263 if p.Right != nil {
264 if err := p.Right.Verify(spec, root, p.Right.Key, p.Right.Value); err != nil {
265 return ufmt.Errorf("right proof, %v", err)
266 }
267 rightKey = p.Right.Key
268 }
269
270 // If both proofs are missing, this is not a valid proof
271 if leftKey == nil && rightKey == nil {
272 return errors.New("both left and right proofs missing")
273 }
274
275 // Ensure in valid range
276 if rightKey != nil {
277 if bytes.Compare(keyForComparison(spec, key), keyForComparison(spec, rightKey)) >= 0 {
278 return errors.New("key is not left of right proof")
279 }
280 }
281
282 if leftKey != nil {
283 if bytes.Compare(keyForComparison(spec, key), keyForComparison(spec, leftKey)) <= 0 {
284 return errors.New("key is not right of left proof")
285 }
286 }
287
288 switch {
289 case leftKey == nil:
290 isLeftMost, err := IsLeftMost(spec.InnerSpec, p.Right.Path)
291 if err != nil {
292 return err
293 }
294
295 if !isLeftMost {
296 return errors.New("left proof missing, right proof must be left-most")
297 }
298 case rightKey == nil:
299 isRightMost, err := IsRightMost(spec.InnerSpec, p.Left.Path)
300 if err != nil {
301 return err
302 }
303
304 if !isRightMost {
305 return errors.New("right proof missing, left proof must be right-most")
306 }
307 default:
308 isLeftNeighbor, err := IsLeftNeighbor(spec.InnerSpec, p.Left.Path, p.Right.Path)
309 if err != nil {
310 return err
311 }
312
313 if !isLeftNeighbor {
314 return errors.New("right proof missing, left proof must be right-most")
315 }
316 }
317
318 return nil
319}
320
321// IsLeftMost returns true if this is the left-most path in the tree, excluding placeholder (empty child) nodes
322func IsLeftMost(spec *InnerSpec, path []*InnerOp) (bool, error) {
323 minPrefix, maxPrefix, suffix, err := getPadding(spec, 0)
324 if err != nil {
325 return false, err
326 }
327
328 // ensure every step has a prefix and suffix defined to be leftmost, unless it is a placeholder node
329 for _, step := range path {
330 if !hasPadding(step, minPrefix, maxPrefix, suffix) {
331 leftBranchesAreEmpty, err := leftBranchesAreEmpty(spec, step)
332 if err != nil {
333 return false, err
334 }
335
336 if !leftBranchesAreEmpty {
337 return false, nil
338 }
339 }
340 }
341 return true, nil
342}
343
344// IsRightMost returns true if this is the right-most path in the tree, excluding placeholder (empty child) nodes
345func IsRightMost(spec *InnerSpec, path []*InnerOp) (bool, error) {
346 last := len(spec.ChildOrder) - 1
347 minPrefix, maxPrefix, suffix, err := getPadding(spec, int32(last))
348 if err != nil {
349 return false, err
350 }
351
352 // ensure every step has a prefix and suffix defined to be rightmost, unless it is a placeholder node
353 for _, step := range path {
354 if !hasPadding(step, minPrefix, maxPrefix, suffix) {
355 rightBranchesAreEmpty, err := rightBranchesAreEmpty(spec, step)
356 if err != nil {
357 return false, err
358 }
359
360 if !rightBranchesAreEmpty {
361 return false, nil
362 }
363 }
364 }
365 return true, nil
366}
367
368// IsLeftNeighbor returns true if `right` is the next possible path right of `left`
369//
370// Find the common suffix from the Left.Path and Right.Path and remove it. We have LPath and RPath now, which must be neighbors.
371// Validate that LPath[len-1] is the left neighbor of RPath[len-1]
372// For step in LPath[0..len-1], validate step is right-most node
373// For step in RPath[0..len-1], validate step is left-most node
374func IsLeftNeighbor(spec *InnerSpec, left []*InnerOp, right []*InnerOp) (bool, error) {
375 if len(left) == 0 || len(right) == 0 {
376 return false, nil
377 }
378
379 // count common tail (from end, near root)
380 left, topleft := left[:len(left)-1], left[len(left)-1]
381 right, topright := right[:len(right)-1], right[len(right)-1]
382 for bytes.Equal(topleft.Prefix, topright.Prefix) && bytes.Equal(topleft.Suffix, topright.Suffix) {
383 if len(left) == 0 || len(right) == 0 {
384 return false, nil
385 }
386 left, topleft = left[:len(left)-1], left[len(left)-1]
387 right, topright = right[:len(right)-1], right[len(right)-1]
388 }
389
390 // now topleft and topright are the first divergent nodes
391 // make sure they are left and right of each other
392 ok, err := isLeftStep(spec, topleft, topright)
393 if err != nil {
394 return false, err
395 }
396 if !ok {
397 return false, nil
398 }
399
400 // left and right are remaining children below the split,
401 // ensure left child is the rightmost path, and visa versa
402 isRightMost, err := IsRightMost(spec, left)
403 if err != nil {
404 return false, err
405 }
406 if !isRightMost {
407 return false, nil
408 }
409
410 isLeftMost, err := IsLeftMost(spec, right)
411 if err != nil {
412 return false, err
413 }
414 if !isLeftMost {
415 return false, nil
416 }
417 return true, nil
418}
419
420// isLeftStep assumes left and right have common parents
421// checks if left is exactly one slot to the left of right
422func isLeftStep(spec *InnerSpec, left *InnerOp, right *InnerOp) (bool, error) {
423 leftidx, err := orderFromPadding(spec, left)
424 if err != nil {
425 return false, err
426 }
427 rightidx, err := orderFromPadding(spec, right)
428 if err != nil {
429 return false, err
430 }
431
432 // TODO: is it possible there are empty (nil) children???
433 return rightidx == leftidx+1, nil
434}
435
436// checks if an op has the expected padding
437func hasPadding(op *InnerOp, minPrefix, maxPrefix, suffix int) bool {
438 if len(op.Prefix) < minPrefix {
439 return false
440 }
441 if len(op.Prefix) > maxPrefix {
442 return false
443 }
444 return len(op.Suffix) == suffix
445}
446
447// getPadding determines prefix and suffix with the given spec and position in the tree
448func getPadding(spec *InnerSpec, branch int32) (minPrefix, maxPrefix, suffix int, err error) {
449 idx, err := getPosition(spec.ChildOrder, branch)
450 if err != nil {
451 return 0, 0, 0, err
452 }
453
454 // count how many children are in the prefix
455 prefix := idx * int(spec.ChildSize)
456 minPrefix = prefix + int(spec.MinPrefixLength)
457 maxPrefix = prefix + int(spec.MaxPrefixLength)
458
459 // count how many children are in the suffix
460 suffix = (len(spec.ChildOrder) - 1 - idx) * int(spec.ChildSize)
461 return minPrefix, maxPrefix, suffix, nil
462}
463
464// leftBranchesAreEmpty returns true if the padding bytes correspond to all empty siblings
465// on the left side of a branch, ie. it's a valid placeholder on a leftmost path
466func leftBranchesAreEmpty(spec *InnerSpec, op *InnerOp) (bool, error) {
467 idx, err := orderFromPadding(spec, op)
468 if err != nil {
469 return false, err
470 }
471 // count branches to left of this
472 leftBranches := int(idx)
473 if leftBranches == 0 {
474 return false, nil
475 }
476 // compare prefix with the expected number of empty branches
477 actualPrefix := len(op.Prefix) - leftBranches*int(spec.ChildSize)
478 if actualPrefix < 0 {
479 return false, nil
480 }
481 for i := 0; i < leftBranches; i++ {
482 idx, err := getPosition(spec.ChildOrder, int32(i))
483 if err != nil {
484 return false, err
485 }
486
487 from := actualPrefix + idx*int(spec.ChildSize)
488 if !bytes.Equal(spec.EmptyChild, op.Prefix[from:from+int(spec.ChildSize)]) {
489 return false, nil
490 }
491 }
492 return true, nil
493}
494
495// rightBranchesAreEmpty returns true if the padding bytes correspond to all empty siblings
496// on the right side of a branch, ie. it's a valid placeholder on a rightmost path
497func rightBranchesAreEmpty(spec *InnerSpec, op *InnerOp) (bool, error) {
498 idx, err := orderFromPadding(spec, op)
499 if err != nil {
500 return false, err
501 }
502 // count branches to right of this one
503 rightBranches := len(spec.ChildOrder) - 1 - int(idx)
504 if rightBranches == 0 {
505 return false, nil
506 }
507 // compare suffix with the expected number of empty branches
508 if len(op.Suffix) != rightBranches*int(spec.ChildSize) {
509 return false, nil // sanity check
510 }
511 for i := 0; i < rightBranches; i++ {
512 idx, err := getPosition(spec.ChildOrder, int32(i))
513 if err != nil {
514 return false, err
515 }
516
517 from := idx * int(spec.ChildSize)
518 if !bytes.Equal(spec.EmptyChild, op.Suffix[from:from+int(spec.ChildSize)]) {
519 return false, nil
520 }
521 }
522 return true, nil
523}
524
525// getPosition checks where the branch is in the order and returns
526// the index of this branch
527func getPosition(order []int32, branch int32) (int, error) {
528 if branch < 0 || int(branch) >= len(order) {
529 return -1, ufmt.Errorf("invalid branch: %d", branch)
530 }
531 for i, item := range order {
532 if branch == item {
533 return i, nil
534 }
535 }
536
537 return -1, ufmt.Errorf("branch %d not found in order %v", branch, order)
538}
539
540// This will look at the proof and determine which order it is...
541// So we can see if it is branch 0, 1, 2 etc... to determine neighbors
542func orderFromPadding(spec *InnerSpec, inner *InnerOp) (int32, error) {
543 maxbranch := int32(len(spec.ChildOrder))
544 for branch := int32(0); branch < maxbranch; branch++ {
545 minp, maxp, suffix, err := getPadding(spec, branch)
546 if err != nil {
547 return 0, err
548 }
549 if hasPadding(inner, minp, maxp, suffix) {
550 return branch, nil
551 }
552 }
553 return 0, errors.New("cannot find any valid spacing for this node")
554}
555
556// Equal returns true if the two ProofSpec instances are deeply equal across
557// every field. Use this when you need a strict content comparison (e.g. to
558// detect attempts at substituting a different spec for an existing client).
559// For the looser, "same shape" comparison historically used to route proof
560// verification through IavlSpec/TendermintSpec, use SpecEquals instead.
561func (p *ProofSpec) Equal(other *ProofSpec) bool {
562 if p == nil || other == nil {
563 return p == other
564 }
565 if p.MaxDepth != other.MaxDepth ||
566 p.MinDepth != other.MinDepth ||
567 p.PrehashKeyBeforeComparison != other.PrehashKeyBeforeComparison {
568 return false
569 }
570 if !p.LeafSpec.Equal(other.LeafSpec) {
571 return false
572 }
573 return p.InnerSpec.Equal(other.InnerSpec)
574}
575
576// Equal returns true if the two LeafOp instances are deeply equal.
577func (p *LeafOp) Equal(other *LeafOp) bool {
578 if p == nil || other == nil {
579 return p == other
580 }
581 return p.Hash == other.Hash &&
582 p.PrehashKey == other.PrehashKey &&
583 p.PrehashValue == other.PrehashValue &&
584 p.Length == other.Length &&
585 bytes.Equal(p.Prefix, other.Prefix)
586}
587
588// Equal returns true if the two InnerSpec instances are deeply equal.
589func (p *InnerSpec) Equal(other *InnerSpec) bool {
590 if p == nil || other == nil {
591 return p == other
592 }
593 if p.ChildSize != other.ChildSize ||
594 p.MinPrefixLength != other.MinPrefixLength ||
595 p.MaxPrefixLength != other.MaxPrefixLength ||
596 p.Hash != other.Hash {
597 return false
598 }
599 if len(p.ChildOrder) != len(other.ChildOrder) {
600 return false
601 }
602 for i := range p.ChildOrder {
603 if p.ChildOrder[i] != other.ChildOrder[i] {
604 return false
605 }
606 }
607 return bytes.Equal(p.EmptyChild, other.EmptyChild)
608}
609
610// SpecEquals returns true if two ProofSpec instances match on the subset of
611// fields that matter for routing proof verification through a known spec
612// (IavlSpec/TendermintSpec). It intentionally ignores MaxDepth/MinDepth,
613// LeafOp.Prefix, ChildOrder contents, and InnerSpec.EmptyChild — it
614// over-declares equality, which we consider fine for that use case.
615// Use Equal for strict field-by-field comparison (e.g. RecoverClient).
616func (p *ProofSpec) SpecEquals(spec *ProofSpec) bool {
617 // 1. Compare LeafSpecs values.
618 switch {
619 case (p.LeafSpec == nil) != (spec.LeafSpec == nil): // One of them is nil.
620 return false
621
622 case p.LeafSpec != nil && spec.LeafSpec != nil:
623 ok := p.LeafSpec.Hash == spec.LeafSpec.Hash &&
624 p.LeafSpec.PrehashKey == spec.LeafSpec.PrehashKey &&
625 p.LeafSpec.PrehashValue == spec.LeafSpec.PrehashValue &&
626 p.LeafSpec.Length == spec.LeafSpec.Length
627 if !ok {
628 return false
629 }
630
631 default: // Both are nil, hence LeafSpec values are equal.
632 }
633
634 // 2. Compare InnerSpec values.
635 switch {
636 case (p.InnerSpec == nil) != (spec.InnerSpec == nil): // One of them is not nil.
637 return false
638
639 case p.InnerSpec != nil && spec.InnerSpec != nil: // Both are non-nil
640 ok := p.InnerSpec.Hash == spec.InnerSpec.Hash &&
641 p.InnerSpec.MinPrefixLength == spec.InnerSpec.MinPrefixLength &&
642 p.InnerSpec.MaxPrefixLength == spec.InnerSpec.MaxPrefixLength &&
643 p.InnerSpec.ChildSize == spec.InnerSpec.ChildSize &&
644 len(p.InnerSpec.ChildOrder) == len(spec.InnerSpec.ChildOrder)
645 if !ok {
646 return false
647 }
648
649 default: // Both are nil, hence InnerSpec values are equal.
650 }
651
652 // By this point all the above conditions pass so they are equal.
653 return true
654}
