Subject: [Trans] Improving get-entries

From: Paul Hadfield <[email-masked]>
Date: Wed, 26 Oct 2016 17:07:39 +0100

Hi trans,

I'd like to put forward ideas I've had about the /ct/v1/get-entries API.
These are
based on experiences we've had running Google's CT Monitor.

The current API looks something like:

req:
  GET /ct/v1/get-entries?start=10&end=14

resp:
     {
       "entries":[
         {"leaf_input: "...", "extra_data": "..."},
         {"leaf_input: "...", "extra_data": "..."},
         {"leaf_input: "...", "extra_data": "..."},
         {"leaf_input: "...", "extra_data": "..."},
         {"leaf_input: "...", "extra_data": "..."}
       ]
     }

When the log being audited functions compliantly, this is fine.  The client
assumes that the 5 entries returned are [10..14] as requested, and this is
borne out by eventually computing a tree root-hash that matches the log's
STH.

The shortcomings become apparent when monitoring a log that misbehaves.

Assuming the client receives valid, well-formed JSON, there's one class of
bad response that immediately looks wrong: where the number of entries
returned exceeds the number requested.

Logs are at liberty to return fewer entries than requested.

So any other invalid get-entries response is only apparent when the tree's
root hash doesn't match that in the STH.  The client is unable to determine
anything more about what fault was present in the log's response, until
after retrying it notices the response change (perhaps the log operator has
fixed a bug in the log software).

A monitor that is fetching the range of entries from STHn-1 to STHn often
must paginate over the range; if STH validation fails in that case there are
then multiple responses to consider when trying to work out where a log
returned invalid data.

My proposal is to modify the response structure to include entry indices. I
can think of two ways to do so:

req:
  GET /ct/v2/get-entries?start=10&end=14

resp:
     {
       "entries":[
         {"index": 10, "leaf_input: "...", "extra_data": "...", "sct":
"..."},
         {"index": 11, "leaf_input: "...", "extra_data": "...", "sct":
"..."},
         {"index": 12, "leaf_input: "...", "extra_data": "...", "sct":
"..."},
         {"index": 13, "leaf_input: "...", "extra_data": "...", "sct":
"..."},
         {"index": 14, "leaf_input: "...", "extra_data": "...", "sct":
"..."}
       ],
       "sth": ...
     }

or the more concise:

resp:
     {
       "entries":{
         "10": {"leaf_input: "...", "extra_data": "...", "sct": "..."},
         "11": {"leaf_input: "...", "extra_data": "...", "sct": "..."},
         "12": {"leaf_input: "...", "extra_data": "...", "sct": "..."},
         "13": {"leaf_input: "...", "extra_data": "...", "sct": "..."},
         "14": {"leaf_input: "...", "extra_data": "...", "sct": "..."}
       },
       "sth": ...
     }

Some classes of bug in log implementations would be more apparent
this way:  eg. an inadvertent duplication of an entry in the response, or
an entry missing within the range returned.  Out-of-order entries would
be apparent too; but a side-benefit of this could be that the requirement
to return log entries in strict order can be relaxed.

Any thoughts?

thanks,
Paul