tags: Meetings

Choice of curves

Goal:

• We will have one curve or cycle of curves chosen for Midnight
• Goal of being rollup friendly
• There are sidechain constraints and there are plutus constraints
• Came up from weekly executive meeting. We need to justify the decision.
• If we make changes soon enough (before handing the keys over), we are the ones taking the decision (rather than convincing the community). Nonetheless, we should justify/motivate this decision as if we had to convince the community (we should have ADRs for this decision).
• The discussion here concerns (cycle of) curves that will be used in midnight. However, the mid/long-term goal is to be able to verify midnight proofs on main-net. This is why Cardano also has weight on this decision (as Plutus will need built-in functions for efficient verification on main-net).

Seems to be clear that there is not one perfect curve that solves all our problems. So we have to understand the trade-offs:

1. Performant proofs at launch and somewhat messy scalability story (heavier engineering lift and not very performant scalability solution).
2. Less performant proofs (linear verification? and logarithmic size) at launch and very clean scalability solution when we cross the bridge. However, these proofs can be batched, and this is how the work can be offloaded.

• This discussion would not only affect midnight, but also other layer 2 solutions.

Jon's requirements:

• Recursion, I would like to have it if we can have predictable cost. We need on-chain execution to be known ahead of time.
• If the choice of curse affect our ability to have a light client (e.g. ruinning the client in the browser), that should also be considered. 'It is a nice to have if we can avoid the proof server'.

Polygon-style:

• Use STARKs for recursion

• Make a Groth16 proof for the STARK

• Publish Groth16 on main-net

• Downsides:

  • It's complex as f***
  • The prover can become quite complex (may require involvement of GPUs).

• If verification is non-constant, this could result in DoS attacks. We have a threshold which we can spend on verifying a transaction -> concern that if we use non-constant proofs we might go over this threshold quite fast.

• Decent chance that doing this proof in WASM (in browser) might kill off browser. Groth16 of the recursion STARKs is not ligh-client friendly.

We should see this problem with different 'citizens' of proof generators:

1. On the one hand we have the Midnight users create 'Layer 1 proofs'
2. On the other hand we have aggregators that create 'Aggregation proofs'

Do we really have a usecase/scenario were recursion is a requirement?

We will want to have rollups at some point. If we make the choice under the current constraints that might not require recursion, changing in the future would be much more complex

But do rollups require recursion?

In our particular case we need to prove the correctness of transactions (which are the 'Layer 1 proofs' mentioned above), which means proving correctness of proofs, and hence recursion. The reason why we use proofs instead of signatures is because of privacy.

In Kachina we prove that a state transition is correct with respect to a script, but you do not need to use the current state to create the proof (which would invalidate it after a state update).

===== Let's (temporarily) roll out pairing friendly curves (BLS/BN) =====

STARK based proofs are much more performant, but require a much higher engineering effort to achieve the solution.

Building a proving system based on STARKs is not realistic. It would take a lot of time. It would be worth checking if there exists some existing libraries for the STARKs-KZG style of proofs. For example, checking if kimchi could help us here.

On the other hand, if we don't want to use KZG and we stick to pasta curves, the most reasonable path would be to use Halo2.

FRI goes with AIR. Moving from plonkish arithmetization to AIR is what is non-trivial.

FRI works well with small field sizes, so this would result in having to implement wrong-field arithmetic.

Is performance of recursion similar between IPA and SNARKs?

It is unclear the performance difference. We do not expertise of SNARKs in-house.

Would it be possible to have Pasta + IPA on midnight, and translate the 'aggregation' proof to KZG based or Groth16? (this may we worth given that these aggregation proofs that go to main-net do not happen very often)

Has not been done before. Feasiable, but maybe not within this year. Difficult would be to emulate the curve, but because they are smaller, we don't need wrong-field arithmetic (we are good with some reductions). This would require time dedication to fully understand the complexity of the solution.

