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.
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.
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?
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!
IMO the strongest applications are blockchain-related, but here are some other ideas which have been suggested -
- One can selectively disclose certain aspects of their identity. E.g. given a commitment to my DNA, I can prove that it doesn't match that of a suspect. (Though the police need some way to trust the commitment, perhaps a signature from the firm that sequenced it.)
- We can build trustless games, like an implementation of battleship where cheating is cryptographically hard.
- We could have trustless computation services, like ec2, or like SETI@home, etc. Though it's difficult to make this practical given the computational overhead of ZKPs.
- ZKPs can turn any delay function (like an iterated hash) into a verifiable delay function (VDF). VDFs could enable trustless lotteries/sortition.
- Given a general-purpose ZKP, it's trivial to build a signature scheme, e.g. by proving knowledge of a hash pre-image. This can sometimes lead to very practical signature schemes, such as Picnic, one of the leading hash-based signature proposals. Ring signatures are another generally-useful application.
- I think ZKPs have also been used as a building block in some FHE and MPC systems, though I don't know much about those areas.
- One can prove the existence of an exploit before divulging the details. This might be useful for e.g. convincing everyone to disable a certain TLS primitive which was just broken.
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.