merklecpp Documentation#

merklecpp is a header-only C++ library for creation and manipulation of Merkle trees. The main entry-point is the merkle::TreeT template, which allows us to create a Merkle tree with a compile-time configurable hash size and function.

A default implementation without further dependencies is provided as merkle::Tree, which uses the SHA256 compression function (merkle::sha256_compress()). merklecpp also provides bindings for the respective OpenSSL functions (see Hash functions), which can be specified as a template parameter as illustrated by the following example:

    merkle::TreeT<32, merkle::sha256_openssl> tree;
    for (auto h : hashes)
    {
      tree.insert(h);
    }
    auto root = tree.root();
    auto path = tree.path(hashes.size() - 1);
    assert(path->verify(root));

Trees#

template<size_t HASH_SIZE, void HASH_FUNCTION> class TreeT#

Template for Merkle trees.

Template Parameters:

HASH_SIZE – Size of each hash in number of bytes
HASH_FUNCTION – The hash function

Public Types

using Hash = HashT<HASH_SIZE>#: The type of hashes in the tree.

using Path = PathT<HASH_SIZE, HASH_FUNCTION>#: The type of paths in the tree.

using Tree = TreeT<HASH_SIZE, HASH_FUNCTION>#: The type of the tree.

Public Functions

TreeT() = default#: Constructs an empty tree.

inline TreeT(const TreeT &other)#: Copies a tree.

inline TreeT(TreeT &&other) noexcept#

Moves a tree.

Parameters:: other – Tree to move

inline TreeT(const std::vector<uint8_t> &bytes)#

Deserialises a tree.

Parameters:: bytes – Byte buffer containing a serialised tree

inline TreeT(const std::vector<uint8_t> &bytes, size_t &position)#

Deserialises a tree.

Parameters:

bytes – Byte buffer containing a serialised tree
position – Position of the first byte within bytes

inline TreeT(const Hash &root)#

Constructs a tree containing one root hash.

Parameters:: root – Root hash of the tree

inline ~TreeT()#: Deconstructor.

inline bool invariant()#: Invariant of the tree.

inline void insert(const uint8_t *hash)#

Inserts a hash into the tree.

Parameters:: hash – Hash to insert

inline void insert(const Hash &hash)#

Inserts a hash into the tree.

Parameters:: hash – Hash to insert

inline void insert(const std::vector<Hash> &hashes)#

Inserts multiple hashes into the tree.

Parameters:: hashes – Vector of hashes to insert

inline void insert(const std::list<Hash> &hashes)#

Inserts multiple hashes into the tree.

Parameters:: hashes – List of hashes to insert

inline void flush_to(size_t index)#

Flush the tree to some leaf.

Note

This invalidates all indicies smaller than index and no paths from them to the root can be extracted anymore.

Parameters:: index – Leaf index to flush the tree to

inline void retract_to(size_t index)#

Retracts a tree up to some leaf index.

Note

This invalidates all indicies greater than index and no paths from them to the root can be extracted anymore.

Parameters:: index – Leaf index to retract the tree to

inline Tree &operator=(const Tree &other)#

Assigns a tree.

Parameters:: other – The tree to assign
Returns:: The tree

inline Tree &operator=(Tree &&other) noexcept#

Assigns a tree by move.

Parameters:: other – The tree to assign
Returns:: The tree

inline const Hash &root()#

Extracts the root hash of the tree.

Returns:: The root hash

inline std::shared_ptr<Hash> past_root(size_t index)#

Extracts a past root hash.

Note

This extracts the root hash of the tree at a past state, when index was the last, right-most leaf index in the tree. It is equivalent to retracting the tree to index and then extracting the root.

Parameters:: index – The last leaf index to consider
Returns:: The root hash

inline Node *walk_to(size_t index, bool update, const std::function<bool(Node*&, bool)> &&f)#

Walks along the path from the root of a tree to a leaf.

Parameters:

index – The leaf index to walk to
update – Flag to enable re-computation of node fields (like subtree size) while walking
f – Function to call for each node on the path; the Boolean indicates whether the current step is a right or left turn.

Returns:

The final leaf node in the walk

inline std::shared_ptr<Path> path(size_t index)#

Extracts the path from a leaf index to the root of the tree.

Parameters:: index – The leaf index of the path to extract
Returns:: The path

inline std::shared_ptr<Path> past_path(size_t index, size_t as_of)#

Extracts a past path from a leaf index to the root of the tree.

Note

This extracts a path at a past state, when as_of was the last, right-most leaf index in the tree. It is equivalent to retracting the tree to as_of and then extracting the path of index.

Parameters:

index – The leaf index of the path to extract
as_of – The maximum leaf index to consider

Returns:

The past path

inline void serialise(std::vector<uint8_t> &bytes)#

Serialises the tree.

Parameters:: bytes – The vector of bytes to serialise to

inline void serialise(size_t from, size_t to, std::vector<uint8_t> &bytes)#

Serialises a segment of the tree.

Parameters:

from – Smalles leaf index to include
to – Greatest leaf index to include
bytes – The vector of bytes to serialise to

