diff options
| -rw-r--r-- | README | 5 | ||||
| -rw-r--r-- | src/ht.erl | 224 |
2 files changed, 229 insertions, 0 deletions
@@ -0,0 +1,5 @@ +plop is a public log based on a Merkle tree. It can be used for +implementing Certificate Transparency (RFC 6962). + +The first implementation is in Erlang. The only interface supported +initially is Erlang messages. diff --git a/src/ht.erl b/src/ht.erl new file mode 100644 index 0000000..97842bc --- /dev/null +++ b/src/ht.erl @@ -0,0 +1,224 @@ +-module('ht'). +-include_lib("eunit/include/eunit.hrl"). + +-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 leafs + tree :: tree()}). % the tree + +-type head() :: #head{}. +-type tree() :: inner() | leaf(). +-type leaf() :: #leaf{}. +-type inner() :: #inner{}. + +-export_type([head/0, tree/0, inner/0, leaf/0]). +-export([create/1, append/2, tree_hash/1, tree_version/1]). + +%% Public interface. +-spec create(iolist() | binary()) -> head(). +create(D) -> + mkhead(1, mkleaf(D)). + +-spec tree_hash(head()) -> binary(); + (tree()) -> binary(). +tree_hash(#head{tree=T}) -> + case T of + #inner{hash=H} -> H; + #leaf{hash=H} -> H + end. + +%% @doc Tree version number, i.e. number of leafs in tree. Note that +%% this is set off by one (one higher) compared with the history tree +%% version as explained by Crosby and Wallach. +-spec tree_version(head()) -> non_neg_integer(). +tree_version(#head{version=Ver}) -> + Ver. + +%% @doc Append Leaf to Head. +%% +%% 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 side to +%% level l, where l is the position of the first set bit in d, looking +%% at d "from the right". l=0 is where the leafs 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. +-spec append(head(), leaf()) -> head(). +append(Head, Leaf) when is_record(Leaf, leaf) -> + N = Head#head.version, + %Depth = depth(Head), + Level = fls(N), + RBD = rightbranchdepth(Head#head.tree), + %io:format("N=~p, Depth=~p, Level=~p, RBD=~p~n", [N, Depth, Level, RBD]), + #head{version = N + 1, tree = append(Head#head.tree, Leaf, RBD-Level-1)}. + +-spec append(tree(), tree(), pos_integer()) -> tree(). +append(Dest, Newtree, _) when is_record(Dest, leaf) -> + mkinner(Dest, Newtree); +append(Dest, Newtree, 0) when is_record(Dest, inner) -> + mkinner(Dest, Newtree); +append(Dest, Newtree, Depth) when is_record(Dest, inner) -> + mkinner(Dest#inner.child0, append(Dest#inner.child1, Newtree, Depth - 1)). + +%% Private functions. + +-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) -> + code:ensure_loaded(crypto), + case erlang:function_exported(crypto, hash, 2) of + true -> crypto:hash(sha256, Data); + _ -> crypto:sha(Data) + end. +%% hashfun_init() -> +%% sha_init(). +%% hashfun_update(C, D) -> +%% sha_update(C, D). +%% hashfun_final(C) -> +%% sha_final(C). + +-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)}. + +%% TODO: merge mkhash/2 and gethash? if so, use it in mkleaf/1. +-spec mkhash(tree(), tree()) -> binary(). +mkhash(Tree0, Tree1) -> + hashfun([<<"\x01">>, gethash(Tree0), gethash(Tree1)]). + +-spec gethash(tree()) -> binary(). +gethash(#leaf{hash=Hash}) -> + Hash; +gethash(#inner{child0=Child0, child1=Child1}) -> + mkhash(Child0, Child1). + +%% @doc Unsigned integer -> binary. +%% In R16, we can use integer_to_binary/1. +-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. +ffs([], Acc) -> + Acc; +ffs([H|T], Acc) -> + case H of + 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). + +%%%%%%%%%%%%%%%%%%%% +%% Internal tests. +-define(EMPTY_HASH, "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"). +-define(TEST_VECTOR_LEAVES, ["", "\x00", "\x10", " !", "01", "@ABC", "PQRSTUVW", "`abcdefghijklmno"]). +-define(TEST_VECTOR_HASHES, ["6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", + "fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", + "aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", + "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", + "4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", + "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", + "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", + "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"]). + +empty_hash_test() -> + ?assertEqual(hex:hexstr_to_bin(?EMPTY_HASH), mth([])). + +mth_test() -> + lists:foreach( + fun(X) -> ?assertEqual( + mth(lists:sublist(?TEST_VECTOR_LEAVES, X)), + hex:hexstr_to_bin(lists:nth(X, ?TEST_VECTOR_HASHES))) + end, + lists:seq(1, length(?TEST_VECTOR_LEAVES))). + + +%% @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), + io:format("~p~n", [L]), + ?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() -> + %% FIXME: Make larger trees once we've fixed That Bug. + L = lists:seq(1, 255), + ?assertEqual(gethash((mkhead(L))#head.tree), mth(L)). + + +%% 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 leafs 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. +-spec mth(list()) -> binary(). +mth([]) -> + hashfun(<<"">>); +mth(L) -> + case length(L) of + 1 -> hashfun([<<"\x00">>, L]); + _ -> Split = 1 bsl ffs(length(L) - 1), + {L1, L2} = lists:split(Split, L), % TODO: PERF + hashfun([<<"\x01">>, mth(L1), mth(L2)]) + end. + +-spec mkhead(list()) -> head(). +mkhead([]) -> + mkhead(1, mkleaf([])); +mkhead(L) when is_list(L) -> + mkhead(create(hd(L)), lists:reverse(tl(L))). |