Non-Interactive Proofs of Proof-of-Work

December 2017 | IOHK – Aggelos Kiayias, Andrew Miller, Dionysis Zindros

Blockchain protocols such as Bitcoin provide decentralized consensus mechanisms based on proof-of-work (PoW). In this work we introduce and instantiate a new primitive for blockchain protocols called Non-Interactive-Proofs-of-Proof-of-Work (NIPoPoWs) which can be adapted into existing PoW-based cryptocurrencies. Unlike a traditional blockchain client which must verify the entire linearly-growing chain of PoWs, clients based on NIPoPoWs can verify a certain blockchain property requiring resources only logarithmic in the length of the blockchain. NIPoPoWs solve two important open questions for PoW based consensus protocols: The problem of constructing efficient transaction verification (SPV) clients and the problem of constructing efficient sidechain proofs. We provide a formal model for NIPoPoWs and two constructions for blockchain properties that we prove secure and are of interest with respect to the above applications. We also provide simulations and experimental data to measure the concrete communication efficiency and security of our construction. We also present an attack against the only previously known (interactive) PoPoW protocol that showcases the difficulty of designing such protocols. Finally, we provide two ways that our NIPoPoWs can be adopted by existing blockchain protocols, first via a soft fork, and second via a new update mechanism that we term a “velvet fork” that enables harnessing some of the performance benefits of NIPoPoWs even with a minority upgrade.


Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain

November 2017 | Bernardo David, Peter Gazi, Aggelos Kiayias, Alexander Russell

We present “Ouroboros Praos”, a proof-of-stake blockchain protocol that, for the first time, provides security against fully-adaptive corruption in the semi-synchronous setting: Specifically, the adversary can corrupt any participant of a dynamically evolving population of stakeholders at any moment as long the stakeholder distribution maintains an honest majority of stake; furthermore, the protocol tolerates an adversarially-controlled message delivery delay unknown to protocol participants.

To achieve these guarantees we formalize and realize in the universal composition setting a suitable form of forward secure digital signatures and a new type of verifiable random function that maintains unpredictability under malicious key generation. Our security proof develops a general combinatorial framework for the analysis of semi-synchronous blockchains that may be of independent interest. We prove our protocol secure under standard cryptographic assumptions in the random oracle model.


Kaleidoscope: An Efficient Poker Protocol with Payment Distribution and Penalty Enforcement

September 2017 | Bernardo David, Rafael Dowsley, Mario Larangeira

The research on secure poker protocols without trusted intermediaries has a long history that dates back to modern cryptography’s infancy. Two main challenges towards bringing it into real-life are enforcing the distribution of the rewards, and penalizing misbehaving/aborting parties. Using recent advances of cryptocurrencies and blockchain technologies, Kumaresan et al. (CCS 2015) and Bentov et al. (ASIACRYPT 2017) were able to address those problems. While they made significant progress towards meeting the real-life deployment requirements, the protocols still lack either efficiency or a formal security proof in a strong model. Specifically, the former relies on Bitcoin and simple contracts, but is not very efficient as it needs numerous interactions with the cryptocurrency network as well as a lot of collateral. The latter improves by using stateful contracts and off-chain execution: it shows a solution based on general multiparty computation that has a security proof in a strong model, but is not very efficient. Alternatively, it proposes to use tailor-made poker protocols as a building block to improve the efficiency. However, a security proof is unfortunately still missing for the latter case: the security properties the tailor-made protocol would need to meet were not even specified, let alone proven to be met by a given protocol. Our solution closes this undesirable gap as it concurrently: (1) enforces the rewards’ distribution; (2) enforces penalties on misbehaving parties; (3) has efficiency comparable to the tailor-made protocols; (4) has a security proof in a simulation-based model of security. Combining techniques from the above works, from tailor-made poker protocols and from efficient zero-knowledge proofs for shuffles, and performing optimizations, we obtain a solution that satisfies all four desired criteria and does not incur a big burden on the blockchain.


Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

August 2017 | Aggelos Kiayias, Alexander Russell, Bernardo David, Roman Oliynykov

