search

nullity00 / circom-circuits

Bit manipulation in Circom
3 stars 0 forks source link

Best Practices for circuits #1

Open nullity00 opened 1 year ago

nullity00 commented 1 year ago

Best Practices for Large Circuits

This document summarizes the best practices for compiling and generating Groth16 proofs for large ZK circuits using the circom / snarkjs toolstack. These techniques are most applicable to circuits with at least 20M constraints.

For such large circuits, you need a machine with an Intel processor, lots of RAM and a large hard drive with swap enabled. For example, the zkPairing project used an AWS r5.8xlarge instance with 32-core 3.1GHz, 256G RAM machine with 1T hard drive and 400G swap.

Our knowledge of the following best practices is almost entirely due to the generosity and guidance of Jordi Baylina from Polygon-Hermez.

Compilation and proving

rapidsnark/build/prover [.zkey] [.wtns] proof.json public.json

Witness generation debugging

In the circuit debugging stage, it is useful to note that you do not need to go through the full setup with key generation above to extract the outputs (if any) of the proof.

After generating the witness file witness.wtns and converting it to json using snarkjs wej [witness.wtns] [witness.json], then indices 1-m of witness.json (index 0 is always equal to 1) will contain the m public outputs of the proof.

In fact, one can in theory extract all witnesses from intermediate steps of the proof from witness.json using the .sym file. We have built an experimental Python parser to do this here (the parser currently may break due to compiler optimizations, run with --O0 for safety).

Setup from scratch

Here are the steps to set up a blank slate machine/instance according to the configuration described above.

Install rust, circom, C++ dependencies, nvm, and yarn.

curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh
source $HOME/.cargo/env
git clone https://github.com/iden3/circom.git
cd circom
cargo build --release
cargo install --path circom

sudo apt install build-essential libgmp-dev libsodium-dev nasm nlohmann-json3-dev

curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.1/install.sh | bash

export NVM_DIR="$HOME/.nvm"
[ -s "$NVM_DIR/nvm.sh" ] && \. "$NVM_DIR/nvm.sh"  # This loads nvm
[ -s "$NVM_DIR/bash_completion" ] && \. "$NVM_DIR/bash_completion"  # This loads nvm bash_completion

nvm install --lts
npm install --global yarn

Remove system memory limit

Run

sysctl -w vm.max_map_count=655300

and fix it to not be reset after a reboot by adding this line

vm.max_map_count=655300

in the file /etc/sysctl.conf.

Setup swap

sudo fallocate -l 400G /swapfile
sudo chmod 600 /swapfile
sudo mkswap /swapfile
sudo swapon /swapfile

sudo sh -c 'echo "vm.max_map_count=10000000" >>/etc/sysctl.conf'
sudo sh -c 'echo 10000000 > /proc/sys/vm/max_map_count'

to make this persistent through reboots, add to /etc/fstab:

/swapfile swap swap defaults 0 0

Install patched node

We use $HOME_DIR as our home directory throughout.

cd $HOME_DIR
curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.37.2/install.sh | bash
source ~/.bashrc
nvm install v14.8.0
node --version

