feat: split field in field emulation into Field and FieldAPI

[ivokub]

Previously there was a single type for exposing field emulation which implemented frontend.API. For writing circuits it was good enough, but it was slightly inconvenient for writing gadgets and defining types on top of non-native Element, as we had to type assert the variables and didn't have some specialised methods (multiplication by constant, for example). Now separated into two Field[T] and FieldAPI[T]. FieldAPI[T] should work as previously (plus I fixed some small bugs here and there on the go) and Field[T] allows to work directly over *Element[T] types.

Internally, changed the implementation such that FieldAPI[T] depends on Field[T] by doing type checking/asserting on the fly. Added a few methods to Field[T] such as MulConst (multiplication by a small constant, very useful for elliptic curves), MulMod (mul+reduce, while testing the circuits made it looks that gives on average lesser number of constraints), MulModMutable (mul+reduce+mutable reduction of the inputs) and corresponding analogues for addition and subtraction.

When I was at it, updated the documentation and added a few documentation examples (how to use Field[T], FieldAPI[T]).

I'll update ECDSA on top of it and then I think I'm finally done :)

[SherLzp]

@ivokub Hi Sir, right now is that available to use field emulation to emulate BW6-761 curve based Groth16/PLONK verification on BN254 curve for Groth16/PLONK proving system?

[ivokub]

@ivokub Hi Sir, right now is that available to use field emulation to emulate BW6-761 curve based Groth16/PLONK verification on BN254 curve for Groth16/PLONK proving system?

Hi,

Am I understanding correctly:

• you want to verify Groth16 or PLONK proof,
• the proof is given over BW6-761 (emulated field),
• the native field is BN254,
• you want to verify proof in Groth16 and PLONK circuits.

Right now you are right it is not possible. We are lacking BW6-761 field emulation description, but it would be simple to add.

For Groth16/PLONK we also need pairings over BW6-761 with field emulations, but this isn't something we are working on right now or intending to include soon. We are working right now on adding BN254 pairing using field emulation and it could be used as a baseline for BW6-761, but it would still require some work.

And I do not think we have PLONK verifier in-circuit yet. I think at some point it makes sense to implement it, but I'm not sure about the timeline. We do have Groth16 verifier, but using 2-chains, not using field emulation. I have tried porting the 2-chain verifier to field emulation and it in general works, but requires a lot of optimisation.

Can you describe why are you particularly interested in these choices of curves? Are you trying to have 3 layers of recursion (BLS12-377 -> BW6-761 -> BN254). The problem with BW6-761 is that its base field is huge and it will be very expensive to emulate (compared to directly emulating BLS12-377 on BN254, for example).

[SherLzp]

@ivokub Hi Sir, right now is that available to use field emulation to emulate BW6-761 curve based Groth16/PLONK verification on BN254 curve for Groth16/PLONK proving system?

Hi,

Am I understanding correctly:

• you want to verify Groth16 or PLONK proof,
• the proof is given over BW6-761 (emulated field),
• the native field is BN254,
• you want to verify proof in Groth16 and PLONK circuits.

Right now you are right it is not possible. We are lacking BW6-761 field emulation description, but it would be simple to add.

For Groth16/PLONK we also need pairings over BW6-761 with field emulations, but this isn't something we are working on right now or intending to include soon. We are working right now on adding BN254 pairing using field emulation and it could be used as a baseline for BW6-761, but it would still require some work.

And I do not think we have PLONK verifier in-circuit yet. I think at some point it makes sense to implement it, but I'm not sure about the timeline. We do have Groth16 verifier, but using 2-chains, not using field emulation. I have tried porting the 2-chain verifier to field emulation and it in general works, but requires a lot of optimisation.

Can you describe why are you particularly interested in these choices of curves? Are you trying to have 3 layers of recursion (BLS12-377 -> BW6-761 -> BN254). The problem with BW6-761 is that its base field is huge and it will be very expensive to emulate (compared to directly emulating BLS12-377 on BN254, for example).

