Re: [Trans] Experiment report: The MMD is a lie

[Andrew Ayer <[e-mail]>]

On Thu, 2 Mar 2017 22:29:11 -0500
Richard Barnes <[e-mail]> wrote:

> On Thu, Mar 2, 2017 at 8:55 PM, Andrew Ayer <[e-mail]>
> wrote:
> 
> > Hi Richard,
> >
> > On Thu, 2 Mar 2017 18:58:49 -0500
> > Richard Barnes <[e-mail]> wrote:
> >
> > > On the third hand, it may be possible to hack around even this.
> > > Even if logs are checkpointed, so that only some tree heads are
> > > "official" and used by clients/auditors, the log could produce a
> > > consistency proof to the last official head at ingress time,
> > > which would provide the client/auditor some assurance that the
> > > cert fits into the global history, which could be verified when
> > > the next official tree head comes out.
> >
> > This sounds interesting - could you elaborate?
> >
> 
> (To be clear: Credit for this idea goes to Zakir, I'm just recapping.)
> 
> Obviously, every time you add a cert to the Merkle tree, you get a
> new tree head.  Say a log produces "official" tree heads ever 5 certs
> and all official heads get sync'ed out to clients, who cache them
> all.  (Just for the sake of argument; obviously you could also
> fetch.)  So you would have a history something like this:
> 
> O1 - H2 - H3 - H4 - H5 - O6 - H7 - H8 - ...
> 
> At the time the fourth certificate (C4) is added, the log can produce
> two things:
> 
> 1. An inclusion proof from C4 to H4
> 2. A consistency proof from O1 to H4
> 
> If these can be provided to the client (say in the cert or stapled
> OCSP) and the client has O1, then the client can verify that there is
> a causal link between the two.  This is slightly better than an SCT
> (e.g., it can't be back-dated to before O1), but doesn't prevent
> forked history.  In order to prevent that, the client still has to
> verify that the head H4 is "forward consistent" with the next tree
> head O6.
> 
> So you still need to get a consistency proof that proves that H4 is
> consistent with O6.  You can do that by fetching it from the log, but
> that's no better from a privacy / log scaling POV than fetching
> inclusion proofs.

Due to the need to get a consistency proof for the intermediate head,
I don't see how this is any better than SCTs - this proposal just swaps
SCTs with intermediate heads and inclusion proofs with consistency
proofs.  The backdating prevention isn't compelling, because a
malicious log can just fork off history from an earlier official SCT if
it wants to backdate an entry.

> It would be lovely if the consistency proof between O1 and O6 could
> also be used to verify any intermediate heads you have, since then
> the client could just sync down the consistency between official
> heads and use that to check the intermediates.  TBH, I don't have
> good enough intuition for consistency proofs to know whether this
> works off the top of my head, and I haven't sat down to figure it out.

Unfortunately, a consistency proof does not contain enough
information to do this - the proof contains the minimal number
of hashes needed, so entire subtrees tend to get condensed into their
root hash.

Regards,
Andrew