Implement consistency proofs.

1 files changed, 101 insertions, 11 deletions

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:32>> || 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) ->