Repository: google/trillian
Pull request #2658 (2022-01-20 13:28:37)

Upgrade merkle proofs API
This change switches to the new proof generation API in `merkle` repo.


Patch:
diff --git a/docs/merkletree/treetex/main.go b/docs/merkletree/treetex/main.go
index 376e4b82..4b27d97b 100644
--- a/docs/merkletree/treetex/main.go
+++ b/docs/merkletree/treetex/main.go
@@ -29,8 +29,8 @@ import (
 	"math/bits"
 	"strings"
 
-	"github.com/transparency-dev/merkle"
 	"github.com/transparency-dev/merkle/compact"
+	"github.com/transparency-dev/merkle/proof"
 )
 
 const (
@@ -380,12 +380,12 @@ func main() {
 		leafID := compact.NewNodeID(0, uint64(*inclusion))
 		modifyNodeInfo(leafID, func(n *nodeInfo) { n.incPath = true })
 		// TODO(pavelkalinnikov): Highlight the "ephemeral" node too.
-		nf, err := merkle.CalcInclusionProofNodeAddresses(*treeSize, uint64(*inclusion))
+		nodes, err := proof.Inclusion(uint64(*inclusion), *treeSize)
 		if err != nil {
 			log.Fatalf("Failed to calculate inclusion proof addresses: %s", err)
 		}
-		for _, n := range nf {
-			modifyNodeInfo(n.ID, func(n *nodeInfo) { n.proof = true })
+		for _, id := range nodes.IDs {
+			modifyNodeInfo(id, func(n *nodeInfo) { n.proof = true })
 		}
 		for h, i := uint(0), leafID.Index; h < height; h, i = h+1, i>>1 {
 			id := compact.NewNodeID(h, i)
diff --git a/go.mod b/go.mod
index 80665e99..95577e22 100644
--- a/go.mod
+++ b/go.mod
@@ -22,7 +22,7 @@ require (
 	github.com/prometheus/client_golang v1.11.0
 	github.com/prometheus/client_model v0.2.0
 	github.com/pseudomuto/protoc-gen-doc v1.5.0
-	github.com/transparency-dev/merkle v0.0.0-20220104141048-2fe6541b4c0d
+	github.com/transparency-dev/merkle v0.0.0-20220119214824-02a3e2029520
 	go.etcd.io/etcd/client/v3 v3.5.1
 	go.etcd.io/etcd/etcdctl/v3 v3.5.1
 	go.etcd.io/etcd/server/v3 v3.5.1
diff --git a/go.sum b/go.sum
index a1a00e0c..7de3b278 100644
--- a/go.sum
+++ b/go.sum
@@ -778,8 +778,8 @@ github.com/tmc/grpc-websocket-proxy v0.0.0-20200427203606-3cfed13b9966/go.mod h1
 github.com/tmc/grpc-websocket-proxy v0.0.0-20201229170055-e5319fda7802 h1:uruHq4dN7GR16kFc5fp3d1RIYzJW5onx8Ybykw2YQFA=
 github.com/tmc/grpc-websocket-proxy v0.0.0-20201229170055-e5319fda7802/go.mod h1:ncp9v5uamzpCO7NfCPTXjqaC+bZgJeR0sMTm6dMHP7U=
 github.com/tomasen/realip v0.0.0-20180522021738-f0c99a92ddce/go.mod h1:o8v6yHRoik09Xen7gje4m9ERNah1d1PPsVq1VEx9vE4=
-github.com/transparency-dev/merkle v0.0.0-20220104141048-2fe6541b4c0d h1:HZKFUT8f3kjIxyJ1IdJZ8Rw0p2rSu0H1URpS2U0Amac=
-github.com/transparency-dev/merkle v0.0.0-20220104141048-2fe6541b4c0d/go.mod h1:B8FIw5LTq6DaULoHsVFRzYIUDkl8yuSwCdZnOZGKL/A=
+github.com/transparency-dev/merkle v0.0.0-20220119214824-02a3e2029520 h1:G8YKtExgEBSSHbrQKa10Tv+sEixDIuLP11m6yC5agaY=
+github.com/transparency-dev/merkle v0.0.0-20220119214824-02a3e2029520/go.mod h1:B8FIw5LTq6DaULoHsVFRzYIUDkl8yuSwCdZnOZGKL/A=
 github.com/ugorji/go v1.1.4/go.mod h1:uQMGLiO92mf5W77hV/PUCpI3pbzQx3CRekS0kk+RGrc=
 github.com/ugorji/go/codec v0.0.0-20181204163529-d75b2dcb6bc8/go.mod h1:VFNgLljTbGfSG7qAOspJ7OScBnGdDN/yBr0sguwnwf0=
 github.com/ulikunitz/xz v0.5.6/go.mod h1:2bypXElzHzzJZwzH67Y6wb67pO62Rzfn7BSiF4ABRW8=
@@ -1121,6 +1121,7 @@ golang.org/x/sys v0.0.0-20210917161153-d61c044b1678/go.mod h1:oPkhp1MJrh7nUepCBc
 golang.org/x/sys v0.0.0-20211007075335-d3039528d8ac/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/sys v0.0.0-20211019181941-9d821ace8654/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/sys v0.0.0-20211124211545-fe61309f8881/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.0.0-20211210111614-af8b64212486/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/sys v0.0.0-20211216021012-1d35b9e2eb4e h1:fLOSk5Q00efkSvAm+4xcoXD+RRmLmmulPn5I3Y9F2EM=
 golang.org/x/sys v0.0.0-20211216021012-1d35b9e2eb4e/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
@@ -1258,6 +1259,7 @@ google.golang.org/api v0.57.0/go.mod h1:dVPlbZyBo2/OjBpmvNdpn2GRm6rPy75jyU7bmhdr
 google.golang.org/api v0.58.0/go.mod h1:cAbP2FsxoGVNwtgNAmmn3y5G1TWAiVYRmg4yku3lv+E=
 google.golang.org/api v0.59.0/go.mod h1:sT2boj7M9YJxZzgeZqXogmhfmRWDtPzT31xkieUbuZU=
 google.golang.org/api v0.61.0/go.mod h1:xQRti5UdCmoCEqFxcz93fTl338AVqDgyaDRuOZ3hg9I=
+google.golang.org/api v0.63.0/go.mod h1:gs4ij2ffTRXwuzzgJl/56BdwJaA194ijkfn++9tDuPo=
 google.golang.org/api v0.64.0 h1:l3pi8ncrQgB9+ncFw3A716L8lWujnXniBYbxWqqy6tE=
 google.golang.org/api v0.64.0/go.mod h1:931CdxA8Rm4t6zqTFGSsgwbAEZ2+GMYurbndwSimebM=
 google.golang.org/appengine v1.1.0/go.mod h1:EbEs0AVv82hx2wNQdGPgUI5lhzA/G0D9YwlJXL52JkM=
@@ -1348,6 +1350,7 @@ google.golang.org/genproto v0.0.0-20211008145708-270636b82663/go.mod h1:5CzLGKJ6
 google.golang.org/genproto v0.0.0-20211018162055-cf77aa76bad2/go.mod h1:5CzLGKJ67TSI2B9POpiiyGha0AjJvZIUgRMt1dSmuhc=
 google.golang.org/genproto v0.0.0-20211118181313-81c1377c94b1/go.mod h1:5CzLGKJ67TSI2B9POpiiyGha0AjJvZIUgRMt1dSmuhc=
 google.golang.org/genproto v0.0.0-20211206160659-862468c7d6e0/go.mod h1:5CzLGKJ67TSI2B9POpiiyGha0AjJvZIUgRMt1dSmuhc=
+google.golang.org/genproto v0.0.0-20211208223120-3a66f561d7aa/go.mod h1:5CzLGKJ67TSI2B9POpiiyGha0AjJvZIUgRMt1dSmuhc=
 google.golang.org/genproto v0.0.0-20211223182754-3ac035c7e7cb h1:ZrsicilzPCS/Xr8qtBZZLpy4P9TYXAfl49ctG1/5tgw=
 google.golang.org/genproto v0.0.0-20211223182754-3ac035c7e7cb/go.mod h1:5CzLGKJ67TSI2B9POpiiyGha0AjJvZIUgRMt1dSmuhc=
 google.golang.org/grpc v1.8.0/go.mod h1:yo6s7OP7yaDglbqo1J04qKzAhqBH6lvTonzMVmEdcZw=
diff --git a/server/log_rpc_server.go b/server/log_rpc_server.go
index e58e288c..60f4309f 100644
--- a/server/log_rpc_server.go
+++ b/server/log_rpc_server.go
@@ -28,6 +28,7 @@ import (
 	"github.com/google/trillian/types"
 	"github.com/google/trillian/util/clock"
 	"github.com/transparency-dev/merkle"
+	"github.com/transparency-dev/merkle/proof"
 	"github.com/transparency-dev/merkle/rfc6962"
 	"google.golang.org/grpc/codes"
 	"google.golang.org/grpc/status"
@@ -398,11 +399,11 @@ func (t *TrillianLogRPCServer) GetLatestSignedLogRoot(ctx context.Context, req *
 }
 
 func tryGetConsistencyProof(ctx context.Context, firstTreeSize, secondTreeSize uint64, tx storage.ReadOnlyLogTreeTX, hasher merkle.LogHasher) (*trillian.Proof, error) {
-	nodeFetches, err := merkle.CalcConsistencyProofNodeAddresses(firstTreeSize, secondTreeSize)
+	nodes, err := proof.Consistency(firstTreeSize, secondTreeSize)
 	if err != nil {
 		return nil, err
 	}
-	proof, err := fetchNodesAndBuildProof(ctx, tx, hasher, 0, nodeFetches)
+	proof, err := fetchNodesAndBuildProof(ctx, tx, hasher, 0, nodes)
 	if err != nil {
 		return nil, err
 	}
@@ -545,12 +546,11 @@ func (t *TrillianLogRPCServer) closeAndLog(ctx context.Context, logID int64, tx
 // and makes additional checks on the returned proof. Returns a Proof suitable for inclusion in
 // an RPC response
 func getInclusionProofForLeafIndex(ctx context.Context, tx storage.ReadOnlyLogTreeTX, hasher merkle.LogHasher, size, leafIndex uint64) (*trillian.Proof, error) {
-	// We have the tree size and leaf index so we know the nodes that we need to serve the proof
-	proofNodeIDs, err := merkle.CalcInclusionProofNodeAddresses(size, leafIndex)
+	nodes, err := proof.Inclusion(leafIndex, size)
 	if err != nil {
 		return nil, err
 	}
-	return fetchNodesAndBuildProof(ctx, tx, hasher, leafIndex, proofNodeIDs)
+	return fetchNodesAndBuildProof(ctx, tx, hasher, leafIndex, nodes)
 }
 
 func (t *TrillianLogRPCServer) getTreeAndHasher(ctx context.Context, treeID int64, opts trees.GetOpts) (*trillian.Tree, merkle.LogHasher, error) {
diff --git a/server/proof_fetcher.go b/server/proof_fetcher.go
index 88c66c06..48f9523c 100644
--- a/server/proof_fetcher.go
+++ b/server/proof_fetcher.go
@@ -22,6 +22,7 @@ import (
 	"github.com/google/trillian/storage/tree"
 	"github.com/transparency-dev/merkle"
 	"github.com/transparency-dev/merkle/compact"
+	"github.com/transparency-dev/merkle/proof"
 )
 
 // nodeReader provides read-only access to the tree nodes.
@@ -35,19 +36,19 @@ type nodeReader interface {
 // This includes rehashing where necessary to serve proofs for tree sizes between stored tree
 // revisions. This code only relies on the nodeReader interface so can be tested without
 // a complete storage implementation.
-func fetchNodesAndBuildProof(ctx context.Context, nr nodeReader, th merkle.LogHasher, leafIndex uint64, proofNodeFetches []merkle.NodeFetch) (*trillian.Proof, error) {
+func fetchNodesAndBuildProof(ctx context.Context, nr nodeReader, th merkle.LogHasher, leafIndex uint64, pn proof.Nodes) (*trillian.Proof, error) {
 	ctx, spanEnd := spanFor(ctx, "fetchNodesAndBuildProof")
 	defer spanEnd()
-	proofNodes, err := fetchNodes(ctx, nr, proofNodeFetches)
+	nodes, err := fetchNodes(ctx, nr, pn.IDs)
 	if err != nil {
 		return nil, err
 	}
 
-	h := make([][]byte, len(proofNodes))
-	for i, node := range proofNodes {
+	h := make([][]byte, len(nodes))
+	for i, node := range nodes {
 		h[i] = node.Hash
 	}
-	proof, err := merkle.Rehash(h, proofNodeFetches, th.HashChildren)
+	proof, err := pn.Rehash(h, th.HashChildren)
 	if err != nil {
 		return nil, err
 	}
@@ -60,13 +61,9 @@ func fetchNodesAndBuildProof(ctx context.Context, nr nodeReader, th merkle.LogHa
 
 // fetchNodes obtains the nodes denoted by the given NodeFetch structs, and
 // returns them after some validation checks.
-func fetchNodes(ctx context.Context, nr nodeReader, fetches []merkle.NodeFetch) ([]tree.Node, error) {
+func fetchNodes(ctx context.Context, nr nodeReader, ids []compact.NodeID) ([]tree.Node, error) {
 	ctx, spanEnd := spanFor(ctx, "fetchNodes")
 	defer spanEnd()
-	ids := make([]compact.NodeID, 0, len(fetches))
-	for _, fetch := range fetches {
-		ids = append(ids, fetch.ID)
-	}
 
 	nodes, err := nr.GetMerkleNodes(ctx, ids)
 	if err != nil {


Test patch:
diff --git a/server/proof_fetcher_test.go b/server/proof_fetcher_test.go
index 9c14458b..e6bd1048 100644
--- a/server/proof_fetcher_test.go
+++ b/server/proof_fetcher_test.go
@@ -22,7 +22,7 @@ import (
 
 	"github.com/google/trillian/internal/merkle/inmemory"
 	"github.com/google/trillian/storage/testonly"
-	"github.com/transparency-dev/merkle"
+	"github.com/transparency-dev/merkle/proof"
 	"github.com/transparency-dev/merkle/rfc6962"
 )
 
@@ -40,12 +40,12 @@ func TestTree813FetchAll(t *testing.T) {
 	})
 
 	for l := uint64(271); l < ts; l++ {
-		fetches, err := merkle.CalcInclusionProofNodeAddresses(ts, l)
+		nodes, err := proof.Inclusion(l, ts)
 		if err != nil {
 			t.Fatal(err)
 		}
 
-		proof, err := fetchNodesAndBuildProof(ctx, r, hasher, l, fetches)
+		proof, err := fetchNodesAndBuildProof(ctx, r, hasher, l, nodes)
 		if err != nil {
 			t.Fatal(err)
 		}
@@ -57,15 +57,15 @@ func TestTree813FetchAll(t *testing.T) {
 		refProof := mt.PathToRootAtSnapshot(int64(l+1), int64(ts))
 
 		if got, want := len(proof.Hashes), len(refProof); got != want {
-			for i, f := range fetches {
-				t.Errorf("Fetch: %d => %+v", i, f.ID)
+			for i, id := range nodes.IDs {
+				t.Errorf("Fetch: %d => %+v", i, id)
 			}
-			t.Fatalf("(%d, %d): got proof len: %d, want: %d: %v\n%v", ts, l, got, want, fetches, refProof)
+			t.Fatalf("(%d, %d): got proof len: %d, want: %d: %v\n%v", ts, l, got, want, nodes, refProof)
 		}
 
 		for i := 0; i < len(proof.Hashes); i++ {
 			if got, want := hex.EncodeToString(proof.Hashes[i]), hex.EncodeToString(refProof[i].Value.Hash()); got != want {
-				t.Fatalf("(%d, %d): %d got proof node: %s, want: %s l:%d fetches: %v", ts, l, i, got, want, len(proof.Hashes), fetches)
+				t.Fatalf("(%d, %d): %d got proof node: %s, want: %s l:%d nodes: %v", ts, l, i, got, want, len(proof.Hashes), nodes)
 			}
 		}
 	}
@@ -82,12 +82,12 @@ func TestTree32InclusionProofFetchAll(t *testing.T) {
 
 		for s := uint64(2); s <= ts; s++ {
 			for l := uint64(0); l < s; l++ {
-				fetches, err := merkle.CalcInclusionProofNodeAddresses(s, l)
+				nodes, err := proof.Inclusion(l, s)
 				if err != nil {
 					t.Fatal(err)
 				}
 
-				proof, err := fetchNodesAndBuildProof(ctx, r, hasher, l, fetches)
+				proof, err := fetchNodesAndBuildProof(ctx, r, hasher, l, nodes)
 				if err != nil {
 					t.Fatal(err)
 				}
@@ -99,12 +99,12 @@ func TestTree32InclusionProofFetchAll(t *testing.T) {
 				refProof := mt.PathToRootAtSnapshot(int64(l+1), int64(s))
 
 				if got, want := len(proof.Hashes), len(refProof); got != want {
-					t.Fatalf("(%d, %d, %d): got proof len: %d, want: %d: %v\n%v", ts, s, l, got, want, fetches, refProof)
+					t.Fatalf("(%d, %d, %d): got proof len: %d, want: %d: %v\n%v", ts, s, l, got, want, nodes, refProof)
 				}
 
 				for i := 0; i < len(proof.Hashes); i++ {
 					if got, want := hex.EncodeToString(proof.Hashes[i]), hex.EncodeToString(refProof[i].Value.Hash()); got != want {
-						t.Fatalf("(%d, %d, %d): %d got proof node: %s, want: %s l:%d fetches: %v", ts, s, l, i, got, want, len(proof.Hashes), fetches)
+						t.Fatalf("(%d, %d, %d): %d got proof node: %s, want: %s l:%d nodes: %v", ts, s, l, i, got, want, len(proof.Hashes), nodes)
 					}
 				}
 			}
@@ -127,13 +127,13 @@ func TestTree32InclusionProofFetchMultiBatch(t *testing.T) {
 
 	for s := uint64(2); s <= 32; s++ {
 		for l := uint64(0); l < s; l++ {
-			fetches, err := merkle.CalcInclusionProofNodeAddresses(s, l)
+			nodes, err := proof.Inclusion(l, s)
 			if err != nil {
 				t.Fatal(err)
 			}
 
 			// Use the highest tree revision that should be available from the node reader
-			proof, err := fetchNodesAndBuildProof(ctx, r, hasher, l, fetches)
+			proof, err := fetchNodesAndBuildProof(ctx, r, hasher, l, nodes)
 			if err != nil {
 				t.Fatal(err)
 			}
@@ -142,12 +142,12 @@ func TestTree32InclusionProofFetchMultiBatch(t *testing.T) {
 			refProof := mt.PathToRootAtSnapshot(int64(l+1), int64(s))
 
 			if got, want := len(proof.Hashes), len(refProof); got != want {
-				t.Fatalf("(%d, %d, %d): got proof len: %d, want: %d: %v\n%v", 32, s, l, got, want, fetches, refProof)
+				t.Fatalf("(%d, %d, %d): got proof len: %d, want: %d: %v\n%v", 32, s, l, got, want, nodes, refProof)
 			}
 
 			for i := 0; i < len(proof.Hashes); i++ {
 				if got, want := hex.EncodeToString(proof.Hashes[i]), hex.EncodeToString(refProof[i].Value.Hash()); got != want {
-					t.Fatalf("(%d, %d, %d): %d got proof node: %s, want: %s l:%d fetches: %v", 32, s, l, i, got, want, len(proof.Hashes), fetches)
+					t.Fatalf("(%d, %d, %d): %d got proof node: %s, want: %s l:%d nodes: %v", 32, s, l, i, got, want, len(proof.Hashes), nodes)
 				}
 			}
 		}
@@ -165,12 +165,12 @@ func TestTree32ConsistencyProofFetchAll(t *testing.T) {
 
 		for s1 := uint64(2); s1 < ts; s1++ {
 			for s2 := uint64(s1 + 1); s2 < ts; s2++ {
-				fetches, err := merkle.CalcConsistencyProofNodeAddresses(s1, s2)
+				nodes, err := proof.Consistency(s1, s2)
 				if err != nil {
 					t.Fatal(err)
 				}
 
-				proof, err := fetchNodesAndBuildProof(ctx, r, hasher, s1, fetches)
+				proof, err := fetchNodesAndBuildProof(ctx, r, hasher, s1, nodes)
 				if err != nil {
 					t.Fatal(err)
 				}
@@ -178,12 +178,12 @@ func TestTree32ConsistencyProofFetchAll(t *testing.T) {
 				refProof := mt.SnapshotConsistency(int64(s1), int64(s2))
 
 				if got, want := len(proof.Hashes), len(refProof); got != want {
-					t.Fatalf("(%d, %d, %d): got proof len: %d, want: %d: %v\n%v", ts, s1, s2, got, want, fetches, refProof)
+					t.Fatalf("(%d, %d, %d): got proof len: %d, want: %d: %v\n%v", ts, s1, s2, got, want, nodes, refProof)
 				}
 
 				for i := 0; i < len(proof.Hashes); i++ {
 					if got, want := hex.EncodeToString(proof.Hashes[i]), hex.EncodeToString(refProof[i].Value.Hash()); got != want {
-						t.Fatalf("(%d, %d, %d): %d got proof node: %s, want: %s l:%d fetches: %v", ts, s1, s2, i, got, want, len(proof.Hashes), fetches)
+						t.Fatalf("(%d, %d, %d): %d got proof node: %s, want: %s l:%d nodes: %v", ts, s1, s2, i, got, want, len(proof.Hashes), nodes)
 					}
 				}
 			}