Orbiter Finance ZK Tech exploration grant
Orbiter Bridge Protocal is a platform that aims at decentralization while ensuring that the Gas cost of users in the cross-chain process is relatively low. On the path to decentralization, Orbiter Bridge Protocal, ZKP needs to be used to reduce the Gas fee in the evil arbitration process. The arbitration process for the Maker will reach a fully open state after the decentralized Orbiter bridge is officially launched.
The Orbiter Bridge Technical Yellow Book is available for more information on how the Orbiter Bridge works in a decentralized way.
Proof time speedup for ZKP
In the cross-roll up bridge arbitration scenario, the arbiter role needs to submit the corresponding Transaction validity proof within the specified time limit.
The reason for the slow proof of ZKP generation
Zero-knowledge proofs (ZKP) are an important part of various blockchain scaling and privacy solutions, including ZK summarization such as StarkNet, private ZK summarization such as Aztec, and layer 1 chains such as Mina, Filecoin, and Aleo. In the process of ZKP generation, there are many and exorbitant mathematical operations, so the generation time is slow and expensive.
Proving a computation requires first converting it from a classical program into a ZK-friendly format. This can be done either by manually rewriting the code or by using a domain-specific language such as Cairo or Circom to compile to the primitives needed to generate the proof. More expensive and complex operations result in longer proof generation times It is also common that certain operations do not fit into ZK, such as the bitwise operations used in SHA or Keccak, resulting in long proof generation times for what might be cheap operations on classical computers.
The proof generation process may vary depending on the proof system, but the bottleneck are:
- Multiplication of large number vectors (field or group elements), in particular variable and fixed cardinality multiscalar multiplication (MSM)
- 2）Fast Fourier Transform (FFT) and inverse FFT (although there are some techniques for FFT-free proof systems)
Proportion of MSM and NTT in the process of generating proofs
In systems with both FFT and MSM, about 70% of the time for generating proofs is spent in MSM, and the rest is dominated by FFT. The specific time allocation may vary from circuit to circuit, with some circuits exhibiting a particularly high proportion of time allocated to evaluation.
Now that we know the drawbacks, how do we optimize them?
The algorithms such as Multi-scalar Multiplication (MSM) and Number theoretic Transformation (NTT) in Halo2 algorithm are time-consuming and involve large-scale parallel computing. At the same time, GPU is good at parallel computing, so we can use GPU for acceleration scheme. From a technical point of view, GPU provides perfect development tools, including programming languages such as CUDA, which help to shorten the development cycle. From a commercialization perspective, Gpus are easily accessible, have a strong supply chain, and a mature ecosystem. Therefore, utilizing GPU acceleration is seen as an ideal direction for ZKP acceleration.
The GPU framework contains an internal GPU manager module that contains Rust code for MSM, NTT, and other modules. The main responsibility of this module is to provide an external interface (FFI), while internally being able to call CUDA code and perform certain management operations. Modules are connected to CUDA code via GPU FFI. In the context of the Halo2 algorithm, the most fundamental computations involve finite field computations, and modules such as MSM, NTT, and evaluation are directions for algorithm optimization built on top of these finite field computations.
This Grant will cooperate with the SuperScalar team to perform deeper hardware acceleration optimization for the Halo2 framework.
About SuperScalar
SuperScalar is a leading computation acceleration company that provides a wide range of Zero-knowledge proof (ZKP) acceleration products, including GPU, FPGA, and ASIC solutions. The company has already launched ZKP FPGA miners (K10 & K11) and zkEVM GPU acceleration solutions in ZK-rollup projects like Taiko. Additionally, it strives to innovate and provide its partners with even more efficient acceleration solutions. Follow @SuperScalar_io for more information.
