VRS Benchmarks

New Results

Multi-threaded:

ℹ️ VID Benchmark

🔔 FRIDA
l, k, n, prover (ms), communication (byte), verifier (ms)
2048, 64, 128, 431, 2960961, 5
4096, 64, 128, 699, 5844545, 7
8192, 64, 128, 1188, 11611713, 9
16384, 64, 128, 2455, 23146049, 16
32768, 64, 128, 4954, 46214721, 27

🔔 Advz
l, k, n, prover (ms), communication (byte), verifier (ms)
2048, 64, 128, 1097, 131480, 10
4096, 64, 128, 1784, 262552, 16
8192, 64, 128, 3479, 524696, 32
16384, 64, 128, 7262, 1048984, 42
32768, 64, 128, 11342, 2097560, 103

🔔 KzgNNT
l, k, n, prover (ms), communication (byte), verifier (ms)
2048, 64, 128, 150, 4104, 9
4096, 64, 128, 274, 4104, 16
8192, 64, 128, 350, 4104, 15
16384, 64, 128, 703, 4104, 29
32768, 64, 128, 1330, 4104, 66

🔔 PedersenNNT
l, k, n, prover (ms), communication (byte), verifier (ms)
2048, 64, 128, 220, 4104, 7
4096, 64, 128, 267, 4104, 11
8192, 64, 128, 559, 4104, 17
16384, 64, 128, 869, 4104, 28
32768, 64, 128, 1449, 4104, 58

🔔 Gxz + PST
l, k, n, prover (ms), communication (byte), verifier (ms)
2048, 64, 128, 829, 3048, 22
4096, 64, 128, 1289, 3144, 22
8192, 64, 128, 2231, 3240, 20
16384, 64, 128, 3934, 3336, 20
32768, 64, 128, 7684, 3432, 25

🔔 BkzgGxz
l, k, n, prover (ms), communication (byte), verifier (ms)
2048, 64, 128, 1222, 128, 13
4096, 64, 128, 2447, 128, 13
8192, 64, 128, 3865, 128, 25
16384, 64, 128, 7059, 128, 55
32768, 64, 128, 13336, 128, 93

ℹ️ DAS Benchmark

🔔 FRIDA
l, k, n, prover (ms), communication (byte), verifier (ms)
64, 4096, 8192, 911, 301793, 15
64, 8192, 16384, 1350, 330337, 36
64, 16384, 32768, 2818, 360641, 40
64, 32768, 65536, 5568, 392705, 117
64, 65536, 131072, 10387, 426529, 118

🔔 Advz
l, k, n, prover (ms), communication (byte), verifier (ms)
64, 4096, 8192, 1822, 4744, 4
64, 8192, 16384, 2202, 4784, 5
64, 16384, 32768, 3648, 4824, 6
64, 32768, 65536, 5954, 4864, 6
64, 65536, 131072, 10752, 4904, 6

🔔 PeerDAS
l, k, n, prover (ms), communication (byte), verifier (ms)
64, 4096, 8192, 23987, 8208, 8
64, 8192, 16384, 44610, 8208, 7
64, 16384, 32768, 80938, 8208, 8
64, 32768, 65536, 121488, 8208, 6
64, 65536, 131072, 237152, 8208, 8

🔔 KzgNNT
l, k, n, prover (ms), communication (byte), verifier (ms)
64, 4096, 8192, 257, 262152, 7
64, 8192, 16384, 485, 524296, 14
64, 16384, 32768, 881, 1048584, 16
64, 32768, 65536, 1691, 2097160, 25
64, 65536, 131072, 3357, 4194312, 40

🔔 PedersenNNT
l, k, n, prover (ms), communication (byte), verifier (ms)
64, 4096, 8192, 199, 262152, 8
64, 8192, 16384, 433, 524296, 11
64, 16384, 32768, 716, 1048584, 17
64, 32768, 65536, 1482, 2097160, 26
64, 65536, 131072, 3011, 4194312, 52

🔔 Gxz + PST
l, k, n, prover (ms), communication (byte), verifier (ms)
64, 4096, 8192, 1115, 5016, 16
64, 16384, 32768, 3623, 5992, 15
64, 65536, 131072, 13598, 7048, 17

