Proving computation and storage: SNARKs and more

A proof system is a protocol in which one party (called the prover) wishes to convince another party (called the verifier) that a given statement is true. A proof of knowledge is a protocol in which the prover succeeds in “convincing” a verifier that it knows something (a password, the input to a computation, etc.) associated with the statement. For example, if the statement is “I am authenticating using my password as Alice.”, the prover should show knowledge of the secret password of Alice. We will study different kinds of such protocols including:

• interactive proofs,
• zero-knowledge proofs,
• Sigma-protocols,
• succinct (non-interactive) arguments.

When it comes to proving storage of some large data, a more specialised cryptographic primitive that solves this are Vector Commitments (VC). These are cryptographic primitives that allows one to commit to a long vector and then “open” some of its positions efficiently by showing a small proof.  We will focus on:

• pairing-based polynomial commitments (KZG),
• inner-product and functional commitments,
• look-up arguments.

Applications

This series of lectures will also cover recent advances and some use-cases of the presented schemes. SNARKs and vector commitments are increasingly recognized as a central tool to scale highly decentralized networks of large size and whose content is dynamic. during the lectures, we will got familiar with such applications and with additional key properties that proofs should satisfy in such settings: succinctness for proofs, efficiency for verification, possibility of aggregation, etc.

 

Material

Materials on sciebo (available until 2024-12-31 with the password told in class).