src/gtest/test_merkletree.cpp

   1 #include <gtest/gtest.h>
   2
   3 #include "test/data/merkle_roots.json.h"
   4 #include "test/data/merkle_roots_empty.json.h"
   5 #include "test/data/merkle_serialization.json.h"
   6 #include "test/data/merkle_witness_serialization.json.h"
   7 #include "test/data/merkle_path.json.h"
   8
   9 #include <iostream>
  10
  11 #include <stdexcept>
  12
  13 #include "utilstrencodings.h"
  14 #include "version.h"
  15 #include "serialize.h"
  16 #include "streams.h"
  17
  18 #include "zcash/IncrementalMerkleTree.hpp"
  19 #include "zcash/util.h"
  20
  21 #include "libsnark/common/default_types/r1cs_ppzksnark_pp.hpp"
  22 #include "libsnark/zk_proof_systems/ppzksnark/r1cs_ppzksnark/r1cs_ppzksnark.hpp"
  23 #include "libsnark/gadgetlib1/gadgets/hashes/sha256/sha256_gadget.hpp"
  24 #include "libsnark/gadgetlib1/gadgets/merkle_tree/merkle_tree_check_read_gadget.hpp"
  25
  26 #include <boost/foreach.hpp>
  27
  28 #include "json/json_spirit_reader_template.h"
  29 #include "json/json_spirit_utils.h"
  30 #include "json/json_spirit_writer_template.h"
  31
  32 using namespace json_spirit;
  33 Array
  34 read_json(const std::string& jsondata)
  35 {
  36     Value v;
  37
  38     if (!read_string(jsondata, v) || v.type() != array_type)
  39     {
  40         ADD_FAILURE();
  41         return Array();
  42     }
  43     return v.get_array();
  44 }
  45
  46 //#define PRINT_JSON 1
  47
  48 using namespace std;
  49 using namespace libsnark;
  50
  51
  52 template<typename T>
  53 void expect_deser_same(const T& expected)
  54 {
  55     CDataStream ss1(SER_NETWORK, PROTOCOL_VERSION);
  56     ss1 << expected;
  57
  58     auto serialized_size = ss1.size();
  59
  60     T object;
  61     ss1 >> object;
  62
  63     CDataStream ss2(SER_NETWORK, PROTOCOL_VERSION);
  64     ss2 << object;
  65
  66     ASSERT_TRUE(serialized_size == ss2.size());
  67     ASSERT_TRUE(memcmp(&*ss1.begin(), &*ss2.begin(), serialized_size) == 0);
  68 }
  69
  70 template<>
  71 void expect_deser_same(const ZCTestingIncrementalWitness& expected)
  72 {
  73     // Cannot check this; IncrementalWitness cannot be
  74     // deserialized because it can only be constructed by
  75     // IncrementalMerkleTree, and it does not yet have a
  76     // canonical serialized representation.
  77 }
  78
  79 template<>
  80 void expect_deser_same(const libzcash::MerklePath& expected)
  81 {
  82     // This deserialization check is pointless for MerklePath,
  83     // since we only serialize it to check it against test
  84     // vectors. See `expect_test_vector` for that. Also,
  85     // it doesn't seem that vector<bool> can be properly
  86     // deserialized by Bitcoin's serialization code.
  87 }
  88
  89 template<typename T, typename U>
  90 void expect_test_vector(T& it, const U& expected)
  91 {
  92     expect_deser_same(expected);
  93
  94     CDataStream ss1(SER_NETWORK, PROTOCOL_VERSION);
  95     ss1 << expected;
  96
  97     #ifdef PRINT_JSON
  98     std::cout << "\t\"" ;
  99     std::cout << HexStr(ss1.begin(), ss1.end()) << "\",\n";
 100     #else
 101     std::string raw = (it++)->get_str();
 102     CDataStream ss2(ParseHex(raw), SER_NETWORK, PROTOCOL_VERSION);
 103
 104     ASSERT_TRUE(ss1.size() == ss2.size());
 105     ASSERT_TRUE(memcmp(&*ss1.begin(), &*ss2.begin(), ss1.size()) == 0);
 106     #endif
 107 }
 108
 109 template<typename A, typename B, typename C>
 110 void expect_ser_test_vector(B& b, const C& c, const A& tree) {
 111     expect_test_vector<B, C>(b, c);
 112 }
 113
 114 template<typename Tree, typename Witness>
 115 void test_tree(Array root_tests, Array ser_tests, Array witness_ser_tests, Array path_tests) {
 116     Array::iterator root_iterator = root_tests.begin();
 117     Array::iterator ser_iterator = ser_tests.begin();
 118     Array::iterator witness_ser_iterator = witness_ser_tests.begin();
 119     Array::iterator path_iterator = path_tests.begin();
 120
 121     uint256 test_commitment = uint256S("e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855");
 122
 123     Tree tree;
 124
 125     // The root of the tree at this point is expected to be the root of the
 126     // empty tree.
 127     ASSERT_TRUE(tree.root() == Tree::empty_root());
 128
 129     // We need to witness at every single point in the tree, so
 130     // that the consistency of the tree and the merkle paths can
 131     // be checked.
 132     vector<Witness> witnesses;
 133
 134     for (size_t i = 0; i < 16; i++) {
 135         // Witness here
 136         witnesses.push_back(tree.witness());
 137
 138         // Now append a commitment to the tree
 139         tree.append(test_commitment);
 140
 141         // Check tree root consistency
 142         expect_test_vector(root_iterator, tree.root());
 143
 144         // Check serialization of tree
 145         expect_ser_test_vector(ser_iterator, tree, tree);
 146
 147         bool first = true; // The first witness can never form a path
 148         BOOST_FOREACH(Witness& wit, witnesses)
 149         {
 150             // Append the same commitment to all the witnesses
 151             wit.append(test_commitment);
 152
 153             if (first) {
 154                 ASSERT_THROW(wit.path(), std::runtime_error);
 155             } else {
 156                 auto path = wit.path();
 157
 158                 {
 159                     expect_test_vector(path_iterator, path);
 160
 161                     typedef Fr<default_r1cs_ppzksnark_pp> FieldT;
 162
 163                     protoboard<FieldT> pb;
 164                     pb_variable_array<FieldT> positions;
 165                     digest_variable<FieldT> commitment(pb, 256, "commitment");
 166                     digest_variable<FieldT> root(pb, 256, "root");
 167                     positions.allocate(pb, INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, "pos");
 168                     merkle_authentication_path_variable<FieldT, sha256_two_to_one_hash_gadget<FieldT>> authvars(pb, INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, "auth");
 169                     merkle_tree_check_read_gadget<FieldT, sha256_two_to_one_hash_gadget<FieldT>> auth(
 170                         pb, INCREMENTAL_MERKLE_TREE_DEPTH_TESTING, positions, commitment, root, authvars, ONE, "path"
 171                     );
 172                     commitment.generate_r1cs_constraints();
 173                     root.generate_r1cs_constraints();
 174                     authvars.generate_r1cs_constraints();
 175                     auth.generate_r1cs_constraints();
 176
 177                     std::vector<bool> commitment_bv;
 178                     {
 179                         std::vector<unsigned char> commitment_v(test_commitment.begin(), test_commitment.end());
 180                         commitment_bv = convertBytesVectorToVector(commitment_v);
 181                     }
 182
 183                     size_t path_index = convertVectorToInt(path.index);
 184
 185                     commitment.bits.fill_with_bits(pb, bit_vector(commitment_bv));
 186                     positions.fill_with_bits_of_ulong(pb, path_index);
 187
 188                     authvars.generate_r1cs_witness(path_index, path.authentication_path);
 189                     auth.generate_r1cs_witness();
 190
 191                     std::vector<bool> root_bv;
 192                     {
 193                         uint256 witroot = wit.root();
 194                         std::vector<unsigned char> root_v(witroot.begin(), witroot.end());
 195                         root_bv = convertBytesVectorToVector(root_v);
 196                     }
 197
 198                     root.bits.fill_with_bits(pb, bit_vector(root_bv));
 199
 200                     ASSERT_TRUE(pb.is_satisfied());
 201
 202                     root_bv[0] = !root_bv[0];
 203                     root.bits.fill_with_bits(pb, bit_vector(root_bv));
 204
 205                     ASSERT_TRUE(!pb.is_satisfied());
 206                 }
 207             }
 208
 209             // Check witness serialization
 210             expect_ser_test_vector(witness_ser_iterator, wit, tree);
 211
 212             ASSERT_TRUE(wit.root() == tree.root());
 213
 214             first = false;
 215         }
 216     }
 217
 218     {
 219         // Tree should be full now
 220         ASSERT_THROW(tree.append(uint256()), std::runtime_error);
 221
 222         BOOST_FOREACH(Witness& wit, witnesses)
 223         {
 224             ASSERT_THROW(wit.append(uint256()), std::runtime_error);
 225         }
 226     }
 227 }
 228
 229 TEST(merkletree, vectors) {
 230     libsnark::default_r1cs_ppzksnark_pp::init_public_params();
 231
 232     Array root_tests = read_json(std::string(json_tests::merkle_roots, json_tests::merkle_roots + sizeof(json_tests::merkle_roots)));
 233     Array ser_tests = read_json(std::string(json_tests::merkle_serialization, json_tests::merkle_serialization + sizeof(json_tests::merkle_serialization)));
 234     Array witness_ser_tests = read_json(std::string(json_tests::merkle_witness_serialization, json_tests::merkle_witness_serialization + sizeof(json_tests::merkle_witness_serialization)));
 235     Array path_tests = read_json(std::string(json_tests::merkle_path, json_tests::merkle_path + sizeof(json_tests::merkle_path)));
 236
 237     test_tree<ZCTestingIncrementalMerkleTree, ZCTestingIncrementalWitness>(root_tests, ser_tests, witness_ser_tests, path_tests);
 238 }
 239
 240 TEST(merkletree, emptyroots) {
 241     Array empty_roots = read_json(std::string(json_tests::merkle_roots_empty, json_tests::merkle_roots_empty + sizeof(json_tests::merkle_roots_empty)));
 242     Array::iterator root_iterator = empty_roots.begin();
 243
 244     libzcash::EmptyMerkleRoots<64, libzcash::SHA256Compress> emptyroots;
 245
 246     for (size_t depth = 0; depth <= 64; depth++) {
 247         expect_test_vector(root_iterator, emptyroots.empty_root(depth));
 248     }
 249
 250     // Double check that we're testing (at least) all the empty roots we'll use.
 251     ASSERT_TRUE(INCREMENTAL_MERKLE_TREE_DEPTH <= 64);
 252 }
 253
 254 TEST(merkletree, emptyroot) {
 255     // This literal is the depth-20 empty tree root with the bytes reversed to
 256     // account for the fact that uint256S() loads a big-endian representation of
 257     // an integer which converted to little-endian internally.
 258     uint256 expected = uint256S("59d2cde5e65c1414c32ba54f0fe4bdb3d67618125286e6a191317917c812c6d7");
 259
 260     ASSERT_TRUE(ZCIncrementalMerkleTree::empty_root() == expected);
 261 }
 262
 263 TEST(merkletree, deserializeInvalid) {
 264     // attempt to deserialize a small tree from a serialized large tree
 265     // (exceeds depth well-formedness check)
 266     ZCIncrementalMerkleTree newTree;
 267
 268     for (size_t i = 0; i < 16; i++) {
 269         newTree.append(uint256S("54d626e08c1c802b305dad30b7e54a82f102390cc92c7d4db112048935236e9c"));
 270     }
 271
 272     newTree.append(uint256S("54d626e08c1c802b305dad30b7e54a82f102390cc92c7d4db112048935236e9c"));
 273
 274     CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
 275     ss << newTree;
 276
 277     ZCTestingIncrementalMerkleTree newTreeSmall;
 278     ASSERT_THROW({ss >> newTreeSmall;}, std::ios_base::failure);
 279 }
 280
 281 TEST(merkletree, deserializeInvalid2) {
 282     // the most ancestral parent is empty
 283     CDataStream ss(
 284         ParseHex("0155b852781b9995a44c939b64e441ae2724b96f99c8f4fb9a141cfc9842c4b0e3000100"),
 285         SER_NETWORK,
 286         PROTOCOL_VERSION
 287     );
 288
 289     ZCIncrementalMerkleTree tree;
 290     ASSERT_THROW(ss >> tree, std::ios_base::failure);
 291 }
 292
 293 TEST(merkletree, deserializeInvalid3) {
 294     // left doesn't exist but right does
 295     CDataStream ss(
 296         ParseHex("000155b852781b9995a44c939b64e441ae2724b96f99c8f4fb9a141cfc9842c4b0e300"),
 297         SER_NETWORK,
 298         PROTOCOL_VERSION
 299     );
 300
 301     ZCIncrementalMerkleTree tree;
 302     ASSERT_THROW(ss >> tree, std::ios_base::failure);
 303 }
 304
 305 TEST(merkletree, deserializeInvalid4) {
 306     // left doesn't exist but a parent does
 307     CDataStream ss(
 308         ParseHex("000001018695873d63ec0bceeadb5bf4ccc6723ac803c1826fc7cfb34fc76180305ae27d"),
 309         SER_NETWORK,
 310         PROTOCOL_VERSION
 311     );
 312
 313     ZCIncrementalMerkleTree tree;
 314     ASSERT_THROW(ss >> tree, std::ios_base::failure);
 315 }
 316
 317 TEST(merkletree, testZeroElements) {
 318     for (int start = 0; start < 20; start++) {
 319         ZCIncrementalMerkleTree newTree;
 320
 321         ASSERT_TRUE(newTree.root() == ZCIncrementalMerkleTree::empty_root());
 322
 323         for (int i = start; i > 0; i--) {
 324             newTree.append(uint256S("54d626e08c1c802b305dad30b7e54a82f102390cc92c7d4db112048935236e9c"));
 325         }
 326
 327         uint256 oldroot = newTree.root();
 328
 329         // At this point, appending tons of null objects to the tree
 330         // should preserve its root.
 331
 332         for (int i = 0; i < 100; i++) {
 333             newTree.append(uint256());
 334         }
 335
 336         ASSERT_TRUE(newTree.root() == oldroot);
 337     }
 338 }