🔔 BkzgGxz
l, k, n, prover (ms), communication (byte), verifier (ms)
64, 4096, 8192, 8918, 128, 3
64, 8192, 16384, 16001, 128, 3
64, 16384, 32768, 26771, 128, 3
64, 32768, 65536, 39469, 128, 3
64, 65536, 131072, 77043, 128, 3

Start:   GxzVRS::compute shares (k=1024, n=2048, L=8)
··Start:   commit twin MLE
····Start:   commit
······End:     commit ..............................................................13.456ms
····End:     commit twin MLE .......................................................14.764ms
··Start:   encode data
····End:     encode data ...........................................................1.577ms
··Start:   merkle commit symbols
····End:     merkle commit symbols .................................................5.064ms
··Start:   eval consolidate
····End:     eval consolidate ......................................................3.236ms
··Start:   mlpc eval
····End:     mlpc eval .............................................................21.771ms
··End:     GxzVRS::compute shares (k=1024, n=2048, L=8) ............................48.679ms
test gxz::transparent::tests::test_gxz_vrs_with_pst ... ok

Our bKZG v.s. ADVZ v.s. NNT

DAS regimes (small

$L$, increasing

$k$)

Multi-threaded (32 threads):

TrustedSetup takes 16020 ms
MultiPartialEval/Fast
deg_x, deg_y, domain_size, commit(ms), prover(ms), communication(byte)
64, 1024, 2048, 36, 959, 128
64, 2048, 4096, 116, 1108, 128
64, 4096, 8192, 215, 1609, 128
64, 8192, 16384, 240, 2094, 128
64, 16384, 32768, 370, 3582, 128
64, 32768, 65536, 670, 7021, 128
64, 65536, 131072, 1160, 14562, 128

MultiEval/Advz
deg_x, deg_y, domain_size, commit+prover(ms), communication(byte)
64, 1024, 2048, 1607, 4728
64, 2048, 4096, 1757, 4768
64, 4096, 8192, 2134, 4808
64, 8192, 16384, 3037, 4848
64, 16384, 32768, 4885, 4888
64, 32768, 65536, 8698, 4928
64, 65536, 131072, 15330, 4968

KZG-NNT
deg_x, deg_y, domain_size, commit(ms), verify(ms), communication(byte)
64, 1024, 2048, 143, 2, 65608
64, 2048, 4096, 182, 3, 131144
64, 4096, 8192, 308, 7, 262216
64, 8192, 16384, 570, 8, 524360
64, 16384, 32768, 1219, 21, 1048648
64, 32768, 65536, 2404, 38, 2097224
64, 65536, 131072, 4751, 85, 4194376

Single-threaded

TrustedSetup takes 442969 ms
MultiPartialEval/Fast
deg_x, deg_y, domain_size, commit(ms), prover(ms), communication(byte)
64, 1024, 2048, 514, 5183, 128
64, 2048, 4096, 1085, 10469, 128
64, 4096, 8192, 1822, 22647, 128
64, 8192, 16384, 3451, 45624, 128
64, 16384, 32768, 6429, 95898, 128
64, 32768, 65536, 12206, 191615, 128
64, 65536, 131072, 23572, 392299, 128

MultiEval/Advz
deg_x, deg_y, domain_size, commit+prover(ms), communication(byte)
64, 1024, 2048, 4128, 4728
64, 2048, 4096, 8599, 4768
64, 4096, 8192, 17837, 4808
64, 8192, 16384, 39121, 4848
64, 16384, 32768, 76362, 4888
64, 32768, 65536, 159465, 4928
64, 65536, 131072, 337270, 4968

KZG-NNT
deg_x, deg_y, domain_size, commit(ms), verify(ms), communication(byte)
64, 1024, 2048, 1453, 16, 65608
64, 2048, 4096, 2970, 24, 131144
64, 4096, 8192, 6244, 42, 262216
64, 8192, 16384, 11591, 69, 524360
64, 16384, 32768, 23196, 133, 1048648
64, 32768, 65536, 46422, 261, 2097224
64, 65536, 131072, 92079, 463, 4194376

VID regimes (moderate

$k$, increasing

$L$)

Multi-threaded (32 threads):

