added client-side inclusion proof verification

3 files changed, 94 insertions, 4 deletions

diff --git a/client/client.go b/client/client.go
index c9aaee3..5209a83 100644
--- a/client/client.go
+++ b/client/client.go
@@ -14,6 +14,7 @@ import (
 	"net/http"
 
 	"github.com/golang/glog"
+	"github.com/google/trillian/merkle/rfc6962"
 	"github.com/system-transparency/stfe"
 	"github.com/system-transparency/stfe/server/descriptor"
 	"golang.org/x/net/context/ctxhttp"
@@ -130,13 +131,33 @@ func (c *Client) GetSth(ctx context.Context) (*stfe.StItem, error) {
 }
 
 func (c *Client) GetConsistencyProof(ctx context.Context, first, second uint64) (*stfe.StItem, error) {
-	glog.V(2).Info("creating get-consistency-proof request")
 	return nil, fmt.Errorf("TODO")
 }
 
-func (c *Client) GetProofByHash(ctx context.Context, treeSize uint64, hash []byte) (*stfe.StItem, error) {
-	glog.V(2).Info("creating get-proof-by-hash request")
-	return nil, fmt.Errorf("TODO")
+func (c *Client) GetProofByHash(ctx context.Context, treeSize uint64, rootHash, leaf []byte) (*stfe.StItem, error) {
+	leafHash := rfc6962.DefaultHasher.HashLeaf(leaf)
+	req, err := http.NewRequest("GET", c.protocol()+c.Log.BaseUrl+"/get-proof-by-hash", nil)
+	if err != nil {
+		return nil, fmt.Errorf("failed creating http request: %v", err)
+	}
+	req.Header.Set("Content-Type", "application/json")
+	q := req.URL.Query()
+	q.Add("hash", base64.StdEncoding.EncodeToString(leafHash))
+	q.Add("tree_size", fmt.Sprintf("%d", treeSize))
+	req.URL.RawQuery = q.Encode()
+	glog.V(2).Infof("created http request: %s %s", req.Method, req.URL)
+
+	item, err := c.doRequestWithStItemResponse(ctx, req)
+	if err != nil {
+		return nil, err
+	}
+	if item.Format != stfe.StFormatInclusionProofV1 {
+		return nil, fmt.Errorf("bad StItem format: %v", item.Format)
+	}
+	if err := VerifyInclusionProofV1(item, rootHash, leafHash); err != nil {
+		return nil, fmt.Errorf("bad inclusion proof: %v", err)
+	}
+	return item, nil
 }
 
 func (c *Client) GetEntries(ctx context.Context, start, end uint64) (*stfe.StItem, error) {
diff --git a/client/get-proof-by-hash/main.go b/client/get-proof-by-hash/main.go
new file mode 100644
index 0000000..78a4621
--- /dev/null
+++ b/client/get-proof-by-hash/main.go
@@ -0,0 +1,58 @@
+package main
+
+import (
+	"context"
+	"flag"
+	"fmt"
+
+	"encoding/base64"
+	"net/http"
+
+	"github.com/golang/glog"
+	"github.com/system-transparency/stfe"
+	"github.com/system-transparency/stfe/client"
+)
+
+var (
+	operators      = flag.String("operators", "../../server/descriptor/stfe.json", "path to json-encoded list of log operators")
+	logId          = flag.String("log_id", "B9oCJk4XIOMXba8dBM5yUj+NLtqTE6xHwbvR9dYkHPM=", "base64-encoded log identifier")
+	chain          = flag.String("chain", "../../server/testdata/chain/ee.pem", "path to pem-encoded certificate chain that the log accepts")
+	signedTreeHead = flag.String("sth", "AAEgB9oCJk4XIOMXba8dBM5yUj+NLtqTE6xHwbvR9dYkHPMAAAF1jnn7fwAAAAAAAAAxICCqLJn4QWYd0aRIRjDWGf4GWalDIb/iH60jSSX89WgvAAAAQF9XPFRdM56KaelHFFg1RqjTw1yFL085zHhdNkLeZh9BCXxVTByqrHEMngAkY69EX45aJMWh9NymmPau0qoigA8=", "base64-encoded StItem of type StFormatSignedTreeHeadV1")
+	entry          = flag.String("entry", "AAUBOCAsYkIyzdIhdxKU37sxCsoACg32rItmtpbZDvBv3vtkow==", "base64-encoded StItem of type StFormatChecksumV1")
+)
+
+func main() {
+	flag.Parse()
+
+	cli, err := client.NewClientFromPath(*logId, *chain, "", *operators, &http.Client{}, true)
+	if err != nil {
+		glog.Fatal(err)
+	}
+
+	var sth stfe.StItem
+	if err := sth.UnmarshalB64(*signedTreeHead); err != nil {
+		glog.Fatalf("bad signed tree head: %v", err)
+	}
+	if err := client.VerifySignedTreeHeadV1(&sth, cli.Log.Scheme, cli.Log.Key()); err != nil {
+		glog.Fatalf("bad signed tree head: %v", err)
+	}
+	glog.V(3).Info("verified sth")
+
+	leaf, err := base64.StdEncoding.DecodeString(*entry)
+	if err != nil {
+		glog.Fatalf("failed decoding entry: %v", err)
+	}
+	proof, err := cli.GetProofByHash(context.Background(), sth.SignedTreeHeadV1.TreeHead.TreeSize, sth.SignedTreeHeadV1.TreeHead.RootHash.Data, leaf)
+	if err != nil {
+		glog.Fatalf("get-proof-by-hash failed: %v", err)
+	}
+	glog.V(3).Info("verified inclusion proof")
+
+	str, err := proof.MarshalB64()
+	if err != nil {
+		glog.Fatalf("failed encoding valid inclusion proof: %v", err)
+	}
+	fmt.Println(str)
+
+	glog.Flush()
+}
diff --git a/client/verify.go b/client/verify.go
index cd2023b..3668bf2 100644
--- a/client/verify.go
+++ b/client/verify.go
@@ -7,6 +7,8 @@ import (
 	"crypto/ed25519"
 	"crypto/tls"
 
+	"github.com/google/trillian/merkle"
+	"github.com/google/trillian/merkle/rfc6962"
 	"github.com/system-transparency/stfe"
 )
 
@@ -42,6 +44,15 @@ func VerifySignedTreeHeadV1(sth *stfe.StItem, scheme tls.SignatureScheme, key cr
 	return nil
 }
 
+// VerifyInclusionProofV1 verifies that an inclusion proof is valid
+func VerifyInclusionProofV1(proof *stfe.StItem, rootHash, leafHash []byte) error {
+	path := make([][]byte, 0, len(proof.InclusionProofV1.InclusionPath))
+	for _, nh := range proof.InclusionProofV1.InclusionPath {
+		path = append(path, nh.Data)
+	}
+	return merkle.NewLogVerifier(rfc6962.DefaultHasher).VerifyInclusionProof(int64(proof.InclusionProofV1.LeafIndex), int64(proof.InclusionProofV1.TreeSize), path, rootHash, leafHash)
+}
+
 // supportedScheme checks whether the client library supports the log's
 // signature scheme and public key type
 func supportedScheme(scheme tls.SignatureScheme, key crypto.PublicKey) error {