search

a16z / jolt

The simplest and most extensible zkVM. Fast and fully open source from a16z crypto and friends. ⚡
https://jolt.a16zcrypto.com
MIT License
587 stars 106 forks source link

Sparse Spartan #324

Open sragss opened 2 months ago

sragss commented 2 months ago

Spartan has 2 sumchecks. Both of them are quite sparse (high P(eval = 0)). Performance is probably not too bad given the special casing in DensePolynomial::bound_poly_var_top_zero_optimized and Sumcheck::compute_eval_points_quadratic but we're wasting 80% of the peak RAM usage in Spartan.

Second sumcheck:

Round: 0
poly_ABC pre binding zeros 771751935/1073741824 = 71.87%
Round: 0
poly_A zeros 234881024/536870912 = 43.75%
Round: 0
poly_B zeros 404681459/536870912 = 75.38%

Round: 1
poly_A zeros 0/268435456 = 0.00%
Round: 1
poly_B zeros 163539569/268435456 = 60.92%

Round: 2
poly_A zeros 0/134217728 = 0.00%
Round: 2
poly_B zeros 45232620/134217728 = 33.70%

Round: 3
poly_A zeros 0/67108864 = 0.00%
Round: 3
poly_B zeros 4167548/67108864 = 6.21%