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
|
// 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.
// verify is a simple example that shows how a verifiable map can be used to
// demonstrate inclusion.
package main
import (
"bytes"
"crypto"
"encoding/json"
"flag"
"fmt"
"os"
"path/filepath"
"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"
"k8s.io/klog/v2"
)
const hash = crypto.SHA512_256
var (
mapDir = flag.String("map_dir", "", "Directory containing map tiles.")
treeID = flag.Int64("tree_id", 12345, "The ID of the tree. Used as a salt in hashing.")
valueSalt = flag.String("value_salt", "v1", "Some string that will be smooshed in with the generated value before hashing. Allows generated values to be deterministic but variable.")
key = flag.Int64("key", 0, "This is the seed for the key that will be looked up.")
prefixStrata = flag.Int("prefix_strata", 1, "The number of strata of 8-bit strata before the final strata.")
)
func main() {
klog.InitFlags(nil)
flag.Parse()
mapDir := filepath.Clean(*mapDir)
if mapDir == "" {
klog.Fatal("No output provided")
}
// 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 := hash.New()
_, _ = fmt.Fprintf(h, "%d", *key)
keyPath := h.Sum(nil)
leafID := node.NewID(string(keyPath), uint(len(keyPath)*8))
expectedString := fmt.Sprintf("[%s]%d", *valueSalt, *key)
expectedValueHash := coniks.Default.HashLeaf(*treeID, leafID, []byte(expectedString))
// Read the tiles required for this check from disk.
tiles, err := getTilesForKey(mapDir, keyPath)
if err != nil {
klog.Exitf("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: *treeID}
needPath, needValue := keyPath, expectedValueHash
for i := *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) {
klog.Fatalf("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 { //nolint:staticcheck // Remove "related info" lint message for suppressed lint check below.
klog.Fatalf("couldn't find expected leaf %x in tile %x", needLeafPath, tile.Path)
}
if !bytes.Equal(leaf.Hash, needValue) { //nolint:staticcheck // Suppress false +ve due to linter not understanding that klog.Fatal() above will exit if leaf == nil
klog.Fatalf("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, coniks.Default.HashChildren,
uint(len(tile.Path)+len(leaf.Path))*8, uint(len(tile.Path))*8)
if err != nil {
klog.Fatalf("failed to create HStar3 for tile %x: %v", tile.Path, err)
}
res, err := hs.Update(et)
if err != nil {
klog.Fatalf("failed to hash tile %x: %v", tile.Path, err)
} else if got, want := len(res), 1; got != want {
klog.Fatalf("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) {
klog.Fatalf("wrong root hash for tile %x: got %x, calculated %x", tile.Path, want, got)
}
// 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
}
// If we get here then we have proved that the value was correct and that the map
// root commits to this value. Any other user with the same map root must see the
// same value under the same key we have checked.
klog.Infof("key %d found at path %x, with value '%s' (%x) committed to by map root %x", *key, keyPath, expectedString, expectedValueHash, needValue)
}
// getTilesForKey loads the tiles on the path from the root to the given leaf.
func getTilesForKey(mapDir string, key []byte) ([]*batchmap.Tile, error) {
tiles := make([]*batchmap.Tile, *prefixStrata+1)
for i := 0; i <= *prefixStrata; i++ {
tilePath := key[0:i]
tileFile := fmt.Sprintf("%s/path_%x", mapDir, tilePath)
in, err := os.ReadFile(tileFile)
if err != nil {
return nil, fmt.Errorf("failed to read file %s: %v", tileFile, err)
}
tile := &batchmap.Tile{}
if err := json.Unmarshal(in, tile); err != nil {
return nil, fmt.Errorf("failed to parse tile in %s: %v", tileFile, 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 {
// CodeQL mollification:
if pLen := len(prefix) + len(l.Path); pLen > 1*1024*1024 {
panic(fmt.Sprintf("absurd path length %d", pLen))
}
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
}
func (e emptyTree) Get(id node.ID) ([]byte, error) {
return coniks.Default.HashEmpty(e.treeID, id), nil
}
func (e emptyTree) Set(id node.ID, hash []byte) {}
|
