New hash tree implementation, using an ETS table for the hashes.

Also, add an untested entry storage implementation, using multiple
DETS tables.

1 files changed, 189 insertions, 371 deletions

diff --git a/src/ht.erl b/src/ht.erl
index b24d04d..bcd9421 100644
--- a/src/ht.erl
+++ b/src/ht.erl
@@ -1,233 +1,204 @@
 %%% 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.
+%%% Implementation of a history tree as 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.
+%%%
+%%% [0] https://www.usenix.org/event/sec09/tech/full_papers/crosby.pdf
 %%%
 %%% Useful terminology:
-%%% C -- Commitment.
-%%% X -- Event, stored in leaf nodes.
-%%% I(i,r) -- Interior node with index i, on layer r.
+%%% E -- Entry, stored in leaf nodes.
+%%% I(i,r) -- Inner 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.
+%%% A version-n tree stores n+1 entries.
 %%% 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
+%%% Data types:
+%%% history_tree
+%%%   version (integer)
+%%%   head (reference to a frozen or warm node)
+%%%   frozen nodes (ets tables handled by ts)
+%%%   warm nodes (ets table handled by ts)
 %%%
-
--module('ht').
+%%% Interface:
+%%% create tree (-> tree)
+%%% add entry (data -> tree)
+%%% get hash of leaf or inner node (i, r -> hash)
+%%% get inclusion proof for leaf i in version-n tree (i, n -> hashes)
+%%% get consistency proof between trees of version n and m (n, m -> hashes)
+%%%
+-module(ht).
+-include("$CTROOT/plop/include/plop.hrl").
 -include_lib("eunit/include/eunit.hrl").
+-import(lists, [foreach/2, foldl/3, reverse/1]).
 
--record(leaf, {hash :: binary()}).              % hash of data
--record(inner, {child0 :: #leaf{} | #inner{},   % left child
-                child1 :: #leaf{} | #inner{},   % right child
-                hash :: binary()}).        % hash of children's hashes
--record(head, {version :: non_neg_integer(),    % number of leaves
-               tree :: tree()}).                % the tree
-
--type head() :: #head{}.
--type tree() :: inner() | leaf() | undefined.
--type leaf() :: #leaf{}.
--type inner() :: #inner{}.
-
--export_type([head/0, tree/0, inner/0, leaf/0]).
--export([create/0, append/2, tree_hash/1, size/1, audit_path/2,
-         consistency_proof/2]).
+-export_type([history_tree/0, inner/0]).
+-export([new/0, new/1, destroy/1, size/1, add/2]).
+-export([get_hash/3, get_incl/3, get_cons/3]).
+-export([tree_hash/1, tree_hash/2]).
 
 %%%%%%%%%%%%%%%%%%%%
 %% Public interface.
 
