<div dir="ltr">There is a quite beautiful contribution in the VerSum paper: <a href="https://pdos.csail.mit.edu/papers/versum:ccs14.pdf">https://pdos.csail.mit.edu/papers/versum:ccs14.pdf</a><br><div><br></div><div>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.</div><div><br></div><div>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.<br></div><div><br></div><div>With CONIKS (<a href="http://www.jbonneau.com/doc/MBBFF15-coniks.pdf">http://www.jbonneau.com/doc/MBBFF15-coniks.pdf</a>) 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.</div><div><br></div><div>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.</div><div><br></div><div>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).</div><div><br></div><div>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).<br></div><div><br></div><div>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.</div></div>