From bf0a6e5458c16cb9bf72db002d840c5e1fbb3f29 Mon Sep 17 00:00:00 2001 From: Linus Nordberg Date: Mon, 20 Oct 2014 12:52:32 +0200 Subject: =?UTF-8?q?Credit=20Emilia=20K=C3=A4sper=20for=20the=20placeholder?= =?UTF-8?q?=20idea.?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- src/ht.erl | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) diff --git a/src/ht.erl b/src/ht.erl index cd4e57c..7051b9e 100644 --- a/src/ht.erl +++ b/src/ht.erl @@ -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). -- cgit v1.1