From e41ef099a6dcf2947b759f6a8fff260d581723c6 Mon Sep 17 00:00:00 2001 From: Linus Nordberg Date: Sun, 14 Sep 2014 13:23:47 +0200 Subject: Implement consistency proofs. --- src/ht.erl | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 101 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/ht.erl b/src/ht.erl index 9c1a193..7d0a75a 100644 --- a/src/ht.erl +++ b/src/ht.erl @@ -27,6 +27,7 @@ -export([start_link/0, start_link/1, stop/0]). -export([init/1, handle_call/3, terminate/2, handle_cast/2, handle_info/2, code_change/3]). +-export([testing_get_state/0, print_tree/0]). -include("$CTROOT/plop/include/plop.hrl"). -include_lib("eunit/include/eunit.hrl"). @@ -58,6 +59,10 @@ path(I, V) -> gen_server:call(?MODULE, {path, I, V}). consistency(V1, V2) -> gen_server:call(?MODULE, {consistency, V1, V2}). +testing_get_state() -> + gen_server:call(?MODULE, testing_get_state). +print_tree() -> + gen_server:call(?MODULE, print_tree). %% gen_server callbacks init([]) -> @@ -87,20 +92,53 @@ handle_call({tree_hash, Version}, _From, 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}. +handle_call({consistency, Version1, Version2}, _From, State) -> + {NewState, ConsProof} = consistency(State, Version1, Version2), + {reply, ConsProof, NewState}; +handle_call(testing_get_state, _From, State) -> + {reply, State, State}; +handle_call(print_tree, _From, State) -> + {reply, print_tree(State), State}. %%%%%%%%%%%%%%%%%%%% %% Private. +-spec consistency(tree(), non_neg_integer(), non_neg_integer()) -> {tree(), list()}. +consistency(Tree, -1, _V2) -> + {Tree, []}; +consistency(Tree, V1, V2) when V1 >= V2 -> + {Tree, []}; +consistency(Tree, _V1, V2) when V2 > Tree#tree.version -> + {Tree, []}; +consistency(Tree, V1, V2) -> + %% Walk up the tree from V1 to first left child. + {StartLayer, StartIndex} = first_left_node(0, V1), + UpdTree = update(Tree, V2), + First = case StartIndex of + 0 -> []; + _ -> [get_hash(UpdTree, {StartIndex, StartLayer})] + end, + %% Get path from first left child to head of V2. + {_, Path} = path(UpdTree, StartLayer, StartIndex, V2), + {UpdTree, First ++ Path}. + %% @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, [])}. + path(Tree, 0, Index, Version). +-spec path(tree(), non_neg_integer(), non_neg_integer(), non_neg_integer()) -> + {tree(), list()}. +path(Tree, Layer, Index, Version) -> + %% The magic here is to tell path/6 to stop at Version >> Layer. + {Tree, path(update(Tree, Version), Layer, Index, + Version bsr Layer, Version, [])}. + +%% @doc Return path from {Layer,I} to head of tree Version. I is the +%% leftmost and ILast the rightmost node to consider, at Layer. -spec path(tree(), non_neg_integer(), non_neg_integer(), non_neg_integer(), non_neg_integer(), list()) -> list(). path(_, _, _, 0, _, Acc) -> reverse(Acc); @@ -177,7 +215,12 @@ last_right_node_rehash(Tree, Version, Layer, Index, RightNodeHash, BAL) -> end, BAL). --spec first_left_node(non_neg_integer(), non_neg_integer(), non_neg_integer()) -> +-spec first_left_node(non_neg_integer(), non_neg_integer()) -> + {non_neg_integer(), non_neg_integer()}. +first_left_node(Layer, Index) -> + first_left_node(Layer, Index, -1). + +-spec first_left_node(non_neg_integer(), non_neg_integer(), integer()) -> {non_neg_integer(), non_neg_integer()}. first_left_node(Layer, Index, BAL) when Layer == BAL -> {Layer, Index}; @@ -324,6 +367,27 @@ hash(Data) -> crypto:hash(sha256, Data). %%%%%%%%%%%%%%%%%%%% +%% Debugging helpers. +print_tree(Tree) -> + print_tree(update(Tree), 0, Tree#tree.version, depth(Tree)). + +print_tree(_, _, _, 0) -> + ok; +print_tree(Tree, Layer, ILast, LayersLeft) -> + print_layer(Tree, Layer, ILast), + print_tree(Tree, Layer + 1, ILast bsr 1, LayersLeft - 1). + +print_layer(Tree, Layer, ILast) -> + foreach( + fun(I) -> io:format("~s ", + [string:substr( + hex:bin_to_hexstr( + get_hash(Tree, {I, Layer})), 1, 4)]) + end, + lists:seq(0, ILast)), + io:format("~n"). + +%%%%%%%%%%%%%%%%%%%% %% Testing ht. %% TODO: Move all these tests to a separate file in ../test. They're %% only using external functions. @@ -336,9 +400,7 @@ test_init(L) -> stop(), {ok, _Pid} = start_link(L). -%% @doc Build tree using add/2 and mth/2 and compare the resulting -%% tree hashes. -%% FIXME: Move outside. +%% @doc Verify trees using add/2. add_test() -> lists:foreach( fun(X) -> L = lists:sublist(?TEST_VECTOR_LEAVES, X), @@ -346,7 +408,6 @@ add_test() -> ?assertEqual(mth(L), tree_hash()) end, random_entries(length(?TEST_VECTOR_LEAVES))). -%% FIXME: Move outside. old_versions_test() -> test_init(?TEST_VECTOR_LEAVES), ?assertEqual(mth(?TEST_VECTOR_LEAVES), tree_hash()), @@ -355,7 +416,6 @@ old_versions_test() -> tree_hash(X - 1)) end, random_entries(length(?TEST_VECTOR_LEAVES))). -%% FIXME: Move outside. old_versions_bigger_test() -> LEAVES = [<> || X <- lists:seq(0, 64)], % 1024 is not unreasonable test_init(LEAVES), @@ -387,7 +447,6 @@ old_versions_bigger_test() -> "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"]}]). %% @doc Test paths on a single version 7 tree. -%% FIXME: Move outside. path_test() -> test_init(?TEST_VECTOR_LEAVES), foreach( @@ -401,7 +460,6 @@ path_test() -> lists:seq(1, length(?TEST_VECTOR_PATHS))). %% @doc Test path on minimal sized trees. -%% FIXME: Move outside. path_inc_test() -> foreach( fun(N) -> @@ -414,6 +472,38 @@ path_inc_test() -> end, lists:seq(1, length(?TEST_VECTOR_PATHS))). +-define(TEST_VECTOR_PROOFS, + [{1, 1, []}, + {1, 8, + ["96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", + "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", + "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"]}, + {6, 8, + ["0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a", + "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", + "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"]}, + {2, 5, + ["5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", + "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"]}]). +%% @doc Test proofs on a single version 7 tree. +consistency_test() -> + test_init(?TEST_VECTOR_LEAVES), + foreach( + fun(N) -> + Test = lists:nth(N, ?TEST_VECTOR_PROOFS), + ?assertEqual( + consistency_proof_ref( + %% element(1, Test) - 1, + %% lists:sublist(?TEST_VECTOR_LEAVES, element(2, Test))), + Test), % FIXME + consistency(element(1, Test) - 1, element(2, Test) - 1)) + end, + lists:seq(1, length(?TEST_VECTOR_PROOFS))). + +%% FIXME: implement and move +consistency_proof_ref(Test) -> + [hex:hexstr_to_bin(X2) || X2 <- element(3, Test)]. + %%%%%%%%%%%%%%%%%%%% %% Test helpers. random_entries(N) -> -- cgit v1.1