[CFRG] Threshold Sig required - Random bit flip hits Cert Transparency Log

[Phillip Hallam-Baker <[e-mail]>]

So it has actually happened, a one in a billion computing error has caused
a cert transparency log to become corrupted due to a bit flip error. There
is a discussion of the issue here:

Single random bit flip causes error in certificate transparency log |
Hacker News (ycombinator.com)
<https://news.ycombinator.com/item?id=27728287>

The solution they obsess over (ECC RAM) is actually irrelevant to the error
in that case as it was an even rarer CPU error. Which means that what I
considered to be a more or less theoretical concern about signing append
only logs turns out to have actually occurred. Do things billions of times
and billion to one chances will happen.


The only robust solution to this issue is for redundant notaries to sign
the log.

Consider the case where we have an append only log that is authenticated by
means of a Merkle tree with the apex of the tree being signed at 10 minute
intervals. If we have a single server doing the signing, any error that
occurs will lead to the log becoming invalid. This condition cannot be
distinguished from a notary default.

But consider the case where there are three notaries each signing the log,
which private key should they use?

All three signers use the same key means that if an error occurs, we risk
having a correct and incorrect version of the same log being signed. That
means there is a real risk of the incorrect log and signature leaking
somehow.

All three signers using different keys is also bad because now we have
three independent notaries and the relying party has to do the job of
deciding which one to trust. There is an even greater risk of the wrong log
being relied on at some point.

A threshold scheme with three shares and a quorum of 2 solves the problem
very neatly. The possibility of an undetected error is now much smaller as
two signers must be hit with an error having exactly the same effect at the
same time. That is a very remote possibility unless the error is somehow
caused by an architectural defect in the CPU. So we should probably choose
separate chipset architectures (Intel, AMD, ARM?) if we want to get to
maximum robustness.


So how is the FROST draft coming?