git clone https://github.com/nodejs/node.git
cd node
git checkout 8beef5eeb82425b13d447b50beafb04ece7f91b1
patch -p1 <<EOL
index 0097683120..d35fd6e68d 100644
--- a/deps/v8/src/api/api.cc
+++ b/deps/v8/src/api/api.cc
@@ -7986,7 +7986,7 @@ void BigInt::ToWordsArray(int* sign_bit, int* word_count,
 void Isolate::ReportExternalAllocationLimitReached() {
   i::Heap* heap = reinterpret_cast<i::Isolate*>(this)->heap();
   if (heap->gc_state() != i::Heap::NOT_IN_GC) return;
-  heap->ReportExternalMemoryPressure();
+  // heap->ReportExternalMemoryPressure();
 }

 HeapProfiler* Isolate::GetHeapProfiler() {
diff --git a/deps/v8/src/objects/backing-store.cc b/deps/v8/src/objects/backing-store.cc
index bd9f39b7d3..c7d7e58ef3 100644
--- a/deps/v8/src/objects/backing-store.cc
+++ b/deps/v8/src/objects/backing-store.cc
@@ -34,7 +34,7 @@ constexpr bool kUseGuardRegions = false;
 // address space limits needs to be smaller.
 constexpr size_t kAddressSpaceLimit = 0x8000000000L;  // 512 GiB
 #elif V8_TARGET_ARCH_64_BIT
-constexpr size_t kAddressSpaceLimit = 0x10100000000L;  // 1 TiB + 4 GiB
+constexpr size_t kAddressSpaceLimit = 0x40100000000L;  // 4 TiB + 4 GiB
 #else
 constexpr size_t kAddressSpaceLimit = 0xC0000000;  // 3 GiB
 #endif
EOL
./configure
make -j16

The patched node executable is located at NODE_PATH = $HOME_DIR/node/out/Release/node.

Install snarkjs from source

cd $HOME_DIR
git clone https://github.com/iden3/snarkjs.git
cd snarkjs
git checkout v0.3.59
npm install

The snarkjs executable is located at SNARKJS_PATH = $HOME_DIR/snarkjs/cli.js.

Install rapidsnark from source

cd $HOME_DIR
git clone git@github.com:iden3/rapidsnark.git
cd rapidsnark

npm install
git submodule init
git submodule update
npx task createFieldSources
npx task buildProver

The rapidsnark executable is located at RAPIDSNARK_PATH = $HOME_DIR/rapidsnark/build/prover.

Build scripts

One can use the following bash script to implement all the proving steps described above. (For a full implementation, see here.)

The Powers of Tau file is located at $PHASE1. Let CIRCUIT_NAME be the name of the circuit. We assume the circuit has already been compiled, with all relevant files in the current directory.

Phase 2 trusted setup

Groth16 requires a separate trusted setup for each circuit. This generates a common reference string (CRS), which is stored in a .zkey file. The following commands should be run once per circuit.

To create the .zkey without phase 2 contributions:

echo "****GENERATING ZKEY 0****"
start=`date +%s`
$NODE_PATH --trace-gc --trace-gc-ignore-scavenger --max-old-space-size=2048000 --initial-old-space-size=2048000 --no-global-gc-scheduling --no-incremental-marking --max-semi-space-size=1024 --initial-heap-size=2048000 --expose-gc $SNARKJS_PATH zkey new "$CIRCUIT_NAME".r1cs "$PHASE1" "$CIRCUIT_NAME"_0.zkey -v
end=`date +%s`
echo "DONE ($((end-start))s)"

We should contribute to the phase 2 ceremony, which requires some randomn input. (For production, one should do multiple contributions with more rigor.)

echo "****CONTRIBUTE TO PHASE 2 CEREMONY****"
start=`date +%s`
$NODE_PATH $SNARKJS_PATH zkey contribute -verbose "$CIRCUIT_NAME"_0.zkey "$CIRCUIT_NAME".zkey -n="First phase2 contribution" -e="some random text for entropy"
end=`date +%s`
echo "DONE ($((end-start))s)"

Verify final zkey:

echo "****VERIFYING FINAL ZKEY****"
start=`date +%s`
$NODE_PATH --trace-gc --trace-gc-ignore-scavenger --max-old-space-size=2048000 --initial-old-space-size=2048000 --no-global-gc-scheduling --no-incremental-marking --max-semi-space-size=1024 --initial-heap-size=2048000 --expose-gc $SNARKJS_PATH zkey verify -verbose "$CIRCUIT_NAME".r1cs "$PHASE1" "$CIRCUIT_NAME".zkey
end=`date +%s`
echo "DONE ($((end-start))s)

The verifier does not need the full zkey to verify a Groth16 proof. They only need a shorter verification key. To export the verification key:

echo "****EXPORTING VKEY****"
start=`date +%s`
$NODE_PATH $SNARKJS_PATH zkey export verificationkey "$CIRCUIT_NAME".zkey [vkey.json] -v
end=`date +%s`
echo "DONE ($((end-start))s)"

Witness and proof generation

The following commands should be run once for each input to generate witness and a proof for that input.

Done by prover:

Generate witness (C++):

cd "$CIRCUIT_NAME"_cpp 
make
./"$CIRCUIT_NAME" [input.json] [witness.wtns]

Change witness to .json:

snarkjs wej [witness.wtns] [witness.json]

Generate proof:

echo "****GENERATING PROOF FOR SAMPLE INPUT****"
start=`date +%s`
$RAPIDSNARK_PATH "$CIRCUIT_NAME".zkey [witness.wtns] [proof.json] [public.json]
end=`date +%s`
echo "DONE ($((end-start))s)"

Done by verifier:

To verify the proof, run:

echo "****VERIFYING PROOF FOR SAMPLE INPUT****"
start=`date +%s`
$NODE_PATH $SNARKJS_PATH groth16 verify [vkey.json] [public.json] [proof.json] -v
end=`date +%s`
echo "DONE ($((end-start))s)"
nullity00 commented 1 year ago

https://hackmd.io/V-7Aal05Tiy-ozmzTGBYPA?view