[messaging] Two possible approaches to key transparency: CONIKS vs. VerSum

[Joseph Bonneau]

There is a quite beautiful contribution in the VerSum paper:
https://pdos.csail.mit.edu/papers/versum:ccs14.pdf

The VerSum protocol allows clients to ask N servers for the result of some
computation over a big public log. A motivating example is the current
balance of a specific bitcoin address, or equivalently the current value
mapped to a name in NameCoin. These are hard to compute without computing
over the entire history, so it's presumed the N servers are tracking
history and maintaining separate data structures to handle these queries
efficiently.

Now, If the servers respond differently, there is an efficient algorithm to
figure out which server is telling the truth by binary search over each
step of the computation which is committed to in its own data structure. As
long as at least one server is honest you'll figure out which one.

With CONIKS (http://www.jbonneau.com/doc/MBBFF15-coniks.pdf) one major goal
was to eliminate costly lookups as in NameCoin with a data structure
designed to make it efficient to prove what the current value is bound to a
name, so no external servers are required (both systems assume that clients
know the current root hash of the entire history-ensuring this is a
different problem). This has real costs in CONIKS: clients either need to
check every version of the data structure, either limiting the update
frequency or requiring more bandwidth. You can ameliorate this in CONIKS
somewhat if you assume version counts or other data is tagged with each
name-but that re-introduces trust in external parties to check that the
data structure is maintained correctly.

Replacing the CONIKS design with a simpler data structure + VerSum is an
interesting design point. This could just be a CT-style append-only log of
key changes, with the most recent being considered correct. Clients would
query several independent servers asking "give me the current value bound
to name X" or "give me the list of all values ever bound to name X" (to
audit their own entry). Using VerSum, you are sure you get the right answer
if at least one server you query is honest.

This has some advantages: the core key service is simpler and therefore
less likely to be be buggy, it can be updated at irregular intervals,
bandwidth can be quite low (as clients don't need proofs in the common case
where all N servers agree).

By contrast, CONIKS is more complicated and probably uses more bandwidth
but offers: no requirement for external services to exist, self-contained
proofs that bindings are correct, better privacy (no queries to external
servers, possible to re-randomize the data structure).

It might be possible to build a hybrid, maintaining a full CONIKS log but
allowing some clients to rely on VerSum-style querying to check it rather
than checking themselves. But then this loses the simplicity advantages of
relying on VerSum.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20160115/2d616332/attachment.html>