1 files changed, 54 insertions, 19 deletions
diff --git a/src/ht.erl b/src/ht.erl
index c10ae33..aeea829 100644
--- a/src/ht.erl
+++ b/src/ht.erl
@@ -87,10 +87,27 @@ append(Dest, Newtree, Depth) when is_record(Dest, inner) ->
 %%
 %% 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. Audit paths prove existance of a given leaf in a given tree.
+%% 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, N) ->
-    [fixme, Head, N].
+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, [gethash2(Right) | Acc]);
+        _ ->                                    % Take a right.
+            audit_path(Right, PathT, [gethash2(Left) | Acc])
+    end.
 
 %% @doc Return a consistency proof.
 %%
@@ -148,8 +165,10 @@ gethash(#leaf{hash=Hash}) ->
 gethash(#inner{child0=Child0, child1=Child1}) ->
     mkhash(Child0, Child1).
 
+gethash2(#leaf{hash = Hash}) -> Hash;
+gethash2(#inner{hash = Hash}) -> Hash.
+
 %% @doc Unsigned integer -> binary.
-%% In R16, we can use integer_to_binary/1.
 -spec ui2b(pos_integer()) -> binary().
 ui2b(Unsigned) ->
     binary:encode_unsigned(Unsigned).
@@ -198,6 +217,21 @@ 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"}).
 
 basic_helpers_test_() ->
     [test_bitcount()].
@@ -252,22 +286,10 @@ append_eq_mth_test() ->
     L = [<<X:16>> || X <- lists:seq(0, Count)],
     ?assertEqual(gethash((mkhead(L))#head.tree), mth(L)).
 
-audit_path_test_() ->
-    Leaves = ["d0", "d1", "d2", "d3", "d4", "d5", "d6"],
+path_test_() ->
+    Leaves = ?TEST_VECTOR_LEAVES2,
+    H = ?TEST_VECTOR_HASHES2,
     %%Tree = lists:foldl(fun(E, T) -> ht:append(T, E) end, ht:create(), Leaves),
-    H = #{
-      a => "C67F9FFE68E0761021341DD516428F42FBDEA633731CBDADA03BEA6B84C652F7",
-      b => "49B717E4D6ECDD82F6F6648CF8F86FDF4A912600A4557398E1733186FA952C1D",
-      c => "F366DF4718EF75064317794FF5300E0963E96DD93FE24203118055FA5A00BE13",
-      d => "5E0C4E1130DFA84D27437BA073EB817E1896643D42EA100A0940F8752D496783",
-      e => "39298BE94337336FC5515E7A34DE6EF23C9A1BFF66378B71918AE2D105D684C8",
-      f => "6D1BB6BBB111AF4A1E9EC0B9FB2613CC2BCB394141CEE8C2CD462B5AD3803D78",
-      g => "46C78708413A23175F51FAF1C22604BCCB44482D553B45943B189130EA8221C8",
-      h => "C59E9A6D9575777BA3BDBD3E3086516196CF87EC9760861362ABA5CD0F78DF1D",
-      i => "A4F2A847CCE0DCE0519B1D6B83E4CA15166193DBB0C8F864E736665EDBDE1994",
-      j => "D750CA922FABC5422EEC469D4370779B61D5488186CB871EEEA299D8113D20BC",
-      k => "8DF3870B33FAE650E81938994F98EB4551B143B86C95D3DAE4E6444E00715016",
-      l => "3CF05FF16D26C024828E93B3A14C5656E5ABCBC5E6F0BCE2CF8A169720599674"},
     [?_assertEqual([maps:get(b, H), maps:get(h, H), maps:get(l, H)],
                    lists:map(fun hex:bin_to_hexstr/1, path(0, Leaves))),
      ?_assertEqual([maps:get(c, H), maps:get(g, H), maps:get(l, H)],
@@ -277,6 +299,19 @@ audit_path_test_() ->
      ?_assertEqual([maps:get(i, H), maps: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([maps:get(b, H), maps:get(h, H), maps:get(l, H)],
+                   lists:map(fun hex:bin_to_hexstr/1, audit_path(Tree, 0))),
+     ?_assertEqual([maps:get(c, H), maps:get(g, H), maps:get(l, H)],
+                   lists:map(fun hex:bin_to_hexstr/1, audit_path(Tree, 3))),
+     ?_assertEqual([maps:get(f, H), maps:get(j, H), maps:get(k, H)],
+                   lists:map(fun hex:bin_to_hexstr/1, audit_path(Tree, 4))),
+     ?_assertEqual([maps:get(i, H), maps:get(k, H)],
+                   lists:map(fun hex:bin_to_hexstr/1, audit_path(Tree, 6)))].
+
 consistency_proof_test_() ->
     H = mkhead([]),
     M = 0,