From 3379f3c6b7cf958146d0da255ebf377270b75b00 Mon Sep 17 00:00:00 2001
From: Linus Nordberg <linus@nordberg.se>
Date: Thu, 5 Jun 2014 15:47:08 +0200
Subject: Add explanatory header.

---
 src/ht.erl | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

(limited to 'src/ht.erl')

diff --git a/src/ht.erl b/src/ht.erl
index 9e99d16..0ef95fe 100644
--- a/src/ht.erl
+++ b/src/ht.erl
@@ -1,3 +1,25 @@
+%%%
+%%% 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").
 
-- 
cgit v1.1