From e84b362eb7f5dbdea44c811534521f89707f66b4 Mon Sep 17 00:00:00 2001 From: Linus Nordberg Date: Thu, 18 Sep 2014 13:00:44 +0200 Subject: Add field 'mtlhash' to the database, for get-proof-by-hash. Also, in db: Add field 'mtlhash' to record 'plop'. Rename 'hash' -> 'entryhash'. Add leaf_hash(), calculating a leaf hash from data. Fix a bug where print_tree() print half a byte of the hashes. Rename tree_hash() -> root(). Closes CATLFISH-3. --- src/db.erl | 43 +++++++++++++++++++++++++++---------------- src/db.hrl | 8 ++++++-- src/ht.erl | 42 ++++++++++++++++++++++-------------------- src/plop.erl | 24 +++++++++++++----------- 4 files changed, 68 insertions(+), 49 deletions(-) (limited to 'src') diff --git a/src/db.erl b/src/db.erl index 8f398cb..25cfc5e 100644 --- a/src/db.erl +++ b/src/db.erl @@ -7,7 +7,7 @@ %% API. -export([start_link/0, stop/0]). -export([init_db/0, init_db/1, init_tables/0, init_tables/1]). --export([add/1, find/1, get_by_index/2, get_by_index_sorted/2, size/0]). +-export([add/1, find/2, get_by_index/2, get_by_index_sorted/2, size/0]). %% API for testing. -export([dump/1, destroy_tables/0, info_tables/0, dump_to_file/1]). %% gen_server callbacks. @@ -48,7 +48,8 @@ init_tables(Nodes) -> {disc_only_copies, DiscOnlyCopies}, {attributes, record_info(fields, plop)}, {majority, true}]), - {atomic, ok} = mnesia:add_table_index(plop, hash). + {atomic, ok} = mnesia:add_table_index(plop, entryhash), + {atomic, ok} = mnesia:add_table_index(plop, mtlhash). destroy_tables() -> mnesia:delete_table(plop). @@ -74,8 +75,12 @@ stop() -> add(Entry) -> gen_server:call(?MODULE, {add, Entry}). -find(Hash) -> - gen_server:call(?MODULE, {find, Hash}). +%% @doc Find entry with entryhash=Hash. +find(entryhash, Hash) -> + gen_server:call(?MODULE, {find, entryhash, Hash}); +%% @doc Find entry with mtlhash=Hash. +find(mtlhash, Hash) -> + gen_server:call(?MODULE, {find, mtlhash, Hash}). dump(Table) -> gen_server:call(?MODULE, {dump, Table}). @@ -122,17 +127,14 @@ handle_call({dump, Table}, _From, State) -> end, Res = mnesia:transaction(F), {reply, Res, State}; -handle_call({find, Hash}, _From, State) -> - F = fun() -> - mnesia:index_read(plop, Hash, #plop.hash) - end, - {atomic, Result} = mnesia:transaction(F), - Record = case length(Result) of - 0 -> []; - 1 -> hd(Result); - _ -> duplicate_hash_in_db % FIXME: log an error - end, - {reply, Record, State}; +handle_call({find, entryhash, Hash}, _From, State) -> + {reply, + find_entry(fun() -> mnesia:index_read(plop, Hash, #plop.entryhash) end), + State}; +handle_call({find, mtlhash, Hash}, _From, State) -> + {reply, + find_entry(fun() -> mnesia:index_read(plop, Hash, #plop.mtlhash) end), + State}; handle_call({get_by_index, {Start, End}}, _From, State) -> Res = [X || [_, X] <- select_index(Start, End)], {reply, Res, State}; @@ -146,10 +148,19 @@ handle_call({get_by_index_sorted, {Start, End}}, _From, State) -> select_index(Start, End) -> F = fun() -> - MatchHead = {plop, '$1', '_', '$2', '_'}, + %% Get index and mtl. + MatchHead = {plop, '$1', '_', '_', '$2', '_'}, Guard = [{'>=', '$1', Start}, {'=<', '$1', End}], Result = ['$$'], mnesia:select(plop, [{MatchHead, Guard, Result}]) end, {atomic, Res} = mnesia:transaction(F), Res. + +find_entry(Fun) -> + {atomic, Result} = mnesia:transaction(Fun), + case length(Result) of + 0 -> []; + 1 -> hd(Result); + _ -> duplicate_hash_in_db % FIXME: log an error? + end. diff --git a/src/db.hrl b/src/db.hrl index 3914a8c..b5ceb2e 100644 --- a/src/db.hrl +++ b/src/db.hrl @@ -2,10 +2,14 @@ %%% See LICENSE for licensing information. %% @doc What's stored in the database. -%% 'index' is the primary key, 'hash' is also indexed. +%% 'index' is the primary key, 'entryhash' and 'mtlhash' are also +%% indexed, see init_tables/1. +%% NOTE: Don't change anything here without also fixing +%% select_index/2, which depends on the order of fields. -record(plop, { index :: non_neg_integer(), % Primary key. - hash :: binary(), % Hash over #plop_entry{} in mtl. + entryhash :: binary(), % Hash over #plop_entry{} in mtl. + mtlhash :: binary(), % Merkle Tree Leaf hash. mtl :: mtl(), % Merkle Tree Leaf. spt :: spt() % Signed Plop Timestamp. }). diff --git a/src/ht.erl b/src/ht.erl index 4150721..b6570a0 100644 --- a/src/ht.erl +++ b/src/ht.erl @@ -22,8 +22,8 @@ -module(ht). -behaviour(gen_server). --export([reset_tree/1, size/0, add/1, tree_hash/0, tree_hash/1]). --export([path/2, consistency/2]). +-export([reset_tree/1, size/0, leaf_hash/1]). +-export([add/1, root/0, root/1, path/2, consistency/2]). -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]). @@ -53,19 +53,21 @@ size() -> gen_server:call(?MODULE, size). add(Entry) -> gen_server:call(?MODULE, {add, Entry}). -tree_hash() -> - gen_server:call(?MODULE, tree_hash). -tree_hash(Version) -> - gen_server:call(?MODULE, {tree_hash, Version}). +root() -> + gen_server:call(?MODULE, root). +root(Version) -> + gen_server:call(?MODULE, {root, Version}). path(I, V) -> gen_server:call(?MODULE, {path, I, V}). consistency(V1, V2) -> gen_server:call(?MODULE, {consistency, V1, V2}). +leaf_hash(Data) -> + gen_server:call(?MODULE, {leaf_hash, Data}). %% Testing and debugging. testing_get_state() -> gen_server:call(?MODULE, testing_get_state). print_tree() -> - gen_server:call(?MODULE, print_tree). + gen_server:call(?MODULE, {print_tree, 4}). print_tree(HashOutputLen) -> gen_server:call(?MODULE, {print_tree, HashOutputLen}). @@ -91,12 +93,14 @@ handle_call(size, _From, State) -> {reply, State#tree.version + 1, State}; handle_call({add, Entry}, _From, State) -> {reply, ok, add(State, Entry)}; -handle_call(tree_hash, _From, State) -> +handle_call(root, _From, State) -> {NewState, Hash} = head(State, State#tree.version), {reply, Hash, NewState}; -handle_call({tree_hash, Version}, _From, State) -> +handle_call({root, Version}, _From, State) -> {NewState, Hash} = head(State, Version), {reply, Hash, NewState}; +handle_call({leaf_hash, Data}, _From, State) -> + {reply, mkleafhash(Data), State}; handle_call({path, Index, Version}, _From, State) -> {NewState, Path} = path(State, Index, Version), {reply, Path, NewState}; @@ -106,8 +110,6 @@ handle_call({consistency, Version1, Version2}, _From, State) -> % testing and debugging handle_call(testing_get_state, _From, State) -> {reply, State, State}; -handle_call(print_tree, _From, State) -> - {reply, print_tree(State, 4), State}; handle_call({print_tree, HashOutputLen}, _From, State) -> {reply, print_tree(State, HashOutputLen), State}. @@ -392,10 +394,10 @@ print_tree(Tree, HashOutputLen, Layer, ILast, LayersLeft) -> print_layer(Tree, HashOutputLen, Layer, ILast) -> foreach( - fun(I) -> io:format("~s ", - [string:substr( - hex:bin_to_hexstr( - get_hash(Tree, {I, Layer})), HashOutputLen, 1)]) + fun(I) -> io:format( + "~s ", [string:substr( + hex:bin_to_hexstr(get_hash(Tree, {Layer, I})), + 1, HashOutputLen)]) end, lists:seq(0, ILast)), io:format("~n"). @@ -418,24 +420,24 @@ add_test() -> lists:foreach( fun(X) -> L = lists:sublist(?TEST_VECTOR_LEAVES, X), test_init(L), - ?assertEqual(mth(L), tree_hash()) end, + ?assertEqual(mth(L), root()) end, random_entries(length(?TEST_VECTOR_LEAVES))). old_versions_test() -> test_init(?TEST_VECTOR_LEAVES), - ?assertEqual(mth(?TEST_VECTOR_LEAVES), tree_hash()), + ?assertEqual(mth(?TEST_VECTOR_LEAVES), root()), lists:foreach( fun(X) -> ?assertEqual(mth(lists:sublist(?TEST_VECTOR_LEAVES, X)), - tree_hash(X - 1)) end, + root(X - 1)) end, random_entries(length(?TEST_VECTOR_LEAVES))). old_versions_bigger_test() -> LEAVES = [<> || X <- lists:seq(0, 64)], % 1024 is not unreasonable test_init(LEAVES), - ?assertEqual(mth(LEAVES), tree_hash()), + ?assertEqual(mth(LEAVES), root()), lists:foreach( fun(X) -> ?assertEqual(mth(lists:sublist(LEAVES, X)), - tree_hash(X - 1)) end, + root(X - 1)) end, random_entries(length(LEAVES))). %% Test vector from Googles C++ implementation, "Generated from diff --git a/src/plop.erl b/src/plop.erl index 81d3cc9..92ada3a 100644 --- a/src/plop.erl +++ b/src/plop.erl @@ -151,9 +151,9 @@ handle_call({consistency, {First, Second}}, _From, Plop) -> {reply, ht:consistency(First - 1, Second - 1), Plop}; handle_call({inclusion, {Hash, TreeSize}}, _From, Plop) -> - {Index, Proof} = case db:find(Hash) of + {Index, Proof} = case db:find(mtlhash, Hash) of [] -> []; - {plop, I, _Hash, _MTL, _SPT} -> + {plop, I, _EntryHash, _MTLHash, _MTL, _SPT} -> {I, ht:path(I, TreeSize - 1)} end, {reply, {Index, Proof}, Plop}; @@ -175,13 +175,14 @@ do_add(TimestampedEntry = #timestamped_entry{entry = PlopEntry}, Privkey, LogID) -> DB_hash = crypto:hash(sha256, serialise(PlopEntry)), - Record = db:find(DB_hash), + Record = db:find(entryhash, DB_hash), case Record of - #plop{index = _I, mtl = #mtl{entry = E}, spt = SPT} -> - %%io:format("Found entry: index=~p~n", [I]), - %% Database consistency checking. FIXME: Remove. + #plop{index = _I, mtl = MTL, spt = SPT} -> + %% Costly database consistency checking. FIXME: Remove. + E = MTL#mtl.entry, Record = Record#plop{ - hash = DB_hash, + entryhash = DB_hash, + mtlhash = ht:leaf_hash(serialise(MTL)), mtl = #mtl{entry = #timestamped_entry{ timestamp = E#timestamped_entry.timestamp, @@ -190,13 +191,14 @@ do_add(TimestampedEntry = #timestamped_entry{entry = PlopEntry}, [] -> NewSPT = spt(LogID, Privkey, TimestampedEntry), MTL = #mtl{entry = TimestampedEntry}, - %%io:format("Creating new entry: index=~p~n", [ht:size()]), + MTLtext = serialise(MTL), DB_data = #plop{index = ht:size(), - hash = DB_hash, + entryhash = DB_hash, + mtlhash = ht:leaf_hash(MTLtext), mtl = MTL, spt = NewSPT}, {atomic, ok} = db:add(DB_data), - {ht:add(serialise(MTL)), NewSPT}; + {ht:add(MTLtext), NewSPT}; Err -> {error, Err} end. @@ -230,7 +232,7 @@ sth(PrivKey, []) -> sth(PrivKey, #sth_signed{version = Version, timestamp = Timestamp_in}) -> Timestamp = timestamp(Timestamp_in), Treesize = ht:size(), - Roothash = ht:tree_hash(), + Roothash = ht:root(), BinToSign = serialise(#sth_signed{ version = Version, signature_type = tree_hash, -- cgit v1.1