forked from cosmos/iavl
-
Notifications
You must be signed in to change notification settings - Fork 0
/
proof_key.go
154 lines (126 loc) · 4.23 KB
/
proof_key.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
package iavl
import (
"bytes"
"fmt"
"github.com/pkg/errors"
"github.com/tendermint/go-wire"
cmn "github.com/tendermint/tmlibs/common"
)
// KeyProof represents a proof of existence or absence of a single key.
type KeyProof interface {
// Verify verfies the proof is valid. To verify absence,
// the value should be nil.
Verify(key, value, root []byte) error
// Root returns the root hash of the proof.
Root() []byte
// Serialize itself
Bytes() []byte
}
const (
// Used for serialization of proofs.
keyExistsMagicNumber = 0x50
keyAbsentMagicNumber = 0x51
)
// KeyExistsProof represents a proof of existence of a single key.
type KeyExistsProof struct {
RootHash cmn.HexBytes `json:"root_hash"`
Version int64 `json:"version"`
*PathToKey `json:"path"`
}
func (proof *KeyExistsProof) Root() []byte {
return proof.RootHash
}
// Verify verifies the proof is valid and returns an error if it isn't.
func (proof *KeyExistsProof) Verify(key []byte, value []byte, root []byte) error {
if !bytes.Equal(proof.RootHash, root) {
return errors.WithStack(ErrInvalidRoot)
}
if key == nil || value == nil {
return errors.WithStack(ErrInvalidInputs)
}
return proof.PathToKey.verify(proofLeafNode{key, value, proof.Version}.Hash(), root)
}
// Bytes returns a go-wire binary serialization
func (proof *KeyExistsProof) Bytes() []byte {
return append([]byte{keyExistsMagicNumber}, wire.BinaryBytes(proof)...)
}
// readKeyExistsProof will deserialize a KeyExistsProof from bytes.
func readKeyExistsProof(data []byte) (*KeyExistsProof, error) {
proof := new(KeyExistsProof)
err := wire.ReadBinaryBytes(data, &proof)
return proof, err
}
///////////////////////////////////////////////////////////////////////////////
// KeyAbsentProof represents a proof of the absence of a single key.
type KeyAbsentProof struct {
RootHash cmn.HexBytes `json:"root_hash"`
Left *pathWithNode `json:"left"`
Right *pathWithNode `json:"right"`
}
func (proof *KeyAbsentProof) Root() []byte {
return proof.RootHash
}
func (p *KeyAbsentProof) String() string {
return fmt.Sprintf("KeyAbsentProof\nroot=%s\nleft=%s%#v\nright=%s%#v\n", p.RootHash, p.Left.Path, p.Left.Node, p.Right.Path, p.Right.Node)
}
// Verify verifies the proof is valid and returns an error if it isn't.
func (proof *KeyAbsentProof) Verify(key, value []byte, root []byte) error {
if !bytes.Equal(proof.RootHash, root) {
return errors.WithStack(ErrInvalidRoot)
}
if key == nil || value != nil {
return ErrInvalidInputs
}
if proof.Left == nil && proof.Right == nil {
return errors.WithStack(ErrInvalidProof)
}
if err := verifyPaths(proof.Left, proof.Right, key, key, root); err != nil {
return err
}
return verifyKeyAbsence(proof.Left, proof.Right)
}
// Bytes returns a go-wire binary serialization
func (proof *KeyAbsentProof) Bytes() []byte {
return append([]byte{keyAbsentMagicNumber}, wire.BinaryBytes(proof)...)
}
// readKeyAbsentProof will deserialize a KeyAbsentProof from bytes.
func readKeyAbsentProof(data []byte) (*KeyAbsentProof, error) {
proof := new(KeyAbsentProof)
err := wire.ReadBinaryBytes(data, &proof)
return proof, err
}
// ReadKeyProof reads a KeyProof from a byte-slice.
func ReadKeyProof(data []byte) (KeyProof, error) {
if len(data) == 0 {
return nil, errors.New("proof bytes are empty")
}
b, val := data[0], data[1:]
switch b {
case keyExistsMagicNumber:
return readKeyExistsProof(val)
case keyAbsentMagicNumber:
return readKeyAbsentProof(val)
}
return nil, errors.New("unrecognized proof")
}
///////////////////////////////////////////////////////////////////////////////
// InnerKeyProof represents a proof of existence of an inner node key.
type InnerKeyProof struct {
*KeyExistsProof
}
// Verify verifies the proof is valid and returns an error if it isn't.
func (proof *InnerKeyProof) Verify(hash []byte, value []byte, root []byte) error {
if !bytes.Equal(proof.RootHash, root) {
return errors.WithStack(ErrInvalidRoot)
}
if hash == nil || value != nil {
return errors.WithStack(ErrInvalidInputs)
}
return proof.PathToKey.verify(hash, root)
}
// ReadKeyInnerProof will deserialize a InnerKeyProof from bytes.
func ReadInnerKeyProof(data []byte) (*InnerKeyProof, error) {
proof := new(InnerKeyProof)
err := wire.ReadBinaryBytes(data, &proof)
return proof, err
}