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 built-in SHA256 function (merkle::sha256()). 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 std::optional<Hash> subtree_root(uint8_t level, size_t index)

Extracts the root hash of a complete subtree resident in memory.

Note

Like root() and path(), it may materialize pending nodes and compute dirty hashes, but does not change logical leaf contents or hashing semantics. It returns std::nullopt if any leaf of the subtree has been flushed, if the subtree extends past the last leaf, or if the node at that position is not a full subtree. The subtree spans leaf indices [index << level, (index + 1) << level).

Parameters:

• level – The height of the subtree (it spans 2**level leaves)

• index – The index of the subtree at that height

Returns:

The subtree root hash if the subtree is complete (balanced) and fully resident in memory; otherwise, std::nullopt

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.

Public Static Attributes

static constexpr auto hash_function = HASH_FUNCTION

Hash function used to combine tree nodes.

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>

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_bytes, bool lower_case = true) const

Convert a hash to a hex-encoded string.

Parameters:

• num_bytes – The number of bytes to convert

• lower_case – Enables lower-case hex characters

Throws:

std::out_of_range – if num_bytes exceeds the hash size

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.

Public Static Attributes

static constexpr size_t size_bytes = SIZE

Size of the hash in 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 its built-in SHA256 function (merkle::sha256()) for node hashes. For convenience, merklecpp 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(const HashT<32> &l, const HashT<32> &r, HashT<32> &out)

Built-in SHA256 function for tree node hashes.

Computes SHA256 over the 64-byte concatenation of l and r, including standard SHA256 message padding.

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.

Parameters:

• l – Left node hash

• r – Right node hash

• out – Output node hash

Indices and tables

• Index

• Search Page