inline void deserialise(const std::vector<uint8_t> &bytes)#

Deserialises a tree.

Parameters:: bytes – The vector of bytes to deserialise from

inline void deserialise(const std::vector<uint8_t> &bytes, size_t &position)#

Deserialises a tree.

Parameters:

bytes – The vector of bytes to deserialise from
position – Position of the first byte in bytes

inline operator std::vector<uint8_t>() const#: Operator to serialise the tree.

inline const Hash &operator[](size_t index) const#

Operator to extract a leaf hash from the tree.

Parameters:: index – Leaf index of the leaf to extract
Returns:: The leaf hash

inline const Hash &leaf(size_t index) const#

Extract a leaf hash from the tree.

Parameters:: index – Leaf index of the leaf to extract
Returns:: The leaf hash

inline size_t num_leaves() const#

Number of leaves in the tree.

Note

This is the abstract number of leaves in the tree (including flushed leaves), not the number of nodes in memory.

Returns:: The number of leaves in the tree

inline size_t min_index() const#

Minimum leaf index.

Note

The smallest leaf index for which it is safe to extract roots and paths.

Returns:: The minumum leaf index

inline size_t max_index() const#

Maximum leaf index.

Note

The greatest leaf index for which it is safe to extract roots and paths.

Returns:: The maximum leaf index

inline bool empty() const#

Indicates whether the tree is empty.

Returns:: Boolean that indicates whether the tree is empty

inline size_t size()#

Computes the size of the tree.

Note

This is the number of nodes in the tree, including leaves and internal nodes.

Returns:: The size of the tree

inline size_t serialised_size()#

Computes the minumal number of bytes required to serialise the tree.

Returns:: The number of bytes required to serialise the tree

inline size_t serialised_size(size_t from, size_t to)#

The number of bytes required to serialise a segment of the tree.

Parameters:

from – The smallest leaf index to include
to – The greatest leaf index to include

Returns:

The number of bytes required to serialise the tree segment

inline std::string to_string(size_t num_bytes = HASH_SIZE) const#

Prints an ASCII representation of the tree to a stream.

Parameters:: num_bytes – The number of bytes of each node hash to print
Returns:: A string representing the tree

Public Members

struct merkle::TreeT::Statistics statistics#: Statistics.

struct Statistics#

Structure to hold statistical information.

Public Functions

inline std::string to_string() const#: String representation of the statistics.

Public Members

size_t num_hash = 0#: The number of hashes taken by the tree via hash()

size_t num_insert = 0#: The number of insert() opertations performed on the tree.

size_t num_root = 0#: The number of root() opertations performed on the tree.

size_t num_past_root = 0#: The number of past_root() opertations performed on the tree.

size_t num_flush = 0#: The number of flush_to() opertations performed on the tree.

size_t num_retract = 0#: The number of retract_to() opertations performed on the tree.

size_t num_paths = 0#: The number of paths extracted from the tree via path()

size_t num_past_paths = 0#: The number of past paths extracted from the tree via past_path()

using merkle::Tree = TreeT<32, sha256_compress>#: Default tree with default hash size and function.

Hashes#

template<size_t SIZE> struct HashT#

Template for fixed-size hashes.

Template Parameters:: SIZE – Size of the hash in number of bytes

Public Functions

inline HashT()#: Constructs a Hash with all bytes set to zero.

inline HashT(const uint8_t *bytes)#

Constructs a Hash from a byte buffer.

Parameters:: bytes – Buffer with hash value

inline HashT(const std::string &s)#

Constructs a Hash from a string.

Parameters:: s – String to read the hash value from

inline HashT(const std::vector<uint8_t> &bytes)#

Deserialises a Hash from a vector of bytes.

Parameters:: bytes – Vector to read the hash value from

inline HashT(const std::vector<uint8_t> &bytes, size_t &position)#

Deserialises a Hash from a vector of bytes.

Parameters:

bytes – Vector to read the hash value from
position – Position of the first byte in bytes

inline HashT(const std::array<uint8_t, SIZE> &bytes)#

Deserialises a Hash from an array of bytes.

Parameters:: bytes – Array to read the hash value from

inline size_t size() const#: The size of the hash (in number of bytes)

inline void zero()#: zeros out all bytes in the hash

inline size_t serialised_size() const#: The size of the serialisation of the hash (in number of bytes)

inline std::string to_string(size_t num_bytes = SIZE, bool lower_case = true) const#

Convert a hash to a hex-encoded string.

Parameters:

num_bytes – The maximum number of bytes to convert
lower_case – Enables lower-case hex characters

inline HashT<SIZE> operator=(const HashT<SIZE> &other)#: Hash assignment operator.

inline bool operator==(const HashT<SIZE> &other) const#: Hash equality operator.

inline bool operator!=(const HashT<SIZE> &other) const#: Hash inequality operator.

inline void serialise(std::vector<uint8_t> &buffer) const#

Serialises a hash.

Parameters:: buffer – Buffer to serialise to

inline void deserialise(const std::vector<uint8_t> &buffer, size_t &position)#

