Cryptographic Frontier

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

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

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!

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.

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?

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?