Pedersen hash doesn't seem to work with bls12-377 curve

[brunoffranca]

When using a Pedersen hash (primitive and gadget) with the following parameters:

pub type CRH = PedersenCRH<bls12_377::G1Projective, CRHWindow>;

#[derive(Clone, PartialEq, Eq, Hash)]
pub struct CRHWindow;

impl PedersenWindow for CRHWindow {
    const WINDOW_SIZE: usize = 128;
    const NUM_WINDOWS: usize = 8;
}

pub type CRHGadget = PedersenCRHGadget<bls12_377::G1Projective, bls12_377::Fq, bls12_377::G1Gadget>;

pub type CRHGadgetParameters = <CRHGadget as FixedLengthCRHGadget<CRH, bls12_377::Fq>>::ParametersGadget;

The gadget and the primitive output different points even when given the same input. The tests crh_works and crh_primitive_gadget_test fail. Weirdly enough, the tests pass with Jujub.

[kobigurk]

I think you need to convert the results of the primitive into affine.

[brunoffranca]

I already do that for both tests. https://github.com/nimiq/nano-sync/blob/recursive/tests/crh.rs on lines 84 and 148.

[kobigurk]

Great :) Interested to see what's the cause. Regardless, can I ask why you're not using it on an embedded Edwards curve?

[paberr]

I just quickly adapted the test in zexe to BLS and it indeed fails: https://github.com/nimiq/zexe/commit/08cd892f2b15eadac5848b14b4b5218a74be8027

test crh::pedersen::constraints::test::crh_primitive_gadget_test ... FAILED

failures:

---- crh::pedersen::constraints::test::crh_primitive_gadget_test stdout ----
number of constraints for input: 1024
number of constraints for input + params: 1024
number of constraints total: 8191
thread 'crh::pedersen::constraints::test::crh_primitive_gadget_test' panicked at 'assertion failed: `(left == right)`
  left: `Fp384(BigInteger384([1044931194681323509, 10839921469360585645, 751076044732586611, 8933225529377120444, 15727545806229301931, 107727304234145827]))`,
 right: `Fp384(BigInteger384([18139646206403924450, 16490754173801960651, 221884837633408559, 17129946961311561011, 15365125705913625573, 9245255423297427]))`', crypto-primitives/src/crh/pedersen/constraints.rs:188:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

failures:
    crh::pedersen::constraints::test::crh_primitive_gadget_test

test result: FAILED. 1 passed; 1 failed; 0 ignored; 0 measured; 13 filtered out

[brunoffranca]

Great :) Interested to see what's the cause. Regardless, can I ask why you're not using it on an embedded Edwards curve?

Because we are using the Pedersen hash as part of a BLS signature. So we need it on the BLS12-377 curve. Anyway, it should work on any curve.

[kobigurk]

I looked at this more closely. I believe you're encountering a problem because precomputed_base_multiscalar_mul start from zero - https://github.com/scipr-lab/zexe/blob/295d25d847c6d519551b8a8005e05ed8310a6301/r1cs-std/src/groups/mod.rs#L143, but since addition is incomplete and assumes that neither points that are being added are zero it produces the wrong results.

To protect against mistakes as a prover, checks can be added. To protect against that as a verifier will be harder I think.

[Pratyush]

Hmm right, it's basically an bug with precomputed_base_multiscalar_mul. (The same condition as here should be enforced.)

Implementing something like https://github.com/scipr-lab/zexe/issues/82 would fix this.

[brunoffranca]

So, doesn't this have an easier solution than implementing #82?

[Pratyush]

Hmm let me think about it for a little bit; I'll update the issue with any thoughts I have

[brunoffranca]

This is a very "hacky" solution, but the way we have been working around not being able to start a running sum with zero is by starting it with a generator point and then subtracting the generator point at the end. You can see it at our implementation of Pedersen hash (https://github.com/nimiq/nano-sync/blob/recursive/src/gadgets/pedersen.rs).

[kobigurk]

This is a very "hacky" solution, but the way we have been working around not being able to start a running sum with zero is by starting it with a generator point and then subtracting the generator point at the end. You can see it at our implementation of Pedersen hash (https://github.com/nimiq/nano-sync/blob/recursive/src/gadgets/pedersen.rs).

I used a similar technique somewhere else, when adding public keys together. There, however, I could assume that this would always be fine since it could be checked by the protocol itself. Haven't thought too much about how it applies here.

[Pratyush]

This should work in master now, as we use complete formulae now.

[burdges]

You should prefer the "jubjub" based on bw6 or whatever instead of doing literally this normally.

[brunoffranca]

You should prefer the "jubjub" based on bw6 or whatever instead of doing literally this normally.

Meanwhile we changed to the MNT curves. But we will eventually update to using the "jubjub" curve on MNT4-753.

[weikengchen]

There is a "jubjub" for MNT4-753: https://github.com/scipr-lab/zexe/blob/master/algebra/src/ed_on_mnt4_753/curves/mod.rs