src/zcash/IncrementalMerkleTree.hpp

   1 #ifndef ZCINCREMENTALMERKLETREE_H_
   2 #define ZCINCREMENTALMERKLETREE_H_
   3
   4 #include <deque>
   5 #include <boost/optional.hpp>
   6 #include <boost/static_assert.hpp>
   7
   8 #include "uint256.h"
   9 #include "serialize.h"
  10
  11 #include "Zcash.h"
  12
  13 namespace libzcash {
  14
  15 class MerklePath {
  16 public:
  17     std::vector<std::vector<bool>> authentication_path;
  18     std::vector<bool> index;
  19
  20     ADD_SERIALIZE_METHODS;
  21
  22     template <typename Stream, typename Operation>
  23     inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
  24         READWRITE(authentication_path);
  25         READWRITE(index);
  26     }
  27
  28     MerklePath() { }
  29
  30     MerklePath(std::vector<std::vector<bool>> authentication_path, std::vector<bool> index)
  31     : authentication_path(authentication_path), index(index) { }
  32 };
  33
  34 template<size_t Depth, typename Hash>
  35 class EmptyMerkleRoots {
  36 public:
  37     EmptyMerkleRoots() {
  38         empty_roots.at(0) = Hash();
  39         for (size_t d = 1; d <= Depth; d++) {
  40             empty_roots.at(d) = Hash::combine(empty_roots.at(d-1), empty_roots.at(d-1));
  41         }
  42     }
  43     Hash empty_root(size_t depth) {
  44         return empty_roots.at(depth);
  45     }
  46 private:
  47     boost::array<Hash, Depth+1> empty_roots;
  48 };
  49
  50 template<size_t Depth, typename Hash>
  51 class IncrementalWitness;
  52
  53 template<size_t Depth, typename Hash>
  54 class IncrementalMerkleTree {
  55
  56 friend class IncrementalWitness<Depth, Hash>;
  57
  58 public:
  59     BOOST_STATIC_ASSERT(Depth >= 1);
  60
  61     IncrementalMerkleTree() { }
  62
  63     void append(Hash obj);
  64     Hash root() const {
  65         return root(Depth, std::deque<Hash>());
  66     }
  67
  68     IncrementalWitness<Depth, Hash> witness() const {
  69         return IncrementalWitness<Depth, Hash>(*this);
  70     }
  71
  72     ADD_SERIALIZE_METHODS;
  73
  74     template <typename Stream, typename Operation>
  75     inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
  76         READWRITE(left);
  77         READWRITE(right);
  78         READWRITE(parents);
  79
  80         wfcheck();
  81     }
  82
  83     static Hash empty_root() {
  84         return emptyroots.empty_root(Depth);
  85     }
  86
  87 private:
  88     static EmptyMerkleRoots<Depth, Hash> emptyroots;
  89     boost::optional<Hash> left;
  90     boost::optional<Hash> right;
  91
  92     // Collapsed "left" subtrees ordered toward the root of the tree.
  93     std::vector<boost::optional<Hash>> parents;
  94     MerklePath path(std::deque<Hash> filler_hashes = std::deque<Hash>()) const;
  95     Hash root(size_t depth, std::deque<Hash> filler_hashes = std::deque<Hash>()) const;
  96     bool is_complete(size_t depth = Depth) const;
  97     size_t next_depth(size_t skip) const;
  98     void wfcheck() const;
  99 };
 100
 101 template <size_t Depth, typename Hash>
 102 class IncrementalWitness {
 103 friend class IncrementalMerkleTree<Depth, Hash>;
 104
 105 public:
 106     MerklePath path() const {
 107         return tree.path(partial_path());
 108     }
 109
 110     Hash root() const {
 111         return tree.root(Depth, partial_path());
 112     }
 113
 114     void append(Hash obj);
 115
 116     ADD_SERIALIZE_METHODS;
 117
 118     template <typename Stream, typename Operation>
 119     inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
 120         READWRITE(tree);
 121         READWRITE(filled);
 122         READWRITE(cursor);
 123
 124         cursor_depth = tree.next_depth(filled.size());
 125     }
 126
 127 private:
 128     IncrementalMerkleTree<Depth, Hash> tree;
 129     std::vector<Hash> filled;
 130     boost::optional<IncrementalMerkleTree<Depth, Hash>> cursor;
 131     size_t cursor_depth;
 132     std::deque<Hash> partial_path() const;
 133     IncrementalWitness(IncrementalMerkleTree<Depth, Hash> tree) : tree(tree) {}
 134 };
 135
 136 class SHA256Compress : public uint256 {
 137 public:
 138     SHA256Compress() : uint256() {}
 139     SHA256Compress(uint256 contents) : uint256(contents) { }
 140
 141     static SHA256Compress combine(const SHA256Compress& a, const SHA256Compress& b);
 142 };
 143
 144 } // end namespace `libzcash`
 145
 146 typedef libzcash::IncrementalMerkleTree<INCREMENTAL_MERKLE_TREE_DEPTH, libzcash::SHA256Compress> ZCIncrementalMerkleTree;
 147 typedef libzcash::IncrementalMerkleTree<INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, libzcash::SHA256Compress> ZCTestingIncrementalMerkleTree;
 148
 149 typedef libzcash::IncrementalWitness<INCREMENTAL_MERKLE_TREE_DEPTH, libzcash::SHA256Compress> ZCIncrementalWitness;
 150 typedef libzcash::IncrementalWitness<INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, libzcash::SHA256Compress> ZCTestingIncrementalWitness;
 151
 152 #endif /* ZCINCREMENTALMERKLETREE_H_ */
 153