Zero Knowledge Internet Computer Virtual Machine

Roadmap
1

I’ve also discussed this in detail in this Twitter thread: https://twitter.com/lastmjs/status/1464466979386015749

I would love to open up this topic for discussion here, please add your thoughts and corrections if necessary.

The idea is to develop a zero knowledge virtual machine to replace the current IC virtual machine. I’m calling the current virtual machine of the IC the ICVM, and the zero knowledge version the zkICVM.

As I understand it, the ICVM is basically a Wasm runtime (wasmtime, not sure if it’s been modified or not) with IC-specific imports allowing canisters to call the IC APIs.

One problem with the current ICVM (or the IC at large) is that it provides no verification of its computations beyond the BFT guarantees of a subnet. This is a major trade-off when you compare the IC to the current version of Ethereum or to Bitcoin.

Bitcoin and Ethereum place a lot of emphasis on allowing their transactions to be verified by all interested parties. They do this by controlling the growth of the blockchain and making all software and blockchain data open. This allows users to use relatively inexpensive computers to download the entire blockchain and run each transaction from genesis.

This is practically impossible to do on the IC for various reasons, and is a major divergence from the long-running blockchain security models of Bitcoin and Ethereum. The point I’m trying to make here is that it’s arguable the IC may be giving up a good amount of security in exchange for scalability, based on the unwillingness of the two most successful blockchains to make this trade-off (though Ethereum may soon be conceding).

One possible solution to this is to develop a zero knowledge version of the ICVM, which again I’ll call the zkICVM. This would provide ZK proofs that would hopefully allow users interacting with subnets to have some verification that both their and others’ update calls have been processed correctly, beyond the BFT guarantees of the subnet.

A first step to implementing the zkICVM could be to implement a zkWasm VM. Basically, imagine a zero knowledge version of wasmtime or other Wasm runtimes, that provide proofs of computation in addition to performing the computation. This would hopefully plug into the ICVM with relatively little modification (I assume similar to how wasmtime probably has little modification to be integrated into the IC), thus resulting in the zkICVM.

zkSync, StarkWare, and Hermez I believe are all developing zkEVMs, which are general-purpose turing-complete (or close to it) VMs that provide SNARK or STARK proofs along with execution. I imagine the actual EVM will eventually be replaced with a zkEVM, allowing all Ethereum computation to be verified with natively-generated proofs.

It seems likely that most blockchains will follow this pattern, and perhaps most computation generally. Let’s help this along with zkWasm (which will provide benefits even outside of the IC and blockchain) and the zkICVM.

28 Likes
2

The Ethereum foundation is actually researching the implementation of a native zkEVM:

GitHub: GitHub - appliedzkp/zkevm-specs
Specs: ZKEVM - HackMD

Their reasoning confirms my own:

“At the moment every node on ethereum has to validate every transaction in the ethereum virtual machine. This means that every transaction adds work that everyone needs to do to verify Ethereum’s history. Worse still is that each transaction needs to be verified by every new node. Which means the amount of work a new node needs to do the sync the network is growing constantly. We want to build a proof of validity for the Ethereum blocks to avoid this.”

Though we might have to go further than just having one proof per block, since we discard old blocks. If we can somehow maintain a proof that proves old blocks as well, that would be ideal. I’m not sure that’s currently possible, as removing the input data might remove the ability to verify the proof.

5 Likes
3

An interesting take on this topic from taken from the Dfinity subreddit:

“L2 ZK rollups do not make sense in context of IC because its whole purpose is to be a scalable blockchain from the beginning. Rollups address the issue of the limited block space of the Ethereum blockchain with low throughput and high fees as a result. The block space in IC is practically unlimited as the number of subnets. Rollups are rather “patches” for the design limitations.”

6 Likes
4

Yes, rollups are a separate topic (and I agree aren’t really useful on the IC). This thread is about a zero knowledge virtual machine, not zero knowledge rollups.

3 Likes
5

Thanks for writing this.

Can you explain why the BFT guarantees of the IC don’t allow a subnet to verify computations? My (limited) understanding of Chain Key Technology is that it does.

Here’s an excerpt from a great Medium article about Chain Key Technology:

