Skip to content

1Aviator1/ZKSYNC1

Repository files navigation

GPU Groth16 prover (3x faster than CPU)

This is a GPU Groth16 prover that won the 2x speedup prize. It follows the template from the reference.

This prover requires a substantial amount of RAM to use. The reference machine has 32GB.

This prover has a slow preprocessing step! Note the changed instructions below.

Dependencies

The code should compile and run on Ubuntu 18.04 with the following dependencies installed:

sudo apt-get install -y build-essential \
    cmake \
    git \
    libomp-dev \
    libgmp3-dev \
    libprocps-dev \
    python-markdown \
    libboost-all-dev \
    libssl-dev \
    pkg-config \
    nvidia-cuda-toolkit

Building on MacOS is not recommended as CUDA support is harder to use. (Apple mostly ships with AMD.)

Build

./build.sh

Generate parameters and inputs

./generate_parameters
./main MNT4753 preprocess MNT4753-parameters # IMPORTANT PREPROCESSING STEPS
./main MNT6753 preprocess MNT6753-parameters

The preprocessed filenames are currently hardcoded to MNT4753_preprocessed and MNT6753_preprocessed.

Run

./main MNT4753 compute MNT4753-parameters MNT4753-input MNT4753-output
./main MNT6753 compute MNT6753-parameters MNT6753-input MNT6753-output
./cuda_prover_piecewise MNT4753 compute MNT4753-parameters MNT4753-input MNT4753-output_cuda
./cuda_prover_piecewise MNT6753 compute MNT6753-parameters MNT6753-input MNT6753-output_cuda

Check results

sha256sum MNT4753-output MNT6753-output MNT4753-output_cuda MNT6753-output_cuda

How to make this faster

There are 3 components to this SNARK prover which can be optimized.

The multiexponentiations are still the bottleneck and optimization efforts should probably be focused there right now.

G1 multiexponentiation

  • The current best implementation performs a "map-reduce" to implement the multiexponentiation with a batched double-and-add being the base multiexponentiation "map" function. The Pippenger algorithm (described here and implemented for another curve here is likely to be significantly faster.

G2 multiexponentiation

  • The above remarks about the Pippenger algorithm also apply here. To repeat, the current best implementation performs a "map-reduce" to implement the multiexponentiation with a batched double-and-add being the base multiexponentiation "map" function. The Pippenger algorithm (described here and implemented for another curve here is likely to be significantly faster.

  • The technique in this paper can be used to speed up the G2 multi-exponentiation by about 2x.

FFT

This implementation did not implement the fast-fourier-transform for the GPU and used the existing C++ CPU implementation. It may be possible to get additional speedups by implementing the FFT on the GPU, although the current-best implementation performs the FFT on the CPU while the GPU is busy working, so it may not be blocking anything at the moment.

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published