3 ms·
I don't know much about STARKs, but I read that SNARKs has a problem with unbounded loops(variable number of iterations), also "break/continue" statements are p
by milansuk 5y ago
I don't know much about STARKs, but I read that SNARKs has a problem with unbounded loops(variable number of iterations), also "break/continue" statements are problematic. Is it still true? Is there some research that will allow running code as is(no inefficient tricks like running maximum possible iterations)?
- tromp 5y agoYou can think of STARKS/SNARKS as proving computation, not by a program, but by a computational circuit. So the circuit size puts limits on the amount of computation. Recently, we see the introduction of recursive proof schemes (such as [1]), where part of the circuit may be verifying a proof of a much larger computation. Those can deal with certain forms of unbounded computation, such as verifying a blockchain history of arbitrarily many blocks. [1] https://eprint.iacr.org/2021/370.pdf https://eprint.iacr.org/2021/370.pdf
- jl2718 5y agoNo. This would be a tautological violation of zero-knowledge, so it will never be solved. However, if all you care about is the verification proof, then yes, you can prove arbitrary recursions by providing the branch condition evaluations as part of the proof.