Cryptology ePrint Archive: Report 2017/935

Overcoming Cryptographic Impossibility Results using Blockchains

Rishab Goyal and Vipul Goyal

Abstract: Blockchain technology has the potential to disrupt how cryptography is done. In this work, we propose to view blockchains as an "enabler", much like indistinguishability obfuscation (Barak et al., CRYPTO 2001, Garg et al., FOCS 2013, and Sahai and Waters, STOC 2014) or one-way functions, for building a variety of cryptographic systems. Our contributions in this work are as follows:

1. A Framework for Proof-of-Stake based Blockchains: We provide an abstract framework for formally analyzing and defining useful security properties for Proof-of-Stake (POS) based blockchain protocols. Interestingly, for some of our applications, POS based protocols are more suitable. We believe our framework and assumptions would be useful in building applications on top of POS based blockchain protocols even in the future.

2. Blockchains as an Alternative to Trusted Setup Assumptions in Cryptography: A trusted setup, such as a common reference string (CRS) has been used to realize numerous systems in cryptography. The paragon example of a primitive requiring trusted setup is a non-interactive zero-knowledge (NIZK) system. We show that already existing blockchains systems including Bitcoin, Ethereum etc. can be used as a foundation (instead of a CRS) to realize NIZK systems.

The novel aspect of our work is that it allows for utilizing an already existing (and widely trusted) setup rather than proposing a new one. Our construction does not require any additional functionality from the miners over the already existing ones, nor do we need to modify the underlying blockchain protocol. If an adversary can violate the security of our NIZK, it could potentially also take over billions of dollars worth of coins in the Bitcoin, Ethereum or any such cryptocurrency!

We believe that such a "trusted setup" represents significant progress over using CRS published by a central trusted party. Indeed, NIZKs could further serve as a foundation for a variety of other cryptographic applications such as round efficient secure computation (Katz and Ostrovsky, CRYPTO 2004 and Horvitz and Katz, CRYPTO 2007).

3. One-time programs and pay-per use programs: Goldwasser et al. (CRYPTO 2008) introduced the notion of one time program and presented a construction using tamper-proof hardware. As noted by Goldwasser et al., clearly a one-time program cannot be solely software based, as software can always be copied and run again. While there have been a number of follow up works (Goyal et al., TCC 2010, Bellare et al., ASIACRYPT 2012, and Applebaum et al., SIAM Journal on Computing 2015), there are indeed no known constructions of one-time programs which do not rely on self destructing tamper-proof hardware (even if one uses trusted setup or random oracles). Somewhat surprisingly, we show that it is possible to base one-time programs on POS based blockchain systems without relying on trusted hardware. Our ideas do not seem to translate over to Proof-of-Work (POW) based blockchains.

We also introduce the notion of pay-per-use programs which is simply a contract between two parties --- service provider and customer. A service provider supplies a program such that if the customer transfers a specific amount of coins to the provider, it can evaluate the program on any input of its choice once, even if the provider is offline. This is naturally useful in a subscription based model where your payment is based on your usage.

Category / Keywords: Blockchain, Bitcoin, Ethereum, Proof-of-Stake, Proof-of-Work, NIZK, One-Time Programs

Original Publication (in the same form): IACR-TCC-2017

Date: received 25 Sep 2017, last revised 25 Sep 2017

Contact author: goyal at utexas edu

Available format(s): PDF | BibTeX Citation

Version: 20170925:182206 (All versions of this report)

Short URL: ia.cr/2017/935

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]