拜占庭将军问题和Paxos算法的提出近40年，真正大规模应用是过去10年，因此Leslie Lamport在2013年获得图灵奖。
Bitcoin从2008年提出至今已过10年，其共识机制PoW算法也稳定运行超过10年。
2018年6月12日VDF函数机制提出，到2019年6月12日，已经满一年。
从Paxos到PoW，再到VDF，分布式系统的理论发展画出了一条美丽的黄金线。
在这条黄金线背后，是计算机系统的基本问题：时间和空间。
当牛顿以为了解这一切的时候，爱因斯坦笑了； 当爱因斯坦以为了解这一切的时候，海森堡和薛定谔笑了； 当人类开始思考时间和空间的时候，上帝笑了。
VDF的提出，是应用加密学，分布式系统和区块链领域的重大技术突破，为区块链的资源共识，时空证明，leader选举等难题奠定可行性的基础。
不仅如此，作为一种延迟服务和随机信标服务，也可以应用到其他领域。
相对于Paxos，VDF保留了区块链开放系统的特点，支持拜占庭容错。相对于PoW，VDF继承了其“工作量”效果，化解了电力之殇。
所以，过去的十年是paxos和pow的十年，未来的十年将是VDF的十年。
因此我倡议成立VDF中国社区，共建硬件和软件生态，一起研究，一起探索新的应用领域。
请志同道合者联系：[email protected]
A verifiable delay function is a function that takes a certain amount of time to compute, and cannot be accelerated through parallelization/additional processors. Once computed, the output can be quickly verified by anyone.
Verifiable Delay Functions take a prescribed time to compute, even on a parallel computer, yet produce a unique output that can be efficiently and publicly verified.
VDFs can be used to create resource-efficient blockchain protocols, and can assist in the construction of proof-of-replication algorithms. You can find more detail about these use cases and others here.
VDFs have a wide variety of decentralized systems: public randomness beacons, leader election in consensus protocols, and proofs of replication.
No -- While VDFs can be seen as a type of ‘proof-of-work’ or hashcash, VDFs differ in that the work can not be greatly parallelized. VDFs have the potential to help create secure consensus algorithms with drastically lower energy costs.
Efficient VDF constructions exist today and can be implemented. However, if malicious actors have access to specialized hardware they can speed up their evaluation, breaking the security of the protocols that rely on VDFs :(
funded 50/50 by Protocol Labs and the Ethereum Foundation
- https://www.supranational.net/
- https://github.com/supranational
- RSA MPC : ligero (to be funded)
- https://vdfresearch.org/
- https://twitter.com/drakefjustin
- https://ethresear.ch/
- MIT VDF Day
- https://www.vdfalliance.org/
Constructions:
2015—Lenstra, Wesolowski A Random Zoo: Sloth, Unicorn, and Trx
2015—Lenstra, Wesolowski A Random Zoo: Sloth, Unicorn, and Trx -- slides
2018 (12 June)—Boneh, Bonneau, Bünz, Fisch Verifiable Delay Functions
2018 (12 June)—Boneh, Bonneau, Bünz, Fisch Verifiable Delay Functions -- slides
2018 (12 June)—Boneh, Bonneau, Bünz, Fisch Verifiable Delay Functions -- vedio
2018 (22 June)—Pietrzak Simple Verifiable Delay Functions
2018 (20 June)—Wesolowski Efficient verifiable delay functions
2018 (30 July)—Boneh, Bünz, Fisch A Survey of Two Verifiable Delay Functions
2019 (13 Feb)—De Feo, Masson, Petit, Sanso Verifiable Delay Functions from Supersingular Isogenies and Pairings
2019 (13 Feb)—De Feo, Masson, Petit, Sanso Verifiable Delay Functions from Supersingular Isogenies and Pairings
2019 ()—Döttling, Garg, Malavolta, Vasudevan Tight Verifiable Delay Functions
2019 (3 June)-Ephraim, Freitag, Komargodski, Pass Continuous Verifiable Delay Functions
TRUST, AND PUBLIC ENTROPY:A UNICORN HUNT
A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
SoK: Transparent Dishonesty: front-running attacks on Blockchain.
Explainers/Articles:
2019—Bruno Skvorc Two Point Oh: Randomness
2018—Bruno Skvorc Two Point Oh: The Beacon Chain
2018—Bruno Skvorc Two Point Oh: Explaining Validators
2019—Maxwell Foley Qi Hardware—VDF FAQ pt. 1
Oct 2018—Arthur Breitman Better randomness
Oct 2018—Trail of Bits Introduction to Verifiable Delay Functions (VDFs)
Sep 2018—Justin Drake Minimal VDF randomness beacon
Aug 2018—Jeromy Johnson A VDF Explainer
Jul 2018—Danny Ryan VDFs are not Proof of Work
Apr 2018—Anatoly Yakovenko Proof of History: A clock for blockchain
A note on isogeny-based hybrid verifiable delay functions
Randomness beacons:
2018 (26 September)—Drake Minimal VDF Randomness Beacon
2018 (16 July)—Drake VDF-based RNG with Linear Lookahead
2018 (8 June)—Jensen, Kristensen, Michno Developing a Trustworthy Randomness Beacon for the Public
2017—Bünz, Goldfeder, Bonneau Proofs-of-delay and Randomness Beacons in Ethereum
2017—Bünz, Goldfeder, Bonneau Proofs-of-delay and Randomness Beacons in Ethereum - slides
2016—Darknet RANDAO: A DAO Working as RNG of Ethereum
1998—Goldschlag, Stubblebine Publicly Veriable Lotteries: Applications of Delaying Functions
Proofs of space/replication:
2018 (August)—Fisch, Bonneau, Greco, Benet Scaling Proof-of-Replication for Filecoin Mining
2018 (24 July)—Fisch Tight Proofs of Space and Replication
2018 (16 July)—Cecchetti, Miers, Juels PIEs: Public Incompressible Encodings for Decentralized Storage
2018 (14 July)—Fisch PoReps: Proofs of Space on Useful Data
2018 (17 Feb)—Pietrzak Proofs of Catalytic Space
2017—Benet, Dalrymple, Greco Proof of Replication
2017—Cohen Proofs of Space and Time
2014—Lerner [Proof of Unique Blockchain Storage](Proof of unique blockchain storage)
2013—Dziembowski, Faust, Kolmogorow, Pietrzak Proofs of Space
video youtube PoS
(pebbling-based PoS)SpaceMint: A Cryptocurrency Based on Proofs of Space
Proof of Space from Stacked Expanders
Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space
Other relevant reading:
2018 (21 July)—Buterin STARKs, Part 3: Into the Weeds
2018 (9 Feb)—Cohen, Pietrzak Simple Proofs of Sequential Work
2014—Gnos1s RSA UFO
2013—Mahmoody, Moran, Vadhan Publicly Verifiable Proofs of Sequential Work
2001—Buchmann, Hamdy A Survey on IQ Cryptography
2000—Boneh, Naor Timed Commitments
1999—Sander Efficient Accumulators without Trapdoor Extended Abstract
1996—Rivest, Shamir, Wagner Time-lock Puzzles and Timed-release Crypto
video：
Justin Drake: Ethereum's Audacious Roadmap to Build a True World Computer
2019—Dan Boneh Verifiable Delay Functions
2019—Jeromy Johnson VDFs and Filecoin
2019—Justin Drake Towards Productions VDFs
2019—Benjamin Wesolowski A Hybrid VDF prover
2019—Erdinc Ozturk Low Latency Modular Multiplication
2019—Abhi Shelat Threshold Factoring from Factoring
2018—Ben Fisch Verifiable Delay Functions: Applications and Candidate Constructions
2018-Justin Drake Ethereum 2.0 randomness
2018-Justin Drake Ethereum 2.0 randomness - Devcon4
2017—Benedikt Bünz Proofs-of-Delay and Randomness Beacons in Ethereum
2017—Joseph Bonneau Verifiable Lotteries
Justin Drake:The Ethereum Community Conference
drg:
Expander Graphs
An introduction to expander graphs
Basic Facts about Expander Graphs
Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions
consensus:
如果比特币没有出块奖励 On the Instability of Bitcoin Without the Block Reward
Snow White: Provably Secure Proofs of Stake
Ouroboros:A Provably Secure Proof-of-Stake Blockchain Protocol
ALGORAND: the efficient and democratic ledger
The Honey Badger of BFT Protocols
https://github.com/poanetwork/hbbft
https://medium.com/poa-network/poa-network-how-honey-badger-bft-consensus-works-4b16c0f1ff94
RANDO Whitepaper
ethereum on VDF:
https://www.mycryptopedia.com/ethereum-beacon-chain-explained/
https://ethresear.ch/t/minimal-vdf-randomness-beacon/3566
https://ethresear.ch/t/sha256-based-vdf/3054
https://ethresear.ch/t/verifiable-delay-functions-and-attacks/2365
https://medium.com/@icebearhww/ethereum-sharding-and-finality-65248951f649
https://medium.com/@icebearhww/ethereum-sharding-workshop-in-taipei-a44c0db8b8d9
https://www.unitimes.io/auther/12232/