Line data    Source code

       1             : // Copyright (c) 2016-2020 The ZCash developers
       2             : // Copyright (c) 2020 The PIVX Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #include "test/test_pivx.h"
       7             : 
       8             : #include "test/data/merkle_roots_sapling.json.h"
       9             : #include "test/data/merkle_serialization_sapling.json.h"
      10             : #include "test/data/merkle_witness_serialization_sapling.json.h"
      11             : #include "test/data/merkle_path_sapling.json.h"
      12             : #include "test/data/merkle_commitments_sapling.json.h"
      13             : 
      14             : #include <iostream>
      15             : #include <stdexcept>
      16             : 
      17             : #include "utilstrencodings.h"
      18             : #include "version.h"
      19             : #include "serialize.h"
      20             : #include "streams.h"
      21             : 
      22             : #include "sapling/incrementalmerkletree.h"
      23             : #include "sapling/sapling_util.h"
      24             : 
      25             : #include "json_test_vectors.h"
      26             : 
      27             : #include <boost/test/unit_test.hpp>
      28             : 
      29             : 
      30             : BOOST_FIXTURE_TEST_SUITE(sapling_merkletree_tests, BasicTestingSetup)
      31             : 
      32             : template<typename A, typename B, typename C>
      33         152 : void expect_ser_test_vector(B& b, const C& c, const A& tree) {
      34         152 :     expect_test_vector<B, C>(b, c);
      35         152 : }
      36             : 
      37             : template<typename Tree, typename Witness>
      38           1 : void test_tree(
      39             :         UniValue commitment_tests,
      40             :         UniValue root_tests,
      41             :         UniValue ser_tests,
      42             :         UniValue witness_ser_tests,
      43             :         UniValue path_tests
      44             : )
      45             : {
      46           1 :     size_t witness_ser_i = 0;
      47           1 :     size_t path_i = 0;
      48             : 
      49           2 :     Tree tree;
      50             : 
      51             :     // The root of the tree at this point is expected to be the root of the
      52             :     // empty tree.
      53           3 :     BOOST_CHECK(tree.root() == Tree::empty_root());
      54             : 
      55             :     // The tree doesn't have a 'last' element added since it's blank.
      56           2 :     BOOST_CHECK_THROW(tree.last(), std::runtime_error);
      57             : 
      58             :     // The tree is empty.
      59           2 :     BOOST_CHECK(tree.size() == 0);
      60             : 
      61             :     // We need to witness at every single point in the tree, so
      62             :     // that the consistency of the tree and the merkle paths can
      63             :     // be checked.
      64           1 :     std::vector<Witness> witnesses;
      65             : 
      66          17 :     for (size_t i = 0; i < 16; i++) {
      67          16 :         uint256 test_commitment = uint256S(commitment_tests[i].get_str());
      68             : 
      69             :         // Witness here
      70          32 :         witnesses.push_back(tree.witness());
      71             : 
      72             :         // Now append a commitment to the tree
      73          16 :         tree.append(test_commitment);
      74             : 
      75             :         // Size incremented by one.
      76          32 :         BOOST_CHECK(tree.size() == i+1);
      77             : 
      78             :         // Last element added to the tree was `test_commitment`
      79          32 :         BOOST_CHECK(tree.last() == test_commitment);
      80             : 
      81             :         // Check tree root consistency
      82          16 :         expect_test_vector(root_tests[i], tree.root());
      83             : 
      84             :         // Check serialization of tree
      85          16 :         expect_ser_test_vector(ser_tests[i], tree, tree);
      86             : 
      87          16 :         bool first = true; // The first witness can never form a path
      88         152 :         for (Witness& wit : witnesses) {
      89             :             // Append the same commitment to all the witnesses
      90         136 :             wit.append(test_commitment);
      91             : 
      92         136 :             if (first) {
      93          32 :                 BOOST_CHECK_THROW(wit.path(), std::runtime_error);
      94          32 :                 BOOST_CHECK_THROW(wit.element(), std::runtime_error);
      95             :             } else {
      96         240 :                 auto path = wit.path();
      97         120 :                 expect_test_vector(path_tests[path_i++], path);
      98             :             }
      99             : 
     100             :             // Check witness serialization
     101         136 :             expect_ser_test_vector(witness_ser_tests[witness_ser_i++], wit, tree);
     102             : 
     103         272 :             BOOST_CHECK(wit.root() == tree.root());
     104             : 
     105         136 :             first = false;
     106             :         }
     107             :     }
     108             : 
     109             :     {
     110             :         // Tree should be full now
     111           3 :         BOOST_CHECK_THROW(tree.append(uint256()), std::runtime_error);
     112             : 
     113          17 :         for (Witness& wit : witnesses) {
     114          48 :             BOOST_CHECK_THROW(wit.append(uint256()), std::runtime_error);
     115             :         }
     116             :     }
     117           1 : }
     118             : 
     119             : #define MAKE_STRING(x) std::string((x), (x)+sizeof(x))
     120             : 
     121           2 : BOOST_AUTO_TEST_CASE(SaplingVectors) {
     122           3 :     UniValue root_tests = read_json(MAKE_STRING(json_tests::merkle_roots_sapling));
     123           3 :     UniValue ser_tests = read_json(MAKE_STRING(json_tests::merkle_serialization_sapling));
     124           3 :     UniValue witness_ser_tests = read_json(MAKE_STRING(json_tests::merkle_witness_serialization_sapling));
     125           3 :     UniValue path_tests = read_json(MAKE_STRING(json_tests::merkle_path_sapling));
     126           2 :     UniValue commitment_tests = read_json(MAKE_STRING(json_tests::merkle_commitments_sapling));
     127             : 
     128           1 :     test_tree<SaplingTestingMerkleTree, SaplingTestingWitness>(
     129             :             commitment_tests,
     130             :             root_tests,
     131             :             ser_tests,
     132             :             witness_ser_tests,
     133             :             path_tests
     134             :     );
     135           1 : }
     136             : 
     137           2 : BOOST_AUTO_TEST_CASE(emptyroots) {
     138           1 :     libzcash::EmptyMerkleRoots<64, libzcash::SHA256Compress> emptyroots;
     139          66 :     std::array<libzcash::SHA256Compress, 65> computed;
     140             : 
     141           1 :     computed.at(0) = libzcash::SHA256Compress::uncommitted();
     142           2 :     BOOST_CHECK(emptyroots.empty_root(0) == computed.at(0));
     143          65 :     for (size_t d = 1; d <= 64; d++) {
     144          64 :     computed.at(d) = libzcash::SHA256Compress::combine(computed.at(d-1), computed.at(d-1), d-1);
     145         128 :     BOOST_CHECK(emptyroots.empty_root(d) == computed.at(d));
     146             :     }
     147             : 
     148             :     // Double check that we're testing (at least) all the empty roots we'll use.
     149           2 :     BOOST_CHECK(INCREMENTAL_MERKLE_TREE_DEPTH <= 64);
     150           1 : }
     151             : 
     152           2 : BOOST_AUTO_TEST_CASE(EmptyrootsSapling) {
     153           1 :     libzcash::EmptyMerkleRoots<62, libzcash::PedersenHash> emptyroots;
     154          64 :     std::array<libzcash::PedersenHash, 63> computed;
     155             : 
     156           1 :     computed.at(0) = libzcash::PedersenHash::uncommitted();
     157           2 :     BOOST_CHECK(emptyroots.empty_root(0) == computed.at(0));
     158          63 :     for (size_t d = 1; d <= 62; d++) {
     159          62 :         computed.at(d) = libzcash::PedersenHash::combine(computed.at(d-1), computed.at(d-1), d-1);
     160         124 :         BOOST_CHECK(emptyroots.empty_root(d) == computed.at(d));
     161             :     }
     162             : 
     163             :     // Double check that we're testing (at least) all the empty roots we'll use.
     164           2 :     BOOST_CHECK(INCREMENTAL_MERKLE_TREE_DEPTH <= 62);
     165           1 : }
     166             : 
     167           2 : BOOST_AUTO_TEST_CASE(EmptyrootSapling) {
     168             :     // This literal is the depth-32 empty tree root with the bytes reversed to
     169             :     // account for the fact that uint256S() loads a big-endian representation of
     170             :     // an integer which converted to little-endian internally.
     171           1 :     uint256 expected = uint256S("3e49b5f954aa9d3545bc6c37744661eea48d7c34e3000d82b7f0010c30f4c2fb");
     172             : 
     173           3 :     BOOST_CHECK(SaplingMerkleTree::empty_root() == expected);
     174           1 : }
     175             : 
     176             : BOOST_AUTO_TEST_SUITE_END()