For the nodes to jointly generate a signature on a message, a standard threshold signing algorithm is sufficient. For the generation and maintenance of all the keys, the DFINITY team has invented new cryptography that we are going to explain at a high level now. There are two main procedures that we have built: (1) The formation of new subnets and the generation of the key materials for them is done by the Internet Computer’s Network Nervous System (NNS) which is implemented by canisters that run on the initial subnet that is created at genesis; and (2) Once the nodes that are to form a new subnet have received their key materials from the NNS and started to operate a new subnet, the subnet will manage and maintain its keys itself as per the Internet Computer Protocol.

These two procedures are built from a number of cryptographic primitives including threshold signatures, public key encryption, and non-interactive zero-knowledge proofs.

Chain Key cryptography will generate secure key materials as long as a single dealer is honest, a criterion which is satisfied if more than one-third of the nodes of the NNS subnet will act as dealers. They each generate a public key, encrypt secret key shares under the encryption keys that the new nodes have made available when registering with the Internet Computer, and then add our tailor-designed noninteractive zero-knowledge proofs that they have done all of this correctly. The NNS subnet as a whole verifies these proofs and, if they are correct, makes the information provided by all of the dealers available to the nodes of the new subnet.

In other words, the IC already internally uses ZK proofs.

In fact, the IC’s use of ZK proofs allows its subnets to generate catch-up packages, which as a side effect allows subnet blockchains to throw away old state. In other words, the IC has already solved the problem you mention the Ethereum Foundation is currently researching.

Take all this with a grain of salt… I am no expert on this. Can someone from DFINITY chime in? I too am curious how the IC fits into a ZK-dominated ecosystem, which seems to be the direction Ethereum is heading in. (I am the author of that Reddit post lol)

6 Likes
6

To the best of my knowledge, and it would be great for DFINITY engineers to discuss:

Notice that the zero knowledge proofs described in those excerpts above are being used to manage the chain key secret key materials, which don’t have much to do with canister execution. It is the canister execution that this proposal wishes to add zero knowledge proofs to.

Once a proper chain key is setup for a subnet, we have high assurance that execution is performed correctly only according to the BFT guarantees of that subnet. As for why BFT guarantees are not enough, we’re basically blindly trusting that 2/3 of the nodes are honest. The problem is that any 2/3 could collude to push through bad state changes, and you as a user would not necessarily be able to immediately tell, because BFT hasn’t been broken.

Zero knowledge proofs of canister execution would provide a proof that the execution was performed correctly, regardless of any BFT guarantees. Even if 2/3 of the nodes were malicious, an incorrect state change would not be able to provide a correct proof. You as a user would then know that something is not correct.

On Ethereum, one defense to a 50% attack is the ability to verify all transactions from genesis for yourself. As soon as a bad transaction came into your node, your node could reject it. Hopefully many other honest nodes would also be rejecting the incorrect state change, and together you may be able to record the correct state of the chain and hopefully restore it once the attack is over. Others have probably thought much more deeply about how local transaction verification provides greater security, but I think that’s the general idea.

The Internet Computer provides no such defense to users, they simply trust execution blindly. Chain key signatures mean nothing if 2/3 of the nodes are malicious. Zero knowledge proofs will provide this extra assurance that the IC is working as intended.

8 Likes
7

The current zero knowledge proofs, chain key, and catch-up packages do not simply allow the IC to throw away old state without a trade-off in security. I feel the materials explainring this have been misleading and incorrect. Dominic Williams seems to finally explain this trade-off in this episode of Epicenter: https://epicenter.tv/episodes/406

Throwing away old state comes with an absolute trade-off in security compared with other blockchains. On the IC you cannot verify the state of the blockchain on your own, you simply trust. This is worse than many other blockchains.

3 Likes
8

Hopefully it is clearer now that this is not the case.

1 Like
9

It seems like we could substantially increase the trust in computations on the IC by implementing a zero knowledge machine. What can we do to help get such a machine onto the IC? I imagine the implementation would have to come from Dfinity? Or could an independent coder do it?

1 Like
10

I don’t think DFINITY necessarily has to do it. We can start with a zkWasm VM, which would be generally beneficial outside of the IC and blockchain. I’ve been reaching out to zk projects to understand if any work is being done on a zkWasm VM. So far I haven’t found any indication that a zkWasm VM is in the works. There seem to be plenty of general purpose ZKVMs out there in various stages of development, but nothing as tidy and easy to use as zkWasm would be.

A really practical thing you can all join me in doing is getting on Twitter, Discord, etc with all of the existing ZK projects, and asking them about zkWasm and finding out of there is any appetite to build it.

