doc
VDF research
A Survey of Two Verifiable Delay Functions
On 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
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))`
\[ \begin{align}\begin{aligned}r = 2^T mod l
2^T = m*l + r\\𝜋 = x^m
y = x^(2^T)\\Verify y = (𝜋^l) * (x^r)\end{aligned}\end{align} \]
QRN是Zn 上的二次剩余的|x|绝对值集合，因此是1/4的Zn。
选取的cyclic group QRN+ 与 QRN 同构，x值在{−(n − 1)/2, … , (n − 1)/2}以内。
\[ \begin{align}\begin{aligned}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))\end{aligned}\end{align} \]
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的 :math::F_(p^k) 上order为N的subgroup
X1, X2, Y1, Y2, G 的order为N
φ, ˆφ 为 E, E’ 之间 degree l 的同态映射
\[ \begin{align}\begin{aligned}φ : 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)\end{aligned}\end{align} \]
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
\[ \begin{align}\begin{aligned}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).\end{aligned}\end{align} \]
supersingular curves over Fp2
Let π be the Frobenius endomorphism of E/Fp, the trace map on E/Fp2 is the map
\[ \begin{align}\begin{aligned}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\end{aligned}\end{align} \]
Univariate permutation polynomials
Verifiable Delay Functions
:math::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求解的困难度
\[ \begin{align}\begin{aligned}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.\end{aligned}\end{align} \]