sysio::chain::incremental_merkle_impl< DigestType, Container, Args > Class Template Reference

detail More...

#include <incremental_merkle.hpp>

Collaboration diagram for sysio::chain::incremental_merkle_impl< DigestType, Container, Args >:

Public Member Functions
	incremental_merkle_impl ()
	incremental_merkle_impl (const incremental_merkle_impl &)=default
	incremental_merkle_impl (incremental_merkle_impl &&)=default
incremental_merkle_impl &	operator= (const incremental_merkle_impl &)=default
incremental_merkle_impl &	operator= (incremental_merkle_impl &&)=default
template<typename Allocator , std::enable_if_t<!std::is_same< std::decay_t< Allocator >, incremental_merkle_impl >::value, int > = 0>
	incremental_merkle_impl (Allocator &&alloc)
const DigestType &	append (const DigestType &digest)
DigestType	get_root () const

Public Attributes
uint64_t	_node_count
Container< DigestType, Args... >	_active_nodes

Detailed Description

template<typename DigestType, template< typename ... > class Container = vector, typename ... Args>
class sysio::chain::incremental_merkle_impl< DigestType, Container, Args >

A balanced merkle tree built in such that the set of leaf nodes can be appended to without triggering the reconstruction of inner nodes that represent a complete subset of previous nodes.

to achieve this new nodes can either imply an set of future nodes that achieve a balanced tree OR realize one of these future nodes.

Once a sub-tree contains only realized nodes its sub-root will never change. This allows proofs based on this merkle to be very stable after some time has past only needing to update or add a single value to maintain validity.

Definition at line 95 of file incremental_merkle.hpp.

Constructor & Destructor Documentation

incremental_merkle_impl() [1/4]

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::incremental_merkle_impl ( )

inline

Definition at line 97 of file incremental_merkle.hpp.

      :_node_count(0)
      {}

incremental_merkle_impl() [2/4]

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::incremental_merkle_impl ( const incremental_merkle_impl< DigestType, Container, Args > & )

default

incremental_merkle_impl() [3/4]

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::incremental_merkle_impl ( incremental_merkle_impl< DigestType, Container, Args > && )

default

incremental_merkle_impl() [4/4]

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

template<typename Allocator , std::enable_if_t<!std::is_same< std::decay_t< Allocator >, incremental_merkle_impl >::value, int > = 0>

sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::incremental_merkle_impl ( Allocator && alloc )

inline

Definition at line 107 of file incremental_merkle.hpp.

:_active_nodes(forward<Allocator>(alloc)){}

Member Function Documentation

append()

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

const DigestType & sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::append ( const DigestType & digest )

inline

Add a node to the incremental tree and recalculate the _active_nodes so they are prepared for the next append.

The algorithm for this is to start at the new node and retreat through the tree for any node that is the concatenation of a fully-realized node and a partially realized node we must record the value of the fully-realized node in the new _active_nodes so that the next append can fetch it. Fully realized nodes and Fully implied nodes do not have an effect on the _active_nodes.

For convention AND to allow appends when the _node_count is a power-of-2, the current root of the incremental tree is always appended to the end of the new _active_nodes.

In practice, this can be done iteratively by recording any "left" value that is to be combined with an implied node.

If the appended node is a "left" node in its pair, it will immediately push itself into the new active nodes list.

If the new node is a "right" node it will begin collapsing upward in the tree, reading and discarding the "left" node data from the old active nodes list, until it becomes a "left" node. It must then push the "top" of its current collapsed sub-tree into the new active nodes list.

Once any value has been added to the new active nodes, all remaining "left" nodes should be present in the order they are needed in the previous active nodes as an artifact of the previous append. As they are read from the old active nodes, they will need to be copied in to the new active nodes list as they are still needed for future appends.

As a result, if an append collapses the entire tree while always being the "right" node, the new list of active nodes will be empty and by definition the tree contains a power-of-2 number of nodes.

Regardless of the contents of the new active nodes list, the top "collapsed" value is appended. If this tree is not a power-of-2 number of nodes, this node will not be used in the next append but still serves as a conventional place to access the root of the current tree. If this is a power-of-2 number of nodes, this node will be needed during then collapse phase of the next append so, it serves double duty as a legitimate active node and the conventional storage location of the root.

Parameters

digest

- the node to add

Returns

- the new root

Definition at line 168 of file incremental_merkle.hpp.

                                                         {
         bool partial = false;
         auto max_depth = detail::calcluate_max_depth(_node_count + 1);
         auto current_depth = max_depth - 1;
         auto index = _node_count;
         auto top = digest;
         auto active_iter = _active_nodes.begin();
         auto updated_active_nodes = vector<DigestType>();
         updated_active_nodes.reserve(max_depth);
 
         while (current_depth > 0) {
            if (!(index & 0x1)) {
               // we are collapsing from a "left" value and an implied "right" creating a partial node
 
               // we only need to append this node if it is fully-realized and by definition
               // if we have encountered a partial node during collapse this cannot be
               // fully-realized
               if (!partial) {
                  updated_active_nodes.emplace_back(top);
               }
 
               // calculate the partially realized node value by implying the "right" value is identical
               // to the "left" value
               top = DigestType::hash(make_canonical_pair(top, top));
               partial = true;
            } else {
               // we are collapsing from a "right" value and an fully-realized "left"
 
               // pull a "left" value from the previous active nodes
               const auto& left_value = *active_iter;
               ++active_iter;
 
               // if the "right" value is a partial node we will need to copy the "left" as future appends still need it
               // otherwise, it can be dropped from the set of active nodes as we are collapsing a fully-realized node
               if (partial) {
                  updated_active_nodes.emplace_back(left_value);
               }
 
               // calculate the node
               top = DigestType::hash(make_canonical_pair(left_value, top));
            }
 
            // move up a level in the tree
            current_depth--;
            index = index >> 1;
         }
 
         // append the top of the collapsed tree (aka the root of the merkle)
         updated_active_nodes.emplace_back(top);
 
         // store the new active_nodes
         detail::move_nodes(_active_nodes, std::move(updated_active_nodes));
 
         // update the node count
         _node_count++;
 
         return _active_nodes.back();
 
      }

Here is the call graph for this function:

get_root()

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

DigestType sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::get_root ( ) const

inline

l return the current root of the incremental merkle

Returns

Definition at line 233 of file incremental_merkle.hpp.

                                  {
         if (_node_count > 0) {
            return _active_nodes.back();
         } else {
            return DigestType();
         }
      }

Here is the caller graph for this function:

operator=() [1/2]

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

incremental_merkle_impl & sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::operator= ( const incremental_merkle_impl< DigestType, Container, Args > & )

default

operator=() [2/2]

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

incremental_merkle_impl & sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::operator= ( incremental_merkle_impl< DigestType, Container, Args > && )

default

Member Data Documentation

_active_nodes

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

Container<DigestType, Args...> sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::_active_nodes

Definition at line 243 of file incremental_merkle.hpp.

_node_count

template<typename DigestType , template< typename ... > class Container = vector, typename ... Args>

uint64_t sysio::chain::incremental_merkle_impl< DigestType, Container, Args >::_node_count

Definition at line 242 of file incremental_merkle.hpp.

---

The documentation for this class was generated from the following file:

• libraries/chain/include/sysio/chain/incremental_merkle.hpp