In this message I offer a brief start of a proposal for improving the scalability, flexibility, privacy, and fungibility of Bitcoin. The idea is based on bleeding-edge cryptography and would require a soft-fork to deploy—so it is not something which could be implemented immediately, but I believe it would be a useful area for further research.
In
SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge (referred to as SCIP below), Eli Ben-Sasson et al. describe their work on highly efficient non-interactive proofs with zero-knowledge for the faithful execution of programs written in C. Eli also
presented at the Bitcoin conference.
The short layman's explanation of their work is that they've constructed a system where someone can run an arbitrary program inside a special environment and then publish a very compact and quickly-checkable proof which will convince anyone that 1) they ran the program faithfully (e.g., without modification or tampering) and 2) that the program "accepted" (e.g., exited with return true;) with a given set of public inputs and (optionally) additional non-public inputs. Because their system provides computational zero knowledge, the program's execution can also depend on any non-public inputs and the validator learns nothing about them beyond the fact that the program accepted.
The mathematics behind this are highly dense—starting with the
surprising result from over twenty years ago that all programs can be converted into interactive proofs, they apply many layers of techniques to build a concrete system with performance that could actually be used, rather than just a proof that proofs of programs are possible.
I've proposed some interesting ideas on how to use this kind of technology with Bitcoin which don't require any changes to Bitcoin itself
elsewhere. But if you add the technology directly to Bitcoin some more interesting things become possible.
One of the obvious applications of this idea is that it could replace
script in Bitcoin. Instead of embedding the rules that govern an output inside the blockchain, you'd instead embed a proof that the rules were followed. Instead of everyone checking that a transaction was permitted to be spent, they'd instead check that you checked.
This is itself interesting, as it would make much more powerful scripts possible without burdening the network with their execution, but improvements to script aren't terribly exciting when the existing system is so far mostly unused. Additionally, the verification of SCIP proofs is somewhat slow compared to ECDSA (on the order of, say, several hundred times slower), and although it scales excellently most transactions are very simple with only a single hash and ECDSA operation.
Here I suggest one very interesting way this functionality could be used.
Let's imagine that my friends and I agree on a set of rules for a verifiable off-chain transaction system. By "verifiable", I mean that if its users record a transcript of the activity for a single coin, they could show the transcript to a third party, and the third party would be convinced that the system is behaving correctly and would know who the ultimate owner of the coin was.
Here are two example systems which would meet that criteria:
Anti-replay oracle basedAlice has a digital coin: coin={Value, Alice's pubkey, transcript of the coin's history}, and wants to assign it to Bob.
Bob tells Alice Hash(bob's pubkey)=HB.
Alice computes Hash(coin)==HC, and also Sign(HB)==SHB.
Alice contacts a trusted anti-replay oracle, telling it {HC,SHB}.
The oracle returns Sign({HC,SHB}) if and only if it has never signed something which began with HC before.
Alice passes this information on to Bob, along with the coin. Bob checks the coin's history and is satisfied that he has a valid coin which has not been double-spent.
This can be continued on and on, passing a coin from party to party, producing an ever-growing transcript. It can be trivially extended by using M of N anti-replay oracles, or other similar improvements. The anti-replay oracles this uses are trusted to not replay, but since they only deal with hashes they learn nothing about the transactions (or even that they're being used for a currency-like use—it might just be timestamping for all the oracle can tell). Such an oracle could be on trusted hardware, fidelity bonded, secured by a bounty txout that you can redeem if and only if you can publish a proof showing a replay, etc.
Blockchain basedAlice has a bitcoin which is represented by a colored coin in some other specific blockchain, perhaps a geographic-specific blockchain.
Alice passes it to Bob by transacting in the normal way.
Bob can form the verifiable transcript by grabbing every transaction along the colored coin's path along with the SPV fragments connecting them to the chain and some additional blockchain headers to show the transactions are adequately buried.
(I provided two examples here to make a point that the idea is completely general. Any other system with the verifiable property, E.g. OpenTransactions, complicated ones involving voting by all participants, or even trivial ones that doesn't have double spending prevention, could be used. Though they'd work best if constructed for very efficient validation.)
The idea I'm calling
CoinWitness is this:
You write down a small program which verifies the faithfulness of one of these transcripts for your chosen verifiable off-chain system. The program requires that the last transaction in the transcript is special in that it pays to a Bitcoin scrippubkey/p2sh. The same address must also be provided as a public input to the program. We call this program a "witness" because it will witness the transcript and accept if and only if the transcript is valid.
You then use the SCIP proof system to convert the program into a verifying key. When someone wants to create a Bitcoin in an off-chain system, they pay that coin to the hash of that verifying key. People then transact in the off-chain system as they wish. To be confident that the system works faithfully they could repeat the computationally-expensive verifying key generation process to confirm that it corresponds to the transaction rules they are expecting.
When a user of one of these coins wants to exit the system (to compact its history, to move to another system, to spend plain Bitcoins, or for any other reason), they form a final transaction paying to a Bitcoin address, and run the witness on their transcript under SCIP and produce a proof. They create a Bitcoin transaction redeeming the coin providing the proof in their script (but not the transcript, thats kept private), and the Bitcoin network validates the proof and the transaction output. The public learns nothing about the intermediate transactions, improving fungibility, but unlike other ideas which improve fungibility this idea has the potential to both improve Bitcoin's scalability and securely integrate new and innovative alternative transaction methods and expand Bitcoin's zero-trust nature to more types of transactions.
Open challenges:
This depends on new cryptographic techniques which may have security weaknesses and may have much room for performance improvement. Use of it requires adding the validation software to the Bitcoin network, which then fixes a particular proof format in stone.
The SCIP proof validation is slow by our standard. In the paper they give an example from their implementation on a 2.4 GHz host where validation of a proof (which is only 2576 bits long for 80-bit security) on a small public input (which is the case for CoinWitness) takes 100ms. This is fast enough that it may actually be viable without further optimization considering the potential for compression of multiple transactions into one.
SCIP proof construction is enormously slow by our standards. In an example given in their paper for a 100-instruction program which executes for 11001 cycles, proof generation takes 155 minutes. Proof time is basically linear with the number of operations, so bringing a coin with a long transcript back into the chain may be computationally prohibitive. However, since this is done off-chain, it at least puts the work with an interested party instead of externalizing it on the whole Bitcoin userbase. (And there likely is a lot of room to improve the performance with software engineering, in particular, the problem is very parallelizable)
The SCIP keys must have an upper bound on the number of operations performed by the program baked into them. This results in a maximum transcript length which must be committed to in advance.
I believe all these issues are surmountable, in time, barring any really exciting cryptographic breaks in the approach.
This CoinWitness idea is something of a less ambitious example of what Eli suggested in his talk—effectively running blockchain validation under SCIP to produce UTXO checkpoints that have cryptographic proof of their correctness. But instead of validating all transactions from a public blockchain, here I suggest validating small sequences of
private transactions to avoid ever making them public at all and, in doing so, improve the scalability, flexibility, privacy, and fungibility of Bitcoin. (And, in fact, this idea may in fact be trivially obvious to those working on the SCIP tools, but I expect it will blow some minds here).