-%% @doc Return an empty tree.
--spec create() -> head().
-create() ->
-    mkhead(0, undefined).
-
-%% @doc Return the merkle tree hash of a tree.
--spec tree_hash(head()) -> binary();
-               (tree()) -> binary().
-tree_hash(#head{tree=T}) ->
-    case T of
-        undefined -> hashfun(<<>>);
-        #inner{hash=H} -> H;
-        #leaf{hash=H} -> H
-    end.
-
-%% @doc Return the size of a tree, i.e. its number of leaves.
--spec size(head()) -> non_neg_integer().
-size(Head) ->
-    tree_version(Head).
-
-%% @doc Append a leaf to a tree.
-%%
-%% Walk down the tree in Head, stop at The Right Place and make Leaf
-%% the right sibling of that place. To find the right place, let d be
-%% the depth of the tree, then go down the tree on the right hand side
-%% to level l, where l is the position of the first set bit in d,
-%% looking at d from the least significant bit. l=0 is where the leaves
-%% are and l=d-1 is the root.
-%%
-%% The depth of the tree is found by walking down the right path. It
-%% would be better if we inserted the leaf and calculated the nodes on
-%% the way up instead of walking down the tree again. Worst case this
-%% is lg2(N) iterations, i.e. 24 steps for N=16e10.
-%%
-%% Example: N=3 (011) => l=0, the rightmost leaf.
-%% Example: N=4 (100) => l=2, the root (soon not to be root).
-%% Example: N=5 (101) => l=0, the rightmost leaf.
-%% Example: N=6 (110) => l=1, the last and rightmost inner node.
-%%
-%% NOTE: Adding a tree requires some more work. One thing is that if
-%% the tree to append doesn't fit in right-hand subtree, it has to be
-%% added in smaller pieces.
-%%
--spec append(head(), leaf() | iolist() | binary()) -> head().
-append(#head{version = 0}, Leaf) when is_record(Leaf, leaf) ->
-    mkhead(1, Leaf);
-append(#head{version = N, tree = Tree}, Leaf) when is_record(Leaf, leaf) ->
-    Level = fls(N),
-    RBD = rightbranchdepth(Tree),
-    %io:format("N=~p, Level=~p, RBD=~p~n", [N, Level, RBD]),
-    #head{version = N + 1, tree = append_at(Tree, Leaf, RBD-Level-1)};
-append(Head, Data) ->
-    append(Head, mkleaf(Data)).
-
--spec append_at(tree(), tree(), pos_integer()) -> tree().
-append_at(Dest, Newtree, _) when is_record(Dest, leaf) ->
-    mkinner(Dest, Newtree);
-append_at(Dest, Newtree, 0) when is_record(Dest, inner) ->
-    mkinner(Dest, Newtree);
-append_at(Dest, Newtree, Depth) when is_record(Dest, inner) ->
-    mkinner(Dest#inner.child0, append_at(Dest#inner.child1, Newtree, Depth - 1)).
-
-%% @doc Return an audit path.
-%%
-%% An audit path is a list of those hashes needed to calculate the
-%% tree hash for Head given the knowledge of the nth hash in the
-%% tree. An audit path proves existance of a given leaf in a given
-%% tree.
-%%
-%% Walk down the tree to N and build the list in Acc by adding each
-%% sibling.
--spec audit_path(head(), non_neg_integer()) -> list().
-audit_path(#head{version = Version, tree = Tree}, N) ->
-    L = [Bit || <<Bit:1>> <= ui2b(N)],
-    {_, Path} = lists:split(length(L) - ffs(Version) -1, L),
-    audit_path(Tree, Path, []).
-audit_path(Tree, _, Acc) when is_record(Tree, leaf) ->
-    Acc;
-audit_path(_, [], Acc) ->
-    Acc;
-audit_path(#inner{child0 = Left, child1 = Right}, [PathH|PathT], Acc) ->
-    case PathH of
-        0 ->                                    % Take a left.
-            audit_path(Left, PathT, [gethash(Right) | Acc]);
-        _ ->                                    % Take a right.
-            audit_path(Right, PathT, [gethash(Left) | Acc])
-    end.
-
-%% @doc Return a consistency proof.
-%%
-%% A consistency proof is the shortest list of nodes required to
-%% verify that the tree built from the first n leaves of a given tree
-%% is a subset of that tree. Consistency proofs prove the append-only
-%% property of a tree.
--spec consistency_proof(head(), non_neg_integer()) -> list().
-consistency_proof(Head, N) ->
-    [fixme, Head, N].
-
 %%%%%%%%%%%%%%%%%%%%
-%% Private functions.
+%% Data types.
+-record(history_tree, {version :: integer(),
+                       store :: ts:tree_store()}).
+-type history_tree() :: #history_tree{}.
+
+-record(inner, {index :: non_neg_integer(), % 27bit integer => max 134e6 entries
+                layer :: non_neg_integer(), % 5bit integer
+                hash :: binary()}).
+-type inner() :: #inner{}.
 
-%% @doc Return version number of a tree.
+%%%%%%%%%%%%%%%%%%%%
+%% Public interface.
+size(#history_tree{version = V}) ->
+    V + 1.
+
+-spec new() -> history_tree().
+new() ->
+    #history_tree{version = -1, store = ts:new()}.
+
+-spec new(integer()) -> history_tree().
+new(Version) ->
+    foldl(fun(#mtl{entry = E}, Tree) ->
+                  D = (E#timestamped_entry.entry)#plop_entry.data,
+                  add(Tree, D) % Return value -> Tree in next invocation.
+          end, new(), db:get_by_index_sorted(0, Version)).
+
+destroy(Tree) ->
+    ts:delete(Tree#history_tree.store).
+
+%% @doc Which layers need to change when creating a version-n tree?
+%% Layer 0 is where the new leaf is added and always needs
+%% updating. Apart from 0, the layers with a number corresponding to
+%% the "positions of the bits set in n" are the ones that need to be
+%% touched. This assumes a somewhat unorthodox bit numbering where the
+%% least significant bit has number 1 (rather than 0).
 %%
-%% The version number is the number of leaves in tree. Note that this
-%% is set off by one (higher) compared to the history tree version as
-%% explained by Crosby and Wallach.
--spec tree_version(head()) -> non_neg_integer().
-tree_version(#head{version=Ver}) ->
-    Ver.
-
--spec mkhead(non_neg_integer(), tree()) -> head();
-            (head(), list()) -> head().
-mkhead(Version, Tree) when is_integer(Version) ->
-    #head{version=Version, tree=Tree};
-mkhead(Head, []) ->
-    Head;
-mkhead(Head, [H|T]) ->
-    append(mkhead(Head, T), mkleaf(H)).
-
--spec hashfun(iolist() | binary()) -> binary().
-hashfun(Data) ->
-    crypto:hash(sha256, Data).
-
--spec mkleaf(iolist() | binary()) -> leaf().
-mkleaf(Data) ->
-    #leaf{hash = hashfun([<<"\x00">>, Data])}.
-
--spec mkinner(tree(), tree()) -> inner().
-mkinner(Leaf, Tree) ->
-    #inner{child0 = Leaf,
-           child1 = Tree,
-           hash = mkhash(Leaf, Tree)}.
-
--spec mkhash(tree(), tree()) -> binary().
-mkhash(Tree0, Tree1) ->
-    hashfun([<<"\x01">>, hash(Tree0), hash(Tree1)]).
-
--spec hash(tree()) -> binary().
-hash(#leaf{hash=Hash}) ->
-    Hash;
-hash(#inner{child0=Child0, child1=Child1}) ->
-    mkhash(Child0, Child1).
-
-gethash(#leaf{hash = Hash}) -> Hash;
-gethash(#inner{hash = Hash}) -> Hash.
-
-%% @doc Unsigned integer -> binary.
--spec ui2b(pos_integer()) -> binary().
-ui2b(Unsigned) ->
-    binary:encode_unsigned(Unsigned).
-
-%% @doc Find first set bit in V, starting counting at zero from the
-%% least significant bit.
-ffs(V) when is_integer(V) ->
-    L = [Bit || <<Bit:1>> <= ui2b(V)],
-    length(L) - ffs(L, 0) - 1.
+%% For example:
+%% A version 2 (0010) tree has had changes to layer 2
+%% A version 5 (0101) tree has had changes to layers 1 and 3
+%% A version 8 (1000) tree has had changes to layer 4
+-spec add(history_tree(), binary()) -> history_tree().
+add(#history_tree{version = V, store = Store}, Entry) ->
+    NewVersion = V + 1,
+    LeafIndex = NewVersion,
+    LeafHash = mkleafhash(Entry),
+    LayerMap = reverse([B || <<B:1>> <= binary:encode_unsigned(NewVersion)]),
+    #history_tree{version = NewVersion,
+                      store = update(ts:store(Store, {LeafIndex, 0}, LeafHash),
+                                     1, LayerMap,
+                                     #inner{index = LeafIndex, layer = 0,
+                                            hash = LeafHash})}.
+
+tree_hash(Tree) ->
+    tree_hash(Tree, Tree#history_tree.version).
+tree_hash(Tree, Version) ->
+    get_hash(Tree, Version, {0, depth(Tree) - 1}).
+
+-spec get_hash(history_tree(), non_neg_integer(), tuple()) -> binary().
+get_hash(#history_tree{store = S}, _Version, IR) ->
+    %% TODO: Use Version!
+    {{_I, _R}, Hash} = ts:retrieve(S, IR),
+    Hash.
+
+%-spec get_incl/3
+get_incl(_, _, _) ->
+    nyi.
+%-spec get_cons/3
+get_cons(_, _, _) ->
+    nyi.
+
+%% Private.
+%% -spec head(history_tree()) -> inner().
+%% head(#history_tree{store = Store}) ->
+%%     {{I, R}, Hash} = ts:retrieve(Store, {0, 0}),
+%%     #inner{index = I, layer = R, hash = Hash}.
+
+%% @doc Return position of highest bit set, counting from the least
+%% significant bit, starting at 1.
+bitpos_first_set(N) ->
+    L = [Bit || <<Bit:1>> <= binary:encode_unsigned(N)],
+    length(L) - ffs(L, 0).
 ffs([], Acc) ->
     Acc;
 ffs([H|T], Acc) ->
     case H of
-        0 -> ffs(T, Acc+1);
+        0 -> ffs(T, Acc + 1);
         _ -> Acc
     end.
-fls(V) when is_integer(V) ->
-    L = lists:reverse([Bit || <<Bit:1>> <= ui2b(V)]),
-    ffs(L, 0).
 
-rightbranchdepth(Tree) ->
-    1 + rightbranchdepth(Tree, 0).
--spec rightbranchdepth(tree(), non_neg_integer()) -> non_neg_integer().
-rightbranchdepth(Tree, Acc) when is_record(Tree, leaf) ->
-    Acc;
-rightbranchdepth(Tree, Acc) ->
-    rightbranchdepth(Tree#inner.child1, Acc + 1).
+depth(#history_tree{version = -1}) ->
+    0;
+depth(#history_tree{version = V}) ->
+    bitpos_first_set(V) + 1.
+
+-spec update(ts:tree_store(), pos_integer(), list(), inner()) -> ts:tree_store().
+update(Store, _, [], _) ->
+    Store;
+update(Store,
+       CurrentLayer, [UpdateThisLayerP|LayerMap],
+       Child = #inner{index = ChildIndex,
+                      layer = ChildLayer,
+                      hash = ChildHash}) ->
+    case UpdateThisLayerP ==  1 of
+        true ->
+            %% Create/update the parent of ChildHash at ChildIndex.
+            %%
+            %% Parent index is equal to child index with its r lowest
+            %% bits stripped off, where r is current layer.
+            %%
+            %% Other child is found by comparing index of parent and
+            %% known child. If they're the same, the known child is
+            %% the left child and its sibling is found on the same
+            %% layer. If they differ, the known child is the right
+            %% child and the left child is to be found one layer below
+            %% the parent, same index.
+
+            Index = strip_low_bits(ChildIndex, CurrentLayer),
+            Hash =
+                case Index == ChildIndex of
+                    true ->
+                        {_SibIR, SibHash} =
+                            ts:retrieve(Store, {Index + (1 bsl ChildLayer) - 1,
+                                                ChildLayer}),
+                        mkinnerhash(ChildHash, SibHash);
+                    _ ->
+                        {_SibIR, SibHash} =
+                            ts:retrieve(Store, {Index, CurrentLayer - 1}),
+                        mkinnerhash(SibHash, ChildHash)
+                end,
+            update(ts:store(Store, {Index, CurrentLayer}, Hash),
+                   CurrentLayer + 1, LayerMap,
+                   #inner{index = Index, layer = CurrentLayer, hash = Hash});
+        _ ->
+            update(Store, CurrentLayer + 1, LayerMap, Child)
+    end.
+
+strip_low_bits(N, Nbits) ->
+    (N bsr Nbits) bsl Nbits.
+
+hash(Data) ->
+    crypto:hash(sha256, Data).
+
+mkleafhash(Data) ->
+    hash([<<"\x00">>, Data]).
+
+mkinnerhash(Hash1, Hash2) ->
+    hash([<<"\x01">>, Hash1, Hash2]).
 
 %%%%%%%%%%%%%%%%%%%%
-%% Internal tests.
--define(TEST_VECTOR_TREES,
-        [[<<"a foo is a bar">>,
-          <<148,242,40,0,3,172,180,106,111,230,146,161,32,40,128,38,103,8,194,
-           102,72,68, 126,70,108,47,8,216,208,146,178,107>>]]).
-%% Test vectors from certificate-transparency/src/python/ct/crypto/merkle_test.py.
--define(EMPTY_HASH,
-        "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855").
+%% Testing ht.
 -define(TEST_VECTOR_LEAVES,
         ["", "\x00", "\x10", " !", "01", "@ABC", "PQRSTUVW", "`abcdefghijklmno"]).
 -define(TEST_VECTOR_HASHES,
@@ -239,43 +210,18 @@ rightbranchdepth(Tree, Acc) ->
          "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef",
          "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c",
          "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"]).
-%% Own test vectors.
--define(TEST_VECTOR_LEAVES2, ["d0", "d1", "d2", "d3", "d4", "d5", "d6"]).
--define(TEST_VECTOR_HASHES2,
-        [
-         {a, "C67F9FFE68E0761021341DD516428F42FBDEA633731CBDADA03BEA6B84C652F7"},
-         {b, "49B717E4D6ECDD82F6F6648CF8F86FDF4A912600A4557398E1733186FA952C1D"},
-         {c, "F366DF4718EF75064317794FF5300E0963E96DD93FE24203118055FA5A00BE13"},
-         {d, "5E0C4E1130DFA84D27437BA073EB817E1896643D42EA100A0940F8752D496783"},
-         {e, "39298BE94337336FC5515E7A34DE6EF23C9A1BFF66378B71918AE2D105D684C8"},
-         {f, "6D1BB6BBB111AF4A1E9EC0B9FB2613CC2BCB394141CEE8C2CD462B5AD3803D78"},
-         {g, "46C78708413A23175F51FAF1C22604BCCB44482D553B45943B189130EA8221C8"},
-         {h, "C59E9A6D9575777BA3BDBD3E3086516196CF87EC9760861362ABA5CD0F78DF1D"},
-         {i, "A4F2A847CCE0DCE0519B1D6B83E4CA15166193DBB0C8F864E736665EDBDE1994"},
-         {j, "D750CA922FABC5422EEC469D4370779B61D5488186CB871EEEA299D8113D20BC"},
-         {k, "8DF3870B33FAE650E81938994F98EB4551B143B86C95D3DAE4E6444E00715016"},
-         {l, "3CF05FF16D26C024828E93B3A14C5656E5ABCBC5E6F0BCE2CF8A169720599674"}
-        ]).
-smap_get(Key, SimpleMap) ->
-    case lists:keyfind(Key, 1, SimpleMap) of
-        {_, Val} -> Val;
-        Notfound -> Notfound
-    end.
 
-basic_helpers_test_() ->
-    [test_bitcount()].
-
-basic_tree_test_() ->
-    TVT1 = lists:nth(1, ?TEST_VECTOR_TREES),
-    [?_assertEqual(#head{version = 0, tree = undefined},
-                   create()),
-     ?_assertEqual(#head{version = 1,
-                         tree = #leaf{hash = lists:last(TVT1)}},
-                   create(hd(TVT1)))].
-
-empty_hash_test_() ->
-    [?_assertEqual(hex:hexstr_to_bin(?EMPTY_HASH), mth([]))].
+%% @doc Build trees using add/2 and mth/2 and compare the resulting
+%% tree hashes.
+add_test() ->
+    lists:foreach(
+      fun(X) -> L = lists:sublist(?TEST_VECTOR_LEAVES, X),
+                ?assertEqual(mth(L), tree_hash(mktree(L)))
+      end,
+      lists:seq(1, length(?TEST_VECTOR_LEAVES))).
 
+%%%%%%%%%%%%%%%%%%%%
+%% Testing the test helpers.
 mth_test() ->
     lists:foreach(
       fun(X) -> ?assertEqual(
@@ -284,153 +230,25 @@ mth_test() ->
       end,
       lists:seq(1, length(?TEST_VECTOR_LEAVES))).
 
-new_tree_test_() ->
-    TVT1 = lists:nth(1, ?TEST_VECTOR_TREES),
-    V0 = create(),
-    V1 = append(V0, hd(TVT1)),
-    [?_assertEqual(0, V0#head.version),
-     ?_assertEqual(undefined, V0#head.tree),
-     ?_assertEqual(lists:last(TVT1), (V1#head.tree)#leaf.hash),
-     ?_assertEqual(1, V1#head.version)].
-
-%% @doc Build trees using append/2 and mth/2 and compare the resulting
-%% tree hashes.
-append_test() ->
-    lists:foreach(
-      fun(X) -> L = lists:sublist(?TEST_VECTOR_LEAVES, X),
-                ?assertEqual(
-		   mth(L),
-		   gethash((mkhead(L))#head.tree))
-      end,
-      lists:seq(1, length(?TEST_VECTOR_LEAVES))).
-
-mkhead_from_list_test() ->
-    L = ["a", "b"],
-    ?assertEqual(append(mkhead(1, mkleaf(lists:nth(1, L))),
-                      mkleaf(lists:nth(2, L))),
-                 mkhead(L)).
-
-append_eq_mth_test() ->
-    Count = 300,
-    L = [<<X:16>> || X <- lists:seq(0, Count)],
-    ?assertEqual(gethash((mkhead(L))#head.tree), mth(L)).
-
-path_test_() ->
-    Leaves = ?TEST_VECTOR_LEAVES2,
-    H = ?TEST_VECTOR_HASHES2,
-    %%Tree = lists:foldl(fun(E, T) -> ht:append(T, E) end, ht:create(), Leaves),
-    [?_assertEqual([smap_get(b, H), smap_get(h, H), smap_get(l, H)],
-                   lists:map(fun hex:bin_to_hexstr/1, path(0, Leaves))),
-     ?_assertEqual([smap_get(c, H), smap_get(g, H), smap_get(l, H)],
-                   lists:map(fun hex:bin_to_hexstr/1, path(3, Leaves))),
-     ?_assertEqual([smap_get(f, H), smap_get(j, H), smap_get(k, H)],
-                   lists:map(fun hex:bin_to_hexstr/1, path(4, Leaves))),
-     ?_assertEqual([smap_get(i, H), smap_get(k, H)],
-                   lists:map(fun hex:bin_to_hexstr/1, path(6, Leaves)))].
-
-audit_path_test_() ->
-    Tree = lists:foldl(fun(E, T) -> ht:append(T, E) end, ht:create(),
-                       ?TEST_VECTOR_LEAVES2),
-    H = ?TEST_VECTOR_HASHES2,
-    [?_assertEqual([smap_get(b, H), smap_get(h, H), smap_get(l, H)],
-                   lists:map(fun hex:bin_to_hexstr/1, audit_path(Tree, 0))),
-     ?_assertEqual([smap_get(c, H), smap_get(g, H), smap_get(l, H)],
-                   lists:map(fun hex:bin_to_hexstr/1, audit_path(Tree, 3))),
-     ?_assertEqual([smap_get(f, H), smap_get(j, H), smap_get(k, H)],
-                   lists:map(fun hex:bin_to_hexstr/1, audit_path(Tree, 4))),
-     ?_assertEqual([smap_get(i, H), smap_get(k, H)],
-                   lists:map(fun hex:bin_to_hexstr/1, audit_path(Tree, 6)))].
-
-consistency_proof_test_() ->
-    H = mkhead([]),
-    M = 0,
-    [?_assertEqual([niy, H, M], proof(H, M))].
-
 %%%%%%%%%%%%%%%%%%%%
 %% Test helpers.
 
-%% @doc Calculate a Merkle Tree Hash from an ordered list as specified
-%% in RFC 6962.
-%%
-%% K, the split point, is the number of leaves comprising the largest
-%% possible full tree. 
-%%
-%% The way we calculate K is to let N be the number of entries, find
-%% the most significant bit in N-1 and raise two to that number. This
-%% is K.
-test_bitcount() ->
-    L = [1, 2, 3, 255, 256, 511, 512, 32767, 32768, 65535, 65536,
-         2147483648, 4294967296, 8589934591, 8589934592, 18446744073709551616],
-    [[?_assertEqual(lists:nth(1, tv_bitcount(X)), ffs(X)) || X <- L],
-     [?_assertEqual(lists:nth(2, tv_bitcount(X)), fls(X)) || X <- L]].
-
-tv_bitcount(1) -> [0, 0];
-tv_bitcount(2) -> [1, 1];
-tv_bitcount(3) -> [1, 0];
-tv_bitcount(255) -> [7, 0];
-tv_bitcount(256) -> [8, 8];
-tv_bitcount(511) -> [8, 0];
-tv_bitcount(512) -> [9, 9];
-tv_bitcount(32767) -> [14, 0];
-tv_bitcount(32768) -> [15, 15];
-tv_bitcount(65535) -> [15, 0];
-tv_bitcount(65536) -> [16, 16];
-tv_bitcount(2147483648) -> [31, 31];
-tv_bitcount(4294967296) -> [32, 32];
-tv_bitcount(8589934591) -> [32, 0];
-tv_bitcount(8589934592) -> [33, 33];
-tv_bitcount(18446744073709551616) -> [64, 64].
+mktree(L) ->
+    mktree(new(), L).
+mktree(Tree, []) ->
+    Tree;
+mktree(Tree, [H|T]) ->
+    mktree(add(Tree, H), T).
 
 %% @doc Return the Merkle Tree Head for the leaves in L. Implements
 %% the algorithm in section 2.1 of RFC 6962. Used for testing.
 -spec mth(list()) -> binary().
 mth([]) ->
-    hashfun(<<"">>);
+    hash(<<"">>);
 mth(L) ->
     case length(L) of
-        1 -> hashfun([<<"\x00">>, L]);
-        _ -> Split = 1 bsl ffs(length(L) - 1),
+        1 -> hash([<<"\x00">>, L]);
+        _ -> Split = 1 bsl (bitpos_first_set(length(L) - 1) - 1),
              {L1, L2} = lists:split(Split, L),  % TODO: PERF
-             hashfun([<<"\x01">>, mth(L1), mth(L2)])
+             hash([<<"\x01">>, mth(L1), mth(L2)])
     end.
-
-%% @doc Return the Merkle Audit Path for leaf m in L. Implements the
-%% algorithm in section 2.1.1 of RFC 6962. Used for testing.
--spec path(integer(), list()) -> list().
-path(0, L) when length(L) == 1 ->
-    [];
-path(M, L) ->
-    K = 1 bsl ffs(length(L) - 1),
-    {L1, L2} = lists:split(K, L),
-    R = case M < K of
-            true -> [path(M, L1), mth(L2)];
-            _ -> [path(M - K, L2), mth(L1)]
-        end,
-    lists:flatten(R).
-
-%% @doc Return the Merkle Consistency Proof between the first m leaves
-%% of L and L. Implements the algorithm in section 2.1.2 of RFC
-%% 6962. Used for testing.
--spec proof(integer(), list()) -> list().
-proof(M, L) ->
-    [niy, M, L].
-
--spec create(iolist() | binary()) -> head().
-create(D) ->
-    mkhead(1, mkleaf(D)).
-
--spec mkhead(list()) -> head().
-mkhead([]) ->
-    mkhead(1, mkleaf([]));
-mkhead(L) when is_list(L) ->
-    mkhead(create(hd(L)), lists:reverse(tl(L))).
-
-%% For looking at a tree in a REPL.
-%% hashes_hex(Head) ->
-%%     lists:map(fun hex:bin_to_hexstr/1, hashes(Head)).
-%% hashes(Head) when is_record(Head, head) ->
-%%     lists:flatten(hashes(Head#head.tree));
-%% hashes(#inner{child0 = L, child1 = R, hash = H}) ->
-%%     [H | [hashes(L), hashes(R)]];
-%% hashes(#leaf{hash = H}) ->
-%%     H.