Verifiable Delay Functions
doc
A Survey of Two Verifiable Delay Functions
计算耗时，校验简单，并行计算不能明显提速
Proofs of sequential work (PoSW)
randomness beacon (unpredictable), multiparty random (not bias), consensus from proof of resources(blockchain, elect/vote)
Setup pp = (ek, vk)
(y, 𝜋) = Eval(ek, x)
Verify(vk, x, y, 𝜋)
Correctness, Soundness, Sequentiality, Decodability, Incremental
Proof of Work
blockchain 求解小于某个t值的 H(nonce, x)
hidden order groups, RSA
euler，n = p*q，ϕ(n)=(p-1)*(q-1)
unknown order, 则为Time-lock puzzles
trusted setup, small subgroup attack
Wesolowski
Wesolowski: Efficient verifiable delay functions
verfier随机选定l, 也可改造为nizk，例如置l=next_prime(hash(x, y, T))
r = 2^T mod l
2^T = m*l + r
𝜋 = x^m
y = x^(2^T)
Verify y = (𝜋^l) * (x^r)
Pietrzak
Pietrzak: Simple Verifiable Delay Functions
QRN是Zn 上的二次剩余的|x|绝对值集合，因此是1/4的Zn。
选取的cyclic group QRN+ 与 QRN 同构，x值在{−(n − 1)/2, . . . , (n − 1)/2}以内。
P: μ = x^(2^(T/2)), y=μ^(2^(T/2))
P->V: y
P->V: μ
V->P: r
P: (x', y') = (x^r * μ, μ^r * y)
P -> V: (x', y'), T/2
V: verify y' = x'^(2^(T/2))
De Feo
De Feo: Verifiable Delay Functions from Supersingular Isogenies and Pairings
trusted setup, attack在于curve内部结构
例如bls signature选用的pairing curve，是在embedding degree k, characteristic p的F_(p^k)上order为N的subgroup
X1, X2, Y1, Y2, G 的order为N
φ, ˆφ 为 E, E’ 之间 degree l 的同态映射
φ : X1 → Y1
eY : Y1 × Y2 → G
X1 × Y2 -> Y1 × Y2 -> G
ˆφ : Y2 → X2
eX : X1 × X2 → G
X1 × Y2 -> X1 x X2 -> G
eX (P, ˆφ(Q)) = eY (φ(P ), Q)
P为X1的生成元
pp = (N, X1, X2, Y1, Y2, G, eX , eY , P, φ(P ))
supersingular curves over Fp
类似CSIDH
supersingular curve E/Fp, order N
E, ̃E 在 Fp2 上 quadratic twist 同构，分别对应X2, X1
u ∈ Fp^2 \ Fp, u^2 ∈ Fp
υ : E → ̃E
(x, y) → (u^2 * x, u^3 * y)
X2 = E[N] ∩ E(Fp).
X1 = υ^−1 ( ̃E[N] ∩ ̃E(Fp) )
Y2 = E′[N] ∩ E′(Fp)
Y1 = υ^−1 ( ̃E′[N] ∩ ̃E′(Fp))
isogeny φ : E → E′ of degree l^T , 对应 ˆφ;
P为X1生成元
(ek, vk) = (ˆφ, (E, E′, P, φ(P)))
Eval( ˆφ, Q ∈ Y2) = ˆφ(Q)
Verify(E, E′, P, Q, φ(P), ˆφ(Q))
ˆφ(Q) ∈ X2
eN (P, ˆφ(Q)) = eN (φ(P), Q).
supersingular curves over Fp2
Let π be the Frobenius endomorphism of E/Fp, the trace map on E/Fp2 is the map
Tr: E/Fp2 → E/Fp,
P → P + π(P).
eN (P, Tr(R)) = eN (P, (1+π)(R))
= eN ((1−π)(P), R)
= eN ([2]P, R)
= eN (P, R) ^2
f : E′[N] → X2,
Q → (Tr ◦ ˆφ)(Q);
Eval( ˆφ, Q ∈ E′[N]) = (Tr ◦ ˆφ)(Q)
Verify(E, E′, P, Q, φ(P ), (Tr ◦ ˆφ)(Q))
(Tr ◦ ˆφ)(Q) ∈ X2
eN (P, (Tr ◦ ˆφ)(Q)) = eN (φ(P), Q) ^2
Univariate permutation polynomials
Y ⊆ Fq^n to X ⊆ Fq^m 的injective rational map F = (f1 , ...., fm)
fi( ̄y) = xi for i = 1, ..., m
fi( ̄y) = g( ̄y)/h( ̄y) = xi
zi( ̄y) := g( ̄y)−xi*h( ̄y) = 0
Rational functions on finite fields
有限域上求根
F(X) = g(X)/h(X)
GCD(X^q − X, g(X) − c · h(X))
outputs X − s for the unique s such that F(s) = c
Rational maps on elliptic curves
曲线上求公共点
E(y, x) = y^2 − x^3 − ax − b
R = Res_y (z1 , z2) is a univariate polynomial in x of degree deg(z1) · deg(z2) such that R(x) = 0
R ′= Res_y (R, E)
weaker VDF
基于GCD/Res求解的困难度
Setup(λ, t): choose a (q, F, X , Y) ∈ F specified by λ and t, and output pp := ((q, F ), (q, F )).
Eval((q, F), ̄x):
for an output ̄x ∈ X ⊆ Fq^m
compute ̄y ∈ Y such that F ( ̄y) = ̄x;
The proof π is empty.
Verify((q, F ), ̄x, ̄y, π)
outputs Yes if F ( ̄y) = ̄x.
