Abstract: This paper presents Mir-BFT (or, simply, Mir), a robust Byzantine fault-tolerant (BFT) total order broadcast protocol aimed at maximizing throughput on wide-area networks (WANs), targeting permissioned and Proof-of-Stake permissionless blockchains. We show that Mir achieves unprecedented throughput on WANs without sacrificing latency, robustness to malicious behavior, or even performance in clusters. Our evaluation shows that Mir orders more than 60000 signed Bitcoin-sized transactions per second on a widely distributed 100 nodes, 1 Gbps WAN setup, while preventing a range of attacks including request duplication performance attacks. To achieve this, Mir relies on a novel protocol mechanism that allows a set of leaders to propose request batches independently, in parallel, while rotating the assignment of a partitioned request hash space to leaders. Several optimizations boost Mir throughput even further, including partial replication through a novel abstraction we call light total order (LTO) broadcast. Perhaps most importantly, Mir relies on proven BFT protocol constructs, which simplifies reasoning about Mir correctness. Specifically, Mir is a generalization of the celebrated and scrutinized PBFT protocol. In a nutshell, Mir follows PBFT "safety-wise'', with changes needed to accommodate novel features restricted to PBFT liveness.

Abstract: Bitcoin and similar blockchain systems have a limited transaction throughput because each transaction must be processed by all parties, on-chain. Payment channels relieve the blockchain by allowing parties to execute transactions off-chain while maintaining the on-chain security guarantees, i.e., no party can be cheated out of their funds. However, to maintain these guarantees all parties must follow blockchain updates ardently. To alleviate this issue, a channel party can hire a "watchtower" to periodically check the blockchain for fraud on its behalf. However, watchtowers will only do their job properly if there are financial incentives, fees, and punishments. There are known solutions, but these need complex smart contracts, and as such are not applicable to Bitcoin's simple script language. This raises the natural question of whether incentivized watchtowers are at all possible in a system like Bitcoin. In this work, we answer this question affirmatively, by introducing Cerberus channels, an extension of Lightning channels. Cerberus channels reward watchtowers while remaining secure against bribing and collusion; thus participants can safely go offline for an extended period of time. We show that Cerberus channels are correct, and provide a proof-of-concept implementation in the Bitcoin script language. Another shortcoming of current off-chain protocols (channels) is that their safety depends on the synchrony assumptions of the blockchain, which leaks to an adversary the exact amount of time needed to control the network for a successful attack. We introduce BRICK, the first incentive-compatible off-chain construction that remains secure under full asynchrony. The core idea is to incorporate the conflict resolution process within the off-chain channel by introducing a rational watchtower committee. Hence, if a party wants to close a channel unilaterally, it can only get the committee’s approval for the last valid state. BRICK provides sub-second latency during updates because it does not employ heavy-weight consensus, unless there is a dispute. Instead, BRICK uses consistent broadcast to announce updates, a light-weight abstraction that is powerful enough to preserve safety and liveness to honest parties. We formally define the properties our state channel construction should fulfill, and prove that BRICK satisfies them. We also design incentives for the committee such that honest and rational behavior align.

Abstract: Everlasting privacy protects electronic elections against future, powerful adversaries. It is motivated by a scenario, in which the weakening or breaking of cryptographic assumptions will allow a technologically advanced authoritarian regime to take advantage of the information hidden in past ballots to better control their subjects. Initially everlasting privacy was synonymous with information theoretic privacy, without considering the types of data that might be available in the future. More recent works provided variations of the concept, limiting the view of the adversary only to publicly available data. However their definitions were presented in the symbolic setting. In this paper, we refine these models by taking into account that a future powerful adversary might take advantage of data obtained from corrupted actors in the present, external or even internal to the election system. We formally express our different adversarial models in the first ever game based definitions for everlasting privacy and discuss their implications.

Joint work with Aris Pagourtzis and Alexandros Zacharakis

Abstract: Distributed ledgers based on Proof-of-Work (PoW) are typically most vulnerable when mining participation is low. During these periods an attacker can mount devastating attacks, such as double spending or censorship of transactions. To mitigate such attacks, our core idea is to employ an external set of parties that securely run an assisting service, which guarantees the ledger's properties when the invested hashing power is low. We realize this assisting service in two ways, via checkpointing and timestamping, and show that a ledger which employs either is secure with high probability. Our design offers both consistency and liveness guarantees, even under adversarial mining majorities. Our liveness analysis also identifies a previously undocumented attack, namely front-running, which enables Denial-of-Service against existing checkpointed ledgers. We evaluate our mechanism on Ethereum Classic, a blockchain which recently suffered a 51% attack, and build a federated fault-tolerant distributed checkpointing service. Finally, we prove the security of our timestamping mechanism, build a fully decentralized timestamping solution, and evaluate its performance using Bitcoin and Ethereum.

Abstract: The process of mining blocks in decentralized ledger protocols traditionally requires each node to maintain state, in the form of a chain, growing linearly in time. In this paper, we present a mining protocol which requires state growing only logarithmically in time. The state represents a compressed form of the chain and provides equivalent security to the full mining protocol. The state is updated as new blocks are mined, but remains succinct, and is sufficient to correctly convince participants synchronizing from genesis. We put forth a mechanism with which existing full nodes can compress their previous linear state into our compressed logarithmic form.

Abstract: Cryptographic accumulators are an important building block for a variety of applications where it is important to represent a set of elements in a compact format while still being able to provide proofs of (non)membership. In this work we give a number of accumulator constructions for the bilinear pairing setting. We utilize the approach of Baldimtsi et al 2017 who proposed building accumulators in a modular way and we present optimally efficient (in terms of communication cost) dynamic positive accumulators in the pairing setting. Additionally, again utilizing modular building approaches, we present a universal dynamic accumulator with efficient non-membership proofs and we show how this can also give rise to more efficient ZK accumulators.

Abstract: E-voting can solve many problems that traditional conventional voting systems cannot, in a secure mathematically proven way. The DEMOS e-voting system is one of the many examples of modern state of the art e-voting systems. The DEMOS e-voting system has many desirable properties and uses many novel techniques. However, DEMOS has some problems that need to be solved, so as to extend its usability. In this presentation, we explain how DEMOS works and what makes it so special. Moreover, we extend DEMOS usability by providing a new way of conducting enhanced voting schemes in the context of DEMOS. This is achieved by changing the way that the ballots are encoded and by providing a new zero knowledge proof approach. Furthermore, our work is supported by the necessary security proofs, while a first practical implementation is also provided. We also provide a novel theoretical proof of concept, for far more complex voting systems like STV, which might be the first of its kind for homomorphic systems. Finally, we provide a new zero knowledge proof of a shuffle argument, which can be used for applications outside of the DEMOS context.

Abstract: A watermarking scheme for a public-key cryptographic functionality enables the embedding of a mark in the instance of the secret-key algorithm such that the functionality of the original scheme is maintained, while it is infeasible for an adversary to remove the mark (unremovability) or mark a fresh object without the marking key (unforgeability). A number of works have appeared in the literature proposing different definitional frameworks and schemes secure under a wide range of assumptions. This talk will focus on presenting the results appeared in the paper "Watermarking Public-key Cryptographic functionalities and implementations" (ISC '17). In this work, we have proposed a meaningful relaxation of the watermarking model and gave constructions for watermarking public key encryption that achieve both unremovability and unforgeability properties under minimal hardness assumptions. In addition, we will present a new construction for watermarking public key encryption functionality which improves upon our previous results.