What's the Deal with Zkapps?
cryptologie.net
cryptologie.net
Even if Intel engineers were capable of writing firmware with zero bugs and their chips were able to resist all hacking attempts, any user of those chips has to treat Intel as a trusted third party.
This is especially bad if, in practice, you have to regularly apply (encrypted?) firmware updates from Intel whenever they tell you to (because your users won't trust an execution which comes with a proof from an out-dated firmware version).
Once you've accepted Intel as a trusted third party, then consider that they are subject to interference by at least one government, so now your threat model has to include them too.
Circom (https://github.com/iden3/circom) has already been used to build several cutting edge privacy tools, such as Tornado Cash, zero knowledge gaming platforms, like the "Dark Forest" game that Gubsheep works on, and lots of really interesting private voting platforms with various properties. The possibilities in this space are truly mind bending.
OTOH, secure enclaves like SGX are convenient since the overhead's not bad, you can run the enclave as a networked service, make HTTPS connections, sample randomness via RDRAND, etc...
Do you think zkapps might have similar capabilities in the future? I'm not sure the analogy works all that well in blockchain land, but perhaps more as a virtual software-only enclave or something?
It's not super clear to me how you would sample private randomness, or perform remote attestation, or prevent replay attacks without a remote trusted storage.
I also remember even the best proof systems seemed to have like 100x prover overhead on CPU + memory usage, but that was a few years ago. Have things gotten better recently?
Interestingly, if you ask people which they would trust for a rollup, most say ZK is the more trustworthy technology. In part just because it doesn't depend on one vendor (the enclave manufacturer).
I think in the future the overhead will improve significantly, and we can already see incremental improvements in some proof systems. For Kimchi (the proof system we’ve built for zkapps/Mina), we've instead focused on features — like infinite recursion. To really see the performance overhead reduce, we’ll need to push more of the compute into silicon (think opcodes designed for zk similar to the ones we have now to accelerate RSA). In the meantime, modern processors are fast enough that this overhead doesn’t hold back many sorts of applications.
On fixed inputs: Kimchi is “universal” in that it can recursively compose arbitrary circuits efficiently — including ones with different public and private inputs and including ones that haven’t been defined yet. This is what powers zkapps and zkapps’ ability to recursively compose circuits on itself (think application-specific rollups).
Randomness: Modern blockchains have mechanisms for trustlessly agreeing on securely generated random seeds. We can tap into that and use mechanisms like verifiable random functions (which Mina uses internally during consensus) to securely manage randomness (caveat: we haven’t built out the randomness APIs for zkapps yet so there may be some nuance here that we haven’t run into yet). If you want to learn more about how this works in Mina, read up on Ouroboros Samasika, Mina Protocol’s consensus mechanism.
Prevent replay attacks: Blockchains are designed for this :). Basically increment a nonce and feed the current nonce as one of the public inputs to the zkapp.
Remote attestation: This requires nuance to define properly as there are different solutions to different versions of this problem. I’ll outline a few here:
1. Consider the case where you trust the entity that attesting to something and they can upgrade their backend: the entity adds a snark friendly signature to their endpoint and you check the signature within the zkapp (remember since they run locally, you execution can just make async network requests)
2. Consider the case where you trust the entity but can’t convince them to change their API: here you can verify the contents of the response against the TLS signature that already exists in the modern web. Caveat: this is still a work in progress, we’re currently calling it zkOracles
3. Consider the case where you don’t trust the entity — in this case we’re talking about reading information from other zkapps or blockchains. Luckily, these all come with signatures in different shapes and sizes so the problem becomes efficiently verifying those signatures from within the zkapp. You can solve this in modern plonkish zk proof systems with custom gates. Caveat: this is also a work in progress for zkapps in Mina.
Speed and memory usage is improving quickly.
If the program is closed source, you can't trust it, so you can't trust its proofs even if you can validate them quickly.
For the rest, the need to trust data is as important as trusting the code. But maybe there are applications where that's not important.
This allows cool things. For example, if you wanted to use a zkSNARK to check if something was sorted, you don't have to implement a sorting algorithm in the zkSNARK language (this would take time nlogn). Instead, you can just implement an algorithm that takes as input a list, and checks that it is in ascending order (which takes time O(n)). In this case, the witness is the sorted list, and the actual sorting happens outside the zkSNARK. This enables the zkSNARK impl to be more efficient.
I didn't read it as suggesting that the source code itself would be secret, only that the code would act on secret data, like private keys.
> non-deterministic (e.g. invokes random)
I'm not sure how that works either, since there's no way to prove that the "random" number you generated off-chain really is random. It's possible to do random number generation among multiple mutually-untrusting parties already, though, just by getting them to each pick a random number, and publishing its hash, then (after receiving all the hashes), revealing the input random numbers and XORing them all together.
> or async (pulls data outside the blockchain).
I assume the data from outside the blockchain has to have signatures on, so that the smart contract on the blockchain can verify that this data is legitimate. Again I'm not sure why that needs zero-knowledge.
I see the stated claims but my current understanding of crypto and smart contracts is insufficient to figure out the inner workings.
It feels like it should be impossible to know/verify the results of a general program without running it yourself.
https://www.youtube.com/playlist?list=PLj80z0cJm8QErn3akRcqv...
Long-term, Ethereum might implement it natively, but right now the tech is advancing so fast that they're happy having multiple layer-2 systems doing it.