Module merkle_tree

Merkle tree implementation with configurable bucketing, branching and hashing.

Copyright © 2011-2014 Zuse Institute Berlin

Version: $Id$

Authors: Maik Lange (malange@informatik.hu-berlin.de).

Description

Merkle tree implementation with configurable bucketing, branching and hashing. Underlaying tree structure is an n-ary tree. After calling gen_hashes the tree is ready to use and sealed.

Data Types

inner_hash_fun()

inner_hash_fun() = fun(([mt_node_key(), ...]) -> mt_node_key())

leaf_hash_fun()

leaf_hash_fun() = 
    fun((mt_bucket(), intervals:interval()) -> binary())

merkle_tree()

merkle_tree() = {merkle_tree, mt_config(), Root :: mt_node()}

mt_bucket()

mt_bucket() = [mt_bucket_entry()]

mt_bucket_entry()

mt_bucket_entry() = {rt_chord:key()}
                  | {rt_chord:key(), any()}
                  | {rt_chord:key(), any(), any()}

add more, if needed

mt_config()

mt_config() = 
    #mt_config{branch_factor = pos_integer(),
               bucket_size = pos_integer(),
               leaf_hf = leaf_hash_fun(),
               inner_hf = inner_hash_fun(),
               keep_bucket = boolean()}

only key value pairs of mt_config allowed:

mt_config_params()

mt_config_params() = [{branch_factor, pos_integer()} |
                      {bucket_size, pos_integer()} |
                      {leaf_hf, leaf_hash_fun()} |
                      {inner_hf, inner_hash_fun()} |
                      {keep_bucket, boolean()}]
                   | []

mt_inner()

mt_inner() = 
    {Hash :: mt_node_key() | nil,
     Count :: non_neg_integer(),
     ItemCount :: non_neg_integer(),
     Interval :: intervals:interval(),
     Child_list :: [mt_leaf() | mt_inner(), ...]}

mt_iter()

mt_iter() = [mt_node() | [mt_node()]]

mt_leaf()

mt_leaf() = 
    {Hash :: mt_node_key() | nil,
     ItemCount :: non_neg_integer(),
     Bucket :: mt_bucket(),
     Interval :: intervals:interval()}

mt_node()

mt_node() = mt_inner() | mt_leaf()

mt_node_key()

mt_node_key() = non_neg_integer()

mt_size()

mt_size() = 
    {InnerNodes :: non_neg_integer(),
     LeafNodes :: non_neg_integer(),
     Items :: non_neg_integer()}

Function Index

gen_hash/1Assigns hash values to all nodes in the tree.
gen_hash/2Assigns hash values to all nodes in the tree and removes the buckets afterwards if CleanBuckets is set.
get_branch_factor/1Gets the given merkle tree's branch factor (max number of children of an inner node).
get_bucket/1
get_bucket_size/1Gets the given merkle tree's bucket size (number of elements in a leaf).
get_childs/1
get_hash/1Gets the node's hash value.
get_interval/1
get_item_count/1Returns the number of items in all buckets in or below this node.
get_items/1Gets all items in the buckets of the given merkle tree or node list (in arbitrary order).
get_leaf_count/1Returns the number of leafs under a bucket (1 if the requested node is a leaf node).
get_leaves/1Gets all leaves in the given merkle tree or node list (in arbitrary order).
get_opt_bucket_size/3
get_root/1Gets the root node of a merkle tree.
insert/2
insert_list/2
is_empty/1Checks whether the merkle tree or tree node has any children or elements.
is_leaf/1Checks whether the given merkle_tree or node is a leaf.
is_merkle_tree/1Returns true if given term is a merkle tree otherwise false.
iterator/1Returns an iterator to visit all tree nodes with next/1.
keys_to_intervals/2Inserts the given keys into the given intervals.
leaf_hash_sha/2Leaf hash fun to use for the embedded merkle tree.
lookup/2Checks whether an interval is present in the merkle tree and returns the node responsible for it (exact match!).
new/1Creates a new empty merkle tree with default params for the given interval.
new/2Creates a new empty merkle tree with the given params and interval.
new/3Creates a new merkle tree with the given params, interval and entries from EntryList.
next/1
size/1Returns the total number of nodes in a tree or node (inner nodes and leaves).
size_detail/1Returns a triple with number of inner nodes, leaf nodes and hashed items.
store_graph/2Stores the tree graph into a png file.
store_to_DOT/2Stores the tree graph into a file in DOT language (for Graphviz or other visualization tools).
tester_create_hash_fun/1
tester_create_inner_hash_fun/1

Function Details

get_bucket_size/1

get_bucket_size(X1 :: merkle_tree()) -> pos_integer()

Gets the given merkle tree's bucket size (number of elements in a leaf).

get_branch_factor/1

get_branch_factor(X1 :: merkle_tree()) -> pos_integer()

Gets the given merkle tree's branch factor (max number of children of an inner node).

get_root/1

get_root(X1 :: merkle_tree()) -> mt_node()

Gets the root node of a merkle tree.

is_empty/1

is_empty(X1 :: merkle_tree() | mt_node()) -> boolean()

Checks whether the merkle tree or tree node has any children or elements.

new/1

