This is a repository of code implementing
- Pietrzak's VDF . For reference see Pietrzak's paper
- Boneh's Implementation study. Boneh
- Ephraim's CVDF . For reference see Ephraim's paper
NIST Security RSA Modulus to bits of security - §5.6.1 p.62–64
Greek letters so I can copy paste them as variables:
Α α, Β β, Γ γ, Δ δ, Ε ε, Ζ ζ, Η η, Θ θ, Ι ι, Κ κ, Λ λ, Μ μ, Ν ν, Ξ ξ, Ο ο, Π π, Ρ ρ, Σ σ/ς, Τ τ, Υ υ, Φ φ, Χ χ, Ψ ψ, and Ω ω.
To run the basic algo
$ python3 SimplePietrzakVDF.py
To run :
$ python3 PietrzakVDF.py
Notice that generating the proof takes twice as long as just computing the solution, because we need the solution to start the proof. This is why Pietrzak suggests using a cache of 2^s values for the first u1,..,us values.
This illustrates the Pietrzak VDF unoptimized proving.
Values: p:123456211,q:123384263 -> N:15232553607007493
Values: t:25 -> τ:33554432, x:10336420527515286
Values: y:6730274324803502
Finished y in 3371.8 ms
Delta: δ:8
Values: T:16777216, x1:737303720960756, y1:6503654552673549, u1:2904550846683176, r1: 3949717375372756
Values: T:8388608, x2:8587259714517165, y2:965774014262304, u2:5132683510045221, r2: 15226174006436100
Values: T:4194304, x3:14357301701474423, y3:11816266434493360, u3:13058390771870895, r3: 4346512451169887
Values: T:2097152, x4:1869756344041072, y4:1818647325997514, u4:3827475356658932, r4: 6460236744955589
Values: T:1048576, x5:5223957487363885, y5:7470077431694890, u5:11765284243589050, r5: 15053332088787858
Values: T:524288, x6:8457766370312006, y6:13840387197545075, u6:6252806191178792, r6: 13470853462648855
Values: T:262144, x7:6543492917407183, y7:6903989491803626, u7:12887160979353178, r7: 4477401081893626
Values: T:131072, x8:10639947021602175, y8:13201177160301614, u8:8539581002386140, r8: 9784615343800531
Values: T:65536, x9:10321653091093358, y9:9894396812075208, u9:5302912364605390, r9: 5895366546123005
Values: T:32768, x10:944960549906164, y10:6021896590182285, u10:8166060922486315, r10: 14475471582341787
Values: T:16384, x11:1101277702987120, y11:3127323027542307, u11:1263533470468999, r11: 6214394948851538
Values: T:8192, x12:4595492128063536, y12:4934097441219446, u12:4286631405870556, r12: 10713158230135794
Values: T:4096, x13:3781220564224712, y13:2381596696209336, u13:5533368843195820, r13: 5908425280076839
Values: T:2048, x14:6237626858562651, y14:2561374779569260, u14:10146029160380048, r14: 13421771146249791
Values: T:1024, x15:12317551697932139, y15:14997272247190783, u15:2584778140375718, r15: 5917364320040939
Values: T:512, x16:14839607224404471, y16:2474176029439793, u16:4475360624683094, r16: 13573088085482958
Values: T:256, x17:3009121572803792, y17:5250900136167050, u17:14456544619420216, r17: 13844865600250513
Match Last (x17)^2^2^8 5250900136167050 = y17: 5250900136167050
Finished total calc+proof in 6668.86 ms
Result: 6730274324803502
Proof: [2904550846683176, 5132683510045221, 13058390771870895, 3827475356658932, 11765284243589050, 6252806191178792, 12887160979353178, 8539581002386140, 5302912364605390, 8166060922486315, 1263533470468999, 4286631405870556, 5533368843195820, 10146029160380048, 2584778140375718, 4475360624683094, 14456544619420216]
Proof is valid. Finished verifying in 0.95 ms
The optimized version really shows how much longer it adds to generate the proof:
This illustrates the Pietrzak Optimized VDF
Values: p:123456211,q:123384263 -> N:15232553607007493
Values: t:25 -> τ:33554432, x:10336420527515286
Delta: δ:8
Finished checkpoints in 0.01 ms
Finished squarings in 3229.45 ms
Values: T:16777216, x0:737303720960756, y0:6503654552673549, u0:2904550846683176, r0: 3949717375372756
Values: T:8388608, x1:8587259714517165, y1:965774014262304, u1:5132683510045221, r1: 15226174006436100
Values: T:4194304, x3:14357301701474423, y3:11816266434493360, u3:13058390771870895, r3: 4346512451169887
Values: T:2097152, x7:1869756344041072, y7:1818647325997514, u7:3827475356658932, r7: 6460236744955589
Values: T:1048576, x15:5223957487363885, y15:7470077431694890, u15:11765284243589050, r15: 15053332088787858
Values: T:524288, x31:8457766370312006, y31:13840387197545075, u31:6252806191178792, r31: 13470853462648855
Values: T:262144, x32:6543492917407183, y32:6903989491803626, u32:12887160979353178, r32: 4477401081893626
Values: T:131072, x33:10639947021602175, y33:13201177160301614, u33:8539581002386140, r33: 9784615343800531
Values: T:65536, x34:10321653091093358, y34:9894396812075208, u34:5302912364605390, r34: 5895366546123005
Values: T:32768, x35:944960549906164, y35:6021896590182285, u35:8166060922486315, r35: 14475471582341787
Values: T:16384, x36:1101277702987120, y36:3127323027542307, u36:1263533470468999, r36: 6214394948851538
Values: T:8192, x37:4595492128063536, y37:4934097441219446, u37:4286631405870556, r37: 10713158230135794
Values: T:4096, x38:3781220564224712, y38:2381596696209336, u38:5533368843195820, r38: 5908425280076839
Values: T:2048, x39:6237626858562651, y39:2561374779569260, u39:10146029160380048, r39: 13421771146249791
Values: T:1024, x40:12317551697932139, y40:14997272247190783, u40:2584778140375718, r40: 5917364320040939
Values: T:512, x41:14839607224404471, y41:2474176029439793, u41:4475360624683094, r41: 13573088085482958
Values: T:256, x42:3009121572803792, y42:5250900136167050, u42:14456544619420216, r42: 13844865600250513
Match Last (x42)^2^2^8 5250900136167050 = y42: 5250900136167050
Finished proof in 51.13 ms
Finished total calc+proof in 3280.66 ms
Result: 6730274324803502
Proof: [2904550846683176, 5132683510045221, 13058390771870895, 3827475356658932, 11765284243589050, 6252806191178792, 12887160979353178, 8539581002386140, 5302912364605390, 8166060922486315, 1263533470468999, 4286631405870556, 5533368843195820, 10146029160380048, 2584778140375718, 4475360624683094, 14456544619420216]
Proof is valid. Finished verifying in 0.79 ms
The repeated squarings take slightly longer, because it requires storing checkpoints. The proof generation requires only 58 ms, for a total that's not that different from the non-proving algorithm.
Also notice the verification is just as fast.