Implement path/2.

1 files changed, 199 insertions, 65 deletions

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:32>> || X <- lists:seq(0, 512)],
+    LEAVES = [<<X:32>> || 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))).