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

From: Richard Barnes <[email-masked]>
Date: Thu, 2 Mar 2017 18:58:49 -0500

Hey all,

This might not be quite the right list for this, but since I'm not aware of
a "ct-implementors" list, I thought I'd go ahead and post it.

tl;dr: Logging with live updates to the Merkle tree can be done at rates of
at least 10-150qps.

It had bothered me for a while that there was this 24-hour delay at the
heart of CT, and I was never satisfied with the hand-wavy answers about
distributed consensus.  At the CT policy days last week, Nick, Zakir, and I
decided to see if we could build a log with two properties:

1. It updates in real time, i.e., it ensures that the Merkle tree is
updated before returning 200/OK to an add-chain query.
2. It updates fast enough that it could plausibly keep up with real log
loads

Property (1) means that if your signer was fast enough to keep up, you
could return an STH instead of an SCT in response to an add-chain query.
This should be appealing to log operators, since if you log this way, you
never have to worry about missing your MMD -- your MMD is zero.

The only real innovation needed here is to focus on the bare minimum that
needs to be done to update a Merkle tree.  In order to add a certificate to
the  tree, you don't need to track the whole tree, you just need to keep
track of a log-size "frontier" of the heads of complete subtrees; these
also happen to be the elements of an inclusion proof from the new cert to
the tree head immediately after its addition.  Then all you need to do to
add a cert to the tree is ensure that the following are done atomically:

- Fetch the latest frontier
- Update it with the new certificate
- Store the certificate and the new frontier

Then you can update your log as fast as your database can do those
transactions.  To estimate how fast this can happen in practice, we tested
out a few storage configurations behind a simple Go front-end that
implements the add-chain endpoint from RFC 6962 [1]:

A. Google Cloud Spanner [2]
B. Postgres running on a dedicated SSD, on the same server as the front end
C. Postgres running remote, on a shared hard disk

(All of these can trivially support multiple front-ends, due to transaction
wrapping; it turns out not to help, because you're limited by the
transaction processing rate.)

Spanner turned out to be the slowest by quite a bit [3], operating at
around 10qps.  Postgres on an SSD was fastest, at 150-200qps.  Postgres in
a more realistic configuration was in the middle, at around 60qps.
Obviously, there's some trade-off with reliability here, but since Google
is using Spanner for their logs, it seems like the Spanner number should
represent a pretty acceptable reliability level.

The upshot is that this style of logging seems eminently feasible.  Almost
all CT logs are growing at well less than 10qps [2], and even Let's Encrypt
on its worst days only generates about 115qps.  And I have pretty high
confidence that if you actually put some thought into designing the storage
scheme, you could get some additional margin here.

=====

What does this mean for CT?  I'm not totally sure.

On the one hand, it seems like it adds some credibility to the idea of
relying more on inclusion proofs, since in principle, a log can issue an
inclusion proof to a tree head immediately on cert submission.  It
certainly makes me wonder if there's an argument in here for getting rid of
SCTs entirely.

On the other hand, it may not be dispositive.  Even if you can create an
inclusion proof to *a* tree head, it's not going to be that useful unless
that a client/auditor can connect that tree head up to some notion of the
global state -- and it will not be feasible for that global state to be the
entire set of tree heads, one per certificate!  Assuming then that logs
will have to only issue global state periodically, there will still be
delay in issuance, just driven by client/auditor caching capabilities
instead of log ingress capabilities.

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.

In any case, we should stop thinking that log delay and the MMD are
essential properties of this system.

--Richard

[1] https://github.com/bifurcation/loggerhead
[2] https://github.com/bifurcation/loggerhead/tree/spanner
[3] It was also really expensive!  Cost almost $100 in free trial credit to
run this experiment :)
[4] https://sslmate.com/labs/ct_growth/

---

From: Ryan Sleevi <[email-masked]>
Date: Thu, 2 Mar 2017 17:04:57 -0800

> essential properties of this system.

I'm confused by this conclusion, and apologies if I've misunderstood.

