Can ZKSnarks be implemented on the Ethereum ecosystem?

Question

Since Zcash seems to have it's ZKSnarks implementation finished (or almost at least).

And versions of JPMorgan's Quorum had appeared with ZKsnarks implementations included see: https://www.coindesk.com/jpmorgan-integrates-zcash-privacy-tech-enterprise-blockchain/

We all know that the verification time of the Snarks its independent from the circuit (not of the number of gates, it's true) but anyway, the verifications of the nodes will be so much faster than they are now because the computations wouldn't be executed anymore.

The possibilities of zkSNARKs are impressive, you can verify the correctness of computations without having to execute them and you will not even learn what was executed – just that it was done correctly.

As it is said on the Ethereum Blog (maybe with a lower "mathematical/theoretical level"

I know about the LibSnark.cpp implementation and other ones, but I'm not talking to put all of this on a SmartContract, I'm talking about the whole blockchain mechanisms adopting the Snarks structures in order to work with full encrypted blocks and transactions, and a verification process of the nodes implemented also with ZkSnarks verifying.

Will be possible to implement those SNARKS at the protocol level to verify the entire Ethereum Blockchain? If it isn't, why?

Thanks.

Answer 1

Disclaimer : I am not a cryptographer nor a mathematician nor a low level software engineer. Please correct me if any information provided below is incorrect.

Very short answer: Yes

Short answer: Possible, but very difficult today.

Longer answer: The main challenge with Ethereum is that since you have a programmable blockchain, you effectively need to implement a virtual machine (e.g. EVM) as an arithmetic circuit, which is possible, but not trivial at all today. Having a circuit specialized for a specific function (e.g. transferring assets) is much simpler, hence why Coda protocol starts with a non-programmable blockchain.

This considered, the question now becomes What do we need to use recursive S(T|N)ARKs to prove the validity of the entire Ethereum chain?

You need to build a circuit that implements a Random Access Machine (RAM), i.e. a CPU that has access to memory registers. Fortunately, such a design was proposed in a paper called Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. Mike Hearn published a fantastic medium post in 2016 describing on a higher level what this small zk-snark von Neumann machine is. Overall, this is still a very complicated circuit where it's very expensive to execute code. However, thanks for the fact that SNARKs proof are parallelizable (e.g. see DIZK), there is a lot of room for parallel proof generation optimization, both between machines and within hardware components like GPUs or SNARK ASICs (not aware of any in existence as of yet).

Once we have a circuit that can run arbitrary computations, we will need languages that compile down to this virtual machine code. At that point, I think we can verify the entire Ethereum blockchain history succinctly, allowing "in-browser full nodes".

Since this will take a long time to reach and will require a lot of rework at the base protocol, it would be interesting to create such a verification system as a L2 service. Basically, you could pay people to prove that a given chain is valid since genesis, which would be incredibly valuable for light clients. This doesn't require a hardfork and could prove to be a valuable experimentation for a full transition to a SNARK based chain.

Answer 2

The problem here is not the feasibility, that is quite proven, but the enormous computational cost (in terms of EVM instructions, not absolute).

Vitalik Buterin is pressing the community for adoption of the technique. May be this could help if some primitive functions be added to the so called “precompiled contract set” of Ethereum, where you can find elliptical calculus, basic hash functions and so on.

At the moment it not so easy to stay in the computational limits stated by EVM and Ethereum (I’m talking about gas limit and so on).

Answer 3

Will be possible to implement those SNARKS at the protocol level to verify the entire Ethereum Blockchain? If it isn't, why?

The answer to this question can only be of speculative nature, but here we go, I'll give it a try.

Eventually it is not necessary to implement this in the main net. Ignis Plasma is coming very close to what you're imagining. Take a look at "https://medium.com/plasma-ignis/presenting-ignis-plasma-of-fire-502fab5a6f17". In Ignis they use ZK-SNARKs to prove on main chain that the plasma chain is executing the code as agreed by participants.

In general, thanks to libraries like ZoKRates (and added support for sha256 recently), the application of ZK-SNARKs is in the reach of possible on Ethereum. There are already PoCs on Reimplementing Zcash on it. See ZKDAI. However, two main problems remain: the resource-intensive computation of the proof (done offchain) and the trusted setup and toxic waste. The verification on chain is O(1), however the gas costs are above 1M gas, which is still very expensive, but it could be considered as feasible. And we can expect to see the limits being pushed in the future.