diff options
author | Linus Nordberg <linus@nordberg.se> | 2014-09-09 16:29:53 +0200 |
---|---|---|
committer | Linus Nordberg <linus@nordberg.se> | 2014-09-09 16:52:57 +0200 |
commit | fbf64f31f34a12a9fc983f74bec27e5fbbe85f34 (patch) | |
tree | 74ba2a26673c4686f0baaad658918e1cf216bc59 | |
parent | e7a1ca43af470b6e99c0e11d845903f9bf00c723 (diff) |
New hash tree implementation, using an ETS table for the hashes.
Also, add an untested entry storage implementation, using multiple
DETS tables.
-rw-r--r-- | src/es.erl | 72 | ||||
-rw-r--r-- | src/ht.erl | 560 | ||||
-rw-r--r-- | src/plop.erl | 31 | ||||
-rw-r--r-- | src/ts.erl | 34 |
4 files changed, 311 insertions, 386 deletions
diff --git a/src/es.erl b/src/es.erl new file mode 100644 index 0000000..9e8be8d --- /dev/null +++ b/src/es.erl @@ -0,0 +1,72 @@ +%%% Copyright (c) 2014, NORDUnet A/S. +%%% See LICENSE for licensing information. +%%% +%%% Entry storage. +%%% +%%% BUGS: Retrieving entries don't update list of tables. The effects +%%% are that 1) dets:open_file is called for each retrieval and 2) +%%% tables only read from won't get closed by close/1. + +-module(es). +-export_type([entry_store/0]). +-export([open/0, close/1, store/3, retrieve/2]). +-import(lists, [filtermap/2, map/2, foreach/2, nth/2, flatten/1]). + +-record(entry_store, {tables :: list()}). % [dets:tab_name()] +-type entry_store() :: #entry_store{}. + +%%%%%%%%%%%%%%%%%%%% +%% Public interface. +-spec open() -> entry_store(). +open() -> + Files = filtermap(fun(F) -> dets:is_dets_file(F) end, + filelib:wildcard("es*.dat")), + Tables = map(fun(F) -> list_to_atom(filename:basename(F, ".dat")) end, + Files), + foreach(fun(T) -> T = open_file(T) end, Tables), + #entry_store{tables = Tables}. + +-spec close(entry_store()) -> ok. +close(#entry_store{tables = Tables}) -> + foreach(fun(Tab) -> dets:close(Tab) end, Tables). + +-spec store(entry_store(), non_neg_integer(), binary()) -> entry_store(). +store(Store, Index, Entry) -> + {Tables, Tab} = get_table(Store#entry_store.tables, Index), + true = dets:insert_new(Tab, {Index, Entry}), + Store#entry_store{tables = Tables}. + +-spec retrieve(entry_store(), non_neg_integer()) -> binary() | notfound. +retrieve(#entry_store{tables = Tables}, Index) -> + {_, Tab} = get_table(Tables, Index), + case dets:lookup(Tab, Index) of + [E] -> element(2, E); + [] -> notfound; + Error -> exit(Error) + end. + +%%%%%%%%%%%%%%%%%%%% +%% Internal functions. +%%-define(TABLE_SIZE, 25000000). % < 2e9 / 32 + 8 +-define(TABLE_SIZE, 256). % For testing. +-define(AUTO_SAVE_INTERVAL, 30000). % Milliseconds. + +-spec get_table(list(), non_neg_integer()) -> {list(), dets:tab_name()}. +get_table(Tables, Index) -> + TableIndex = trunc(Index / ?TABLE_SIZE) + 1, + if TableIndex =< length(Tables) -> + {Tables, nth(TableIndex, Tables)}; + true -> + Tab = open_file(list_to_atom(flatten( + io_lib:format("es~p", [TableIndex])))), + {Tables ++ [Tab], Tab} % Order is important, efficiency not. + end. + +-spec open_file(atom()) -> dets:tab_name(). +open_file(Name) -> + {ok, Tab} = dets:open_file(Name, [{type, set}, + {file, atom_to_list(Name)++".dat"}, + {auto_save, ?AUTO_SAVE_INTERVAL}, + {min_no_slots, ?TABLE_SIZE}, + {max_no_slots, ?TABLE_SIZE}]), + Tab. @@ -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. diff --git a/src/plop.erl b/src/plop.erl index f681898..8377684 100644 --- a/src/plop.erl +++ b/src/plop.erl @@ -45,7 +45,7 @@ -record(state, {pubkey :: public_key:rsa_public_key(), privkey :: public_key:rsa_private_key(), logid :: binary(), - hashtree :: ht:head()}). + hashtree :: ht:history_tree()}). %% @doc The parts of an STH which is to be signed. Used as the %% interface to plop:sth/1, for testing. @@ -158,20 +158,21 @@ handle_call({test, pubkey}, _From, {reply, PK, Plop}. %%%%%%%%%%%%%%%%%%%% --spec build_tree_from_db() -> ht:head(). +-spec build_tree_from_db() -> ht:history_tree(). build_tree_from_db() -> - build_tree(ht:create(), lists:seq(0, db:size() - 1)). --spec build_tree(ht:head(), list()) -> ht:head(). -build_tree(Tree, []) -> - Tree; -build_tree(Tree, [H|T]) -> - Data = db_get_single_entry(H), - build_tree(ht:append(Tree, Data), T). - -db_get_single_entry(N) -> - [#mtl{entry = #timestamped_entry{entry = #plop_entry{data = Data}}}] = - db:get_by_index(N, N), - Data. + ht:new(db:size() - 1). + +%% -spec build_tree(ht:head(), list()) -> ht:head(). +%% build_tree(Tree, []) -> +%% Tree; +%% build_tree(Tree, [H|T]) -> +%% Data = db_get_single_entry(H), +%% build_tree(ht:append(Tree, Data), T). + +%% db_get_single_entry(N) -> +%% [#mtl{entry = #timestamped_entry{entry = #plop_entry{data = Data}}}] = +%% db:get_by_index(N, N), +%% Data. -spec do_add(timestamped_entry(), public_key:rsa_private_key(), binary(), any()) -> {any(), binary()}. @@ -199,7 +200,7 @@ do_add(TimestampedEntry = #timestamped_entry{entry = PlopEntry}, mtl = MTL, spt = NewSPT}, {atomic, ok} = db:add(DB_data), - {ht:append(Tree, serialise(MTL)), % New tree. + {ht:add(Tree, serialise(MTL)), % New tree. NewSPT}; % New SPT. Err -> {error, Err} end. diff --git a/src/ts.erl b/src/ts.erl new file mode 100644 index 0000000..8ea4895 --- /dev/null +++ b/src/ts.erl @@ -0,0 +1,34 @@ +% tree storage +-module(ts). +-include_lib("eunit/include/eunit.hrl"). +-export_type([tree_store/0]). +-export([new/0, delete/1, store/3, retrieve/2, retrieve_hash/2]). + +%% -record(tree_store, {warm :: ets:tid(), +%% frozen :: list()}). % [ets:tid()] +-record(tree_store, {table :: ets:tid()}). +-type tree_store() :: #tree_store{}. + +new() -> + %% tree_store#{warm = ets:new(nil, [{read_concurrency, true}]), + %% frozen = ets:new(nil, [{read_concurrency, true}])}. + #tree_store{table = ets:new(nil, [{read_concurrency, true}])}. + +delete(Store) -> + ets:delete(Store#tree_store.table). + +-spec store(tree_store(), tuple(), binary()) -> tree_store(). +store(Store, IR, Hash) -> + ets:insert(Store#tree_store.table, {IR, Hash}), + Store. + +-spec retrieve(tree_store(), tuple()) -> {tuple(), binary()}. +retrieve(#tree_store{table = Tab}, IR) -> + case ets:lookup(Tab, IR) of + [] -> exit(IR); + [R] -> R + end. + +-spec retrieve_hash(tree_store(), tuple()) -> binary(). +retrieve_hash(#tree_store{table = Tab}, IR) -> + ets:lookup_element(Tab, IR, 2). |