mirror of
https://github.com/darkrenaissance/darkfi.git
synced 2026-04-28 03:00:18 -04:00
74 lines
1.6 KiB
Python
74 lines
1.6 KiB
Python
#!/usr/bin/env sage
|
|
|
|
"""
|
|
Implements the simplified Nova scheme introduced in [1] Section 5.1
|
|
|
|
[1] Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
|
|
https://eprint.iacr.org/2021/370.pdf
|
|
[2] Nova: The ZK Bug of the Year (by Wilson Nguyen)
|
|
https://www.youtube.com/watch?v=SOAQCL1NaYY
|
|
"""
|
|
|
|
q = 0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001
|
|
K = GF(q)
|
|
|
|
hash_table = {}
|
|
def hash(key):
|
|
if key in hash_table:
|
|
return hash_table[key]
|
|
|
|
c = K.random_element()
|
|
while c > 2**250 - 1:
|
|
c = K.random_element()
|
|
hash_table[key] = c
|
|
return c
|
|
|
|
def fold(U, u):
|
|
return U + (u,)
|
|
|
|
z0 = 5
|
|
F = lambda z, ω: 5*z
|
|
|
|
i = 0
|
|
ω0 = ()
|
|
z1 = F(z0, ω0)
|
|
u1 = hash((1, z0, z1, ()))
|
|
U1 = ()
|
|
# ZK proof
|
|
assert u1 == hash((1, z0, z1, ()))
|
|
assert z1 == F(z0, ω0)
|
|
|
|
i = 1
|
|
ω1 = ()
|
|
U2 = fold(U1, u1)
|
|
z2 = F(z1, ω1)
|
|
u2 = hash((i+1, z0, z2, U2))
|
|
assert u1 == hash((i, z0, z1, U1))
|
|
assert U2 == fold(U1, u1)
|
|
assert z2 == F(z1, ω1)
|
|
assert u2 == hash((i+1, z0, z2, U2))
|
|
|
|
i = 2
|
|
ω2 = ()
|
|
U3 = fold(U2, u2)
|
|
z3 = F(z2, ω2)
|
|
u3 = hash((i+1, z0, z3, U3))
|
|
assert u2 == hash((i, z0, z2, U2))
|
|
assert U3 == fold(U2, u2)
|
|
assert z3 == F(z2, ω2)
|
|
assert u3 == hash((i+1, z0, z3, U3))
|
|
|
|
# By folding proofs, we simultaneously verify all the asserts
|
|
# when verifying U3 with u3.
|
|
|
|
# Although there is no connection between u2 in i=1, and u2 in i=2,
|
|
# by including the satisfying accumulator U2, and proving U3 = fold(U2, u2),
|
|
# we guarantee the recursive nature of the circuit.
|
|
|
|
# We've now made a proof of what 5^4 is
|
|
assert z0 == 5
|
|
assert z1 == 5*5
|
|
assert z2 == 5*5*5
|
|
assert z3 == 5^(i+2)
|
|
|