Can you explain how this statement differs, from say a discussion about
keeping a database in RAM and never flushing to disk? You can have amazing
QPS - but terrible reliability. It sounds like you're describing that
you've built an unreliable, but efficient, system, and are using that as
proof that reliability is not a critical property?

---

From: Ryan Sleevi <[email-masked]>
Date: Thu, 2 Mar 2017 17:06:19 -0800

> proof that reliability is not a critical property?

And as a concrete example, consider
https://groups.google.com/a/chromium.org/d/msg/ct-policy/ohtZ64gLN3I/q4nSPkrWCQAJ

---

From: Richard Barnes <[email-masked]>
Date: Thu, 2 Mar 2017 20:38:32 -0500

> proof that reliability is not a critical property?

That's part of why I used Spanner as one of our test points.  At least
according to Al at the CT policy days, that's what his team is using as
storage for their logs.  So presumably it's suitably reliable?

I'm definitely willing to admit there's a trade-off here.  My point is just
that the reliability requirements are not inconsistent with a sufficiently
high transaction rate to serve existing needs.

--Richard

---

From: Andrew Ayer <[email-masked]>
Date: Thu, 2 Mar 2017 17:55:14 -0800

Hi Richard,

On Thu, 2 Mar 2017 18:58:49 -0500
Richard Barnes <[email-masked]> 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?

Regards,
Andrew

---

From: Richard Barnes <[email-masked]>
Date: Thu, 2 Mar 2017 22:29:11 -0500

> 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.

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.

--Richard

---

From: Ryan Sleevi <[email-masked]>
Date: Thu, 2 Mar 2017 21:37:56 -0800

On Thu, Mar 2, 2017 at 5:38 PM, Richard Barnes <[email-masked]> wrote:

> I'm definitely willing to admit there's a trade-off here.  My point is
> just that the reliability requirements are not inconsistent with a
> sufficiently high transaction rate to serve existing needs.
>

Again, I'm confused as to how you reach that conclusion, so apologies if
I'm just dense here.

You've compared an extremely reliable, globally consistent storage system
and established one bound (10qps) for your idea. You've then compared an
extremely unreliable, globally inconsistent storage system and established
another bound (60qps-200qps)

I'm not sure why you've introduced the unreliable system - which has SPOF
written all over it - or how it relates to this proposal. Are you
suggesting that reliability is no longer necessary?

Assuming reliability is necessary, and we accept 10qps for 'extremely high'
reliability, and 60qps for 'extremely low reliability', doesn't your
solution only provide value iff the growth rate of the ecosystem is
somewhere within these bounds? Are you asserting that "10-60 qps should be
enough for everyone"?

I guess what I'm trying to figure out is what the consequence of this
experiment is - are you proposing change? Because aren't those bounds only
relevant to the specific experiment you did, which is related to your
proposed solution for STH-on-every-cert?

I apologize if I'm simply dense from what this implementation feedback is
related to, or understanding the objective of this experiment. You suggest
it may be feasible, but I see those numbers and reach the opposite
conclusion, so I'm trying to understand where I'm misunderstanding.

---

From: Al Cutter <[email-masked]>
Date: Fri, 3 Mar 2017 10:19:19 +0000

I thought I'd throw a few things into the discussion...

So, I think what Richard, Nick and Zakir have reinvented, is more or less
the original plan for how CT was going to work; chains would be submitted,
and the caller would be told either a) here's your inclusion proof+STH, or
b) come back and try again in a bit.
At that time, CAs were understandably wary of blocking their issuance on
processes with an unbounded (or at least slightly hand-wavy) deadline.
Enter SCTs, which we we all know and, um, love.
(You all probably knew that already, and if you've been following or
involved with CT for a while also probably know a lot of the trade-offs
that we made in our Google log implementation, mostly swapping speed and
comfort for quite paranoid levels of redundancy.)

As I said during the talk Pierre and I gave at the start of the CT policy
days about running logs at scale, personally, I really like the idea of
serving proofs directly (I think I said something along the lines of it
holding a special place in my heart) and I suspect that's at least in part
what's triggered this to resurface.

