docs: revise document of Merkle tree
Change-Id: I948dd0fb85d31d5fa92b6859bcfb41a697611021
diff --git a/docs/design-doc/fig/MerkleTreeLarge.png b/docs/design-doc/fig/MerkleTreeLarge.png
new file mode 100644
index 0000000..ef65549
--- /dev/null
+++ b/docs/design-doc/fig/MerkleTreeLarge.png
Binary files differ
diff --git a/docs/design-doc/merkle.rst b/docs/design-doc/merkle.rst
new file mode 100644
index 0000000..063b455
--- /dev/null
+++ b/docs/design-doc/merkle.rst
@@ -0,0 +1,165 @@
+=========================================
+Tamper-evident-Data-Structure-Merkle-Tree
+=========================================
+
+Overview
+---------------
+
+Merkle Tree is a data structure aiming to provide tamper-evident logging.
+This data structure maintains a tree structure, which merely uses its
+leaf nodes to store data,
+with internal nodes storing the iteratively cumulated hash value of
+the leaves.
+The hash value of the tree's root will serves as a certificate for the
+intactness of all the data in this tree.
+Thus, the Merkle Tree structure proves to be efficient in authenticating data's integrity.
+
+.. image:: fig/MerkleTreeLarge.png
+
+
+Modules Introduction
+-----------------------
+
++ **Node**: a class to manage the local information of each log, which
+ includes data, timestamp, hash value, sibling/child/parent node index.
+
++ **Mtree**: a class to maintain the core function of Merkle Tree, which involves the construction, reshape, add/set,
+ computeCommitment, findPath, generateProof, verifyConsistency, etc. function.
+
++ **Auditor**: a class to implement consistency verification.
+
+
+Data Structure Design
+--------------------------------
+
+*Index struct*
+~~~~~~~~~~~~~~~~~~~
+The index of nodes in the tree is defined as follows: For all nodes,
+the index is defined as a pair (number, level),
+where level denotes which level it belongs, and number denotes the
+smallest index of the leaf that belongs to its subtree.
+For leaf node, especially,
+idx is exactly the index of the leaf itself and lev equals to 0
+(both level and index starts from 0).
+
+*Leaf and Internal Nodes*
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
++ Node class member variable
+
++------------+-------------------------+-----------------------------------------------------------------------------+
+|Name | Type | Description |
++------------+-------------------------+-----------------------------------------------------------------------------+
+|hashValue | `ndn::ConstBufferPtr` | hash value of data |
++------------+-------------------------+-----------------------------------------------------------------------------+
+|m_index | `Index` | No. and level of the leaf |
++------------+-------------------------+-----------------------------------------------------------------------------+
+|m_timestamp | TBD | Not Added Yet.(Attribute: the maximum timestamp in the subtree of this node)|
++------------+-------------------------+-----------------------------------------------------------------------------+
+
++ Node class member function
+
++---------------+---------------------------------------------------------------------------------+
+|Name | Description |
++---------------+---------------------------------------------------------------------------------+
+|`getIndex()` | |
++---------------+---------------------------------------------------------------------------------+
+|`getTimestp()` | |
++---------------+---------------------------------------------------------------------------------+
+|`computeHash()`| compute the aggregation hash value of its children by invoking Hasher's function|
++---------------+---------------------------------------------------------------------------------+
+
++ Leaf-node subclass member variable
+
++------+-----------------------+---------------------+
+|Name | Type | Description |
++------+-----------------------+---------------------+
+|m_data| `ndn::ConstBufferPtr` |store raw data |
++------+-----------------------+---------------------+
+
+
++ Leaf-node subclass member function
+
++---------+--------------------+
+|Name | Description |
++---------+--------------------+
+|getData()|get the certificate |
++---------+--------------------+
+
++ Internal-node subclass member variable
+
++--------+---------+-----------------------------------------------------+
+|Name | Type | Description |
++--------+---------+-----------------------------------------------------+
+|m_isFull| `bool` | whether the leaves in the subtree all set with data |
++--------+---------+-----------------------------------------------------+
+
++ Internal-node subclass member function
+
++----------+-------------------------------------------+
+|Name | Description |
++----------+-------------------------------------------+
+|`isFull()`| judge whether the subtree is full of data |
++----------+-------------------------------------------+
+
+
+
+
+
+
+*Merkle Tree*
+~~~~~~~~~~~~~~~~~~~~~~~~~
+
++ MTree class member variable
+
++----------+--------------------+--------------------------------+
+|Name | Type | Description |
++----------+--------------------+--------------------------------+
+|tree |`map<Index, Node>` | Index contains all informations|
++----------+--------------------+--------------------------------+
+|treeLevel |`size_t` | height of the tree |
++----------+--------------------+--------------------------------+
+|leafNum |`size_t` | stored data item number |
++----------+--------------------+--------------------------------+
+
++ MTree class member function
+
++-----------------+---------------------------+----------------------+--------------------------------------------------+
+|Name | argument | return value | Description |
++-----------------+---------------------------+----------------------+--------------------------------------------------+
+|`getNode()` |`Index index` |`Node* node` | fetch node in the tree, given a index |
++-----------------+---------------------------+----------------------+--------------------------------------------------+
+|`getLevel()` | |`size_t level` | |
++-----------------+---------------------------+----------------------+--------------------------------------------------+
+|`getLeafNum()` | |`size_t leaf_num` | |
++-----------------+---------------------------+----------------------+--------------------------------------------------+
+|`addLeaf()` |`ndn::ConstBufferPtr info` | | add a info into the MTree (recalculate root hash |
+| | | | and update the tree info every time) |
++-----------------+---------------------------+----------------------+--------------------------------------------------+
+|`generateProof()`|`size_t version1, version2`| `vector<Node*> proof`|generate a pruned tree proof between version1 and |
+| | | |version2 |
++-----------------+---------------------------+----------------------+--------------------------------------------------+
+
+
+
+
+
+
+
+
+*Auditor*
+~~~~~~~~~~~~~~~~
+
++ Auditor class member function
+
++---------------------+----------------------------------------------------+---------------------+----------------------+
+|Name | argument | return value | Description |
++---------------------+----------------------------------------------------+---------------------+----------------------+
+|`verifyConsistency()`|`size_t version1, version2, size_t present_version, |`bool isConsistent` |verify whether the |
+| |ndn::ConstBufferPtr hash1, ndn::ConstBufferPtr hash2| |version1 and version2 |
+| |,std::vector<Node*> proof` | |are consistent |
++---------------------+----------------------------------------------------+---------------------+----------------------+
+|`queryByTime()` |`std::time_t` |`vector<Node*> nodes`|find nodes that |
+| | | |is generated later |
+| | | |later than given time |
++---------------------+----------------------------------------------------+---------------------+----------------------+
diff --git a/docs/design.rst b/docs/design.rst
new file mode 100644
index 0000000..dd11bb8
--- /dev/null
+++ b/docs/design.rst
@@ -0,0 +1,8 @@
+.. _design:
+
+NSL Design Document
+==============
+
+.. toctree::
+ design-doc/merkle
+ :maxdepth: 1
diff --git a/docs/index.rst b/docs/index.rst
index 8dbcefa..bc31c03 100644
--- a/docs/index.rst
+++ b/docs/index.rst
@@ -16,6 +16,7 @@
README
INSTALL
manpages
+ design
- :doc:`README`
@@ -23,6 +24,8 @@
- :doc:`manpages`
+- :doc:`design`
+
Documentation for ndn-cxx developers and contributors
+++++++++++++++++++++++++++++++++++++++++++++++++++++
