Implement path/1 for testing.

1 files changed, 44 insertions, 4 deletions

diff --git a/src/ht.erl b/src/ht.erl
index 68a7b59..ff7b52a 100644
--- a/src/ht.erl
+++ b/src/ht.erl
@@ -249,16 +249,38 @@ append_eq_mth_test() ->
     ?assertEqual(gethash((mkhead(L))#head.tree), mth(L)).
 
 audit_path_test_() ->
-    H = mkhead([]),
-    M = 0,
-    [?_assertEqual([niy, H, M], path(H, M))].
+    Leaves = ["d0", "d1", "d2", "d3", "d4", "d5", "d6"],
+    %%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)],
+                   lists:map(fun hex:bin_to_hexstr/1, path(3, Leaves))),
+     ?_assertEqual([maps:get(f, H), maps:get(j, H), maps:get(k, H)],
+                   lists:map(fun hex:bin_to_hexstr/1, path(4, Leaves))),
+     ?_assertEqual([maps:get(i, H), maps:get(k, H)],
+                   lists:map(fun hex:bin_to_hexstr/1, path(6, Leaves)))].
 
 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.
 %%
@@ -307,8 +329,16 @@ mth(L) ->
 %% @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) ->
-    [niy, 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
@@ -326,3 +356,13 @@ 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.