diff options
| -rw-r--r-- | related papers/Li - Implemeting aggregation and broadcast over distributed hash tables.pdf | bin | 0 -> 391511 bytes | |||
| -rw-r--r-- | related papers/reading notes.txt | 77 |
2 files changed, 77 insertions, 0 deletions
diff --git a/related papers/Li - Implemeting aggregation and broadcast over distributed hash tables.pdf b/related papers/Li - Implemeting aggregation and broadcast over distributed hash tables.pdf Binary files differnew file mode 100644 index 0000000..d8795f3 --- /dev/null +++ b/related papers/Li - Implemeting aggregation and broadcast over distributed hash tables.pdf diff --git a/related papers/reading notes.txt b/related papers/reading notes.txt new file mode 100644 index 0000000..560eba4 --- /dev/null +++ b/related papers/reading notes.txt @@ -0,0 +1,77 @@ +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 + + + + |