可验证延迟函数（Verifiable Delay Function, VDF）：
VDF 这个概念最初由斯坦福大学密码学教授 Dan Boneh 等人在2018年论文《Verifiable Delay Functions》中给出。该篇文章于 2018 年发表在密码学顶级会议之一的 CRYPTO 上。
目前的VDF算法复杂度较高，离实用仍有差距。
https://github.com/Chia-Network/vdf-competition/中有对VDF的实现进行了竞赛。
[研究]可验证延迟函数（VDF）（一）一文搞懂VDF中有很详细的介绍。
https://github.com/cambrian/accumulator/blob/master/src/group/class.rs中有对https://github.com/Chia-Network/vdf-competition/blob/master/classgroups.pdf的class group 做实现。
VDF是串行运算算法，执行时间可预知，且无法通过并行来加速。通过VDF生成的证明可被快速verify。
目前知名的不可并行的串行运算为：对未知order的group进行repeated squaring。
The unknown order requirement is due to the divisibility of the order of a finite group by the order of any element in the group; if the group order is known then the repeated squaring operation could be reduced modulo the order of the group, shortcutting the computation.
在VDF中：
- 若使用RSA group，则需要trusted setup，并保证生成后的有毒垃圾被即时清理，否则VDF的sequentiality requirement将broken。
- 若使用class group of binary quadratic form将不需要trusted setup。因为其order为一个负素数判别式 d d d，当 ∣ d ∣ ≡ 3 m o d 4 |d|\equiv 3\ mod\ 4 ∣d∣≡3 mod 4时，is believed to be difficult to compute when d d d is sufficiently large, making the order of the class group effectively unknown. Therefore, a suitable discriminant ——and its associated class group —— can be chosen without the need for a trusted setup, which is a major advantage for using class groups in applications requiring groups of unknown order.
1. Binary quadratic form
f
(
x
,
y
)
=
a
x
2
+
b
x
y
+
c
y
2
f(x,y)=ax^2+bxy+cy^2
f(x,y)=ax2+bxy+cy2, where
a
,
b
,
c
∈
R
a,b,c\in R
a,b,c∈R and
a
!
=
0
,
b
!
=
0
,
c
!
=
0
a!=0, b!=0,c!=0
a!=0,b!=0,c!=0。
f
=
(
a
,
b
,
c
)
f=(a,b,c)
f=(a,b,c)可称为a form。
若
f
=
(
a
,
b
,
c
)
f=(a,b,c)
f=(a,b,c), where
a
,
b
,
c
∈
Z
a,b,c\in Z
a,b,c∈Z and
a
!
=
0
,
b
!
=
0
,
c
!
=
0
a!=0, b!=0,c!=0
a!=0,b!=0,c!=0，则 f 称为integral form。
c
o
n
f
(
f
)
=
g
c
d
(
a
,
b
,
c
)
conf(f)=gcd(a,b,c)
conf(f)=gcd(a,b,c)称为content of a form。
若
c
o
n
f
(
f
)
=
1
conf(f)=1
conf(f)=1，则form f称为primitive。
discriminant of form f为：
Δ
(
f
)
=
b
2
−
4
a
c
\Delta(f)=b^2-4ac
Δ(f)=b2−4ac。
若
−
a
<
b
≤
a
-a
