[Trans] Design of gossip

[Watson Ladd <[e-mail]>]

Dear all,

As has been noted a lot depends on the gossip protocol, and there
isn't a lot said about it right now. I'd like to kick that off by
outlining some of the fundamental choices that need to be made, and
what I think (possibly wrongly) their implications are.

The first choice is what to gossip: tree heads and proofs or certs.
Both have privacy implications: while certs more directly reveal which
sites are visited, it's possible that tree heads will be unique per
cert due to the impact of adding to a tree one cert at a time, so each
precert will end up showing a different head. This is a tricky issue.

The second choice is what gossip produces. In particular do we push
consistency proofs towards clients, or pull the heads towards
monitors? Either approach can work, but the first approach could save
bandwidth: a consistent head does not need to be reported. The first
also enables remembering what has been recorded. The second approach
is simpler for gossipers.

The third choice is how to gossip. Probably the best approach is some
sort of peer-to-peer network, with the possibility of using other
servers if the P2P approach doesn't work. However, gossip needs to be
censorship resistant, which can be a bit tricky. We also want gossip
to deal with a small fraction of malicious nodes, which means some
approaches are tricky: in particular nodes can't stop if some nodes
say "we've heard it before".

We also need to make sure we don't lose submitted heads, even as old
heads grow in number. Using consistency proofs to reduce the number of
heads helps with this problem.

DHTs may be a workable approach, but I don't know of Byzantine proof
ones. Flood-fill on random graphs scales if you make it publish only,
but dealing with old data gets tricky: we want new nodes to learn it,
without having to send it unnecessarily. Showing the result of an
audit and backfilling can work, but we need to think about the details
and try some experiments.

Sincerely,
Watson Ladd