Lurk – Language for Recursive ZK-SNARKs Inspired by Common Lisp and Scheme

This page summarizes the projects mentioned and recommended in the original post on news.ycombinator.com

Our great sponsors
  • InfluxDB - Power Real-Time Data Analytics at Scale
  • WorkOS - The modern identity platform for B2B SaaS
  • SaaSHub - Software Alternatives and Reviews
  • lurk-rs

    Lurk is a Turing-complete programming language for recursive zk-SNARKs. It is a statically scoped dialect of Lisp, influenced by Scheme and Common Lisp.

    > My understanding is that a SNARK circuit is used to prove a series of computations without revealing any of the inputs or outputs.

    Close: the so-called 'public inputs' must be revealed because these are checked by the verifier. What's neat is that many (even 'most') of the so-called 'private inputs' need not be revealed. This lets you prove statements that have the form, "I know of secret values x, y, z, etc. such that the following arithmetic relationship holds: [statement including public and private inputs]." One of Lurk's contributions is that this 'statement' can express arbitrary computation, including anything requiring unbounded recursion. That's what makes it Turing complete. A traditional SNARK circuit is expressive enough to describe any computation, but the limitation on requiring a fixed size means you have to know (and are limited by) an upper bound on the size of the computation in advance.

    > 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?

    Yes, exactly. You can construct an arbitrary program (say `((lambda (x) (* x x)) public-input)`) and pass that whole expression to the verifier. The prover can then provide the claimed result, which will also be a public input to the verifier, along with a proof that the 'input' evaluates (according to Lurk semantics) to the 'output'. Note that both what I called 'input' and 'output' will be public-inputs used by the verifier.

    > So lurk programs can point to previously proven (and published?) hashes to make provable claims about their calculations?

    Yes, that is one use case. Take the example above: the whole lambda expression I gave as an input example will actually be represented as a 'hash' (a content-address for the complete expression). But the 'interesting' part of the function doesn't actually have to have been given to the verifier. Instead, the prover might have committed to this function previously. The prover then 'opens' the commitment on the provided input. This is possible because the verifier can construct the 'hash' corresponding to the 'input' without knowing the internal hashes of the entire expression. The verifier might only know she is verifying a statement of the form `( public-input)`. But she still knows that the claimed output is indeed an evaluation of the pre-committed secret function because she trusts the cryptographic proof.

    We have an example project dealing with exactly this situation. The examples need a lot of work, but you can see the idea here: https://github.com/lurk-lang/lurk-rs/tree/master/fcomm

    This WIP commit adapts the example to use a more explicit form of commitments and should make clearer what's going on: https://github.com/lurk-lang/lurk-rs/pull/112/files#diff-d6b...

    The initial example took advantage of the fact that all compound Lurk data is produced by hashing anyway.

    > Is this like "merkle-izing" computation?

    You merkle-ize the recipe/program. The computation itself is performed normally (by the prover), but only needs to happen once. Thereafter any number of verifiers can 'check the prover's work' and see that it was performed correctly. Both the input and output to the computation proven can be merkle roots — so the amount of private versus public data can be tuned to the needs of the application.

    > Sorry I'm just really trying to wrap my head around this.

    It's a lot to grok and takes a while (but not too bad if you're really interested). If you follow us on Twitter (https://twitter.com/LurkLab) you'll see when we publish some blog posts in which I hope to walk through examples like this in a lot more detail. That should give a very concrete sense for what is possible and what is involved from a programmer perpsective.

  • zexe

    Rust library for decentralized private computation

    I wonder how this compares to something like zexe (https://github.com/brucechin/zexe). This domain interests me although I have little practical knowledge/experience in it.

  • InfluxDB

    Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  • pact

    The Pact Smart Contract Language

  • Nova

    Nova: High-speed recursive arguments from folding schemes (by microsoft)

    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), 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.

  • alucard

    A common lisp DSL for writing zero knowledge circuits

    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

  • coalton

    Coalton is an efficient, statically typed functional programming language that supercharges Common Lisp.

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a more popular project.

Suggest a related project

Related posts