To make things concrete let's look at an example. Computational state in a block chain contract is typically stored in a Merkle hash trie. Let's say that the data stored is a key, and the holder of the key is allowed to spend the coins bound to the contract. The _computation_ is to check that the key is contained within the Merkel trie, then check signature of the key and the spend. However with some cool zero-knowledge crypto magic, you don't even have to reveal the Merkle inclusion proof, nor even the key itself. All you have to do is provide a zero-knowledge transcript which verifies that the computation of the contract (Merkle inclusion proof and signature check) validates. This is, essentially, how zerocash works.
This result generalizes. For whatever computation you want to perform in a contract, the contract can be rewritten to instead just validate a transcript of a successful execution of that computation. This isn't just academic either. All NP problems have transcripts that are validatable in polynomial time. A derivative of this result is that while you might need Turing completeness to express the logic of a smart contract, you do NOT need Turing completeness to validate its transcript. As a trivial example, a smart contract that involves computing a hash preimage by brute force in a tight loop, could be replaced with a contract that merely takes a string and checks that it hashes to the desired value.
Sure, but are they provable in polynomial time?
Proof generation is much more expensive than just running through the original computation through standard means.
> However with some cool zero-knowledge crypto magic, you don't even have to reveal the Merkle inclusion proof, nor even the key itself.
I hate that the exact way that ZK systems work is always omitted from any discussion of the subject. It is very complicated, which explains why no one like to (or is even able to) get into the specifics, but somehow this also leads to handwavy assertion that all we need to do to avoid all that expensive and duplicative computation is to sprinkle in some zero-knowledge proofs.
Due to performance limitations, for all intents and purposes ZK tech is impractical to the point of being infeasible for truly decentralized blockchains with turing-complete smart contract capabilities. It works for more specialized purposes, but it is not a currently solution to the "duplicative computation" problem.
It doesn’t matter, does it? That computation happens off-chain.
As an actual example, there are contracts locked to providing a collision proof for various hash functions. The one for SHA1 was claimed a few years ago when Google generated the first SHA-1 collision. That represented a lot of work on Google’s behalf, but was trivial for bitcoin nodes to validate.
> Due to performance limitations, for all intents and purposes ZK tech is impractical to the point of being infeasible for truly decentralized blockchains with turing-complete smart contract capabilities. It works for more specialized purposes, but it is not a currently solution to the "duplicative computation" problem.
You misunderstand me. I’m not suggesting that such a general zkp system be used, but rather offering it as a theoretical point.
In practice you make a specialized zk proof for whatever you are trying to do. And despite the hype, the practical use cases for Turing complete smart contracts are quite small and limited in scope. If you have a smart contract with real world applicability that can’t be reduced down to a handful of easily checked signatures and if-else clauses (or something of similar complexity), I’d like to see it. I know of scant few examples, and this is my field of expertise.
Look into Mina or Zcash to better understand what I mean. Off-chain clients (eg, wallets in Zcash) keep the application state, and the state committed to the chain is just the proof that the application state is following an agreed-upon state transition function.
Relying on hashing, computation proofs, etc are ways to asymmetrically enjoy the benefits of global coordination without requiring all nodes in the network to run the code. Instead, they just verify the receipts of off-chain agents who ran the code.