2023-03-24

The road to Lurk

Chhi'mèd Künzang

Cryptography

In early 2018, I joined the Filecoin team at Protocol Labs as a contractor. I was fascinated by the promise of decentralized storage and the possibility of consensus based on storage power. I eagerly devoured the Filecoin whitepaper and puzzled over how the proofs were supposed to actually work. Sufficiently persistent enthusiasm paid off, and I ended up joining Protocol Labs full-time to lead the Filecoin Proofs implementation.

Today is my last day at Protocol Labs, after which I am moving on to be the CTO of Lurk Lab. The last five years have gone by in the blink of an eye. As is common in transition, I find myself reflecting on how the past became the present and on the future to come. This post is a whirlwind summary of some of the highlights of my research/development work at Protocol Labs. Because this has been a period of intense and fruitful focus, a narrative thread also emerges.

This post is several things:

• A retrospective tour of some things I worked on while at PL, providing some insight into how the sausage is made.
• A summary of the latest state of the VDF project and a first look at some related research outputs.
• The (eponymous) road to Lurk.

Filecoin

Much has been written about Filecoin and the Filecoin Proofs. Here are a few notes about lesser corners of the work that went into arriving where we did.

One of the earliest abstractions we adopted was embodied in the CompoundProof trait. I am both proud and horrified that I broke ground on what would become a central part of our proofs implementation while simultaneously learning Rust and the underlying cryptography: research development at its finest fastest. More seriously, though, CompoundProof formalized a relationship between ‘vanilla’ proofs and their zk-SNARK counterparts, initializing a thread of investigation eventually leading to Lurk.

On the way to mainnet, we needed a way to model the many parameters associated with the network and especially candidate proof constructions. Hence was born Orient (a relational language for expressing systems of bi-directional arithmetic constraints, implemented in Common Lisp). From this, we built the Filecoin Ubercalc. Though crude, it proved powerful and flexible enough to interactively model the characteristics of proposed candidates and their parameterizations in order to make difficult time-critical decisions about what we could deploy on time, with acceptable performance, and without sacrificing network security.

One thing that became clear in the Ubercalc analyses was that none of our then-current candidate hashes struck the right balance of performance inside and outside arithmetic circuits. Whereas several years earlier, we had ruled out Poseidon as being ’too new’, we decided making a (hedged) bet on SNARK-friendly hashing was our best option. To that end, I created Neptune, one of the first production implementations of Poseidon, and as far as I know, the first to tackle the sparse matrix optimizations enabling best non-circuit performance for higher arity hashes.

• Because we needed to build Merkle trees as fast as possible, that included a GPU implementation (Triton).

• Don’t get me wrong, the initial GPU implementation was nowhere near as performant as possible – though Supranational has more recently done tremendous work to squeeze out the best performance. Rather, it was ‘fast to build’ for someone who didn’t know GPU programming. I used Futhark – a purely-functional GPU programming language (Retrospective on an implementation of the Poseidon hash function in Futhark).

  • Sometimes research engineering demands a dose of self-medicated rabbit-holing, and the requisite implementation of Finite Fields for Futhark helped me through those dark days.

Along the way, a number of long-running SNARK engineering research projects allowed us to scout optimal paths,

• In the end, we managed to launch in 2020 with what soon became the largest and most performant SNARK deployment ever (at least at the time we published zk-SNARKs for the world!).

VDF

After mainnet launch, I transitioned away from maintenance of the Filecoin proofs to focus on accelerating usability of verifiable delay functions. There were several potential use cases for VDFs in Filecoin, and my aim was to help make a viable implementation available to such downstream applications. As long as it remained a 'someday' technology, practical research and development could not assume it.

As importantly, in targeting this project as a means to drive SNARK research, I identified VDFs as an optimal test case for recursive SNARK technology generally. The extreme simplicity of an iterative algorithm like a VDF would allow us to push proving system design and implementation forward as rapidly as possible – if only by providing demand and supporting early adoption. By focusing on an almost trivial computational problem, we incidentally ensured that success in proving would accrue almost entirely to the underlying proving system.

