/nova-sha256

Nova-based SHA256 benchmarks

Primary LanguageRustApache License 2.0Apache-2.0

Nova-based SHA256

Nova is a recursive SNARK that is suitable for computations with repeated structure, i.e. computations of the form $z_{i+1} = F(z_i)$. At each step, the function $F$ is allowed to have private inputs.

The SHA256 hash of a long input is computed by repeatedly applying the SHA256 compression function. At each step, the compression function consumes the previous 32-byte digest and a 64-byte block of the padded input. In the first step, a fixed initial value ($IV$) is used as the digest.

To use Nova to prove that the output of a message has a particular hash value, we can set $z_0 = IV$ and $F$ = SHA256 compression function. At each step, we provide the 64-byte message block as a private input.

Running the example

Run the following commands.

cargo build --release
cargo run -r --example sha256 6

In the above case, The input message to SHA256 will be $2^6$ zero bytes. The output will look like the following.

Nova-based SHA256 compression function iterations
=========================================================
Producing public parameters...
PublicParams::setup, took 3.607127198s 
Number of constraints per step (primary circuit): 37034
Number of constraints per step (secondary circuit): 10347
Number of variables per step (primary circuit): 37000
Number of variables per step (secondary circuit): 10329
Generating a RecursiveSNARK...
RecursiveSNARK::prove_step 0: true, took 1.047µs 
RecursiveSNARK::prove_step 1: true, took 81.249423ms 
Total time taken by RecursiveSNARK::prove_steps: 81.283345ms
Verifying a RecursiveSNARK...
RecursiveSNARK::verify: true, took 71.64086ms
Generating a CompressedSNARK using Spartan with IPA-PC...
CompressedSNARK::prove: true, took 3.971226131s
Total proving time is 4.54092927s
CompressedSNARK::len 9938 bytes
Verifying a CompressedSNARK...
CompressedSNARK::verify: true, took 141.363763ms
=========================================================
Public parameters generation time: 3.607127198s 
Total proving time (excl pp generation): 4.54092927s
Total verification time: 141.363763ms
=========================================================
Expected value of final hash = "f5a5fd42d16a20302798ef6ed309979b43003d2320d9f0e8ea9831a92759fb4b"
Actual value of final hash   = "f5a5fd42d16a20302798ef6ed309979b43003d2320d9f0e8ea9831a92759fb4b"

To change the input length to 64 KB ($2^{16}$ bytes), run the following command. The input is again all zero bytes.

cargo run -r --example sha256 16

Generating the benchmarks

Run the following commands (shell script tested only on Ubuntu).

cargo build --release --examples
./genlog_all.sh

The logs directory will have two files per input length N, for N in the set {64, 128, ..., 65536}.

  • output_N.txt has the program output.
  • time_output_N.txt has the output of the time command. This is used to measure peak memory usage.

To generate the logs for a particular length, you can run the genlog.sh script. For example, the following command will generate logs for input length 1024 bytes.

./genlog.sh 10

Existing benchmarks

The existing files in the logs directory were generated on a Dell Inspiron laptop with a 11th Gen Intel i5-11320H CPU and 16 GB of RAM. The CPU has 4 cores with 2 threads per core.

  • For all lengths
    • The peak memory usage was about 260 MB.
    • Verification time was less than 150 milliseconds.
    • Proof size was about 10,000 bytes.
    • Public parameter generation time was about 4 seconds
  • The proving time for 64KB input was around 2 minutes. Proving times for other lengths are shown below.

Proving times

$ grep "Total proving time is" $(ls logs/output_* -rt)
logs/output_65536.txt:Total proving time is 128.361272568s
logs/output_32768.txt:Total proving time is 67.385187591s
logs/output_16384.txt:Total proving time is 35.242403037s
logs/output_8192.txt:Total proving time is 19.427134991s
logs/output_4096.txt:Total proving time is 11.853209643s
logs/output_2048.txt:Total proving time is 8.10600355s
logs/output_1024.txt:Total proving time is 6.274435826s
logs/output_512.txt:Total proving time is 5.395036577s
logs/output_256.txt:Total proving time is 4.970008973s
logs/output_128.txt:Total proving time is 4.551801823s
logs/output_64.txt:Total proving time is 4.475632468s

