5 ms·

It's confusing because there are two distinct 'recursive things' involved. You may be noting that distinction. On the one hand, Lurk allows expression of recur

It's confusing because there are two distinct 'recursive things' involved. You may be noting that distinction. On the one hand, Lurk allows expression of recursive computations (like in the cited example). This doesn't necessarily demand 'verifying previous proofs' (in proofs). However, recursive SNARKs (where proofs of proofs are verified ad infinitum) are useful for actually producing a single succinct proof of a potentially unbounded recursive computation. So there is a practical relationship between the two recursive aspects, but they're not strictly the same thing. This is indeed a bit of a confusing subtlety.

noman-land 4y ago
So you could do a collaborative computation of a particular index in fibonacci by taking turns computing up to a certain index, getting the hash and handing it off like a baton to someone else who could prove the starting value they're given is correct for the starting index and then keep going?
- porcuquine 4y ago
  Yep, that's a perfect minimal example of the kind of thing we could do. Exactly how to 'extend' the computation depends on how it's set up. What you describe is possible, as are more elaborate applications in which the 'result so far' includes a log of all previous results (basically a memoized table of the recursive computation so far). If you have a proof that the merkle root of this table is correct, then you can just look up any so-far-known value. Taken to its extreme, this could be used to produce a collective database reducing arbitrary deterministic functions to lookup — what I think of as 'compute-addressable' (riffing on content-addressable) data. Since Lurk can express arbitrary computation in its own data language, such a universal database wouldn't strictly require per-function circuits (though for performance, some customization will help).
  - noman-land 4y ago
    So incredibly cool. I've been thinking about a use case for the 'result so far' mechanic and I've been trying to figure out how to build it. Perhaps I'll give lurk a try :). Are you on any zk chat channels on matrix/telegram/discord/etc? Would love to chat more about this.
    - tylersmith 4y ago
      The term you want to look into is Incrementally Verifiable Computation.

noman-land 4y ago

So you could do a collaborative computation of a particular index in fibonacci by taking turns computing up to a certain index, getting the hash and handing it off like a baton to someone else who could prove the starting value they're given is correct for the starting index and then keep going?

porcuquine 4y ago
Yep, that's a perfect minimal example of the kind of thing we could do. Exactly how to 'extend' the computation depends on how it's set up. What you describe is possible, as are more elaborate applications in which the 'result so far' includes a log of all previous results (basically a memoized table of the recursive computation so far). If you have a proof that the merkle root of this table is correct, then you can just look up any so-far-known value. Taken to its extreme, this could be used to produce a collective database reducing arbitrary deterministic functions to lookup — what I think of as 'compute-addressable' (riffing on content-addressable) data. Since Lurk can express arbitrary computation in its own data language, such a universal database wouldn't strictly require per-function circuits (though for performance, some customization will help).
- noman-land 4y ago
  So incredibly cool. I've been thinking about a use case for the 'result so far' mechanic and I've been trying to figure out how to build it. Perhaps I'll give lurk a try :). Are you on any zk chat channels on matrix/telegram/discord/etc? Would love to chat more about this.
  - tylersmith 4y ago
    The term you want to look into is Incrementally Verifiable Computation.