4 ms·
The tricky part of the whole thing is that the original writeup claims "there are compilers that convert C to circuits". This is technically true but not helpf
by mike_hearn 11y ago
The tricky part of the whole thing is that the original writeup claims "there are compilers that convert C to circuits".
This is technically true but not helpful, because (as far as I'm aware) none of the good ones are open source or even publicly available at all.
Also, they typically compile only a restrictive subset of C, not full blown C. For instance, you normally have to be able to statically unroll all the loops. The only compiler that can handle full C works by using a (very large) circuit that emulates an actual CPU. Proving times are extremely high, as you might imagine.
Without a compiler, you are restricted to proving very trivial statements that are of little practical use (except as building blocks for more advanced apps) ... things like "I own the solution to a soduku puzzle" i.e. a pure constraint satisfaction problem.
- Manishearth 11y ago> Also, they typically compile only a restrictive subset of C, It has to be a restrictive subset of C; since not all C code has a combinatorical equivalent. Sequential circuits (those with things like flip flops) do not work with this proof[1]. I also suspect that there is no general zero knowledge proof for these circuits/programs, and there may be sequential circuits for which there is no ZKP at all. This is because variables like "the number of iterations in a loop" can be extracted from the execution proof, making it no longer zero knowledge. I don't think that this can be masked in a general solution that doesn't completely unroll loops. I don't know how to prove this, but I suspect that the halting problem will be involved in raining on this parade. However, most problems can be converted to this restrictive subset, since given the size of the input there is usually a bound on the number of iterations of a loop. In general the halting problem should stop you from calculating this bound, but in most specific cases I think this would be doable. > none of the good ones are open source or even publicly available at all. I've not used it, but libsnark (https://github.com/scipr-lab/libsnark https://github.com/scipr-lab/libsnark) seems to have a bunch of utilities to be able to construct programs using various abstractions it provides. But yeah, no compiler. > you are restricted to proving very trivial statements that are of little practical use Agree 100%. I'm more interested in the cool theory behind it (and its ability to compose with systems like Bitcoin) than actual practical uses. This is pretty much my usual attitude towards such things One practical use I can come up with would be to securely sell a decryption key (or really, any kind of key) via Bitcoin. The bitcoin script already lets you do this, however in the process the key would become publicly known. You can use the trick with the pad mentioned at the bottom of the post in conjunction with ZKP. I suspect that writing the verifier for this using something like libsnark wouldn't be too hard, but I don't know for sure. [1]: They work in the sense that it's still possible to prove things using the same algorithm, but it's no longer zero knowledge: many gates will be visited multiple times, so more than one truth table entry will be revealed, which makes it possible to decrypt the gate. The number of times a gate is visited also leaks information.