refactor code
Change-Id: Ia2bc49ed8742d79000fd59f7e95fa9b957573c54
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