1Data Model
2==========
3
4This document establishes terminology shared throughout this repositotry around
5the structure and components of the Merkle tree.
6
7### Merkle tree
8
9In this repository, by Merkle trees we mean a slightly modified version of
10"history trees" introduced by Crosby and Wallach in the *Efficient Data
11Structures for Tamper-Evident Logging*
12[paper](https://static.usenix.org/event/sec09/tech/full_papers/crosby.pdf).
13
14
15
16The basis of the data structure is an append-only **log** consisting of log
17**entries**, numbered with consecutive integers starting from 0.
18
19Built on top of the log entries, there is a highly regular structure of nodes of
20a perfect binary tree-like shape. Nodes are addressed as `(level, index)` pairs.
21Nodes at level 0 are called **leaf nodes**, and correspond directly to the log
22entries. Nodes at higher levels are defined recursively based on nodes of the
23lower levels. Specifically, `(level, index)` depends directly on nodes
24`(level-1, index*2)` and `(level-1, index*2 + 1)`, and, recursively, nodes of
25its entire subtree.
26
27The data structure evolves dynamically. Initially, the log is empty, and all
28the nodes of the tree have no data. When new entries are appended to the log,
29nodes that recursively depend on these entries are updated. While the nodes can
30be updated, they are in **ephemeral** state. Eventually, when the log grows
31past a certain size, a node becomes **perfect**, and is never modified again.
32
33Effectively, perfect nodes are immutable / write-once registers, and ephemeral
34nodes are mutable.
35
36### Tree state
37
38
39
40To represent the state of the entire log, often a single ephemeral node is used
41which covers all the corresponding leaves. For example, in a tree with 21
42leaves, as in the picture above, this would be the ephemeral node 5.0.
43
44### TODO: Things to cover:
45
46- Append-only.
47- Merkle tree hasher.
48- Structured objects, like proofs and compact ranges.
View as plain text