-
Notifications
You must be signed in to change notification settings - Fork 3.6k
/
merkle.go
186 lines (151 loc) · 4.82 KB
/
merkle.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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
package commitment
import (
"errors"
"net/url"
"github.com/tendermint/tendermint/crypto/merkle"
"github.com/cosmos/cosmos-sdk/store/rootmulti"
host "github.com/cosmos/cosmos-sdk/x/ibc/24-host"
)
// ICS 023 Merkle Types Implementation
//
// This file defines Merkle commitment types that implements ICS 023.
// Merkle proof implementation of the Proof interface
// Applied on SDK-based IBC implementation
var _ RootI = Root{}
// Root defines a merkle root hash.
// In the Cosmos SDK, the AppHash of a block header becomes the Root.
type Root struct {
Hash []byte `json:"hash" yaml:"hash"`
}
// NewRoot constructs a new Root
func NewRoot(hash []byte) Root {
return Root{
Hash: hash,
}
}
// GetCommitmentType implements RootI interface
func (Root) GetCommitmentType() Type {
return Merkle
}
// GetHash implements RootI interface
func (r Root) GetHash() []byte {
return r.Hash
}
// IsEmpty returns true if the root is empty
func (r Root) IsEmpty() bool {
return len(r.GetHash()) == 0
}
var _ PrefixI = Prefix{}
// Prefix is merkle path prefixed to the key.
// The constructed key from the Path and the key will be append(Path.KeyPath, append(Path.KeyPrefix, key...))
type Prefix struct {
KeyPrefix []byte `json:"key_prefix" yaml:"key_prefix"` // byte slice prefixed before the key
}
// NewPrefix constructs new Prefix instance
func NewPrefix(keyPrefix []byte) Prefix {
return Prefix{
KeyPrefix: keyPrefix,
}
}
// GetCommitmentType implements PrefixI
func (Prefix) GetCommitmentType() Type {
return Merkle
}
// Bytes returns the key prefix bytes
func (p Prefix) Bytes() []byte {
return p.KeyPrefix
}
// IsEmpty returns true if the prefix is empty
func (p Prefix) IsEmpty() bool {
return len(p.Bytes()) == 0
}
var _ PathI = Path{}
// Path is the path used to verify commitment proofs, which can be an arbitrary
// structured object (defined by a commitment type).
type Path struct {
KeyPath merkle.KeyPath `json:"key_path" yaml:"key_path"` // byte slice prefixed before the key
}
// NewPath creates a new CommitmentPath instance
func NewPath(keyPathStr []string) Path {
merkleKeyPath := merkle.KeyPath{}
for _, keyStr := range keyPathStr {
merkleKeyPath = merkleKeyPath.AppendKey([]byte(keyStr), merkle.KeyEncodingURL)
}
return Path{
KeyPath: merkleKeyPath,
}
}
// GetCommitmentType implements PathI
func (Path) GetCommitmentType() Type {
return Merkle
}
// String implements fmt.Stringer.
func (p Path) String() string {
return p.KeyPath.String()
}
// Pretty returns the unescaped path of the URL string.
func (p Path) Pretty() string {
path, err := url.PathUnescape(p.KeyPath.String())
if err != nil {
panic(err)
}
return path
}
// IsEmpty returns true if the path is empty
func (p Path) IsEmpty() bool {
return len(p.KeyPath) == 0
}
// ApplyPrefix constructs a new commitment path from the arguments. It interprets
// the path argument in the context of the prefix argument.
//
// CONTRACT: provided path string MUST be a well formated path. See ICS24 for
// reference.
func ApplyPrefix(prefix PrefixI, path string) (Path, error) {
err := host.DefaultPathValidator(path)
if err != nil {
return Path{}, err
}
if prefix == nil || prefix.IsEmpty() {
return Path{}, errors.New("prefix can't be empty")
}
return NewPath([]string{string(prefix.Bytes()), path}), nil
}
var _ ProofI = Proof{}
// Proof is a wrapper type that contains a merkle proof.
// It demonstrates membership or non-membership for an element or set of elements,
// verifiable in conjunction with a known commitment root. Proofs should be
// succinct.
type Proof struct {
Proof *merkle.Proof `json:"proof" yaml:"proof"`
}
// GetCommitmentType implements ProofI
func (Proof) GetCommitmentType() Type {
return Merkle
}
// VerifyMembership verifies the membership pf a merkle proof against the given root, path, and value.
func (proof Proof) VerifyMembership(root RootI, path PathI, value []byte) error {
if proof.IsEmpty() || root == nil || root.IsEmpty() || path == nil || path.IsEmpty() || len(value) == 0 {
return errors.New("empty params or proof")
}
runtime := rootmulti.DefaultProofRuntime()
return runtime.VerifyValue(proof.Proof, root.GetHash(), path.String(), value)
}
// VerifyNonMembership verifies the absence of a merkle proof against the given root and path.
func (proof Proof) VerifyNonMembership(root RootI, path PathI) error {
if proof.IsEmpty() || root == nil || root.IsEmpty() || path == nil || path.IsEmpty() {
return errors.New("empty params or proof")
}
runtime := rootmulti.DefaultProofRuntime()
return runtime.VerifyAbsence(proof.Proof, root.GetHash(), path.String())
}
// IsEmpty returns true if the root is empty
func (proof Proof) IsEmpty() bool {
return (proof == Proof{}) || proof.Proof == nil
}
// ValidateBasic checks if the proof is empty.
func (proof Proof) ValidateBasic() error {
if proof.IsEmpty() {
return ErrInvalidProof
}
return nil
}