/
inclusion.go
171 lines (150 loc) · 6.37 KB
/
inclusion.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
// Copyright 2020 Google LLC. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Package verification contains verifiers for clients of the map to confirm
// entries are committed to.
package verification
import (
"bytes"
"crypto"
"fmt"
"github.com/google/trillian/experimental/batchmap"
"github.com/google/trillian/merkle/coniks"
"github.com/google/trillian/merkle/smt"
"github.com/google/trillian/merkle/smt/node"
)
// TileFetch gets the tile at the specified path in the given map revision.
// There is currently an assumption that this is very fast and thus it looks
// up tiles one at a time. This can be replaced with a batch version if that
// assumption is invalidated (e.g. this method triggers network operations).
type TileFetch func(revision int, path []byte) (*batchmap.Tile, error)
// MapVerifier verifies inclusion of key/values in a map.
type MapVerifier struct {
tileFetch TileFetch
prefixStrata int
treeID int64
hash crypto.Hash
}
// NewMapVerifier returns a MapVerifier for the map at the given location and with the
// configuration provided.
func NewMapVerifier(tileFetch TileFetch, prefixStrata int, treeID int64, hash crypto.Hash) *MapVerifier {
return &MapVerifier{
tileFetch: tileFetch,
prefixStrata: prefixStrata,
treeID: treeID,
hash: hash,
}
}
// CheckInclusion confirms that the key & value are committed to by the map in the given
// directory, and returns the computed and confirmed root hash that commits to this.
func (v *MapVerifier) CheckInclusion(rev int, key string, value []byte) ([]byte, error) {
// Determine the key/value we expect to find.
// Note that the map tiles do not contain raw values, but commitments to the values.
// If the map needs to return the values to clients then it is recommended that the
// map operator uses a Content Addressable Store to store these values.
h := v.hash.New()
h.Write([]byte(key))
keyPath := h.Sum(nil)
leafID := node.NewID(string(keyPath), uint(len(keyPath)*8))
expectedValueHash := coniks.Default.HashLeaf(v.treeID, leafID, value)
// Read the tiles required for this check from disk.
tiles, err := v.getTilesForKey(rev, keyPath)
if err != nil {
return nil, fmt.Errorf("couldn't load tiles: %v", err)
}
// Perform the verification.
// 1) Start at the leaf tile and check the key/value.
// 2) Compute the merkle root of the leaf tile
// 3) Check the computed root matches that reported in the tile
// 4) Check this root value is the key/value of the tile above.
// 5) Rinse and repeat until we reach the tree root.
et := emptyTree{treeID: v.treeID, hasher: coniks.Default}
needPath, needValue := keyPath, expectedValueHash
for i := v.prefixStrata; i >= 0; i-- {
tile := tiles[i]
// Check the prefix of what we are looking for matches the tile's path.
if got, want := tile.Path, needPath[:len(tile.Path)]; !bytes.Equal(got, want) {
return nil, fmt.Errorf("wrong tile found at index %d: got %x, want %x", i, got, want)
}
// Leaf paths within a tile are within the scope of the tile, so we can
// drop the prefix from the expected path now we have verified it.
needLeafPath := needPath[len(tile.Path):]
// Identify the leaf we need, and convert all leaves to the format needed for hashing.
var leaf *batchmap.TileLeaf
nodes := make([]smt.Node, len(tile.Leaves))
for j, l := range tile.Leaves {
if bytes.Equal(l.Path, needLeafPath) {
leaf = l
}
nodes[j] = toNode(tile.Path, l)
}
// Confirm we found the leaf we needed, and that it had the value we expected.
if leaf == nil {
return nil, fmt.Errorf("couldn't find expected leaf %x in tile %x", needLeafPath, tile.Path)
}
if !bytes.Equal(leaf.Hash, needValue) {
return nil, fmt.Errorf("wrong leaf value in tile %x, leaf %x: got %x, want %x", tile.Path, leaf.Path, leaf.Hash, needValue)
}
// Hash this tile given its leaf values, and confirm that the value we compute
// matches the value reported in the tile.
hs, err := smt.NewHStar3(nodes, et.hasher.HashChildren,
uint(len(tile.Path)+len(leaf.Path))*8, uint(len(tile.Path))*8)
if err != nil {
return nil, fmt.Errorf("failed to create HStar3 for tile %x: %v", tile.Path, err)
}
res, err := hs.Update(et)
if err != nil {
return nil, fmt.Errorf("failed to hash tile %x: %v", tile.Path, err)
} else if got, want := len(res), 1; got != want {
return nil, fmt.Errorf("wrong number of roots for tile %x: got %v, want %v", tile.Path, got, want)
}
if got, want := res[0].Hash, tile.RootHash; !bytes.Equal(got, want) {
return nil, fmt.Errorf("wrong root hash for tile %x: got %x, calculated %x", tile.Path, got, want)
}
// Make the next iteration of the loop check that the tile above this has the
// root value of this tile stored as the value at the expected leaf index.
needPath, needValue = tile.Path, res[0].Hash
}
return needValue, nil
}
// getTilesForKey loads the tiles on the path from the root to the given leaf.
func (v *MapVerifier) getTilesForKey(rev int, key []byte) ([]*batchmap.Tile, error) {
tiles := make([]*batchmap.Tile, v.prefixStrata+1)
for i := 0; i <= v.prefixStrata; i++ {
tilePath := key[0:i]
tile, err := v.tileFetch(rev, tilePath)
if err != nil {
return nil, fmt.Errorf("failed to read tile %x @ revision %d: %v", tilePath, rev, err)
}
tiles[i] = tile
}
return tiles, nil
}
// toNode converts a TileLeaf into the equivalent Node for HStar3.
func toNode(prefix []byte, l *batchmap.TileLeaf) smt.Node {
path := make([]byte, 0, len(prefix)+len(l.Path))
path = append(append(path, prefix...), l.Path...)
return smt.Node{
ID: node.NewID(string(path), uint(len(path))*8),
Hash: l.Hash,
}
}
// emptyTree is a NodeAccessor for an empty tree with the given ID.
type emptyTree struct {
treeID int64
hasher *coniks.Hasher
}
func (e emptyTree) Get(id node.ID) ([]byte, error) {
return e.hasher.HashEmpty(e.treeID, id), nil
}
func (e emptyTree) Set(id node.ID, hash []byte) {}