proof.gno

 1package mpt
 2
 3import (
 4	"bytes"
 5	"encoding/hex"
 6
 7	"gno.land/p/nt/ufmt/v0"
 8)
 9
10// missingNodeError reports which proof node index/hash verifyProof needed
11// but didn't find, mirroring VerifyProof's "proof node %d (hash %064x)
12// missing" message. It satisfies errors.Is(err, ErrMissingNode) via Is, since
13// ufmt.Errorf has no %w wrapping to attach the sentinel directly.
14type missingNodeError struct {
15	index int
16	hash  [32]byte
17}
18
19func (e *missingNodeError) Error() string {
20	return ufmt.Sprintf("mpt: proof node %d (hash %s) missing", e.index, hex.EncodeToString(e.hash[:]))
21}
22
23func (e *missingNodeError) Is(target error) bool {
24	return target == ErrMissingNode
25}
26
27// verifyProof mirrors VerifyProof (proofDb pre-indexed by hash, matching how
28// go-ethereum's caller populates it via Prove).
29// Reference:
30// https://github.com/ethereum/go-ethereum/blob/v1.10.26/trie/proof.go#L111-L135
31func verifyProof(rootHash [32]byte, key []byte, proofDb map[[32]byte][]byte) ([]byte, error) {
32	key = keybytesToHex(key)
33	wantHash := rootHash
34
35	for i := 0; ; i++ {
36		buf, ok := proofDb[wantHash]
37		if !ok {
38			return nil, &missingNodeError{index: i, hash: wantHash}
39		}
40
41		n, err := decodeNode(buf)
42		if err != nil {
43			return nil, err
44		}
45
46		keyrest, cld := get(n, key, true)
47
48		switch c := cld.(type) {
49		case nil:
50			return nil, nil
51		case hashNode:
52			key = keyrest
53			copy(wantHash[:], c)
54		case valueNode:
55			return c, nil
56		}
57	}
58}
59
60// get mirrors get.
61// Reference:
62// https://github.com/ethereum/go-ethereum/blob/v1.10.26/trie/proof.go#L580-L608
63func get(tn node, key []byte, skipResolved bool) ([]byte, node) {
64	for {
65		switch n := tn.(type) {
66		case *shortNode:
67			if len(key) < len(n.Key) || !bytes.Equal(n.Key, key[:len(n.Key)]) {
68				return nil, nil
69			}
70
71			tn = n.Val
72			key = key[len(n.Key):]
73
74			if !skipResolved {
75				return key, tn
76			}
77
78		case *fullNode:
79			tn = n.Children[key[0]]
80			key = key[1:]
81
82			if !skipResolved {
83				return key, tn
84			}
85
86		case hashNode:
87			return key, n
88
89		case nil:
90			return key, nil
91
92		case valueNode:
93			return nil, n
94		}
95	}
96}