Finally, a promising new direction is using time-based cryptography, specifically verifiable delay functions (VDFs). This approach promises to provide good communication efficiency and robustness with resilience to N-1 malicious nodes.
Going back to the original commit-reveal protocol, traditional commitments can be replaced with timed commitments to eliminate the problem of participants refusing to reveal their random contribution. Timed commitments can be opened efficiently by the original committer, or by anybody who is willing to compute a slow function (essentially a VDF). Thus, if any participant drops out of a commit-reveal protocol, their commitment can still be opened by others. It’s essential that the minimum time to open the commitment is long enough that it cannot be done during the first round (the commit phase) of the protocol, otherwise malicious participants could open others’ commitments quickly enough to modify their own contribution and bias the result.
An even more elegant one-round protocol is possible with modern VDFs: drop the commitment entirely. Each participant can simply publish their random contribution ri, and the final result is a combination of each participant’s contribution, run through a VDF. The time delay in computing the VDF ensures that nobody can choose their commitment in a way which biases the final output. This approach was proposed as UNICORN by Arjen Lenstra and Benjamin Wesolowski in 2015, and indeed was a key motivating application in the development of VDFs.
This approach has seen some practical deployment. Chia implements a version of this as part of its consensus protocol, using repeated-squaring VDFs in class groups. Starkware implemented a proof-of-concept VDF-based beacon using SNARK-based VDFs. Ethereum also plans to use this approach, building a dedicated ASIC for computing VDFs to generate randomness at the consensus layer.
Public randomness is an essential component of many protocols, but we still lack any standard DRB that provides high security. The design space is large and many hybrids and combinations of the above approaches are possible. For example, it’s possible to combine a VRF-based protocol with a VDF-based protocol, which adds fresh entropy, for example, as proposed by RandRunner. Ethereum’s Beacon Chain currently uses VRFs, although it may add VDFs in the future to eliminate the possibility of bias from block withholding attacks.
It’s also an open question when honest-majority protocols are acceptable. For a relatively small, vetted group of participants – like the League of Entropy – an honest majority assumption is reasonable. On the other hand, protocols which only require a single honest participant have an inherent advantage – more participants can only improve security. This means these protocols can potentially be deployed with open, permissionless participation.
In Part II, we will discuss the specific application of randomized leader election in consensus protocols, which has slightly different design goals and as a result has seen even more protocols and approaches proposed.
Joseph Bonneau is a Research Partner at a16z crypto. His research focuses on applied cryptography and blockchain security. He has taught cryptocurrency courses at the University of Melbourne, NYU, Stanford, and Princeton, and received a PhD in computer science from the University of Cambridge and BS/MS degrees from Stanford.
Valeria Nikolaenko is a Research Partner at a16z crypto. Her research focuses on cryptography and blockchain security. She has also worked on topics such as long-range attacks in PoS consensus protocols, signature schemes, post-quantum security, and multi-party computation. She holds a PhD in Cryptography from Stanford University under advisorship of Professor Dan Boneh, and worked on the Diem blockchain as part of the core research team.
Editor: Tim Sullivan
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.
Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.