scipr-lab / libsnark

C++ library for zkSNARKs
Other
1.8k stars 570 forks source link

Use of `long` in sha256_round_function_gadget provides incorrect constraints on 32bit platform #157

Open HarryR opened 4 years ago

HarryR commented 4 years ago

The use of long type for variable K in the sha256_round_function_gadget gadget breaks stuff when building on platforms where long is 32bit.

Specifically, in sha256_components.tcc the SHA256_K array is typed unsigned long.

However, in the sha256_round_function_gadget definition the parameter type for K is simply long.

So the constant term for the unreduced_new_e and unreduced_new_a constraints is interpreted as p-K (because it's negative...).

Example diff of constraints, where green is 64bit platform and red is 32bit platform:

    <a,(1,x)> = 1
-   <b,(1,x)> = 21888242871839275222246405745257275088548364400416034343698204186575137909401
+   <b,(1,x)> = 3624381080
    <c,(1,x)> = 0
 constraint was:
 terms for a:
     1 * 1
 terms for b:
-    1 * 21888242871839275222246405745257275088548364400416034343698204186575137909401
+    1 * 3624381080
     x_1814 * 1
     where x_1814 (module.leaf_hash.hasher input_hasher packed_W_8) was assigned value 0
       i.e. negative of 0

Because of this bug the proofs on both 32bit and 64bit platforms are self-consistent, but the constraint system is different - so the same proving key doesn't work on both platforms.

Changing the definition of the K variable in sha256_round_function_gadget to unsigned long does not fix the problem, because the Fp_model constructor with default arguments thinks that the variable is signed.

There is only one constructor:

Fp_model(const long x, const bool is_unsigned=false);

Which performs implicit conversion from an unsigned long to a long then re-interprets it as a signed integer because the is_unsigned flag is never provided (e.g. via the linear combination + operator).

Changing the type of the K instance variable to FieldT constructor to the following fixes the problem:

template<typename FieldT>
sha256_round_function_gadget<FieldT>::sha256_round_function_gadget(protoboard<FieldT> &pb,
                                                                   const pb_linear_combination_array<FieldT> &a,
                                                                   const pb_linear_combination_array<FieldT> &b,
                                                                   const pb_linear_combination_array<FieldT> &c,
                                                                   const pb_linear_combination_array<FieldT> &d,
                                                                   const pb_linear_combination_array<FieldT> &e,
                                                                   const pb_linear_combination_array<FieldT> &f,
                                                                   const pb_linear_combination_array<FieldT> &g,
                                                                   const pb_linear_combination_array<FieldT> &h,
                                                                   const pb_variable<FieldT> &W,
                                                                   const unsigned long K,
                                                                   const pb_linear_combination_array<FieldT> &new_a,
                                                                   const pb_linear_combination_array<FieldT> &new_e,
                                                                   const std::string &annotation_prefix) :
    gadget<FieldT>(pb, annotation_prefix),
    a(a),
    b(b),
    c(c),
    d(d),
    e(e),
    f(f),
    g(g),
    h(h),
    W(W),
    K(K, true),
    new_a(new_a),
    new_e(new_e)
{

However, I really recommend that the Fp_model doesn't take long variable with an extra unsigned parameter to do the equivalent of a static_cast - and instead handles long and unsigned long separately.