1// Copyright 2018 Keybase Inc. All rights reserved.
2// Use of this source code is governed by a BSD
3// license that can be found in the LICENSE file.
4
5package libkbfs
6
7import (
8	"bytes"
9	"context"
10
11	"github.com/keybase/client/go/kbfs/kbfsmd"
12	"github.com/keybase/client/go/kbfs/tlf"
13	merkle "github.com/keybase/go-merkle-tree"
14	"github.com/pkg/errors"
15)
16
17// merkleChecker implements a storage engine that can be used to
18// verify a chain of merkle nodes returned from the server, to
19// validate a given MD leaf.
20type merkleChecker struct {
21	root     *kbfsmd.MerkleRoot
22	nodes    [][]byte
23	nextNode int
24}
25
26var _ merkle.StorageEngine = (*merkleChecker)(nil)
27
28func (mc *merkleChecker) StoreNode(
29	_ context.Context, _ merkle.Hash, _ []byte) error {
30	return errors.New("merkleChecker can't store nodes")
31}
32
33func (mc *merkleChecker) CommitRoot(
34	_ context.Context, _ merkle.Hash, _ merkle.Hash, _ merkle.TxInfo) error {
35	return errors.New("merkleChecker can't commit roots")
36}
37
38func (mc *merkleChecker) LookupNode(
39	_ context.Context, h merkle.Hash) ([]byte, error) {
40	// Assume the hash refers to the next node in the list; if not,
41	// the tree will fail when verifying.
42	if mc.nextNode >= len(mc.nodes) {
43		return nil, errors.Errorf(
44			"Can't lookup node %d when there are only %d nodes",
45			mc.nextNode, len(mc.nodes))
46	}
47	n := mc.nodes[mc.nextNode]
48	mc.nextNode++
49	return n, nil
50}
51
52func (mc *merkleChecker) LookupRoot(_ context.Context) (
53	h merkle.Hash, err error) {
54	return mc.root.Hash, nil
55}
56
57func verifyMerkleNodes(
58	ctx context.Context, kbfsRoot *kbfsmd.MerkleRoot, nodes [][]byte,
59	tlfID tlf.ID) error {
60	// Verify the merkle nodes by pretending to look up the nodes
61	// using a merkle.Tree, which verifies all the nodes along the
62	// path of the lookup.
63	mc := &merkleChecker{kbfsRoot, nodes, 0}
64	config := merkle.NewConfig(
65		merkle.SHA512Hasher{}, 256, 512, kbfsmd.MerkleLeaf{})
66	tree := merkle.NewTree(mc, config)
67	// If any of the nodes returned by the server fail to match their
68	// expected hashes, `Find` will return an error.
69	foundLeaf, rootHash, err := tree.Find(ctx, merkle.Hash(tlfID.Bytes()))
70	if err != nil {
71		return err
72	}
73	if !rootHash.Eq(kbfsRoot.Hash) {
74		return errors.Errorf("Root hashes don't match: found=%v, rootHash=%v",
75			rootHash, kbfsRoot.Hash)
76	}
77	// If the checker returned all the nodes except the last one
78	// (which is the encoded leaf, and not directly walked by the
79	// `Find` call above), we know they all verified and we reached
80	// the expected leaf.
81	if mc.nextNode != len(nodes)-1 {
82		return errors.Errorf("We checked %d nodes instead of %d",
83			mc.nextNode, len(nodes))
84	}
85
86	leafBytes, ok := foundLeaf.(*[]byte)
87	if !ok {
88		return errors.Errorf(
89			"Found merkle leaf isn't a byte slice pointer: %T", foundLeaf)
90	}
91
92	if !bytes.Equal(*leafBytes, nodes[len(nodes)-1]) {
93		return errors.Errorf("Expected leaf didn't match found leaf: expected=%x, found=%x", nodes[len(nodes)-1], *leafBytes)
94	}
95
96	return nil
97}
98