To detour for a moment, Richard's right in that you certainly can update
Merkle trees in real time, and very quickly - in fact, if you forgo the
full-fat Merkle tree and use what we term a "compact" merkle tree (see
github [1] for details - I believe this is what Richard describes as his
"frontier" tree), then you can update it at many hundreds of thousands of
qps, when you start trying to actually store and sign things it slows down
a fair bit, but depending on storage layer/layout/and whatnots you could
still reasonably expect to be able to do many thousands per second.
Obviously as you crank the hypothetical lever away from "low reliability"
(perhaps not really useful* in the current CT system, but impressively
fast) over to "reliable and globally consistent" things slow down further,
but our recent experiences with Trillian suggest that you can still do this
sort of thing at multiple hundreds to a couple of thousand qps if you're
willing to batch a bit (Trillian has levers too, in particular to trade off
between throughput, scale, and low integration latency, but we need to do
more testing to better understand the full implications.)

Back to the policy day; the next thing I said after sharing my wistful
dreams, was that I felt that in order for anything like those dreams to
become reality there would need to be changes in the ecosystem, the ones I
called out in particular were that we'd need to have many logs, and that
they'd need to be open.  The reason for this, which I think I didn't go
into any detail about and Ryan has touched on above, is because cold hard
operational reality has a habit of crashing through the door whenever
there's something I'd like to have - things like machines failing, software
updates (even rolling ones), bugs, master elections, network partitions,
and Stuff, all mean that you will not *always* be able to have your
throughput, and there *will* be stretches of time you are completely unable
to update your tree (I'm assuming the local/global level is pulled over
towards the global side here). If the ecosystem has sufficient open logs
and CAs were all attempting to log in parallel to sufficiently large subset
of those, they maybe that's fine and it turns out to be overwhelmingly
likely that there are enough logs not having a bad day for the world to
roll on.

I think none of this dream world is in conflict with the current state of
-bis, other than possibly that requirement to limit STH issuance to one per
hour. I understand why it got put in, but I do wonder if it really belongs
in the Gossip doc rather than -bis where it's potentially discouraging This
Sort of Thing.

Anyway, I just thought I'd chip in with some colour.

[1]
https://github.com/google/certificate-transparency/blob/master/cpp/merkletree/compact_merkle_tree.h

On Fri, Mar 3, 2017 at 5:37 AM, Ryan Sleevi <[email-masked]> wrote:

> Assuming reliability is necessary, and we accept 10qps for 'extremely
> high' reliability, and 60qps for 'extremely low reliability', doesn't your
> _______________________________________________
> Trans mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/trans
>
>

---

From: Richard Barnes <[email-masked]>
Date: Fri, 3 Mar 2017 10:23:14 -0500

Hey Al,

Thanks for chipping in.  I'm not surprised to hear that this stuff is not
novel :)

Since I've got you here, here's one thing I'm confused about: Why don't you
have the same reliability problems with SCTs?  Before you issue the SCT,
you've got to be really sure that you've got that cert and it's going to
make it into the log.

The only difference we're talking about here is that in addition to that
append operation, you also have a read operation.  Either way, you have a
stack of things you're appending to, either a stack of just certs or a
stack of (cert, frontier) pairs.  In the SCT case, you have to reliably
push a cert onto the stack.  In the no-MMD case, you have to peek at the
top of the stack to get the last frontier, then push the new (cert,
frontier) pair.  That does extend the scope of the transaction a bit, but
it certainly doesn't seem like it should take you from "effectively
instantaneous" to "we'll get back to you tomorrow".

Am I misunderstanding how reliability works for SCTs?  If you have a
reliability problem with updating the tree in this way, don't you already
have a reliability problem with SCTs?

--Richard

On Fri, Mar 3, 2017 at 5:19 AM, Al Cutter <[email-masked]> wrote:

