# Glossary¶

The purpose of this section is to equip the reader with necessary background about the most common keywords and concepts used in the development of verifiable (or authenticated) data structures.

## Cryptographic primitives¶

Cryptographic hash functions and digital signatures are the fundamental building blocks for creating authenticated data structures.

### Hash functions¶

A cryptographic hash function compresses an arbitrary large message *m* into a
fixed size digest *h*. Due to the large space of messages mapped, collisions
are inevitable but they must be computationally hard to find. A cryptographic
hash function must conform with the following properties:

**Preimage resistance:**given a digest *h* <- H(*m*) for message*m*, it must be computationally hard to find a preimage*m’*generating*h*without knowledge of*m*.**Second preimage resistance:**given a fixed preimage*m*, it must be computationally hard to find another preimage*m’ != m*such that H(*m*) = H(*m’*).**Collision resistance:**it must be computationally hard to find any distinct preimages*m1*and*m2*such that H(*m1*) = H(*m2*).

## Digital signatures¶

A digital signature is a mathematical scheme for demonstrating the
*authenticity*, *non-repudiation* and *integrity* of a message. So a valid
digital signature gives a recipient a reason to believe that the message was
created by a known sender, that the sender cannot deny having sent the message
and that the message was not altered in transit.

## Tree-based data structures¶

A tree is an (un)ordered collection of entities, not necessarily unique, that
has a hierarchical parent-child relationship between pairs of entities. Every
tree has a single *root* node designating the start of the tree, and each
*descendant* is recursively defined as a tree. A node is said to be an
*ancestor* to all its descendants, and a parent to its concrete *children*.
All children that have the same parent are referred to as *siblings*, and
every node without children is referred to as a *leaf*. The root is said to be
found at *level* one, the *height *is the number of levels in the tree, and
the *depth* of a subtree rooted at a leaf is zero.

### Binary tree¶

A binary tree is a tree where each node is restricted to at most a *left
child* and a *right child*.

### Perfect binary tree¶

A binary tree of height *h* that must contain exactly 2^h - 1 nodes.

### Full binary tree¶

A binary tree which all nodes must have two or no children.

### Complete binary tree¶

A binary tree which must be filled left-to-right at the lowest level, and entirely at the level above.

## Merkle tree¶

A binary tree that stores values at the lowest level of the tree and uses cryptographic hash functions. While leaves compute the hash of their own attributes, parents derive the hash of their children’s hashes concatenated left-to-right. Therefore the hash rooted at a particular subtree is recursively dependent on all its descendants, effectively serving as a succinct summary for that subtree.

### Membership proof¶

A Merkle tree can prove values to be present by constructing efficient
*membership proofs*. Each proof must include a *Merkle audit path*, and it is
verified by recomputing all hashes, bottom up, from the leaf that the proof
concerns towards the root. The proof is believed to be valid if the recomputed
root hash matches that of the original Merkle tree, but to be convincing it
requires a trustworthy root (e.g., signed by a trusted party or published
periodically in a newspaper).

### Merkle audit path¶

A Merkle audit path for a leaf is the list of all additional nodes in the Merkle tree required to compute the Merkle Tree Hash for that tree. If the root computed from the audit path matches the true root, then the audit path is proof that the leaf exists in the tree.

## History tree¶

An append-only Merkle tree that stores *events* left-to-right at the lowest
level of the tree. It is not lexicographically sorted, and unable to generate
efficient non-membership proofs, but it is *naturally persistent*, supports
efficient membership proofs and allows to generate *incremental proofs*.

### Persistent nature¶

A history tree is naturally persistent, in the sense that past versions of the tree can be efficiently reconstructed and queried for membership.

### Incremental proof¶

A history tree can show consistency between root hashes for different views, and that requires proving all events in the earlier view present in the newer view. It is achieved by returning just enough information to reconstruct both root hashes checking if expected roots are obtained.

## Binary search tree¶

A binary tree that requires the value of each node to be greater (or lesser)
that the value of its left (or right) child. This property, referred to as the
*BST property*, implies a lexicographical order and allows every look-up
operation to use a divide-and-conquer technique known as *binary search*.
Because the time required to complete a binary search is bounded by the height
of the BST, it is important that the tree structure remains *balanced*.

## Heap¶

A specialized tree-based data structure used in the context of priority
queues. It associates each node a priority and preserves, at all times, two
properties: the *shape property*, requiring that the heap is a complete binary
tree; and the *heap property*, requiring that every node has a lower or equal
priority with respect to its parent.

## Treap¶

A randomized search tree associating with each entity a *key* and a randomly
selected priority. Treaps enforce the BST property with respect to keys, the
heap property with respect to priorities, and are also *set-unique*.
Set-uniqueness ensures the tree structures of identical collections to be
equivalent, thereby implying *history independence* if priorities are assigned
deterministically.

## Hash treap¶

A lexicographically sorted history independent key-value store combining a regular Merkle tree and a deterministic treap. Each node is associated with an entity and every (non-)member has a unique position, therefore hash treaps support efficient (non-)membership proofs.

## Sparse Merkle tree¶

A Merkle tree which depth is fixed in advance with respect to the underlying
hash function H, meaning there are always 2^|H(.)| leaves. These are referred
left-to-right by indices, and are associated with either *default* or
*non-default* values. In the latter case the hash of a key determines the
index, which implies there is a unique leaf reserved for every conceivable
digest H(*k*). This allows generation of (non-)membership proofs using regular
Merkle audit paths. The SMT is *sparse* because the large majority of all
leaves will be empty, and consequently most nodes rooted at lower levels of
the tree derive identical default hashes.