At the same time, this focus on ultimate simplicity in the circuit to be proved exerted a profound influence on the work (see below) which would become Lurk.

Computational VDF

The dominant approach to VDFs involves functions that are slow to compute but fast to verify for computational reasons.

• To that end, in November 2021, I organized a collaboration to build a Practical SNARK-based VDF.

• I built and maintained an initial VDF prototype, allowing iteration on the design and coordination between the hardware, algorithmic, and proof design – including explorations of optimal parallelism for min-root informing the eventual evaluator ASIC design (see below).

• In Open VDF: Accelerating the Nova SNARK-based VDF, Supranational writes:

‘Approximately one year ago, we announced a collaboration with the Ethereum Foundation, Filecoin Foundation, Supranational, Microsoft, and the Electric Coin Company to improve the performance of SNARKs, and to make SNARK-based Verifiable Delay Functions (VDFs) practical. VDFs have the potential to improve the security, privacy, and scalability of blockchain platforms and are being evaluated by a number of blockchain platforms, including Ethereum, Filecoin, Tezos, and Zcash. Over the past year, we have collectively made a huge amount of progress towards that goal, including an ASIC implementation of the MinRoot algorithm, implementation of a recursion-enabled proof system (Nova), and support for GPU accelerated proof generation. While we have laid the groundwork to make SNARK-based VDFs practical, these developments will have much wider-ranging implications. For instance, through the development of a performance approach to incrementally verifiable computation, we have made practical novel and powerful use cases such as true zero-knowledge VMs like Lurk. Furthermore, in addition to these SW developments, earlier this year we received initial prototypes of the MinRoot ASIC design, manufactured on 12 nm technology. Over the coming months, we will integrate the MinRoot ASIC with the Nova proof system and produce an end-to-end implementation of SNARK-based VDFs. Once this is complete, we will be sharing this implementation with the community and are excited to see how this new cryptographic primitive can improve the security and scalability of blockchain networks.’

Fundamental Latency VDF

Although computational VDFs are marvelous, they suffer one significant problem. Their performance on the key metric of VDFs (Amax) depends on engineering attempts to implement an evaluator which is as fast as possible. This fails to whatever extent an attacker can accelerate the computation. In practice, this means computational VDFs with an Amax very close to 1 are not realistic.

What this means is that a single VDF computation cannot be used as fine-grained timer for applications that require high assurance that no attacker can obtain the result with less delay than an honest party. Some of the motivating Filecoin applications required this property in order to satisfy their economic requirements (essentially the Amax acted as a cost multiplier).

In the spirit of stimulating the otherwise impossible (it was part of a post-mainnet vibe that possessed me), it occurred to me that communication latency does indeed allow for uncheatable minimum times (with the speed of light famously providing a universal speed limit).

• I wrote up my initial, partially-baked thoughts in a starry-eyed document titled SpaceVDF.

• The ideas were promising enough that I followed up with Cryptosat, and after some discussion, we commissioned a system-level trade study.

• I’m excited to announce the publication of the SpaceVDF White Paper.

‘In this document we aim to evaluate how VDF algorithms based on physical limits can be implemented in satellites and which physical properties / or roles of physics we can utilize to guarantee the passage of time. The goal of this study is to perform principal system analysis, identify main issues and risks, propose a path for derisking and come up with a budget and timeline for a suitable satellite (or satellite constellation).’

• Just as my seed ideas were only suggestive of the actual engineering that would be required for any real-world deployment of a SpaceVDF, the cryptographic constructs imagined were also vague and incomplete. To that end, I connected with Bernardo David, who agreed the core ideas were interesting enough to develop further.

• We sponsored Bernardo and his co-authors to put meat on the bone, and the result has just been released as an eprint: CaSCaDE: (Time-Based) Cryptography from Space Communications DElay

