Что не так с моей программой предикатов соответствия libsnark?

#c #proof

Вопрос:

Это не удается на этапе проверки, когда сумма сдвига (фиктивная) равна 1. Я действительно не понимаю, почему это так. Я десятки раз читал генераторы ограничений и свидетелей, не замечая ошибки/несоответствия.

Что код «доказывает», так это то, что определенное число может быть получено, начиная с 0 и сдвигаясь в битах в конце.

 // The following code file is mainly cobbled together from bits of
// libsnark. It is hereby released under the MIT license, but it is
// not itself part of libsnark as some of the copy-pasted file headers
// would indicate.

/**
*****************************************************************************
* @author     This file is part of libsnark, developed by SCIPR Lab
*             and contributors (see AUTHORS).
* @copyright  MIT license (see LICENSE file)
*****************************************************************************/
#include <libsnark/common/default_types/r1cs_ppzkpcd_pp.hpp>

/** @file
*****************************************************************************

Declaration of functionality that runs the R1CS single-predicate ppzkPCD
for a compliance predicate example.

*****************************************************************************
* @author     This file is part of libsnark, developed by SCIPR Lab
*             and contributors (see AUTHORS).
* @copyright  MIT license (see LICENSE file)
*****************************************************************************/

#ifndef RUN_R1CS_SP_PPZKPCD_HPP_
#define RUN_R1CS_SP_PPZKPCD_HPP_

#include <cstddef>

namespace libsnark {

  /**
   * Runs the single-predicate ppzkPCD (generator, prover, and verifier) for the
   * "tally compliance predicate", of a given wordsize, arity, and depth.
   *
   * Optionally, also test the serialization routines for keys and proofs.
   * (This takes additional time.)
   */
  template<typename PCD_ppT>
  bool run_r1cs_sp_ppzkpcd_tally_example(const size_t value,
                                         const bool test_serialization);

} // libsnark

/** @file
*****************************************************************************

Implementation of functionality that runs the R1CS single-predicate ppzkPCD
for a compliance predicate example.

See run_r1cs_sp_ppzkpcd.hpp .

*****************************************************************************
* @author     This file is part of libsnark, developed by SCIPR Lab
*             and contributors (see AUTHORS).
* @copyright  MIT license (see LICENSE file)
*****************************************************************************/

#ifndef RUN_R1CS_SP_PPZKPCD_TCC_
#define RUN_R1CS_SP_PPZKPCD_TCC_

/** @file
*****************************************************************************

Declaration of interfaces for the tally compliance predicate.

The tally compliance predicate has two purposes:
(1) it exemplifies the use of interfaces declared in cp_handler.hpp, and
(2) it enables us to test r1cs_pcd functionalities.

See
- libsnark/zk_proof_systems/pcd/r1cs_pcd/r1cs_sp_ppzkpcd/examples/run_r1cs_sp_ppzkpcd.hpp
- libsnark/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/examples/run_r1cs_mp_ppzkpcd.hpp
for code that uses the tally compliance predicate.

*****************************************************************************
* @author     This file is part of libsnark, developed by SCIPR Lab
*             and contributors (see AUTHORS).
* @copyright  MIT license (see LICENSE file)
*****************************************************************************/

#ifndef TALLY_CP_HPP_
#define TALLY_CP_HPP_

#include <libsnark/gadgetlib1/gadgets/basic_gadgets.hpp>
#include <libsnark/zk_proof_systems/pcd/r1cs_pcd/compliance_predicate/compliance_predicate.hpp>
#include <libsnark/zk_proof_systems/pcd/r1cs_pcd/compliance_predicate/cp_handler.hpp>

namespace libsnark {

  /**
   * Subclasses a R1CS PCD message to the tally compliance predicate.
   */
  template<typename FieldT>
  class tally_pcd_message : public r1cs_pcd_message<FieldT> {
  public:
    size_t value;

    tally_pcd_message(const size_t type,
                      const size_t value);
    r1cs_variable_assignment<FieldT> payload_as_r1cs_variable_assignment() const;
    void print() const;

    ~tally_pcd_message() = defau<
  };

  template<typename FieldT>
  class tally_pcd_local_data : public r1cs_pcd_local_data<FieldT> {
  public:
    bool lowbit;

    tally_pcd_local_data(const bool lowbit);
    r1cs_variable_assignment<FieldT> as_r1cs_variable_assignment() const;
    void print() const;

    ~tally_pcd_local_data() = defau<
  };