Verification times

$ grep "CompressedSNARK::verify" $(ls logs/output_* -rt)
logs/output_65536.txt:CompressedSNARK::verify: true, took 161.669379ms
logs/output_32768.txt:CompressedSNARK::verify: true, took 154.329705ms
logs/output_16384.txt:CompressedSNARK::verify: true, took 154.323314ms
logs/output_8192.txt:CompressedSNARK::verify: true, took 150.839038ms
logs/output_4096.txt:CompressedSNARK::verify: true, took 140.438199ms
logs/output_2048.txt:CompressedSNARK::verify: true, took 135.292959ms
logs/output_1024.txt:CompressedSNARK::verify: true, took 132.714996ms
logs/output_512.txt:CompressedSNARK::verify: true, took 139.134246ms
logs/output_256.txt:CompressedSNARK::verify: true, took 135.419974ms
logs/output_128.txt:CompressedSNARK::verify: true, took 133.126469ms
logs/output_64.txt:CompressedSNARK::verify: true, took 123.653851ms

Proof sizes

$ grep "len" $(ls logs/output_* -rt)
logs/output_65536.txt:CompressedSNARK::len 9976 bytes
logs/output_32768.txt:CompressedSNARK::len 9975 bytes
logs/output_16384.txt:CompressedSNARK::len 9977 bytes
logs/output_8192.txt:CompressedSNARK::len 9971 bytes
logs/output_4096.txt:CompressedSNARK::len 9974 bytes
logs/output_2048.txt:CompressedSNARK::len 9972 bytes
logs/output_1024.txt:CompressedSNARK::len 9971 bytes
logs/output_512.txt:CompressedSNARK::len 9975 bytes
logs/output_256.txt:CompressedSNARK::len 9973 bytes
logs/output_128.txt:CompressedSNARK::len 9974 bytes
logs/output_64.txt:CompressedSNARK::len 9938 bytes

Peak memory usage

$ grep "Maximum resident set size" $(ls logs/time_output_* -rt)
logs/time_output_65536.txt:     Maximum resident set size (kbytes): 261356
logs/time_output_32768.txt:     Maximum resident set size (kbytes): 265844
logs/time_output_16384.txt:     Maximum resident set size (kbytes): 260856
logs/time_output_8192.txt:      Maximum resident set size (kbytes): 266920
logs/time_output_4096.txt:      Maximum resident set size (kbytes): 262376
logs/time_output_2048.txt:      Maximum resident set size (kbytes): 264108
logs/time_output_1024.txt:      Maximum resident set size (kbytes): 261804
logs/time_output_512.txt:       Maximum resident set size (kbytes): 263784
logs/time_output_256.txt:       Maximum resident set size (kbytes): 262496
logs/time_output_128.txt:       Maximum resident set size (kbytes): 263340
logs/time_output_64.txt:        Maximum resident set size (kbytes): 262608

Public parameter generation time

$ grep "Public parameters" $(ls logs/output_* -rt)
logs/output_65536.txt:Public parameters generation time: 3.612032586s 
logs/output_32768.txt:Public parameters generation time: 3.87279403s 
logs/output_16384.txt:Public parameters generation time: 3.920718336s 
logs/output_8192.txt:Public parameters generation time: 3.846917525s 
logs/output_4096.txt:Public parameters generation time: 3.795370968s 
logs/output_2048.txt:Public parameters generation time: 3.72987859s 
logs/output_1024.txt:Public parameters generation time: 3.679694828s 
logs/output_512.txt:Public parameters generation time: 3.720623095s 
logs/output_256.txt:Public parameters generation time: 3.717689922s 
logs/output_128.txt:Public parameters generation time: 3.662263553s 
logs/output_64.txt:Public parameters generation time: 3.597867008s

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.