From fbf64f31f34a12a9fc983f74bec27e5fbbe85f34 Mon Sep 17 00:00:00 2001 From: Linus Nordberg Date: Tue, 9 Sep 2014 16:29:53 +0200 Subject: New hash tree implementation, using an ETS table for the hashes. Also, add an untested entry storage implementation, using multiple DETS tables. --- src/ht.erl | 560 +++++++++++++++++++++---------------------------------------- 1 file changed, 189 insertions(+), 371 deletions(-) (limited to 'src/ht.erl') 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 || <> <= 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 || <> <= 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 || <> <= 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 || <> <= 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 || <> <= 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 <- 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. -- cgit v1.1