Tokamak zk-EVM 2023 Q1 Report
Visualization and documentation of project ideas
Greetings. This is Jake, the leader of the Tokamak zk-EVM project. We share the 1st quarter progress of the Tokamak zk-EVM project.
- About the Tokamak zk-EVM project
- This project is financially supported by Ecosystem Support Program of Ethereum Foundation through Academic Grants Round 2023.
The theme of 1st quarter is Visualization and Documentation of the project ideas.
Major outcomes
- We updated the specification of our SNARK, universal Groth16 (We are consistently updating it with further discussion after this upload, but please understand that the release of the updates is being delayed).
- We wrote a project proposal (which is private, but a public version can be found here).
- We made some slides about project ideas.
- We applied an interactive command line interface to the demo implementation of universal Groth16, for improved user convenience.
- We improved the performance of the demo implementation of universal Groth16.
Some of the details
Interactive command line interface for universal Groth16
With the aim of providing an improved user experience, the commands we created need to be tweaked and adjusted to better align with the standard conventions of CLI applications to ensure that our application is as intuitive and user-friendly as possible.
To this end, we have developed an interactive Command Line Interface (CLI). This feature allows users to easily navigate through different functionalities and options in a seamless and intuitive manner. Additionally, we have included fuzzy search so that users can quickly find and access the input files by typing keywords and arrow keys. Thanks to Pleiadex.
The README also has been updated with how to use our interactive CLI, to make it accessible to users of all skill levels.
Improved performance of universal Groth16 by applying fast Fourier transform
The previous version of the implementation had a huge number of computations to generate a Zero-Knowledge proof for even a simple smart contract; generating proof for an Ethereum transfer smart contract required a staggering five hours. We found that the biggest overhead was due to polynomial multiplications and divisions, since those were computed with the convolution of polynomial coefficients that requires O(n²) field operations (The rest parts of generating proofs require O(n) group exponentiations, which is similar to that required by the original Groth16).
It is well known that the convolution can be replaced with fast Fourier transforms (FFT) to reduce the complexity from O(n²) to O(nlogn). There are many open-source libraries that perform NTT (an FFT over a finite field) dealing with 1-D vectors. As our SNARK uses bivariate polynomials rather than univariates ones, which generate 2-D matrices, we needed modifications to the open-source.
As a result, we implemented 2-d FFT(NTT) for multiplications of bivariate polynomials. Proving time was reduced from five hours to 18 minutes for the same circuit. Thanks to Pleiadex.
Contact us
We are actively seeking creative researchers and developers, please contact us at hr@tokamak.network. Also, we welcome contacting jake@tokamak.network for technical discussions.
