Overcoming Cryptographic Impossibility Results Using Blockchains

We would like to point out that (unlike other works like [2, 3, 11, 39]) none of our applications require the underlying blockchain protocol to provide a sufficiently expressive scripting language. This suggests that our applications could be based on top of almost all existing blockchain protocols.

At first sight one might ask whether a strong assumption like extractable WE is necessary, or could it be relaxed. It turns out that, to construct one-time programs, it is sufficient and necessary to assume a slightly weaker primitive which we call one-time extractable WE. A one-time extractable WE is same as a standard extractable WE scheme, except the decryption algorithm could only be run once on each ciphertext. In other words, if we decrypt a one-time WE ciphertext with a bad witness the first time, then next time decryption (on that same ciphertext) will always fail even if we use a correct witness. Again this cannot be solely software based as then ciphertext could always be copied, and thus one-time decryption wouldn’t make sense. It is straightforward to verify in our OTP construction that we could instead use such a one-time extractable WE scheme. Additionally, anologous to construction of extractable WE from VBB obfuscation, we could show that a OTP already implies a one-time extractable WE, therefore our assumption of one-time extractable WE for constructing OTPs is both necessary and sufficient.

In cryptocurrencies, stake of any party simply corresponds to the amount of coins it controls.

Previous works also define chain growth as a desideratum, however in this work we will only focus on chain consistency and quality properties.

A fork is simply a private chain of blocks which significantly diverges from global blockchain in honest parties’ view.

For instance, most blockchain protocols (like Bitcoin, Ethereum etc.) already use ECDSA based signature schemes for which we could directly use ECIES-like integrated encryption schemes [47].

The local state should be considered as the entire blockchain (i.e., sequence of mined blocks along with metadata) in Bitcoin and other cryptocurrencies.

The sequence \(\varvec{\mathrm {B}}\) should be considered as the entire transaction history in Bitcoin and other cryptocurrencies, where the blocks are ordered in the sequence they were mined.

The validity predicate could be used to capture various fundamental properties. E.g., In Bitcoin and other cryptocurrencies, it could be used to check for double spending, correct mining etc.

We have overloaded the notation by using \(\mathsf {GetRecords}\) algorithm to take as input the view of a party instead of its state. This is still well defined since the state of any party is part of its view.

The rightmost (i.e., most recently added) block is called the head of the blockchain.

Note that a party could potentially mine more than one block in a sequence of \(\ell \) blocks.

As we mentioned before, most blockchain protocols (like Bitcoin, Ethereum etc.) use ECDSA based signature schemes for which we could directly use ECIES-like integrated encryption schemes [47]. Thus, our NIZKs are instantiable over existing blockchain protocols.

Observe that since \(\mathsf {HS}\) is an integrated encryption-signature scheme, therefore the public verification keys of all parties executing the blockchain protocol could be used for encryption as well.

Formally, the consistency should be checked as \(\varvec{\mathrm {B}}^{\lceil \kappa } \preceq \widetilde{\varvec{\mathrm {B}}}\) for an appropriate value of parameter \(\kappa \) (Definition 4), however for ease of exposition we avoid it.