30 May 2022
Open Problems in Decentralized Computation
at Eurocrypt 2022
Workshop on Open Cryptographic Problems in
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.
Monday May 30
Clarion Congress Hotel, Trondheim
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.
Registration 9:30 - 10:00 AM
10:00 - 10:15
Welcome and Intro
Break 10:45 - 11:00
11:00 - 12:00
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?
Break 12:00 - 12:30
12:30 - 13:00
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
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.
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
Break 16:30 - 17:00
17:00 - 17:30
Matteo Campanelli (PL)
Rosario Gennaro (PL)
Irene Giacomelli (PL)
Thomas Piellard (ConsenSys)
Dmitry Khovratovich (EF)
Mary Maller (EF)
Anca Nitulescu (PL)
Omer Shlomovits (Ingonyama)