> [1] https://github.com/google/certificate-transparency/blob/
> master/cpp/merkletree/compact_merkle_tree.h
>

---

From: Paul Wouters <[email-masked]>
Date: Fri, 3 Mar 2017 10:40:26 -0500 (EST)

On Thu, 2 Mar 2017, Richard Barnes wrote:

Richard,

> This might not be quite the right list for this, but since I'm not aware of a "ct-implementors" list, I thought
> I'd go ahead and post it.
> 
> tl;dr: Logging with live updates to the Merkle tree can be done at rates of at least 10-150qps.

Thanks for the update. Am I right that this resolves your concerns about
6962bis, and that you no longer think the specification needs changing
to support the expected load for the deployment you have in mind?

I'm trying to determine if we are now ready to send the document to the IESG.

Paul

---

From: Richard Barnes <[email-masked]>
Date: Fri, 3 Mar 2017 10:59:07 -0500

> I'm trying to determine if we are now ready to send the document to the

Short answer: No.

Longer answer: After a late-night pizza / scotch / whiteboard session with
Eran and a few others last week, I have some more focused asks.  I'll try
to get them written up this afternoon.

--Richard

---

From: Eric Mill <[email-masked]>
Date: Fri, 3 Mar 2017 11:12:56 -0500

> comfort for quite paranoid levels of redundancy.)

Is it possible to "let the market decide" whether STHs can be served in a
reasonable timeframe so we have a chance to figure this out in practice?
For example, what if browsers with a CT policy allowed either SCTs *or*
STHs to qualify?

Logs could optionally offer endpoints that produce STHs immediately upon
logging (in addition to their SCT endpoints), and CAs could see whether
logs can produce STHs at levels of latency and reliability acceptable to
production use.

-- Eric

---

From: Al Cutter <[email-masked]>
Date: Fri, 3 Mar 2017 16:36:55 +0000

> Thanks for chipping in.  I'm not surprised to hear that this stuff is not

You're welcome, and yeah - we've been at this a while :)

>
> Since I've got you here, here's one thing I'm confused about: Why don't
> you have the same reliability problems with SCTs?  Before you issue the
> SCT, you've got to be really sure that you've got that cert and it's going
> to make it into the log.
>

Because this decouples the acceptance (distributed) side from the (serial)
sequencing side.
So, for example, our first generation logs do this for every add-*chain:
 - write to a journal file in a quorum of geographically distributed
datacentres, if that fails, return an error to the CA
 - write the requested cert to the queue of things to integrate (which is
also a distributed store, Megastore in ye olde logs, and Spanner nowadays),
if that fails, journal it and return an error to the CA
 - write "Win!" to the journal, and return the SCT to the CA, otherwise
return an error.

You're probably thinking that's bordering on the excessively paranoid, and
I'm not going to argue, but I hope you'd agree that we've got your cert, or
at least told you otherwise.  Note that to do this doesn't **require**
global consensus (unless you promise not to include dupes in your log).

So I get to stay available, potentially even in the event of loss of global
consensus, and certainly in the case where the dog ate my signer, it's just
that I only have twentyish hours in which to sort it out (rather than a
handful of seconds).

> append operation, you also have a read
>

Well, you have a transactional operation consisting of a read and one or
more writes which must all be [globally] strongly consistent or you'll fork
your tree, which is a bit different.

operation.  Either way, you have a stack of things you're appending to,
> either a stack of just certs or a stack of (cert, frontier) pairs.  In the
> SCT case, you have to reliably push a cert onto the stack.  In the no-MMD
> case, you have to peek at the top of the stack to get the last frontier,
> then push the new (cert, frontier) pair.  That does extend the scope of the
> transaction a bit, but it certainly doesn't seem like it should take you
> from "effectively instantaneous" to "we'll get back to you tomorrow".
>

How do you this in practice?
 - have a single webserver handling all the add requests and sequencing
in-line?
 - have lots of webservers all internally RPC to a single "sequencing"
server?