However, each regular operation you need to add modulo constraints, which might be expensive nonetheless. You need to use padding (verifier key needs to be constant length). Seems that public inputs might complicate this recursion [Didn't fully understand this point though]. Multiscalar multiplication are arbitrary size, so we need to put an upper bound. We could fix certain scripts (i.e.: one for 2^20 constraints, one for 2^25 constraints) so that their verification is constant, but then we would need to handle different verification keys, which increases complexity.

Suggestion is to use Groth16 instead of plonk to wrap up the IPA recursion proofs.

Pasta curves (there is an audit of the curve implementation)

• Verification several scripts same block?

Pluto/Eris

If auditing is a concern, we should nonetheless consider it, as we'll have to go through a ton of audits.

• SafeCurve criteria is passing
• 2-adicity 2^32, which is much better than BN. Which means we could put bigger circuits inside of the curve (future proof)
• Seemingly, it will take a lot of memory requirements (order of 10s of GB for not so big circuits)

Standardisation friendliness

Only mentions to BLS or BN curves for pairing friendly. Pluto-Eris and Pasta may be too novel. Another worth direction is the ZKProof organisation, but does not seem to have any standardisation process active. But nothing so far.

Action items

• Pluto-Eris:
  • OK if it satisfies security requirements?
  • Normal algorithms will be more expensive
• Pasta:
  • Verification time (not succinct)
  • Aggregation is not very clear

Next day (24 - 01)

The problem of using IPA, is that a full node of midnight might not be able to verify all transactions. There must be a lot of weight in blacklisting, etc, so that batch transactions actually verify (otherwise DoS sending incorrect proofs). Another problem, IPA proofs will dominate the throughput of the blocks (which dictates how many txs we can process).

IPA proofs with 2^16 constraints, we are around 90ms (for verification), and 1,5KB per proof. This means that without aggregation, we are at 3 TPS. We would need to have a good understanding of how IPA reacts with aggregation.

we are aggregating 10 base circuits, where highest is 2^20. If we aggregate these proofs, let t be the verification time for 2^20 circuit. The full verification of the aggregate proof is

the same as t, with a sublinear component.

and the size

Asymptotically, it is the same as the size of the larger proof.

The above two points are attractive, as we don't have to store everything on-chain, but then we run into the problem of the data availability. This, however, does not seem to be highly problematic for midnight.

Carlo's concerns:

• If we go with IPA as default method, if zkVM (or other roll-up solutions), then verification would be too expensive (apparently we are talking about ~2^25 constraints for zkVM solutions)
• However, we could do tricks as the midnight aggregation for these L2. So the question is whether there exists a way to do a zkVM that works well with IPA.

If we go with this, who does the aggregation

Yes, it is pretty cheap. Just random linear combinations of a couple of things. As the O(n) operation is a field operation (aka, cheap operation).

The main bottleneck is block producers will have to verify each individual proof nonetheless

So we still need blacklisting.

Why not use KZG 10 and simply proof all txs of a block in a single proof.

Reason for going with IPA, is because we can aggregate each block proof, which is later used to prove correctness of the state to main-net. The other one is that users need to create the proofs themselves for privacy (i.e. it cannot be generated by a single entity).

e.g. if you have two proofs, one that says that the balance is higher than, and another proof that says that I own the sk of the balance. In order to aggregate these together, we need to provide these type of linking, and apparetnly this was a big mess for zkEVM.

In some cases, spliting works more naturally, but we cannot expect this to work always.

Is it feasible to have two proving systems in Midnight? One for the state of the chain, another for the individual txs.

Would be feasible, but does not seem to make sense, as there should be an explicit distinction between both things. And at the end of the day, the users are interested in state proofs, not individual proofs.

Summary of the first half

• Pluto-Eris seems to be a risky road
• Pasta (+ IPA) has a lot of upsides
• Two contending: Pasta (+ IPA) and BLS12 (+ KZG)
  • In favour of IPA we can have efficient aggregation, recursion. The cost could be breaking up the circuit. Still unclear how much of a challenge this aggregation could be from an engineering perspective.
  • KZG problem is that each individual tx/proof will have its own cost, and aggregating all proofs into a single block, or even into a single state transition, would be much harder.

Second half

KZG proof of an IPA would be around 5h30. GPU proving could help us. The limiting factors for proving times are FFTs (60%), and the multi-scalar multiplication. Alberto unhappy with this times. But of course, we cannot have it all. There is no 'winner takes it all'.

1 block 20 seconds.

Cycle is necessary for the accumulation strategy. But if we use Pallas or Vesta for the underlying algorithms (for which we are making proofs), then the proof will be simple.

From the transaction semantics, we probably want all the user proofs to use the same curve (either pallas or vesta).

RBTP

Midnight is a compliance layer, not just privacy. So there must be some notion of identity -> We might rely in Atala. One of the strategies of atala is to be standards compliant, and they are using ECDSA over secp256k1. However, for the privacy preserving extension, they will probably rely on BLS12-381.

When verifying Atala credentials could work with the tricks of aggregation as before. One has the proof of some statement on credentials, and it aggregates it with whatever other statement it is proving. However, these proofs of the statement happen in the BLS12-381 curve.

What exactly would we need in midnight about these credentials?

For example, rate limiting nullifier (RLN). This prevents users to perform DoS attacks by floding the network with messages. You have to create a ZKP proving that you have not surpassed the number of messages you have 'assigned'.

Other examples are Tax compliance, privatised DAO. e.g. this is my ID, connected to a certificate authority, and use that as a credential to make the next payment following certain compliance rules.

How does it look on the side of the project.

Simulating arithmetic of other curves is a useful tool. And emulating BLS is tough, but emulating secp is perfectly doable. So this extension of Atala credentials would use some traditional crypto (ElGamal, Schnorr, etc)

There is another structure of curves
There are cycles of curves which are "a pairing friendly curve, which has a pairing friendly curve embedded, which has another curve embedded". BLS12-377.

Conclusion

Final argument seems to be:

• Clearly IPA for midnight (or so)
• Can we use a final pairing-based proof for the bridge?
  • This can be incentivised
  • We should analyse how much this would cost in AWS
  • There is a lot of things that can be done towards optimisation for the prover
  • E.g. polygon can prove an entire ethereum proof within 1 minute (using GPU, etc)
  • Of course, we'll need to hire people that are proficient on GPU optimisation

Next day (27-01)

Concern that we may hit the theoretical limits of batching IPA in KZG. Having a setup to allow circuits of 2^32 is just nuts. And if we get down this numbers to be feasible on the setup, but then we get circuits which are too small for IPA.

Setup of 2^32 would be needed for IPA circuits of 2^20, which are reasonable enough.

Another option is the FRI path. But proving correctness will also be very complet. However, not a lot of circuits done with plonky2 (only thing that is available right now in the space), decently big knowledge gap that will have to be closed by research.

problem of polygon's solution. Their solution is not all MIT. Quite ZKEVM focused. Jordi codes in W/ASM, so auditing is a nightmare. They have a team (of ~3) that are excluseively dedicated to optimisation.

Concern of verifier efficiency of transactions for FRI.
FRI has also good recursive properties, in that you end up 'paying' the most expensive one. However, the verifier is more expensive both in terms of size and computation.
There seems to be an inflection point between IPA and FRI. Which could be interesting when working with very complex circuits. We could switch from a IPA to FRI, and then verify it on main-net. The FRI proof will be smaller.

One thought of IPA, seems there could be engineering effort to split up an IPA proof into smaller chunks, and only pay the cost of the biggest of these chunks.
You can do this up to a limit. You do it by making statements of the proof, but you cannot go lower than the circuit that proves the statements of other proofs.

What about splitting up MSM. If we split it in 8 parts, we could create 8 smaller proofs. And then batch them.

Seems unfeasible to verify on main-net with 50ms if its not with KZG or Groth16.

The proofs that benefit a lot from hardware, are those that have FFTs, as that is extremely paralelisable.

However, Pippenger's, if we have a lot of memory, you can compute a higher precomputed table. Any ideas of where we can get any numbers?

We have options,

• To convince Cardano to have an IPA verifier. They have other use cases, like Hydra, and we can make a case to use IPA in the node.
• We could reconsider what are the security assumptions we want in the bridge.
• Pluto-Eris -> Downsides are obvious to everyone. Not feasible to do it right now, but might be out there in a year.