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.

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.

• 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.’

Although computational VDFs are marvelous, they suffer one significant problem. Their performance on the key metric of VDFs ($A_{max}$) 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 $A_{max}$ 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 $A_{max}$ 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.’

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.

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.