‘Accountable liveness’: New paper alert
Our new paper explores when and how adversarial nodes can be punished if they stall transaction confirmation in blockchains, showing how and to what extent accountability guarantees are achievable for liveness. Beyond these theoretical contributions, liveness accountability also has practical implications. The paper provides rigorous foundations for liveness-accountability heuristics such as the “inactivity leaks” employed in Ethereum.
Background: Crypto-economic security
Traditional consensus security demands the following two properties to hold whenever there aren’t too many adversarial nodes:
- Safety: No two honest nodes ever disagree on the confirmed transactions.
- Liveness: Transactions eventually get confirmed by every honest node.
However, if the fraction of adversary nodes exceeds the protocol’s resilience, the protocol’s security properties no longer hold. What then? If either safety or liveness is violated, can we at least determine which nodes caused it? Identifying adversary nodes allows the system to confiscate their stake as a form of punishment, which incentivizes honest behavior and allows the system to compensate damages caused by the violations. Such aims are often referred to as crypto-economic security.
Researchers have recently introduced the notion of accountable safety, a strengthening of safety. It stipulates (in addition to the aforementioned traditional safety property) that if any two nodes at any two points in time ever have inconsistent confirmed transactions (i.e., a safety violation occurs), then a substantial fraction of nodes can be identified as having provably violated the protocol.
Our contribution: Liveness accountability
Our paper extends the idea of accountability to liveness, so that whenever transaction confirmation stalls, a substantial fraction of nodes can be identified as having provably violated the protocol. We show how PBFT-style consensus protocols that are safe and live under partial synchrony up to 1/3 adversary nodes (e.g., the Tendermint protocol) can be equipped with liveness accountability if a majority of nodes is honest and the network is “more often synchronous than asynchronous” (which we define precisely in the paper).
This guarantee thus comes with two compromises: one on network timing, and the second on the number of adversarial nodes. We show that these compromises are unavoidable:
- While safety accountability works irrespective of network timing assumptions, for liveness accountability, no protocol can provide it, if the network is “more often asynchronous than synchronous.”
- For safety, the adversary cannot escape accountability, even if almost all nodes are adversarial. But for liveness, we show that accountability is impossible if the adversary controls a majority of the nodes.
These provable limitations vindicate the intuition that, because liveness violations involve the unexpected absence of messages (like votes) rather than the unexpected presence of messages (like equivocating votes), accountability is more difficult for liveness than for safety.
Beyond these contributions to theory, the work serves as a starting point for automating responses to liveness attacks in blockchains. Ethereum, notably, already implements an automated response to major liveness issues. Its consensus protocol, Gasper, addresses liveness violations through a heuristic mechanism called “inactivity leaks.” The methods described in the paper enable the detection and formal identification of adversarial nodes through certificates of guilt. This provides a complementary and more general approach, akin to Ethereum’s inactivity leaks but with precise and stronger accountability guarantees.
Go deeper
Tim Roughgarden’s explainer video
Joachim Neu’s introductory tweets
***
Andrew Lewis-Pye is a Professor at the London School of Economics. He has worked in various fields, including mathematical logic, network science, population genetics, and blockchain. For the last four years his research focus has been on blockchain, where his principal interests are in consensus protocols and tokenomics. You can find him on Twitter @AndrewLewisPye .
Joachim Neu is a postdoc Research Associate at a16z Crypto Research. Previously, he earned a PhD at Stanford, advised by David Tse. His current research focus is blockchain-era consensus and decentralized-systems security. His broader interests include distributed computing and systems, applied cryptography, and networking and communications.
Tim Roughgarden is a Professor of Computer Science and a member of the Data Science Institute at Columbia University, and Head of Research at a16z crypto.
Luca Zanolini serves as a Research Scientist at the Ethereum Foundation and is actively engaged in the design and analysis of both short term and long term enhancements to Ethereum’s consensus mechanism. Currently, he focuses on characterising and devising dynamically-available consensus protocols, and exploring single-slot finality for Ethereum.
***
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 current or 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/.
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.