# Non-native field ECC performance

This document summarises performance numbers for non-native operations, in particular relevant to credential verification, when emulated within Pasta curve used in Plonk/Halo.

## Signature requirements

1. Ed25519
- EdDSA on Curve25519 w/ SHA2-512, [reference](https://cryptobook.nakov.com/digital-signatures/eddsa-and-ed25519).
- Verification: 2 scalar multiplications + hash + 1 addition + comparison.
- Signing: 2 scalar multiplications + 3 hashes + few field add/mult mod q
2. ECDSA
- On Secp256k1, [reference](https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages).
- Verification: 2 scalar multiplications + 1 hash + 3 field muls.
3. BBS+
- Will be used in Anoncreds instead of currently CL signatures (which are basically RSA).
- On BLS12-381 or BN256, [reference](https://github.com/mattrglobal/bbs-signatures/).
- Verification: 1 scalar multiplication + 1 pairing (I think one can do 1 instead of 2)

Therefore we target Curve25519, secp256k1, BN256, and BLS12-381.
- General curves summary: https://hackmd.io/@davidnevadoc/ByCnkTSOi
- Pasta: https://github.com/zcash/pasta

## Circuit sizes

The table compares performance for `halo2wrong` (implementing Pasta,BN,Secp) and `halo2ecc-s` (implementing BLS embeddin)g libraries, in thousand of Halo2 constraints.

| Type | Mult | MSM 2 | MSM 4 | MSM 8 | MSM 16 | Pairing | Table |
| -------------------- | ---- | ----- | ----- | ----- | ------ | ------- | ----- |
| On Pallas: BN256 | 71 | 52 | 38 | 32 | 30 | | 197 |
| On Pallas: Secp256k1 | 69 | 51 | 38 | 32 | 29 | | 164 |
| On Pallas: Vesta | 71 | 52 | 38 | 32 | 29 | | 197 |
| On BN256: BLS12-381 | | 132 | 127 | 84 | 67 | 3115 | 786 |

MSM N means "gates per multiplication for MSM batch size N". "Table" is a lookup table. For source see: https://github.com/volhovm/halo2wrong/tree/master/dev

NB: Curve25519 is not yet estimated, since there is no straightforward way to, but since it also 256 bit, the numbers should be similar to the Secp256k1/BN256.

## Real performance

We will be targeting BN256 inside Pasta, using halo2wrong library, in halo2 with IPA. Embedding other curves of the same size has a similar overhead; for BLS381 scale by ~1.5.

### Circuit
The circuit will be dominated by two scalar multiplications, which is a realistic assumption on how much we need to verify an Ed/ECDSA signature. This in the wrong field take about 140k constraints if we use 2 separate multiplications, and about 105k if we use 2-MSM. In both cases we need to use k = 18 (circuit height), and the whole circuit size is thus 2^k = 262k rows. The 190k lookup table also fits there too -- it is occupying a different column, so it does not increase the number of rows.

### Hardware
I used a "standard" university desktop with i5-8500, 6 cores, 3 GHz. However, my setup only provides 16GB of memory, which is most likely a bottleneck for proof generation, since swap (in my case slow HDD) is used.

### Estimate & Justification

| | Proving time | Verification time |
| ----------- | ------------ | ----------------- |
| Single core | 21 min | 24 sec |
| 4 cores | 6 min | 6.6 sec |

According to the estimations [here](https://blog.celer.network/2023/03/01/the-pantheon-of-zero-knowledge-proof-development-frameworks/) these numbers are somewhat reasonable. The blog post claims 4M (k=22) circuit in halo2 (with KZG though), executed on 12 cores (IIRC) takes about 7.5min to build, and takes about 35-40GB of RAM. This translates to about 5.6 minutes of proving time for a circuit of our size (k=18) assuming everything scales linearly. However my setup has only 16GB of RAM, so HDD swap is slowing proving time down even further, and also IPA proving time is higher than KZG (IIRC).

### Potential optimisations

I think the circuit size could be (maybe) squeezed by 20-30% by using the optimisation that David was working on.

## Temporary Summary

Ed25519 and ECDSA must be doable with halo2/IPA, within several seconds of proving time, however these are expensive one-time computations. On a very basic single core software (worst case) we'd get 10-20 minutes proving time to prove-your-signature. On a reasonably good server software we'd get few seconds verification time.

BBS+ with its pairings -- much more heavy, not sure if within realms of possible at least with IPA, but probably doable with non-IPA variant of halo2.