src/zerocash/zerocash_pour_gadget.tcc

   1 /** @file
   2  *****************************************************************************
   3
   4  Implementation of interfaces for the Zerocash Pour gadget.
   5
   6  See zerocash_pour_gadget.hpp .
   7
   8  *****************************************************************************
   9  * @author     This file is part of libzerocash, developed by the Zerocash
  10  *             project and contributors (see AUTHORS).
  11  * @copyright  MIT license (see LICENSE file)
  12  *****************************************************************************/
  13
  14 #include "algebra/fields/field_utils.hpp"
  15
  16 namespace libzerocash {
  17
  18 template<typename FieldT>
  19 zerocash_pour_gadget<FieldT>::zerocash_pour_gadget(protoboard<FieldT> &pb,
  20                                                    const size_t num_old_coins,
  21                                                    const size_t num_new_coins,
  22                                                    const size_t tree_depth,
  23                                                    const std::string &annotation_prefix) :
  24     gadget<FieldT>(pb, FMT(annotation_prefix, " zerocash_pour_gadget")),
  25     tree_depth(tree_depth),
  26     num_old_coins(num_old_coins),
  27     num_new_coins(num_new_coins)
  28 {
  29     /* allocate packed inputs */
  30     const size_t input_size_in_bits = sha256_digest_len + num_old_coins*sha256_digest_len + num_new_coins*sha256_digest_len + (coin_value_length * 2) + (num_old_coins + 1) * sha256_digest_len;
  31     const size_t input_size_in_field_elements = div_ceil(input_size_in_bits, FieldT::capacity());
  32     input_as_field_elements.allocate(pb, input_size_in_field_elements, FMT(annotation_prefix, " input_as_field_elements"));
  33     this->pb.set_input_sizes(input_size_in_field_elements);
  34
  35     /* allocate inputs */
  36     merkle_tree_root_variable.reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " merkle_tree_root_variable")));
  37
  38     old_coin_enforce_commitment.allocate(pb, num_old_coins, FMT(annotation_prefix, " old_coin_enforce_commitment"));
  39     old_coin_serial_number_variables.resize(num_old_coins);
  40     for (size_t i = 0; i < num_old_coins; ++i)
  41     {
  42         old_coin_serial_number_variables[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " old_coin_serial_number_variables_%zu", i)));
  43     }
  44
  45     new_coin_commitment_variables.resize(num_new_coins);
  46     for (size_t i = 0; i < num_new_coins; ++i)
  47     {
  48         new_coin_commitment_variables[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " new_coin_commitment_variables_%zu", i)));
  49     }
  50
  51     public_old_value_variable.allocate(pb, coin_value_length, FMT(annotation_prefix, " public_old_value_variable"));
  52     public_new_value_variable.allocate(pb, coin_value_length, FMT(annotation_prefix, " public_new_value_variable"));
  53     signature_public_key_hash_variable.reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " signature_public_key_hash")));
  54
  55     mac_of_signature_public_key_hash_variables.resize(num_old_coins);
  56     for (size_t i = 0; i < num_old_coins; ++i)
  57     {
  58         mac_of_signature_public_key_hash_variables[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " mac_of_signature_public_key_hash_variables_%zu", i)));
  59     }
  60
  61     /* do the multipacking */
  62     input_as_bits.insert(input_as_bits.end(), merkle_tree_root_variable->bits.begin(), merkle_tree_root_variable->bits.end());
  63     for (size_t i = 0; i < num_old_coins; ++i)
  64     {
  65         input_as_bits.insert(input_as_bits.end(), old_coin_serial_number_variables[i]->bits.begin(), old_coin_serial_number_variables[i]->bits.end());
  66     }
  67     for (size_t i = 0; i < num_new_coins; ++i)
  68     {
  69         input_as_bits.insert(input_as_bits.end(), new_coin_commitment_variables[i]->bits.begin(), new_coin_commitment_variables[i]->bits.end());
  70     }
  71     input_as_bits.insert(input_as_bits.end(), public_old_value_variable.begin(), public_old_value_variable.end());
  72     input_as_bits.insert(input_as_bits.end(), public_new_value_variable.begin(), public_new_value_variable.end());
  73     input_as_bits.insert(input_as_bits.end(), signature_public_key_hash_variable->bits.begin(), signature_public_key_hash_variable->bits.end());
  74     for (size_t i = 0; i < num_old_coins; ++i)
  75     {
  76         input_as_bits.insert(input_as_bits.end(), mac_of_signature_public_key_hash_variables[i]->bits.begin(), mac_of_signature_public_key_hash_variables[i]->bits.end());
  77     }
  78     assert(input_as_bits.size() == input_size_in_bits);
  79     unpack_inputs.reset(new multipacking_gadget<FieldT>(this->pb, input_as_bits, input_as_field_elements, FieldT::capacity(), FMT(this->annotation_prefix, " unpack_inputs")));
  80
  81     pb_linear_combination_array<FieldT> IV = SHA256_default_IV(pb);
  82     zero.allocate(this->pb, FMT(this->annotation_prefix, " zero")); /* TODO */
  83
  84     /* allocate witness */
  85     new_address_public_key_variables.resize(num_new_coins);
  86     new_address_commitment_nonce_variables.resize(num_new_coins);
  87     new_coin_serial_number_nonce_variables.resize(num_new_coins);
  88     new_coin_value_variables.resize(num_new_coins);
  89     for (size_t i = 0; i < num_new_coins; ++i)
  90     {
  91         new_address_public_key_variables[i].allocate(pb, address_public_key_length, FMT(annotation_prefix, " new_address_public_key_variables_%zu", i));
  92         new_address_commitment_nonce_variables[i].allocate(pb, address_commitment_nonce_length, FMT(annotation_prefix, " new_address_commitment_nonce_variables_%zu", i));
  93         new_coin_serial_number_nonce_variables[i].allocate(pb, serial_number_nonce_length, FMT(annotation_prefix, " new_coin_serial_number_nonce_variables_%zu", i));
  94         new_coin_value_variables[i].allocate(pb, coin_value_length, FMT(annotation_prefix, " new_coin_value_variables_%zu", i));
  95     }
  96
  97     old_address_secret_key_variables.resize(num_old_coins);
  98     old_address_commitment_nonce_variables.resize(num_old_coins);
  99     old_coin_serial_number_nonce_variables.resize(num_old_coins);
 100     old_coin_value_variables.resize(num_old_coins);
 101     for (size_t i = 0; i < num_old_coins; ++i)
 102     {
 103         old_address_secret_key_variables[i].allocate(pb, address_secret_key_length, FMT(annotation_prefix, " old_address_secret_key_variables_%zu", i));
 104         old_address_commitment_nonce_variables[i].allocate(pb, address_commitment_nonce_length, FMT(annotation_prefix, " old_address_commitment_nonce_variables_%zu", i));
 105         old_coin_serial_number_nonce_variables[i].allocate(pb, serial_number_nonce_length, FMT(annotation_prefix, " old_coin_serial_number_nonce_variables_%zu", i));
 106         old_coin_value_variables[i].allocate(pb, coin_value_length, FMT(annotation_prefix, " old_coin_value_variables_%zu", i));
 107     }
 108
 109     /* do the actual hashing */
 110     pb_variable_array<FieldT> zero_one;
 111     zero_one.emplace_back(zero);
 112     zero_one.emplace_back(ONE);
 113
 114     prf_for_old_coin_serial_number_input_variables.resize(num_old_coins);
 115     prfs_for_old_coin_serial_numbers.resize(num_old_coins);
 116     for (size_t i = 0; i < num_old_coins; ++i)
 117     {
 118         /* (C) old_coin_serial_number_variables[i] = PRF_{old_address_secret_key_variables[i]}^{sn}
 119            (old_coin_serial_number_nonce_variables[0..254]) =
 120            H(old_address_secret_key_variables[i] || 01 || old_coin_serial_number_nonce_variables[0..254]) */
 121         prf_for_old_coin_serial_number_input_variables[i].reset(new block_variable<FieldT>(pb, {
 122                     old_address_secret_key_variables[i],
 123                         zero_one,
 124                         pb_variable_array<FieldT>(old_coin_serial_number_nonce_variables[i].begin(),
 125                                                   old_coin_serial_number_nonce_variables[i].begin() + truncated_serial_number_length) },
 126                 FMT(annotation_prefix, " prf_for_old_coin_serial_number_input_variables_%zu", i)));
 127         prfs_for_old_coin_serial_numbers[i].reset(new sha256_compression_function_gadget<FieldT>(pb, IV, prf_for_old_coin_serial_number_input_variables[i]->bits, *old_coin_serial_number_variables[i], FMT(annotation_prefix, " prfs_for_old_coin_serial_numbers_%zu", i)));
 128     }
 129
 130     old_address_public_key_variables.resize(num_old_coins);
 131     prf_for_old_address_public_key_input_variables.resize(num_old_coins);
 132     prfs_for_old_address_public_keys.resize(num_old_coins);
 133
 134     for (size_t i = 0; i < num_old_coins; ++i)
 135     {
 136         old_address_public_key_variables[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " old_address_public_key_variables_%zu", i)));
 137
 138         /* (B) old_address_public_keys[i] = PRF_{old_address_secret_key_variables[i]}^{addr}(z) =
 139            H(old_address_secret_key_variables[i] || 00 || z), where z = 0...0 */
 140         pb_variable_array<FieldT> addr_pk_pad(address_public_key_padding_length, zero);
 141         prf_for_old_address_public_key_input_variables[i].reset(new block_variable<FieldT>(pb,
 142             { old_address_secret_key_variables[i], addr_pk_pad },
 143                 FMT(annotation_prefix, " prf_for_old_address_public_key_input_variables_%zu", i)));
 144         prfs_for_old_address_public_keys[i].reset(new sha256_compression_function_gadget<FieldT>(pb,
 145                                                                                                  IV,
 146                                                                                                  prf_for_old_address_public_key_input_variables[i]->bits,
 147                                                                                                  *old_address_public_key_variables[i],
 148                                                                                                  FMT(annotation_prefix, " prfs_for_old_address_public_keys_%zu", i)));
 149     }
 150
 151     commitments_to_old_address_public_keys.resize(num_old_coins);
 152     commit_to_old_address_public_key_input_variables.resize(num_old_coins);
 153     commit_to_old_address_public_keys.resize(num_old_coins);
 154
 155     for (size_t i = 0; i < num_old_coins; ++i)
 156     {
 157         /* (D0) commitments_to_old_address_public_keys[i] = H(old_address_public_key_variables[i] || old_coin_serial_number_nonce_variables[i]) */
 158         commitments_to_old_address_public_keys[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " commitments_to_old_address_public_keys_%zu", i)));
 159         commit_to_old_address_public_key_input_variables[i].reset(new block_variable<FieldT>(pb, { old_address_public_key_variables[i]->bits, old_coin_serial_number_nonce_variables[i] }, FMT(annotation_prefix, " commit_to_old_address_public_key_input_variables_%zu", i)));
 160         commit_to_old_address_public_keys[i].reset(new sha256_compression_function_gadget<FieldT>(pb, IV, commit_to_old_address_public_key_input_variables[i]->bits, *commitments_to_old_address_public_keys[i], FMT(annotation_prefix, " commit_to_old_address_public_keys_%zu", i)));
 161     }
 162
 163     old_coin_value_commitment_nonces.resize(num_old_coins);
 164     commit_to_old_coin_value_commitment_nonce_input_variables.resize(num_old_coins);
 165     commit_to_old_coin_value_commitment_nonces.resize(num_old_coins);
 166
 167     for (size_t i = 0; i < num_old_coins; ++i)
 168     {
 169         /* (D1) old_coin_value_commitment_nonces[i] =
 170            H(old_address_commitment_nonce_variables[i] || commitments_to_old_address_public_keys[i] [0..128]) */
 171         old_coin_value_commitment_nonces[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " old_coin_value_commitment_nonces_%zu", i)));
 172         commit_to_old_coin_value_commitment_nonce_input_variables[i].reset(new block_variable<FieldT>(pb, { old_address_commitment_nonce_variables[i], pb_variable_array<FieldT>(commitments_to_old_address_public_keys[i]->bits.begin(), commitments_to_old_address_public_keys[i]->bits.begin()+ truncated_coin_commitment_length) }, FMT(annotation_prefix, " commit_to_old_coin_value_commitment_nonce_input_variables_%zu", i)));
 173         commit_to_old_coin_value_commitment_nonces[i].reset(new sha256_compression_function_gadget<FieldT>(pb, IV, commit_to_old_coin_value_commitment_nonce_input_variables[i]->bits, *old_coin_value_commitment_nonces[i], FMT(annotation_prefix, " commit_to_old_coin_value_commitment_nonces_%zu", i)));
 174     }
 175
 176     pb_variable_array<FieldT> coincomm_pad(coin_commitment_padding_length, zero);
 177     old_coin_commitment_variables.resize(num_old_coins);
 178     compute_old_coin_commitment_input_variables.resize(num_old_coins);
 179     compute_old_coin_commitments.resize(num_old_coins);
 180
 181     for (size_t i = 0; i < num_old_coins; ++i)
 182     {
 183         /* (D2) old_coin_commitment_variables[i] = COMM_s(old_coin_value_variables[i] || old_coin_value_commitment_nonces[i])
 184            H(old_coin_value_commitment_nonces[i] || 0^{192} || old_coin_value_variables[i])
 185
 186            Here we ignore commitment randomness s, as k = old_coin_value_commitment_nonces[i] is an output of a
 187            statistically hiding commitment scheme. */
 188         old_coin_commitment_variables[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " old_coin_commitment_variables_%zu", i)));
 189         compute_old_coin_commitment_input_variables[i].reset(new block_variable<FieldT>(pb, { old_coin_value_commitment_nonces[i]->bits, coincomm_pad, old_coin_value_variables[i] }, FMT(annotation_prefix, " compute_old_coin_commitment_input_variables_%zu", i)));
 190         compute_old_coin_commitments[i].reset(new sha256_compression_function_gadget<FieldT>(pb, IV, compute_old_coin_commitment_input_variables[i]->bits, *old_coin_commitment_variables[i], FMT(annotation_prefix, " compute_old_coin_commitment_%zu", i)));
 191     }
 192
 193     commitments_to_new_address_public_keys.resize(num_new_coins);
 194     commit_to_new_address_public_key_input_variables.resize(num_new_coins);
 195     commit_to_new_address_public_keys.resize(num_new_coins);
 196
 197     for (size_t i = 0; i < num_new_coins; ++i)
 198     {
 199         /* (E0) commitments_to_new_address_public_keys[i] = H(new_address_public_key_variables[i] || new_coin_serial_number_nonce_variables[i]) */
 200         commitments_to_new_address_public_keys[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " commitments_to_new_address_public_keys_%zu", i)));
 201         commit_to_new_address_public_key_input_variables[i].reset(new block_variable<FieldT>(pb, { new_address_public_key_variables[i], new_coin_serial_number_nonce_variables[i] }, FMT(annotation_prefix, " commit_to_new_address_public_key_input_variables_%zu", i)));
 202         commit_to_new_address_public_keys[i].reset(new sha256_compression_function_gadget<FieldT>(pb, IV, commit_to_new_address_public_key_input_variables[i]->bits, *commitments_to_new_address_public_keys[i], FMT(annotation_prefix, " commit_to_new_address_public_keys_%zu", i)));
 203     }
 204
 205     new_coin_value_commitment_nonces.resize(num_new_coins);
 206     commit_to_new_coin_value_commitment_nonce_input_variables.resize(num_new_coins);
 207     commit_to_new_coin_value_commitment_nonces.resize(num_new_coins);
 208     for (size_t i = 0; i < num_new_coins; ++i)
 209     {
 210         /* (E1) new_coin_value_commitment_nonces[i] =
 211            H(new_address_commitment_nonce_variables[i] || commitments_to_new_address_public_keys[i] [0..128]) */
 212         new_coin_value_commitment_nonces[i].reset(new digest_variable<FieldT>(pb, sha256_digest_len, FMT(annotation_prefix, " new_coin_value_commitment_nonces_%zu", i)));
 213         commit_to_new_coin_value_commitment_nonce_input_variables[i].reset(new block_variable<FieldT>(pb, { new_address_commitment_nonce_variables[i], pb_variable_array<FieldT>(commitments_to_new_address_public_keys[i]->bits.begin(), commitments_to_new_address_public_keys[i]->bits.begin()+ truncated_coin_commitment_length) }, FMT(annotation_prefix, " commit_to_new_coin_value_commitment_nonce_input_variables_%zu", i)));
 214         commit_to_new_coin_value_commitment_nonces[i].reset(new sha256_compression_function_gadget<FieldT>(pb, IV, commit_to_new_coin_value_commitment_nonce_input_variables[i]->bits, *new_coin_value_commitment_nonces[i], FMT(annotation_prefix, " commit_to_new_coin_value_commitment_nonces_%zu", i)));
 215     }
 216
 217     compute_new_coin_commitment_input_variables.resize(num_new_coins);
 218     compute_new_coin_commitments.resize(num_new_coins);
 219
 220     for (size_t i = 0; i < num_new_coins; ++i)
 221     {
 222         /* (E2) new_coin_commitment_variables[i] = COMM_s(new_coin_value_variables[i] || new_coin_value_commitment_nonces[i])
 223            H(new_coin_value_commitment_nonces[i] || 0^{192} || new_coin_value_variables[i]) */
 224         compute_new_coin_commitment_input_variables[i].reset(new block_variable<FieldT>(pb, { new_coin_value_commitment_nonces[i]->bits, coincomm_pad, new_coin_value_variables[i] }, FMT(annotation_prefix, " compute_new_coin_commitment_input_variables_%zu", i)));
 225         compute_new_coin_commitments[i].reset(new sha256_compression_function_gadget<FieldT>(pb, IV, compute_new_coin_commitment_input_variables[i]->bits, *new_coin_commitment_variables[i], FMT(annotation_prefix, " compute_new_coin_commitment_%zu", i)));
 226     }
 227
 228     /* compute signature public key macs */
 229     prf_for_macs_of_signature_public_key_hash_input_variables.resize(num_old_coins);
 230     prfs_for_macs_of_signature_public_key_hash.resize(num_old_coins);
 231     const size_t truncated_signature_public_key_hash_length = indexed_signature_public_key_hash_length - log2(num_old_coins);
 232
 233     for (size_t i = 0; i < num_old_coins; ++i)
 234     {
 235         /* (F) mac_of_signature_public_key_hash_variables[i] = PRF_{old_address_secret_key_variables[i]}^{pk}
 236            (i || signature_public_key_hash_variable) =
 237            H(old_address_secret_key_variables[i] || 10 || i || signature_public_key_hash_variable)
 238
 239            Here signature_public_key_hash is truncated so that the entire argument fits inside SHA256 block.
 240            Furthermore, the representation of i is MSB to LSB and is exactly log2(num_old_coins) bits long. */
 241         pb_variable_array<FieldT> prf_padding;
 242         prf_padding.emplace_back(ONE);
 243         prf_padding.emplace_back(zero);
 244
 245         for (size_t j = 0; j < log2(num_old_coins); ++j)
 246         {
 247             prf_padding.emplace_back((i >> (log2(num_old_coins) - j - 1)) & 1 ? ONE : zero);
 248         }
 249
 250         prf_for_macs_of_signature_public_key_hash_input_variables[i].reset(new block_variable<FieldT>(pb, { old_address_secret_key_variables[i], prf_padding, pb_variable_array<FieldT>(signature_public_key_hash_variable->bits.begin(), signature_public_key_hash_variable->bits.begin()+truncated_signature_public_key_hash_length) }, FMT(annotation_prefix, " prf_for_macs_of_signature_public_key_hash_input_variables_%zu", i)));
 251         prfs_for_macs_of_signature_public_key_hash[i].reset(new sha256_compression_function_gadget<FieldT>(pb, IV, prf_for_macs_of_signature_public_key_hash_input_variables[i]->bits, *mac_of_signature_public_key_hash_variables[i], FMT(annotation_prefix, " prfs_for_macs_of_signature_public_key_hash_%zu", i)));
 252     }
 253
 254     /* prove membership in the Merkle tree*/
 255     old_coin_merkle_tree_position_variables.resize(num_old_coins);
 256     old_coin_authentication_path_variables.resize(num_old_coins);
 257     old_coin_commitments_in_tree.resize(num_old_coins);
 258     for (size_t i = 0; i < num_old_coins; ++i)
 259     {
 260         /* (A) old_coin_commitment_variables[i] appears on path old_coin_authentication_paths[i]
 261            to merkle_tree_root_variable */
 262         old_coin_merkle_tree_position_variables[i].allocate(pb, tree_depth, FMT(annotation_prefix, " old_coin_merkle_tree_position_variables_%zu", i));
 263         old_coin_authentication_path_variables[i].reset(new merkle_authentication_path_variable<FieldT, sha256_two_to_one_hash_gadget<FieldT> >(pb, tree_depth, FMT(annotation_prefix, " old_coin_authentication_path_variables_%zu", i)));
 264         old_coin_commitments_in_tree[i].reset(new merkle_tree_check_read_gadget<FieldT, sha256_two_to_one_hash_gadget<FieldT> >(
 265                                                   pb, tree_depth, old_coin_merkle_tree_position_variables[i], *old_coin_commitment_variables[i], *merkle_tree_root_variable,
 266                                                   *old_coin_authentication_path_variables[i], old_coin_enforce_commitment[i], FMT(annotation_prefix, " old_coin_commitments_in_tree_%zu", i)));
 267     }
 268 }
 269
 270 template<typename FieldT>
 271 void zerocash_pour_gadget<FieldT>::generate_r1cs_constraints()
 272 {
 273     generate_r1cs_equals_const_constraint<FieldT>(this->pb, zero, FieldT::zero(), FMT(this->annotation_prefix, " zero"));
 274
 275     for (size_t i = 0; i < num_old_coins; ++i)
 276     {
 277         prfs_for_old_coin_serial_numbers[i]->generate_r1cs_constraints();
 278         prfs_for_old_address_public_keys[i]->generate_r1cs_constraints();
 279         commit_to_old_address_public_keys[i]->generate_r1cs_constraints();
 280         commit_to_old_coin_value_commitment_nonces[i]->generate_r1cs_constraints();
 281         compute_old_coin_commitments[i]->generate_r1cs_constraints();
 282         old_coin_commitments_in_tree[i]->generate_r1cs_constraints();
 283         prfs_for_macs_of_signature_public_key_hash[i]->generate_r1cs_constraints();
 284
 285         for (size_t j = 0; j < tree_depth; ++j)
 286         {
 287             generate_boolean_r1cs_constraint<FieldT>(this->pb, old_coin_merkle_tree_position_variables[i][j], FMT(this->annotation_prefix, " old_coin_merkle_tree_position_variables_%zu_%zu", i, j));
 288         }
 289     }
 290
 291     for (size_t i = 0; i < num_new_coins; ++i)
 292     {
 293         commit_to_new_address_public_keys[i]->generate_r1cs_constraints();
 294         commit_to_new_coin_value_commitment_nonces[i]->generate_r1cs_constraints();
 295         compute_new_coin_commitments[i]->generate_r1cs_constraints();
 296     }
 297
 298     unpack_inputs->generate_r1cs_constraints(true);
 299
 300     /* ensure bitness of all values */
 301     for (size_t j = 0; j < coin_value_length; ++j)
 302     {
 303         for (size_t i = 0; i < num_old_coins; ++i)
 304         {
 305             generate_boolean_r1cs_constraint<FieldT>(this->pb, old_coin_value_variables[i][j], FMT(this->annotation_prefix, " old_coin_value_variables_%zu_%zu", i, j));
 306         }
 307         for (size_t i = 0; i < num_new_coins; ++i)
 308         {
 309             generate_boolean_r1cs_constraint<FieldT>(this->pb, new_coin_value_variables[i][j], FMT(this->annotation_prefix, " new_coin_value_variables_%zu_%zu", i, j));
 310         }
 311     }
 312
 313     for (size_t i = 0; i < num_old_coins; ++i)
 314     {
 315         generate_boolean_r1cs_constraint<FieldT>(this->pb, old_coin_enforce_commitment[i], FMT(this->annotation_prefix, " old_coin_enforce_commitment_%zu", i));
 316         this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(
 317             pb_packing_sum<FieldT>(pb_variable_array<FieldT>(old_coin_value_variables[i].rbegin(), old_coin_value_variables[i].rend())),
 318             1 - old_coin_enforce_commitment[i],
 319             0), FMT(this->annotation_prefix, " enforce_%zu", i));
 320     }
 321
 322     /* check the balance equation */
 323     linear_combination<FieldT> old_packed_value;
 324     for (size_t i = 0; i < num_old_coins; ++i)
 325     {
 326         old_packed_value = old_packed_value + pb_packing_sum<FieldT>(pb_variable_array<FieldT>(old_coin_value_variables[i].rbegin(), old_coin_value_variables[i].rend()));
 327     }
 328     old_packed_value = old_packed_value + pb_packing_sum<FieldT>(pb_variable_array<FieldT>(public_old_value_variable.rbegin(), public_old_value_variable.rend()));
 329
 330     linear_combination<FieldT> new_packed_value;
 331     for (size_t i = 0; i < num_new_coins; ++i)
 332     {
 333         new_packed_value = new_packed_value + pb_packing_sum<FieldT>(pb_variable_array<FieldT>(new_coin_value_variables[i].rbegin(), new_coin_value_variables[i].rend()));
 334     }
 335     new_packed_value = new_packed_value + pb_packing_sum<FieldT>(pb_variable_array<FieldT>(public_new_value_variable.rbegin(), public_new_value_variable.rend()));
 336
 337     this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(1, old_packed_value, new_packed_value), FMT(this->annotation_prefix, " balance"));
 338 }
 339
 340 template<typename FieldT>
 341 void zerocash_pour_gadget<FieldT>::generate_r1cs_witness(const std::vector<merkle_authentication_path> &old_coin_authentication_paths,
 342                                                          const std::vector<size_t> &old_coin_merkle_tree_positions,
 343                                                          const bit_vector &merkle_tree_root,
 344                                                          const std::vector<bit_vector> &new_address_public_keys,
 345                                                          const std::vector<bit_vector> &old_address_secret_keys,
 346                                                          const std::vector<bit_vector> &new_address_commitment_nonces,
 347                                                          const std::vector<bit_vector> &old_address_commitment_nonces,
 348                                                          const std::vector<bit_vector> &new_coin_serial_number_nonces,
 349                                                          const std::vector<bit_vector> &old_coin_serial_number_nonces,
 350                                                          const std::vector<bit_vector> &new_coin_values,
 351                                                          const bit_vector &public_old_value,
 352                                                          const bit_vector &public_new_value,
 353                                                          const std::vector<bit_vector> &old_coin_values,
 354                                                          const bit_vector &signature_public_key_hash)
 355 {
 356     /* fill in the auxiliary variables */
 357     this->pb.val(zero) = FieldT::zero();
 358
 359     /* fill in the witness */
 360     for (size_t i = 0; i < num_new_coins; ++i)
 361     {
 362         new_address_public_key_variables[i].fill_with_bits(this->pb, new_address_public_keys[i]);
 363         new_address_commitment_nonce_variables[i].fill_with_bits(this->pb, new_address_commitment_nonces[i]);
 364     }
 365
 366     for (size_t i = 0; i < num_old_coins; ++i)
 367     {
 368         old_address_secret_key_variables[i].fill_with_bits(this->pb, old_address_secret_keys[i]);
 369         old_address_commitment_nonce_variables[i].fill_with_bits(this->pb, old_address_commitment_nonces[i]);
 370     }
 371
 372     for (size_t i = 0; i < num_new_coins; ++i)
 373     {
 374         new_coin_serial_number_nonce_variables[i].fill_with_bits(this->pb, new_coin_serial_number_nonces[i]);
 375         new_coin_value_variables[i].fill_with_bits(this->pb, new_coin_values[i]);
 376     }
 377
 378     for (size_t i = 0; i < num_old_coins; ++i)
 379     {
 380         this->pb.val(old_coin_enforce_commitment[i]) = FieldT::zero();
 381         old_coin_serial_number_nonce_variables[i].fill_with_bits(this->pb, old_coin_serial_number_nonces[i]);
 382         old_coin_value_variables[i].fill_with_bits(this->pb, old_coin_values[i]);
 383
 384         for (size_t j = 0; j < coin_value_length; ++j)
 385         {
 386             if (old_coin_values[i][j]) {
 387                 // If any bit in the value is nonzero, the value is nonzero.
 388                 // Thus, the old coin must be committed in the tree.
 389                 this->pb.val(old_coin_enforce_commitment[i]) = FieldT::one();
 390                 break;
 391             }
 392         }
 393     }
 394
 395     public_old_value_variable.fill_with_bits(this->pb, public_old_value);
 396     public_new_value_variable.fill_with_bits(this->pb, public_new_value);
 397     signature_public_key_hash_variable->generate_r1cs_witness(signature_public_key_hash);
 398
 399     /* do the hashing */
 400     for (size_t i = 0; i < num_old_coins; ++i)
 401     {
 402         prfs_for_old_coin_serial_numbers[i]->generate_r1cs_witness();
 403         prfs_for_old_address_public_keys[i]->generate_r1cs_witness();
 404         commit_to_old_address_public_keys[i]->generate_r1cs_witness();
 405         commit_to_old_coin_value_commitment_nonces[i]->generate_r1cs_witness();
 406         compute_old_coin_commitments[i]->generate_r1cs_witness();
 407         prfs_for_macs_of_signature_public_key_hash[i]->generate_r1cs_witness();
 408     }
 409
 410     for (size_t i = 0; i < num_new_coins; ++i)
 411     {
 412         commit_to_new_address_public_keys[i]->generate_r1cs_witness();
 413         commit_to_new_coin_value_commitment_nonces[i]->generate_r1cs_witness();
 414         compute_new_coin_commitments[i]->generate_r1cs_witness();
 415     }
 416
 417     /* prove the membership in the Merkle tree */
 418     for (size_t i = 0; i < num_old_coins; ++i)
 419     {
 420         /* (A) old_coin_commitment_variables[i] appears on path old_coin_authentication_paths[i]
 421            to merkle_tree_root_variable */
 422         old_coin_merkle_tree_position_variables[i].fill_with_bits_of_ulong(this->pb, old_coin_merkle_tree_positions[i]);
 423         old_coin_authentication_path_variables[i]->generate_r1cs_witness(old_coin_merkle_tree_positions[i], old_coin_authentication_paths[i]);
 424         old_coin_commitments_in_tree[i]->generate_r1cs_witness();
 425     }
 426
 427     /* pack the input */
 428     unpack_inputs->generate_r1cs_witness_from_bits();
 429
 430 #ifdef DEBUG
 431     printf("input_as_field_elements according to witness map:\n");
 432     for (size_t i = 0; i < input_as_field_elements.size(); ++i)
 433     {
 434         this->pb.val(input_as_field_elements[i]).print();
 435     }
 436 #endif
 437 }
 438
 439 template<typename FieldT>
 440 r1cs_primary_input<FieldT> zerocash_pour_input_map(const size_t num_old_coins,
 441                                                    const size_t num_new_coins,
 442                                                    const bit_vector &merkle_tree_root,
 443                                                    const std::vector<bit_vector> &old_coin_serial_numbers,
 444                                                    const std::vector<bit_vector> &new_coin_commitments,
 445                                                    const bit_vector &public_old_value,
 446                                                    const bit_vector &public_new_value,
 447                                                    const bit_vector &signature_public_key_hash,
 448                                                    const std::vector<bit_vector> &signature_public_key_hash_macs)
 449 {
 450     enter_block("Call to zerocash_pour_input_map");
 451     assert(merkle_tree_root.size() == sha256_digest_len);
 452     assert(old_coin_serial_numbers.size() == num_old_coins);
 453     for (auto &old_coin_serial_number : old_coin_serial_numbers)
 454     {
 455         assert(old_coin_serial_number.size() == serial_number_length);
 456     }
 457     assert(new_coin_commitments.size() == num_new_coins);
 458     for (auto &new_coin_commitment : new_coin_commitments)
 459     {
 460         assert(new_coin_commitment.size() == coin_commitment_length);
 461     }
 462     assert(public_old_value.size() == coin_value_length);
 463     assert(public_new_value.size() == coin_value_length);
 464     assert(signature_public_key_hash.size() == sha256_digest_len);
 465     assert(signature_public_key_hash_macs.size() == num_old_coins);
 466     for (auto &signature_public_key_hash_mac : signature_public_key_hash_macs)
 467     {
 468         assert(signature_public_key_hash_mac.size() == sha256_digest_len);
 469     }
 470
 471     bit_vector input_as_bits;
 472
 473     input_as_bits.insert(input_as_bits.end(), merkle_tree_root.begin(), merkle_tree_root.end());
 474     for (auto &old_coin_serial_number : old_coin_serial_numbers)
 475     {
 476         input_as_bits.insert(input_as_bits.end(), old_coin_serial_number.begin(), old_coin_serial_number.end());
 477     }
 478     for (auto &new_coin_commitment : new_coin_commitments)
 479     {
 480         input_as_bits.insert(input_as_bits.end(), new_coin_commitment.begin(), new_coin_commitment.end());
 481     }
 482     input_as_bits.insert(input_as_bits.end(), public_old_value.begin(), public_old_value.end());
 483     input_as_bits.insert(input_as_bits.end(), public_new_value.begin(), public_new_value.end());
 484     input_as_bits.insert(input_as_bits.end(), signature_public_key_hash.begin(), signature_public_key_hash.end());
 485     for (auto &signature_public_key_hash_mac : signature_public_key_hash_macs)
 486     {
 487         input_as_bits.insert(input_as_bits.end(), signature_public_key_hash_mac.begin(), signature_public_key_hash_mac.end());
 488     }
 489     std::vector<FieldT> input_as_field_elements = pack_bit_vector_into_field_element_vector<FieldT>(input_as_bits);
 490
 491 #ifdef DEBUG
 492     printf("input_as_field_elements from zerocash_pour_input_map:\n");
 493     for (size_t i = 0; i < input_as_field_elements.size(); ++i)
 494     {
 495         input_as_field_elements[i].print();
 496     }
 497 #endif
 498     leave_block("Call to zerocash_pour_input_map");
 499
 500     return input_as_field_elements;
 501 }
 502
 503 } // libzerocash