Dynamic Extraction of Multi-Round Knowledge Argument Systems

Bulletproofs sind ein beliebtes auf der diskreten Logarithmus-Annahme basierendes Beweissystem. Dieses kann unter anderem verwendet werden, um vertrauliche Transaktionen auf Blockchains zu ermöglichen. Die Hauptkomponente davon ist das sogenannte Inner Product Argument, bei welchem für zwei Vektoren, auf welche Commitments bekannt sind, bewiesen wird, dass diese ein bestimmtes Skalarprodukt besitzen. Dabei wird nur eine logarithmische Rundenanzahl in der Länge der Vektoren benötigt mit einer geringen, konstanten Anzahl an zu sendenden Elementen.
Um Knowledge Soundness für diese Protokolle zu beweisen, muss ein Emulator angegeben werden. ... mehrDieser baut gewöhnlicherweise zuerst einen Transkriptbaum auf und nutzt diesen dann, um die Vektoren als Zeugen zu extrahieren. Da das Beweissystem auf der diskreten Logarithmus-Annahme basiert, liefert die Extraktion also entweder einen diskreten Logarithmus oder Vektoren, die die Commitments öffnen.
Hoffmann, Klooß und Rupp [8] haben bemerkt, dass beim Extraktionsprozess nie der gesamte Transkriptbaum benötigt wird. Im Falle einer erfolgreichen Vektorextraktion werden nur eine lineare Anzahl an Transkripten in der Größe des Zeugen verwendet; wenn ein diskreter Logarithmus gefunden wurde, benötigt man eine quasi-lineare Anzahl. Dies ist deutlich besser als die quadratische Anzahl an Transkripten aus dem Bulletproof-Papier [5]. Um diese Beob achtung nutzen zu können, wird ein dynamischer Zugriff auf den Transkriptbaum benötigt. Dieses Problem haben die Autoren für weitere Forschung offen gelassen.
Diese Masterarbeit beschäftigt sich damit, wie ein solcher dynamischer Zugriff auf den Transkriptbaum aussehen könnte: Zuerst wird eine Abstraktion des Transkriptanfrageverhal- tens des Extraktors formuliert, anhand derer dann die Grenzen der bisherigen Beweisstrategie aufgezeigt werden. Außerdem werden das Inner Product Argument und dessen Extraktion konkretisiert und bewiesen. Zum Abschluss wird ein formelles Framework für die Beschreibung der dynamischen Extraktion und des dynamischen Transkriptbaumaufbaus aufgezeigt und wichtige Eigenschaften desselben bewiesen.

Bulletproofs 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.
... mehr
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.