TrustedSetup takes 7733 ms
MultiPartialEval/Fast
deg_x, deg_y, domain_size, commit(ms), prover(ms), communication(byte)
256, 256, 512, 46, 475, 128
512, 256, 512, 156, 427, 128
1024, 256, 512, 233, 633, 128
2048, 256, 512, 380, 726, 128
4096, 256, 512, 701, 1263, 128
8192, 256, 512, 1423, 1782, 128

MultiEval/Advz
deg_x, deg_y, domain_size, commit+prover(ms), communication(byte)
256, 256, 512, 749, 16936
512, 256, 512, 820, 33320
1024, 256, 512, 1117, 66088
2048, 256, 512, 1563, 131624
4096, 256, 512, 2505, 262696
8192, 256, 512, 4503, 524840

KZG-NNT
deg_x, deg_y, domain_size, commit(ms), verify(ms), communication(byte)
256, 256, 512, 111, 2, 16456
512, 256, 512, 160, 3, 16456
1024, 256, 512, 286, 3, 16456
2048, 256, 512, 519, 5, 16456
4096, 256, 512, 931, 6, 16456
8192, 256, 512, 1834, 13, 16456

Breakdownn of Advz & NNT Cost

Start:   AdvzVRS::compute shares (k=257, n=512, L=4097)
··Start:   encode data
··End:     encode data .............................................................141.219ms
··Start:   aggregate poly
··End:     aggregate poly ..........................................................841.822ms
··Start:   commit row_poly
··End:     commit row_poly .........................................................877.784ms
··Start:   multi-eval on agg_poly
··End:     multi-eval on agg_poly ..................................................884.534ms
End:     AdvzVRS::compute shares (k=257, n=512, L=4097) ............................2.745s
    
======
Start:   KzgNntVRS::compute shares (k=257, n=512, L=4097)
Start:   encode data
End:     encode data ...............................................................117.211ms
Start:   commit col_poly
End:     commit col_poly ...........................................................466.776ms
End:     KzgNntVRS::compute shares (k=257, n=512, L=4097)
4096, 256, 512, 818, 10, 16456

Single-threaded:

TrustedSetup takes 194907 ms
MultiPartialEval/Fast
deg_x, deg_y, domain_size, commit(ms), prover(ms), communication(byte)
256, 256, 512, 454, 2484, 128
512, 256, 512, 940, 3621, 128
1024, 256, 512, 1769, 6523, 128
2048, 256, 512, 4507, 10658, 128
4096, 256, 512, 8014, 18422, 128
8192, 256, 512, 12148, 34084, 128

MultiEval/Advz
deg_x, deg_y, domain_size, commit+prover(ms), communication(byte)
256, 256, 512, 1798, 16936
512, 256, 512, 2822, 33320
1024, 256, 512, 4821, 66088
2048, 256, 512, 8805, 131624
4096, 256, 512, 17717, 262696
8192, 256, 512, 32795, 524840

KZG-NNT
deg_x, deg_y, domain_size, commit(ms), verify(ms), communication(byte)
256, 256, 512, 969, 7, 16456
512, 256, 512, 1573, 11, 16456
1024, 256, 512, 2779, 18, 16456
2048, 256, 512, 5072, 25, 16456
4096, 256, 512, 8922, 39, 16456
8192, 256, 512, 16346, 70, 16456

Auxiliary

Hyperplonk PST on Mac M1

Variables,Commit (ms),Open (ms),Verify (ms)
4,416.404,1153.950,4377.812
5,568.337,1647.862,4404.954
6,799.970,2206.016,4578.862
7,1158.545,3073.854,4973.125
8,1807.720,4209.100,4878.687
9,2760.254,5908.054,5253.408
10,5000.208,9872.716,5512.441
11,7777.350,14534.000,5455.500
12,14038.450,20789.658,5497.175
13,25255.433,34812.616,5648.091
14,45133.875,59521.841,5718.000
15,82943.466,110527.916,6165.308
16,151415.858,201583.800,6203.800
17,299628.700,349609.908,6446.908
18,574171.683,648265.383,6888.983
19,1169633.475,1223891.008,7087.250
20,2242165.562,2377528.562,7677.542
21,4185713.333,4776341.916,7194.437
22,7639503.208,8568359.250,7354.958
23,15347376.041,16793795.812,7370.395
24,34434604.896,35856089.958,9392.187

Example toggle

CODE!