knapsack_gadget.hpp

Go to the documentation of this file.

 
#ifndef KNAPSACK_GADGET_HPP_
#define KNAPSACK_GADGET_HPP_
 
#include <libsnark/common/data_structures/merkle_tree.hpp>
#include <libsnark/gadgetlib1/gadgets/basic_gadgets.hpp>
#include <libsnark/gadgetlib1/gadgets/hashes/hash_io.hpp>
 
namespace libsnark
{
 
/************************** Choice of dimension ******************************/
 
template<typename FieldT> struct knapsack_dimension {
    // the size of FieldT should be (approximately) at least 200 bits
    static const size_t dimension = 1;
};
 
/*********************** Knapsack with field output **************************/
 
template<typename FieldT>
class knapsack_CRH_with_field_out_gadget : public gadget<FieldT>
{
private:
    static std::vector<FieldT> knapsack_coefficients;
    static size_t num_cached_coefficients;
 
public:
    size_t input_len;
    size_t dimension;
 
    block_variable<FieldT> input_block;
    pb_linear_combination_array<FieldT> output;
 
    knapsack_CRH_with_field_out_gadget(
        protoboard<FieldT> &pb,
        const size_t input_len,
        const block_variable<FieldT> &input_block,
        const pb_linear_combination_array<FieldT> &output,
        const std::string &annotation_prefix);
    void generate_r1cs_constraints();
    void generate_r1cs_witness();
 
    static size_t get_digest_len();
    // return 0 as block length, as the hash function is variable-input
    static size_t get_block_len();
    static std::vector<FieldT> get_hash(const libff::bit_vector &input);
    static void sample_randomness(const size_t input_len);
 
    // for debugging
    static size_t expected_constraints();
};
 
/********************** Knapsack with binary output **************************/
 
template<typename FieldT>
class knapsack_CRH_with_bit_out_gadget : public gadget<FieldT>
{
public:
    typedef libff::bit_vector hash_value_type;
    typedef merkle_authentication_path merkle_authentication_path_type;
 
    size_t input_len;
    size_t dimension;
 
    pb_linear_combination_array<FieldT> output;
 
    std::shared_ptr<knapsack_CRH_with_field_out_gadget<FieldT>> hasher;
 
    block_variable<FieldT> input_block;
    digest_variable<FieldT> output_digest;
 
    knapsack_CRH_with_bit_out_gadget(
        protoboard<FieldT> &pb,
        const size_t input_len,
        const block_variable<FieldT> &input_block,
        const digest_variable<FieldT> &output_digest,
        const std::string &annotation_prefix);
    void generate_r1cs_constraints(const bool enforce_bitness = true);
    void generate_r1cs_witness();
 
    static size_t get_digest_len();
    // return 0 as block length, as the hash function is variable-input
    static size_t get_block_len();
    static hash_value_type get_hash(const libff::bit_vector &input);
    static void sample_randomness(const size_t input_len);
 
    // for debugging
    static size_t expected_constraints(const bool enforce_bitness = true);
};
 
template<typename FieldT> void test_knapsack_CRH_with_bit_out_gadget();
 
} // namespace libsnark
 
#include <libsnark/gadgetlib1/gadgets/hashes/knapsack/knapsack_gadget.tcc>
 
#endif // KNAPSACK_GADGET_HPP_