30 May 2022

Cryptographic Frontier

Open Problems in Decentralized Computation

at Eurocrypt 2022

Workshop on Open Cryptographic Problems in

Decentralized Computation

Decentralized Blockchain Applications rely on a variety of different cryptographic primitives and protocols that directly affect both security and efficiency. Improving these tools is not only of academic interest, but also impacts the security of millions of users. These applications relies on advanced frontier crypto schemes in order to tackle the harsh requirements of scalability and performance that haunt the most popular decentralised systems.

This workshop brings the most interesting and challenging open cryptographic questions that Ethereum, Filecoin and other blockchain systems face, to the attention of academia. We will cover a large spectrum of research topics, such as vector commitments, SNARKs, shuffles, authenticated data structures and more. We will start the day with an update on to the problems discussed at last year's workshop.

The day

Monday May 30

Clarion Congress Hotel, Trondheim

Workshop from 9:00 to 17:00 CET

The sessions

Each session starts with a talk (approx 15 minutes long), which introduces the problem, a tentative solution, and open questions. It is followed by a working group. Sessions are independent i.e. one is not required to understand another.

To participate, register to Eurocrypt 2022 with the option "In-person workshop attendance" and select “Cryptographic Frontier” as your affiliated event for Monday, May 30th.

Workshop program

(Local Time)

Registration 9:30 - 10:00 AM

10:00 - 10:15

Welcome and Intro

10:15 - 10:45

Session 1: Updates from last year workshop (slides)

Dmitry Khovratovich & Mary Maller (Ethereum Foundation)

We will discuss the progress made on the problems discussed at last year Cryptographic Frontier Workshop

Break 10:45 - 11:00

11:00 - 12:00

Session 2: Vector Commitments and Lookups

Anca Nitulescu (Protocol Labs) Space-Time Trade-Offs (slides)

Mary Maller (Ethereum Foundation) Lookup Arguments for SNARKs (slides)

This session will discuss open problems related to two topics:

Space-Time Trade-Offs for Vector Commitments. Vector commitments are designed to enable fast and efficient verification of short opening proofs for values in some committed vector. While we care about the verifier's time and space, what can be done for the prover?

A prover could use some space to store precomputed values in order to save time when generating new opening proofs. While Merkle trees and RSA-based Vector Commitments provide some interesting space-time trade-offs for the prover, we are not aware of any such savings in the pairing-based vector commitments.

Space-Time Matters!

Lookup Arguments for SNARKs. Polynomial commitments imply SNARKs. SNARKs are slow. Slow SNARKs can be made faster using lookups. Lookups are hard to engineer to make SNARKs faster. Faster Lookup Arguments make engineering easy. How fast can we go?

If you are too fast,

Don't Look Up

Break 12:00 - 12:30

12:30 - 13:00

Session 3: Secure Shuffles and Stirs (slides)

Dmitry Khovratovich (Ethereum Foundation)

When people do not trust each other, can they shuffle a set if everyone shuffles only a few? How can a VDF and a Feistel cipher be involved in it? Is it crucial to pre-commit to your shuffle before the run? A number of open questions are exposed in a hot Ethereum 2.0 problem.

See Sam shuffling? said Sarah. Secure shuffles seem so straightforward. Sadly, stubborn scholars still study shuffles. Safe shuffle should supercede secure shuffles, so should semiconfident sailors swim shuffled? Serene studies show secure shuffles so sexy. Stop singing swinging, start securing shuffles!

Lunch 13:00 - 14:30

14:30 - 15:30

Session 4: SNARKs Implementation

Thomas Piellard (ConsenSys) SNARKs on any field (slides)

Omer Shlomovits (Ingonyama) ZK hardware acceleration (slides)

Thomas Piellard, "SNARKs on any field"

SNARKs involve many polynomial arithmetic operations that are best implemented using Fast Fourier Transfroms (FFTs). These operations take place in the subgroup of some pairing-friendly elliptic curve.

