5 ms·

These days I'm working on "proof of execution" and "proof of data availability", which are an interesting application of zero-knowledge proofs to very large seq

These days I'm working on "proof of execution" and "proof of data availability", which are an interesting application of zero-knowledge proofs to very large sequences of values. The steps aren't revealed, but the rule which the steps must follow is revealed. It's almost magical how it's possible to prove that N billion steps of a simulated virtual computer, run exactly according to specification, complete with CPU and memory, given a particular set of input files (or even a hash of an input) and program (or hash of a program), produces a particular set of output files. All summarised in a short proof that a verifier can easily and quickly check, so it doesn't have to redo the computation itself - it can trust the outputs it receives, due to the proof.

orbat 4y ago
Interesting! Sounds somewhat like what the Cairo programming language & VM does https://www.cairo-lang.org https://www.cairo-lang.org; Turing-complete provable computation using a fairly funky "arithmetic" CPU architecture.
- jlokier 4y ago
  Yes, like Cairo. In fact I almost applied to a job working with Cairo recently, but I was told someone else had just started it. It's possible to build more standard CPUs as well which use ordinary arithmetic, logic and memory, at some cost to efficiency. But the cost is almost entirely borne by the prover.
victor106 4y ago
Interesting, any resources you can share?
- jlokier 4y ago
  As a start I suggest you look at whatever is written about SNARK and STARK in the Ethereum world. Vitalik Buterin's blog has some good technical articles (literally look for those words in the titles). They don't cover proofs of CPU-like systems, though. There are a lot of other articles, papers, etc. I'm just suggeting those search terms as a starting point. The Cairo system from Starkware is a pretty good, modern CPU-like system (albeit using finite fields and an unusual CPU model, instead of normal numbers), which is simpler than its predecessors in some ways because the techniques have matured and they have been able to use techniques devised by many different R&D groups before that iteration. As far as I'm aware, however, performance at the billions of steps level is more on the frontier. I'd love to share details of what I've been working on, and I hope I will be able to one day. One problem is I'm looking for work, and there's an interesting company I'm negotiating with but their view of IP may prevent me from publishing my own work in this area after I've started. Meanwhile, I haven't published yet, even though I've done a lot of work on it. I do not like this, I always want to share, but...
WithinReason 4y ago
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?

orbat 4y ago

Interesting! Sounds somewhat like what the Cairo programming language & VM does https://www.cairo-lang.org https://www.cairo-lang.org; Turing-complete provable computation using a fairly funky "arithmetic" CPU architecture.

jlokier 4y ago
Yes, like Cairo. In fact I almost applied to a job working with Cairo recently, but I was told someone else had just started it. It's possible to build more standard CPUs as well which use ordinary arithmetic, logic and memory, at some cost to efficiency. But the cost is almost entirely borne by the prover.

victor106 4y ago

Interesting, any resources you can share?

jlokier 4y ago
As a start I suggest you look at whatever is written about SNARK and STARK in the Ethereum world. Vitalik Buterin's blog has some good technical articles (literally look for those words in the titles). They don't cover proofs of CPU-like systems, though. There are a lot of other articles, papers, etc. I'm just suggeting those search terms as a starting point. The Cairo system from Starkware is a pretty good, modern CPU-like system (albeit using finite fields and an unusual CPU model, instead of normal numbers), which is simpler than its predecessors in some ways because the techniques have matured and they have been able to use techniques devised by many different R&D groups before that iteration. As far as I'm aware, however, performance at the billions of steps level is more on the frontier. I'd love to share details of what I've been working on, and I hope I will be able to one day. One problem is I'm looking for work, and there's an interesting company I'm negotiating with but their view of IP may prevent me from publishing my own work in this area after I've started. Meanwhile, I haven't published yet, even though I've done a lot of work on it. I do not like this, I always want to share, but...

WithinReason 4y ago

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?