in sumdb/tlog/tile.go [302:435]
func (r *tileHashReader) ReadHashes(indexes []int64) ([]Hash, error) {
h := r.tr.Height()
tileOrder := make(map[Tile]int) // tileOrder[tileKey(tiles[i])] = i
var tiles []Tile
// Plan to fetch tiles necessary to recompute tree hash.
// If it matches, those tiles are authenticated.
stx := subTreeIndex(0, r.tree.N, nil)
stxTileOrder := make([]int, len(stx))
for i, x := range stx {
tile, _, _ := tileForIndex(h, x)
tile = tileParent(tile, 0, r.tree.N)
if j, ok := tileOrder[tile]; ok {
stxTileOrder[i] = j
continue
}
stxTileOrder[i] = len(tiles)
tileOrder[tile] = len(tiles)
tiles = append(tiles, tile)
}
// Plan to fetch tiles containing the indexes,
// along with any parent tiles needed
// for authentication. For most calls,
// the parents are being fetched anyway.
indexTileOrder := make([]int, len(indexes))
for i, x := range indexes {
if x >= StoredHashIndex(0, r.tree.N) {
return nil, fmt.Errorf("indexes not in tree")
}
tile, _, _ := tileForIndex(h, x)
// Walk up parent tiles until we find one we've requested.
// That one will be authenticated.
k := 0
for ; ; k++ {
p := tileParent(tile, k, r.tree.N)
if j, ok := tileOrder[p]; ok {
if k == 0 {
indexTileOrder[i] = j
}
break
}
}
// Walk back down recording child tiles after parents.
// This loop ends by revisiting the tile for this index
// (tileParent(tile, 0, r.tree.N)) unless k == 0, in which
// case the previous loop did it.
for k--; k >= 0; k-- {
p := tileParent(tile, k, r.tree.N)
if p.W != 1<<uint(p.H) {
// Only full tiles have parents.
// This tile has a parent, so it must be full.
return nil, fmt.Errorf("bad math in tileHashReader: %d %d %v", r.tree.N, x, p)
}
tileOrder[p] = len(tiles)
if k == 0 {
indexTileOrder[i] = len(tiles)
}
tiles = append(tiles, p)
}
}
// Fetch all the tile data.
data, err := r.tr.ReadTiles(tiles)
if err != nil {
return nil, err
}
if len(data) != len(tiles) {
return nil, fmt.Errorf("TileReader returned bad result slice (len=%d, want %d)", len(data), len(tiles))
}
for i, tile := range tiles {
if len(data[i]) != tile.W*HashSize {
return nil, fmt.Errorf("TileReader returned bad result slice (%v len=%d, want %d)", tile.Path(), len(data[i]), tile.W*HashSize)
}
}
// Authenticate the initial tiles against the tree hash.
// They are arranged so that parents are authenticated before children.
// First the tiles needed for the tree hash.
th, err := HashFromTile(tiles[stxTileOrder[len(stx)-1]], data[stxTileOrder[len(stx)-1]], stx[len(stx)-1])
if err != nil {
return nil, err
}
for i := len(stx) - 2; i >= 0; i-- {
h, err := HashFromTile(tiles[stxTileOrder[i]], data[stxTileOrder[i]], stx[i])
if err != nil {
return nil, err
}
th = NodeHash(h, th)
}
if th != r.tree.Hash {
// The tiles do not support the tree hash.
// We know at least one is wrong, but not which one.
return nil, fmt.Errorf("downloaded inconsistent tile")
}
// Authenticate full tiles against their parents.
for i := len(stx); i < len(tiles); i++ {
tile := tiles[i]
p := tileParent(tile, 1, r.tree.N)
j, ok := tileOrder[p]
if !ok {
return nil, fmt.Errorf("bad math in tileHashReader %d %v: lost parent of %v", r.tree.N, indexes, tile)
}
h, err := HashFromTile(p, data[j], StoredHashIndex(p.L*p.H, tile.N))
if err != nil {
return nil, fmt.Errorf("bad math in tileHashReader %d %v: lost hash of %v: %v", r.tree.N, indexes, tile, err)
}
if h != tileHash(data[i]) {
return nil, fmt.Errorf("downloaded inconsistent tile")
}
}
// Now we have all the tiles needed for the requested hashes,
// and we've authenticated the full tile set against the trusted tree hash.
r.tr.SaveTiles(tiles, data)
// Pull out the requested hashes.
hashes := make([]Hash, len(indexes))
for i, x := range indexes {
j := indexTileOrder[i]
h, err := HashFromTile(tiles[j], data[j], x)
if err != nil {
return nil, fmt.Errorf("bad math in tileHashReader %d %v: lost hash %v: %v", r.tree.N, indexes, x, err)
}
hashes[i] = h
}
return hashes, nil
}