Paper 2022/1162

Pairings in Rank-1 Constraint Systems

Youssef El Housni, École Polytechnique, ConsenSyS R&D
Abstract

Bilinear pairings have been used in different cryptographic applications and demonstrated to be a key building block for a plethora of constructions. In particular, some Succinct Non-interactive ARguments of Knowledge (SNARKs) have very short proofs and very fast verifi- cation thanks to a multi-pairing computation. This succinctness makes pairing-based SNARKs suitable for proof recursion, that is proofs veri- fying other proofs. In this scenario one requires to express efficiently a multi-pairing computation as a SNARK arithmetic circuit. Other com- pelling applications such as verifying Boneh–Lynn–Shacham (BLS) sig- natures or Kate–Zaverucha–Goldberg (KZG) polynomial commitment opening in a SNARK fall into the same requirement. The implementation of pairings is challenging but the literature has very detailed approaches on how to reach practical and optimized implementations in different contexts and for different target environments. However, to the best of our knowledge, no previous publication has addressed the question of ef- ficiently implementing a pairing as a SNARK arithmetic circuit. In this work, we consider efficiently implementing pairings in Rank-1 Constraint Systems (R1CS), a widely used model to express SNARK statements. We implement our techniques in the gnark open-source ecosystem and show that the arithmetic circuit depth can be almost halved compared to the previously best known pairing implementation on a Barreto–Lynn–Scott (BLS) curve of embedding degree 12, resulting in a significantly faster proving time. We also investigate and implement the case of BLS curves of embedding degree 24.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
SNARK R1CS Pairing Elliptic Curve
Contact author(s)
youssef elhousni @ consensys net
History
2022-09-06: approved
2022-09-06: received
See all versions
Short URL
https://ia.cr/2022/1162
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1162,
      author = {Youssef El Housni},
      title = {Pairings in Rank-1 Constraint Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1162},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1162}},
      url = {https://eprint.iacr.org/2022/1162}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.