  /**
   * Subclass a R1CS compliance predicate handler to the tally compliance predicate handler.
   */
  template<typename FieldT>
  class tally_cp_handler : public compliance_predicate_handler<FieldT, protoboard<FieldT> > {
  public:
    typedef compliance_predicate_handler<FieldT, protoboard<FieldT> > base_handler;

    tally_cp_handler(const size_t type,
                     const bool relies_on_same_type_inputs = false,
                     const std::set<size_t> accepted_input_types = std::set<size_t>());

    void generate_r1cs_constraints();
    void generate_r1cs_witness(const std::vector<std::shared_ptr<r1cs_pcd_message<FieldT> > > amp;incoming_messages,
                               const std::shared_ptr<r1cs_pcd_local_data<FieldT> > amp;local_data);

    r1cs_pcd_message<FieldT>* get_base_case_message() const;
  };

} // libsnark

/** @file
*****************************************************************************

Implementation of interfaces for the tally compliance predicate.

See tally_cp.hpp .

*****************************************************************************
* @author     This file is part of libsnark, developed by SCIPR Lab
*             and contributors (see AUTHORS).
* @copyright  MIT license (see LICENSE file)
*****************************************************************************/

#ifndef TALLY_CP_TCC_
#define TALLY_CP_TCC_

#include <algorithm>
#include <functional>

#include <libff/algebra/fields/field_utils.hpp>

namespace libsnark {

  template<typename FieldT>
  tally_pcd_message<FieldT>::tally_pcd_message(const size_t type,
                                               const size_t value) :
    r1cs_pcd_message<FieldT>(type), value(value)
  {
  }

  template<typename FieldT>
  r1cs_variable_assignment<FieldT> tally_pcd_message<FieldT>::payload_as_r1cs_variable_assignment() const
  {
    r1cs_variable_assignment<FieldT> resu<
  
    result.push_back(value);
  
    return resu<
  }

  template<typename FieldT>
  void tally_pcd_message<FieldT>::print() const
  {
    printf("Tally message of type %zu:n", this->type);
    printf("  value: %zun", value);
  }

  template<typename FieldT>
  tally_pcd_local_data<FieldT>::tally_pcd_local_data(const bool lowbit) :
    lowbit(lowbit)
  {
  }

  template<typename FieldT>
  r1cs_variable_assignment<FieldT> tally_pcd_local_data<FieldT>::as_r1cs_variable_assignment() const
  {
    const r1cs_variable_assignment<FieldT> result = { FieldT(lowbit ? FieldT::one() : FieldT::zero()) };
    return resu<
  }

  template<typename FieldT>
  void tally_pcd_local_data<FieldT>::print() const
  {
    printf("Tally PCD local data:n");
    printf("  lowbit: %zun", lowbit);
  }

  template<typename FieldT>
  class tally_pcd_message_variable: public r1cs_pcd_message_variable<FieldT> {
  public:
    pb_variable<FieldT> value;

    tally_pcd_message_variable(protoboard<FieldT> amp;pb,
                               const std::string amp;annotation_prefix) :
      r1cs_pcd_message_variable<FieldT>(pb, annotation_prefix)
    {
      value.allocate(pb, FMT(annotation_prefix, " value"));

      this->update_all_vars();
    }

    std::shared_ptr<r1cs_pcd_message<FieldT> > get_message() const
    {
      const size_t type_val = this->pb.val(this->type).as_ulong();
      const size_t value_val = this->pb.val(this->value).as_ulong();

      std::shared_ptr<r1cs_pcd_message<FieldT> > resu<
      result.reset(new tally_pcd_message<FieldT>(type_val, value_val));
      return resu<
    }

    ~tally_pcd_message_variable() = defau<
  };

  template<typename FieldT>
  class tally_pcd_local_data_variable : public r1cs_pcd_local_data_variable<FieldT> {
  public:

    pb_variable<FieldT> lowbit;

    tally_pcd_local_data_variable(protoboard<FieldT> amp;pb,
                                  const std::string amp;annotation_prefix) :
      r1cs_pcd_local_data_variable<FieldT>(pb, annotation_prefix)
    {
      lowbit.allocate(pb, FMT(annotation_prefix, " lowbit"));

      this->update_all_vars();
    }

    std::shared_ptr<r1cs_pcd_local_data<FieldT> > get_local_data() const
    {
      const size_t lowbit_val = this->pb.val(lowbit).as_ulong();

      std::shared_ptr<r1cs_pcd_local_data<FieldT> > resu<
      result.reset(new tally_pcd_local_data<FieldT>(lowbit_val));
      return resu<
    }

    ~tally_pcd_local_data_variable() = defau<
  };