What happens when they catch fire?
Failover - you're down until everything is back up and running, you can
probably do that in O(tens of seconds) say (you really don't want multiple
of these things believing they're the one and only though, so do it
properly), and depending on your storage infrastructure your master
node/group leader/whatever could be far away from the new location slowing
these operations down until it migrates or your old machines come back.

 - Have all your frontends try to transactionally update the tree state
when they get a request
At anything above very noddy add-chain rates (i.e. where they're arriving
in parallel to different frontends) you're going to fail almost all of
these transactions because they have to be strongly consistent or you fork
your tree.

Like I said, I really love the idea of embedding proofs, and I even think
it's likely to be technically doable with Trillian based logs at a broadly
acceptable latency, but only with the ecosystem evolution I mentioned in
the last mail.
Modulo the STH frequency thing, I'm not aware of a reason why -bis can't
support that in its current state, although certainly if this is something
which were desired/not universally despised then the text around the
add-chain (or whatever it's called in -bis) method could perhaps be widened
to allow for returning TransItems containing things other than X.509 SCTs
for example.  But I believe you could compose several calls to get a
similar result as it stands currently.

> have a reliability problem with SCTs?

Maybe, a little bit :)
But I wouldn't hold it against you or anyone else who hasn't already built
and operated a Log at scale.

>>>>> Can you explain how this statement differs, from say a discussion
>>>>> about keeping a database in RAM and never flushing to disk? You can have
>>>>> amazing QPS - but terrible reliability. It sounds like you're describing
>>>>> that you've built an unreliable, but efficient, system, and are using that
>>>>> as proof that reliability is not a critical property?
>>>>>
>>>>
>>> You've compared an extremely reliable, globally consistent storage
>>> system and established one bound (10qps) for your idea. You've then
>>> compared an extremely unreliable, globally inconsistent storage system and
>>> established another bound (60qps-200qps)
>>>
>>> I'm not sure why you've introduced the unreliable system - which has
>>> SPOF written all over it - or how it relates to this proposal. Are you
>>> I apologize if I'm simply dense from what this implementation feedback
>>> is related to, or understanding the objective of this experiment. You
>>> suggest it may be feasible, but I see those numbers and reach the opposite

---

From: Andrew Ayer <[email-masked]>
Date: Fri, 3 Mar 2017 11:08:23 -0800

On Thu, 2 Mar 2017 22:29:11 -0500
Richard Barnes <[email-masked]> 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.
> >
> 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:
> 
> At the time the fourth certificate (C4) is added, the log can produce
> two things:
> 
> 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.
> 
> 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

---

From: Kurt Roeckx <[email-masked]>
Date: Fri, 3 Mar 2017 20:29:51 +0100

> scheme, you could get some additional margin here.

Let's encrypt seems to be doing around 1M per day on "its worst
days", which is still only in the range of 10 per second.

Kurt

---

From: Rob Stradling <[email-masked]>
Date: Fri, 3 Mar 2017 20:32:23 +0000

> days", which is still only in the range of 10 per second.

That assumes an even distribution throughout the day, which isn't the 
reality.

A couple of days ago, Google's Pilot log generated 582 SCTs during a 
single second (2017-03-01 14:01:07 UTC).

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Al Cutter <[email-masked]>
Date: Mon, 13 Mar 2017 13:53:06 +0000

On Mon, Mar 13, 2017 at 12:47 PM, Linus Nordberg <[email-masked]> wrote:

> Al Cutter <[email-masked]> wrote
> Fri, 3 Mar 2017 10:19:19 +0000:
>
> 6962bis doesn't say one hour. It says a log must stipulate its maximum
> number of STHs per MMD in its metadata.
>

Yep, my mistake, sorry for the noise.

> Since it's a requirement on logs, it should be in a document
> standardising logs.
>

Standardising the knob makes sense, I just didn't like the idea of
standardising the values I can dial in here (and I now know they aren't,
thanks!)

---

From: Linus Nordberg <[email-masked]>
Date: Mon, 13 Mar 2017 13:47:44 +0100