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