From 782a42a88533fc6fe2b82aac3f191d32eafcb76c Mon Sep 17 00:00:00 2001 From: Linus Nordberg Date: Sat, 13 Sep 2014 19:53:31 +0200 Subject: Implement path/2. --- src/ht.erl | 264 ++++++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 199 insertions(+), 65 deletions(-) (limited to 'src') diff --git a/src/ht.erl b/src/ht.erl index 8118274..9c1a193 100644 --- a/src/ht.erl +++ b/src/ht.erl @@ -79,69 +79,111 @@ handle_call(size, _From, State) -> handle_call({add, Entry}, _From, State) -> {reply, ok, add(State, Entry)}; handle_call(tree_hash, _From, State) -> - {NewState, Hash} = tree_hash(State, State#tree.version), + {NewState, Hash} = head(State, State#tree.version), {reply, Hash, NewState}; handle_call({tree_hash, Version}, _From, State) -> - {NewState, Hash} = tree_hash(State, Version), + {NewState, Hash} = head(State, Version), {reply, Hash, NewState}; -handle_call({path, _Index, _Version}, _From, State) -> - {reply, nyi, State}; +handle_call({path, Index, Version}, _From, State) -> + {NewState, Path} = path(State, Index, Version), + {reply, Path, NewState}; handle_call({consistency, _Version1, _Version2}, _From, State) -> {reply, nyi, State}. %%%%%%%%%%%%%%%%%%%% %% Private. --spec get_hash(tree(), non_neg_integer(), tuple()) -> {tree(), binary()}. -get_hash(Tree, Version, IR) -> - NewTree = update(Tree, Version), - Hash = ts:retrieve_hash(NewTree#tree.store, IR), - {NewTree, Hash}. -%% FIXME: rename to tree_head or maybe just head? --spec tree_hash(tree(), integer()) -> {tree(), binary()}. -tree_hash(Tree, -1) -> +%% @doc Return a list of hashes showing the path from leaf Index to +%% the tree head in the tree of version Version. +-spec path(tree(), non_neg_integer(), non_neg_integer()) -> {tree(), list()}. +path(Tree, _Index, -1) -> + {Tree, []}; +path(Tree, Index, Version) -> + {Tree, path(update(Tree, Version), 0, Index, Version, Version, [])}. + +-spec path(tree(), non_neg_integer(), non_neg_integer(), non_neg_integer(), non_neg_integer(), list()) -> list(). +path(_, _, _, 0, _, Acc) -> + reverse(Acc); +path(Tree, Layer, I, ILast, Version, Acc) -> + path(Tree, Layer + 1, parent(I), parent(ILast), Version, + case sibling(I) of + Sib when Sib == ILast -> + %% We're at the edge of the layer and might need to + %% recompute an old tree. + [old_version_tree_head(Tree, Version, Layer) | Acc]; + Sib when Sib < ILast -> + %% Just use sibling. + [get_hash(Tree, {Sib, Layer}) | Acc]; + _ -> + %% Sibling is larger than ILast so doesn't exist. + Acc + end). + +%% @doc updates the tree and returns new tree plus hash for IR +-spec get_hash(tree(), tuple()) -> binary(). +get_hash(Tree, IR) -> + ts:retrieve_hash(Tree#tree.store, IR). + +-spec head(tree(), integer()) -> {tree(), binary()}. +head(Tree, -1) -> {Tree, hash(<<"">>)}; -tree_hash(Tree = #tree{version = V}, Version) when Version == V -> - get_hash(Tree, Version, {0, depth(Tree) - 1}); -tree_hash(Tree = #tree{version = V}, Version) when Version > V -> +head(Tree = #tree{version = V}, Version) when Version == V -> + NewTree = update(Tree), + {NewTree, get_hash(NewTree, {0, depth(Tree) - 1})}; +head(Tree = #tree{version = V}, Version) when Version > V -> {Tree, enotimetravel}; -tree_hash(Tree, Version) -> - old_version_tree_head(update(Tree, Version), Version). +head(Tree, Version) -> + NewTree = update(Tree, Version), + {NewTree, old_version_tree_head(NewTree, Version)}. --spec old_version_tree_head(tree(), non_neg_integer()) -> {tree(), binary()}. +-spec old_version_tree_head(tree(), non_neg_integer()) -> binary(). old_version_tree_head(Tree, Version) -> + old_version_tree_head(Tree, Version, -1). + +-spec old_version_tree_head(tree(), non_neg_integer(), integer()) -> binary(). +old_version_tree_head(Tree, Version, BreakAtLayer) -> true = Tree#tree.evaluated >= Version, % ASSERTION %% Go up the tree from the rightmost leaf (index=Version) until a %% left node is found. (There is always one -- the head is a left %% node.) - {FirstLeftR, FirstLeftI} = first_left_node(0, Version), + {FirstLeftR, FirstLeftI} = first_left_node(0, Version, BreakAtLayer), %% Walk up the tree from this lowest left node up to and including %% the last right node, rehashing as we go. Calculate the parent %% hash of that node and its sibling. Return that hash. - {NewTree, LeftHash} = get_hash(Tree, Version, {FirstLeftI, FirstLeftR}), - last_right_node_rehash(NewTree, Version, FirstLeftR, FirstLeftI, LeftHash). + last_right_node_rehash(Tree, Version, FirstLeftR, FirstLeftI, + get_hash(Tree, {FirstLeftI, FirstLeftR}), + BreakAtLayer). -spec last_right_node_rehash(tree(), non_neg_integer(), non_neg_integer(), - non_neg_integer(), binary()) -> {tree(), binary()}. -last_right_node_rehash(Tree, _Version, _Layer, 0, RightNodeHash) -> - {Tree, RightNodeHash}; -last_right_node_rehash(Tree, Version, Layer, Index, RightNodeHash) -> - {NewTree, Hash} = - case right_node_p(Index) of - true -> - {T2, LHash} = get_hash(Tree, Version, {Index - 1, Layer}), - {T2, mkinnerhash(LHash, RightNodeHash)}; - false -> - {Tree, RightNodeHash} - end, - last_right_node_rehash(NewTree, Version, Layer + 1, parent(Index), Hash). - --spec first_left_node(non_neg_integer(), non_neg_integer()) -> + non_neg_integer(), binary(), integer()) -> + binary(). +last_right_node_rehash(_, _, Layer, _, RightNodeHash, BAL) when Layer == BAL -> + %% Bailing out at Layer. + RightNodeHash; +last_right_node_rehash(_, _, _, 0, RightNodeHash, _) -> + %% Index is 0, we're done. + RightNodeHash; +last_right_node_rehash(Tree, Version, Layer, Index, RightNodeHash, BAL) -> + last_right_node_rehash( + Tree, Version, Layer + 1, parent(Index), + case right_node_p(Index) of + true -> + %% Rehash parent using sibling. + mkinnerhash(get_hash(Tree, {Index - 1, Layer}), RightNodeHash); + false -> + %% Just use the incoming hash. + RightNodeHash + end, + BAL). + +-spec first_left_node(non_neg_integer(), non_neg_integer(), non_neg_integer()) -> {non_neg_integer(), non_neg_integer()}. -first_left_node(Layer, Index) -> +first_left_node(Layer, Index, BAL) when Layer == BAL -> + {Layer, Index}; +first_left_node(Layer, Index, BAL) -> case right_node_p(Index) of - true -> first_left_node(Layer + 1, parent(Index)); + true -> first_left_node(Layer + 1, parent(Index), BAL); false -> {Layer, Index} end. @@ -171,6 +213,9 @@ new([List]) when is_list(List) -> add(Tree, D) % Return value -> Tree in next invocation. end, new(), List). +update(Tree) -> + update(Tree, Tree#tree.version). + %% @doc Calculate hashes in Tree up to and including node with index %% equal to Version. Update Tree.evaluated to reflect the new state. -spec update(tree(), non_neg_integer()) -> tree(). @@ -238,6 +283,13 @@ right_node_p(Index) -> _ -> false end. +-spec sibling(non_neg_integer()) -> non_neg_integer(). +sibling(Index) -> + case right_node_p(Index) of + true -> Index - 1; + false -> Index + 1 + end. + strip_bits_bottom(N, Nbits) -> (N bsr Nbits) bsl Nbits. @@ -273,20 +325,13 @@ hash(Data) -> %%%%%%%%%%%%%%%%%%%% %% Testing ht. +%% TODO: Move all these tests to a separate file in ../test. They're +%% only using external functions. -define(TEST_VECTOR_LEAVES, ["", "\x00", "\x10", " !", "01", "@ABC", "PQRSTUVW", "`abcdefghijklmno"]). --define(TEST_VECTOR_HASHES, - ["6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", - "fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", - "aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", - "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", - "4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", - "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", - "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", - "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"]). %% FIXME: Don't start and stop the server manually all the time. EUnit -%% can help. +%% can help! test_init(L) -> stop(), {ok, _Pid} = start_link(L). @@ -310,8 +355,9 @@ old_versions_test() -> tree_hash(X - 1)) end, random_entries(length(?TEST_VECTOR_LEAVES))). +%% FIXME: Move outside. old_versions_bigger_test() -> - LEAVES = [<> || X <- lists:seq(0, 512)], + LEAVES = [<> || X <- lists:seq(0, 64)], % 1024 is not unreasonable test_init(LEAVES), ?assertEqual(mth(LEAVES), tree_hash()), lists:foreach( @@ -319,32 +365,120 @@ old_versions_bigger_test() -> tree_hash(X - 1)) end, random_entries(length(LEAVES))). -%%%%%%%%%%%%%%%%%%%% -%% Testing the test helpers. -mth_test() -> - lists:foreach( - fun(X) -> ?assertEqual( - mth(lists:sublist(?TEST_VECTOR_LEAVES, X)), - hex:hexstr_to_bin(lists:nth(X, ?TEST_VECTOR_HASHES))) +%% Test vector from Googles C++ implementation, "Generated from +%% ReferenceMerklePath." +-define(TEST_VECTOR_PATHS, + %% {leaf_index+1, version+1, path} + [{0, 0, []}, + {1, 1, []}, + {1, 8, + ["96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", + "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", + "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"]}, + {6, 8, + ["bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", + "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", + "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"]}, + {3, 3, + ["fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125"]}, + {2, 5, + ["6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", + "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", + "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"]}]). + +%% @doc Test paths on a single version 7 tree. +%% FIXME: Move outside. +path_test() -> + test_init(?TEST_VECTOR_LEAVES), + foreach( + fun(N) -> + Test = lists:nth(N, ?TEST_VECTOR_PATHS), + ?assertEqual( + path_ref(element(1, Test) - 1, + lists:sublist(?TEST_VECTOR_LEAVES, element(2, Test))), + path(element(1, Test) - 1, element(2, Test) - 1)) end, - lists:seq(1, length(?TEST_VECTOR_LEAVES))). + lists:seq(1, length(?TEST_VECTOR_PATHS))). + +%% @doc Test path on minimal sized trees. +%% FIXME: Move outside. +path_inc_test() -> + foreach( + fun(N) -> + Test = lists:nth(N, ?TEST_VECTOR_PATHS), + Leaves = lists:sublist(?TEST_VECTOR_LEAVES, element(2, Test)), + test_init(Leaves), + ?assertEqual( + path_ref(element(1, Test) - 1, Leaves), + path(element(1, Test) - 1, element(2, Test) - 1)) + end, + lists:seq(1, length(?TEST_VECTOR_PATHS))). %%%%%%%%%%%%%%%%%%%% %% Test helpers. - random_entries(N) -> [V || {_, V} <- lists:sort( [{random:uniform(N), E} || E <- lists:seq(1, N)])]. -%% @doc Return the Merkle Tree Head for the leaves in L. Implements -%% the algorithm in section 2.1 of RFC 6962. Used for testing. +%% @doc Return the Merkle Tree Head for the leaves in L. Reference +%% implementation for testing. Implements the algorithm in section 2.1 +%% of RFC 6962. -spec mth(list()) -> binary(). mth([]) -> hash(<<"">>); +mth([E]) -> + hash([<<"\x00">>, E]); mth(L) -> - case length(L) of - 1 -> hash([<<"\x00">>, L]); - _ -> Split = 1 bsl (bitpos_first_set(length(L) - 1) - 1), - {L1, L2} = lists:split(Split, L), % TODO: PERF - hash([<<"\x01">>, mth(L1), mth(L2)]) + Split = 1 bsl (bitpos_first_set(length(L) - 1) - 1), + {L1, L2} = lists:split(Split, L), + hash([<<"\x01">>, mth(L1), mth(L2)]). + +%% @doc Return the Merkle Audit Path from I to the root of the tree +%% with leaves L. Reference implementation for testing. Implements the +%% algorithm in section 2.1.1 of RFC 6962. +-spec path_ref(non_neg_integer(), list()) -> list(). +path_ref(I, _) when I < 0 -> + []; +path_ref(I, L) when I >= length(L) -> + []; +path_ref(0, [_]) -> + []; +path_ref(I, L) -> + Split = 1 bsl (bitpos_first_set(length(L) - 1) - 1), + {L1, L2} = lists:split(Split, L), + case I of + I when I < Split -> + path_ref(I, L1) ++ [mth(L2)]; + _ -> + path_ref(I - Split, L2) ++ [mth(L1)] end. + +%%%%%%%%%%%%%%%%%%%% +%% Testing the test helpers. It's turtles all the way down. +-define(TEST_VECTOR_HASHES, + ["6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", + "fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", + "aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", + "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", + "4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", + "76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", + "ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", + "5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328"]). +mth_test() -> + lists:foreach( + fun(X) -> ?assertEqual( + hex:hexstr_to_bin(lists:nth(X, ?TEST_VECTOR_HASHES)), + mth(lists:sublist(?TEST_VECTOR_LEAVES, X))) + end, + lists:seq(1, length(?TEST_VECTOR_LEAVES))). + +path_ref_test() -> + foreach( + fun(N) -> + Test = lists:nth(N, ?TEST_VECTOR_PATHS), + ?assertEqual( + [hex:hexstr_to_bin(X) || X <- element(3, Test)], + path_ref(element(1, Test) - 1, + lists:sublist(?TEST_VECTOR_LEAVES, element(2, Test)))) + end, + lists:seq(1, length(?TEST_VECTOR_PATHS))). -- cgit v1.1