node.gno

  1package mpt
  2
  3import (
  4	"gno.land/p/onbloc/encoding/rlp"
  5)
  6
  7// isDataNode reports whether v is a string/byte payload rather than a list.
  8func isDataNode(v rlp.Value) bool {
  9	return v.Kind == rlp.KindString || v.Kind == rlp.KindByte
 10}
 11
 12// node mirrors go-ethereum's node interface (marker only; cache/encode/
 13// fstring are for trie construction, unneeded for verification).
 14// Reference:
 15// https://github.com/ethereum/go-ethereum/blob/v1.10.26/trie/node.go#L30-L48
 16type node interface{}
 17
 18// flags nodeFlag (cached hash + dirty bit, for incremental rehashing on
 19// mutation) is dropped from both structs below: never read by decodeNode,
 20// get, or verifyProof.
 21type (
 22	fullNode struct {
 23		Children [17]node
 24	}
 25	shortNode struct {
 26		Key []byte
 27		Val node
 28	}
 29	hashNode  []byte
 30	valueNode []byte
 31)
 32
 33// decodeNode mirrors decodeNode (hash argument dropped: cache-only, unused
 34// by verification).
 35// Reference:
 36// https://github.com/ethereum/go-ethereum/blob/v1.10.26/trie/node.go#L133-L151
 37func decodeNode(buf []byte) (node, error) {
 38	v, err := rlp.DecodeValue(buf)
 39	if err != nil {
 40		return nil, err
 41	}
 42
 43	return decodeNodeValue(v)
 44}
 45
 46// decodeNodeValue is decodeNode's dispatch step, split out so decodeRef can
 47// resolve an already-decoded embedded child without re-parsing raw bytes.
 48func decodeNodeValue(v rlp.Value) (node, error) {
 49	if v.Kind != rlp.KindList {
 50		return nil, ErrUnexpectedNode
 51	}
 52
 53	switch len(v.List) {
 54	case 2:
 55		return decodeShort(v)
 56	case 17:
 57		return decodeFull(v)
 58	default:
 59		return nil, ErrUnexpectedNode
 60	}
 61}
 62
 63// decodeShort mirrors decodeShort.
 64// Reference:
 65// https://github.com/ethereum/go-ethereum/blob/v1.10.26/trie/node.go#L153-L173
 66func decodeShort(elems rlp.Value) (node, error) {
 67	kbuf := elems.List[0]
 68	if !isDataNode(kbuf) {
 69		return nil, ErrUnexpectedNode
 70	}
 71
 72	key := compactToHex(kbuf.Bytes)
 73
 74	if hasTerm(key) {
 75		val := elems.List[1]
 76		if !isDataNode(val) {
 77			return nil, ErrUnexpectedNode
 78		}
 79
 80		return &shortNode{Key: key, Val: valueNode(val.Bytes)}, nil
 81	}
 82
 83	r, err := decodeRef(elems.List[1])
 84	if err != nil {
 85		return nil, err
 86	}
 87
 88	return &shortNode{Key: key, Val: r}, nil
 89}
 90
 91// decodeFull mirrors decodeFull.
 92// Reference:
 93// https://github.com/ethereum/go-ethereum/blob/v1.10.26/trie/node.go#L175-L192
 94func decodeFull(elems rlp.Value) (*fullNode, error) {
 95	n := &fullNode{}
 96
 97	for i := 0; i < 16; i++ {
 98		cld, err := decodeRef(elems.List[i])
 99		if err != nil {
100			return n, err
101		}
102
103		n.Children[i] = cld
104	}
105
106	val := elems.List[16]
107	if !isDataNode(val) {
108		return n, ErrUnexpectedNode
109	}
110
111	if len(val.Bytes) > 0 {
112		n.Children[16] = valueNode(val.Bytes)
113	}
114
115	return n, nil
116}
117
118// decodeRef mirrors decodeRef, minus its "oversized embedded node" size
119// check (no verifier-side security benefit: the parent hash already covers
120// these bytes regardless of embed size).
121// Reference:
122// https://github.com/ethereum/go-ethereum/blob/v1.10.26/trie/node.go#L196-L218
123func decodeRef(buf rlp.Value) (node, error) {
124	if buf.Kind == rlp.KindList {
125		return decodeNodeValue(buf)
126	}
127
128	switch len(buf.Bytes) {
129	case 0:
130		return nil, nil
131
132	case 32:
133		return hashNode(buf.Bytes), nil
134
135	default:
136		return nil, ErrInvalidReference
137	}
138}