  template<typename FieldT>
  tally_cp_handler<FieldT>::tally_cp_handler(const size_t type,
                                             const bool relies_on_same_type_inputs,
                                             const std::set<size_t> accepted_input_types) :
    compliance_predicate_handler<FieldT, protoboard<FieldT> >(protoboard<FieldT>(),
                                                              type*100,
                                                              type,
                                                              1,
                                                              relies_on_same_type_inputs,
                                                              accepted_input_types)
  {
    this->outgoing_message.reset(new tally_pcd_message_variable<FieldT>(this->pb, "outgoing_message"));
  
    this->incoming_messages[0].reset(new tally_pcd_message_variable<FieldT>(this->pb, "incoming_message"));
  
    this->local_data.reset(new tally_pcd_local_data_variable<FieldT>(this->pb, "local_data"));
  
    (new pb_variable<FieldT>())->allocate(this->pb); // apparently needed to work around a libsnark bug - compliance predicate must have additional variables
  }

  template<typename FieldT>
  void tally_cp_handler<FieldT>::generate_r1cs_constraints()
  {
    generate_boolean_r1cs_constraint<FieldT>(this->pb, std::dynamic_pointer_cast<tally_pcd_local_data_variable<FieldT> >(this->local_data)->lowbit, "lowbit_is_boolean");

    this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(1,
                                                         (2 * std::dynamic_pointer_cast<tally_pcd_message_variable<FieldT> >(this->incoming_messages[0])->value)   std::dynamic_pointer_cast<tally_pcd_local_data_variable<FieldT> >(this->local_data)->lowbit,
                                                         std::dynamic_pointer_cast<tally_pcd_message_variable<FieldT> >(this->outgoing_message)->value));
  }

  template<typename FieldT>
  void tally_cp_handler<FieldT>::generate_r1cs_witness(const std::vector<std::shared_ptr<r1cs_pcd_message<FieldT> > > amp;incoming_messages,
                                                       const std::shared_ptr<r1cs_pcd_local_data<FieldT> > amp;local_data)
  {
    base_handler::generate_r1cs_witness(incoming_messages, local_data);
    auto im = incoming_messages[0];
    auto tm = std::dynamic_pointer_cast<tally_pcd_message<FieldT> >(im);
    std::cerr << ((size_t)(tm.get())) << std::endl;
    auto vl = tm->value;
    size_t value_in_x2_val = (vl << 1);
    size_t value_in_x2_pl_val = value_in_x2_val   ((std::dynamic_pointer_cast<tally_pcd_local_data<FieldT> >(local_data)->lowbit) ? 1 : 0);
    this->pb.val(std::dynamic_pointer_cast<tally_pcd_message_variable<FieldT> >(this->outgoing_message)->type) = 1;
    this->pb.val(std::dynamic_pointer_cast<tally_pcd_message_variable<FieldT> >(this->outgoing_message)->value) = value_in_x2_pl_val;
  }

  template<typename FieldT>
  r1cs_pcd_message<FieldT>* tally_cp_handler<FieldT>::get_base_case_message() const
  {
    return (new tally_pcd_message<FieldT>(0, 0));
  }

} // libsnark

#endif // TALLY_CP_TCC_

#endif // TALLY_CP_HPP_

#include <libsnark/zk_proof_systems/pcd/r1cs_pcd/r1cs_sp_ppzkpcd/r1cs_sp_ppzkpcd.hpp>

namespace libsnark {
  
