Line data    Source code

       1             : // Copyright (c) 2016-2018 The Zcash developers
       2             : // Copyright (c) 2020-2021 The PIVX Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or https://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #ifndef PIVX_SAPLING_INCREMENTALMERKLETREE_H
       7             : #define PIVX_SAPLING_INCREMENTALMERKLETREE_H
       8             : 
       9             : #include "uint256.h"
      10             : #include "optional.h"
      11             : #include "serialize.h"
      12             : 
      13             : #include "sapling/sapling.h"
      14             : #include "sapling/sapling_util.h"
      15             : 
      16             : #include <array>
      17             : #include <deque>
      18             : 
      19             : namespace libzcash {
      20             : 
      21         313 : class MerklePath {
      22             : public:
      23             :     std::vector<std::vector<bool>> authentication_path;
      24             :     std::vector<bool> index;
      25             : 
      26             :     template<typename Stream>
      27         433 :     void Serialize(Stream &s) const
      28             :     {
      29           0 :         std::vector<std::vector<unsigned char>> pathBytes;
      30             :         uint64_t indexInt;
      31         433 :         assert(authentication_path.size() == index.size());
      32         433 :         pathBytes.resize(authentication_path.size());
      33        4209 :         for (size_t i = 0; i < authentication_path.size(); i++) {
      34        3776 :             pathBytes[i].resize((authentication_path[i].size()+7)/8);
      35      970432 :             for (unsigned int p = 0; p < authentication_path[i].size(); p++) {
      36      966656 :                 pathBytes[i][p / 8] |= authentication_path[i][p] << (7-(p % 8));
      37             :             }
      38             :         }
      39         433 :         indexInt = convertVectorToInt(index);
      40         433 :         ::Serialize(s, pathBytes);
      41         433 :         ::Serialize(s, indexInt);
      42         433 :     }
      43             : 
      44             :     template<typename Stream>
      45         120 :     void Unserialize(Stream &s)
      46             :     {
      47         120 :         std::vector<std::vector<unsigned char>> pathBytes;
      48             :         uint64_t indexInt;
      49         120 :         ::Unserialize(s, pathBytes);
      50         120 :         ::Unserialize(s, indexInt);
      51         120 :         MerklePath &us = *(const_cast<MerklePath*>(this));
      52         600 :         for (size_t i = 0; i < pathBytes.size(); i++) {
      53         960 :             us.authentication_path.push_back(convertBytesVectorToVector(pathBytes[i]));
      54         480 :             us.index.push_back((indexInt >> ((pathBytes.size() - 1) - i)) & 1);
      55             :         }
      56         120 :     }
      57             : 
      58         120 :     MerklePath() { }
      59             : 
      60         193 :     MerklePath(std::vector<std::vector<bool>> authentication_path, std::vector<bool> index)
      61         193 :     : authentication_path(authentication_path), index(index) { }
      62             : };
      63             : 
      64             : template<size_t Depth, typename Hash>
      65             : class EmptyMerkleRoots {
      66             : public:
      67         132 :     EmptyMerkleRoots() { }
      68     3388499 :     Hash empty_root(size_t depth) const {
      69     3388497 :         return Hash::EmptyRoot(depth);
      70             :     }
      71             :     template <size_t D, typename H>
      72             :     friend bool operator==(const EmptyMerkleRoots<D, H>& a,
      73             :                            const EmptyMerkleRoots<D, H>& b);
      74             : private:
      75             :     std::array<Hash, Depth+1> empty_roots;
      76             : };
      77             : 
      78             : template<size_t Depth, typename Hash>
      79           4 : bool operator==(const EmptyMerkleRoots<Depth, Hash>& a,
      80             :                 const EmptyMerkleRoots<Depth, Hash>& b) {
      81           4 :     return a.empty_roots == b.empty_roots;
      82             : }
      83             : 
      84             : template<size_t Depth, typename Hash>
      85             : class IncrementalWitness;
      86             : 
      87             : template<size_t Depth, typename Hash>
      88      655016 : class IncrementalMerkleTree {
      89             : 
      90             : friend class IncrementalWitness<Depth, Hash>;
      91             : 
      92             : public:
      93             :     BOOST_STATIC_ASSERT(Depth >= 1);
      94             : 
      95      166418 :     IncrementalMerkleTree() { }
      96             : 
      97       57599 :     size_t DynamicMemoryUsage() const {
      98             :         return 32 + // left
      99       57599 :                32 + // right
     100       57599 :                parents.size() * 32; // parents
     101             :     }
     102             : 
     103             :     size_t size() const;
     104             : 
     105             :     void append(Hash obj);
     106       86453 :     Hash root() const {
     107      172906 :         return root(Depth, std::deque<Hash>());
     108             :     }
     109             :     Hash last() const;
     110             : 
     111        1217 :     IncrementalWitness<Depth, Hash> witness() const {
     112        3651 :         return IncrementalWitness<Depth, Hash>(*this);
     113             :     }
     114             : 
     115        1832 :     SERIALIZE_METHODS(IncrementalMerkleTree, obj)
     116             :     {
     117        2742 :         READWRITE(obj.left, obj.right, obj.parents);
     118        2742 :         obj.wfcheck();
     119             :     }
     120             : 
     121       23008 :     static Hash empty_root() {
     122       23008 :         return emptyroots.empty_root(Depth);
     123             :     }
     124             : 
     125             :     template <size_t D, typename H>
     126             :     friend bool operator==(const IncrementalMerkleTree<D, H>& a,
     127             :                            const IncrementalMerkleTree<D, H>& b);
     128             : 
     129             : private:
     130             :     static EmptyMerkleRoots<Depth, Hash> emptyroots;
     131             :     Optional<Hash> left;
     132             :     Optional<Hash> right;
     133             : 
     134             :     // Collapsed "left" subtrees ordered toward the root of the tree.
     135             :     std::vector<Optional<Hash>> parents;
     136             :     MerklePath path(std::deque<Hash> filler_hashes = std::deque<Hash>()) const;
     137             :     Hash root(size_t depth, std::deque<Hash> filler_hashes = std::deque<Hash>()) const;
     138             :     bool is_complete(size_t depth = Depth) const;
     139             :     size_t next_depth(size_t skip) const;
     140             :     void wfcheck() const;
     141             : };
     142             : 
     143             : template<size_t Depth, typename Hash>
     144           4 : bool operator==(const IncrementalMerkleTree<Depth, Hash>& a,
     145             :                 const IncrementalMerkleTree<Depth, Hash>& b) {
     146           8 :     return (a.emptyroots == b.emptyroots &&
     147           4 :             a.left == b.left &&
     148          12 :             a.right == b.right &&
     149           4 :             a.parents == b.parents);
     150             : }
     151             : 
     152             : template <size_t Depth, typename Hash>
     153             : class IncrementalWitness {
     154             : friend class IncrementalMerkleTree<Depth, Hash>;
     155             : 
     156             : public:
     157             :     // Required for Unserialize()
     158         137 :     IncrementalWitness() {}
     159             : 
     160         209 :     MerklePath path() const {
     161         402 :         return tree.path(partial_path());
     162             :     }
     163             : 
     164             :     // Return the element being witnessed (should be a note
     165             :     // commitment!)
     166          16 :     Hash element() const {
     167          16 :         return tree.last();
     168             :     }
     169             : 
     170         976 :     uint64_t position() const {
     171         976 :         return tree.size() - 1;
     172             :     }
     173             : 
     174       19204 :     Hash root() const {
     175       38408 :         return tree.root(Depth, partial_path());
     176             :     }
     177             : 
     178             :     void append(Hash obj);
     179             : 
     180         138 :     SERIALIZE_METHODS(IncrementalWitness, obj)
     181             :     {
     182        1381 :         READWRITE(obj.tree, obj.filled, obj.cursor);
     183        1381 :         SER_READ(obj, obj.cursor_depth = obj.tree.next_depth(obj.filled.size()));
     184         137 :     }
     185             : 
     186             :     template <size_t D, typename H>
     187             :     friend bool operator==(const IncrementalWitness<D, H>& a,
     188             :                            const IncrementalWitness<D, H>& b);
     189             : 
     190             : private:
     191             :     IncrementalMerkleTree<Depth, Hash> tree;
     192             :     std::vector<Hash> filled;
     193             :     Optional<IncrementalMerkleTree<Depth, Hash>> cursor;
     194             :     size_t cursor_depth = 0;
     195             :     std::deque<Hash> partial_path() const;
     196        1217 :     explicit IncrementalWitness(IncrementalMerkleTree<Depth, Hash> tree) : tree(tree) {}
     197             : };
     198             : 
     199             : template<size_t Depth, typename Hash>
     200           4 : bool operator==(const IncrementalWitness<Depth, Hash>& a,
     201             :                 const IncrementalWitness<Depth, Hash>& b) {
     202           8 :     return (a.tree == b.tree &&
     203           4 :             a.filled == b.filled &&
     204          12 :             a.cursor == b.cursor &&
     205           4 :             a.cursor_depth == b.cursor_depth);
     206             : }
     207             : 
     208             : class SHA256Compress : public uint256 {
     209             : public:
     210         388 :     SHA256Compress() : uint256() {}
     211             :     SHA256Compress(uint256 contents) : uint256(contents) { }
     212             : 
     213             :     static SHA256Compress combine(
     214             :         const SHA256Compress& a,
     215             :         const SHA256Compress& b,
     216             :         size_t depth
     217             :     );
     218             : 
     219           1 :     static SHA256Compress uncommitted() {
     220           2 :         return SHA256Compress();
     221             :     }
     222             :     static SHA256Compress EmptyRoot(size_t);
     223             : };
     224             : 
     225             : class PedersenHash : public uint256 {
     226             : public:
     227     7341014 :     PedersenHash() : uint256() {}
     228      204968 :     PedersenHash(uint256 contents) : uint256(contents) { }
     229             : 
     230             :     static PedersenHash combine(
     231             :         const PedersenHash& a,
     232             :         const PedersenHash& b,
     233             :         size_t depth
     234             :     );
     235             : 
     236             :     static PedersenHash uncommitted();
     237             :     static PedersenHash EmptyRoot(size_t);
     238             : };
     239             : 
     240             : template<size_t Depth, typename Hash>
     241             : EmptyMerkleRoots<Depth, Hash> IncrementalMerkleTree<Depth, Hash>::emptyroots;
     242             : 
     243             : } // end namespace `libzcash`
     244             : 
     245             : typedef libzcash::IncrementalMerkleTree<SAPLING_INCREMENTAL_MERKLE_TREE_DEPTH, libzcash::PedersenHash> SaplingMerkleTree;
     246             : typedef libzcash::IncrementalMerkleTree<INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, libzcash::PedersenHash> SaplingTestingMerkleTree;
     247             : 
     248             : typedef libzcash::IncrementalWitness<SAPLING_INCREMENTAL_MERKLE_TREE_DEPTH, libzcash::PedersenHash> SaplingWitness;
     249             : typedef libzcash::IncrementalWitness<INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, libzcash::PedersenHash> SaplingTestingWitness;
     250             : 
     251             : #endif // PIVX_SAPLING_INCREMENTALMERKLETREE_H