6 ms·

Hi, this is my project, though I wasn't expecting to see it here just now. I gave some quick (probably too quick) answers below, and I'm happy to try to answer

Hi, this is my project, though I wasn't expecting to see it here just now. I gave some quick (probably too quick) answers below, and I'm happy to try to answer further questions anyone might have. It's a bit of a strange problem domain so might be hard to orient to what's even going on here if you're not already somewhat familiar. I have to step away for a little while now, but I'll check in later and try to address any questions/comments that emerge in the meantime.

ecesena 4y ago
Any reason to build from scratch vs contributing to arkworks?
- porcuquine 4y ago
  Arkworks isn't really addressing the core of what Lurk provides. In theory, we could use Arkworks to implement a backend — but we are targeting Nova (https://github.com/microsoft/Nova https://github.com/microsoft/Nova), and I don't think Arkworks supports Nova currently. So the part we are building from scratch (the language itself) is at a higher level of abstraction. We like Nova's characteristics and are actively helping with aspects of its implementation so we can use it as soon as possible.
  - ecesena 4y ago
    Great, thank you for the details!
noman-land 4y ago
I've been following this space with extreme fascination from the perspective of a software engineer with no formal mathematics study so please take my questions with a grain of salt. My understanding is that a SNARK circuit is used to prove a series of computations without revealing any of the inputs or outputs. For example some people submit their salaries in encrypted form through a compiled zk circuit and receive an encrypted answer on the other side that that tells them which person earns the most money without revealing who earns what. Is my understanding correct that lurk would be used instead of something like circom where circom can create simple arithmetic zk circuits, whereas lurk can create circuits that can describe arbitrary computations? > Lurk constructs compound data using SNARK-friendly Poseidon hashes (provided by Neptune), so its data is naturally content-addressable. So lurk programs can point to previously proven (and published?) hashes to make provable claims about their calculations? Is this like "merkle-izing" computation? Sorry I'm just really trying to wrap my head around this.
- sterlind 4y ago
  not OP or a crypto expert, but: yes, zk-SNARKs are useful because you can prove you executed a program without revealing inputs or outputs. you can't send encrypted inputs to a zk-SNARK program and get encrypted outputs out, though. you're confusing this with homomorphic encryption. iirc, with Lurk you could, say, convince someone you'd correctly solved a difficult NP-complete problem, by writing a Lurk program that validates a solution to that problem, and publishing the output (Solved) along with the proof steps without revealing your answer. you could, theoretically, write an homomorphic encryption library in Lurk, and then when people send you their encrypted inputs you can send them encrypted outputs along with a proof you faithfully evaluated the FHE circuit. this is actually missing from FHE - a malicious evaluator can do whatever the hell they want with your input data, or make up outputs completely, they just can't see what's inside. that seems pretty neat to me actually, I wonder if the Lurk people are thinking about this. niche but it'd have its uses.
  - porcuquine 4y ago
    > you can't send encrypted inputs to a zk-SNARK program and get encrypted outputs out, though. you're confusing this with homomorphic encryption. Not encrypted, but they can be 'hidden'. For example the input to one computation might have been the output of another — and might be entirely opaque. (For example, the hash corresponding to `(this is a list of data 1 2 3 9873)` will include 32 bytes of data from which it's impossible to compute the original expression unless you already know it. > that seems pretty neat to me actually, I wonder if the Lurk people are thinking about this. niche but it'd have its uses. We are thinking about it, and Lurk would lend itself well to expressing FHE programs. One of our team members has an academic background in FHE, and we're interested in such problems. It's not our top priority right now, but it's a natural area to explore when the core language is more mature.
  - emmorais 4y ago
    Proving correct evaluation of FHE circuits is indeed a nice example of how Lurk can help. We are considering different possibilities regarding FHE, but not as a priority.
- 4y ago
medo-bear 4y ago
hi this is very interesting. why is there a common lisp and rust version? digging through i also found Alu [0], another common lisp project for zk circuits. since you are using common lisp and static typing is important to you are you aware of coalton [1]? [0] https://github.com/heliaxdev/alu https://github.com/heliaxdev/alu [1] https://coalton-lang.github.io/ https://coalton-lang.github.io/
- porcuquine 4y ago
  Nice, I'll have to take a look at Alu. I'm also aware of Coalton. It's very cool in principle, though I have not used it (yet?). The original proof-of-concept was written in Common Lisp, and development of core language features often happens in that version. It's more flexible for rapid development, and the 'API' can be taken it at a glance a bit more simply. Having multiple implementations also has the benefit of keeping us honest (at the cost of some hopefully-ephemeral drift and maintenance).
porcuquine 4y ago
FYI, I will be in transit for much of today so may find further responses difficult (but I will try). I'm hoping others with knowledge of the project might pop in to answer more questions that might arise or provide other detail. If not, this was fun. Thank you, and do follow on Twitter (https://twitter.com/LurkLab https://twitter.com/LurkLab) if you want to stay in the loop. We hope to publish some blog posts with concrete examples and usage soon.
tromp 4y ago
How hard would it be to prove correctness of the root HASH of a merkle tree of N signatures over some CURVE, in terms of proof size, proof construction time, proof verification time, in the following cases? HASH = SHA256/blake2b, CURVE = secp256k1, N = 10^6 HASH = SHA256/blake2b, CURVE = secp256k1, N = 10^9 HASH = Poseidon, CURVE = SNARK-friendly, N = 10^9
- emmorais 4y ago
  Proof size and verification time would be constant (therefore efficient) for all cases. Not using a friendly signature scheme would in principle cause a big increase in proving time. The same situation happens if you want to use something different from Poseidon. But we are designing an improvement to the architecture that allows to deal with such cases, shortly by constructing specialized co-processors. However, it is not yet clear how it would affect performance in practice, but the goal is exactly to improve it significantly.
  - tromp 4y ago
    Yes, I'm asking for the rough sizes of these constants, i.e. order of magnitude. Is proof size for the first case closer to 1MB or 10MB? Is verification time closer to 1s, 10s, 100s, or 1000s?
    - emmorais 4y ago
      It depends on which backend you want to use (currently Groth16 or Nova, but more options can be implemented). For example, Nova proof is roughly 8-9 KB. In this situation we have that verification is not constant, for instance, for 2^20 constraints it would take roughly 1s.
      - tromp 4y ago
        And how many constraints would roughly be needed to represent the first case of a million secp256k1 signatures in a SHA256 Merkle tree?

ecesena 4y ago

Any reason to build from scratch vs contributing to arkworks?

porcuquine 4y ago
Arkworks isn't really addressing the core of what Lurk provides. In theory, we could use Arkworks to implement a backend — but we are targeting Nova (https://github.com/microsoft/Nova https://github.com/microsoft/Nova), and I don't think Arkworks supports Nova currently. So the part we are building from scratch (the language itself) is at a higher level of abstraction. We like Nova's characteristics and are actively helping with aspects of its implementation so we can use it as soon as possible.
- ecesena 4y ago
  Great, thank you for the details!

noman-land 4y ago

I've been following this space with extreme fascination from the perspective of a software engineer with no formal mathematics study so please take my questions with a grain of salt. My understanding is that a SNARK circuit is used to prove a series of computations without revealing any of the inputs or outputs. For example some people submit their salaries in encrypted form through a compiled zk circuit and receive an encrypted answer on the other side that that tells them which person earns the most money without revealing who earns what. Is my understanding correct that lurk would be used instead of something like circom where circom can create simple arithmetic zk circuits, whereas lurk can create circuits that can describe arbitrary computations? > Lurk constructs compound data using SNARK-friendly Poseidon hashes (provided by Neptune), so its data is naturally content-addressable. So lurk programs can point to previously proven (and published?) hashes to make provable claims about their calculations? Is this like "merkle-izing" computation? Sorry I'm just really trying to wrap my head around this.

sterlind 4y ago
not OP or a crypto expert, but: yes, zk-SNARKs are useful because you can prove you executed a program without revealing inputs or outputs. you can't send encrypted inputs to a zk-SNARK program and get encrypted outputs out, though. you're confusing this with homomorphic encryption. iirc, with Lurk you could, say, convince someone you'd correctly solved a difficult NP-complete problem, by writing a Lurk program that validates a solution to that problem, and publishing the output (Solved) along with the proof steps without revealing your answer. you could, theoretically, write an homomorphic encryption library in Lurk, and then when people send you their encrypted inputs you can send them encrypted outputs along with a proof you faithfully evaluated the FHE circuit. this is actually missing from FHE - a malicious evaluator can do whatever the hell they want with your input data, or make up outputs completely, they just can't see what's inside. that seems pretty neat to me actually, I wonder if the Lurk people are thinking about this. niche but it'd have its uses.
- porcuquine 4y ago
  > you can't send encrypted inputs to a zk-SNARK program and get encrypted outputs out, though. you're confusing this with homomorphic encryption. Not encrypted, but they can be 'hidden'. For example the input to one computation might have been the output of another — and might be entirely opaque. (For example, the hash corresponding to `(this is a list of data 1 2 3 9873)` will include 32 bytes of data from which it's impossible to compute the original expression unless you already know it. > that seems pretty neat to me actually, I wonder if the Lurk people are thinking about this. niche but it'd have its uses. We are thinking about it, and Lurk would lend itself well to expressing FHE programs. One of our team members has an academic background in FHE, and we're interested in such problems. It's not our top priority right now, but it's a natural area to explore when the core language is more mature.
- emmorais 4y ago
  Proving correct evaluation of FHE circuits is indeed a nice example of how Lurk can help. We are considering different possibilities regarding FHE, but not as a priority.
4y ago

medo-bear 4y ago

hi this is very interesting. why is there a common lisp and rust version? digging through i also found Alu [0], another common lisp project for zk circuits. since you are using common lisp and static typing is important to you are you aware of coalton [1]? [0] https://github.com/heliaxdev/alu https://github.com/heliaxdev/alu [1] https://coalton-lang.github.io/ https://coalton-lang.github.io/

porcuquine 4y ago
Nice, I'll have to take a look at Alu. I'm also aware of Coalton. It's very cool in principle, though I have not used it (yet?). The original proof-of-concept was written in Common Lisp, and development of core language features often happens in that version. It's more flexible for rapid development, and the 'API' can be taken it at a glance a bit more simply. Having multiple implementations also has the benefit of keeping us honest (at the cost of some hopefully-ephemeral drift and maintenance).

porcuquine 4y ago

FYI, I will be in transit for much of today so may find further responses difficult (but I will try). I'm hoping others with knowledge of the project might pop in to answer more questions that might arise or provide other detail. If not, this was fun. Thank you, and do follow on Twitter (https://twitter.com/LurkLab https://twitter.com/LurkLab) if you want to stay in the loop. We hope to publish some blog posts with concrete examples and usage soon.

tromp 4y ago

How hard would it be to prove correctness of the root HASH of a merkle tree of N signatures over some CURVE, in terms of proof size, proof construction time, proof verification time, in the following cases? HASH = SHA256/blake2b, CURVE = secp256k1, N = 10^6 HASH = SHA256/blake2b, CURVE = secp256k1, N = 10^9 HASH = Poseidon, CURVE = SNARK-friendly, N = 10^9

emmorais 4y ago
Proof size and verification time would be constant (therefore efficient) for all cases. Not using a friendly signature scheme would in principle cause a big increase in proving time. The same situation happens if you want to use something different from Poseidon. But we are designing an improvement to the architecture that allows to deal with such cases, shortly by constructing specialized co-processors. However, it is not yet clear how it would affect performance in practice, but the goal is exactly to improve it significantly.
- tromp 4y ago
  Yes, I'm asking for the rough sizes of these constants, i.e. order of magnitude. Is proof size for the first case closer to 1MB or 10MB? Is verification time closer to 1s, 10s, 100s, or 1000s?
  - emmorais 4y ago
    It depends on which backend you want to use (currently Groth16 or Nova, but more options can be implemented). For example, Nova proof is roughly 8-9 KB. In this situation we have that verification is not constant, for instance, for 2^20 constraints it would take roughly 1s.
    - tromp 4y ago
      And how many constraints would roughly be needed to represent the first case of a million secp256k1 signatures in a SHA256 Merkle tree?