leanVM

Minimal hash-based zkVM, for a Post-Quantum Ethereum.

Warning: not (yet) production ready.

leanVM was originally designed over the KoalaBear prime and Poseidon, still available in the koalabear branch; it is now using binary fields and BLAKE2s.

Benchmarks

Machine: Mac M4 Max

XMSS aggregation

The XMSS parameters are specified in XMSS.pdf.

cargo run --release -- aggregate --xmss 900 --log-inv-rate 1 --repeat 3

aggregation, 900 XMSS signatures
  cycles (VM steps)           : 1,571,100 = 2^20.583
    details                   : DEREF 2^18.978 (32.9%)  SET 2^18.525 (24.0%)  MUL 2^18.199 (19.2%)  BLAKE2S 2^16.989 (8.3%)  XOR 2^16.979 (8.2%)  JUMP 2^16.839 (7.5%)  MEMORY 2^21.304  TOTAL_COMMITTED 2^26.195
  proof size                  : 294.9 KiB
  proving time                : 0.765 s ± 6.9%      peak memory 8.812 GiB
  per signature               : 1,177.218 signatures/s
  verifying                   : 0.00416 s

SPHINCS aggregation

The SPHINCS parameters are specified in SPHINCS.pdf.

cargo run --release -- aggregate --sphincs 245 --log-inv-rate 1 --repeat 3

aggregation, 245 SPHINCS signatures
  cycles (VM steps)           : 2,629,937 = 2^21.327
    details                   : DEREF 2^19.438 (27.0%)  XOR 2^19.239 (23.5%)  MUL 2^19.215 (23.1%)  SET 2^18.833 (17.8%)  BLAKE2S 2^16.992 (5.0%)  JUMP 2^16.543 (3.6%)  MEMORY 2^21.794  TOTAL_COMMITTED 2^26.664
  proof size                  : 320.1 KiB
  proving time                : 1.007 s ± 3.7%      peak memory 12.507 GiB
  per signature               : 243.224 signatures/s
  verifying                   : 0.00426 s

Recursion

cargo run --release -- recursion --n 2 --xmss-per-leaf 900 --log-inv-rate 2 --repeat 3

recursion 2→1, over leaves of 900 XMSS signatures
  cycles (VM steps)           : 585,312 = 2^19.159
    details                   : MUL 2^17.652 (35.2%)  DEREF 2^17.328 (28.1%)  XOR 2^16.827 (19.9%)  SET 2^15.739 (9.3%)  JUMP 2^14.761 (4.7%)  BLAKE2S 2^13.978 (2.8%)  MEMORY 2^19.533  TOTAL_COMMITTED 2^24.237 TOTAL_COMMITTED 2^24.237
  proof size                  : 195.0 KiB
  proving time                : 0.295 s ± 2.3%      peak memory 10.129 GiB
  verifying                   : 0.0042 s

Data Availability

cargo run --release -- aggregate --blobs 16 --log-inv-rate 1 --repeat 3

aggregation, 16 blobs
  cycles (VM steps)           : 2,974,203 = 2^21.504
    details                   : MUL 2^19.84 (31.6%)  XOR 2^19.809 (30.9%)  DEREF 2^19.211 (20.4%)  JUMP 2^18.299 (10.8%)  SET 2^16.71 (3.6%)  BLAKE2S 2^16.295 (2.7%)  MEMORY 2^21.692  TOTAL_COMMITTED 2^26.695
  proof size                  : 323.8 KiB
  proving time                : 0.994 s ± 2.5%      peak memory 12.643 GiB
  blob throughput             : 16.101 blobs/s, 2.013 MiB/s
  verifying                   : 0.00657 s

Fibonacci

cargo run --release -- fibonacci --n 2000000 --log-inv-rate 1 --repeat 3

Fibonacci (in the exponent, i.e. modulo 2^64 - 1), N = 2,000,000
  cycles (VM steps)           : 2,127,880
    details                   : MUL 2^20.936 (98.7%)  DEREF 2^13.967 (0.8%)  SET 2^12.552 (0.3%)  JUMP 2^10.968 (0.1%)  XOR 2^10.966 (0.1%)  MEMORY 2^20.957  TOTAL_COMMITTED 2^25.263
  proof size                  : 285.8 KiB
  proving                     : 0.393 s ± 1.5%   5,416,521 cycles/s      peak memory 5.019 GiB
  verifying                   : 0.00227 s

Batch proving BLAKE2s

BENCH_REPEAT=3 BENCH_COOLDOWN=2 FLOCK_N_LOG=18 cargo test --release --package flock --test batch_proving_hashes -- hash_batch_prove_verify --exact --nocapture --include-ignored

Flock BLAKE2s batch proving, 262,144 compressions (2^18 slots)
  setup (preprocessing, excluded) :      0.0 ms
  witness-gen                     :     64.1 ms ± 8.1%   10.6%
  commit                          :    100.5 ms ± 0.7%   16.6%
  zerocheck                       :    243.6 ms ± 7.5%   40.3%
  lincheck                        :     20.7 ms ± 16.6%   3.4%
  pcs opening                     :    175.6 ms ± 2.4%   29.1%
  other                           :      0.0 ms           0.0%
  ------------------------------------------
  prove TOTAL (witness excluded)  :    540.5 ms ± 4.6%   89.4%
  verify                          :      1.9 ms
  throughput                      :        485,033 compressions/s ± 4.6%
  (~3322.1 XMSS/s equivalent at 146 compressions/signature)

Security

• 128-bit (LDR Johnson, no proximity gaps conjecture)

Snark machinery

• Binary field of 192 bits (tower of degree 3 over the 64 bit field)
• PCS: WHIR (aka Ligerito)
• Proving BLAKE2s by Flock
• RingSwitching, M3 arithmetisation, (and more) by Binius / Binius64 (see DP23 and DP24)