A recent work of Ben-Sasson et al. enables doing FFTs over non-smooth fields (ECFFT), it seems now viable to instantiate a SNARK with an elliptic curve of non-smooth subgroup order (any curve with pairings). Particularly, one layer SNARK composition can be achieved with less constraints for the choice of curves (e.g. on recursion with BLS12-381). However there are major limitations of ECFFT that we want to discuss:

- ECFFT requires finding a suitable curve to do the the isogenies walk. This is a similar problem studied in a different field (ECM for factorisation). We will talk about this as a 2-syllow group problem.

- More importantly ECFFT is incomplete. It requires two algorithms (ENTER and EXIT as in the paper notations) that are not algorithmitically described and we think might be very costy.

We will continue our exploration on more efficient SNARKs with discussions on the implementation challenges to construct SNARKS over any field.

Omer Shlomovits, "SNARK hardware acceleration"

We will also discuss ZK Hardware Acceleration: Real-world Zero-Knowledge (ZK) systems open up a fascinating yet complex trade-off space, including prover, verifier, and proof complexity. Most commonly in today’s systems, we encounter computation bottlenecks for prover latency or throughput. As algorithmic improvements are approaching lower bounds, it is time to consider hardware acceleration to meet the needs of concrete applications in web3.

In this talk, we analyze ZK proofs through the lens of hardware engineers. We start by identifying the compute problems underlying ZK systems used in practice. We then discuss different approaches for building ZK HW accelerators and compare GPUs to FPGAs/ASICs.

We move on to describe several acceleration techniques that require specialized hardware and current industry efforts, such as Zprize.

We conclude by presenting open research questions on how to make ZK more hardware friendly.

Break 15:30 - 16:00

16:00 - 16:30

Session 5: Data Retrievability (slides)

Rosario Gennaro & Irene Giacomelli (Protocol Labs)

The data retrievability problem, or: ”I can not force you to speak, but I can make your silence expensive”

Consider the scenario of a decentralized storage network. That is, there is a network of storage providers with storage capabilities and there are clients that delegate the storage of their own data to this network, paying the providers for this service. We assume that the market runs on a blockchain that guarantees that data are stored and providers are paid for this service.

Now that we have guaranteed storage, we want to look at the data retrievability problem. It is natural to assume the a client who stores the data with the providers may ask to retrieve the data (possibly paying for this service). However a “lazy” provider can ignore this request and keeping the data “as hostage”. We can not prevent this behaviour, but we can make it irrational. That is, we need a system that punish a provider not answering a retrieval request. For example, we can think about a smart contract locking down tokes from the provider’s account and which are then burn by the contract active by a client who did not get the data.

However, this system is not resilient to exploitations from malicious miner. How can we prevent this? In other words, how can we device a “proof of deliver” that a provider can use to show its fulfilment of a retrieval request?

Break 16:30 - 17:00

17:00 - 17:30

Session 6: Authenticated Data Structures (slides)

Matteo Campanelli (Protocol Labs)

Lesson to be Learned on Queries on Structured Data

We often care about this setting: committing to some large highly structured data and then prove they satisfy certain properties (while the proofs/commitments are required to be highly succinct and cheap to generate).

This "structure" we assume on the data can span from the simple (a table/KV map) to the complex (a collection of related tables, e.g., a flat database of some sort, or a DAG of related databases, e.g., an object in IPLD, which is a more recursively-flavored beast).

We ask: what are our gaps in the understanding of this problem from the two perspectives of concrete efficiency and that of its theoretical underpinnings? If general-purpose SNARKs are often a solution on paper, they rarely are one ready to be deployed in the real world. Also, maybe extractability is an overkill in certain applications. Commitments with special properties (vector, polynomial, or functional) offer interesting tradeoffs, but they have other limitations.

Can one beef up functional commitments or dumb down general purpose SNARKs to solve this problem?

The Sponsors

The Speakers

Matteo Campanelli (PL)

Rosario Gennaro (PL)

Irene Giacomelli (PL)

Thomas Piellard (ConsenSys)

Dmitry Khovratovich (EF)

Mary Maller (EF)

Anca Nitulescu (PL)

Omer Shlomovits (Ingonyama)

The Venue

Clarion Congress Hotel, Trondheim

Same as Eurocrypt 2022