diff options
author | Linus Nordberg <linus@nordu.net> | 2014-06-15 13:35:43 +0200 |
---|---|---|
committer | Linus Nordberg <linus@nordu.net> | 2014-06-15 13:35:43 +0200 |
commit | 558a56adfe02a0803bbbbf4ddaef0271e586930b (patch) | |
tree | d339c2eb08652f16bbc1e2e15b988187a2774281 /src/ht.erl | |
parent | 5b57e05b6fcf9739f50ffe552053b2a254a08b3f (diff) | |
parent | b756d6af862e97c1279d6006ed7684e28564aa97 (diff) |
Merge branch 'master' of /home/linus/repo/plop
# Please enter a commit message to explain why this merge is necessary,
# especially if it merges an updated upstream into a topic branch.
#
# Lines starting with '#' will be ignored, and an empty message aborts
# the commit.
Diffstat (limited to 'src/ht.erl')
-rw-r--r-- | src/ht.erl | 24 |
1 files changed, 24 insertions, 0 deletions
@@ -1,3 +1,27 @@ +%%% Copyright (c) 2014, NORDUnet A/S. +%%% See LICENSE for licensing information. +%%% +%%% Implementation of a history tree similar to what is described in +%%% Efficient Data Structures for Tamper-Evident Logging [0]. This +%%% implementation follows RFC 6962 and differs from [0] only in how +%%% non-full trees are handled. +%%% +%%% Useful terminology: +%%% C -- Commitment. +%%% X -- Event, stored in leaf nodes. +%%% I(i,r) -- Interior node with index i, on layer r. +%%% A(v)(i,r) -- Hash of I(i,r) in tree of version v. +%%% d -- Depth of tree. +%%% +%%% Nodes are identified by their index i and layer r. +%%% I(i,r) has left child I(i,r-1) and right child I(i+2^(r-1),r-1). +%%% +%%% A version-n tree stores n+1 events. +%%% In a version-n tree, I(i,r) is frozen when n >= i + 2^r - 1. +%%% +%%% [0] https://www.usenix.org/event/sec09/tech/full_papers/crosby.pdf +%%% + -module('ht'). -include_lib("eunit/include/eunit.hrl"). |