‘In this work, we investigate how to construct time-based cryptographic primitives from communication delay, which has a known lower bound given the physical distance between devices: the speed of light. In order to obtain high delays, we explore the sequential communication delay that arises when sending a message through a constellation of satellites. This has the advantage that distances between protocol participants are guaranteed as positions of satellites are observable, so delay lower bounds can be easily computed. At the same time, building cryptographic primitives for this setting is challenging due to the constrained resources of satellites and possible corruption of parties within the constellation.

We address these challenges by constructing efficient proofs of sequential communication delay to convince a verifier that a message has accrued delay by traversing a path among satellites. As part of this construction, we propose the first ordered multisignature scheme with security under a version of the discrete logarithm assumption, which enjoys constant-size signatures and, modulo preprocessing, computational complexity independent of the number of signers. Building on our proofs of sequential communication delay, we show new constructions of Publicly Verifiable TLPs and VDFs whose delay guarantees are rooted in physical communication delay lower bounds. Our protocols, as well as the ordered multisignature, are analyzed in the Universal Composability framework using novel models for sequential communication delays and (ordered) multisignatures. A direct application of our results is a randomness beacon that only accesses expensive communication resources in case of cheating.’

Lurk

Of the potential applications in which VDFs might play a critical role, one of the most interesting was Hierarchical Consensus (which has since been re-branded as Interplanetary Consensus). However, following a worrisome trend, the more I pondered it, the less obvious it became that the application would be straightforward. Whereas the VDF (see above) represented the simplest possible proof statement, it seemed more elaborate statements would need to be proved in order to serve the needs of substantial applications like hierarchical consensus.

I wrote Hierarchical Consensus with VDFs and/or Turing-Complete SNARKs before Chat GPT came along, so the concept of LLM hallucination was not yet widespread. Nevertheless, it would not be too far off to view this document and the prompt that is its epigraph to be a fever dream. Please note that it was written in mid-2021 and predated current work on IPC, so nothing about that project should be inferred from its first-principle extrapolations. As it turns out, the Turing-Complete SNARKs part may indeed provide high value to IPC (or a system like it), even if the VDFs prove dispensable.

Gripped by further self-medication of research development fever, I saw fit to focus on what seemed another missing piece to be forced into existence ahead of its time, leading to the MetaProof project – described as follows:

‘The first step of the MetaProof project follows the shortest path to Turing complete SNARKs via recursive computation. We design a minimal Lisp-family language using SNARK-friendly hashing for memory access — and implement an arithmetic circuit proving one reduction step of this language’s expression evaluator. Combined with any IVC-like construction (including SnarkPack + input aggregation), this will allow succinct proofs of arbitrary computation from a single circuit. In addition to the operational benefits of avoiding the research/development lifecycle associated with new circuits (potentially including trusted setup), this will allow entirely new categories of computations to be proved.’

One thing led to another, and Lurk was born.

In house style, implementation led articulation, but now we have an articulate explanation as well: LURK: Lambda, the Ultimate Recursive Knowledge.

‘We introduce Lurk, a new LISP-based programming language for zk-SNARKs. Traditional approaches to programming over zero-knowledge proofs require compiling the desired computation into a flat circuit, imposing serious constraints on the size and complexity of computations that can be achieved in practice. Lurk programs are instead provided as data to the universal Lurk interpreter circuit, allowing the resulting language to be Turing-complete without compromising the size of the resulting proof artifacts. Our work describes the design and theory behind Lurk, along with detailing how its implementation of content addressing can be used to sidestep many of the usual concerns of programming zero-knowledge proofs.'

And that brings us up to the edge of the present.

Lurk Lab calls.

PL has partnered with Lurk Lab to bring general-purpose zero-knowledge proofs to Filecoin, and is our largest investor.

Here’s a brief (if imperfect) Lurk demo.

Chhi'mèd Künzang, 24 March 2023

1. Technically, “brought into the light of the solar system,” per @jsoares.