[Soroban] Support cryptographic primitives for proof verification

[jayz22]

Cross-posting notes from @kwantam at the early stage of Soroban (around 06/2022). This is to be used as reference and starting point of discussions around adding new crypto primitives in Soroban.

This document lists cryptographic primitives and related algorithms for
proof verification and related protocols.

# Hash functions

In addition to the standard primitives (SHA2, SHA3, Blake), it *may* be
worthwhile to support circuit-friendly hash functions like
[Poseidon](https://www.poseidon-hash.info)
or
[Reinforced Concrete](https://eprint.iacr.org/2021/1038.pdf).

That said, as long as efficient field arithmetic and basic data structures
(e.g., 2d arrays) are available and have good performance, circuit-friendly
hash functions can probably be implemented in terms of those primitives.
This is worth testing before making a decision.

# Field arithmetic

Arithmetic over all of the fields associated with the elliptic curves
below (base field, scalar field) is worthwhile to support. Generic modular
arithmetic support might suffice if it has good performance.

Pairing-friendly elliptic curves sometimes require arithmetic over extension
fields, too. This can be implemented via prime field arithmetic, but it might
be worthwhile to give users access to routines tailored to the extension
fields used by supported elliptic curves (benchmark before deciding).

## useful algorithms for field elements

If all computations are over public, on-chain data, none of these algorithms
need to be constant time. This may save cost, but it's also worth considering
how likely these primitives are to be (mis)used in a secret context.

- exponentiation - in principle could include optimizations for fixed bases
  or fixed exponents, but that might be overkill.

- multi-exponentiation via Pippenger's algorithm

- fast inversion via Euclidean division. Might also consider batch
  inversion via Montgomery's trick, but a built-in may not be needed
  (benchmark before deciding).

- conversion of byte sequences (interpreted as integers) into field elements

- modular square root via Tonelli-Shanks

# Elliptic curve primitives

## pairing-friendly elliptic curves

- BN254 aka BN256 aka alt-bn128 aka the curve that cannot be (reliably) named.

  This curve is currently supported by Ethereum and is in widespread use. A
  2016 paper by Kim and Barbulescu showed that its security was lower than
  previously thought (estimates range from 100 to 112 bits, target was 128).

  Possible implementations:

  - [go-ethereum](https://github.com/ethereum/go-ethereum/tree/master/crypto/bn256)
    has two, one from Google and one from Cloudflare's CIRCL library.
  - [arkworks](https://github.com/arkworks-rs/curves/tree/master/bn254)
  - [gnark](https://github.com/ConsenSys/gnark-crypto/tree/master/ecc/bn254)

- BLS12-381

  This is the curve that is slated to replace BN254, eventually. EIP-2537 has
  been waiting in the wings for years. Maybe it'll land someday.

  Possible implementations:

  - [blst](https://github.com/supranational/blst/)
  - [arkworks](https://github.com/arkworks-rs/curves/tree/master/bls12_381)
  - [gnark](https://github.com/ConsenSys/gnark-crypto/tree/master/ecc/bls12-381)

- BLS12-377 (maybe)

  This curve was designed for recursive proofs ("proofs of proofs"). It is used by
  [Aleo](https://developer.aleo.org/autogen/advanced/the_aleo_curves/bls12-377/).

  Possible implementations:

  - [arkworks](https://github.com/arkworks-rs/curves/tree/master/bls12_377)
  - [gnark](https://github.com/ConsenSys/gnark-crypto/tree/master/ecc/bls12-377)

- BW6-761 (if supporting BLS12-377)

  This curve is used with BLS12-377 to generate depth-1 recursive proofs. It
  is used by Aleo.

  Possible implementations:

  - [arkworks](https://github.com/arkworks-rs/curves/tree/master/bw6_761)
  - [gnark](https://github.com/ConsenSys/gnark-crypto/tree/master/ecc/bw6-761)

## non--pairing-friendly elliptic curves

- curve25519 / edwards25519

  General-purpose curve used for key exchange and EdDSA signatures.

- secp256k1

  Curve used by Bitcoin and many others for digital signatures.

- Baby Jubjub

  This curve's base field matches the scalar field of BN254, which means
  that proofs over the BN254 curve can efficiently embed (say) verification
  of signatures over Baby Jubjub. This is a common pattern, e.g., in rollups.

  Possible implementations:

  - [arkworks](https://github.com/arkworks-rs/curves/tree/master/ed_on_bn254)

- Jubjub

  This curve's base field matches the scalar field of BLS12-381. This curve
  is used in Zcash Sapling for efficient proof of knowledge of signatures.

  Possible implementations:

  - [zkcrypto](https://github.com/zkcrypto/jubjub)
  - [arkworks](https://github.com/arkworks-rs/curves/tree/master/ed_on_bls12_381)

- Edwards curve on BLS12-377 (if supporting BLS12-377)

  This curve is to BLS12-377 as Jubjub is to BLS12-381.

  Possible implementations:

  - [arkworks](https://github.com/arkworks-rs/curves/tree/master/ed_on_bls12_377)

- Edwards curve on BW6-761 (if supporting BW6-761)

  This curve is to BW6-761 as Jubjub is to BLS12-381.

  Possible implementations:

  - [arkworks](https://github.com/arkworks-rs/curves/tree/master/ed_on_bw6_761)

- Pallas and Vesta, aka the "pasta" curves

  This is a non--pairing-friendly elliptic curve cycle (i.e., the base
  field of each matches the scalar field of the other). These are used
  to build certain recursive proofs (e.g., Halo2, NOVA).

  Possible implementations:

  - arkworks: [pallas](https://github.com/arkworks-rs/curves/tree/master/pallas) and [vesta](https://github.com/arkworks-rs/curves/tree/master/vesta)
  - [zcash](https://github.com/zcash/pasta_curves)

## useful algorithms for elliptic curves

- scalar multiplication and multi-multiplication via Pippenger's algorithm

- conversion of pairs or triplets of field elements into elliptic curve
  points, and conversion from curve point to pair of field elements.

- hash to curve - takes an arbitrary string and outputs a point on the
  curve. It might suffice to provide "map to curve", i.e., mapping from
  base field to curve point, and let users handle hashing arbitrary string
  to field element.

- fast point validation, i.e., checking that a point is both on the curve
  and in the prime-order subgroup. There's some question here of who ought
  to be responsible for enforcing that points are valid and in the correct
  subgroup. It's sometimes handy to be able to construct points that are
  not in the correct subgroup and then "fix" them---notably, for hashing
  to curve---but maybe it makes sense to enforce validity by default. Then
  again, the validity check is not free!

(@kwantam if you have an updated opinion based on recent developments in the field, feel free to post your comments below)

[jayz22]

There has been substantial discussion (and a prototype implementation!) around adding BLS12-381 stellar/rs-soroban-env#779.
I would like to take a step back and verify if this is the right curve choice and examine some of the alternatives.

BLS12-381 is the de-facto standard pairing-friendly curve of choice, adopted by Ethereum. It is designed to replace BN254 (due to its lower security, as mentioned in notes).

The most frequent mention as an alternative is BLS12-377. It has many similar characteristics to BLS12-381 (same embedding degree, similar subgroup order and prime field size etc) and similar performance (see this reference for benchmark between various curves and libraries).
The main benefit is that it forms a 2-curve cycle with BW6-761, which enables efficient verification of recurve proofs. So if we support BLS12-377, ideally we also want to also add BW6-761.

However, the same developer of BW6-761 has proposed a similar curve BW6-767 that can be cycled with BLS12-381 for the same benefits. This makes me wonder if BLS12-377's main advantage is still relevant at all.

There are other curves such as MNT4 and MNT6, Pallas and Vesta (see ref1 and ref2) that has been adopted by various protocols. I don't understand the cryptographic details beyond the fact that they also enable efficient recursive proof verification.

So my conclusion is we have to support BLS12-381 (for the simple reason of interoperability, besides the curve's own strengths).
However my questions are, how serious should we consider supporting theses other curves:

• how important are recursive proofs, i.e. is it needed for most applications building zk-snarks?
• if so, do we have to support two-cycle curves (BW6-761 with BLS12-377, BW6-767 with BLS12-381)?
• besides pairing friendly curves (and operations on them), which other primitives are considered necessary to build a fully functional proof verification-capable platform in Soroban.

would love to hear opinions from cryptography experts and ecosystem builders such as @kwantam, @rsinha, @PlamenHristov @heytdep

[tomerweller]

Positive signal for BLS12-381 wider ecosystem support: It was just added to CosmWasm.

CosmWasm/cosmwasm#2106

[rsinha]

Lot of great points already, but here are my 2¢. In general, supporting recursive proofs (and their curve cycles) is useful as the most recent SNARK constructions rely on them for efficiency. These may either be a 2-cycle of pairing friendly curves (e.g. BLS and MNT), or non-pairing (e.g. pallas and vesta) -- in either case, it is sufficient for Soroban to only support one curve, say BLS, as the off-chain prover application is responsible working with both curves. Within BLS, we have the option for 12-377 and 12-381, and it appears that wider ecosystem support may push the case for BLS 12-381.

That said, it is worth considering the brief history of SNARKs (I am only mentioning a few works here for brevity).

• Groth16 (2016), and later Plonk (2019), work with KZG polynomial commitments over any pairing-friendly curve.
• The next improvement came from folding schemes such as Nova (2021) and their followups, which work with pasta curves that do not require pairing.
• Concurrently, there is a line of work building on FRI commitments that only rely on hashing. This includes STARKs, and recent RiscV zkVMs such as risc0 and succint. They are typically used with a Groth16 recursion at the end to reduce gas cost.

Today, there is no one-size-fits-all or one winning SNARK amonst these options. An app developer will explore different tradeoffs amongst these options. Moreover, we can expect further improvements, both in SNARK constructions and newer curves, over the next few years. Considering this in mind, and also crypto agility (for addressing new attacks on curves), it might be worth also having a plan for supporting additional families of curves, with a common host function interface. The arkworks library is a great example of this, as the application developer can switch curves by changing a single line defining the import.

[heytdep]

Sorry to chime in late here, I agree with @rsinha. I think we could also directly rely on Arkwork's implementation directly on the host. We cannot directly have guest <> host calls with a generic pairing engine impl such as arkwork does of course, but we can either use the supported curves as a host fn argument to keep the host interface as generic as possible. But yeah, I don't think we can actually have the guest specify a curve without some kind of specific implementation/adapter for the curve on the host.

[jayz22]

Thank you @rsinha and @heytdep for both your feedback.
Yes I agree this is a deep and fast evolving field (I don't want to pretend to understand most of it) and we need be able to adapt and support new curves/proof schemes/protocols easily.
The arkworks provides a whole ecosystem. The abstractions built around the curve and field arithmetics is also quite good, making it much easier to add a new curve. I have incorporated it into my initial prototype (env and sdk, which is built on top of what @PlamenHristov started).
For the host interface though, I think we should still stick to the proposed (the eth-precompile-like naming convention), since the host functions are low-level, and we can always build more abstractions at the sdk level.