Gitiles
Code Review Sign In
gerrit.named-data.net / ndn-delorean / 883a787660dc04ef626645ac38fd6442d06807cf / . / docs / design-doc / merkle.rst
blob: 063b455efcf29fa013d63a03354f35b3a81ac6c4 [file] [log] [blame]
peizhen guo883a7872014-08-11 09:26:49 -0700[diff] [blame^]1=========================================
2Tamper-evident-Data-Structure-Merkle-Tree
3=========================================
4
5Overview
6---------------
7
8Merkle Tree is a data structure aiming to provide tamper-evident logging.
9This data structure maintains a tree structure, which merely uses its
10leaf nodes to store data,
11with internal nodes storing the iteratively cumulated hash value of
12the leaves.
13The hash value of the tree's root will serves as a certificate for the
14intactness of all the data in this tree.
15Thus, the Merkle Tree structure proves to be efficient in authenticating data's integrity.
16
17.. image:: fig/MerkleTreeLarge.png
18
19
20Modules Introduction
21-----------------------
22
23+ **Node**: a class to manage the local information of each log, which
24 includes data, timestamp, hash value, sibling/child/parent node index.
25
26+ **Mtree**: a class to maintain the core function of Merkle Tree, which involves the construction, reshape, add/set,
27 computeCommitment, findPath, generateProof, verifyConsistency, etc. function.
28
29+ **Auditor**: a class to implement consistency verification.
30
31
32Data Structure Design
33--------------------------------
34
35*Index struct*
36~~~~~~~~~~~~~~~~~~~
37The index of nodes in the tree is defined as follows: For all nodes,
38the index is defined as a pair (number, level),
39where level denotes which level it belongs, and number denotes the
40smallest index of the leaf that belongs to its subtree.
41For leaf node, especially,
42idx is exactly the index of the leaf itself and lev equals to 0
43(both level and index starts from 0).
44
45*Leaf and Internal Nodes*
46~~~~~~~~~~~~~~~~~~~~~~~~~~~~
47
48+ Node class member variable
49
50+------------+-------------------------+-----------------------------------------------------------------------------+
51|Name | Type | Description |
52+------------+-------------------------+-----------------------------------------------------------------------------+
53|hashValue | `ndn::ConstBufferPtr` | hash value of data |
54+------------+-------------------------+-----------------------------------------------------------------------------+
55|m_index | `Index` | No. and level of the leaf |
56+------------+-------------------------+-----------------------------------------------------------------------------+
57|m_timestamp | TBD | Not Added Yet.(Attribute: the maximum timestamp in the subtree of this node)|
58+------------+-------------------------+-----------------------------------------------------------------------------+
59
60+ Node class member function
61
62+---------------+---------------------------------------------------------------------------------+
63|Name | Description |
64+---------------+---------------------------------------------------------------------------------+
65|`getIndex()` | |
66+---------------+---------------------------------------------------------------------------------+
67|`getTimestp()` | |
68+---------------+---------------------------------------------------------------------------------+
69|`computeHash()`| compute the aggregation hash value of its children by invoking Hasher's function|
70+---------------+---------------------------------------------------------------------------------+
71
72+ Leaf-node subclass member variable
73
74+------+-----------------------+---------------------+
75|Name | Type | Description |
76+------+-----------------------+---------------------+
77|m_data| `ndn::ConstBufferPtr` |store raw data |
78+------+-----------------------+---------------------+
79
80
81+ Leaf-node subclass member function
82
83+---------+--------------------+
84|Name | Description |
85+---------+--------------------+
86|getData()|get the certificate |
87+---------+--------------------+
88
89+ Internal-node subclass member variable
90
91+--------+---------+-----------------------------------------------------+
92|Name | Type | Description |
93+--------+---------+-----------------------------------------------------+
94|m_isFull| `bool` | whether the leaves in the subtree all set with data |
95+--------+---------+-----------------------------------------------------+
96
97+ Internal-node subclass member function
98
99+----------+-------------------------------------------+
100|Name | Description |
101+----------+-------------------------------------------+
102|`isFull()`| judge whether the subtree is full of data |
103+----------+-------------------------------------------+
104
105
106
107
108
109
110*Merkle Tree*
111~~~~~~~~~~~~~~~~~~~~~~~~~
112
113+ MTree class member variable
114
115+----------+--------------------+--------------------------------+
116|Name | Type | Description |
117+----------+--------------------+--------------------------------+
118|tree |`map<Index, Node>` | Index contains all informations|
119+----------+--------------------+--------------------------------+
120|treeLevel |`size_t` | height of the tree |
121+----------+--------------------+--------------------------------+
122|leafNum |`size_t` | stored data item number |
123+----------+--------------------+--------------------------------+
124
125+ MTree class member function
126
127+-----------------+---------------------------+----------------------+--------------------------------------------------+
128|Name | argument | return value | Description |
129+-----------------+---------------------------+----------------------+--------------------------------------------------+
130|`getNode()` |`Index index` |`Node* node` | fetch node in the tree, given a index |
131+-----------------+---------------------------+----------------------+--------------------------------------------------+
132|`getLevel()` | |`size_t level` | |
133+-----------------+---------------------------+----------------------+--------------------------------------------------+
134|`getLeafNum()` | |`size_t leaf_num` | |
135+-----------------+---------------------------+----------------------+--------------------------------------------------+
136|`addLeaf()` |`ndn::ConstBufferPtr info` | | add a info into the MTree (recalculate root hash |
137| | | | and update the tree info every time) |
138+-----------------+---------------------------+----------------------+--------------------------------------------------+
139|`generateProof()`|`size_t version1, version2`| `vector<Node*> proof`|generate a pruned tree proof between version1 and |
140| | | |version2 |
141+-----------------+---------------------------+----------------------+--------------------------------------------------+
142
143
144
145
146
147
148
149
150*Auditor*
151~~~~~~~~~~~~~~~~
152
153+ Auditor class member function
154
155+---------------------+----------------------------------------------------+---------------------+----------------------+
156|Name | argument | return value | Description |
157+---------------------+----------------------------------------------------+---------------------+----------------------+
158|`verifyConsistency()`|`size_t version1, version2, size_t present_version, |`bool isConsistent` |verify whether the |
159| |ndn::ConstBufferPtr hash1, ndn::ConstBufferPtr hash2| |version1 and version2 |
160| |,std::vector<Node*> proof` | |are consistent |
161+---------------------+----------------------------------------------------+---------------------+----------------------+
162|`queryByTime()` |`std::time_t` |`vector<Node*> nodes`|find nodes that |
163| | | |is generated later |
164| | | |later than given time |
165+---------------------+----------------------------------------------------+---------------------+----------------------+