Hi @ivokub ,
Thanks for your feedback. That's what I want to do as you described. I'm trying to have 3 layers of recursion. Due to the limit of Ethereum or other EVM-based chains, they only support BN254 as native operations. By using 3 layers of recursion, we can greatly improve the performance(maybe TPS) or verify more data on-chain.

If I want to emulate BW6-761 operations on BN254, can I follow the code here to simulate a implementation? https://github.com/ConsenSys/gnark/tree/master/std/algebra/fields_bls12377
https://github.com/ConsenSys/gnark/tree/master/std/algebra/sw_bls12377

What do you think about the constraints cost for emulating pairing operation of BW6-761 on BN254? Will that close to 20M(which is also acceptable)? If we try to use plookup, will that greatly reduce the constraints cost?

[ivokub]

If I want to emulate BW6-761 operations on BN254, can I follow the code here to simulate a implementation? https://github.com/ConsenSys/gnark/tree/master/std/algebra/fields_bls12377 https://github.com/ConsenSys/gnark/tree/master/std/algebra/sw_bls12377

When I started implementing BN254 pairing using field emulation, then @yelhousni recommended me to start from its implementation in gnark-crypto, as sw_bls12377 is heavily optimized for the particular 2-chain. So have a look here.

What do you think about the constraints cost for emulating pairing operation of BW6-761 on BN254? Will that close to 20M(which is also acceptable)? If we try to use plookup, will that greatly reduce the constraints cost?

I have no idea. Extrapolating from sw_bls12377 which is approx 12k, and assuming 1000x blowup, then lower bound would be 12M. But bw6-761 is more than 2x longer field, so would be approx 2x more difficult. So, ballpark lower bound is approx 20M, but could go higher.

Plookups (particularly, more efficient range proofs for limb constraining in field emulation) would help a lot. They are planned, but cannot give an estimate.

[SherLzp]

If I want to emulate BW6-761 operations on BN254, can I follow the code here to simulate a implementation? https://github.com/ConsenSys/gnark/tree/master/std/algebra/fields_bls12377 https://github.com/ConsenSys/gnark/tree/master/std/algebra/sw_bls12377

When I started implementing BN254 pairing using field emulation, then @yelhousni recommended me to start from its implementation in gnark-crypto, as sw_bls12377 is heavily optimized for the particular 2-chain. So have a look here.

What do you think about the constraints cost for emulating pairing operation of BW6-761 on BN254? Will that close to 20M(which is also acceptable)? If we try to use plookup, will that greatly reduce the constraints cost?

I have no idea. Extrapolating from sw_bls12377 which is approx 12k, and assuming 1000x blowup, then lower bound would be 12M. But bw6-761 is more than 2x longer field, so would be approx 2x more difficult. So, ballpark lower bound is approx 20M, but could go higher.

Plookups (particularly, more efficient range proofs for limb constraining in field emulation) would help a lot. They are planned, but cannot give an estimate.

Thanks for your reply! I will dig into it.

[SherLzp]

Hi sir @ivokub ,

I tried the test here: https://github.com/ConsenSys/gnark/blob/develop/std/math/emulated/field_test.go#L274
which aims to run pairing of BLS12-377 on BN254, it will cost 93M constraints.

But I see the result from here: https://github.com/yi-sun/circom-pairing
It seems only cost close to 20M constraints.

Do you have any ideas about which part makes the computation so heavy?

