Opened 5 years ago

Closed 5 years ago

#163 closed defect (duplicate)

The entire STH history of the log must be accessible

Reported by: rlb@… Owned by: eranm@…
Priority: major Milestone: review
Component: rfc6962-bis Version:
Severity: - Keywords:
Cc:

Description

The public verifiability properties of this system rest on logs producing a
linear sequence of STHs, with no forks. Given an STH, how is an auditor
supposed to tell if it is legitimate?

Right now, the auditor has to download the entire contents of the log up to the
tree size claimed by the STH and compute every possible tree head in order to
conclude that the signed tree head is not among those produced by the log's
contents.

This is an unreasonable burden, which can be fixed with a few small changes:

  • As part of its definition of a log, this specification should include the official STH history of the log, which must be linear. That is, a log comprises not just a Merkle tree (which it is at a given point in time), but also a history of signed Merkle tree heads.
  • The log needs to make this history accessible, by providing an endpoint to access arbitrary STHs, instead of just the current one.
  • In addition, it needs to be possible for a log client to traverse the entire history, either by assigning STHs sequence numbers or by having each STH include a reference to its predecessor.

As an aside, including a predecessor reference in each STH also makes it easy to
recognize forks in history, by looking for two STHs that have the same
predecessor.

As part of this, Section 4 should be make clear that it is not just the current
state of the log, but all past STHs that comprise the official contents of the
log. That is, we require the log not just to be a Merkle tree at any given
point in time, but also to have grown in a consistent manner from initiation.

Change History (6)

comment:1 Changed 5 years ago by rob.stradling@…

  • Component changed from client-behavior to to-be-decided

comment:2 Changed 5 years ago by eranm@…

  • Component changed from to-be-decided to rfc6962-bis
  • Owner changed from draft-ietf-trans-rfc6962-bis@… to eranm@…
  • Status changed from new to assigned

Potential resolution:

  • Add a sequence number field to the STH, to easily identify each STH and know which STH came after which.
  • Add get-sths API for getting historical STHs from log. Said API will take as input a range of STHs (according to their indices, timestamps or tree sizes - TBD).

IMHO the addition of get-sths is pretty not-controversial: having historical STHs to compare with output from get-entries is useful for making sure the MMD was never blown.

Sequence numbers need more reasoning - does give an easy way to refer to an STH, but may be incompatible with rlb's idea of "canonical STHs".

comment:3 Changed 5 years ago by benl@…

This is incorrect: "Right now, the auditor has to download the entire contents of the log up to the
tree size claimed by the STH and compute every possible tree head in order to
conclude that the signed tree head is not among those produced by the log's
contents."

That is not so, it only needs to calculate the head generated by the tree of exactly that size.

As a result, I am not sure what problem this solves.

comment:4 Changed 5 years ago by eranm@…

(alternative discussed out-of-band with colleagues):
Allow requesting STHs by specification of time range.
Similar to get-entries, the log would return a list of STHs issued on that time range (capped by an amount chosen by the log).

The problem it solves is the lack of ability to verify that the log did not breach the MMD throughout its lifetime: A submission's timestamp is available via get-entries, but unless a monitor has observed STHs issued by the log around the time an entry was created for it, there's no proof that the entry was incorporated within the MMD.

comment:5 Changed 5 years ago by eranm@…

  • Milestone set to review

Suggest marking as a duplicate of 160.

comment:6 Changed 5 years ago by melinda.shore@…

  • Resolution set to duplicate
  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.