4 ms·

Does this mean we could have cryptocurrencies with proof-of-work mechanisms that perform useful work? You could have a decentralised crowd sourced general super

Does this mean we could have cryptocurrencies with proof-of-work mechanisms that perform useful work? You could have a decentralised crowd sourced general supercomputer which could perform folding-at-home, neural network training etc. and you could get paid for it with no middleman?

a_tartaruga 4y ago
Yes. Also networks that perform simple versions of useful work exist today. I work on a network which uses zk proofs to check storage of user input data and pays out blockchain consensus rewards accordingly.
jlokier 4y ago
Sort of, yes, but doing that would be a waste of energy, compared with altruistically donating your cycles like in folding@home. The cost of proving execution is high compared with the cost of execution without proof. (Even in a dedicated proof-of-execution hardware CPU, which by the way I'm also working on a little, in case someone out there finds themselves looking to hire someone doing this sort of thing ;-) On the other hand, for proof-of-stake and similar systems, these kinds of proofs completely change the dynamics because there is no need for every node to duplicate all the state machine updates. Current blockchains have hundreds or thousands of full nodes, each of them executing the same code to verify the behaviour is the same. They can accept proofs instead, so that executions are done by only a few nodes. That greatly changes the scaling cost. With a few more tricks it starts to look more like a giant CRDT with lightweight nodes maintaining just a "view" of the part they are interested in, and some more tricks on top of that for latency hiding, it starts to look more real-time, as in MMO levels of interactive performance, not the blockchain you are used to.
- WithinReason 4y ago
  > The cost of proving execution is high compared with the cost of execution without proof. What ratio are we talking about here roughly? Is is 10% higher or 1000x higher?
  - jlokier 4y ago
    Roughly, closer to 100x-10000x than +10%. GPU vs CPU vs FPGA vs ASIC makes a lot of difference. New algorithms are being discovered or developed that improve the speed. I think we may see roughly 10x in the next few years on ideal hardware for the task, but the economics might not be there to pay for building it.
    - WithinReason 4y ago
      Can you achieve something similar by having multiple (e.g. 5) randomly chosen nodes perform the same calculation and compare their results? Or is there always a way around that?
      - jlokier 4y ago
        That's a different sort of proof, the computer equivalent of social proof. It's not as cryptographically strong as zero-knowledge proofs can be. Those 5 nodes could all be dishonest, unless you know they are not. Whereas you don't have to trust a zero-knowledge prover at all. A dishonest prover will "always" be detected (for a definition of "always" similar to general cryptography, i.e. extreme probabilities). Zk proofs (of the type I'm using) are more like fancy hash functions, where there's one correct answer and no node-specific key. Unlike, say, TLS PKI where you have to obtain certificates and trust particular nodes. (There are sometimes keys in zk, called "trusted setup", but those keys are computed in distributed ceremonies and shared with everyone.) That said, there are some interesting tricks, similar to your idea, for distributing a zk computation among nodes who cross-verify-and-prove each other's work without needing to trust each other, reducing the amount of work per node and perhaps latency. You do need the social proof type as well in practice. The zk proofs assert some fact which may accompany data, and some clever networking protocols can build on that, like proofs of (recent) data availability. But for consensus protocols, the zk proofs don't tell you which of those facts everyone is collectively agreeing to. For that, comparing results is required. In blockchains where the p2p networking is automated, typically there's an assumption that your node will find at least one honest node with respect to the consensus, or some small number, and their information will outweigh bad information from other nodes. While bootstrapping more honest nodes are required than later, when following a networking in its live state. But there's always a possibility that a node is only able to connect to a coordinated group of dishonest nodes, especially if someone is hacking the network aroud the target node, e.g. by affecting the routers. That's called an eclipse attack. Note: I keep talking about blockchains because you asked about PoW, and that's where a lot of the zk proof of execution and proof of data availability stuff is focused these days, and it's a natural fit when multiple nodes and networking get discussed. But there are many non-blockchain uses as well!

a_tartaruga 4y ago

Yes. Also networks that perform simple versions of useful work exist today. I work on a network which uses zk proofs to check storage of user input data and pays out blockchain consensus rewards accordingly.

jlokier 4y ago

Sort of, yes, but doing that would be a waste of energy, compared with altruistically donating your cycles like in folding@home. The cost of proving execution is high compared with the cost of execution without proof. (Even in a dedicated proof-of-execution hardware CPU, which by the way I'm also working on a little, in case someone out there finds themselves looking to hire someone doing this sort of thing ;-) On the other hand, for proof-of-stake and similar systems, these kinds of proofs completely change the dynamics because there is no need for every node to duplicate all the state machine updates. Current blockchains have hundreds or thousands of full nodes, each of them executing the same code to verify the behaviour is the same. They can accept proofs instead, so that executions are done by only a few nodes. That greatly changes the scaling cost. With a few more tricks it starts to look more like a giant CRDT with lightweight nodes maintaining just a "view" of the part they are interested in, and some more tricks on top of that for latency hiding, it starts to look more real-time, as in MMO levels of interactive performance, not the blockchain you are used to.

WithinReason 4y ago
> The cost of proving execution is high compared with the cost of execution without proof. What ratio are we talking about here roughly? Is is 10% higher or 1000x higher?
- jlokier 4y ago
  Roughly, closer to 100x-10000x than +10%. GPU vs CPU vs FPGA vs ASIC makes a lot of difference. New algorithms are being discovered or developed that improve the speed. I think we may see roughly 10x in the next few years on ideal hardware for the task, but the economics might not be there to pay for building it.
  - WithinReason 4y ago
    Can you achieve something similar by having multiple (e.g. 5) randomly chosen nodes perform the same calculation and compare their results? Or is there always a way around that?
    - jlokier 4y ago
      That's a different sort of proof, the computer equivalent of social proof. It's not as cryptographically strong as zero-knowledge proofs can be. Those 5 nodes could all be dishonest, unless you know they are not. Whereas you don't have to trust a zero-knowledge prover at all. A dishonest prover will "always" be detected (for a definition of "always" similar to general cryptography, i.e. extreme probabilities). Zk proofs (of the type I'm using) are more like fancy hash functions, where there's one correct answer and no node-specific key. Unlike, say, TLS PKI where you have to obtain certificates and trust particular nodes. (There are sometimes keys in zk, called "trusted setup", but those keys are computed in distributed ceremonies and shared with everyone.) That said, there are some interesting tricks, similar to your idea, for distributing a zk computation among nodes who cross-verify-and-prove each other's work without needing to trust each other, reducing the amount of work per node and perhaps latency. You do need the social proof type as well in practice. The zk proofs assert some fact which may accompany data, and some clever networking protocols can build on that, like proofs of (recent) data availability. But for consensus protocols, the zk proofs don't tell you which of those facts everyone is collectively agreeing to. For that, comparing results is required. In blockchains where the p2p networking is automated, typically there's an assumption that your node will find at least one honest node with respect to the consensus, or some small number, and their information will outweigh bad information from other nodes. While bootstrapping more honest nodes are required than later, when following a networking in its live state. But there's always a possibility that a node is only able to connect to a coordinated group of dishonest nodes, especially if someone is hacking the network aroud the target node, e.g. by affecting the routers. That's called an eclipse attack. Note: I keep talking about blockchains because you asked about PoW, and that's where a lot of the zk proof of execution and proof of data availability stuff is focused these days, and it's a natural fit when multiple nodes and networking get discussed. But there are many non-blockchain uses as well!