new(I :: intervals:interval()) -> merkle_tree()

Creates a new empty merkle tree with default params for the given interval. Also creates the hash values.

new/2

new(I :: intervals:interval(), ConfParams :: mt_config_params()) ->
       merkle_tree()

Creates a new empty merkle tree with the given params and interval. Also creates the hash values. ConfParams = list of tuples defined by {config field name, value} e.g. [{branch_factor, 32}, {bucket_size, 16}]

new/3

new(I :: intervals:interval(),
    EntryList :: mt_bucket(),
    ConfParams :: mt_config_params()) ->
       merkle_tree()

Creates a new merkle tree with the given params, interval and entries from EntryList. Also creates the hash values. ConfParams = list of tuples defined by {config field name, value} e.g. [{branch_factor, 32}, {bucket_size, 16}]

lookup/2

lookup(I :: intervals:interval(), X2 :: merkle_tree()) ->
          mt_node() | not_found

Checks whether an interval is present in the merkle tree and returns the node responsible for it (exact match!).

get_hash/1

get_hash(X1 :: merkle_tree() | mt_node()) -> mt_node_key()

Gets the node's hash value.

get_interval/1

get_interval(X1 :: merkle_tree() | mt_node()) ->
                intervals:interval()

get_childs/1

get_childs(X1 :: merkle_tree() | mt_node()) -> [mt_node()]

get_item_count/1

get_item_count(X1 :: merkle_tree() | mt_node()) ->
                  non_neg_integer()

Returns the number of items in all buckets in or below this node.

get_items/1

get_items(N :: merkle_tree() | mt_node() | [mt_node()]) ->
             {Items :: mt_bucket(),
              LeafCount :: non_neg_integer()}

Gets all items in the buckets of the given merkle tree or node list (in arbitrary order).

get_leaf_count/1

get_leaf_count(N :: merkle_tree() | mt_node()) -> pos_integer()

Returns the number of leafs under a bucket (1 if the requested node is a leaf node). NOTE: This scans through the whole sub-tree!

get_leaves/1

get_leaves(N :: merkle_tree() | mt_node() | [mt_node()]) ->
              [mt_node()]

Gets all leaves in the given merkle tree or node list (in arbitrary order).

is_leaf/1

is_leaf(X1 :: merkle_tree() | mt_node()) -> boolean()

Checks whether the given merkle_tree or node is a leaf.

is_merkle_tree/1

is_merkle_tree(X1 :: any()) -> boolean()

Returns true if given term is a merkle tree otherwise false.

get_bucket/1

get_bucket(X1 :: merkle_tree() | mt_node()) -> mt_bucket()

insert_list/2

insert_list(Terms :: mt_bucket(), Tree :: merkle_tree()) ->
               merkle_tree()

insert/2

insert(Key :: mt_bucket_entry(), Tree :: merkle_tree()) ->
          merkle_tree()

gen_hash/1

gen_hash(Tree :: merkle_tree()) -> merkle_tree()

Assigns hash values to all nodes in the tree.

gen_hash/2

gen_hash(X1 :: merkle_tree(), CleanBuckets :: boolean()) ->
            merkle_tree()

Assigns hash values to all nodes in the tree and removes the buckets afterwards if CleanBuckets is set.

size/1

size(Node :: merkle_tree() | mt_node()) -> non_neg_integer()

Returns the total number of nodes in a tree or node (inner nodes and leaves)

size_detail/1

size_detail(Nodes :: merkle_tree() | [mt_node()]) -> mt_size()

Returns a triple with number of inner nodes, leaf nodes and hashed items.

iterator/1

iterator(Tree :: merkle_tree()) -> Iter :: mt_iter()

Returns an iterator to visit all tree nodes with next/1. Iterates over all tree nodes from left to right in a deep first manner.

next/1

next(R :: mt_iter()) -> none | {Node :: mt_node(), mt_iter()}

store_graph/2

store_graph(MerkleTree :: merkle_tree(), FileName :: string()) ->
               ok

Stores the tree graph into a png file.

store_to_DOT/2

store_to_DOT(MerkleTree :: merkle_tree(), FileName :: string()) ->
                ok

Stores the tree graph into a file in DOT language (for Graphviz or other visualization tools).

get_opt_bucket_size/3

get_opt_bucket_size(N :: non_neg_integer(),
                    V :: non_neg_integer(),
                    S :: pos_integer()) ->
                       pos_integer()

keys_to_intervals/2

keys_to_intervals(KList :: mt_bucket(), I :: [I, ...]) ->
                     Buckets ::
                         [{I,
                           Count :: non_neg_integer(),
                           mt_bucket()}]

Inserts the given keys into the given intervals.

leaf_hash_sha/2

leaf_hash_sha(Bucket :: merkle_tree:mt_bucket(),
              I :: intervals:interval()) ->
                 binary()

Leaf hash fun to use for the embedded merkle tree.

tester_create_hash_fun/1

tester_create_hash_fun(I :: 1) -> leaf_hash_fun()

tester_create_inner_hash_fun/1

tester_create_inner_hash_fun(I :: 1) -> inner_hash_fun()


Generated by EDoc, Sep 11 2020, 15:24:57.