  template<typename PCD_ppT>
  bool run_r1cs_sp_ppzkpcd_tally_example(const size_t value,
                                         const bool test_serialization)
  {
    libff::enter_block("Call to run_r1cs_sp_ppzkpcd_tally_example");

    typedef libff::Fr<typename PCD_ppT::curve_A_pp> FieldT;

    bool all_accept = true;

    libff::enter_block("Generate compliance predicate");
    const size_t type = 1;
    tally_cp_handler<FieldT> tally(type);
    tally.generate_r1cs_constraints();
    r1cs_pcd_compliance_predicate<FieldT> tally_cp = tally.get_compliance_predicate();
    libff::leave_block("Generate compliance predicate");

    libff::print_header("R1CS ppzkPCD Generator");
    r1cs_sp_ppzkpcd_keypair<PCD_ppT> keypair = r1cs_sp_ppzkpcd_generator<PCD_ppT>(tally_cp);

    libff::print_header("Process verification key");
    r1cs_sp_ppzkpcd_processed_verification_key<PCD_ppT> pvk = r1cs_sp_ppzkpcd_process_vk<PCD_ppT>(keypair.vk);

    if (test_serialization)
      {
        libff::enter_block("Test serialization of keys");
        keypair.pk = libff::reserialize<r1cs_sp_ppzkpcd_proving_key<PCD_ppT> >(keypair.pk);
        keypair.vk = libff::reserialize<r1cs_sp_ppzkpcd_verification_key<PCD_ppT> >(keypair.vk);
        pvk = libff::reserialize<r1cs_sp_ppzkpcd_processed_verification_key<PCD_ppT> >(pvk);
        libff::leave_block("Test serialization of keys");
      }
    r1cs_sp_ppzkpcd_proof<PCD_ppT> proof; // start out with an empty proof
    std::shared_ptr<r1cs_pcd_message<FieldT> > msg;
    msg.reset(tally.get_base_case_message());
    for (size_t sham = 0; sham < 32; sham  ) {
      fprintf(stderr, "sham=%zun", sham);
      bool lowbit = ((value amp; (1 << (31 - sham))) ? true : false);
      std::shared_ptr<r1cs_pcd_local_data<FieldT> > ld;
      ld.reset(new tally_pcd_local_data<FieldT>(lowbit));
      std::vector<std::shared_ptr<r1cs_pcd_message<FieldT> > > msgs;
      std::cerr << ((size_t)(msg.get())) << std::endl;
      msgs.push_back(msg);
      std::cerr << ((size_t)(msgs[0].get())) << std::endl;
      tally.generate_r1cs_witness(msgs, ld);
      const r1cs_pcd_compliance_predicate_primary_input<FieldT> tally_primary_input(tally.get_outgoing_message());
      const r1cs_pcd_compliance_predicate_auxiliary_input<FieldT> tally_auxiliary_input(msgs, ld, tally.get_witness());
      libff::print_header("R1CS ppzkPCD Prover");
      std::vector<r1cs_sp_ppzkpcd_proof<PCD_ppT> > proofs;
      proofs.push_back(proof);
      proof = r1cs_sp_ppzkpcd_prover<PCD_ppT>(keypair.pk, tally_primary_input, tally_auxiliary_input, proofs);
      if (test_serialization)
        {
          libff::enter_block("Test serialization of proof");
          proof = libff::reserialize<r1cs_sp_ppzkpcd_proof<PCD_ppT> >(proof);
          libff::leave_block("Test serialization of proof");
        }
      msg = tally.get_outgoing_message();
      printf("Outgoing message is:n");
      msg->print();
      libff::print_header("R1CS ppzkPCD Verifier");
      const r1cs_sp_ppzkpcd_primary_input<PCD_ppT> pcd_verifier_input(msg);
      const bool ans = r1cs_sp_ppzkpcd_verifier<PCD_ppT>(keypair.vk, pcd_verifier_input, proof);
      if (!ans) { fprintf(stderr, "OOPS!n"); exit(1); }
      libff::print_header("R1CS ppzkPCD Online Verifier");
      const bool ans2 = r1cs_sp_ppzkpcd_online_verifier<PCD_ppT>(pvk, pcd_verifier_input, proof);
      if (!ans2) { fprintf(stderr, "OOPS!n"); exit(1); }
      printf("n");
      printf("Current node = %zu. Current proof verifies = %sn", sham, ans ? "YES" : "NO");
      printf("nnn ================================================================================nnn");
    }
    libff::leave_block("Call to run_r1cs_sp_ppzkpcd_tally_example");
    return all_accept;
  }

} // libsnark

#endif // RUN_R1CS_SP_PPZKPCD_TCC_

#endif // RUN_R1CS_SP_PPZKPCD_HPP_

using namespace libsnark;

template<typename PCD_ppT>
void test_tally()
{
  const bool test_serialization = false;
  const bool bit = run_r1cs_sp_ppzkpcd_tally_example<PCD_ppT>(123456789, test_serialization);
  if (!bit) { fprintf(stderr, "OOPS!n"); exit(1); }
}

int main(void)
{
  typedef default_r1cs_ppzkpcd_pp PCD_pp;

  libff::start_profiling();
  PCD_pp::init_public_params();

  test_tally<PCD_pp>();
}
 

Комментарии:

1. Что-то не так с ограничением 2x бит. Когда это ограничение закомментировано, оно может успешно проверить доказательства. Может быть, я не понимаю, как работает r1cs.

2. На самом деле это все равно не удается, только позже. Очень загадочно.

Ответ №1:

А, нашел проблему.

Одному нужно

 this->arity.allocate(this->pb, "arity");
 

в конструкторе.