4 ms·

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 blockc

by rafale 4y ago

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.

dane-pgp 4y ago
> the program can have secrets (closed source) 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.
Ar-Curunir 4y ago
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.

by rafale 4y ago

dane-pgp 4y ago

> the program can have secrets (closed source) 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.

Ar-Curunir 4y ago

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.