-
Notifications
You must be signed in to change notification settings - Fork 1
/
proof.go
163 lines (140 loc) · 3.38 KB
/
proof.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
package merkletree_proof
import (
"bytes"
"context"
"encoding/json"
"errors"
"fmt"
"math/big"
"github.com/iden3/go-merkletree-sql/v2"
)
var ErrNodeNotFound = errors.New("node not found")
type ReverseHashCli interface {
GenerateProof(ctx context.Context,
treeRoot *merkletree.Hash,
key *merkletree.Hash) (*merkletree.Proof, error)
GetNode(ctx context.Context,
hash *merkletree.Hash) (Node, error)
SaveNodes(ctx context.Context,
nodes []Node) error
}
type NodeType byte
const (
NodeTypeUnknown NodeType = iota
NodeTypeMiddle NodeType = iota
NodeTypeLeaf NodeType = iota
NodeTypeState NodeType = iota
)
var hashOne, _ = merkletree.NewHashFromBigInt(big.NewInt(1))
type Node struct {
Hash *merkletree.Hash
Children []*merkletree.Hash
}
func (n Node) Type() NodeType {
if len(n.Children) == 2 {
return NodeTypeMiddle
}
if len(n.Children) == 3 && *n.Children[2] == *hashOne {
return NodeTypeLeaf
}
if len(n.Children) == 3 {
return NodeTypeState
}
return NodeTypeUnknown
}
type jsonNode struct {
Hash string `json:"hash"`
Children []string `json:"children"`
}
func (n *Node) UnmarshalJSON(in []byte) error {
var jsonN jsonNode
err := json.Unmarshal(in, &jsonN)
if err != nil {
return err
}
n.Hash, err = merkletree.NewHashFromHex(jsonN.Hash)
if err != nil {
return err
}
n.Children, err = hexesToHashes(jsonN.Children)
return err
}
func (n Node) MarshalJSON() ([]byte, error) {
return json.Marshal(jsonNode{
Hash: n.Hash.Hex(),
Children: hashesToHexes(n.Children),
})
}
type NodeReader interface {
GetNode(context.Context, *merkletree.Hash) (Node, error)
}
func GenerateProof(ctx context.Context, cli NodeReader,
treeRoot *merkletree.Hash,
key *merkletree.Hash) (*merkletree.Proof, error) {
var exists bool
var siblings []*merkletree.Hash
var nodeAux *merkletree.NodeAux
mkProof := func() (*merkletree.Proof, error) {
return merkletree.NewProofFromData(exists, siblings, nodeAux)
}
nextKey := treeRoot
for depth := uint(0); depth < uint(len(key)*8); depth++ {
if *nextKey == merkletree.HashZero {
return mkProof()
}
n, err := cli.GetNode(ctx, nextKey)
if err != nil {
return nil, err
}
switch nt := n.Type(); nt {
case NodeTypeLeaf:
if bytes.Equal(key[:], n.Children[0][:]) {
exists = true
return mkProof()
}
// We found a leaf whose entry didn't match hIndex
nodeAux = &merkletree.NodeAux{
Key: n.Children[0],
Value: n.Children[1],
}
return mkProof()
case NodeTypeMiddle:
if merkletree.TestBit(key[:], depth) {
nextKey = n.Children[1]
siblings = append(siblings, n.Children[0])
} else {
nextKey = n.Children[0]
siblings = append(siblings, n.Children[1])
}
default:
return nil, fmt.Errorf(
"found unexpected node type in tree (%v): %v",
nt, n.Hash.Hex())
}
}
return nil, errors.New("tree depth is too high")
}
func hashesToHexes(hashes []*merkletree.Hash) []string {
if hashes == nil {
return nil
}
hexes := make([]string, len(hashes))
for i, h := range hashes {
hexes[i] = h.Hex()
}
return hexes
}
func hexesToHashes(hexes []string) ([]*merkletree.Hash, error) {
if hexes == nil {
return nil, nil
}
hashes := make([]*merkletree.Hash, len(hexes))
var err error
for i, h := range hexes {
hashes[i], err = merkletree.NewHashFromHex(h)
if err != nil {
return nil, fmt.Errorf("can't parse hex #%v: %w", i, err)
}
}
return hashes, nil
}