diff options
Diffstat (limited to 'src/ht.erl')
-rw-r--r-- | src/ht.erl | 73 |
1 files changed, 54 insertions, 19 deletions
@@ -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, |