As we dicsussed before, I try to run pairing of BW6-761 on BN254: https://github.com/SherLzp/gnark/blob/develop/std/algebra/sw_bw6761/pairing_test.go#L121
It will crash if I open this part: https://github.com/SherLzp/gnark/blob/develop/std/algebra/fields_bw6761/e6.go#L190
The error is:

    pairing_test.go:122: 
        	Error Trace:	D:\Projects\mygo\src\Zecrey\SherLzp\gnark\std\algebra\sw_bw6761\pairing_test.go:122
        	Error:      	Received unexpected error:
        	            	NewHint: input length mismatch
        	            	emulated.computeDivisionHint[...]

        	            		hints.go:217
        	            	emulated.(*field[...]).Div
        	            		field.go:171
        	            	emulated.(*field[...]).DivUnchecked
        	            		field.go:155
        	            	fields_bw6761.(*E6).DecompressKarabina
        	            		e6.go:190
        	            	fields_bw6761.(*E6).Expt
        	            		e6_pairing.go:56
        	            	sw_bw6761.FinalExponentiation
        	            		pairing.go:90
        	            	sw_bw6761.Pair
        	            		pairing.go:60
        	            	sw_bw6761.(*pairingBW6761).Define

        	            		pairing_test.go:43
        	Test:       	TestPairingBW6761

Do you know what's the reason of it?

In addition, it will cost at least 220M constraints to do pairing of BW6-761, that's too bad performance.

[ivokub]

I tried the test here: https://github.com/ConsenSys/gnark/blob/develop/std/math/emulated/field_test.go#L274 which aims to run pairing of BLS12-377 on BN254, it will cost 93M constraints.

But I see the result from here: https://github.com/yi-sun/circom-pairing It seems only cost close to 20M constraints.

Do you have any ideas about which part makes the computation so heavy?
Did you run it on develop? Looking at the error below, it looks to be the case.

The first implementation of the field emulation was not very optimal. I think the main reason for the high number of constraints for the pairing is due to amortised reduction. It seemed a good approach (which other projects had also recommended), but in practice seems to give worse result than modular reducing after every multiplication. The problem with amortising modular reductions is that the cost of the reduction becomes higher and the cost spreads into consecutive operations which use non-reduced inputs.

As we dicsussed before, I try to run pairing of BW6-761 on BN254: https://github.com/SherLzp/gnark/blob/develop/std/algebra/sw_bw6761/pairing_test.go#L121 It will crash if I open this part: https://github.com/SherLzp/gnark/blob/develop/std/algebra/fields_bw6761/e6.go#L190 The error is:
Do you know what's the reason of it?

This is a bug. Fixed in this PR.

Otherwise - I also tried writing gadgets using field emulation with the previous "fake-API" method, but it doesn't provide enough freedom to optimise for field emulation. In this PR, I have separated fake-API and Field, where we can directly work with emulated.Element instances (not frontend.Variable). This new type provides more methods (for example Mul, MulMod etc.).

I have rudimentary implementation of another pairing in #411 which uses field emulation natively (instead of through fake-API). I just completed it yesterday and haven't been able to fully compile yet, but hopefully could show significant improvement. We are thinking about making the pairing implementation over different curves generic, but right now it is only for BN254.

[SherLzp]

The first implementation of the field emulation was not very optimal. I think the main reason for the high number of constraints for the pairing is due to amortised reduction. It seemed a good approach (which other projects had also recommended), but in practice seems to give worse result than modular reducing after every multiplication. The problem with amortising modular reductions is that the cost of the reduction becomes higher and the cost spreads into consecutive operations which use non-reduced inputs.

@ivokub
Will we use modular reductions instead of amortised reductions in this PR #411 ?

I have rudimentary implementation of another pairing in #411 which uses field emulation natively (instead of through fake-API). I just completed it yesterday and haven't been able to fully compile yet, but hopefully could show significant improvement. We are thinking about making the pairing implementation over different curves generic, but right now it is only for BN254.

That's cool, just saw it yesterday. I will follow your branch to implement the pairing of BW6-761.

[ivokub]

@ivokub Will we use modular reductions instead of amortised reductions in this PR #411 ?

That's cool, just saw it yesterday. I will follow your branch to implement the pairing of BW6-761.

@SherLzp, I tried compiling the BN254 pairing with non-amortized reductions. With Groth16 and BN254 as native field the cost for Miller loop is 9.8M and final exp 11.3M. Note that both tests include equality assertion (for checking the correctness of the result) and thus the actual costs are slightly smaller. So, ballpark estimate for full pairing is 21M constraints.

