1. Merkle - Protocols for public key cryptosystems
==================================================

Protocol to build a proof that you possess some content (e.g a public key) that
is part of a larger set of data known by everyone (the set of all public keys)

* put each piece of data at the leaves of a binary tree
* each internal node of the tree computes the hash of its left child concatenated
with its right child
* everybody computes the hash tree and stores the root hash plus the hashes going from
the root to his own leaf
* The list of hashes from the root to f yields a proof that f is part of the big set
of files. Indeed, one can test that repeatedly hashing f yields the
same hashes.

Space : log(N) where N is the number of files
Problem : everyone must compute the hash tree and thus must know every file

2. Benaloh, de Mare - Efficient Broadcast Time-Stamping
=======================================================

Almost the same as 1., but here applied to time-stamping. New concept : proceed 
in rounds

* the root hash of the previous round is added to each leaf file before hashing it.

=> the proof now depends on the round => it's possible to proove that the file was present at
a given round

Space : log(N)
Problem : you need to know the root time-stamp of the previous round to time-stamp
a document. Not a big issue

3. Benaloh, de Mare - One-way accumulators: a decentralized alternative to digital signatures
=============================================================================================

Improvement of 2. Use of quasi-commutative hash functions :
h(h(x,y1),y2) = h(h(x,y2)y1)
Thus, starting from a common value x, the order with which the hashing is done
doesn't matter.

* everyone agrees on a starting value x (for example the root hash of previous round)
* everyone computes the total hash :
z = h(h(h(.....h(x,y1),y2),y3).....)
and the hash of everybody except his own y_i : z_i
* then (z_i,y_i) yields a proof that y_i is part of the big set of files. Indeed :
z = h(z_i, y_i)

Space : constant !!
Problem : you still need to know the whole set of files

Maybe this can be used to store a branch in pacemaker...

4. Maniatis, Baker - Secure history preservation through timeline entanglement
==============================================================================

* Idea of tamper-evident log/history.
* If h_(k-1) is your history up to date k-1. If event e_k occurs at time 
k then :
h_k = H(h_(k-1),H(e_k)) is your new history
* Same idea as in 2. : h_k, e_k is a proof

5. Haeberlen - PeerReview: Practical Accountability for Distributed Systems
===========================================================================

Use the idea of 4 to build a review protocol.

* each node keeps his own log
* at any time a node can commit to event e_k by broadcasting (h_k,e_k) to its witnesses
* it's possible to challenge a node on event e_k : the node should answer h_(k-1) such that
h_k = H(h_(k-1),H(e_k))

This relies heavily on peer reviews as in AVMON