ops.gno
8.64 Kb · 306 lines
1package ics23
2
3import (
4 "bytes"
5 "encoding/binary"
6 "errors"
7
8 // adds sha256 capability to crypto.SHA256
9
10 "crypto/sha256"
11
12 "gno.land/p/nt/ufmt/v0"
13)
14
15type HashOp int32
16
17const (
18 // NO_HASH is the default if no data passed. Note this is an illegal argument some places.
19 HashOp_NO_HASH HashOp = 0
20 HashOp_SHA256 HashOp = 1
21)
22
23// LengthOp defines how to process the key and value of the LeafOp
24// to include length information. After encoding the length with the given
25// algorithm, the length will be prepended to the key and value bytes.
26// (Each one with it's own encoded length)
27type LengthOp int32
28
29const (
30 // NO_PREFIX don't include any length info
31 LengthOp_NO_PREFIX LengthOp = 0
32 // VAR_PROTO uses protobuf (and go-amino) varint encoding of the length
33 LengthOp_VAR_PROTO LengthOp = 1
34)
35
36// validateIavlOps validates the prefix to ensure it begins with
37// the height, size, and version of the IAVL tree. Each varint must be a bounded value.
38// In addition, the remaining bytes are validated to ensure they correspond to the correct
39// length. The layerNum is the inverse of the tree depth, i.e. depth=0 means leaf, depth>=1 means inner node
40func validateIavlOps(op opType, layerNum int) error {
41 r := bytes.NewReader(op.GetPrefix())
42
43 height, err := binary.ReadVarint(r)
44 if err != nil {
45 return ufmt.Errorf("failed to read IAVL height varint: %v", err)
46 }
47 if int(height) < 0 || int(height) < layerNum {
48 return ufmt.Errorf("IAVL height (%d) must be non-negative and greater than or equal to the layer number (%d)", height, layerNum)
49 }
50
51 size, err := binary.ReadVarint(r)
52 if err != nil {
53 return ufmt.Errorf("failed to read IAVL size varint: %v", err)
54 }
55
56 if int(size) < 0 {
57 return ufmt.Errorf("IAVL size must be non-negative")
58 }
59
60 version, err := binary.ReadVarint(r)
61 if err != nil {
62 return ufmt.Errorf("failed to read IAVL version varint: %v", err)
63 }
64
65 if int(version) < 0 {
66 return ufmt.Errorf("IAVL version must be non-negative")
67 }
68
69 // grab the length of the remainder of the prefix
70 remLen := r.Len()
71 if layerNum == 0 {
72 // leaf node
73 if remLen != 0 {
74 return ufmt.Errorf("expected remaining prefix length to be 0, got: %d", remLen)
75 }
76 if height != 0 {
77 return ufmt.Errorf("expected leaf node height to be 0, got: %d", remLen)
78 }
79 if size != 1 {
80 return ufmt.Errorf("expected leaf node size to be 1, got: %d", remLen)
81 }
82 } else {
83 // inner node
84 //
85 // when the child comes from the left, the suffix if filled in
86 // prefix: height | size | version | length byte (1 remainder)
87 //
88 // when the child comes from the right, the suffix is empty
89 // prefix: height | size | version | length byte | 32 byte hash | next length byte (34 remainder)
90 if remLen != 1 && remLen != 34 {
91 return ufmt.Errorf("remainder of prefix must be of length 1 or 34, got: %d", remLen)
92 }
93 if op.GetHash() != HashOp_SHA256 {
94 return ufmt.Errorf("IAVL hash op must be %v", HashOp_SHA256)
95 }
96 }
97 return nil
98}
99
100// validateTendermintOps validates the prefix to ensure it begins with []byte{1}.
101func validateTendermintOps(op *InnerOp) error {
102 if len(op.Prefix) == 0 {
103 return ufmt.Errorf("inner op prefix must not be empty")
104 }
105
106 innerPrefix := []byte{1}
107 if op.Suffix != nil {
108 if !bytes.Equal(op.Prefix, innerPrefix) {
109 return ufmt.Errorf("expected inner op prefix: %v, got: %v", innerPrefix, op.Prefix)
110 }
111 }
112
113 if !bytes.HasPrefix(op.Prefix, innerPrefix) {
114 return ufmt.Errorf("expected inner op prefix to begin with: %v, got: %v", innerPrefix, op.Prefix[:1])
115 }
116
117 return nil
118}
119
120// Apply will calculate the leaf hash given the key and value being proven
121func (op *LeafOp) Apply(key []byte, value []byte) ([]byte, error) {
122 if len(key) == 0 {
123 return nil, errors.New("leaf op needs key")
124 }
125 if len(value) == 0 {
126 return nil, errors.New("leaf op needs value")
127 }
128 pkey, err := prepareLeafData(op.PrehashKey, op.Length, key)
129 if err != nil {
130 return nil, ufmt.Errorf("prehash key, %v", err)
131 }
132 pvalue, err := prepareLeafData(op.PrehashValue, op.Length, value)
133 if err != nil {
134 return nil, ufmt.Errorf("prehash value, %v", err)
135 }
136
137 data := op.Prefix
138 data = append(data, pkey...)
139 data = append(data, pvalue...)
140
141 return doHash(op.Hash, data)
142}
143
144// Apply will calculate the hash of the next step, given the hash of the previous step
145func (op *InnerOp) Apply(child []byte) ([]byte, error) {
146 if len(child) == 0 {
147 return nil, errors.New("inner op needs child value")
148 }
149 preimage := op.Prefix
150 preimage = append(preimage, child...)
151 preimage = append(preimage, op.Suffix...)
152 return doHash(op.Hash, preimage)
153}
154
155// CheckAgainstSpec will verify the LeafOp is in the format defined in spec
156func (op *LeafOp) CheckAgainstSpec(spec *ProofSpec) error {
157 if spec == nil {
158 return errors.New("op and spec must be non-nil")
159 }
160 lspec := spec.LeafSpec
161 if lspec == nil {
162 return errors.New("spec.LeafSpec must be non-nil")
163 }
164
165 if spec.SpecEquals(IavlSpec()) {
166 err := validateIavlOps(op, 0)
167 if err != nil {
168 return err
169 }
170 }
171
172 if op.Hash != lspec.Hash {
173 return ufmt.Errorf("unexpected HashOp: %d", op.Hash)
174 }
175 if op.PrehashKey != lspec.PrehashKey {
176 return ufmt.Errorf("unexpected PrehashKey: %d", op.PrehashKey)
177 }
178 if op.PrehashValue != lspec.PrehashValue {
179 return ufmt.Errorf("unexpected PrehashValue: %d", op.PrehashValue)
180 }
181 if op.Length != lspec.Length {
182 return ufmt.Errorf("unexpected LengthOp: %d", op.Length)
183 }
184 if !bytes.HasPrefix(op.Prefix, lspec.Prefix) {
185 return ufmt.Errorf("leaf Prefix doesn't start with %X", lspec.Prefix)
186 }
187 return nil
188}
189
190// CheckAgainstSpec will verify the InnerOp is in the format defined in spec
191func (op *InnerOp) CheckAgainstSpec(spec *ProofSpec, b int) error {
192 if spec == nil {
193 return errors.New("op and spec must be both non-nil")
194 }
195 if spec.InnerSpec == nil {
196 return errors.New("spec.InnerSpec must be non-nil")
197 }
198 if spec.LeafSpec == nil {
199 return errors.New("spec.LeafSpec must be non-nil")
200 }
201
202 if op.Hash != spec.InnerSpec.Hash {
203 return ufmt.Errorf("unexpected HashOp: %d", op.Hash)
204 }
205
206 if spec.SpecEquals(IavlSpec()) {
207 err := validateIavlOps(op, b)
208 if err != nil {
209 return err
210 }
211 }
212
213 if spec.SpecEquals(TendermintSpec()) {
214 err := validateTendermintOps(op)
215 if err != nil {
216 return err
217 }
218 }
219
220 leafPrefix := spec.LeafSpec.Prefix
221 if bytes.HasPrefix(op.Prefix, leafPrefix) {
222 return ufmt.Errorf("inner Prefix starts with %X", leafPrefix)
223 }
224 if len(op.Prefix) < int(spec.InnerSpec.MinPrefixLength) {
225 return ufmt.Errorf("innerOp prefix too short (%d)", len(op.Prefix))
226 }
227 maxLeftChildBytes := (len(spec.InnerSpec.ChildOrder) - 1) * int(spec.InnerSpec.ChildSize)
228 if len(op.Prefix) > int(spec.InnerSpec.MaxPrefixLength)+maxLeftChildBytes {
229 return ufmt.Errorf("innerOp prefix too long (%d)", len(op.Prefix))
230 }
231
232 if spec.InnerSpec.ChildSize <= 0 {
233 return errors.New("spec.InnerSpec.ChildSize must be >= 1")
234 }
235
236 if spec.InnerSpec.MaxPrefixLength >= spec.InnerSpec.MinPrefixLength+spec.InnerSpec.ChildSize {
237 return errors.New("spec.InnerSpec.MaxPrefixLength must be < spec.InnerSpec.MinPrefixLength + spec.InnerSpec.ChildSize")
238 }
239
240 // ensures soundness, with suffix having to be of correct length
241 if len(op.Suffix)%int(spec.InnerSpec.ChildSize) != 0 {
242 return ufmt.Errorf("InnerOp suffix malformed")
243 }
244
245 return nil
246}
247
248// doHash will preform the specified hash on the preimage.
249// if hashOp == NONE, it will return an error (use doHashOrNoop if you want different behavior)
250func doHash(hashOp HashOp, preimage []byte) ([]byte, error) {
251 switch hashOp {
252 case HashOp_SHA256:
253 h := sha256.Sum256(preimage)
254 return h[:], nil
255 }
256 return nil, ufmt.Errorf("unsupported hashop: %d", hashOp)
257}
258
259func prepareLeafData(hashOp HashOp, lengthOp LengthOp, data []byte) ([]byte, error) {
260 // TODO: lengthop before or after hash ???
261 hdata, err := doHashOrNoop(hashOp, data)
262 if err != nil {
263 return nil, err
264 }
265
266 return doLengthOp(lengthOp, hdata)
267}
268
269type opType interface {
270 GetPrefix() []byte
271 GetHash() HashOp
272}
273
274// doLengthOp will calculate the proper prefix and return it prepended
275//
276// doLengthOp(op, data) -> length(data) || data
277func doLengthOp(lengthOp LengthOp, data []byte) ([]byte, error) {
278 switch lengthOp {
279 case LengthOp_NO_PREFIX:
280 return data, nil
281 case LengthOp_VAR_PROTO:
282 res := append(encodeVarintProto(len(data)), data...)
283 return res, nil
284 }
285 return nil, ufmt.Errorf("unsupported lengthop: %d", lengthOp)
286}
287
288func encodeVarintProto(l int) []byte {
289 // avoid multiple allocs for normal case
290 res := make([]byte, 0, 8)
291 for l >= 1<<7 {
292 res = append(res, uint8(l&0x7f|0x80))
293 l >>= 7
294 }
295 res = append(res, uint8(l))
296 return res
297}
298
299// doHashOrNoop will return the preimage untouched if hashOp == NONE,
300// otherwise, perform doHash
301func doHashOrNoop(hashOp HashOp, preimage []byte) ([]byte, error) {
302 if hashOp == HashOp_NO_HASH {
303 return preimage, nil
304 }
305 return doHash(hashOp, preimage)
306}