[SherLzp]

@ivokub Will we use modular reductions instead of amortised reductions in this PR #411 ?
That's cool, just saw it yesterday. I will follow your branch to implement the pairing of BW6-761.

@SherLzp, I tried compiling the BN254 pairing with non-amortized reductions. With Groth16 and BN254 as native field the cost for Miller loop is 9.8M and final exp 11.3M. Note that both tests include equality assertion (for checking the correctness of the result) and thus the actual costs are slightly smaller. So, ballpark estimate for full pairing is 21M constraints.

Hi sir @ivokub ,

I think there are still some bugs exist for Field, Element and FieldAPI.

I follow your code to implement the BW6761 pairing on BN254 native field. When I try to add a test for MulBy034 for e6 (https://github.com/SherLzp/gnark/blob/develop/std/algebra/pairing_bw6761/e6_pairing_test.go#L145), it comes to the not equal error. However, every operation in MulBy034 has passed tests in https://github.com/SherLzp/gnark/blob/develop/std/algebra/pairing_bw6761/e3_test.go

I try to print it out, it's not easy to do that and I find that it seems it did not do modular operation after every operation, such as Mul, Add. When I try to print the value by MulByElement here: https://github.com/SherLzp/gnark/blob/develop/std/algebra/pairing_bw6761/e6_pairing.go#L101
It seems the limbs are quite bigger than just fp.Element{}.Mul() gives.

What's more, when I try to make the test for FinalExponentiation here: https://github.com/SherLzp/gnark/blob/develop/std/algebra/pairing_bw6761/pairing_test.go#L103
It will come to the following error:

15:02:22 DBG running circuit in test engine
    pairing_test.go:130: 
        	Error Trace:	D:\Projects\mygo\src\Zecrey\SherLzp\gnark\std\algebra\pairing_bw6761\pairing_test.go:130
        	Error:      	Received unexpected error:
        	            	[assertIsEqual] 18578408903715543 == 450923973131283159
        	            	bits.toBinary
        	            		conversion_binary.go:93
        	            	bits.ToBase
        	            		conversion.go:25
        	            	bits.ToBinary
        	            		conversion_binary.go:18
        	            	emulated.(*Field[...]).EnforceWidth
        	            		field_assert.go:135

        	            	emulated.(*Field[...]).PackLimbs
        	            		field.go:114
        	            	emulated.(*Field[...]).computeQuoHint
        	            		hints.go:141
        	            	emulated.(*Field[...]).AssertIsEqual
        	            		field_assert.go:158

        	            	emulated.(*Field[...]).Reduce
        	            		field_ops.go:226
        	            	emulated.(*Field[...]).reduceAndOp
        	            		field_ops.go:350
        	            	emulated.(*Field[...]).Mul
        	            		field_ops.go:104
        	            	pairing_bw6761.ext6.CyclotomicSquareCompressed
        	            		e6.go:125
        	            	pairing_bw6761.ext6.nSquareCompressed
        	            		e6_pairing.go:30
        	            	pairing_bw6761.ext6.Expt
        	            		e6_pairing.go:55
        	            	pairing_bw6761.Pairing.FinalExponentiation
        	            		pairing.go:101
        	            	pairing_bw6761.(*finalExponentiationBW6761).Define
        	            		pairing_test.go:93
        	Test:       	TestFinalExponentiationBW6761
--- FAIL: TestFinalExponentiationBW6761 (1.85s)
FAIL

Could you help me figure out what happend here?

In addition, could you please give an example as you mentioned about non-amortized reductions?

[ivokub]

@SherLzp, I'll have a look tomorrow, I am traveling today. I have a local branch which is useful for debugging code as can print variable values in test engine.

It may be there are still bugs.

[ivokub]

@SherLzp, I continued the discussion thread in #420. This PR is now merged and difficult to track.