Improve subgroup enforcements

[arielgabizon]

The jubjub group contains a prime subgroup of cofactor 8, that the honest prover is always supposed to use. In the current circuit we do not always enforce elements being in the prime subgroup, as such checks are expensive, and only check points are not of small order. Our analysis shows no harm can come from a malicious prover using (high order) points outside of the subgroup, but still, ideally with cost considerations aside, we would want to enforce input points being in the subgroup.
Here are two ways to do this cheaply in a future upgrade.

1. (Suggested by the QED-it team - @kobigurk, Daniel Benarroch, Aurélien Nicolas) Give as input to the circuit the point P/8 instead of P, and multiply by 8 in the circuit (this costs the same as multiplying P by 8 for a small order check)

2. Use Ristretto https://blog.chain.com/faster-bulletproofs-with-ristretto-avx2-29450b4490cd to
   obtain a prime group with the same discrete log hardness as the underlying Edwards curve.

[arielgabizon]

The main difference between 1 & 2 is that Ristretto enforces a unique legal encoding on the subgroup point; whereas the P/8 encoding gives 8 legal encodings per point.
It seems almost certain the P/8 encoding and decoding is more efficient (and is immediately generalizable to any cofactor h vs Ristretto being curve & cofactor specific afaik)
The uniqueness is potentially important if you use the encoding as a hash input to compute a nullifier or something.
However, if you make sure the encoded P/8 input is only used in the circuit for decoding and nowhere else it's equivalent to a circuit that started with a unique encoding. This perhaps raises interesting questions about having mechanisms in circuit languages like bellman & Zokrates to say "These inputs should only be used in this way"

[daira]

I don't understand the claim that "the P/8 encoding gives 8 legal encodings per point." P/8 is a private input to the circuit; P has only one legal encoding.

IMHO the P/8 (or more generally P/h) approach is clearly simpler and more general than Ristretto. It also represents each group element by a point in the subgroup (unlike Ristretto which uses a coset element that is unique but not necessarily in the subgroup). This facilitates converting to the birationally equivalent Montgomery form and using incomplete addition in the implementation of scalar multiplication, which is much more efficient.

[arielgabizon]

I don't understand the claim that "the P/8 encoding gives 8 legal encodings per point." P/8 is a private input to the circuit; P has only one legal encoding.

If you define "legal" as what we actually enforce, and we only enforce being on the curve and not being in the subgroup cause we want it to be cheap, then P has 8 legal encodings.

IMHO the P/8 (or more generally P/h) approach is clearly simpler and more general than Ristretto. It also represents each group element by a point in the subgroup (unlike Ristretto which uses a coset element that is unique but not necessarily in the subgroup). This facilitates converting to the birationally equivalent Montgomery form and using incomplete addition in the implementation of scalar multiplication, which is much more efficient.

I basically agree, of course the (perhaps minor in our context) caveat, is that you have to enclose the encoding not to touch anywhere where uniqueness of encoding matters. Seems it's fine when it's a private input to the decoding by *8 function. I'm not familiar enough with Bellman to understand whether private input really means no-one can accidentally use it elsewhere.

So moving to Montgomery requires a subgroup point? I didn't know that, that is a point if favor of P/8.
In terminology though, we should perhaps say the decoding output is in the subgroup, not the encoding, assuming we don't want to do subgroup checks on encodings.

[arielgabizon]

Btw, I've understood Ristretto a bit more by now. Seems the main cost of decoding is two strict <r checks..so about 255 constraints I guess.

[daira]

I meant that P has only one legal encoding if [8] [P/8] = P ≠ 𝓞 is enforced.

The bellman API does keep private inputs properly scoped to the gadget using them.

I referred to (prime-order) group elements as being represented by points in the subgroup, which is the correct terminology I think.

Strict < r_S checks take 323 constraints each using the optimized method in Appendix A.3.2.2 of the spec. (I'm not sure whether you meant r_S or r_J; they're roughly the same.)

[arielgabizon]

I meant that P has only one legal encoding if [8] [P/8] = P ≠ 𝓞 is enforced.
I referred to (prime-order) group elements as being represented by points in the subgroup, which is the correct terminology I think.

Perhaps nitpicking, but I think the best way to think about this is that a "legal encoding" is whatever will successfully pass the decoding procedure, and I'm assuming we want the decode procedure to be "1.check point is on curve 2. multiply by 8"

Strict < rS checks take 323 constraints each using the optimized method in Appendix A.3.2.2 of the spec. (I'm not sure whether you meant rS or rJ; they're roughly the same.)

I meant rS, cause what we're checking is an x coordinate of a curve point.
OK, so looks like Ristretto will cost 650-700 constraints.