Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs
The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-06-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/10972 |
| _version_ | 1797807353390694400 |
|---|---|
| author | Gautam Botrel Youssef El Housni |
| author_facet | Gautam Botrel Youssef El Housni |
| author_sort | Gautam Botrel |
| collection | DOAJ |
| description |
The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. We prove that this is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Our contribution is twofold: first, we optimize the arithmetic of finite fields by improving on the well-known Coarsely Integrated Operand Scanning (CIOS) modular multiplication. This is a contribution of independent interest that applies to many different contexts. Second, we propose a new coordinate system for twisted Edwards curves tailored for the Pippenger MSM algorithm.
Accelerating the MSM over these curves is critical for deployment of recursive proof< systems applications such as proof-carrying-data, blockchain rollups and blockchain light clients. We implement our work in Go and benchmark it on two different CPU architectures (x86 and arm64). We show that our implementation achieves a 40-47% speedup over the state-of-the-art implementation (which was implemented in Rust). This MSM implementation won the first place in the ZPrize competition in the open division “Accelerating MSM on Mobile” and will be deployed in two real-world applications: Linea zkEVM by ConsenSys and probably Celo network.
|
| first_indexed | 2024-03-13T06:21:18Z |
| format | Article |
| id | doaj.art-05dc327ef8174357a96866ad7ab2d6fb |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-03-13T06:21:18Z |
| publishDate | 2023-06-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-05dc327ef8174357a96866ad7ab2d6fb2023-06-09T15:49:36ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252023-06-012023310.46586/tches.v2023.i3.504-521Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKsGautam Botrel0Youssef El Housni1Linea, Fort Worth (Texas), USALinea, Fort Worth (Texas), USA The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. We prove that this is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Our contribution is twofold: first, we optimize the arithmetic of finite fields by improving on the well-known Coarsely Integrated Operand Scanning (CIOS) modular multiplication. This is a contribution of independent interest that applies to many different contexts. Second, we propose a new coordinate system for twisted Edwards curves tailored for the Pippenger MSM algorithm. Accelerating the MSM over these curves is critical for deployment of recursive proof< systems applications such as proof-carrying-data, blockchain rollups and blockchain light clients. We implement our work in Go and benchmark it on two different CPU architectures (x86 and arm64). We show that our implementation achieves a 40-47% speedup over the state-of-the-art implementation (which was implemented in Rust). This MSM implementation won the first place in the ZPrize competition in the open division “Accelerating MSM on Mobile” and will be deployed in two real-world applications: Linea zkEVM by ConsenSys and probably Celo network. https://tches.iacr.org/index.php/TCHES/article/view/10972elliptic curvesmulti-scalar-multiplicationimplementationzero-knowledge proof |
| spellingShingle | Gautam Botrel Youssef El Housni Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs Transactions on Cryptographic Hardware and Embedded Systems elliptic curves multi-scalar-multiplication implementation zero-knowledge proof |
| title | Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs |
| title_full | Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs |
| title_fullStr | Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs |
| title_full_unstemmed | Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs |
| title_short | Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs |
| title_sort | faster montgomery multiplication and multi scalar multiplication for snarks |
| topic | elliptic curves multi-scalar-multiplication implementation zero-knowledge proof |
| url | https://tches.iacr.org/index.php/TCHES/article/view/10972 |
| work_keys_str_mv | AT gautambotrel fastermontgomerymultiplicationandmultiscalarmultiplicationforsnarks AT youssefelhousni fastermontgomerymultiplicationandmultiscalarmultiplicationforsnarks |