Asiacrypt ‘22: Field Notes
Editor’s note: Field notes is a series where we report on the ground at significant industry, research, and other events. In this edition, Joe Bonneau, a16z crypto Research Partner, shares highlights particularly related to blockchains from Asiacrypt, which was held in Taiwan December 6-9. Also in attendance was Arasu Arun, an a16z crypto research intern during the summer of 2022, who also presented a paper (see below). Asiacrypt is a theoretical cryptography conference, and many of the results are far ahead of practical industry concerns today, but this summary focuses on talks with potential implications for web3. You can see the complete program here.
Asiacrypt papers are free online, and each author made a 5 minute video summarizing their paper. Many of these are very useful because they force the presenter to omit technical detail and explain the problem they were working on at a high level. Paradoxically, I learned more from some short videos than the full talk (and they can be more difficult for authors to prepare than a longer talk). I’d recommend starting with the short videos (before full talks or full papers). (Some of the videos are very creative: one author made a rap video and another did a dramatic enactment of their signature scheme attack.)
While Asiacrypt is not blockchain-focused, a surprising number of talks cited blockchains as motivating applications for designing new primitives (even though many of the solutions are theoretical rather than practical). There were also a number of talks on related topics, especially Zero Knowledge and SNARKs. Other popular topics included post-quantum crypto and advanced primitives like functional encryption and witness encryption (which are not practical today).
Several papers take ideas that arose in the blockchain space, formalize the concepts, and provide more rigorous security definitions or prove fundamental limits. It’s clear that ideas and concepts are flowing back and forth between the traditional cryptography community and the blockchain research community.
Best paper winners
Full Quantum Equivalence of Group Action DLog and CDH, and More Hart Montgomery, Mark Zhandry
Many of the most efficient and powerful cryptographic schemes we know of are based on the hardness of discrete log and related problems in finite groups (e.g., CDH and DDH). Unfortunately, these assumptions are not quantum secure, as Shor’s algorithm can compute discrete logs generically (in any group) using a quantum computer. However, there is a more relaxed notion of group actions, which can be defined in other settings like isogenies and lattices. Group exponentiation is one example of a group action, which most classical crypto is based on, but there are modern proposals which are plausibly-post-quantum like SIDH (now broken), CSI-Fish, and CSIDH. There are parallel problems of discrete log (GA-DL) and other classic assumptions (GA-CDH, GA-DDG) in the group action model. The main contribution of this talk is to show that GA-DL and GA-CDH are equivalent to a quantum attacker, so any traditional cryptosystem based on CDH has a GA-CDH equivalent that is secure if GA-DL is hard. This is a somewhat theoretical result but it’s important to show that the group action problems behave somewhat like classical equivalents. This paper also proves a ton of other useful results and is a good overview of the group actions abstraction.
SwiftEC: Shallue–van de Woestijne Indifferentiable Function to Elliptic Curves Jorge Chávez-Saab Francisco Rodrı́guez-Henrı́quez Mehdi Tibouchi
Hashing to an elliptic curve is an important step in many cryptographic operations (including BLS signatures and VRFs). The classic method is to hash, hope you hit a point, then repeat, but this is not efficient or side-channel resistant (the timing is data-dependent). This paper introduces a new method that improves on Elligator^2, the prior state-of-the-art, but works on more curves while still being practically efficient, constant-time, and indistinguishable from random (given an underlying hash that is a random oracle).
Directly blockchain-relevant papers
Non-Interactive Mimblewimble Transactions, Revisited Georg Fuchsbauer, Michele Orrù
MimbleWimble is an interesting proposal for private, efficient cryptocurrency transactions which has seen some adoption (MimbleWimbleCoin, Grin). MimbleWimble transactions build off of confidential transactions, hiding the amount of each input and output. They also support efficient cut-through, which means two transactions with a matching input/output can be non-interactively combined into a single simplified transaction. In fact, at any time the entire blockchain can be represented as a single transaction from a set of inputs (coin-minting transactions) to outputs (all currently valid UTXOs) aggregating all other chain activity. A drawback of the original MimbleWimble transaction was that transaction creation is an interactive protocol between sender and receiver who must both be online to create a transaction. There was a proposal in 2019 to enable non-interactive transactions (like most cryptocurrencies support). This paper describes a flaw in that protocol, fixes it, and proves the result secure. This is practical construction and the fixed protocol has already been implemented by the MWEB extension for Litecoin.
A Universally Composable Non-Interactive Aggregate Cash System Yanxue Jia, Shi-Feng Sun, Hong-Sheng Zhou, Dawu Gu
This paper also works on MimbleWimble (see above), introducing an abstract definition for an “aggregate cash system” of which MimbleWimble is an example. The paper also introduces precise security definitions in the Universal Composability (UC) model and proves a modified version of MimbleWimble secure under this rigorous definition. This work is slightly more theoretical and does not consider non-interactive transactions as the Fuchsbauer et al. paper does.
Practical Provably Secure Flooding for Blockchains Chen-Da Liu-Zhang, Christian Matt, Ueli Maurer, Guilherme Rito, Søren Eller Thomsen
This paper considers the peer-to-peer network layer (or “flooding layer”) underlying all blockchain consensus protocols. This has always been something of a backwater in terms of blockchain analysis with everybody just hoping for the best without any formal security properties. There has always been a risk that an attacker who creates a huge number of sybil nodes can disrupt consensus by preventing messages between honest parties from being delivered (e.g., what if you spin up a Bitcoin node and every peer you connect to is malicious?) This paper proposes a way around this, by incorporating “weight” (percentage of hash power or stake) at the network layer. The core idea is that nodes prioritize peering with parties with higher weight. In this way, as long as a majority of the weight is honest (as is assumed at the consensus layer), the network layer should be secure. This paper proves that result rigorously. I thought this was one of the most creative and original talks, on a problem most people hadn’t been thinking enough about. I think this might be interesting to pursue for practical projects.
SNACKs: Leveraging Proofs of Sequential Work for Blockchain Light Clients Hamza Abusalah, Georg Fuchsbauer, Peter Gazi, Karen Klein
This paper considers the problem of an ultralight client joining a blockchain network and needing to verify a proof of how long the current longest chain is. The proof is called a SNACK (succinct non-interactive argument of chain knowledge). The problem is similar to the problem studied by FlyClient (a version of which is now implemented by Ethereum 2.0) and NiPoPoW (Non-interactive proofs of proofs of work). This is not the same as a succinct blockchain like Mina in that the proofs in SNACKs/FlyClient don’t attest to the validity of transactions, only the aggregate proof of work/space, and so on. (It’s not clear how these ideas extend to proof-of-stake.) SNACKs connects this problem to constructions for Proofs of Sequential Work, which is an interesting duality – PoSW constructions turn out to be generically sufficient to construct SNACKs. This paper also discusses a practical attack where clients accept a proof for a chain, but the prover never releases the data.
Papers on consensus protocols
YOLO YOSO: Fast and Simple Encryption and Secret Sharing in the YOSO Model Ignacio Cascudo, Bernardo David, Lydia Garms, Anders Konring
The “You only speak once” design principle has evolved out of protocols like Algorand consensus. To avoid adaptive attackers in a communication-efficient protocol (like consensus), a random committee is chosen for each step of a protocol (e.g., propose, confirm, finalize), and committee members only broadcast one message each. So by the time their membership in the committee is known they are no longer a target for adaptive attackers. Cryptographers have since produced a few papers formalizing this model. This paper introduces a new efficient technique for encrypting messages to anonymous YOSO committees (that may not even have been chosen yet), which is a useful tool for designing protocols in this model.
Efficient Adaptively-Secure Byzantine Agreement for Long Messages Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak
Most work on distributed consensus doesn’t worry about the impact of agreeing to long messages (e.g., large transactions in one block) and treats messages as arbitrarily small. This paper works in a model that takes into account message size, reconsidering and improving known bounds. The results are asymptotic, but it is interesting to see that accounting for very large messages changes formal bounds on distributed consensus.
State Machine Replication under Changing Network Conditions Andreea Alexandru, Erica Blum, Jonathan Katz, Julian Loss
State Machine Replication (SMR) is an abstraction of Byzantine consensus where parties maintain a state machine – essentially what all blockchains try to achieve. Classically, most BFT protocols assume either a synchronous network (in which up to N/2 corruptions can be tolerated) or an asynchronous network (in which up to N/3 corruptions can be tolerated). This paper asks: can we design a protocol that works under either condition and achieves the optimal fault-tolerance in either case? It turns out to be possible and this paper introduces two protocols (Update and Upstate) that do so and can even tolerate the network oscillating from synchronous to asynchronous (if the attacker’s power decreases whenever the network is asynchronous). Unfortunately, the communication complexity is O(N^3) and O(N^2), so they are only practical when run with small fixed committees. An interesting future direction might be to design or analyze communication-efficient SMR protocols like modern proof-of-stake protocols which similarly tolerate changing network models.
Encryption to the Future: A Paradigm for Sending Secret Messages to Future (Anonymous) Committees Matteo Campanelli, Bernardo David, Hamidreza Khoshakhlagh, Anders Konring, Jesper Buus Nielsen
This paper considers protocols with a rotating committee in the YOSO model. That is, every epoch a new anonymous committee is formed via random selection. How can the current committee hand over secret state (e.g., a signing key) to the next committee? This paper proposes encryption-to-the-future, a primitive where the current committee can encrypt so that future committee members can decrypt, even though the future committee is not yet known. This relies on witness encryption and hence is not a practical solution (yet) but is a powerful way of modeling this problem. Unfortunately, they also show that under some conditions this problem is as hard as witness encryption, so it is unlikely to have an efficient general solution.
Papers on ZK proofs
Flashproofs: Efficient Zero-Knowledge Arguments of Range and Polynomial Evaluation with Transparent Setup Nan Wang, Sid Chi-Kin Chau
Range proofs (or technically range arguments), which show that a private committed value is within a certain range, are used in many blockchain protocols, from Confidential Transactions to proofs of solvency to sealed-bid auctions. This paper introduces a new variant of range proofs for Pedersen Commitments with no trusted setup that is more efficient than prior work. The authors implemented it in Solidity and the gas costs for verifying a 32-bit range proof (about 230k gas) are similar to verifying a Groth16 SNARK. There is also an amortized version for verifying multiple range proofs. This could be a useful tool for implementations seeking to skip the trusted setup in Groth16. The paper also introduces a related proof of correct polynomial evaluation.
Improved Straight-Line Extraction in the Random Oracle Model With Applications to Signature Aggregation Yashvanth Kondi, abhi shelat
This paper reconsiders the problem of signature aggregation. A prover (potentially a block creator) wants to show that a set of public keys have signed a set of messages, with less work for the verifier than just doing a linear verification of each key/message/signature tuple. Note that BLS signatures easily support this use case and this is increasingly popular in many blockchain protocol designs, but this work focuses on aggregating Schnorr or other signatures (like EdDSA). Some new theoretical techniques are introduced which increase by about two orders of magnitude the practical performance of the prior best-known approach (Fischlin ‘05).
Short-Lived Zero-Knowledge Proofs and Signatures Arasu Arun, Joseph Bonneau, Jeremy Clark
The goal of this work is to design short-lived zero-knowledge proofs whose soundness expires, so they are convincing for a brief period of time and then not convincing because they might have been forged. Potential applications include bringing deniability in email signing or verifiable election ballot-casting. The paper proposes constructions for proofs and signatures which are actually quite practical. It’s an interesting question if there are applications in the blockchain space.
Rotatable Zero Knowledge Sets: Post Compromise Secure Auditable Dictionaries with application to Key Transparency Brian Chen, Yevgeniy Dodis, Esha Ghosh, Eli Goldin, Balachandar Kesavan, Antonio Marcedone, Merry Ember Mou
Verifiable random functions (VRFs) are a powerful tool for random selection in blockchains. They’re also used for privacy in public transparency logs – for example, proposals for key transparency like CONIKs or in DNSSEC’s NSEC5 extension. These protocols, however, assume a fixed VRF key forever. Changing the VRF key in a large directory is tedious because it requires proving all of the new VRF outputs correspond correctly to old outputs. This paper proposes a new VRF construction, a rotatable VRF, designed to make this process more efficient by producing a compact proof of consistency over a large set of VRF outputs. This might have applications in consensus protocols which use VRFs as well, though this was not explored in the paper/talk.
Linear-map Vector Commitments and their Practical Applications Matteo Campanelli, Anca Nitulescu, Carla Rafols, Alexandros Zacharakis, Arantxa Zapico
A vector commitment is an abstraction that includes Merkle trees, which commit to a vector of values in each leaf and are used, for example, to commit to the storage of a smart contract. The concept has been around since Merkle but was formalized in 2013. This paper adds new definitions for properties like aggregatable vector commitments. If a block contains multiple smart contract transactions that try to prove the contents of values in their storage, an aggregatable vector commitment scheme can combine these proofs more efficiently (for verifiers) than verifying each individual proof. This talk was not blockchain-focused but introduced definitions for aggregation (including unbounded aggregation, when aggregated proofs can themselves be aggregated) as well as an abstraction for recursively building a vector-commitment of vector commitments, similar to how Verkle trees work.
PointProofs, Revisited Benoît Libert, Alain Passelègue, Mahshid Riahinia
PointProofs is an efficient aggregatable vector commitment scheme (see above), introduced in 2022. It’s an interesting proposal that might be useful in blockchain projects. This paper doesn’t modify PointProofs at all but provides a better security proof using a weaker assumption.
An Analysis of the Algebraic Group Model Jonathan Katz, Cong Zhang, Hong-Sheng Zhou
The Algebraic Group Model (AGM) is a recent popular abstraction for security proofs in crypto protocols. Like the Random Oracle Model for hash functions, this model is not achievable in reality (as it only considers a natural subset of possible attacks) but enables efficient and elegant security proofs. It has been claimed that AGM proofs are stronger than an earlier version, the Generic Group Model (GGM), in the sense that any AGM proof implies a GGM proof exists as well. This paper shows that this is not true via counter-example and suggests an updated AGM. It’s unclear if this actually affects any of the schemes (some of which are used in deployed blockchain protocols) which are proven secure under AGM.
***
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.
***
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.