Deserialises a hash.

Parameters:

buffer – Buffer to read the hash from
position – Position of the first byte in bytes

inline void deserialise(const std::vector<uint8_t> &buffer)#

Deserialises a hash.

Parameters:: buffer – Buffer to read the hash from

inline operator std::vector<uint8_t>() const#: Conversion operator to vector of bytes.

Public Members

uint8_t bytes[SIZE]#: Holds the hash bytes.

Paths#

template<size_t HASH_SIZE, void HASH_FUNCTION> class PathT#

Template for Merkle paths.

Template Parameters:

HASH_SIZE – Size of each hash in number of bytes
HASH_FUNCTION – The hash function

Public Types

Direction = enum { PATH_LEFT, PATH_RIGHT }: Path direction.

Element = struct { HashT< HASH_SIZE > hash: Path element.

using const_iterator = typename std::list<Element>::const_iterator#: Iterator for path elements.

Public Functions

inline PathT(const HashT<HASH_SIZE> &leaf, size_t leaf_index, std::list<Element> &&elements, size_t max_index)#

Path constructor.

Parameters:

leaf –
leaf_index –
elements –
max_index –

PathT(const PathT &other) = default#

Path copy constructor.

Parameters:: other – Path to copy

PathT(PathT &&other) noexcept = default#

Path move constructor.

Parameters:: other – Path to move

inline PathT(const std::vector<uint8_t> &bytes)#

Deserialises a path.

Parameters:: bytes – Vector to deserialise from

inline PathT(const std::vector<uint8_t> &bytes, size_t &position)#

Deserialises a path.

Parameters:

bytes – Vector to deserialise from
position – Position of the first byte in bytes

inline std::shared_ptr<HashT<HASH_SIZE>> root() const#: Computes the root at the end of the path.

Note

This (re-)computes the root by hashing the path elements, it does not return a previously saved root hash.

inline bool verify(const HashT<HASH_SIZE> &expected_root) const#

Verifies that the root at the end of the path is expected.

Parameters:: expected_root – The root hash that the elements on the path are expected to hash to.

inline void serialise(std::vector<uint8_t> &bytes) const#

Serialises a path.

Parameters:: bytes – Vector of bytes to serialise to

inline void deserialise(const std::vector<uint8_t> &bytes, size_t &position)#

Deserialises a path.

Parameters:

bytes – Vector of bytes to serialise from
position – Position of the first byte in bytes

inline void deserialise(const std::vector<uint8_t> &bytes)#

Deserialises a path.

Parameters:: bytes – Vector of bytes to serialise from

inline operator std::vector<uint8_t>() const#: Conversion operator to vector of bytes.

inline size_t size() const#: The number of elements on the path.

inline size_t serialised_size() const#: The size of the serialised path in number of bytes.

inline size_t leaf_index() const#: Index of the leaf of the path.

inline size_t max_index() const#: Maximum index of the tree at the time the path was extracted.

inline const HashT<HASH_SIZE> &operator[](size_t i) const#

Operator to extract the hash of a given path element.

Parameters:: i – Index of the path element

inline const_iterator begin() const#: Start iterator for path elements.

inline const_iterator end() const#: End iterator for path elements.

inline std::string to_string(size_t num_bytes = HASH_SIZE, bool lower_case = true) const#

Convert a path to a string.

Parameters:

num_bytes – The maximum number of bytes to convert
lower_case – Enables lower-case hex characters

inline const HashT<HASH_SIZE> &leaf() const#: The leaf hash of the path.

inline bool operator==(const PathT<HASH_SIZE, HASH_FUNCTION> &other) const#: Equality operator for paths.

inline bool operator!=(const PathT<HASH_SIZE, HASH_FUNCTION> &other) const#: Inequality operator for paths.

Public Members

Direction direction#: The direction at which hash joins at this path element.

Note

If direction == PATH_LEFT, hash joins at the left, i.e. if t is the current hash, e.g. a leaf, then t’ = Hash( hash, t );

Hash functions#

By default, merklecpp uses the SHA256 compression function (merkle::sha256_compress()) for node hashes. For convenience, it also provides bindings to the SHA256 implementation in OpenSSL. To enable these bindings, merklecpp requires the compiler macro HAVE_OPENSSL to be defined.

static inline void merkle::sha256_compress(const HashT<32> &l, const HashT<32> &r, HashT<32> &out)#

SHA256 compression function for tree node hashes.

This function is the compression function of SHA256, which, for the special case of hashing two hashes, is more efficient than a full SHA256 while providing similar guarantees.

Parameters:

l – Left node hash
r – Right node hash
out – Output node hash

static inline void merkle::sha256_openssl(const merkle::HashT<32> &l, const merkle::HashT<32> &r, merkle::HashT<32> &out)#

OpenSSL SHA256.

Note

Some versions of OpenSSL may not provide SHA256_Transform.

Parameters:

l – Left node hash
r – Right node hash
out – Output node hash

merklecpp Documentation#

Trees#

Hashes#

Paths#

Hash functions#

Indices and tables#