diff --git a/core/auditor.cpp b/core/auditor.cpp
index d0afa62..34f85d0 100644
--- a/core/auditor.cpp
+++ b/core/auditor.cpp
@@ -16,175 +16,225 @@
  * You should have received a copy of the GNU General Public License along with
  * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
  */
+
 #include "auditor.hpp"
 
+#include <ndn-cxx/util/digest.hpp>
+
 namespace nsl {
 
-ndn::ConstBufferPtr
-Auditor::computeHash(ndn::ConstBufferPtr hash_l, ndn::ConstBufferPtr hash_r)
+bool
+Auditor::doesExist(const NonNegativeInteger& seqNo,
+                   ndn::ConstBufferPtr hash,
+                   const NonNegativeInteger& rootNextSeqNo,
+                   ndn::ConstBufferPtr rootHash,
+                   const std::vector<shared_ptr<Data>>& proofs,
+                   const Name& loggerName)
 {
-  ndn::Buffer tmp_buf = *hash_l;
-  for (int i = 0; i < hash_r->size(); i++)
-    {
-      tmp_buf.push_back((*hash_r)[i]);
+  BOOST_ASSERT(rootHash != nullptr);
+  BOOST_ASSERT(hash != nullptr);
+
+  std::map<Node::Index, ConstSubTreeBinaryPtr> trees;
+
+  if (!loadProof(trees, proofs, loggerName))
+    return false;
+
+  // std::cerr << "Loaded" << std::endl;
+
+  size_t rootLevel = 0;
+  NonNegativeInteger tmpSeqNo = rootNextSeqNo - 1;
+  while (tmpSeqNo != 0) {
+    rootLevel++;
+    tmpSeqNo = tmpSeqNo >> 1;
+  }
+
+  if (rootLevel == 0) { // only one node
+    // std::cerr << "one level" << std::endl;
+    if (seqNo != 0)
+      return false;
+
+    auto it = trees.find(Node::Index(0, SubTreeBinary::SUB_TREE_DEPTH - 1));
+    if (it != trees.end()) {
+      // std::cerr << "find subtree" << std::endl;
+      auto node = it->second->getNode(Node::Index(0, 0));
+      if (node != nullptr && *node->getHash() == *hash && *hash == *rootHash)
+        return true;
+      else
+        return false;
     }
-  ndn::ConstBufferPtr digest = ndn::crypto::sha256(tmp_buf.buf(), tmp_buf.size());
-  return digest;
+    else
+      return false;
+  }
+
+
+  NonNegativeInteger childSeqMask = 1;
+  NonNegativeInteger childSeqNo = seqNo;
+  size_t childLevel = 0;
+  ndn::ConstBufferPtr childHash = hash;
+
+  NonNegativeInteger parentSeqMask = (~0) << 1;
+  NonNegativeInteger parentSeqNo = childSeqNo & parentSeqMask;
+  size_t parentLevel = 1;
+
+  Node::Index treePeakIndex(0, 0);
+  ConstSubTreeBinaryPtr subTree;
+
+  do { // get parent hash
+    Node::Index tmpIndex =
+      SubTreeBinary::toSubTreePeakIndex(Node::Index(childSeqNo, childLevel));
+
+    // std::cerr << "peak: " << tmpIndex.level << ", " << tmpIndex.seqNo << std::endl;
+    if (tmpIndex != treePeakIndex) {
+      treePeakIndex = tmpIndex;
+      auto it = trees.find(treePeakIndex);
+      if (it != trees.end() && it->second != nullptr) {
+        subTree = it->second;
+      }
+      else
+        return false;
+    }
+
+    // std::cerr << "Hey" << std::endl;
+    // right child or left child
+    ndn::util::Sha256 sha256;
+    if (childSeqMask & seqNo) { // right child
+      // std::cerr << "right" << std::endl;
+      // std::cerr << parentSeqNo << ", " << childLevel << std::endl;
+      auto leftChild = subTree->getNode(Node::Index(parentSeqNo, childLevel));
+      if (leftChild == nullptr && leftChild->getHash() == nullptr)
+        return false;
+
+      // std::cerr << "found node" << std::endl;
+      sha256 << parentLevel << parentSeqNo;
+      sha256.update(leftChild->getHash()->buf(), leftChild->getHash()->size());
+      sha256.update(childHash->buf(), childHash->size());
+    }
+    else { // left child
+      // std::cerr << "left" << std::endl;
+      ndn::ConstBufferPtr rightChildHash = Node::getEmptyHash();
+      if (rootNextSeqNo > childSeqNo + (1 << childLevel)) {
+        // std::cerr << childSeqNo + (1 << childLevel) << ", " << childLevel << std::endl;
+        auto rightChild = subTree->getNode(Node::Index(childSeqNo + (1 << childLevel), childLevel));
+        if (rightChild == nullptr || rightChild->getHash() == nullptr)
+          return false;
+        rightChildHash = rightChild->getHash();
+        // std::cerr << "left done" << std::endl;
+      }
+
+      sha256 << parentLevel << parentSeqNo;
+      sha256.update(childHash->buf(), childHash->size());
+      sha256.update(rightChildHash->buf(), rightChildHash->size());
+    }
+
+    childSeqMask = childSeqMask << 1;
+    childSeqNo = parentSeqNo;
+    childLevel = parentLevel;
+    childHash = sha256.computeDigest();
+
+    parentSeqMask = parentSeqMask << 1;
+    parentSeqNo = childSeqNo & parentSeqMask;
+    parentLevel++;
+
+  } while (childLevel < rootLevel);
+
+  // std::cerr << "done" << std::endl;
+
+  return (*childHash == *rootHash);
 }
 
-
-
-
-
-ndn::ConstBufferPtr
-Auditor::computeHashOneSide(ndn::ConstBufferPtr hash_l)
-{
-  ndn::ConstBufferPtr digest = ndn::crypto::sha256(hash_l->buf(), hash_l->size());
-  return digest;
-}
-
-
-
-
-
-
 bool
-Auditor::verifyConsistency(uint64_t version1, uint64_t version2, ndn::ConstBufferPtr hash1,
-                           ndn::ConstBufferPtr hash2, std::vector<ConstNodePtr> proof)
+Auditor::isConsistent(const NonNegativeInteger& oldRootNextSeqNo,
+                      ndn::ConstBufferPtr oldRootHash,
+                      const NonNegativeInteger& newRootNextSeqNo,
+                      ndn::ConstBufferPtr newRootHash,
+                      const std::vector<shared_ptr<Data>>& proofs,
+                      const Name& loggerName)
 {
-  // find version2's level
-  uint64_t levelVer2 = 1;
-  uint64_t ver2 = version2;
-  while(ver2 >= 1)
-    {
-      ver2 = ver2 / 2;
-      levelVer2 += 1;
-    }
+  BOOST_ASSERT(oldRootHash != nullptr);
+  BOOST_ASSERT(newRootHash != nullptr);
 
-  // compare version2's hash
-  ndn::ConstBufferPtr hash_l;
-  ndn::ConstBufferPtr hash_r;
-  ndn::ConstBufferPtr tmp_hash;
-  Index tmp_idx = proof[0]->getIndex();
-  int isRight = tmp_idx.number % int(pow(2, tmp_idx.level + 1));
-  if (isRight != 0)
-    hash_r = proof[0]->getHash();
-  else
-    hash_l = proof[0]->getHash();
-  uint64_t i_ = 1;
-  for (; tmp_idx.level < levelVer2 - 1; )
-    {
-      if (isRight != 0)
-        {
-          hash_l = proof[i_]->getHash();
-          tmp_hash = computeHash(hash_l, hash_r);
-          i_++;
-        }
-      else
-        {
-          tmp_hash = computeHashOneSide(hash_l);
-        }
-      tmp_idx.level += 1;
-      tmp_idx.number -= tmp_idx.number % int(pow(2, tmp_idx.level));
-      isRight = tmp_idx.number % int(pow(2, tmp_idx.level + 1));
-      if (isRight != 0)
-        {
-          hash_r = tmp_hash;
-        }
-      else
-        {
-          hash_l = tmp_hash;
-        }
-    }
-  bool hash2_consis = true;
-  if (isRight != 0)
-    {
-      for (int i = 0; i < hash_r->size() ; i++)
-        {
-          if ((*hash2)[i] != (*hash_r)[i])
-            {
-              hash2_consis = false;
-              break;
-            }
-        }
-    }
-  else
-    {
-      for (int i = 0; i < hash_l->size() ; i++)
-        {
-          if ((*hash2)[i] != (*hash_l)[i])
-            {
-              hash2_consis = false;
-              break;
-            }
-        }
-    }
+  if (oldRootNextSeqNo > newRootNextSeqNo)
+    return false;
 
+  std::map<Node::Index, ConstSubTreeBinaryPtr> trees;
+  if (!loadProof(trees, proofs, loggerName))
+    return false;
 
+  // std::cerr << "1" << std::endl;
 
+  // get boundary leaf:
+  NonNegativeInteger leafSeqNo = oldRootNextSeqNo - 1;
+  NonNegativeInteger treeSeqNo = leafSeqNo & ((~0) << (SubTreeBinary::SUB_TREE_DEPTH - 1));
+  auto it = trees.find(Node::Index(treeSeqNo, SubTreeBinary::SUB_TREE_DEPTH - 1));
+  if (it == trees.end())
+    return false;
 
-  // compare hash1
-  tmp_idx = proof[i_]->getIndex();
-  isRight = tmp_idx.number % int(pow(2, tmp_idx.level + 1));
-  if (isRight != 0)
-    hash_r = proof[i_]->getHash();
-  else
-    hash_l = proof[i_]->getHash();
-  i_++;
-  for (; i_ < proof.size(); )
-    {
-      if (isRight != 0)
-        {
-          hash_l = proof[i_]->getHash();
-          tmp_hash = computeHash(hash_l, hash_r);
-          i_++;
-        }
-      else
-        {
-          tmp_hash = computeHashOneSide(hash_l);
-        }
-      tmp_idx.level += 1;
-      tmp_idx.number -= tmp_idx.number % int(pow(2, tmp_idx.level));
-      isRight = tmp_idx.number % int(pow(2, tmp_idx.level + 1));
-      if (isRight != 0)
-        {
-          hash_r = tmp_hash;
-        }
-      else
-        {
-          hash_l = tmp_hash;
-        }
-    }
+  auto leaf = it->second->getNode(Node::Index(leafSeqNo, 0));
+  if (leaf == nullptr || leaf->getHash() == nullptr)
+    return false;
 
-  bool hash1_consis = true;
-  if (isRight != 0)
-    {
-      for (int i = 0; i < hash_r->size() ; i++)
-        {
-          if ((*hash1)[i] != (*hash_r)[i])
-            {
-              hash1_consis = false;
-              break;
-            }
-        }
-    }
-  else
-    {
-      for (int i = 0; i < hash_l->size() ; i++)
-        {
-          if ((*hash1)[i] != (*hash_l)[i])
-            {
-              hash1_consis = false;
-              break;
-            }
-        }
-    }
+  if (!doesExist(leafSeqNo, leaf->getHash(), oldRootNextSeqNo, oldRootHash,
+                 proofs, loggerName))
+    return false;
 
-  return hash1_consis && hash2_consis;
+  // std::cerr << "2" << std::endl;
 
+  if (oldRootNextSeqNo == newRootNextSeqNo) {
+    if (*oldRootHash == *newRootHash)
+      return true;
+    else
+      return false;
+  }
+
+  // std::cerr << "3" << std::endl;
+
+  if (!doesExist(leafSeqNo, leaf->getHash(), newRootNextSeqNo, newRootHash,
+                 proofs, loggerName))
+    return false;
+
+  // std::cerr << "4" << std::endl;
+
+  return true;
 }
 
+bool
+Auditor::loadProof(std::map<Node::Index, ConstSubTreeBinaryPtr>& trees,
+                   const std::vector<shared_ptr<Data>>& proofs,
+                   const Name& loggerName)
+{
+  try {
+    for (auto proof : proofs) {
+      // std::cerr << proof->getName() << std::endl;
+      auto subtree =
+        make_shared<SubTreeBinary>(loggerName,
+                                   [] (const Node::Index& idx) {},
+                                   [] (const Node::Index&,
+                                       const NonNegativeInteger& seqNo,
+                                       ndn::ConstBufferPtr hash) {});
+      subtree->decode(*proof);
+
+      // std::cerr << subtree->getPeakIndex().level << ", " << subtree->getPeakIndex().seqNo << std::endl;
+      if (trees.find(subtree->getPeakIndex()) == trees.end())
+        trees[subtree->getPeakIndex()] = subtree;
+      else
+        return false;
+    }
+  }
+  catch (SubTreeBinary::Error& e) {
+    // std::cerr << e.what() << std::endl;
+    return false;
+  }
+  catch (Node::Error& e) {
+    // std::cerr << e.what() << std::endl;
+    return false;
+  }
+  catch (tlv::Error&) {
+    return false;
+  }
+
+  return true;
+}
 
 } // namespace nsl
diff --git a/core/auditor.hpp b/core/auditor.hpp
index 8f2919a..9117d5d 100644
--- a/core/auditor.hpp
+++ b/core/auditor.hpp
@@ -16,59 +16,47 @@
  * You should have received a copy of the GNU General Public License along with
  * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
  */
-#ifndef NLS_CORE_AUDITOR_HPP
-#define NLS_CORE_AUDITOR_HPP
 
-#include <string>
+#ifndef NSL_CORE_AUDITOR_HPP
+#define NSL_CORE_AUDITOR_HPP
+
+#include "common.hpp"
+#include "node.hpp"
+#include "sub-tree-binary.hpp"
+#include "util/non-negative-integer.hpp"
+#include <ndn-cxx/encoding/buffer.hpp>
 #include <vector>
 
-#include <math.h>
-#include <stdint.h>
-
-#include <ndn-cxx/util/crypto.hpp>
-
-#include "node.hpp"
-
 namespace nsl {
 
-typedef ndn::shared_ptr<const Node> ConstNodePtr;
-typedef ndn::shared_ptr<Node> NodePtr;
-
 class Auditor
 {
 public:
-  Auditor()
-  {
-  }
+  static bool
+  doesExist(const NonNegativeInteger& seqNo,
+            ndn::ConstBufferPtr hash,
+            const NonNegativeInteger& rootNextSeqNo,
+            ndn::ConstBufferPtr rootHash,
+            const std::vector<shared_ptr<Data>>& proofs,
+            const Name& loggerName);
 
+  static bool
+  isConsistent(const NonNegativeInteger& seqNo,
+               ndn::ConstBufferPtr hash,
+               const NonNegativeInteger& rootNextSeqNo,
+               ndn::ConstBufferPtr rootHash,
+               const std::vector<shared_ptr<Data>>& proofs,
+               const Name& loggerName);
 
-  ~Auditor()
-  {
-  }
-
-
-  bool
-  verifyConsistency(uint64_t version1, uint64_t version2, ndn::ConstBufferPtr hash1,
-                    ndn::ConstBufferPtr hash2, std::vector<ConstNodePtr> proof);
-
-
-  std::vector<Node*>
-  queryByTime(time_t);
-
-  ndn::ConstBufferPtr
-  computeHash(ndn::ConstBufferPtr hash_l, ndn::ConstBufferPtr hash_r);
-
-
-  ndn::ConstBufferPtr
-  computeHashOneSide(ndn::ConstBufferPtr hash_l);
-
-
-private:
-
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+  static bool
+  loadProof(std::map<Node::Index, ConstSubTreeBinaryPtr>& trees,
+            const std::vector<shared_ptr<Data>>& proofs,
+            const Name& loggerName);
 };
 
 } // namespace nsl
 
-#endif // NLS_CORE_AUDITOR_HPP
+#endif // NSL_CORE_AUDITOR_HPP
diff --git a/core/db.cpp b/core/db.cpp
new file mode 100644
index 0000000..22361c5
--- /dev/null
+++ b/core/db.cpp
@@ -0,0 +1,309 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014,  Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "db.hpp"
+
+#include <sqlite3.h>
+#include <string>
+#include <boost/filesystem.hpp>
+
+namespace nsl {
+
+static const std::string INITIALIZATION =
+  "CREATE TABLE IF NOT EXISTS                    \n"
+  "  cTrees(                                     \n"
+  "    id                    INTEGER PRIMARY KEY,\n"
+  "    level                 INTEGER NOT NULL,   \n"
+  "    seqNo                 INTEGER NOT NULL,   \n"
+  "    data                  BLOB NOT NULL       \n"
+  "  );                                          \n"
+  "CREATE UNIQUE INDEX IF NOT EXISTS             \n"
+  "  cTreeIndex ON cTrees(level, seqNo);         \n"
+  "CREATE TRIGGER IF NOT EXISTS                  \n"
+  "  cTrees_after_insert_trigger                 \n"
+  "  AFTER INSERT ON cTrees                      \n"
+  "  FOR EACH ROW                                \n"
+  "  BEGIN                                       \n"
+  "    DELETE FROM pTrees                        \n"
+  "    WHERE level=NEW.level AND seqNo=NEW.seqNo;\n"
+  "  END;                                        \n"
+  "                                              \n"
+  "CREATE TABLE IF NOT EXISTS                    \n"
+  "  pTrees(                                     \n"
+  "    id                    INTEGER PRIMARY KEY,\n"
+  "    level                 INTEGER NOT NULL,   \n"
+  "    seqNo                 INTEGER NOT NULL,   \n"
+  "    nextLeafSeqNo         INTEGER NOT NULL,   \n"
+  "    data                  BLOB NOT NULL       \n"
+  "  );                                          \n"
+  "CREATE UNIQUE INDEX IF NOT EXISTS             \n"
+  "  pTreeIndex ON pTrees(level, seqNo);         \n"
+  "                                              \n"
+  "CREATE TABLE IF NOT EXISTS                    \n"
+  "  leaves(                                     \n"
+  "    id                    INTEGER PRIMARY KEY,\n"
+  "    dataSeqNo             INTEGER NOT NULL,   \n"
+  "    dataName              BLOB NOT NULL,      \n"
+  "    signerSeqNo           INTEGER NOT NULL,   \n"
+  "    timestamp             INTEGER NOT NULL,   \n"
+  "    isCert                INTEGER DEFAULT 0,  \n"
+  "    cert                  BLOB                \n"
+  "  );                                          \n"
+  "CREATE UNIQUE INDEX IF NOT EXISTS             \n"
+  "  leavesIndex ON leaves(dataSeqNo);           \n";
+
+
+/**
+ * A utility function to call the normal sqlite3_bind_blob where the value and length are
+ * block.wire() and block.size().
+ */
+static int
+sqlite3_bind_block(sqlite3_stmt* statement,
+                   int index,
+                   const Block& block,
+                   void(*destructor)(void*))
+{
+  return sqlite3_bind_blob(statement, index, block.wire(), block.size(), destructor);
+}
+
+/**
+ * A utility function to generate block by calling the normal sqlite3_column_text.
+ */
+static Block
+sqlite3_column_block(sqlite3_stmt* statement, int column)
+{
+  return Block(sqlite3_column_blob(statement, column), sqlite3_column_bytes(statement, column));
+}
+
+void
+Db::open(const std::string& dbDir)
+{
+  // Determine the path of logger database
+  if (dbDir == "")
+    throw Error("Db: empty db path");
+
+  boost::filesystem::path dir = boost::filesystem::path(dbDir);
+  boost::filesystem::create_directories(dir);
+
+  // Open database
+  int result = sqlite3_open_v2((dir / "sig-logger.db").c_str(), &m_db,
+                               SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE,
+#ifdef NSL_DISABLE_SQLITE3_FS_LOCKING
+                               "unix-dotfile"
+#else
+                               nullptr
+#endif
+                               );
+
+  if (result != SQLITE_OK)
+    throw Error("SigLogger DB cannot be opened/created: " + dbDir);
+
+  // initialize SigLogger specific tables
+  char* errorMessage = nullptr;
+  result = sqlite3_exec(m_db, INITIALIZATION.c_str(), nullptr, nullptr, &errorMessage);
+  if (result != SQLITE_OK && errorMessage != nullptr) {
+    sqlite3_free(errorMessage);
+    throw Error("SigLogger DB cannot be initialized");
+  }
+
+  getMaxLeafSeq();
+}
+
+bool
+Db::insertSubTreeData(size_t level, const NonNegativeInteger& seqNo,
+                      const Data& data,
+                      bool isFull, const NonNegativeInteger& nextLeafSeqNo)
+{
+  sqlite3_stmt* statement;
+  if (isFull) {
+    sqlite3_prepare_v2(m_db,
+                       "INSERT INTO cTrees (level, seqNo, data) VALUES (?, ?, ?)",
+                       -1, &statement, nullptr);
+  }
+  else {
+    sqlite3_prepare_v2(m_db,
+                       "INSERT OR REPLACE INTO pTrees (level, seqNo, data, nextLeafSeqNo)\
+                        VALUES (?, ?, ?, ?)",
+                       -1, &statement, nullptr);
+  }
+  sqlite3_bind_int(statement, 1, level);
+  sqlite3_bind_int(statement, 2, seqNo);
+  sqlite3_bind_block(statement, 3, data.wireEncode(), SQLITE_TRANSIENT);
+  if (!isFull)
+    sqlite3_bind_int(statement, 4, nextLeafSeqNo);
+
+  int result = sqlite3_step(statement);
+  sqlite3_finalize(statement);
+
+  if (result == SQLITE_OK)
+    return true;
+  return false;
+}
+
+shared_ptr<Data>
+Db::getSubTreeData(size_t level, const NonNegativeInteger& seqNo)
+{
+  sqlite3_stmt* statement;
+  sqlite3_prepare_v2(m_db,
+                     "SELECT data FROM cTrees WHERE level=? AND seqNo=?",
+                     -1, &statement, nullptr);
+  sqlite3_bind_int(statement, 1, level);
+  sqlite3_bind_int(statement, 2, seqNo);
+
+  if (sqlite3_step(statement) == SQLITE_ROW) {
+    auto result = make_shared<Data>(sqlite3_column_block(statement, 0));
+    sqlite3_finalize(statement);
+    return result;
+  }
+
+  sqlite3_prepare_v2(m_db,
+                     "SELECT data FROM pTrees WHERE level=? AND seqNo=?",
+                     -1, &statement, nullptr);
+  sqlite3_bind_int(statement, 1, level);
+  sqlite3_bind_int(statement, 2, seqNo);
+
+  shared_ptr<Data> result;
+  if (sqlite3_step(statement) == SQLITE_ROW)
+    result = make_shared<Data>(sqlite3_column_block(statement, 0));
+
+  sqlite3_finalize(statement);
+  return result;
+}
+
+std::vector<shared_ptr<Data>>
+Db::getPendingSubTrees()
+{
+  sqlite3_stmt* statement;
+  sqlite3_prepare_v2(m_db,
+                     "SELECT data FROM pTrees ORDER BY level DESC",
+                     -1, &statement, nullptr);
+
+  std::vector<shared_ptr<Data>> datas;
+  while (sqlite3_step(statement) == SQLITE_ROW)
+    datas.push_back(make_shared<Data>(sqlite3_column_block(statement, 0)));
+
+  sqlite3_finalize(statement);
+  return datas;
+}
+
+bool
+Db::insertLeafData(const Leaf& leaf)
+{
+  if (leaf.getDataSeqNo() != m_nextLeafSeqNo)
+    return false;
+
+  sqlite3_stmt* statement;
+  sqlite3_prepare_v2(m_db,
+                     "INSERT INTO leaves (dataSeqNo, dataName, signerSeqNo, timestamp, isCert)\
+                      VALUES (?, ?, ?, ?, 0)",
+                     -1, &statement, nullptr);
+
+  sqlite3_bind_int(statement, 1, leaf.getDataSeqNo());
+  sqlite3_bind_block(statement, 2, leaf.getDataName().wireEncode(), SQLITE_TRANSIENT);
+  sqlite3_bind_int(statement, 3, leaf.getSignerSeqNo());
+  sqlite3_bind_int(statement, 4, leaf.getTimestamp());
+
+  int result = sqlite3_step(statement);
+  sqlite3_finalize(statement);
+
+  if (result == SQLITE_OK || result == SQLITE_DONE) {
+    m_nextLeafSeqNo++;
+    return true;
+  }
+
+  return false;
+}
+
+bool
+Db::insertLeafData(const Leaf& leaf, const Data& data)
+{
+  if (leaf.getDataSeqNo() != m_nextLeafSeqNo)
+    return false;
+
+  sqlite3_stmt* statement;
+  sqlite3_prepare_v2(m_db,
+                     "INSERT INTO leaves (dataSeqNo, dataName, signerSeqNo, timestamp, isCert, cert)\
+                      VALUES (?, ?, ?, ?, 1, ?)",
+                     -1, &statement, nullptr);
+
+  sqlite3_bind_int(statement, 1, leaf.getDataSeqNo());
+  sqlite3_bind_block(statement, 2, leaf.getDataName().wireEncode(), SQLITE_TRANSIENT);
+  sqlite3_bind_int(statement, 3, leaf.getSignerSeqNo());
+  sqlite3_bind_int(statement, 4, leaf.getTimestamp());
+  sqlite3_bind_block(statement, 5, data.wireEncode(), SQLITE_TRANSIENT);
+
+  int result = sqlite3_step(statement);
+  sqlite3_finalize(statement);
+
+  if (result == SQLITE_OK || result == SQLITE_DONE) {
+    m_nextLeafSeqNo++;
+    return true;
+  }
+
+  return false;
+}
+
+std::pair<shared_ptr<Leaf>, shared_ptr<Data>>
+Db::getLeaf(const NonNegativeInteger& seqNo)
+{
+  sqlite3_stmt* statement;
+  sqlite3_prepare_v2(m_db,
+                     "SELECT dataName, signerSeqNo, timestamp, cert\
+                      FROM leaves WHERE dataSeqNo=?",
+                     -1, &statement, nullptr);
+
+  sqlite3_bind_int(statement, 1, seqNo);
+
+  if (sqlite3_step(statement) == SQLITE_ROW) {
+    auto leaf = make_shared<Leaf>(Name(sqlite3_column_block(statement, 0)),
+                                  sqlite3_column_int(statement, 2),
+                                  seqNo,
+                                  sqlite3_column_int(statement, 1));
+
+    shared_ptr<Data> data;
+    if (sqlite3_column_bytes(statement, 3) != 0) {
+      data = make_shared<Data>(sqlite3_column_block(statement, 3));
+    }
+    sqlite3_finalize(statement);
+    return std::make_pair(leaf, data);
+  }
+  else {
+    sqlite3_finalize(statement);
+    return std::make_pair(nullptr, nullptr);
+  }
+}
+
+const NonNegativeInteger&
+Db::getMaxLeafSeq()
+{
+  sqlite3_stmt* statement;
+
+  sqlite3_prepare_v2(m_db, "SELECT count(dataSeqNo) FROM leaves", -1, &statement, nullptr);
+  if (sqlite3_step(statement) == SQLITE_ROW)
+    m_nextLeafSeqNo = sqlite3_column_int(statement, 0);
+  else
+    throw Error("getMaxLeafSeq: db error");
+
+  sqlite3_finalize(statement);
+  return m_nextLeafSeqNo;
+}
+
+} // namespace nsl
diff --git a/core/db.hpp b/core/db.hpp
new file mode 100644
index 0000000..503b562
--- /dev/null
+++ b/core/db.hpp
@@ -0,0 +1,84 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014,  Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#ifndef NSL_CORE_DB_HPP
+#define NSL_CORE_DB_HPP
+
+#include "common.hpp"
+#include "leaf.hpp"
+#include "util/non-negative-integer.hpp"
+#include <vector>
+
+struct sqlite3;
+
+namespace nsl {
+
+class Db : noncopyable
+{
+public:
+  class Error : public std::runtime_error
+  {
+  public:
+    explicit
+    Error(const std::string& what)
+      : std::runtime_error(what)
+    {
+    }
+  };
+
+public:
+  void
+  open(const std::string& dbDir);
+
+  bool
+  insertSubTreeData(size_t level, const NonNegativeInteger& seqNo,
+                    const Data& data,
+                    bool isFull = true,
+                    const NonNegativeInteger& nextLeafSeqNo = 0);
+
+  shared_ptr<Data>
+  getSubTreeData(size_t level, const NonNegativeInteger& seqNo);
+
+  std::vector<shared_ptr<Data>>
+  getPendingSubTrees();
+
+  bool
+  insertLeafData(const Leaf& leaf);
+
+  bool
+  insertLeafData(const Leaf& leaf, const Data& data);
+
+  std::pair<shared_ptr<Leaf>, shared_ptr<Data>>
+  getLeaf(const NonNegativeInteger& seqNo);
+
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+  const NonNegativeInteger&
+  getMaxLeafSeq();
+
+private:
+  sqlite3* m_db;
+
+  NonNegativeInteger m_nextLeafSeqNo;
+};
+
+} // namespace nsl
+
+#endif // NSL_CORE_DB_HPP
diff --git a/core/intermediate-node.cpp b/core/intermediate-node.cpp
deleted file mode 100644
index 11c37ff..0000000
--- a/core/intermediate-node.cpp
+++ /dev/null
@@ -1,72 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014,  Regents of the University of California
- *
- * This file is part of NSL (NDN Signature Logger).
- * See AUTHORS.md for complete list of NSL authors and contributors.
- *
- * NSL is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
- */
-#include "intermediate-node.hpp"
-
-namespace nsl {
-
-bool
-IntermediateNode::isFull() const
-{
-  return m_isFull;
-}
-
-
-
-bool
-IntermediateNode::setIsFull(uint64_t number)
-{
-  Index info = this->getIndex();
-  uint64_t num = info.number;
-  uint64_t lev = info.level;
-  if (double(num) + pow(2, lev) <= number)
-    {
-      m_isFull = true;
-      return m_isFull;
-    }
-  else
-    {
-      m_isFull = false;
-      return m_isFull;
-    }
-
-}
-
-
-
-void
-IntermediateNode::computeHash(ndn::ConstBufferPtr hash_l, ndn::ConstBufferPtr hash_r)
-{
-  ndn::Buffer tmp_buf = *hash_l;
-  for (int i = 0; i < hash_r->size(); i++)
-    {
-      tmp_buf.push_back((*hash_r)[i]);
-    }
-  ndn::ConstBufferPtr digest = ndn::crypto::sha256(tmp_buf.buf(), tmp_buf.size());
-  this->setHash(digest);
-}
-
-void IntermediateNode::computeHashOneSide(ndn::ConstBufferPtr hash_l)
-{
-  ndn::ConstBufferPtr digest = ndn::crypto::sha256(hash_l->buf(), hash_l->size());
-  this->setHash(digest);
-}
-
-} // namespace nsl
diff --git a/core/intermediate-node.hpp b/core/intermediate-node.hpp
deleted file mode 100644
index c2c3c0b..0000000
--- a/core/intermediate-node.hpp
+++ /dev/null
@@ -1,76 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014,  Regents of the University of California
- *
- * This file is part of NSL (NDN Signature Logger).
- * See AUTHORS.md for complete list of NSL authors and contributors.
- *
- * NSL is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
- */
-#ifndef NLS_CORE_INTERMEDIATE_NODE_HPP
-#define NLS_CORE_INTERMEDIATE_NODE_HPP
-
-#include <stddef.h>
-#include <math.h>
-#include <ndn-cxx/util/crypto.hpp>
-#include "node.hpp"
-
-
-namespace nsl {
-
-
-class IntermediateNode : public Node
-{
-public:
-
-  IntermediateNode()
-    : Node()
-  {
-  }
-
-  IntermediateNode(uint64_t sequenceNumber, uint64_t level, time_t timestamp)
-    : Node(sequenceNumber, level, timestamp), m_isFull(false)
-  {
-  }
-
-  IntermediateNode(const IntermediateNode& new_node)
-    :Node(new_node.getIndex().number, new_node.getIndex().level, 0)
-  {
-    m_isFull = new_node.isFull();
-    this->setHash(new_node.getHash());
-  }
-
-  ~IntermediateNode()
-  {
-  }
-
-  bool
-  setIsFull(uint64_t totalLeafNum);
-
-  bool
-  isFull() const;
-
-  void
-  computeHash(ndn::ConstBufferPtr hash_l, ndn::ConstBufferPtr hash_r);
-
-  void
-  computeHashOneSide(ndn::ConstBufferPtr hash_l);
-
-private:
-  bool m_isFull;
-};
-
-} // namespace nsl
-
-#endif // NLS_CORE_INTERMEDIATE_NODE_HPP
diff --git a/core/leaf.cpp b/core/leaf.cpp
index 33ee527..e862d37 100644
--- a/core/leaf.cpp
+++ b/core/leaf.cpp
@@ -16,25 +16,239 @@
  * You should have received a copy of the GNU General Public License along with
  * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
  */
+
 #include "leaf.hpp"
+#include "tlv.hpp"
+#include <ndn-cxx/security/digest-sha256.hpp>
+#include <ndn-cxx/encoding/block-helpers.hpp>
+#include <ndn-cxx/util/crypto.hpp>
 
-namespace nsl{
+namespace nsl {
 
-ndn::ConstBufferPtr
-Leaf::getData() const
+const Name Leaf::EMPTY_NAME;
+const size_t Leaf::N_LOGGER_LEAF_SUFFIX = 4;
+const ssize_t Leaf::OFFSET_LEAF_SEQNO = -2;
+const ssize_t Leaf::OFFSET_LEAF_HASH = -1;
+
+Leaf::Leaf()
 {
-  return m_data;
 }
 
-
+Leaf::Leaf(const Name& dataName,
+       const Timestamp& timestamp,
+       const NonNegativeInteger& dataSeqNo,
+       const NonNegativeInteger& signerSeqNo,
+       const Name& loggerName)
+  : m_dataName(dataName)
+  , m_timestamp(timestamp)
+  , m_dataSeqNo(dataSeqNo)
+  , m_signerSeqNo(signerSeqNo)
+  , m_loggerName(loggerName)
+{
+  if (m_dataSeqNo < m_signerSeqNo)
+    throw Error("Leaf: signer seqNo should be less than the data seqNo");
+}
 
 void
-Leaf::computeHash()
+Leaf::setDataSeqNo(const NonNegativeInteger& dataSeqNo)
 {
-  ndn::ConstBufferPtr digest = ndn::crypto::sha256(m_data->buf(), m_data->size());
-  this->setHash(digest);
+  if (dataSeqNo < m_signerSeqNo)
+    throw Error("Leaf: signer seqNo should be less than the data seqNo");
+
+  m_wire.reset();
+  m_dataSeqNo = dataSeqNo;
+}
+
+void
+Leaf::setDataName(const Name& dataName)
+{
+  m_wire.reset();
+  m_dataName = dataName;
+}
+
+void
+Leaf::setTimestamp(const Timestamp& timestamp)
+{
+  m_wire.reset();
+  m_timestamp = timestamp;
+}
+
+void
+Leaf::setSignerSeqNo(const NonNegativeInteger& signerSeqNo)
+{
+  if (m_dataSeqNo < signerSeqNo)
+    throw Error("Leaf: signer seqNo should be less than the data seqNo");
+
+  m_wire.reset();
+  m_signerSeqNo = signerSeqNo;
+}
+
+void
+Leaf::setLoggerName(const Name& loggerName)
+{
+  m_loggerName = loggerName;
+}
+
+ndn::ConstBufferPtr
+Leaf::getHash() const
+{
+  wireEncode();
+  return ndn::crypto::sha256(m_wire.wire(), m_wire.size());
+}
+
+shared_ptr<Data>
+Leaf::encode() const
+{
+  auto data = make_shared<Data>();
+
+  ndn::ConstBufferPtr hash = getHash();
+
+  // Name
+  Name dataName = m_loggerName;
+  dataName.appendNumber(m_dataSeqNo).append(hash->buf(), hash->size());
+  data->setName(dataName);
+
+  // Content
+  data->setContent(wireEncode());
+
+  // Signature
+  ndn::DigestSha256 sig;
+  data->setSignature(sig);
+
+  Block sigValue(tlv::SignatureValue,
+                 ndn::crypto::sha256(data->wireEncode().value(),
+                                     data->wireEncode().value_size() -
+                                     data->getSignature().getValue().size()));
+  data->setSignatureValue(sigValue);
+
+  data->wireEncode();
+
+  return data;
+}
+
+void
+Leaf::decode(const Data& data)
+{
+  const Name& dataName = data.getName();
+
+  if (!m_loggerName.isPrefixOf(dataName))
+    throw Error("decode: leaf data name does not match logger name");
+
+  if (m_loggerName.size() + N_LOGGER_LEAF_SUFFIX != dataName.size())
+    throw Error("decode: leaf data name does not follow the naming convention");
+
+  ndn::ConstBufferPtr leafHash;
+  NonNegativeInteger dataSeqNo;
+  try {
+    leafHash = make_shared<ndn::Buffer>(dataName.get(OFFSET_LEAF_HASH).value(),
+                                        dataName.get(OFFSET_LEAF_HASH).value_size());
+
+    dataSeqNo = dataName.get(OFFSET_LEAF_SEQNO).toNumber();
+  }
+  catch (tlv::Error&) {
+    throw Error("decode: logger name encoding error");
+  }
+
+  wireDecode(data.getContent().blockFromValue());
+
+  if (*leafHash != *getHash())
+    throw Error("decode: inconsistent hash");
+
+  if (m_dataSeqNo != dataSeqNo)
+    throw Error("decode: seqNo does not match");
+}
+
+template<ndn::encoding::Tag TAG>
+size_t
+Leaf::wireEncode(ndn::EncodingImpl<TAG>& block) const
+{
+  size_t totalLength = 0;
+
+  totalLength += ndn::prependNonNegativeIntegerBlock(block, tlv::SignerSeqNo, m_signerSeqNo);
+  totalLength += ndn::prependNonNegativeIntegerBlock(block, tlv::DataSeqNo, m_dataSeqNo);
+  totalLength += ndn::prependNonNegativeIntegerBlock(block, tlv::Timestamp, m_timestamp);
+  totalLength += m_dataName.wireEncode(block);
+
+  totalLength += block.prependVarNumber(totalLength);
+  totalLength += block.prependVarNumber(tlv::LoggerLeaf);
+
+  return totalLength;
+}
+
+template size_t
+Leaf::wireEncode<ndn::encoding::EncoderTag>(ndn::EncodingImpl<ndn::encoding::EncoderTag>&) const;
+
+template size_t
+Leaf::wireEncode<ndn::encoding::EstimatorTag>(ndn::EncodingImpl<ndn::encoding::EstimatorTag>&) const;
+
+
+const Block&
+Leaf::wireEncode() const
+{
+  if (m_wire.hasWire())
+    return m_wire;
+
+  ndn::EncodingEstimator estimator;
+  size_t estimatedSize = wireEncode(estimator);
+
+  ndn::EncodingBuffer buffer(estimatedSize, 0);
+  wireEncode(buffer);
+
+  m_wire = buffer.block();
+  return m_wire;
+}
+
+void
+Leaf::wireDecode(const Block& wire)
+{
+  if (!wire.hasWire()) {
+    throw Error("The supplied block does not contain wire format");
+  }
+
+  m_wire = wire;
+  m_wire.parse();
+
+  if (m_wire.type() != tlv::LoggerLeaf)
+    throw tlv::Error("Unexpected TLV type when decoding logger leaf");
+
+  Block::element_const_iterator it = m_wire.elements_begin();
+
+  // the first block must be dataName
+  if (it != m_wire.elements_end() && it->type() == tlv::Name) {
+    m_dataName.wireDecode(*it);
+    it++;
+  }
+  else
+    throw Error("The first sub-TLV is not Name");
+
+  // the second block must be timestamp
+  if (it != m_wire.elements_end() && it->type() == tlv::Timestamp) {
+    m_timestamp = readNonNegativeInteger(*it);
+    it++;
+  }
+  else
+    throw Error("The second sub-TLV is not Timestamp");
+
+  // the third block must be DataSeqNo
+  if (it != m_wire.elements_end() && it->type() == tlv::DataSeqNo) {
+    m_dataSeqNo = readNonNegativeInteger(*it);
+    it++;
+  }
+  else
+    throw Error("The third sub-TLV is not DataSeqNo");
+
+  // the third block must be SignerSeqNo
+  if (it != m_wire.elements_end() && it->type() == tlv::SignerSeqNo) {
+    m_signerSeqNo = readNonNegativeInteger(*it);
+    it++;
+  }
+  else
+    throw Error("The fourth sub-TLV is not SignerSeqNo");
+
+  if (it != m_wire.elements_end())
+    throw Error("No more sub-TLV in LoggerLeaf");
 }
 
 } // namespace nsl
diff --git a/core/leaf.hpp b/core/leaf.hpp
index 9576c09..3f8b0a5 100644
--- a/core/leaf.hpp
+++ b/core/leaf.hpp
@@ -16,56 +16,128 @@
  * You should have received a copy of the GNU General Public License along with
  * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
  */
-#ifndef NLS_CORE_LEAF_HPP
-#define NLS_CORE_LEAF_HPP
 
-#include <vector>
-#include <ndn-cxx/util/crypto.hpp>
-#include "node.hpp"
+#ifndef NSL_CORE_LEAF_HPP
+#define NSL_CORE_LEAF_HPP
+
+#include "common.hpp"
+#include "util/non-negative-integer.hpp"
+#include "util/timestamp.hpp"
+#include <ndn-cxx/encoding/buffer.hpp>
 
 namespace nsl {
 
-class Leaf : public Node
+class Leaf
 {
 public:
-
-  Leaf()
-    : Node()
+  class Error : public std::runtime_error
   {
+  public:
+    explicit
+    Error(const std::string& what)
+      : std::runtime_error(what)
+    {
+    }
+  };
+
+public:
+  Leaf();
+
+  Leaf(const Name& dataName,
+       const Timestamp& timestamp,
+       const NonNegativeInteger& leafSeqNo,
+       const NonNegativeInteger& signerSeqNo,
+       const Name& loggerName = EMPTY_NAME);
+
+  void
+  setDataSeqNo(const NonNegativeInteger& dataSeqNo);
+
+  const NonNegativeInteger&
+  getDataSeqNo() const
+  {
+    return m_dataSeqNo;
   }
 
+  void
+  setDataName(const Name& dataName);
 
-  Leaf(ndn::ConstBufferPtr data, uint64_t sequenceNumber, uint64_t level, time_t timestamp)
-    : Node(sequenceNumber, level, timestamp), m_data(data)
+  const Name&
+  getDataName() const
   {
+    return m_dataName;
   }
 
+  void
+  setTimestamp(const Timestamp& timestamp);
 
-  Leaf(const Leaf& new_leaf)
-    : Node(new_leaf.getIndex().number, new_leaf.getIndex().level, new_leaf.getTimestamp())
+  const Timestamp&
+  getTimestamp() const
   {
-    m_data = new_leaf.getData();
-    this->setHash(new_leaf.getHash());
+    return m_timestamp;
   }
 
+  void
+  setSignerSeqNo(const NonNegativeInteger& signerSeqNo);
 
-  ~Leaf()
+  const NonNegativeInteger&
+  getSignerSeqNo() const
   {
+    return m_signerSeqNo;
+  }
+
+  void
+  setLoggerName(const Name& loggerName);
+
+  const Name&
+  getLoggerName() const
+  {
+    return m_loggerName;
   }
 
   ndn::ConstBufferPtr
-  getData() const;
+  getHash() const;
 
+  shared_ptr<Data>
+  encode() const;
 
   void
-  computeHash();
+  decode(const Data& data);
+
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+  /// @brief Encode to a wire format or estimate wire format
+  template<ndn::encoding::Tag TAG>
+  size_t
+  wireEncode(ndn::EncodingImpl<TAG>& block) const;
+
+  /// @brief Encode to a wire format
+  const Block&
+  wireEncode() const;
+
+  /// @brief Decode from a wire format
+  void
+  wireDecode(const Block& wire);
+
+public:
+  static const Name EMPTY_NAME;
+
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+  static const size_t N_LOGGER_LEAF_SUFFIX;
+  static const ssize_t OFFSET_LEAF_SEQNO;
+  static const ssize_t OFFSET_LEAF_HASH;
 
 private:
-  ndn::ConstBufferPtr m_data;
+  Name m_dataName;
+  Timestamp m_timestamp;
+  NonNegativeInteger m_dataSeqNo;
+  NonNegativeInteger m_signerSeqNo;
+
+  mutable Block m_wire;
+
+  Name m_loggerName;
 };
 
 } // namespace nsl
 
-#endif // NLS_CORE_LEAF_HPP
+#endif // NSL_CORE_LEAF_HPP
diff --git a/core/merkle-tree-cache.cpp b/core/merkle-tree-cache.cpp
deleted file mode 100644
index a7f2dc0..0000000
--- a/core/merkle-tree-cache.cpp
+++ /dev/null
@@ -1,353 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014,  Regents of the University of California
- *
- * This file is part of NSL (NDN Signature Logger).
- * See AUTHORS.md for complete list of NSL authors and contributors.
- *
- * NSL is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
- */
-
-#include "merkle-tree-cache.hpp"
-
-
-
-namespace nsl {
-
-typedef std::map<Index, int>::iterator tree_iter;
-typedef std::map<uint64_t, ndn::ConstBufferPtr>::iterator leaf_iter;
-
-Index
-MerkleTreeCache::findSubTree(Index nodeIndex)
-{
-  if(nodeIndex.level % 6 == 0 && nodeIndex.level != 0)
-    {
-      return nodeIndex;
-    }
-  else
-    {
-      uint8_t step = (uint64_t(nodeIndex.level / 6) + 1) * 6 - nodeIndex.level;
-      for (int i = 0; i < step; i++)
-        {
-          nodeIndex.number -= nodeIndex.number % int(pow(2, nodeIndex.level + 1));
-          nodeIndex.level += 1;
-        }
-      return nodeIndex;
-    }
-}
-
-Index
-MerkleTreeCache::getParentRootIndex(Index thisRootIndex)
-{
-  Index parentIndex;
-  parentIndex.number = thisRootIndex.number;
-  parentIndex.level = thisRootIndex.level;
-  for (int i = 0; i < 6; i++)
-    {
-      parentIndex.number -= parentIndex.number%int(pow(2, parentIndex.level + 1));
-      parentIndex.level += 1;
-    }
-  return parentIndex;
-}
-
-
-void
-MerkleTreeCache::removeSubTree()
-{
-  if (doesCacheFull() > 1)
-    {
-      // find out the least recent used subtree
-      tree_iter _i = m_timeFromLastUse.begin();
-      int idle_time_max = -1;
-      Index rm_index_max = _i->first;
-      int idle_time_min = _i->second;
-      Index rm_index_min = _i->first;
-      for (_i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
-        {
-          if (_i->second > idle_time_max && m_cachedTree[_i->first]->getRemainPosition() == 0)
-            {
-              idle_time_max = _i->second;
-              rm_index_max = _i->first;
-            }
-          if (_i->second < idle_time_min)
-            {
-              idle_time_min = _i->second;
-              rm_index_min = _i->first;
-            }
-        }
-
-      // refresh the timer
-      for (_i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
-        {
-          _i->second -= idle_time_min;
-        }
-      // update to database and remove subtree from cache and timer,only when there is full subtree
-      if (m_cachedTree[rm_index_max]->getRemainPosition() == 0 && idle_time_max >= 0)
-        {
-          m_database.addSubTree(m_cachedTree[rm_index_max]);
-          m_cachedTree.erase(rm_index_max);
-          m_timeFromLastUse.erase(rm_index_max);
-        }
-    }
-}
-
-void
-MerkleTreeCache::removeLeaf()
-{
-  if (doesCacheFull() % 2 != 0)
-    {
-      // randomly pick a old leaf to remove
-      leaf_iter _i = m_leavesData.begin();
-      while (_i->first == m_nLeaves - 1)
-        {
-          _i++;
-        }
-      m_database.addLeafInfo(_i->first, _i->second);
-      m_leavesData.erase(_i->first);
-    }
-}
-
-
-
-
-
-// Do not have to deal with NOT-IN-MEMORY issue because not full tree will not in database
-void
-MerkleTreeCache::addLeaf(Leaf newLeaf)
-{
-  ndn::ConstBufferPtr data = newLeaf.getData();
-  removeLeaf(); // test whether is full, if so, delete an old item
-  m_leavesData[newLeaf.getIndex().number] = data;
-  Index leafIndex = newLeaf.getIndex();
-  ndn::ConstBufferPtr hash = newLeaf.getHash();
-
-  Index subTreeRoot = findSubTree(leafIndex);
-  if (m_nLeaves > 0)
-    {
-      // Not full so that always in memory
-      m_cachedTree[subTreeRoot]->addNode(hash);
-      m_nLeaves += 1;
-    }
-  else
-    {
-      SubTreePtr newTree(new SubTree(subTreeRoot,
-                                     ndn::bind(&MerkleTreeCache::update, this,
-                                               subTreeRoot, _1, _2)));
-      newTree->addNode(hash);
-      removeSubTree();
-      m_cachedTree[subTreeRoot] = newTree;
-      m_nLeaves = 1;
-      m_nLevels = 1;
-    }
-
-  for (tree_iter _i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
-    {
-      _i->second += 1;
-    }
-  m_timeFromLastUse[subTreeRoot] = 0; // if not exist, automatically create one and set to 0
-}
-
-
-// Deal with loading from database
-// database update
-// consider add to database when a subtree is full
-void
-MerkleTreeCache::update(Index subRootIndex, uint8_t subRemainNum, ndn::ConstBufferPtr subRootHash)
-{
-  if ((subRootIndex.level / 6) < m_nLevels)
-    {
-      Index parentRoot = getParentRootIndex(subRootIndex);
-
-      // bring in memory if parentRoot not in
-      if (m_cachedTree.count(parentRoot) <= 0)
-        {
-          loadSubTreeFromDatabase(parentRoot);
-        }
-      m_cachedTree[parentRoot]->updateLeafHash(subRootIndex, subRootHash);
-      m_timeFromLastUse[parentRoot] = 0;
-    }
-
-  if (subRemainNum == 0) // add the current full subtree into the database
-    {
-      Index parentRoot = getParentRootIndex(subRootIndex);
-      if ((subRootIndex.level / 6) >= m_nLevels) // if it is the top subtree
-        {
-          SubTreePtr newTree(new SubTree(parentRoot,
-                                         ndn::bind(&MerkleTreeCache::update, this,
-                                                   parentRoot, _1, _2)));
-          removeSubTree();
-          m_cachedTree[parentRoot] = newTree;
-          m_nLevels += 1;
-          m_timeFromLastUse[parentRoot] = 0;
-          m_cachedTree[parentRoot]->updateLeafHash(subRootIndex, subRootHash);
-        }
-      Index newRoot;
-      newRoot.level = subRootIndex.level;
-      newRoot.number = subRootIndex.number + int(pow(2, subRootIndex.level));
-      // whether the updated subtree is already full,
-      // but its child subtree is not full.
-      // To avoid create multiple sibling new subtree
-      if (m_cachedTree.count(newRoot) == 0)
-        {
-          SubTreePtr newTree(new SubTree(newRoot,
-                                         ndn::bind(&MerkleTreeCache::update, this,
-                                                   newRoot, _1, _2)));
-          removeSubTree();
-          m_cachedTree[newRoot] = newTree;
-          m_timeFromLastUse[newRoot] = 0;
-        }
-    }
-}
-
-
-NodePtr
-MerkleTreeCache::queryNode(Index nodeIndex)
-{
-  // update timer
-  for (tree_iter _i = m_timeFromLastUse.begin(); _i != m_timeFromLastUse.end(); _i++)
-    {
-      _i->second += 1;
-    }
-
-  Index rootIndex = findSubTree(nodeIndex);
-  ndn::ConstBufferPtr hash;
-  if (m_cachedTree.count(rootIndex) == 0)
-    {
-      loadSubTreeFromDatabase(rootIndex);
-    }
-  hash = m_cachedTree[rootIndex]->getHash(nodeIndex);
-
-  if (nodeIndex.level == 0)
-    {
-      if (m_leavesData.count(nodeIndex.number) == 0)
-        {
-          loadLeafFromDatabase(nodeIndex.number);
-        }
-      NodePtr node_ptr(new Leaf(m_leavesData[nodeIndex.number],
-                                nodeIndex.number, nodeIndex.level, 0));
-      node_ptr->setHash(hash);
-      return node_ptr;
-    }
-  else
-    {
-      NodePtr node_ptr(new IntermediateNode(nodeIndex.number, nodeIndex.level, 0));
-      node_ptr->setHash(hash);
-      ((IntermediateNode*)node_ptr.get())->setIsFull(m_nLeaves);
-      return node_ptr;
-    }
-}
-
-
-bool
-MerkleTreeCache::doesNodeExist(Index nodeIndex)
-{
-  Index rootIndex = findSubTree(nodeIndex);
-  if (m_cachedTree.count(rootIndex) > 0)
-    {
-      return true;
-    }
-  else
-    {
-      bool result = m_database.doesSubTreeExist(rootIndex);
-      return result;
-    }
-}
-
-
-
-SubTreePtr
-MerkleTreeCache::decoding(std::string subTreeInfo)
-{
-  uint64_t seq = 0;
-  unsigned char tmp = 0;
-  for (int i = 7; i >= 0; i--)
-    {
-      tmp = subTreeInfo[i];
-      seq += tmp;
-      seq = seq << 8;
-    }
-  seq = seq >> 8;
-  uint64_t lev = 0;
-  for (int i = 15; i >= 8; i--)
-    {
-      tmp = subTreeInfo[i];
-      lev += tmp;
-      lev = lev << 8;
-    }
-  lev = lev >> 8;
-  Index rootIndex;
-  rootIndex.number = seq;
-  rootIndex.level = lev;
-  SubTreePtr newTree(new SubTree(rootIndex,
-                                 ndn::bind(&MerkleTreeCache::update, this,
-                                           rootIndex, _1, _2)));
-  uint8_t remain = subTreeInfo[16]; // not useful
-  if (remain == 0)
-    {
-      std::vector<ndn::BufferPtr> hashes;
-      for (int i = 0; i < 127; i++)
-        {
-          ndn::Buffer buf;
-          for(int j = 17 + 32 * i; j < 49 + 32 * i; j++)
-            {
-              buf.push_back(subTreeInfo[j]);
-            }
-          ndn::BufferPtr thisBuf = ndn::make_shared<ndn::Buffer>(buf);
-          hashes.push_back(thisBuf);
-        }
-      newTree->resumeFromString(remain, hashes);
-      return newTree;
-    }
-  else
-    {
-      std::vector<ndn::BufferPtr> hashes;
-      uint8_t lastNo = 126 - remain;
-      for (int i = 63; i <= lastNo; i++)
-        {
-          ndn::Buffer buf;
-          for(int j = 17 + 32 * i; j < 49 + 32 * i; j++)
-            {
-              buf.push_back(subTreeInfo[j]);
-            }
-          ndn::BufferPtr thisBuf = ndn::make_shared<ndn::Buffer>(buf);
-          hashes.push_back(thisBuf);
-        }
-      newTree->resumeFromString(remain, hashes);
-      return newTree;
-    }
-}
-
-
-void
-MerkleTreeCache::loadSubTreeFromDatabase(Index rootIndex)
-{
-  // Detect the cache limitation
-  removeSubTree();
-  std::string tmp_str = m_database.getSubTree(rootIndex);
-  SubTreePtr newtree = decoding(tmp_str);
-  m_cachedTree[rootIndex] = newtree;
-  m_timeFromLastUse[rootIndex] = 0;
-}
-
-void
-MerkleTreeCache::loadLeafFromDatabase(uint64_t sequence)
-{
-  // Detect the cache limitation
-  removeLeaf();
-  ndn::ConstBufferPtr newleaf = m_database.getLeafInfo(sequence);
-  m_leavesData[sequence] = newleaf;
-}
-
-
-} // namespace nsl
diff --git a/core/merkle-tree-cache.hpp b/core/merkle-tree-cache.hpp
deleted file mode 100644
index 97e8908..0000000
--- a/core/merkle-tree-cache.hpp
+++ /dev/null
@@ -1,176 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014,  Regents of the University of California
- *
- * This file is part of NSL (NDN Signature Logger).
- * See AUTHORS.md for complete list of NSL authors and contributors.
- *
- * NSL is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
- */
-#ifndef NLS_CORE_MERKLE_TREE_CACHE_HPP
-#define NLS_CORE_MERKLE_TREE_CACHE_HPP
-
-#include <map>
-#include <vector>
-
-#include "sub-tree.hpp"
-#include "leaf.hpp"
-#include "intermediate-node.hpp"
-#include "merkle-tree-sqlite3.hpp"
-
-
-namespace nsl {
-
-
-typedef ndn::shared_ptr<const SubTree> ConstSubTreePtr;
-typedef ndn::shared_ptr<SubTree> SubTreePtr;
-typedef ndn::shared_ptr<const Node> ConstNodePtr;
-typedef ndn::shared_ptr<Node> NodePtr;
-
-class MerkleTreeCache
-{
-public:
-
-  MerkleTreeCache()
-    :m_nLevels(0),
-     m_nLeaves(0)
-  {
-  }
-
-  ~MerkleTreeCache()
-  {
-  }
-
-  uint8_t
-  getLevel()
-  {
-    return m_nLevels;
-  }
-
-  uint64_t
-  getLeaves()
-  {
-    return m_nLeaves;
-  }
-
-  SubTreePtr
-  getSubTree(Index rootIndex)
-  {
-    if (m_cachedTree.count(rootIndex) > 0)
-      {
-        //std::cout<<"I'm here!"<<int(m_cachedTree[rootIndex]->getRemainPosition())<<std::endl;
-        return m_cachedTree[rootIndex];
-      }
-    else
-      {
-        std::string treeString = m_database.getSubTree(rootIndex);
-        SubTreePtr newtree = decoding(treeString);
-        return newtree;
-      }
-  }
-
-  // Do the update when a subtree is full
-  // Iteratively: find parent --> check full --> ... --> if not full -->
-  // create subtree --> create subsubtree --> ... --> until down to the leaf
-  // invoke a subtree.updateHash(), and decide whether to add new subtrees according to the callback
-  // remainPosition value.
-  void
-  update(Index subRootIndex, uint8_t subRemainNum, ndn::ConstBufferPtr subRootHash);
-
-  void
-  addLeaf(Leaf newLeaf);
-
-  NodePtr
-  queryNode(Index nodeIndex);
-
-  bool
-  doesNodeExist(Index nodeIndex);
-
-  void
-  loadSubTreeFromDatabase(Index rootIndex);
-
-  void
-  loadLeafFromDatabase(uint64_t sequence);
-
-
-
-  SubTreePtr
-  decoding(std::string subTreeInfo);
-
-  // remove the comment to test sqlite3 function
-  // MerkleTreeSqlite3 m_database;
-
-  // To show the exact size of the cache
-  // std::map<Index, SubTreePtr> m_cachedTree;
-  // std::map<uint64_t, ndn::ConstBufferPtr> m_leavesData;
-
-
-private:
-
-  // find which subTree the node belongs to (not include root node)
-  Index
-  findSubTree(Index nodeIndex);
-
-  // find a subTree's parent root index
-  Index
-  getParentRootIndex(Index thisRootIndex);
-
-
-  // To be finished
-  uint8_t
-  doesCacheFull()
-  {
-    if (m_cachedTree.size() >= 3 && m_leavesData.size() >= 64)
-      {
-        return 3;
-      }
-    else if (m_cachedTree.size() >= 3 && m_leavesData.size() < 64)
-      {
-        return 2;
-      }
-    else if (m_cachedTree.size() < 3 && m_leavesData.size() >= 64)
-      {
-        return 1;
-      }
-    else
-      {
-        return 0;
-      }
-  }
-
-  // choose a cache item to remove,
-  // exactly remove items from cache only when: 1)have full subtrees 2)cache is full
-  void
-  removeSubTree();
-
-  void
-  removeLeaf();
-
-private:
-  // partly in cache, completely in db
-  std::map<Index, SubTreePtr> m_cachedTree;
-  std::map<uint64_t, ndn::ConstBufferPtr> m_leavesData; //starts from 0(same as leaf)
-
-  // completely in memory, add & delete with time
-  std::map<Index, int> m_timeFromLastUse;
-  uint8_t m_nLevels; // levels counted based on subtree unit
-  uint64_t m_nLeaves; // sequence number + 1
-
-  // sqlite3 database
-  MerkleTreeSqlite3 m_database;
-};
-
-} // namespace nsl
-
-#endif // NLS_CORE_MERKLE_TREE_CACHE_HPP
diff --git a/core/merkle-tree-sqlite3.cpp b/core/merkle-tree-sqlite3.cpp
deleted file mode 100644
index 1844ad4..0000000
--- a/core/merkle-tree-sqlite3.cpp
+++ /dev/null
@@ -1,332 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014,  Regents of the University of California
- *
- * This file is part of NSL (NDN Signature Logger).
- * See AUTHORS.md for complete list of NSL authors and contributors.
- *
- * NSL is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
- */
-
-#include "merkle-tree-sqlite3.hpp"
-#include <stdlib.h>
-#include <boost/filesystem.hpp>
-
-
-namespace nsl {
-
-static const std::string INIT_SUBTREE_TABLE = "\
-CREATE TABLE IF NOT EXISTS                                           \n \
-  SubTree(                                                           \n \
-      subTree_sequence     INTEGER,                                  \n \
-      subTree_level        INTEGER,                                  \n \
-      subTree_info         BLOB,                                     \n \
-                                                                     \
-      PRIMARY KEY (subTree_sequence, subTree_level)                  \n \
-  );                                                                 \n \
-                                                                     \
-CREATE INDEX subTree_index ON SubTree(subTree_sequence);             \n \
-";
-
-static const std::string INIT_LEAF_TABLE = "\
-CREATE TABLE IF NOT EXISTS                                           \n \
-  Leaf(                                                              \n \
-      leaf_sequence     INTEGER,                                     \n \
-      leaf_info         BLOB,                                        \n \
-                                                                     \
-      PRIMARY KEY (leaf_sequence)                                    \n \
-  );                                                                 \n \
-                                                                     \
-CREATE INDEX leaf_index ON Leaf(leaf_sequence);                      \n \
-";
-
-/**
- * A utility function to call the normal sqlite3_bind_text where the value and length are
- * value.c_str() and value.size().
- */
-static int sqlite3_bind_text(sqlite3_stmt* statement,
-                             int index,
-                             const std::string& value,
-                             void(*destructor)(void*))
-{
-  return sqlite3_bind_text(statement, index, value.c_str(), value.size(), destructor);
-}
-
-
-MerkleTreeSqlite3::MerkleTreeSqlite3()
-{
-  boost::filesystem::path identityDir = boost::filesystem::path("/Users/GPZ/Develop/nslDB");
-  boost::filesystem::create_directories(identityDir);
-
-  /// @todo Add define for windows/unix in wscript. The following may completely fail on windows
-  int res = sqlite3_open_v2((identityDir / "nsl-merkle-tree.db").c_str(), &m_database,
-                            SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE,
-#ifdef NDN_CXX_DISABLE_SQLITE3_FS_LOCKING
-                            "unix-dotfile"
-#else
-                            0
-#endif
-                            );
-
-  if (res != SQLITE_OK)
-    std::cout << "DB cannot be opened/created";
-
-  //Check if SubTree table exists;
-  sqlite3_stmt* statement;
-  sqlite3_prepare_v2(m_database,
-                     "SELECT name FROM sqlite_master WHERE type='table' And name='SubTree'",
-                     -1, &statement, 0);
-  res = sqlite3_step(statement);
-
-  bool SubTreeTableExists = false;
-  if (res == SQLITE_ROW)
-    SubTreeTableExists = true;
-
-  sqlite3_finalize(statement);
-
-  if (!SubTreeTableExists)
-    {
-      char* errorMessage = 0;
-      res = sqlite3_exec(m_database, INIT_SUBTREE_TABLE.c_str(), NULL, NULL, &errorMessage);
-
-      if (res != SQLITE_OK && errorMessage != 0)
-        {
-          sqlite3_free(errorMessage);
-        }
-    }
-
-  //Check if Leaf table exists;
-  sqlite3_prepare_v2(m_database,
-                     "SELECT name FROM sqlite_master WHERE type='table' And name='Leaf'",
-                     -1, &statement, 0);
-  res = sqlite3_step(statement);
-
-  bool LeafTableExists = false;
-  if (res == SQLITE_ROW)
-    LeafTableExists = true;
-
-  sqlite3_finalize(statement);
-
-  if (!LeafTableExists)
-    {
-      char* errorMessage = 0;
-      res = sqlite3_exec(m_database, INIT_LEAF_TABLE.c_str(), NULL, NULL, &errorMessage);
-
-      if (res != SQLITE_OK && errorMessage != 0)
-        {
-          sqlite3_free(errorMessage);
-        }
-    }
-
-}
-
-
-MerkleTreeSqlite3::~MerkleTreeSqlite3()
-{
-}
-
-
-void
-MerkleTreeSqlite3::addSubTree(SubTreePtr oldSubTree)
-{
-  Index old_idx = oldSubTree->getRootIndex();
-  std::string old_info = oldSubTree->encoding();
-
-  sqlite3_stmt* statement;
-  sqlite3_prepare_v2(m_database,
-                     "INSERT OR REPLACE INTO SubTree \
-                      (subTree_sequence, subTree_level, subTree_info)   \
-                      values (?, ?, ?)",
-                     -1, &statement, 0);
-  sqlite3_bind_int64(statement, 1, old_idx.number);
-  sqlite3_bind_int64(statement, 2, old_idx.level);
-  sqlite3_bind_text(statement, 3, old_info, SQLITE_TRANSIENT);
-  sqlite3_step(statement);
-  sqlite3_finalize(statement);
-}
-
-
-std::string
-MerkleTreeSqlite3::getSubTree(Index rootIndex)
-{
-  sqlite3_stmt* statement;
-  sqlite3_prepare_v2(m_database,
-                     "SELECT subTree_info FROM SubTree \
-                      WHERE subTree_sequence=? AND subTree_level=?",
-                     -1, &statement, 0);
-  sqlite3_bind_int64(statement, 1, rootIndex.number);
-  sqlite3_bind_int64(statement, 2, rootIndex.level);
-  int res = sqlite3_step(statement);
-  std::string result;
-  if (res == SQLITE_ROW)
-    {
-      result = std::string(reinterpret_cast<const char *>(sqlite3_column_text(statement, 0)),
-                           sqlite3_column_bytes(statement, 0));
-      sqlite3_finalize(statement);
-      return result;
-    }
-  else
-    {
-      sqlite3_finalize(statement);
-      return result;
-    }
-}
-
-
-bool
-MerkleTreeSqlite3::doesSubTreeExist(Index rootIndex)
-{
-  bool result = false;
-  sqlite3_stmt* statement;
-  sqlite3_prepare_v2(m_database,
-                     "SELECT count(*) FROM SubTree WHERE subTree_sequence=? AND subTree_level=?",
-                     -1, &statement, 0);
-  sqlite3_bind_int64(statement, 1, rootIndex.number);
-  sqlite3_bind_int64(statement, 2, rootIndex.level);
-  int res = sqlite3_step(statement);
-  if (res == SQLITE_ROW)
-    {
-      int countAll = sqlite3_column_int(statement, 0);
-      if (countAll > 0)
-        result = true;
-    }
-  sqlite3_finalize(statement);
-  return result;
-}
-
-
-void
-MerkleTreeSqlite3::deleteSubTree(Index rootIndex)
-{
-  sqlite3_stmt* stmt;
-  sqlite3_prepare_v2(m_database, "DELETE FROM SubTree WHERE subTree_sequence=? AND subTree_level=?",
-                     -1, &stmt, 0);
-  sqlite3_bind_int64(stmt, 1, rootIndex.number);
-  sqlite3_bind_int64(stmt, 2, rootIndex.level);
-  sqlite3_step(stmt);
-  sqlite3_finalize(stmt);
-}
-
-
-void
-MerkleTreeSqlite3::getAllSubTree(std::vector<std::string> subTreeInfoList)
-{
-  sqlite3_stmt* stmt;
-  sqlite3_prepare_v2(m_database,
-                     "SELECT subTree_info FROM SubTree",
-                     -1, &stmt, 0);
-  while (sqlite3_step(stmt) == SQLITE_ROW)
-    subTreeInfoList.push_back(std::string(reinterpret_cast<const char *>
-                                          (sqlite3_column_text(stmt, 0)),
-                                          sqlite3_column_bytes(stmt, 0)));
-
-  sqlite3_finalize(stmt);
-}
-
-
-// For leafInfo
-
-void
-MerkleTreeSqlite3::addLeafInfo(uint64_t sequence, ndn::ConstBufferPtr buf_ptr)
-{
-
-  sqlite3_stmt* statement;
-  sqlite3_prepare_v2(m_database,
-                     "INSERT OR REPLACE INTO Leaf  \
-                      (leaf_sequence, leaf_info)   \
-                      values (?, ?)", -1, &statement, 0);
-  sqlite3_bind_int64(statement, 1, sequence);
-  sqlite3_bind_blob(statement, 2, buf_ptr->buf(), buf_ptr->size(), SQLITE_STATIC);
-  sqlite3_step(statement);
-  sqlite3_finalize(statement);
-}
-
-
-ndn::ConstBufferPtr
-MerkleTreeSqlite3::getLeafInfo(uint64_t sequence)
-{
-  sqlite3_stmt* statement;
-  sqlite3_prepare_v2(m_database,
-                     "SELECT leaf_info FROM Leaf \
-                      WHERE leaf_sequence=?", -1, &statement, 0);
-  sqlite3_bind_int64(statement, 1, sequence);
-  int res = sqlite3_step(statement);
-  if (res == SQLITE_ROW)
-    {
-      ndn::Buffer res_buf(sqlite3_column_blob(statement, 0), sqlite3_column_bytes(statement, 0));
-      ndn::ConstBufferPtr result = ndn::make_shared<ndn::Buffer>(res_buf);
-      sqlite3_finalize(statement);
-      return result;
-    }
-  else
-    {
-      sqlite3_finalize(statement);
-      return ndn::ConstBufferPtr();
-    }
-}
-
-
-bool
-MerkleTreeSqlite3::doesLeafInfoExist(uint64_t sequence)
-{
-  bool result = false;
-  sqlite3_stmt* statement;
-  sqlite3_prepare_v2(m_database,
-                     "SELECT count(*) FROM Leaf WHERE leaf_sequence=?",
-                     -1, &statement, 0);
-  sqlite3_bind_int64(statement, 1, sequence);
-  int res = sqlite3_step(statement);
-  if (res == SQLITE_ROW)
-    {
-      int countAll = sqlite3_column_int(statement, 0);
-      if (countAll > 0)
-        result = true;
-    }
-  sqlite3_finalize(statement);
-  return result;
-}
-
-
-void
-MerkleTreeSqlite3::deleteLeafInfo(uint64_t sequence)
-{
-  sqlite3_stmt* stmt;
-  sqlite3_prepare_v2(m_database, "DELETE FROM Leaf WHERE leaf_sequence=?",
-                     -1, &stmt, 0);
-  sqlite3_bind_int64(stmt, 1, sequence);
-  sqlite3_step(stmt);
-  sqlite3_finalize(stmt);
-}
-
-
-void
-MerkleTreeSqlite3::getAllLeafInfo(std::map<uint64_t, ndn::ConstBufferPtr> leaves)
-{
-  sqlite3_stmt* stmt;
-  sqlite3_prepare_v2(m_database,
-                     "SELECT leaf_sequence, leaf_info FROM Leaf",
-                     -1, &stmt, 0);
-  while (sqlite3_step(stmt) == SQLITE_ROW)
-    {
-      uint64_t seq = sqlite3_column_int64(stmt, 0);
-      ndn::ConstBufferPtr buf = ndn::make_shared<ndn::Buffer>(sqlite3_column_blob(stmt, 1),
-                                                              sqlite3_column_bytes(stmt, 1));
-      leaves[seq] = buf;
-    }
-
-  sqlite3_finalize(stmt);
-}
-
-
-} // namespace nsl
diff --git a/core/merkle-tree-sqlite3.hpp b/core/merkle-tree-sqlite3.hpp
deleted file mode 100644
index 617d20c..0000000
--- a/core/merkle-tree-sqlite3.hpp
+++ /dev/null
@@ -1,86 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014,  Regents of the University of California
- *
- * This file is part of NSL (NDN Signature Logger).
- * See AUTHORS.md for complete list of NSL authors and contributors.
- *
- * NSL is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
- */
-
-#ifndef NLS_CORE_MERKLE_TREE_SQLITE3_HPP
-#define NLS_CORE_MERKLE_TREE_SQLITE3_HPP
-
-#include <sqlite3.h>
-#include <map>
-#include "sub-tree.hpp"
-typedef ndn::shared_ptr<const nsl::SubTree> ConstSubTreePtr;
-typedef ndn::shared_ptr<nsl::SubTree> SubTreePtr;
-
-struct sqlite3;
-
-namespace nsl {
-
-class MerkleTreeSqlite3
-{
-public:
-
-  MerkleTreeSqlite3();
-
-  ~MerkleTreeSqlite3();
-
-  // SubTree
-  void
-  addSubTree(SubTreePtr oldSubTree);
-
-  std::string
-  getSubTree(Index rootIndex);
-
-  bool
-  doesSubTreeExist(Index rootIndex);
-
-  void
-  deleteSubTree(Index rootIndex);
-
-  void
-  getAllSubTree(std::vector<std::string> subTreeInfoList);
-
-
-  // LeafInfo (no need of encoding/decoding scheme)
-  void
-  addLeafInfo(uint64_t sequence, ndn::ConstBufferPtr buf_ptr);
-
-  ndn::ConstBufferPtr
-  getLeafInfo(uint64_t sequence);
-
-  bool
-  doesLeafInfoExist(uint64_t sequence);
-
-  void
-  deleteLeafInfo(uint64_t sequence);
-
-  void
-  getAllLeafInfo(std::map<uint64_t, ndn::ConstBufferPtr> leaves);
-
-
-private:
-  sqlite3* m_database;
-
-};
-
-
-} // namespace nsl
-
-
-#endif // NLS_CORE_MERKLE_TREE_SQLITE3_HPP
diff --git a/core/merkle-tree.cpp b/core/merkle-tree.cpp
index f74af33..a579350 100644
--- a/core/merkle-tree.cpp
+++ b/core/merkle-tree.cpp
@@ -16,125 +16,205 @@
  * You should have received a copy of the GNU General Public License along with
  * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
  */
+
 #include "merkle-tree.hpp"
 
 namespace nsl {
 
-MerkleTree::MerkleTree()
+MerkleTree::MerkleTree(Db& db)
+  : m_db(db)
+  , m_nextLeafSeqNo(0)
 {
-  m_nLevels = 0;
-  m_nLeaves = 0;
 }
 
-
-ConstNodePtr
-MerkleTree::getNode(const Index& index)
+MerkleTree::MerkleTree(const Name& loggerName, Db& db)
+  : m_loggerName(loggerName)
+  , m_db(db)
+  , m_nextLeafSeqNo(0)
 {
-  ConstNodePtr p_leav;
-  if (m_cache.doesNodeExist(index))
-    {
-      p_leav = m_cache.queryNode(index);
-      return p_leav;
+  loadPendingSubTrees();
+}
+
+MerkleTree::~MerkleTree()
+{
+  savePendingTree();
+}
+
+void
+MerkleTree::setLoggerName(const Name& loggerName)
+{
+  m_loggerName = loggerName;
+}
+
+bool
+MerkleTree::addLeaf(const NonNegativeInteger& seqNo, ndn::ConstBufferPtr hash)
+{
+  auto baseTree = m_pendingTrees[SubTreeBinary::SUB_TREE_DEPTH - 1];
+  BOOST_ASSERT(baseTree != nullptr);
+
+  NodePtr leaf = make_shared<Node>(seqNo, 0, seqNo + 1, hash);
+  return baseTree->addLeaf(leaf);
+}
+
+void
+MerkleTree::savePendingTree()
+{
+  size_t level = m_rootSubTree->getPeakIndex().level;
+  size_t step = SubTreeBinary::SUB_TREE_DEPTH - 1;
+
+  for (size_t i = level; i > 0; i -= step) {
+    auto pendingTree = m_pendingTrees[i];
+    BOOST_ASSERT(pendingTree != nullptr);
+
+    auto data = pendingTree->encode();
+    if (data != nullptr) {
+      m_db.insertSubTreeData(pendingTree->getPeakIndex().level, pendingTree->getPeakIndex().seqNo,
+                             *data, false, pendingTree->getNextLeafSeqNo());
     }
+  }
+}
+
+shared_ptr<Data>
+MerkleTree::getPendingSubTreeData(size_t level)
+{
+  auto it = m_pendingTrees.find(level);
+  if (it != m_pendingTrees.end())
+    return it->second->encode();
   else
-    return p_leav;
+    return nullptr;
 }
 
-
-uint64_t
-MerkleTree::getLeafNum() const
+// private:
+void
+MerkleTree::loadPendingSubTrees()
 {
-  return m_nLeaves;
+  std::vector<shared_ptr<Data>> subtreeDatas = m_db.getPendingSubTrees();
+
+  shared_ptr<SubTreeBinary> subtree;
+  if (subtreeDatas.empty()) {
+    subtree = make_shared<SubTreeBinary>(m_loggerName,
+      Node::Index(0, SubTreeBinary::SUB_TREE_DEPTH - 1),
+      [this] (const Node::Index& idx) {
+        // std::cerr << "complete: " << idx.level << ", " << idx.seqNo << std::endl;
+        this->getNewRoot(idx);
+      },
+      [this] (const Node::Index& idx,
+              const NonNegativeInteger& seqNo,
+              ndn::ConstBufferPtr hash) {
+        // std::cerr << "update: " << idx.level << ", " << idx.seqNo << std::endl;
+        // std::cerr << "seqNo: " << seqNo << std::endl;
+        this->m_nextLeafSeqNo = seqNo;
+        this->m_hash = hash;
+      });
+    m_pendingTrees[SubTreeBinary::SUB_TREE_DEPTH - 1] = subtree;
+    m_rootSubTree = subtree;
+    return;
+  }
+
+  subtree = make_shared<SubTreeBinary>(m_loggerName,
+    [this] (const Node::Index& idx) { this->getNewRoot(idx); },
+    [this] (const Node::Index& idx,
+            const NonNegativeInteger& seqNo,
+            ndn::ConstBufferPtr hash) {
+      this->m_nextLeafSeqNo = seqNo;
+      this->m_hash = hash;
+    });
+
+  subtree->decode(*subtreeDatas[0]);
+  m_pendingTrees[subtree->getPeakIndex().level] = subtree;
+  m_rootSubTree = subtree;
+
+  shared_ptr<SubTreeBinary> parentTree = subtree;
+  for (size_t i = 1; i < subtreeDatas.size(); i++) {
+    subtree = make_shared<SubTreeBinary>(m_loggerName,
+      [this] (const Node::Index& idx) {
+        this->getNewSibling(idx);
+      },
+      [parentTree] (const Node::Index&,
+           const NonNegativeInteger& seqNo,
+           ndn::ConstBufferPtr hash) {
+        parentTree->updateLeaf(seqNo, hash);
+      });
+
+    subtree->decode(*subtreeDatas[i]);
+    if (parentTree->getPeakIndex().level + 1 - SubTreeBinary::SUB_TREE_DEPTH !=
+        subtree->getPeakIndex().level)
+      throw Error("loadPendingSubTrees: inconsistent pending subtree level");
+
+    if (parentTree->getNextLeafSeqNo() != subtree->getNextLeafSeqNo())
+      throw Error("loadPendingSubTrees: inconsistent pending subtree next leaf seqNo");
+
+    m_pendingTrees[subtree->getPeakIndex().level] = subtree;
+    parentTree = subtree;
+  }
 }
 
-
-uint64_t
-MerkleTree::getLevel() const
+void
+MerkleTree::getNewRoot(const Node::Index& idx)
 {
-  return m_nLevels;
+  // save the old root tree into db
+  auto oldRoot = m_pendingTrees[idx.level];
+  BOOST_ASSERT(oldRoot != nullptr);
+  m_db.insertSubTreeData(idx.level, idx.seqNo, *oldRoot->encode());
+
+  // create a new root tree
+  Node::Index newRootIdx(0, idx.level + SubTreeBinary::SUB_TREE_DEPTH - 1);
+  auto newRoot = make_shared<SubTreeBinary>(m_loggerName, newRootIdx,
+    [this] (const Node::Index& idx) {
+      // std::cerr << "complete: " << idx.level << ", " << idx.seqNo << std::endl;
+      this->getNewRoot(idx);
+    },
+    [this] (const Node::Index& index,
+         const NonNegativeInteger& seqNo,
+         ndn::ConstBufferPtr hash) {
+      // std::cerr << "update: " << index.level << ", " << index.seqNo << std::endl;
+      // std::cerr << "seqNo: " << seqNo << std::endl;
+      this->m_nextLeafSeqNo = seqNo;
+      this->m_hash = hash;
+    });
+
+  m_pendingTrees[newRoot->getPeakIndex().level] = newRoot;
+  m_rootSubTree = newRoot;
+
+  bool result = newRoot->updateLeaf(idx.seqNo + idx.range, oldRoot->getRoot()->getHash());
+  BOOST_ASSERT(result);
+
+  // create a sibling
+  getNewSibling(idx);
 }
 
-
-
-uint64_t
-MerkleTree::addLeaf(ndn::ConstBufferPtr info)
+void
+MerkleTree::getNewSibling(const Node::Index& idx)
 {
-  Leaf new_leaf(info, m_nLeaves, 0, 0);
-  new_leaf.computeHash(); // computeHash() has been written.
-  m_nLeaves++;
-  if (m_nLeaves > int(pow(2, int(m_nLevels) - 1)))
-    {
-      m_nLevels++;
-    }
-  m_cache.addLeaf(new_leaf);
-  return m_nLeaves - 1;
+  // save old sibling
+  auto oldSibling = m_pendingTrees[idx.level];
+  BOOST_ASSERT(oldSibling != nullptr);
+  m_db.insertSubTreeData(idx.level, idx.seqNo, *oldSibling->encode());
+
+  // get parent tree
+  Node::Index parentIdx(0, idx.level + SubTreeBinary::SUB_TREE_DEPTH - 1);
+  auto parent = m_pendingTrees[parentIdx.level];
+  BOOST_ASSERT(parent != nullptr);
+
+  // create a new sibling
+  Node::Index newSiblingIdx(idx.seqNo + idx.range, idx.level);
+  // std::cerr << "new Sibling: " << newSiblingIdx.level << ", " << newSiblingIdx.seqNo << std::endl;
+  auto newSibling = make_shared<SubTreeBinary>(m_loggerName, newSiblingIdx,
+    [this] (const Node::Index& idx) { this->getNewSibling(idx); },
+    [parent] (const Node::Index& index,
+         const NonNegativeInteger& seqNo,
+         ndn::ConstBufferPtr hash) {
+      // std::cerr << "update: " << index.level << ", " << index.seqNo << std::endl;
+      // std::cerr << "seqNo: " << seqNo << std::endl;
+      // std::cerr << "parent: " << parent->getRoot()->getIndex().level << ", " <<
+      //                            parent->getRoot()->getIndex().seqNo << std::endl;
+      bool result = parent->updateLeaf(seqNo, hash);
+      BOOST_ASSERT(result);
+    });
+
+  m_pendingTrees[newSibling->getPeakIndex().level] = newSibling;
 }
 
-
-std::vector<ConstNodePtr>
-MerkleTree::generateProof(uint64_t version1, uint64_t version2)
-{
-  std::vector<ConstNodePtr> proof;
-  if (version1 >= version2)
-    {
-      return proof;
-    }
-
-  //add a memberproof from version2
-  Index this_idx;
-  this_idx.number = version2;
-  this_idx.level = 0;
-  ConstNodePtr p_leav;
-  p_leav = m_cache.queryNode(this_idx);
-  proof.push_back(p_leav);
-  if ((this_idx.number % 2) != 0)
-    {
-      this_idx.number -= 1;
-      p_leav = m_cache.queryNode(this_idx);
-      proof.push_back(p_leav);
-    }
-  this_idx.level += 1;
-  this_idx.number -= this_idx.number % 2;
-  for (int i = 1; i < m_nLevels - 1 ; i++)
-    {
-      if (this_idx.number % int(pow(2, i + 1)) != 0)
-        {
-          this_idx.number -= int(pow(2, i));
-          p_leav = m_cache.queryNode(this_idx);
-          proof.push_back(p_leav);
-        }
-      this_idx.level += 1;
-      this_idx.number -= this_idx.number % int(pow(2, i + 1));
-    }
-
-  //add another path from version1
-  this_idx.number = version1;
-  this_idx.level = 0;
-  p_leav = m_cache.queryNode(this_idx);
-  proof.push_back(p_leav);
-  if ((this_idx.number % 2) != 0)
-    {
-      this_idx.number -= 1;
-      p_leav = m_cache.queryNode(this_idx);
-      proof.push_back(p_leav);
-    }
-  this_idx.level += 1;
-  this_idx.number -= this_idx.number % 2;
-  for (int i = 1; i < m_nLevels - 1 ; i++)
-    {
-      if (this_idx.number % int(pow(2, i + 1)) != 0)
-        {
-          this_idx.number -= int(pow(2, i));
-          p_leav = m_cache.queryNode(this_idx);
-          proof.push_back(p_leav);
-        }
-      this_idx.level += 1;
-      this_idx.number -= this_idx.number % int(pow(2, i + 1));
-    }
-
-  return proof;
-}
-
-} // namespace nsl
+}// namespace nsl
diff --git a/core/merkle-tree.hpp b/core/merkle-tree.hpp
index ccf73c5..3e877f1 100644
--- a/core/merkle-tree.hpp
+++ b/core/merkle-tree.hpp
@@ -16,60 +16,93 @@
  * You should have received a copy of the GNU General Public License along with
  * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
  */
-#ifndef NLS_CORE_MERKLE_TREE_HPP
-#define NLS_CORE_MERKLE_TREE_HPP
 
-#include <map>
+#ifndef NSL_CORE_MERKLE_TREE_HPP
+#define NSL_CORE_MERKLE_TREE_HPP
+
+#include "common.hpp"
+#include "db.hpp"
+#include "sub-tree-binary.hpp"
 #include <vector>
 
-#include <stddef.h>
-#include <stdint.h>
-#include <time.h>
-
-#include "leaf.hpp"
-#include "intermediate-node.hpp"
-#include "merkle-tree-cache.hpp"
-
 namespace nsl {
 
 class MerkleTree
 {
 public:
-  MerkleTree();
-
-  ~MerkleTree()
+  class Error : public std::runtime_error
   {
+  public:
+    explicit
+    Error(const std::string& what)
+      : std::runtime_error(what)
+    {
+    }
+  };
+
+public:
+  /**
+   * @brief Constructor
+   */
+  MerkleTree(Db& db);
+
+  MerkleTree(const Name& loggerName, Db& db);
+
+  ~MerkleTree();
+
+  void
+  setLoggerName(const Name& loggerName);
+
+  const NonNegativeInteger&
+  getNextLeafSeqNo() const
+  {
+    return m_nextLeafSeqNo;
   }
 
-  ConstNodePtr
-  getNode(const Index& index);
+  const ndn::ConstBufferPtr&
+  getRootHash() const
+  {
+    return m_hash;
+  }
 
-  uint64_t
-  getLeafNum() const;
+  bool
+  addLeaf(const NonNegativeInteger& seqNo, ndn::ConstBufferPtr hash);
 
-  uint64_t
-  getLevel() const;
+  void
+  loadPendingSubTrees();
 
+  void
+  savePendingTree();
 
-  //return root hash value
-  uint64_t
-  addLeaf(ndn::ConstBufferPtr info);
+  shared_ptr<Data>
+  getPendingSubTreeData(size_t level);
 
+  std::vector<ConstSubTreeBinaryPtr>
+  getExistenceProof(const NonNegativeInteger& seqNo);
 
-  std::vector<ConstNodePtr>
-  generateProof(uint64_t version1, uint64_t version2); // version equals to leaf's index number
-
+  std::vector<ConstSubTreeBinaryPtr>
+  getConsistencyProof(const NonNegativeInteger& seqNo);
 
 private:
-  MerkleTreeCache m_cache;
-  uint64_t m_nLevels;
-  uint64_t m_nLeaves;
+  void
+  getNewRoot(const Node::Index& idx);
 
+  void
+  getNewSibling(const Node::Index& idx);
+
+private:
+  Name m_loggerName;
+  Db& m_db;
+
+  shared_ptr<SubTreeBinary> m_rootSubTree;
+  NonNegativeInteger m_nextLeafSeqNo;
+  ndn::ConstBufferPtr m_hash;
+
+  std::map<size_t, shared_ptr<SubTreeBinary>> m_pendingTrees;
 };
 
+}// namespace nsl
 
-} // namespace nsl
-
-#endif // NLS_CORE_MERKLE_TREE_HPP
+#endif // NSL_CORE_MERKLE_TREE_HPP
diff --git a/core/node.cpp b/core/node.cpp
index 66921cd..11e1cd0 100644
--- a/core/node.cpp
+++ b/core/node.cpp
@@ -16,48 +16,108 @@
  * You should have received a copy of the GNU General Public License along with
  * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
  */
 #include "node.hpp"
 
+#include <ndn-cxx/util/digest.hpp>
+#include <boost/lexical_cast.hpp>
+
 namespace nsl {
 
-Node::Node(uint64_t sequenceNumber, uint64_t level, time_t timestamp)
+ndn::ConstBufferPtr Node::EMPTY_HASH;
+
+Node::Index::Index(const NonNegativeInteger& nodeSeq, size_t nodeLevel)
+  : seqNo(nodeSeq)
+  , level(nodeLevel)
+  , range(1 << nodeLevel)
 {
-  m_index.number = sequenceNumber;
-  m_index.level = level;
-  m_timeStamp = timestamp;
+  if (seqNo % range != 0)
+    throw Error("Index: index level and seqNo do not match: (" +
+                boost::lexical_cast<std::string>(seqNo) + ", " +
+                boost::lexical_cast<std::string>(level) + ")");
 }
 
-
-const Index&
-Node::getIndex() const
+bool
+Node::Index::operator<(const Index& other) const
 {
-  return m_index;
+  if (seqNo < other.seqNo) {
+    return true;
+  }
+  else if (seqNo == other.seqNo) {
+    return level < other.level;
+  }
+  else {
+    return false;
+  }
 }
 
-
-
-time_t
-Node::getTimestamp() const
+bool
+Node::Index::operator==(const Index& other) const
 {
-  return m_timeStamp;
+  return equals(other);
 }
 
+bool
+Node::Index::operator!=(const Index& other) const
+{
+  return !equals(other);
+}
 
+bool
+Node::Index::equals(const Index& other) const
+{
+  if (seqNo == other.seqNo && level == other.level) {
+    return true;
+  }
+  else {
+    return false;
+  }
+}
+
+Node::Node(const NonNegativeInteger& nodeSeqNo,
+           size_t nodeLevel,
+           const NonNegativeInteger& leafSeqNo,
+           ndn::ConstBufferPtr hash)
+  : m_index(nodeSeqNo, nodeLevel)
+  , m_hash(hash)
+{
+  if (leafSeqNo == 0 && m_index.seqNo > leafSeqNo)
+    m_leafSeqNo = m_index.seqNo;
+  else
+    setLeafSeqNo(leafSeqNo);
+}
 
 void
-Node::setHash(ndn::ConstBufferPtr digest)
+Node::setLeafSeqNo(const NonNegativeInteger& leafSeqNo)
 {
-  m_hash = digest;
+  if (leafSeqNo > m_index.seqNo + m_index.range || leafSeqNo < m_index.seqNo)
+    throw Error("Node: leaf seqNo is out of range");
+
+  m_leafSeqNo = leafSeqNo;
 }
 
+void
+Node::setHash(ndn::ConstBufferPtr hash)
+{
+  m_hash = hash;
+}
 
+bool
+Node::isFull() const
+{
+  return m_index.seqNo + m_index.range == m_leafSeqNo;
+}
 
 ndn::ConstBufferPtr
-Node::getHash() const
+Node::getEmptyHash()
 {
-  return m_hash;
+  if (EMPTY_HASH == nullptr) {
+    ndn::util::Sha256 sha256;
+    EMPTY_HASH = sha256.computeDigest();
+  }
+
+  return EMPTY_HASH;
 }
 
 } // namespace nsl
diff --git a/core/node.hpp b/core/node.hpp
index be2ed92..c3d0572 100644
--- a/core/node.hpp
+++ b/core/node.hpp
@@ -16,92 +16,109 @@
  * You should have received a copy of the GNU General Public License along with
  * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
+ * See AUTHORS.md for complete list of nsl authors and contributors.
  */
 
-#ifndef NLS_CORE_NODE_HPP
-#define NLS_CORE_NODE_HPP
-#include <stddef.h>
-#include <time.h>
+#ifndef NSL_CORE_NODE_HPP
+#define NSL_CORE_NODE_HPP
 
-#include <ndn-cxx/util/crypto.hpp>
+#include "common.hpp"
+#include "util/non-negative-integer.hpp"
+#include <ndn-cxx/encoding/buffer.hpp>
 
 namespace nsl {
 
-class Index
-{
-public:
-  Index()
-  {
-  }
-
-  Index(const Index& idx)
-    : number(idx.number),
-      level(idx.level)
-  {
-  }
-
-  bool operator<(const Index& other) const
-  {
-    if (number < other.number)
-      {
-        return true;
-      }
-    else if (number == other.number)
-      {
-        return level < other.level;
-      }
-    else
-      {
-        return false;
-      }
-
-  }
-
-public:
-  uint64_t number;
-  uint64_t level;
-};
-
-
 class Node
 {
 public:
-
-  Node()
+  class Error : public std::runtime_error
   {
-  }
+  public:
+    explicit
+    Error(const std::string& what)
+      : std::runtime_error(what)
+    {
+    }
+  };
 
-
-  Node(uint64_t sequenceNumber, uint64_t level, time_t timestamp);
-
-
-  ~Node()
+  class Index
   {
-  }
+  public:
+    explicit
+    Index(const NonNegativeInteger& seqNo = 0, size_t level = 0);
 
+    /**
+     * @brief compare two indices
+     *
+     * A index is larger than the other if its seqNo is larger than the other,
+     * or their seqNos are equal but its level is lower.
+     */
+    bool
+    operator<(const Index& other) const;
+
+    bool
+    operator==(const Index& other) const;
+
+    bool
+    operator!=(const Index& other) const;
+
+    bool
+    equals(const Index& other) const;
+
+  public:
+    NonNegativeInteger seqNo;
+    size_t level;
+    NonNegativeInteger range;
+  };
+
+public:
+  Node(const NonNegativeInteger& seqNo,
+       size_t level,
+       const NonNegativeInteger& leafSeqNo = 0,
+       ndn::ConstBufferPtr hash = nullptr);
 
   const Index&
-  getIndex() const;
-
-
-  time_t
-  getTimestamp() const;
-
+  getIndex() const
+  {
+    return m_index;
+  }
 
   void
-  setHash(ndn::ConstBufferPtr digest);
+  setLeafSeqNo(const NonNegativeInteger& leafSeqNo);
 
+  const NonNegativeInteger&
+  getLeafSeqNo() const
+  {
+    return m_leafSeqNo;
+  }
+
+  void
+  setHash(ndn::ConstBufferPtr hash);
 
   ndn::ConstBufferPtr
-  getHash() const;
+  getHash() const
+  {
+    return m_hash;
+  }
+
+  bool
+  isFull() const;
+
+  static ndn::ConstBufferPtr
+  getEmptyHash();
+
+protected:
+  Index m_index;
+  NonNegativeInteger m_leafSeqNo;
+  ndn::ConstBufferPtr m_hash;
 
 private:
-  ndn::ConstBufferPtr m_hash;
-  Index m_index;   // Node index.number starts from 0 (the index of current root)
-  time_t m_timeStamp;
+  static ndn::ConstBufferPtr EMPTY_HASH;
 };
 
+typedef shared_ptr<Node> NodePtr;
+typedef shared_ptr<const Node> ConstNodePtr;
+
 } // namespace nsl
 
-#endif // NLS_CORE_NODE_HPP
+#endif // NSL_CORE_NODE_HPP
diff --git a/core/sub-tree-binary.cpp b/core/sub-tree-binary.cpp
new file mode 100644
index 0000000..be9c2d3
--- /dev/null
+++ b/core/sub-tree-binary.cpp
@@ -0,0 +1,471 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014,  Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#include "sub-tree-binary.hpp"
+
+#include <ndn-cxx/util/digest.hpp>
+#include <ndn-cxx/util/crypto.hpp>
+#include <ndn-cxx/security/digest-sha256.hpp>
+
+namespace nsl {
+
+const time::milliseconds SubTreeBinary::INCOMPLETE_FRESHNESS_PERIOD(60000);
+const std::string SubTreeBinary::COMPONENT_COMPLETE("complete");
+const ssize_t SubTreeBinary::OFFSET_ROOTHASH = -1;
+const ssize_t SubTreeBinary::OFFSET_COMPLETE = -2;
+const ssize_t SubTreeBinary::OFFSET_SEQNO = -3;
+const ssize_t SubTreeBinary::OFFSET_LEVEL = -4;
+const size_t SubTreeBinary::N_LOGGER_SUFFIX = 4;
+const size_t SubTreeBinary::SUB_TREE_DEPTH = 6;
+
+
+SubTreeBinary::SubTreeBinary(const Name& loggerName,
+                             const CompleteCallback& completeCallback,
+                             const RootUpdateCallback& rootUpdateCallback)
+  : m_loggerName(loggerName)
+  , m_completeCallback(completeCallback)
+  , m_rootUpdateCallback(rootUpdateCallback)
+{
+}
+
+SubTreeBinary::SubTreeBinary(const Name& loggerName,
+                             const Node::Index& peakIndex,
+                             const CompleteCallback& completeCallback,
+                             const RootUpdateCallback& rootUpdateCallback)
+  : m_loggerName(loggerName)
+  , m_completeCallback(completeCallback)
+  , m_rootUpdateCallback(rootUpdateCallback)
+{
+  initialize(peakIndex);
+}
+
+const NonNegativeInteger&
+SubTreeBinary::getNextLeafSeqNo() const
+{
+  if (m_actualRoot != nullptr)
+    return m_actualRoot->getLeafSeqNo();
+
+  return m_peakIndex.seqNo;
+}
+
+ndn::ConstBufferPtr
+SubTreeBinary::getRootHash() const
+{
+  if (m_actualRoot != nullptr)
+    return m_actualRoot->getHash();
+
+  return nullptr;
+}
+
+ConstNodePtr
+SubTreeBinary::getNode(const Node::Index& index) const
+{
+  auto it = m_nodes.find(index);
+  if (it != m_nodes.end()) {
+    return it->second;
+  }
+
+  return nullptr;
+}
+
+bool
+SubTreeBinary::addLeaf(NodePtr leaf)
+{
+  // sanity check: must be a valid leaf
+  if (leaf->getIndex().level != m_leafLevel ||
+      leaf->getIndex().seqNo < m_minSeqNo ||
+      leaf->getIndex().seqNo >= m_maxSeqNo)
+    return false;
+
+  // sanity check: must be the expected next leaf
+  if (leaf->getIndex().seqNo != m_pendingLeafSeqNo ||
+      !m_isPendingLeafEmpty)
+    return false;
+
+  // add the leaf
+  m_nodes[leaf->getIndex()] = leaf;
+
+  // update actual root (guarantee we will have a root)
+  updateActualRoot(leaf);
+
+  // update nodes and their hashes
+  updateParentNode(leaf);
+
+  if (leaf->isFull()) {
+    m_pendingLeafSeqNo = leaf->getIndex().seqNo + leaf->getIndex().range;
+    m_isPendingLeafEmpty = true;
+  }
+  else {
+    m_isPendingLeafEmpty = false;
+  }
+
+  return true;
+}
+
+bool
+SubTreeBinary::updateLeaf(const NonNegativeInteger& nextSeqNo, ndn::ConstBufferPtr hash)
+{
+  // std::cerr << "NextSeqNo: " << nextSeqNo << std::endl;
+  // std::cerr << "minSeqNo: " << m_minSeqNo << std::endl;
+  // std::cerr << "maxSeqNo: " << m_maxSeqNo << std::endl;
+
+  // sanity check
+  if (nextSeqNo < m_minSeqNo || nextSeqNo > m_maxSeqNo)
+    return false;
+
+  // std::cerr << "2" << std::endl;
+  // determine leaf index
+  NonNegativeInteger leafSeqNo = ((nextSeqNo - 1) >> m_leafLevel) << m_leafLevel;
+  if (m_pendingLeafSeqNo != leafSeqNo)
+    return false;
+
+  Node::Index index(leafSeqNo, m_leafLevel);
+  auto leaf = m_nodes[index];
+
+  if (leaf == nullptr) {
+    leaf = make_shared<Node>(leafSeqNo, m_leafLevel, nextSeqNo, hash);
+    m_nodes[index] = leaf;
+    updateActualRoot(leaf);
+  }
+  else {
+    leaf->setLeafSeqNo(nextSeqNo);
+    leaf->setHash(hash);
+  }
+
+  if (nextSeqNo == leafSeqNo + (1 << m_leafLevel)) {
+    m_pendingLeafSeqNo = nextSeqNo;
+    m_isPendingLeafEmpty = true;
+  }
+
+  updateParentNode(leaf);
+
+  return true;
+}
+
+bool
+SubTreeBinary::isFull() const
+{
+  if (m_actualRoot != nullptr &&
+      m_actualRoot->getIndex() == m_peakIndex &&
+      m_actualRoot->isFull())
+    return true;
+
+  return false;
+}
+
+shared_ptr<Data>
+SubTreeBinary::encode() const
+{
+  if (m_actualRoot == nullptr) {
+    auto emptyData = make_shared<Data>();
+    // Name
+    Name emptyName = m_loggerName;
+    emptyName.appendNumber(m_peakIndex.level)
+      .appendNumber(m_peakIndex.seqNo)
+      .appendNumber(m_peakIndex.seqNo)
+      .append(Node::getEmptyHash()->buf(), Node::getEmptyHash()->size());
+    emptyData->setName(emptyName);
+
+    // MetaInfo
+    emptyData->setFreshnessPeriod(time::milliseconds(0));
+
+    // Signature
+    ndn::DigestSha256 sig;
+    emptyData->setSignature(sig);
+
+    Block sigValue(tlv::SignatureValue,
+                   ndn::crypto::sha256(emptyData->wireEncode().value(),
+                                       emptyData->wireEncode().value_size() -
+                                       emptyData->getSignature().getValue().size()));
+    emptyData->setSignatureValue(sigValue);
+
+    emptyData->wireEncode();
+
+    return emptyData;
+  }
+
+  // Name
+  Name dataName = m_loggerName;
+  dataName.appendNumber(m_actualRoot->getIndex().level)
+    .appendNumber(m_actualRoot->getIndex().seqNo);
+  if (isFull())
+    dataName.append(COMPONENT_COMPLETE.c_str());
+  else
+    dataName.appendNumber(m_actualRoot->getLeafSeqNo());
+  dataName.append(m_actualRoot->getHash()->buf(), m_actualRoot->getHash()->size());
+
+  auto data = make_shared<Data>(dataName);
+
+  // MetaInfo
+  if (!isFull())
+    data->setFreshnessPeriod(INCOMPLETE_FRESHNESS_PERIOD);
+
+  // Content
+  auto buffer = make_shared<ndn::Buffer>();
+  NonNegativeInteger range = 1 << m_leafLevel;
+  for (NonNegativeInteger i = m_minSeqNo; i < m_maxSeqNo; i += range) {
+    auto it = m_nodes.find(Node::Index(i, m_leafLevel));
+    if (it == m_nodes.end())
+      break;
+
+    auto leaf = it->second;
+    if (leaf == nullptr)
+      break;
+    BOOST_ASSERT(leaf->getHash() != nullptr);
+    BOOST_ASSERT(leaf->getHash()->size() == 32);
+    buffer->insert(buffer->end(), leaf->getHash()->begin(), leaf->getHash()->end());
+  }
+  data->setContent(buffer->buf(), buffer->size());
+
+  // Signature
+  ndn::DigestSha256 sig;
+  data->setSignature(sig);
+
+  Block sigValue(tlv::SignatureValue,
+                 ndn::crypto::sha256(data->wireEncode().value(),
+                                     data->wireEncode().value_size() -
+                                     data->getSignature().getValue().size()));
+  data->setSignatureValue(sigValue);
+
+  data->wireEncode();
+  return data;
+}
+
+void
+SubTreeBinary::decode(const Data& data)
+{
+  bool isComplete = false;
+  NonNegativeInteger nextSeqNo;
+  ndn::ConstBufferPtr rootHash;
+  NonNegativeInteger seqNo;
+  size_t level;
+
+  const Name& dataName = data.getName();
+
+  if (!m_loggerName.isPrefixOf(dataName))
+    throw Error("decode: logger name does not match");
+
+  if (m_loggerName.size() + N_LOGGER_SUFFIX != dataName.size())
+    throw Error("decode: data name does not follow the naming convention");
+
+  try {
+    if (dataName.get(OFFSET_COMPLETE).toUri() == COMPONENT_COMPLETE)
+      isComplete = true;
+    else
+      nextSeqNo = dataName.get(OFFSET_COMPLETE).toNumber();
+
+    rootHash = make_shared<ndn::Buffer>(dataName.get(OFFSET_ROOTHASH).value(),
+                                        dataName.get(OFFSET_ROOTHASH).value_size());
+
+    seqNo = dataName.get(OFFSET_SEQNO).toNumber();
+    level = dataName.get(OFFSET_LEVEL).toNumber();
+  }
+  catch (tlv::Error&) {
+    throw Error("decode: logger name encoding error");
+  }
+
+  if (seqNo == 0) {
+    size_t peakLevel = 0;
+    if (level % (SUB_TREE_DEPTH - 1) != 0)
+      peakLevel = ((level + SUB_TREE_DEPTH - 1) / (SUB_TREE_DEPTH - 1)) * (SUB_TREE_DEPTH - 1);
+    else
+      peakLevel = level;
+
+    if (nextSeqNo == 1 << peakLevel)
+      peakLevel = peakLevel + SUB_TREE_DEPTH - 1;
+
+    initialize(Node::Index(seqNo, peakLevel));
+  }
+  else
+    initialize(Node::Index(seqNo, level));
+
+  if (isComplete)
+    nextSeqNo = seqNo + (1 << level);
+  else if (nextSeqNo == seqNo) // empty tree
+    return;
+
+  if (rootHash->size() != 32)
+    throw Error("decode: wrong root hash size");
+
+  if (nextSeqNo <= seqNo || nextSeqNo > seqNo + (1 << level))
+    throw Error("decode: wrong current leaf SeqNo");
+
+  int nLeaves = (nextSeqNo - seqNo - 1) / (1 << m_leafLevel) + 1;
+
+  // std::cerr << data.getName() << std::endl;
+  // std::cerr << nextSeqNo << std::endl;
+  // std::cerr << nLeaves * 32 << std::endl;
+  // std::cerr << data.getContent().value_size() << std::endl;
+
+  if (nLeaves * 32 != data.getContent().value_size())
+    throw Error("decode: inconsistent content");
+
+  const uint8_t* offset = data.getContent().value();
+  NonNegativeInteger seqNoInterval = 1 << m_leafLevel;
+  int i = 0;
+  for (; i < nLeaves - 1; i++) {
+    auto node = make_shared<Node>(seqNo + (i * seqNoInterval),
+                                  m_peakIndex.level + 1 - SUB_TREE_DEPTH,
+                                  seqNo + (i * seqNoInterval) + seqNoInterval,
+                                  make_shared<ndn::Buffer>(offset + (i * 32), 32));
+    addLeaf(node);
+  }
+
+  auto node = make_shared<Node>(seqNo + (i * seqNoInterval),
+                                m_peakIndex.level + 1 - SUB_TREE_DEPTH,
+                                nextSeqNo,
+                                make_shared<ndn::Buffer>(offset + (i * 32), 32));
+  addLeaf(node);
+
+  if (*rootHash != *getRoot()->getHash())
+    throw Error("decode: Inconsistent hash");
+}
+
+Node::Index
+SubTreeBinary::toSubTreePeakIndex(const Node::Index& index, bool notRoot)
+{
+  size_t peakLevel =
+    ((index.level + SUB_TREE_DEPTH - 1) / (SUB_TREE_DEPTH - 1)) * (SUB_TREE_DEPTH - 1);
+
+  size_t leafLevel = peakLevel + 1 - SUB_TREE_DEPTH;
+
+  if (index.level % (SUB_TREE_DEPTH - 1) == 0 && index.level > 0 && !notRoot) {
+    peakLevel -= (SUB_TREE_DEPTH - 1);
+    leafLevel -= (SUB_TREE_DEPTH - 1);
+  }
+
+  NonNegativeInteger peakSeqNo = (index.seqNo >> peakLevel) << peakLevel;
+
+  return Node::Index(peakSeqNo, peakLevel);
+}
+
+void
+SubTreeBinary::initialize(const Node::Index& peakIndex)
+{
+  m_peakIndex = peakIndex;
+
+  if (peakIndex.level + 1 < SUB_TREE_DEPTH ||
+      peakIndex.level % (SUB_TREE_DEPTH - 1) != 0)
+    throw Error("SubTreeBinary: peak level does not match the depth");
+
+  m_leafLevel = peakIndex.level + 1 - SUB_TREE_DEPTH;
+
+  m_minSeqNo = peakIndex.seqNo;
+  m_maxSeqNo = peakIndex.seqNo + peakIndex.range;
+
+  m_pendingLeafSeqNo = m_minSeqNo;
+  m_isPendingLeafEmpty = true;
+}
+
+
+
+void
+SubTreeBinary::updateActualRoot(NodePtr node)
+{
+  if (m_actualRoot == nullptr) {
+    // if actual root is not set yet
+    if (node->getIndex().seqNo == 0) { // root sub-tree
+      m_actualRoot = node;
+      m_rootUpdateCallback(node->getIndex(), node->getLeafSeqNo(), node->getHash());
+      return;
+    }
+    else {
+      m_actualRoot = make_shared<Node>(m_peakIndex.seqNo, m_peakIndex.level);
+      m_nodes[m_actualRoot->getIndex()] = m_actualRoot;
+      return;
+    }
+  }
+
+  if (m_actualRoot->getIndex() == m_peakIndex)
+    return;
+
+  if ((node->getIndex().seqNo >> m_actualRoot->getIndex().level) != 0) {
+    // a new actual root at a higher is needed
+    m_actualRoot = make_shared<Node>(m_minSeqNo, m_actualRoot->getIndex().level + 1);
+    m_nodes[m_actualRoot->getIndex()] = m_actualRoot;
+    return;
+  }
+}
+
+void
+SubTreeBinary::updateParentNode(NodePtr node)
+{
+  if (node->getIndex() == m_actualRoot->getIndex()) { // root does not have a parent
+    return;
+  }
+
+  size_t parentLevel = node->getIndex().level + 1;
+  NodePtr parentNode;
+
+  if ((node->getIndex().seqNo >> node->getIndex().level) % 2 == 0) { // left child
+    // parent may not exist
+    Node::Index parentIndex(node->getIndex().seqNo, parentLevel);
+    parentNode = m_nodes[parentIndex];
+
+    ndn::util::Sha256 sha256;
+    sha256 << parentIndex.level << parentIndex.seqNo;
+    sha256.update(node->getHash()->buf(), node->getHash()->size());
+    sha256.update(Node::getEmptyHash()->buf(), Node::getEmptyHash()->size());
+
+    if (parentNode == nullptr) {
+      parentNode = make_shared<Node>(node->getIndex().seqNo,
+                                     parentLevel,
+                                     node->getLeafSeqNo(),
+                                     sha256.computeDigest());
+    }
+    else {
+      parentNode->setHash(sha256.computeDigest());
+      parentNode->setLeafSeqNo(node->getLeafSeqNo());
+    }
+
+    m_nodes[parentNode->getIndex()] = parentNode;
+  }
+  else { // right child
+    // parent must exist
+    NonNegativeInteger parentSeqNo = node->getIndex().seqNo - node->getIndex().range;
+
+    Node::Index parentIndex(parentSeqNo, parentLevel);
+    Node::Index siblingIndex(parentSeqNo, parentLevel - 1);
+
+    parentNode = m_nodes[parentIndex];
+    auto siblingNode = m_nodes[siblingIndex];
+
+    ndn::util::Sha256 sha256;
+    sha256 << parentNode->getIndex().level << parentNode->getIndex().seqNo;
+    sha256.update(siblingNode->getHash()->buf(), siblingNode->getHash()->size());
+    sha256.update(node->getHash()->buf(), node->getHash()->size());
+
+    parentNode->setHash(sha256.computeDigest());
+    parentNode->setLeafSeqNo(node->getLeafSeqNo());
+  }
+
+  if (parentNode->getIndex() == m_actualRoot->getIndex()) { // reach root
+    m_rootUpdateCallback(parentNode->getIndex(),
+                         parentNode->getLeafSeqNo(),
+                         parentNode->getHash());
+    if (parentNode->getIndex() == m_peakIndex && parentNode->isFull())
+      m_completeCallback(parentNode->getIndex());
+  }
+  else
+    updateParentNode(parentNode);
+}
+
+} // namespace nsl
diff --git a/core/sub-tree-binary.hpp b/core/sub-tree-binary.hpp
new file mode 100644
index 0000000..15a0e3e
--- /dev/null
+++ b/core/sub-tree-binary.hpp
@@ -0,0 +1,182 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014,  Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#ifndef NSL_CORE_SUB_TREE_HPP
+#define NSL_CORE_SUB_TREE_HPP
+
+#include "node.hpp"
+
+namespace nsl {
+
+typedef std::function<void(const Node::Index&)> CompleteCallback;
+typedef std::function<void(const Node::Index&,
+                           const NonNegativeInteger&,
+                           ndn::ConstBufferPtr)> RootUpdateCallback;
+
+class SubTreeBinary
+{
+public:
+  class Error : public std::runtime_error
+  {
+  public:
+    explicit
+    Error(const std::string& what)
+      : std::runtime_error(what)
+    {
+    }
+  };
+
+public:
+  /**
+   * @brief Constructor
+   *
+   * Create an empty subtree.
+   *
+   * @param loggerName The name of logger
+   * @param completeCallback Callback when the subtree is complete
+   * @param rootUpdateCallback Callback when the subtree root is updated
+   */
+  SubTreeBinary(const Name& loggerName,
+                const CompleteCallback& completeCallback,
+                const RootUpdateCallback& rootUpdateCallback);
+  /**
+   * @brief Constructor
+   *
+   * Create a subtree with its first leaf node hash.
+   *
+   * @param loggerName The name of logger
+   * @param rootIndex The index of sub tree root when it is full
+   * @param completeCallback Callback when the subtree is complete
+   * @param rootUpdateCallback Callback when the subtree root is updated
+   */
+  SubTreeBinary(const Name& loggerName,
+                const Node::Index& rootIndex,
+                const CompleteCallback& completeCallback,
+                const RootUpdateCallback& rootUpdateCallback);
+
+  const Node::Index&
+  getPeakIndex() const
+  {
+    return m_peakIndex;
+  }
+
+  const NonNegativeInteger&
+  getMinSeqNo() const
+  {
+    return m_minSeqNo;
+  }
+
+  const NonNegativeInteger&
+  getMaxSeqNo() const
+  {
+    return m_maxSeqNo;
+  }
+
+  size_t
+  getLeafLevel() const
+  {
+    return m_leafLevel;
+  }
+
+  const NonNegativeInteger&
+  getNextLeafSeqNo() const;
+
+  /**
+   * @brief get the root of the subtree
+   *
+   * @return pointer to the root, nullptr if no leaf added
+   */
+  ConstNodePtr
+  getRoot() const
+  {
+    return m_actualRoot;
+  }
+
+  ndn::ConstBufferPtr
+  getRootHash() const;
+
+  ConstNodePtr
+  getNode(const Node::Index& index) const;
+
+  bool
+  addLeaf(NodePtr leaf);
+
+  bool
+  updateLeaf(const NonNegativeInteger& nextSeqNo, ndn::ConstBufferPtr hash);
+
+  bool
+  isFull() const;
+
+  shared_ptr<Data>
+  encode() const;
+
+  void
+  decode(const Data& data);
+
+public:
+  static Node::Index
+  toSubTreePeakIndex(const Node::Index& index, bool notRoot = true);
+
+private:
+  void
+  initialize(const Node::Index& peakIndex);
+
+  void
+  updateActualRoot(NodePtr node);
+
+  void
+  updateParentNode(NodePtr node);
+
+public:
+  static const size_t SUB_TREE_DEPTH;
+
+NSL_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
+  static const time::milliseconds INCOMPLETE_FRESHNESS_PERIOD;
+  static const std::string COMPONENT_COMPLETE;
+  static const ssize_t OFFSET_ROOTHASH;
+  static const ssize_t OFFSET_COMPLETE;
+  static const ssize_t OFFSET_SEQNO;
+  static const ssize_t OFFSET_LEVEL;
+  static const size_t N_LOGGER_SUFFIX;
+
+private:
+  Name m_loggerName;
+  Node::Index m_peakIndex;
+  NonNegativeInteger m_minSeqNo;
+  NonNegativeInteger m_maxSeqNo;
+  size_t m_leafLevel;
+
+  CompleteCallback m_completeCallback;
+  RootUpdateCallback m_rootUpdateCallback;
+
+  NodePtr m_actualRoot;
+  bool m_isPendingLeafEmpty;
+  NonNegativeInteger m_pendingLeafSeqNo;
+
+  std::map<Node::Index, NodePtr> m_nodes;
+};
+
+typedef shared_ptr<SubTreeBinary> SubTreeBinaryPtr;
+typedef shared_ptr<const SubTreeBinary> ConstSubTreeBinaryPtr;
+
+} // namespace nsl
+
+#endif // NSL_CORE_SUB_TREE_HPP
diff --git a/core/sub-tree.cpp b/core/sub-tree.cpp
deleted file mode 100644
index 46f3f5c..0000000
--- a/core/sub-tree.cpp
+++ /dev/null
@@ -1,213 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014,  Regents of the University of California
- *
- * This file is part of NSL (NDN Signature Logger).
- * See AUTHORS.md for complete list of NSL authors and contributors.
- *
- * NSL is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
- */
-
-#include "sub-tree.hpp"
-#include "Auditor.hpp"
-#include <math.h>
-
-
-namespace nsl {
-
-void
-SubTree::addNode(ndn::ConstBufferPtr hash_ptr)
-{
-  if(m_remainPosition > 0)
-    {
-      uint8_t seqNo = 127 - m_remainPosition;
-      m_nodeHashes[seqNo] = ndn::make_shared<ndn::Buffer>(*hash_ptr);
-      m_remainPosition -= 1;
-      updateHash();
-    }
-}
-
-void
-SubTree::updateHash()
-{
-  uint8_t i_ = 6;
-  uint8_t lastNo = 126 - m_remainPosition;
-  for (; i_ > 0; i_--)
-    {
-      for (int i = int(pow(2, i_)) - 1; i <= lastNo; i+= 2)
-        {
-          if ((i + 1) <= lastNo)
-            {
-              uint8_t up_idx = (i-1) / 2;
-              Auditor hasher;
-              ndn::ConstBufferPtr buf = hasher.computeHash(m_nodeHashes[i],
-                                                           m_nodeHashes[i + 1]);
-              m_nodeHashes[up_idx] = ndn::make_shared<ndn::Buffer>(*buf);
-            }
-          else
-            {
-              uint8_t up_idx = (i-1) / 2;
-              Auditor hasher;
-              ndn::ConstBufferPtr buf = hasher.computeHashOneSide(m_nodeHashes[i]);
-              m_nodeHashes[up_idx] = ndn::make_shared<ndn::Buffer>(*buf);
-            }
-        }
-      lastNo = (lastNo - 1) / 2;
-    }
-  m_callBackUpdate(m_remainPosition, m_nodeHashes[0]);
-}
-
-
-
-
-void
-SubTree::updateLeafHash(Index subRootIndex, ndn::ConstBufferPtr hash)
-{
-  uint8_t lastNo = 126 - m_remainPosition;
-  uint64_t sequenceNo = subRootIndex.number;
-  uint64_t level = subRootIndex.level;
-  uint8_t indexBase = int(pow(2, m_root.level - level) - 1);
-  uint8_t indexOffset = (sequenceNo - m_root.number) / int(pow(2, level));
-  m_nodeHashes[indexBase + indexOffset] = ndn::make_shared<ndn::Buffer>(*hash);
-  if (lastNo < indexBase + indexOffset) // update value ? add new value
-    {
-      m_remainPosition -= 1;
-    }
-  updateHash();
-}
-
-ndn::ConstBufferPtr
-SubTree::getHash(Index nodeIndex)
-{
-  uint64_t sequenceNo = nodeIndex.number;
-  uint64_t level = nodeIndex.level;
-  uint8_t indexBase = int(pow(2, m_root.level - level) - 1);
-  uint8_t indexOffset = (sequenceNo - m_root.number) / int(pow(2, level));
-  return m_nodeHashes[indexBase + indexOffset];
-}
-
-
-
-
-Index
-SubTree::getRootIndex()
-{
-  return m_root;
-}
-
-uint8_t
-SubTree::getRemainPosition()
-{
-  return m_remainPosition;
-}
-
-Index
-SubTree::getParentRootIndex()
-{
-  Index parentIndex;
-  parentIndex.number = m_root.number;
-  parentIndex.level = m_root.level;
-  for (int i = 0; i < 6; i++)
-    {
-      parentIndex.number -= parentIndex.number%int(pow(2, parentIndex.level + 1));
-      parentIndex.level += 1;
-    }
-  return parentIndex;
-}
-
-
-
-std::string
-SubTree::encoding()
-{
-  std::string subTreeInfo = "";
-  uint64_t seq = m_root.number;
-  uint64_t lev = m_root.level;
-  unsigned char div_seq[8];
-  unsigned char div_lev[8];
-  for (int i = 0; i < 8; i++)
-    {
-      div_seq[i] = (seq >> (8*i)) & 0xFF;
-      div_lev[i] = (lev >> (8*i)) & 0xFF;
-    }
-  for (int i = 0; i < 8; i++)
-    {
-      subTreeInfo += div_seq[i];
-    }
-  for (int i = 0; i < 8; i++)
-    {
-      subTreeInfo += div_lev[i];
-    }
-  subTreeInfo += m_remainPosition;
-  for (int i = 0; i < 127; i++)
-    {
-      for (int j = 0; j < m_nodeHashes[i]->size(); j++)
-        {
-          subTreeInfo += (*m_nodeHashes[i])[j];
-        }
-      uint8_t flag = 0;
-      for (int j = m_nodeHashes[i]->size(); j < 32; j++)
-        {
-          subTreeInfo += flag;
-        }
-    }
-  return subTreeInfo;
-}
-
-void
-SubTree::resumeFromString(uint8_t remain, std::vector<ndn::BufferPtr> hashes)
-{
-  m_remainPosition = remain;
-  if (remain == 0)
-    {
-      for (int i = 0; i < hashes.size(); i++)
-        {
-          m_nodeHashes[i] = hashes[i];
-        }
-    }
-  else
-    {
-      for (int i = 0; i < hashes.size(); i++)
-        {
-          m_nodeHashes[63 + i] = hashes[i];
-        }
-      uint8_t i_ = 6;
-      uint8_t lastNo = 126 - m_remainPosition;
-      for (; i_ > 0; i_--)
-        {
-          for (int i = int(pow(2, i_)) - 1; i <= lastNo; i+= 2)
-            {
-              if ((i + 1) <= lastNo)
-                {
-                  uint8_t up_idx = (i-1) / 2;
-                  Auditor hasher;
-                  ndn::ConstBufferPtr buf = hasher.computeHash(m_nodeHashes[i],
-                                                               m_nodeHashes[i + 1]);
-                  m_nodeHashes[up_idx] = ndn::make_shared<ndn::Buffer>(*buf);
-                }
-              else
-                {
-                  uint8_t up_idx = (i-1) / 2;
-                  Auditor hasher;
-                  ndn::ConstBufferPtr buf = hasher.computeHashOneSide(m_nodeHashes[i]);
-                  m_nodeHashes[up_idx] = ndn::make_shared<ndn::Buffer>(*buf);
-                }
-            }
-          lastNo = (lastNo - 1) / 2;
-        }
-    }
-}
-
-
-} // namespace nsl
diff --git a/core/sub-tree.hpp b/core/sub-tree.hpp
deleted file mode 100644
index 55a0f53..0000000
--- a/core/sub-tree.hpp
+++ /dev/null
@@ -1,105 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014,  Regents of the University of California
- *
- * This file is part of NSL (NDN Signature Logger).
- * See AUTHORS.md for complete list of NSL authors and contributors.
- *
- * NSL is free software: you can redistribute it and/or modify it under the terms
- * of the GNU General Public License as published by the Free Software Foundation,
- * either version 3 of the License, or (at your option) any later version.
- *
- * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
- * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
- * PURPOSE.  See the GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along with
- * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * @author Peizhen Guo <patrick.guopz@gmail.com>
- */
-#ifndef NLS_CORE_SUB_TREE_CACHE_HPP
-#define NLS_CORE_SUB_TREE_CACHE_HPP
-
-#include <ndn-cxx/encoding/buffer.hpp>
-#include <stdint.h>
-#include <string.h>
-
-#include "node.hpp"
-
-namespace nsl {
-
-typedef ndn::function<void(uint8_t, ndn::ConstBufferPtr)> CallBack;
-
-class SubTree
-{
-public:
-  SubTree()
-  {
-  }
-
-  SubTree(Index rootIndex, CallBack callBackFunction)
-    : m_root(rootIndex),
-      m_remainPosition(64),
-      m_callBackUpdate(callBackFunction)
-  {
-    for (int i = 0; i < 127; i++)
-      {
-        m_nodeHashes.push_back(ndn::BufferPtr(new ndn::Buffer));
-      }
-  }
-
-  ~SubTree()
-  {
-  }
-
-  void
-  addNode(ndn::ConstBufferPtr hash_ptr);
-
-  Index
-  getRootIndex();
-
-  uint8_t
-  getRemainPosition();
-
-  Index
-  getParentRootIndex();
-
-  ndn::ConstBufferPtr
-  getHash(Index nodeIndex);
-
-  // change when subtree's root hash below it changes
-  void
-  updateLeafHash(Index subRootIndex, ndn::ConstBufferPtr hash);
-
-
-  // decode is implemented in MerkleTreeCache class
-  std::string
-  encoding();
-
-  void
-  resumeFromString(uint8_t remain, std::vector<ndn::BufferPtr> hashes);
-
-private:
-
-  void
-  updateHash();
-
-
-private:
-
-  //Based on the following sequence number
-  //         0
-  //    1          2
-  //  3   4     5     6
-  // 7 8 9 10 11 12 13 14
-  std::vector<ndn::BufferPtr> m_nodeHashes;
-  Index m_root;
-  uint8_t m_remainPosition;
-  CallBack m_callBackUpdate;
-};
-
-
-} // namespace nsl
-
-#endif // NLS_CORE_SUB_TREE_CACHE_HPP
diff --git a/core/tlv.hpp b/core/tlv.hpp
index e69de29..6dd7cac 100644
--- a/core/tlv.hpp
+++ b/core/tlv.hpp
@@ -0,0 +1,42 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014,  Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+
+#ifndef NSL_CORE_TLV_HPP
+#define NSL_CORE_TLV_HPP
+
+namespace nsl {
+namespace tlv {
+
+/**
+ * @brief Type value of leaf related TLVs
+ */
+enum {
+  LoggerLeaf  = 128, // 0x80
+  Timestamp   = 129, // 0x81
+  DataSeqNo   = 130, // 0x82
+  SignerSeqNo = 131  // 0x83
+};
+
+} // namespace tlv
+} // namespace nsl
+
+#endif // NSL_CORE_TLV_HPP
diff --git a/core/util/non-negative-integer.hpp b/core/util/non-negative-integer.hpp
new file mode 100644
index 0000000..eecef0f
--- /dev/null
+++ b/core/util/non-negative-integer.hpp
@@ -0,0 +1,31 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014,  Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#ifndef NSL_UTIL_NON_NEGATIVE_INTEGER_HPP
+#define NSL_UTIL_NON_NEGATIVE_INTEGER_HPP
+
+namespace nsl {
+
+typedef uint64_t NonNegativeInteger;
+
+} // namespace nsl
+
+#endif // NSL_UTIL_NON_NEGATIVE_INTEGER_HPP
diff --git a/core/util/timestamp.hpp b/core/util/timestamp.hpp
new file mode 100644
index 0000000..a955e1c
--- /dev/null
+++ b/core/util/timestamp.hpp
@@ -0,0 +1,31 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014,  Regents of the University of California
+ *
+ * This file is part of NSL (NDN Signature Logger).
+ * See AUTHORS.md for complete list of NSL authors and contributors.
+ *
+ * NSL is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NSL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NSL, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of nsl authors and contributors.
+ */
+
+#ifndef NSL_UTIL_TIMESTAMP_HPP
+#define NSL_UTIL_TIMESTAMP_HPP
+
+namespace nsl {
+
+typedef uint64_t Timestamp;
+
+} // namespace nsl
+
+#endif // NSL_UTIL_TIMESTAMP_HPP