core: Add Mtree
Change-Id: I80205fb0d1f4ee5bcbc6c73651bb697fe854bf53
diff --git a/core/merkle-tree-cache.cpp b/core/merkle-tree-cache.cpp
new file mode 100644
index 0000000..a7f2dc0
--- /dev/null
+++ b/core/merkle-tree-cache.cpp
@@ -0,0 +1,353 @@
+/* -*- 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
new file mode 100644
index 0000000..97e8908
--- /dev/null
+++ b/core/merkle-tree-cache.hpp
@@ -0,0 +1,176 @@
+/* -*- 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
new file mode 100644
index 0000000..1844ad4
--- /dev/null
+++ b/core/merkle-tree-sqlite3.cpp
@@ -0,0 +1,332 @@
+/* -*- 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
new file mode 100644
index 0000000..617d20c
--- /dev/null
+++ b/core/merkle-tree-sqlite3.hpp
@@ -0,0 +1,86 @@
+/* -*- 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
new file mode 100644
index 0000000..f74af33
--- /dev/null
+++ b/core/merkle-tree.cpp
@@ -0,0 +1,140 @@
+/* -*- 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.hpp"
+
+namespace nsl {
+
+MerkleTree::MerkleTree()
+{
+ m_nLevels = 0;
+ m_nLeaves = 0;
+}
+
+
+ConstNodePtr
+MerkleTree::getNode(const Index& index)
+{
+ ConstNodePtr p_leav;
+ if (m_cache.doesNodeExist(index))
+ {
+ p_leav = m_cache.queryNode(index);
+ return p_leav;
+ }
+ else
+ return p_leav;
+}
+
+
+uint64_t
+MerkleTree::getLeafNum() const
+{
+ return m_nLeaves;
+}
+
+
+uint64_t
+MerkleTree::getLevel() const
+{
+ return m_nLevels;
+}
+
+
+
+uint64_t
+MerkleTree::addLeaf(ndn::ConstBufferPtr info)
+{
+ 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;
+}
+
+
+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
diff --git a/core/merkle-tree.hpp b/core/merkle-tree.hpp
new file mode 100644
index 0000000..ccf73c5
--- /dev/null
+++ b/core/merkle-tree.hpp
@@ -0,0 +1,75 @@
+/* -*- 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_HPP
+#define NLS_CORE_MERKLE_TREE_HPP
+
+#include <map>
+#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()
+ {
+ }
+
+ ConstNodePtr
+ getNode(const Index& index);
+
+ uint64_t
+ getLeafNum() const;
+
+ uint64_t
+ getLevel() const;
+
+
+ //return root hash value
+ uint64_t
+ addLeaf(ndn::ConstBufferPtr info);
+
+
+ std::vector<ConstNodePtr>
+ generateProof(uint64_t version1, uint64_t version2); // version equals to leaf's index number
+
+
+private:
+ MerkleTreeCache m_cache;
+ uint64_t m_nLevels;
+ uint64_t m_nLeaves;
+
+};
+
+
+} // namespace nsl
+
+#endif // NLS_CORE_MERKLE_TREE_HPP
diff --git a/core/sub-tree.cpp b/core/sub-tree.cpp
new file mode 100644
index 0000000..46f3f5c
--- /dev/null
+++ b/core/sub-tree.cpp
@@ -0,0 +1,213 @@
+/* -*- 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
new file mode 100644
index 0000000..55a0f53
--- /dev/null
+++ b/core/sub-tree.hpp
@@ -0,0 +1,105 @@
+/* -*- 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/tests/core/test-merkle-tree-cache.cpp b/tests/core/test-merkle-tree-cache.cpp
new file mode 100644
index 0000000..12e534a
--- /dev/null
+++ b/tests/core/test-merkle-tree-cache.cpp
@@ -0,0 +1,143 @@
+/* -*- 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 <boost-test.hpp>
+#include <iostream>
+
+#include "merkle-tree-cache.hpp"
+#include "Auditor.hpp"
+
+
+namespace nsl {
+
+boost::test_tools::predicate_result check_buffer_cache(ndn::ConstBufferPtr ptr1,
+ ndn::ConstBufferPtr ptr2)
+{
+ bool result = true;
+ for (int i = 0; i < ptr1->size(); i++)
+ {
+ if ((*ptr1)[i] != (*ptr2)[i])
+ {
+ result = false;
+ break;
+ }
+ }
+ return result;
+}
+
+BOOST_AUTO_TEST_SUITE(TestCache)
+
+BOOST_AUTO_TEST_CASE(TestFunction)
+{
+ // Test build
+ ndn::Buffer buf[200];
+ Index idx[200];
+ for (uint8_t i = 0; i < 200; i++)
+ {
+ buf[i].push_back(i);
+ idx[i].number = i;
+ idx[i].level = 0;
+ }
+ MerkleTreeCache treeCache;
+ for (int i = 0; i < 200; i++)
+ {
+ ndn::ConstBufferPtr p_buf = ndn::make_shared<ndn::Buffer>(buf[i]);
+ Leaf newleaf(p_buf, idx[i].number, idx[i].level, 0);
+ newleaf.computeHash();
+ treeCache.addLeaf(newleaf);
+ BOOST_CHECK(treeCache.getLeaves() == i + 1);
+ }
+ BOOST_CHECK(treeCache.getLevel() == 2 && treeCache.getLeaves() == 200);
+ // std::cout<<treeCache.m_cachedTree.size()<<' '<<treeCache.m_leavesData.size()<<std::endl;
+
+ // Test query
+ ndn::ConstBufferPtr data_buf90 = ((Leaf*)(treeCache.queryNode(idx[90]).get()))->getData();
+ BOOST_CHECK(int((*data_buf90)[0]) == 90);
+ ndn::ConstBufferPtr data_buf10 = ((Leaf*)(treeCache.queryNode(idx[10]).get()))->getData();
+ BOOST_CHECK(int((*data_buf10)[0]) == 10);
+
+ ndn::ConstBufferPtr hash_buf1 = ((Leaf*)(treeCache.queryNode(idx[0]).get()))->getHash();
+ ndn::ConstBufferPtr hash_buf2 = ((Leaf*)(treeCache.queryNode(idx[1]).get()))->getHash();
+ ndn::ConstBufferPtr hash_buf3 = ((Leaf*)(treeCache.queryNode(idx[2]).get()))->getHash();
+ ndn::ConstBufferPtr hash_buf4 = ((Leaf*)(treeCache.queryNode(idx[3]).get()))->getHash();
+ Auditor audit;
+ ndn::ConstBufferPtr hash_buf5 = audit.computeHash(hash_buf1, hash_buf2);
+ ndn::ConstBufferPtr hash_buf6 = audit.computeHash(hash_buf3, hash_buf4);
+ ndn::ConstBufferPtr hash_buf7 = audit.computeHash(hash_buf5, hash_buf6);
+ Index idx1;
+ idx1.number = 0; idx1.level = 2;
+ ndn::ConstBufferPtr hash_buf8 = ((IntermediateNode*)(treeCache.queryNode(idx1).get()))->getHash();
+ BOOST_CHECK(check_buffer_cache(hash_buf7, hash_buf8));
+ idx1.number = 70; idx1.level = 1;
+ ndn::ConstBufferPtr hash_buf70 = ((Leaf*)(treeCache.queryNode(idx[70]).get()))->getHash();
+ ndn::ConstBufferPtr hash_buf71 = ((Leaf*)(treeCache.queryNode(idx[71]).get()))->getHash();
+ ndn::ConstBufferPtr hash_buf72 = audit.computeHash(hash_buf70, hash_buf71);
+ ndn::ConstBufferPtr hash_buf73 = ((IntermediateNode*)
+ (treeCache.queryNode(idx1).get()))->getHash();
+ BOOST_CHECK(check_buffer_cache(hash_buf72, hash_buf73));
+
+ // Test Encoding Decoding
+ idx1.number = 0; idx1.level = 12;
+ SubTreePtr sub_ptr1 = treeCache.getSubTree(idx1);
+ std::string tmp_str = sub_ptr1->encoding();
+ SubTreePtr sub_ptr2 = treeCache.decoding(tmp_str);
+ BOOST_CHECK(sub_ptr1->getRootIndex().number == sub_ptr2->getRootIndex().number &&
+ sub_ptr1->getRootIndex().level == sub_ptr2->getRootIndex().level);
+ BOOST_CHECK(sub_ptr1->getRemainPosition() == sub_ptr2->getRemainPosition());
+ idx1.number = 0; idx1.level = 10;
+ ndn::ConstBufferPtr origin_buf = sub_ptr1->getHash(idx1);
+ ndn::ConstBufferPtr resume_buf = sub_ptr2->getHash(idx1);
+ BOOST_CHECK(check_buffer_cache(origin_buf, resume_buf));
+
+
+ // Test Sqlite3 (move m_database to public to test)
+ /*
+ idx1.number = 0; idx1.level = 12;
+ treeCache.m_database.addSubTree(sub_ptr1);
+ std::string str = treeCache.m_database.getSubTree(idx1);
+ SubTreePtr sub_ptr_sql = treeCache.decoding(str);
+ BOOST_CHECK(sub_ptr1->getRootIndex().number == sub_ptr_sql->getRootIndex().number &&
+ sub_ptr1->getRootIndex().level == sub_ptr_sql->getRootIndex().level);
+ BOOST_CHECK(sub_ptr1->getRemainPosition() == sub_ptr_sql->getRemainPosition());
+ idx1.number = 0; idx1.level = 10;
+ origin_buf = sub_ptr1->getHash(idx1);
+ resume_buf = sub_ptr_sql->getHash(idx1);
+ BOOST_CHECK(check_buffer_cache(origin_buf, resume_buf));
+ idx1.number = 0; idx1.level = 12;
+ BOOST_CHECK(treeCache.m_database.doesSubTreeExist(idx1) == true);
+ idx1.number = 300; idx1.level = 2;
+ BOOST_CHECK(treeCache.m_database.doesSubTreeExist(idx1) == false);
+
+ uint64_t sequence = 90;
+ treeCache.m_database.addLeafInfo(sequence, data_buf90);
+ ndn::ConstBufferPtr data_buf_sql = treeCache.m_database.getLeafInfo(sequence);
+ BOOST_CHECK(int((*data_buf_sql)[0]) == 90);
+ BOOST_CHECK(treeCache.m_database.doesLeafInfoExist(400) == false);
+ // insert update
+ treeCache.m_database.addLeafInfo(sequence, data_buf10);
+ data_buf_sql = treeCache.m_database.getLeafInfo(sequence);
+ BOOST_CHECK(int((*data_buf_sql)[0]) == 10);
+ */
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace nsl
diff --git a/tests/core/test-merkle-tree-sqlite3.cpp b/tests/core/test-merkle-tree-sqlite3.cpp
new file mode 100644
index 0000000..683fa1d
--- /dev/null
+++ b/tests/core/test-merkle-tree-sqlite3.cpp
@@ -0,0 +1,38 @@
+/* -*- 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 <boost-test.hpp>
+#include <iostream>
+
+#include "merkle-tree-sqlite3.hpp"
+#include "sub-tree.hpp"
+
+namespace nsl {
+
+BOOST_AUTO_TEST_SUITE(TestSqlite3)
+
+BOOST_AUTO_TEST_CASE(TestInit)
+{
+ MerkleTreeSqlite3 database;
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace nsl
diff --git a/tests/core/test-merkle-tree.cpp b/tests/core/test-merkle-tree.cpp
new file mode 100644
index 0000000..2260ccf
--- /dev/null
+++ b/tests/core/test-merkle-tree.cpp
@@ -0,0 +1,198 @@
+/* -*- 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 <boost-test.hpp>
+#include <iostream>
+
+#include "merkle-tree.hpp"
+
+namespace nsl {
+
+boost::test_tools::predicate_result check_buffer(ndn::ConstBufferPtr ptr1, ndn::ConstBufferPtr ptr2)
+{
+ bool result = true;
+ for (int i = 0; i < ptr1->size(); i++)
+ {
+ if ((*ptr1)[i] != (*ptr2)[i])
+ {
+ result = false;
+ break;
+ }
+ }
+ return result;
+}
+
+BOOST_AUTO_TEST_SUITE(TestTree)
+
+
+BOOST_AUTO_TEST_CASE(TestBuild)
+{
+ std::string str1 = "peizhen";
+ std::string str2 = "guo";
+ std::string str3 = "is";
+ std::string str4 = "building";
+ std::string str5 = "this";
+ std::string str6 = "logging";
+ std::string str7 = "system";
+ ndn::Buffer buf1;
+ ndn::Buffer buf2;
+ ndn::Buffer buf3;
+ ndn::Buffer buf4;
+ ndn::Buffer buf5;
+ ndn::Buffer buf6;
+ ndn::Buffer buf7;
+ for (int i=0; i < str1.size(); i++)
+ buf1.push_back(uint8_t(str1[i]));
+ for (int i=0; i < str2.size(); i++)
+ buf2.push_back(uint8_t(str2[i]));
+ for (int i=0; i < str3.size(); i++)
+ buf3.push_back(uint8_t(str3[i]));
+ for (int i=0; i < str4.size(); i++)
+ buf4.push_back(uint8_t(str4[i]));
+ for (int i=0; i < str5.size(); i++)
+ buf5.push_back(uint8_t(str5[i]));
+ for (int i=0; i < str6.size(); i++)
+ buf6.push_back(uint8_t(str6[i]));
+ for (int i=0; i < str7.size(); i++)
+ buf7.push_back(uint8_t(str7[i]));
+ ndn::ConstBufferPtr buf_p1 = boost::make_shared<ndn::Buffer>(buf1);
+ ndn::ConstBufferPtr buf_p2 = boost::make_shared<ndn::Buffer>(buf2);
+ ndn::ConstBufferPtr buf_p3 = boost::make_shared<ndn::Buffer>(buf3);
+ ndn::ConstBufferPtr buf_p4 = boost::make_shared<ndn::Buffer>(buf4);
+ ndn::ConstBufferPtr buf_p5 = boost::make_shared<ndn::Buffer>(buf5);
+ ndn::ConstBufferPtr buf_p6 = boost::make_shared<ndn::Buffer>(buf6);
+ ndn::ConstBufferPtr buf_p7 = boost::make_shared<ndn::Buffer>(buf7);
+
+ //Test add/get function
+ MerkleTree merkle_tree;
+ merkle_tree.addLeaf(buf_p1);
+ Index idx;
+ idx.number = 0;
+ idx.level = 0;
+ ndn::ConstBufferPtr tmp_ptr = ((Leaf*)(merkle_tree.getNode(idx).get()))->getData();
+ BOOST_CHECK(merkle_tree.getLeafNum() == 1 && merkle_tree.getLevel() == 1
+ && merkle_tree.getLevel() == idx.level + 1);
+ BOOST_CHECK(check_buffer(tmp_ptr, buf_p1));
+
+ merkle_tree.addLeaf(buf_p2);
+ idx.number += 1;
+ BOOST_CHECK(check_buffer(((Leaf*)(merkle_tree.getNode(idx).get()))->getData(), buf_p2));
+ idx.number = 0;
+ idx.level = 1;
+ BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == true
+ && merkle_tree.getLeafNum() == 2 && merkle_tree.getLevel() == 2
+ && merkle_tree.getLevel() == idx.level + 1);
+
+
+ merkle_tree.addLeaf(buf_p3);
+ idx.number = 2; idx.level = 0;
+ BOOST_CHECK(check_buffer(((Leaf*)(merkle_tree.getNode(idx).get()))->getData(), buf_p3));
+ idx.level = 1;
+ BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == false);
+ idx.number = 0;
+ BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == true);
+ BOOST_CHECK(merkle_tree.getLeafNum() == 3 && merkle_tree.getLevel() == 3);
+
+
+ merkle_tree.addLeaf(buf_p4);
+ merkle_tree.addLeaf(buf_p5);
+ merkle_tree.addLeaf(buf_p6);
+ merkle_tree.addLeaf(buf_p7);
+ BOOST_CHECK(merkle_tree.getLeafNum() == 7 && merkle_tree.getLevel() == 4);
+ idx.level = 2;
+ idx.number = 4;
+ BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == false);
+ idx.level = 1;
+ idx.number = 2;
+ BOOST_CHECK(((IntermediateNode*)(merkle_tree.getNode(idx).get()))->isFull() == true);
+}
+
+
+
+BOOST_AUTO_TEST_CASE(TestGenerateProof)
+{
+
+ std::string str1 = "peizhen";
+ std::string str2 = "guo";
+ std::string str3 = "is";
+ std::string str4 = "building";
+ std::string str5 = "this";
+ std::string str6 = "logging";
+ std::string str7 = "system";
+ ndn::Buffer buf1;
+ ndn::Buffer buf2;
+ ndn::Buffer buf3;
+ ndn::Buffer buf4;
+ ndn::Buffer buf5;
+ ndn::Buffer buf6;
+ ndn::Buffer buf7;
+ for (int i=0; i < str1.size(); i++)
+ buf1.push_back(uint8_t(str1[i]));
+ for (int i=0; i < str2.size(); i++)
+ buf2.push_back(uint8_t(str2[i]));
+ for (int i=0; i < str3.size(); i++)
+ buf3.push_back(uint8_t(str3[i]));
+ for (int i=0; i < str4.size(); i++)
+ buf4.push_back(uint8_t(str4[i]));
+ for (int i=0; i < str5.size(); i++)
+ buf5.push_back(uint8_t(str5[i]));
+ for (int i=0; i < str6.size(); i++)
+ buf6.push_back(uint8_t(str6[i]));
+ for (int i=0; i < str7.size(); i++)
+ buf7.push_back(uint8_t(str7[i]));
+ ndn::ConstBufferPtr buf_p1 = boost::make_shared<ndn::Buffer>(buf1);
+ ndn::ConstBufferPtr buf_p2 = boost::make_shared<ndn::Buffer>(buf2);
+ ndn::ConstBufferPtr buf_p3 = boost::make_shared<ndn::Buffer>(buf3);
+ ndn::ConstBufferPtr buf_p4 = boost::make_shared<ndn::Buffer>(buf4);
+ ndn::ConstBufferPtr buf_p5 = boost::make_shared<ndn::Buffer>(buf5);
+ ndn::ConstBufferPtr buf_p6 = boost::make_shared<ndn::Buffer>(buf6);
+ ndn::ConstBufferPtr buf_p7 = boost::make_shared<ndn::Buffer>(buf7);
+
+
+ // Test genProof function
+ MerkleTree merkle_tree;
+ merkle_tree.addLeaf(buf_p1);
+ merkle_tree.addLeaf(buf_p2);
+ merkle_tree.addLeaf(buf_p3);
+ merkle_tree.addLeaf(buf_p4);
+ merkle_tree.addLeaf(buf_p5);
+ merkle_tree.addLeaf(buf_p6);
+ merkle_tree.addLeaf(buf_p7);
+ std::vector<ConstNodePtr> verifyPathPresent = merkle_tree.generateProof(2, 5);
+ std::vector<ConstNodePtr> verifyPathPrevious = merkle_tree.generateProof(4, 6);
+ Index idx;
+ for (int i = 0; i < verifyPathPresent.size(); i++)
+ {
+ idx = (verifyPathPresent[i])->getIndex();
+ std::cout << idx.number << "," << idx.level << std::endl;
+ }
+ std::cout << std::endl;
+ for (int i = 0; i < verifyPathPrevious.size(); i++)
+ {
+ idx = (verifyPathPrevious[i])->getIndex();
+ std::cout << idx.number << "," << idx.level << std::endl;
+ }
+}
+
+
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace nsl