> These chips would typically be certified by some vendor (for example, Intel SGX) with some claim that it’s hard to tamper with them. Unfortunately for Intel and others, the security community has found a lot of interest in publishing attacks on their "secure" hardware, and we see new hacks coming up pretty much every year.
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.
Gubsheep's talk last week wildly changed my perspective on zk-crypto. Basically he frames zk-circuits as an "expressive language for claims". For example, while you can come up with custom crypto schemes for claims like "I know a private key that belongs to Alice's public key", RSA and ECDSA both do this, but using zk-circiuts you can easily make much more complex claims. The example he gives later is "I know a private key corresponding to Alice, Bob or Charlie's public keys, and the other two can (or maybe can't) prove that they did NOT generate this message." So, using these tools, you as a programmer can build up complex cryptographic machinery claiming all sorts of wild things without needing a cryptographer standing over your shoulder.
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.
Cool. My takeaway is this: Instead of sending an RPC call to the network to execute code and change state, code is executed off chain (locally), and the state change is sent to the network with proof that it's valid state. If my thinking is correct, this is pretty awesome. The article was very well written IMO.
Woah this looks cool! My current (clearly outdated) mental model requires fixed inputs for a zkp, e.g., some fixed view of the chain state, some encrypted inputs, etc... I'm curious to know more how Mina overcomes these limitations.
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?
There are definitely certain scenarios, especially around verifiable compute, in which you can think of ZK as a software alternative to a secure enclave.
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 work on the tooling layer for zkapps on Mina — Great questions!
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.
There are projects doing general propose computing/turning complete vm to zk which will be big deal. Maybe some research paper / hardware implementation away from speed enough for their general propose use ¯\_(ツ)_/¯, very excited. :D
Examples include the various zkEVM projects, risc0, and slightly more limited stuff like our effort to compile PyTorch/ONNX to a zk circuit (https://github.com/zkonduit/ezkl).
I didn't understand the part where the program can have secrets (closed source), non-deterministic (e.g. invokes random) or async (pulls data outside the blockchain).
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.
Non-determinism in the context of zkSNARKs refers not to randomness, but rather to NP-style non-determinism. I.e., zkSNARKs support statements of the form "There exists a witness w such that f(x, w) = true", where f is a predicate, and x is a publicly known value.
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.
Nothing, it's already supported. In fact, Circom, one zk programming language, will output a Solidity verifier that can be deployed on any EVM chain. The proof generation would be run off chain, but the verification can and does occur directly on mainnet.
It already has zkrollups, which run zkapps off-chain but store their state and the proofs on chain. That multiplies Ethereum's transaction capacity by an order of magnitude or two, without losing any security.
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.
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.