4 ms·

Interesting, can you give me a good link on this? Overall I'm skeptic (even of PoUW). That's because verifying work is usually almost as difficult as computing

Interesting, can you give me a good link on this? Overall I'm skeptic (even of PoUW). That's because verifying work is usually almost as difficult as computing. I believe the only true solution to this is Fully Homomorphic encryption (FHE), but known constructions so far have had absolutely massive constants. Is there enough demand of highly-assymetric and verifiable NP-hard like problems?

DennisP 9y ago
A simple way would be to implement the entire work on chain; a challenger has to pay for the entire work on chain, but in theory that rarely happens if the deposit is large enough. Anyone thinking about submitting the wrong answer has to consider that it's easy for prospective challengers to check the work before running the on-chain fraud proof. More complex methods allow fraud to be proven with only a partial computation, by applying merkle proofs. I haven't really dug into it but the TrueBit paper is probably the best source: https://truebit.io/ https://truebit.io/
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 ago
  Oh 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 ago
    All sorts, but those that are easy to convince yourself about are any arithmetic or Boolean circuit.

DennisP 9y ago

A simple way would be to implement the entire work on chain; a challenger has to pay for the entire work on chain, but in theory that rarely happens if the deposit is large enough. Anyone thinking about submitting the wrong answer has to consider that it's easy for prospective challengers to check the work before running the on-chain fraud proof. More complex methods allow fraud to be proven with only a partial computation, by applying merkle proofs. I haven't really dug into it but the TrueBit paper is probably the best source: https://truebit.io/ https://truebit.io/

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 ago
Oh 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 ago
  All sorts, but those that are easy to convince yourself about are any arithmetic or Boolean circuit.