Incomplete SW group operations may be worthwhile

[weikengchen]

This is to be left as a todo for the future.

There seems to be a big gap in constraints & density of complete vs incomplete group operations, as well as operations on affine vs projective.

Ideally, if permitted by completeness and soundness, incomplete + affine can lead to fewer constraints & lower density.

However, it seems to require certain efforts to investigate whether the soundness holds, and to what extent. And completeness would be a separate issue that the application needs to handle. Especially, the application needs to have some sort of "reject sampling" so that it can retry proving until it avoids the incompleteness barriers.

[weikengchen]

A potential fix for completeness during additions is probably this:

• Assume we are adding multiple points.
• The prover can instantiate any non-infinity point as the initial value. The prover is supposed to choose a random one.
• The prover needs to subtract the same point as the end.

Since the initial value is random, it may be able to provide some sort of "reject sampling".

[Pratyush]

This issue shows that maybe one can do this without exceptions inside the circuit: zcash/zcash#3924

So the idea would be to convert to affine form, check for exceptional cases in the scalar, perform scalar multiplications via the foregoing algorithm, and to then convert back to projective form.

[Pratyush]

In particular these portions seem relevant: *

• Double and add: https://github.com/ebfull/halo/blob/d9d341f19b1122f975c2fc7c583490a830a9020a/src/gadgets/ecc.rs#L1327
• Scalar multiply: https://github.com/ebfull/halo/blob/d9d341f19b1122f975c2fc7c583490a830a9020a/src/gadgets/ecc.rs#L1762

[weikengchen]

For the record, based on a measurement, our current implementation has roughly 12 constraints and 71 non-zeros per addition.

[weikengchen]

The solution with without exceptions may have 11 constraints, as follows:

• Convert each of the two points to their affine forms => getting x/z and y/z, 2 * 2 = 4 constraints. This check also rules out the infinity points.
• Check the exceptional case; so, it requires that x1 does not equal x2, 1 constraint
• The foregoing algorithm, 6 constraints

So the saving is not significant.

[weikengchen]

If the projective form is unused, but we only use the affine form, then maybe we can have fewer constraints, I assume:

• Check x1 does not equal x2 requires 1 constraint => this is because the addition formula will fail for doubling.
• The foregoing algorithm, 6 constraints.

Given that the affine form is likely to behave very differently from the complete form, it seems better to have a separate trait for it (so, not CurveVar). Any idea on the traits and implementations?

[Pratyush]

The solution with without exceptions may have 11 constraints, as follows:

* Convert each of the two points to their affine forms => getting x/z and y/z, 2 * 2 = 4 constraints. This check also rules out the infinity points.

* Check the exceptional case; so, it requires that x1 does not equal x2, 1 constraint

* The foregoing algorithm, 6 constraints

So the saving is not significant.

I think the idea would be to use the exceptional-addition inside scalar multiplication, where it seems we can do an edge-case once check at the beginning.

So we would have a specialized scalar multiplication, while leaving addition and doubling as-is

[Pratyush]

By the way, another option for some curves with a cofactor is to convert to an alternate form (eg: edwards), and to perform the scalar arithmetic there, and to then convert back to short weierstrass form.

[zhenfeizhang]

In particular these portions seem relevant: *

• Double and add: https://github.com/ebfull/halo/blob/d9d341f19b1122f975c2fc7c583490a830a9020a/src/gadgets/ecc.rs#L1327
• Scalar multiply: https://github.com/ebfull/halo/blob/d9d341f19b1122f975c2fc7c583490a830a9020a/src/gadgets/ecc.rs#L1762

Is there an API to call scalar multiplications over an EdwardsVar as in the second link?
Or are the callers expected to do a double-then-add approach?

[weikengchen]

@zhenfeizhang The current library implements group elements on Edward curves as ProjectiveCurve and AffineCurve, so they can use the corresponding interfaces: https://github.com/arkworks-rs/algebra/blob/master/ec/src/models/twisted_edwards_extended.rs

And the ProjectiveCurve interface has mul: https://github.com/arkworks-rs/algebra/blob/master/ec/src/lib.rs#L209, which can be used for scalar mult.

[Pratyush]

see also this paper which reduces the number of muls compared to [ELM02].

NVM, it's slower than [ELM02] because it assumes inversions are expensive. It's instead faster than [CJLM06], which is a followup to [ELM02].

[zhenfeizhang]

I guess there was some misunderstanding. I am wondering about group muls over Vars rather than ProjectiveCurve or AffineCurve. Is there an API for this? Or should the caller do it themselfs?

looking at the code here:
https://github.com/arkworks-rs/crypto-primitives/blob/ce5cc89011b394eb006987a24088947d5099d641/src/commitment/pedersen/constraints.rs#L77

it seems that there isn't an API -- the caller needs to decomposite the scalars and then do the scalar mul.
Is this a fair understanding?

[weikengchen]

@zhenfeizhang I look up the curve's interface, does this one work for you? https://github.com/arkworks-rs/succinct_r1cs/blob/0164f52ae0109c6e0a89c75fc9abc66c4ec0c5dc/r1cs-std/src/groups/mod.rs#L91

[zhenfeizhang]

LOL. This is likely a private repo :-) I don't have access

[weikengchen]

Sorry, wrong link. This one:

r1cs-std/src/groups/mod.rs

Line 91 in 636f93a

fn scalar_mul_le<'a>(

[zhenfeizhang]

Yes. Thanks!

[Pratyush]

So, this is implemented now, but without the optimizations from zcash/zcash#3924