diff options
author | Linus Nordberg <linus@nordberg.se> | 2014-10-20 12:52:32 +0200 |
---|---|---|
committer | Linus Nordberg <linus@nordberg.se> | 2014-10-20 12:52:32 +0200 |
commit | bf0a6e5458c16cb9bf72db002d840c5e1fbb3f29 (patch) | |
tree | ebb413b35d385aeb5eeaa74456a092c4dc6099b7 | |
parent | 77e68d48e60599da5db3e310f98c7fbc41d63b88 (diff) |
Credit Emilia Käsper for the placeholder idea.
-rw-r--r-- | src/ht.erl | 14 |
1 files changed, 10 insertions, 4 deletions
@@ -6,18 +6,24 @@ %%% follows RFC 6962 and differs from [0] only in how non-full trees %%% are handled. %%% -%%% [0] https://www.usenix.org/event/sec09/tech/full_papers/crosby.pdf +%%% The idea with placeholder nodes on incomplete layers is borrowed +%%% from Emilia Käspers implementation in Google's +%%% certificate-transparency project. %%% -%%% Hashes of inner nodes and leaves are stored in arrays, one per -%%% layer with layer 0 being where the leaves are. The total number of -%%% arrays is equal to the depth of the tree. The depth of the tree is +%%% Hashes of inner nodes and leaves are stored in whatever +%%% datastructure the ts module uses, one per layer. Layer 0 is where +%%% the leaves are. The total number of datastructures used in ts is +%%% equal to the depth of the tree. The depth of the tree is %%% ceil(lg2(number of leaves)). +%%% %%% Let {r,i} denote the hash with index i on layer r. The first leaf %%% is {0,0}, second is {0,1} and n:th is {0,n-1}. %%% The parent of {r,i} is {r+1,floor(i/2)} (not strictly true because %%% of "placeholder nodes", see update_parent/4). %%% The sibling of {r,i} is {r,i+1} when i is even and {r,i-1} when i %%% is odd. +%%% +%%% [0] https://www.usenix.org/event/sec09/tech/full_papers/crosby.pdf -module(ht). -behaviour(gen_server). |