Dynamic Extraction of Multi-Round Knowledge Argument Systems

Hybrid: Geb. 50.34, Raum 252 oder https://i62bbb.tm.kit.edu/b/mic-7xx-rfr

2022-03-08

Konstantin Fickel

15:45

Bulletproofs [5] are a popular proof system in the discrete logarithm setting. They can be used to enable confidential transactions on blockchains. The central component of Bulletproofs is the Inner Product Argument. It proves that two vectors, which have been committed to, result in a certain inner product, using a logarithmic amount of communication rounds in the size of the vectors.

To prove knowledge soundness of those protocols, the emulator first builds up a tree of transcripts and then uses this tree to extract the witness. Since the proof system is based on the discrete logarithm assumption, extraction has to either yield a discrete logarithm relation or vectors the commitments can be opened to.

Hoffmann, Klooß, and Rupp [8] noticed that this extraction process never uses the whole tree of transcripts. In the case of a successful vector extraction, only a linear amount of transcripts is needed; in the case of a discrete logarithm relation being found the amount is quasi-linear in the size of the proof. This is an improvement compared to the quadratic amount required in [5]. To make use of this observation, dynamic access to the tree is required with new transcripts generated on demand. This has been left as an open problem for further research.

This thesis outlines how such a dynamic access to the tree of transcripts may look like: First an abstraction for the sampling behaviour of such an extractor is formalized, based on which it is explained why the commonly used proof technique does not work in this case. Then, the Inner Product Argument and its extraction are described and proven. Finally, a formal framework describing dynamic extraction is specified and important properties are proven.