Although blockchains aim for immutability as their core feature, several instances have exposed the harms with perfect immutability. The permanence of illicit content inserted in Bitcoin poses a challenge to law enforcement agencies like Interpol, and millions of dollars are lost in buggy smart contracts in Ethereum. A line of research then spawned on Redactable blockchains with the aim of solving the problem of redacting illicit contents from both permissioned and permissionless blockchains. However, all the existing proposals follow the build-new-chain approach for redactions, and cannot be integrated with existing systems like Bitcoin and Ethereum.
We present Reparo, a generic protocol that acts as a publicly verifiable layer on top of any blockchain to perform repairs, ranging from fixing buggy contracts to removing illicit contents from the chain. Reparo facilitates additional functionalities for blockchains while maintaining the same provable security guarantee; thus, Reparo can be integrated with existing blockchains and start performing repairs on the pre-existent data. Any system user may propose a repair and a deliberation process ensues resulting in a decision that complies with the repair policy of the chain and is publicly verifiable.
Our Reparo layer can be easily tailored to different consensus requirements, does not require heavy cryptographic machinery and can, therefore, be efficiently instantiated in any permission-ed or -less setting. We demonstrate it by giving efficient instantiations of Reparo on top of Ethereum (with PoS and PoW), Bitcoin, and Cardano. Moreover, we evaluate Reparo with Ethereum mainnet and show that the cost of fixing several prominent smart contract bugs is almost negligible. For instance, the cost of repairing the prominent Parity Multisig wallet bug with Reparo is as low as 0.000000018% of the Ethers that can be retrieved after the fix.
Abstract: Existing Nakamoto-style blockchains (NSBs) rely on some sort of synchrony assumption to offer any type of safety guarantees. A basic requirement is that when a party produces a new block, then all previously produced blocks should be known to that party, as otherwise the new block might not append the current head of the chain, creating a fork. In practice, however, the network delay for parties to receive messages is not a known constant, but rather varies over time. The consequence is that the parameters of the blockchain need to be set such that the time between the generation of two blocks is typically larger than the network delay (e.g.,minutes in Bitcoin) to guarantee security even under bad network conditions. This results in lost efficiency for two reasons: (1) Since blocks are produced less often, there is low throughput. Furthermore, (2) blocks can only be considered final, and thus the transactions inside confirmed, once they are extended by sufficiently many other blocks, which incurs a waiting time that is a multiple of 10 minutes. This is true even if the actual network delay is only second, meaning that NSBs are slow even under good network conditions. We show how the Bitcoin protocol can be adjusted such that we preserve Bitcoin’s security guarantees in the worst case, and in addition, our protocol can produce blocks arbitrarily fast and achieve optimistic responsiveness. The latter means that in periods without corruption, the confirmation time only depends on the (unknown) actual network delay instead of the known upper bound. Technically, we propose an approach where blocks are treated differently in the “longest chain rule”. The crucial parameter of our protocol is a weight function assigning different weight to blocks according to their hash value. We present a framework for analyzing different weight functions, in which we prove all statements at the appropriate level of abstraction. This allows us to quickly derive protocol guarantees for different weight functions. We exemplify the usefulness of our framework by capturing the classical Bitcoin protocol as well as exponentially growing functions as special cases, where the latter provide the above mentioned guarantees, including optimistic responsivene
Abstract: Proactive security is the notion of defending a distributed system against an attacker who compromises different devices through its lifetime, but no more than a threshold number of them at any given time. The emergence of threshold wallets for more secure cryptocurrency custody warrants an efficient proactivization protocol tailored to this setting. While many proactivization protocols have been devised and studied in the literature, none of them have communication patterns ideal for threshold wallets. In particular a (t,n) threshold wallet is designed to have t parties jointly sign a transaction (of which only one may be honest) whereas even the best current proactivization protocols require at least an additional thonest parties to come online simultaneously to refresh the system.
In this work we formulate the notion of refresh with offline devices, where any tparties (no honest majority) may proactivize the system at any time and the remaining n−t offline parties can non-interactively “catch up” at their leisure. However due to the inherent unfairness of dishonest majority MPC, many subtle issues arise in realizing this pattern. We discuss these challenges, yet give a highly efficient protocol to upgrade a number of standard (2,n) threshold signature schemes to proactive security with offline refresh. Our approach involves a threshold signature internal to the system itself, carefully interleaved with the larger threshold signing. We design our protocols so that they can augment existing implementations of threshold wallets for immediate use– we show that proactivization does not have to interfere with their native mode of operation.
Our proactivization technique is compatible with Schnorr, EdDSA, and even sophisticated ECDSA protocols, while requiring no extra assumptions. By implementation we show that proactivizing two different recent (2,n) ECDSA protocols incurs only 14% and 24% computational overhead respectively, less than 200 bytes, and no extra round of communication.
Category / Keywords: cryptographic protocols / threshold cryptography; key management; digital signatures; oblivious transfer
Abstract: Most existing blockchains either rely on a Nakamoto-style of consensus, where the chain can fork and produce rollbacks, or on a committee-based Byzantine fault tolerant (CBFT) consensus, where no rollbacks are possible. While the latter ones offer better consistency, the former can be more efficient, tolerate more corruptions, and offer better availability during bad network conditions. To achieve the best of both worlds, we initiate the formal study of finality layers. Such a finality layer can be combined with a Nakamoto-style blockchain and periodically declare blocks as final, preventing rollbacks beyond final blocks.
As conceptual contributions, we identify the following properties to be crucial for a finality layer: finalized blocks form a chain (chain-forming), all parties agree on the finalized blocks (agreement), the last finalized block does not fall too far behind the last block in the underlying blockchain (updated), and all finalized blocks at some point have been on the chain adopted by at least k honest parties (k-support).
As technical contributions, we propose two variants of a finality layer protocol. The first variant satisfies all of the aforementioned requirements (with k=1) when combined with an arbitrary blockchain that satisfies the usual common-prefix, chain-growth, and chain-quality properties. The second one needs an additional, mild assumption on the underlying blockchain, but is more efficient and satisfies k=n/3-support. We prove both of them secure in the setting with t<n/3 Byzantine parties and a partially synchronous network. We finally show that t<n/3 is optimal for partially synchronous finality layers.
Category / Keywords: cryptographic protocols / blockchain, finality, Byzantine agreement