3 Likes
11

Zero knowledge proofs of canister execution would provide a proof that the execution was performed correctly, regardless of any BFT guarantees. Even if 2/3 of the nodes were malicious, an incorrect state change would not be able to provide a correct proof. You as a user would then know that something is not correct.

Wouldn’t any zero-knowledge proof be provided (i.e. jointly signed?) by those same nodes anyways? So if 2/3 of nodes are corrupt, can’t they also collude to provide a seemingly correct proof? Not sure how ZK proofs can get around that.

I always thought ZK proof was a way for one blockchain (like a rollup) to tell another blockchain (like Ethereum) that some block generated by the rollup is valid. In other words, I thought it was “inter-chain”.

In this case, you’re referring to proofs made by nodes in the same subnet, which is “intra-chain”. I dunno… would be nice to get clarification by DFINITY on something as fundamental as this.

I feel the materials explainring this have been misleading and incorrect. Dominic Williams seems to finally explain this trade-off in this episode of Epicenter: https://epicenter.tv/episodes/406

Do you mind sharing when in this episode he talks about this? Also, kinda wished these episodes were timestamped… not sure if this was recorded a year ago or last week.

1 Like
12

Here’s one example of a ZK VM: GitHub - GuildOfWeavers/distaff: Zero-knowledge virtual machine written in Rust

This project is basically what we would want to develop (perhaps a SNARK/PLONK would be used instead?), but instead of using their DSL bytecode or assembly, we would use Wasm bytecode, thus it would be a zkWasm VM.

Then any program written in Rust, C, Motoko, or anything else that compiles to Wasm could run on the VM, and proofs could be produced!

Here’s another similar project: GitHub - novifinancial/winterfell: A STARK prover and verifier for arbitrary computations

7 Likes
13

It’s from august 24th 2021

1 Like
14

This is cool stuff. Right now, zk VMs are like a magic black box to me.

Surely there must be limitations on what programs they can run? It sounds too good to be true for a holder of a zk proof to be able to verify that some output was indeed generated by some input + program given only the program source hash for ANY arbitrary program… how does that even work lol

4 Likes
15

I’d love to work on this! :slight_smile:
I’ll add the potential benefit of privacy: a single node can do the computation (with some backup mechanism to not lose state if it crashes) and prove the computation is correct, which enables confidential computation where you trust one node (plus backups) instead of every node in a subnet.
The disadvantage is cost. In theory you can do SNARKs for Wasm, in practice it will make execution orders of magnitude slower. So the question is which applications want to make the tradeoff.

18 Likes
16

How would this work with wasi imports and i/o operations? E.g. if the input is a path and uses the runtime to read the input file? Or the output is actually writing to the file system or uploading to an api?

17

I think in terms of scalability the IC is making different trade-offs compared to the roll-up centric ZK world of Ethereum. I don’t actually feel as though this is a bad thing. The PBFT style consensus is the way to go as it lets you get the security guarantees without having to do all that work without using snarks and data availability proofs, which I am not sure are all that friendly for the interoperability side.

Using BLS signatures is actually a beautiful way of handling interoperability, as it means one only needs the signature to verify data cross-chain rather than using the state-roots from snarks.

Not saying there aren’t other advantages to a snark-based VM like privacy. That’s a separate topic. But seems the TEE enhancement proposal may also help with privacy as well.

2 Likes
18

In terms of meeting with the ETH 2.0 roadmap, I actually think that the data-availability proofs would be most useful. If we wanted to archive and verify the prior state of the IC.

Snarks seem like a substitute for BFT consensus, which is not needed in the current design of the IC IMO, unless it is to enhance specific applications.

2 Likes
19

I would love you to work on this.

3 Likes
20

After reading this recent article by @JensGroth on privacy on the IC, I was struck by this part:

As the Internet Computer grows more sophisticated, we expect transparency to increase. One option is verifiable builds of canisters. Canisters are provided by developers in the form of WebAssembly (Wasm) modules. Deterministic compilers can link the Wasm module directly to the original source code.

I wonder if this is a potential application of zk proofs. For example, some canister build process could generate a proof in addition to the actual compiled wasm binary. Then, others could verify (with the proof) that the binary came from the published source code without repeating the potentially expensive compilation themselves. Of course, like before this still requires the canister be open source.

Not sure if this is actually a step forward… just thinking aloud.

1 Like