3 ms·
> That's because verifying work is usually almost as difficult as computing. Where did you get that idea? What about zk-proofs, like SNARKs and STARKs? I'm wor
by mhluongo 9y ago
> That's because verifying work is usually almost as difficult as computing.
Where did you get that idea? What about zk-proofs, like SNARKs and STARKs? I'm working on a multiparty computation system right now that uses a proof system to offload costly computation.
- darkmighty 9y agoOh interesting. Like I wrote, I'm aware there are certain problems that can be verified efficiently, that is, whose computation time is much larger than verification time, ver_t/comp_t<<1, but is it possible to take a generic program and offload it with (1) cryptographically secure verification afterwards and (2) ver_t/comp_t << 1? As a challenge, take the problem of computing 1000000 iterations of a memory-hard hash function, such as scrypt or argon2d. If someone presents you a hash (of length N), the best you can do to verify it is actually compute the iterated hash function (assuming it has no cryptographic weakness). This would prove, in particular, that my required method is impossible (i.e. there are at least some problems that can't be efficient offloaded). What kind of problems can the technologies you cited offload?
- mhluongo 9y agoAll sorts, but those that are easy to convince yourself about are any arithmetic or Boolean circuit.