Only bootstrap a compact range once per log

As opposed to doing a new bootstrap with get-proof-by-hash every time
the next root is constructed.  Bootstrapping the compact range from a
get-proof-by-hash query works for the most part, but fails if the log
included a duplicate entry and gives us the index for that instead.  Log
operators with duplicate entries include Cloudflare and Digicert.

If bootstrap fails (unlucky), we try to bootstrap again once the log's
signed tree head moved forward (hoping the last entry has no duplicate).

The more reliable way to bootstrap a compact range would be to use the
get-entry-and-proof endpoint.  This does not work in practise because
some logs are not implementing this endpoint.  Digicert has such logs.

5 files changed, 163 insertions, 57 deletions

diff --git a/internal/ioutil/ioutil.go b/internal/ioutil/ioutil.go
index 7fe6cfc..8e98c65 100644
--- a/internal/ioutil/ioutil.go
+++ b/internal/ioutil/ioutil.go
@@ -1,6 +1,7 @@
 package ioutil
 
 import (
+	"crypto/sha256"
 	"encoding/json"
 	"fmt"
 	"os"
@@ -54,3 +55,34 @@ func DirectoriesExist(paths []string) error {
 	}
 	return nil
 }
+
+func CopyHashes(hashes [][sha256.Size]byte) (ret [][sha256.Size]byte) {
+	for _, hash := range hashes {
+		var dst [sha256.Size]byte
+		copy(dst[:], hash[:])
+		ret = append(ret, dst)
+	}
+	return
+}
+
+func SliceHashes(hashes [][sha256.Size]byte) (ret [][]byte) {
+	for _, hash := range hashes {
+		dst := hash
+		ret = append(ret, dst[:])
+	}
+	return
+}
+
+// UnsliceHashes panics unless all hashes are 32 bytes
+func UnsliceHashes(hashes [][]byte) (ret [][sha256.Size]byte) {
+	for _, hash := range hashes {
+		if got, want := len(hash), sha256.Size; got != want {
+			panic(fmt.Sprintf("bug: invalid hash: size %d", got))
+		}
+
+		var dst [sha256.Size]byte
+		copy(dst[:], hash)
+		ret = append(ret, dst)
+	}
+	return
+}
diff --git a/internal/logutil/logutil.go b/internal/logutil/logutil.go
new file mode 100644
index 0000000..27c3a73
--- /dev/null
+++ b/internal/logutil/logutil.go
@@ -0,0 +1,108 @@
+// Package logutil wraps functions related to a log's Merkle tree.  All log
+// queries use a context where the deadline is set to a hardcoded value.
+package logutil
+
+import (
+	"context"
+	"crypto/sha256"
+	"fmt"
+	"time"
+
+	ct "github.com/google/certificate-transparency-go"
+	"github.com/google/certificate-transparency-go/client"
+	"github.com/transparency-dev/merkle/compact"
+	"github.com/transparency-dev/merkle/rfc6962"
+	"gitlab.torproject.org/rgdd/ct/pkg/merkle"
+	"rgdd.se/silent-ct/internal/ioutil"
+)
+
+const timeout = 10 * time.Second
+
+func GetSignedTreeHead(ctx context.Context, cli client.CheckLogClient) (*ct.SignedTreeHead, error) {
+	rctx, cancel := context.WithTimeout(ctx, timeout)
+	defer cancel()
+	return cli.GetSTH(rctx)
+}
+
+func GetConsistencyProof(ctx context.Context, cli client.CheckLogClient, oldSize, newSize uint64) ([][sha256.Size]byte, error) {
+	if oldSize > newSize {
+		return nil, fmt.Errorf("old size %d is larger than new size %d", oldSize, newSize)
+	}
+	if oldSize == 0 || oldSize == newSize {
+		return [][sha256.Size]byte{}, nil
+	}
+
+	rctx, cancel := context.WithTimeout(ctx, timeout)
+	defer cancel()
+	proof, err := cli.GetSTHConsistency(rctx, oldSize, newSize)
+	if err != nil {
+		return nil, err
+	}
+	return ioutil.UnsliceHashes(proof), nil
+}
+
+func GetEntry(ctx context.Context, cli *client.LogClient, index uint64) (*ct.LeafEntry, error) {
+	rctx, cancel := context.WithTimeout(ctx, timeout)
+	defer cancel()
+
+	rsp, err := cli.GetRawEntries(rctx, int64(index), int64(index))
+	if err != nil {
+		return nil, err
+	}
+	if got, want := len(rsp.Entries), 1; got != want {
+		return nil, fmt.Errorf("too many log entries: %d (want one)", got)
+	}
+	return &rsp.Entries[0], nil
+}
+
+// GetCompactRange constructs the compact range [0, index) by doing a
+// get-proof-by-hash query to obtain the necessary tree hashes
+func GetCompactRange(ctx context.Context, cli *client.LogClient, entry *ct.LeafEntry, index uint64) (*compact.Range, error) {
+	rctx, cancel := context.WithTimeout(ctx, timeout)
+	defer cancel()
+
+	leafHash := merkle.HashLeafNode(entry.LeafInput)
+	proof, err := cli.GetProofByHash(rctx, leafHash[:], index+1)
+	if err != nil {
+		return nil, err
+	}
+	if got, want := uint64(proof.LeafIndex), index; got != want {
+		return nil, fmt.Errorf("invalid leaf index: %d (want %d)", got, want)
+	}
+	tree := ioutil.UnsliceHashes(reverse(proof.AuditPath))
+	return AppendCompactRange(tree, index, [][sha256.Size]byte{leafHash})
+}
+
+// RootHash panics if the compact range is malformed
+func RootHash(cr *compact.Range) (ret [sha256.Size]byte) {
+	rootHash, err := cr.GetRootHash(nil)
+	if err != nil {
+		panic(fmt.Sprintf("bug: compact: %v", err))
+	}
+	if got, want := len(rootHash), sha256.Size; got != want {
+		panic(fmt.Sprintf("bug: invalid root hash: size %d", got))
+	}
+	copy(ret[:], rootHash[:])
+	return
+}
+
+// AppendCompactRange appends a list of leaf hashes to the compact range [0, size)
+func AppendCompactRange(tree [][sha256.Size]byte, size uint64, pending [][sha256.Size]byte) (*compact.Range, error) {
+	rf := compact.RangeFactory{Hash: rfc6962.DefaultHasher.HashChildren}
+	cr, err := rf.NewRange(0, size, ioutil.SliceHashes(tree))
+	if err != nil {
+		return nil, fmt.Errorf("compact: %v", err)
+	}
+	for _, leafHash := range pending {
+		dst := leafHash
+		cr.Append(dst[:], nil)
+	}
+	return cr, nil
+}
+
+func reverse(hashes [][]byte) (ret [][]byte) {
+	for i := len(hashes) - 1; i >= 0; i-- {
+		ret = append(ret, hashes[i])
+	}
+	return
+}
diff --git a/internal/manager/manager.go b/internal/manager/manager.go
index bf1ad92..ce31b1b 100644
--- a/internal/manager/manager.go
+++ b/internal/manager/manager.go
@@ -51,6 +51,7 @@ func New(cfg Config, fch chan []feedback.Event, mch chan monitor.Event, cch chan
 	s, err := storage.New(storage.Config{
 		Bootstrap:  cfg.Bootstrap,
 		Directory:  cfg.Directory,
+		Logger:     cfg.Logger,
 		AlertDelay: cfg.AlertDelay,
 		StaticLogs: cfg.Policy.StaticLogs,
 		RemoveLogs: cfg.Policy.RemoveLogs,
diff --git a/internal/monitor/monitor.go b/internal/monitor/monitor.go
index 6de7193..2fe4d88 100644
--- a/internal/monitor/monitor.go
+++ b/internal/monitor/monitor.go
@@ -11,6 +11,7 @@ package monitor
 
 import (
 	"context"
+	"crypto/sha256"
 	"crypto/x509"
 	"encoding/base64"
 	"fmt"
@@ -32,10 +33,12 @@ type MonitoredLog struct {
 }
 
 // State is the latest append-only state the monitor observed from its local
-// vantage point.  The next entry to download is specified by NextIndex.
+// vantage point.  The compact range covers [0, NextIndex).  The next entry to
+// download from the log is at index NextIndex.
 type State struct {
 	ct.SignedTreeHead `json:"latest_sth"`
-	NextIndex         uint64 `json:"next_index"`
+	CompactRange      [][sha256.Size]byte `json:"compact_range"`
+	NextIndex         uint64              `json:"next_index"`
 }
 
 // Event carries the latest consistent monitor state, found matches, as well as
diff --git a/internal/monitor/tail.go b/internal/monitor/tail.go
index 0e16476..6be165b 100644
--- a/internal/monitor/tail.go
+++ b/internal/monitor/tail.go
@@ -2,15 +2,14 @@ package monitor
 
 import (
 	"context"
-	"crypto/sha256"
 	"fmt"
 	"sync"
-	"time"
 
-	ct "github.com/google/certificate-transparency-go"
 	"github.com/google/certificate-transparency-go/client"
 	"github.com/google/certificate-transparency-go/scanner"
 	"gitlab.torproject.org/rgdd/ct/pkg/merkle"
+	"rgdd.se/silent-ct/internal/ioutil"
+	"rgdd.se/silent-ct/internal/logutil"
 )
 
 type tail struct {
@@ -118,7 +117,7 @@ func (t *tail) nextState(ctx context.Context, state State, c *chunk) (State, err
 }
 
 func (t *tail) nextConsistentState(ctx context.Context, state State) (State, error) {
-	sth, err := getSignedTreeHead(ctx, t.checker)
+	sth, err := logutil.GetSignedTreeHead(ctx, t.checker)
 	if err != nil {
 		return State{}, fmt.Errorf("%s: get-sth: %v", t.checker.BaseURI(), err)
 	}
@@ -128,73 +127,36 @@ func (t *tail) nextConsistentState(ctx context.Context, state State) (State, err
 	newSize := sth.TreeSize
 	newRoot := sth.SHA256RootHash
 
-	proof, err := getConsistencyProof(ctx, t.checker, oldSize, newSize)
+	proof, err := logutil.GetConsistencyProof(ctx, t.checker, oldSize, newSize)
 	if err != nil {
 		return State{}, fmt.Errorf("%s: get-consistency: %v", t.checker.BaseURI(), err)
 	}
-	if err := merkle.VerifyConsistency(oldSize, newSize, oldRoot, newRoot, unslice(proof)); err != nil {
+	if err := merkle.VerifyConsistency(oldSize, newSize, oldRoot, newRoot, proof); err != nil {
 		return State{}, fmt.Errorf("%s: verify consistency: %v", t.checker.BaseURI(), err)
 	}
 
-	return State{SignedTreeHead: *sth, NextIndex: state.NextIndex}, nil
+	return State{SignedTreeHead: *sth, CompactRange: ioutil.CopyHashes(state.CompactRange), NextIndex: state.NextIndex}, nil
 }
 
 func (t *tail) nextIncludedState(ctx context.Context, state State, c *chunk) (State, error) {
-	leafHash := c.leafHashes[0]
-	oldSize := state.NextIndex + uint64(len(c.leafHashes))
-	iproof, err := getInclusionProof(ctx, t.checker, leafHash, oldSize) // FIXME: set leaf index in ctx to hack into tile API
-	if err != nil {
-		return State{}, fmt.Errorf("%s: get-inclusion: %v", t.checker.BaseURI(), err)
-	}
-	if got, want := uint64(iproof.LeafIndex), state.NextIndex; got != want {
-		return State{}, fmt.Errorf("%s: wrong index for get-inclusion proof query %x:%d", t.checker.BaseURI(), leafHash[:], oldSize)
-	}
-	oldRoot, err := merkle.TreeHeadFromRangeProof(c.leafHashes, state.NextIndex, unslice(iproof.AuditPath))
+	cr, err := logutil.AppendCompactRange(state.CompactRange, state.NextIndex, c.leafHashes)
 	if err != nil {
-		return State{}, fmt.Errorf("%s: range proof: %v", t.checker.BaseURI(), err)
+		panic(fmt.Sprintf("bug: %v", err))
 	}
-
-	newSize := state.TreeSize
+	oldRoot := logutil.RootHash(cr)
+	oldSize := state.NextIndex + uint64(len(c.leafHashes))
 	newRoot := state.SHA256RootHash
-	cproof, err := getConsistencyProof(ctx, t.checker, oldSize, newSize)
+	newSize := state.TreeSize
+
+	proof, err := logutil.GetConsistencyProof(ctx, t.checker, oldSize, newSize)
 	if err != nil {
-		return State{}, fmt.Errorf("%s: get-consistency: %v", t.checker.BaseURI(), err)
+		return State{}, fmt.Errorf("%s: tree: get-consistency: %v", t.checker.BaseURI(), err)
 	}
-	if err := merkle.VerifyConsistency(oldSize, newSize, oldRoot, newRoot, unslice(cproof)); err != nil {
-		return State{}, fmt.Errorf("%s: verify consistency: %v", t.checker.BaseURI(), err)
+	if err := merkle.VerifyConsistency(oldSize, newSize, oldRoot, newRoot, proof); err != nil {
+		return State{}, fmt.Errorf("%s: tree: verify consistency: %v", t.checker.BaseURI(), err)
 	}
 
 	state.NextIndex += uint64(len(c.leafHashes))
+	state.CompactRange = ioutil.UnsliceHashes(cr.Hashes())
 	return state, nil
 }
-
-func getInclusionProof(ctx context.Context, cli client.CheckLogClient, leafHash [sha256.Size]byte, size uint64) (*ct.GetProofByHashResponse, error) {
-	rctx, cancel := context.WithTimeout(ctx, 10*time.Second)
-	defer cancel()
-	return cli.GetProofByHash(rctx, leafHash[:], size)
-}
-
-func getConsistencyProof(ctx context.Context, cli client.CheckLogClient, oldSize, newSize uint64) ([][]byte, error) {
-	if oldSize == 0 || oldSize >= newSize {
-		return [][]byte{}, nil
-	}
-	rctx, cancel := context.WithTimeout(ctx, 10*time.Second)
-	defer cancel()
-	return cli.GetSTHConsistency(rctx, oldSize, newSize)
-}
-
-func getSignedTreeHead(ctx context.Context, cli client.CheckLogClient) (*ct.SignedTreeHead, error) {
-	rctx, cancel := context.WithTimeout(ctx, 10*time.Second)
-	defer cancel()
-	return cli.GetSTH(rctx)
-}
-
-func unslice(hashes [][]byte) [][sha256.Size]byte {
-	var ret [][sha256.Size]byte
-	for _, hash := range hashes {
-		var h [sha256.Size]byte
-		copy(h[:], hash)
-		ret = append(ret, h)
-	}
-	return ret
-}