Computational cryptography › Live on mainnet today › Pairing curves
Hardness assumptionKE: gives key exchange

q-type / knowledge assumptions

In plain words

Assumptions behind the zero-knowledge proofs checked on Ethereum's older, cheaper curve, BN254, which gives somewhat less security than today's targets.

The idea: SNARK verifiers on BN254 check a few pairing equations that only a prover who really ran the computation should be able to satisfy. Proving that formally takes strong assumptions, including "knowledge" assumptions: anyone who outputs a valid proof must, in effect, know a valid set of inputs. And the curve itself is smaller than ideal, at about 100 bits of security.

Why it matters: Most ZK rollups and privacy apps rely on it today.

The details

On the map: on BN254

Groth16 and PLONK verifiers on BN254 rest on q-type and knowledge assumptions in idealized models: assumptions that an adversary who produces a valid proof must actually "know" a valid witness[1, 2].

BN254 security is about 100 bits after the 2016 number-field-sieve improvements[3], below the usual 128-bit target[4]. It is still used because Ethereum has had cheap precompiles for it since 2017 (KE)[5, 6].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (3 boxes)

About the tags

KE
This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.

References

  1. Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. Advances in Cryptology – EUROCRYPT 2016. doi:10.1007/978-3-662-49896-5_11
  2. Ariel Gabizon, Zachary J. Williamson and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR Cryptology ePrint Archive, Paper 2019/953. eprint.iacr.org/2019/953
  3. Taechan Kim and Razvan Barbulescu. Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case. Advances in Cryptology – CRYPTO 2016. doi:10.1007/978-3-662-53018-4_20
  4. Razvan Barbulescu and Sylvain Duquesne. Updating Key Size Estimations for Pairings. Journal of Cryptology, 2019. doi:10.1007/s00145-018-9280-5
  5. Christian Reitwiessner. EIP-196: Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128. Ethereum Improvement Proposals (Final), 2017. eips.ethereum.org/EIPS/eip-196
  6. Vitalik Buterin and Christian Reitwiessner. EIP-197: Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128. Ethereum Improvement Proposals (Final), 2017. eips.ethereum.org/EIPS/eip-197