diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/ht.erl | 47 |
1 files changed, 41 insertions, 6 deletions
@@ -14,7 +14,8 @@ -type inner() :: #inner{}. -export_type([head/0, tree/0, inner/0, leaf/0]). --export([create/0, append/2, tree_hash/1, size/1, audit_path/2]). +-export([create/0, append/2, tree_hash/1, size/1, audit_path/2, + consistency_proof/2]). %% Public interface. -spec create() -> head(). @@ -73,12 +74,21 @@ append(Dest, Newtree, 0) when is_record(Dest, inner) -> append(Dest, Newtree, Depth) when is_record(Dest, inner) -> mkinner(Dest#inner.child0, append(Dest#inner.child1, Newtree, Depth - 1)). -%% @doc return a list of those hashes needed to calculate the tree -%% hash for Head given the knowledge of the hash in entry with number -%% Index. +%% @doc Return an audit path, i.e 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. -spec audit_path(head(), non_neg_integer()) -> list(). -audit_path(Head, Index) -> - [fixme, Head, Index]. +audit_path(Head, N) -> + [fixme, Head, N]. + +%% @doc Return a consistency proof, i.e. the shortest list of nodes +%% required to verify that the tree built from the first n leaves of a +%% given tree is a subset of that tree. Consistency proofs prove the +%% append-only property of a tree. +-spec consistency_proof(head(), non_neg_integer()) -> list(). +consistency_proof(Head, N) -> + [fixme, Head, N]. %%%%%%%%%%%%%%%%%%%% %% Private functions. @@ -236,6 +246,16 @@ append_eq_mth_test() -> L = [<<X:16>> || X <- lists:seq(0, Count)], ?assertEqual(gethash((mkhead(L))#head.tree), mth(L)). +audit_path_test_() -> + H = mkhead([]), + M = 0, + [?_assertEqual([niy, H, M], path(H, M))]. + +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. @@ -269,6 +289,8 @@ tv_bitcount(8589934591) -> [32, 0]; tv_bitcount(8589934592) -> [33, 33]; tv_bitcount(18446744073709551616) -> [64, 64]. +%% @doc Return the Merkle Tree Head for the leafs in L. Implements +%% the algorithm in section 2.1 of RFC 6962. Used for testing. -spec mth(list()) -> binary(). mth([]) -> hashfun(<<"">>); @@ -280,6 +302,19 @@ mth(L) -> hashfun([<<"\x01">>, mth(L1), mth(L2)]) end. +%% @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(M, L) -> + [niy, M, L]. + +%% @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 +%% 6962. Used for testing. +-spec proof(integer(), list()) -> list(). +proof(M, L) -> + [niy, M, L]. + -spec create(iolist() | binary()) -> head(). create(D) -> mkhead(1, mkleaf(D)). |