We present “Ouroboros”, the first blockchain protocol based on proof of stake with rigorous security guarantees. We establish security properties for the protocol comparable to those achieved by the bitcoin blockchain protocol. As the protocol provides a “proof of stake” blockchain discipline, it offers qualitative efficiency advantages over blockchains based on proof of physical resources (e.g., proof of work). We also present a novel reward mechanism for incentivizing Proof of Stake protocols and we prove that, given this mechanism, honest behavior is an approximate Nash equilibrium, thus neutralizing attacks such as selfish mining. We also present initial evidence of the practicality of our protocol in real world settings by providing experimental results on transaction confirmation and processing.


An Ontology for Smart Contracts

July 2017 | Darryl McAdams

This paper introduces a basic ontology that attempts to capture the essential features of many smart contracts, in order to aid in formal reasoning about their behavior. Section II gives a general overview of the proposed ontology, and Section III gives analyses of a number of interesting smart contracts from the literature, through the lens of this ontology. The proposals here are not intended to be the One True Ontology, but rather a useful ontology. A well-designed blockchain should be able to support arbitrary such ontologies.


SCRAPE: Scalable Randomness Attested by Public Entities

June 2017 | Bernardo David, Ignacio Cascudo

Uniform randomness beacons whose output can be publicly attested to be unbiased are required in several cryptographic protocols. A common approach to building such beacons is having a number parties run a coin tossing protocol with guaranteed output delivery (so that adversaries cannot simply keep honest parties from obtaining randomness, consequently halting protocols that rely on it). However, current constructions face serious scalability issues due to high computational and communication overheads. We present a coin tossing protocol for an honest majority that allows for any entity to verify that an output was honestly generated by observing publicly available information (even after the execution is complete), while achieving both guaranteed output delivery and scalability. The main building block of our construction is the first Publicly Verifiable Secret Sharing scheme for threshold access structures that requires only O(n) exponentiations. Previous schemes required O(nt) exponentiations (where t is the threshold) from each of the parties involved, making them unfit for scalable distributed randomness generation, which requires t=n/2 and thus O(n^2) exponentiations.


TwinsCoin: A Cryptocurrency via Proof-of-Work and Proof-of-Stake

March 2017 | Alexander Chepurnoy, Tuyet Duong, Lei Fan, Hong-Sheng Zhou

We design and implement TwinsCoin, the first cryptocurrency based on a provably secure and scalable public blockchain design using both proof-of-work and proof-of-stake mechanisms. Different from the proof-of-work based Bitcoin, our construction uses two types of resources, computing power and coins (i.e., stake). The blockchain in our system is more robust than that in a pure proof-of-work based system; even if the adversary controls the majority of mining power, we can still have the chance to secure the system by relying on honest stake. In contrast, Bitcoin blockchain will be insecure if the adversary controls more than 50% of mining power.

Our design follows a recent provably secure proof-of-work/proof-of-stake hybrid blockchain by Duong et al. (ePrint 2016). In order to make our construction practical, we enhance Duong et al.’s design. In particular, we introduce a new strategy for difficulty adjustment in the hybrid blockchain and provide an analysis of it. We also show how to construct a light client for proof-of-stake cryptocurrencies and evaluate the proposal practically.

We implement our new design. Our implementation uses a recent modular development framework for blockchains, called Scorex. It allows us to change only certain parts of an application leaving other codebase intact. In addition to the blockchain implementation, a testnet is deployed. Source code is publicly available.


Four Blockchain Use Cases for Banks

February 2017 | FinTech Network

This whitepaper sets out four potential use cases for banks including reduction of fraud, KYC, trading platforms and concentrating on the last use case of payments, in considering the possibility of utilising blockchain technology in banking.


Tech Trends 2017 – The Australian Cut – The Kinetic Enterprise

2017 | Deliotte

Blink and you could miss it. The speed at which technology advances and upgrades can seem overwhelming. In the kinetic enterprise, the only constant is change. The 2017 report outlines how companies presently must sift through the promotional noise and hyperbole surrounding emerging technologies to find those solutions offering real potential. To realise that potential, they should become ‘kinetic’ organisations—companies with the dexterity and vision required to thrive amid ongoing technology-fueled disruption.

While the report identifies key trends that will likely revolutionise enterprise technology in the next 18-24 months, the exponentials chapter looks even farther into the future, describing four key areas that blend science and applied technologies.


Back to University Archives