- Alex Xiong·Last edited by Alex Xiong on Mar 7, 2025Linked with GitHubContributed by
Log in to edit or delete your comments and be notified of replies.
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
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
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!
Read more
Subset Sum from Lattice Reduction
Recall that the goal of lattice reduction algorithms are to find orthonormal bases (i.e. nice, short, and nearly orthogonal) given an arbitrary bases of the lattice. More technically, they obtain a basis whose Gram-Schmidt vectors are not decreasing too quickly (which implies that the basis vectors are somewhat orthogonal to each other).
Nov 5, 2024Rust `no_std` Playbook
This is a note summarizing my experience with making rust libraries no_std compatible (especially for WASM supports).
Apr 4, 2024On Siddhartha
a personal digest of the book <Siddhartha> by Hermann Hesse, and reflection on its messages.
Apr 4, 2024CRYSTAL-Kyber Engineering Plan
Presentation slide by Alex
Jul 14, 2023Published on 
HackMD
HackMD