Privacy enhancing technologies for distributed ledgers

Abstract

In our digital society, proofs of computation provide new means of interaction among distrusting parties. This thesis investigates why these proof systems are especially desirable tools in the Blockchain space. We first provide a formal definition of a Nakamoto-style-Blockchain, and an overview of state-of-the-art ‘privacy enhancing technologies’currently used in these decentralized environments. The main focus lies on ‘pairingbased preprocessed zero knowledge succinct non interactive arguments of knowledge’(zkSNARKs). This thesis also investigates their mathematical foundations and providesthe description and implementation of a zkSNARK construction that is derived froma new type of underlying circuit. This new circuit extends F-arithmetic circuit-basedconstructions to enable proving knowledge of the discrete logarithm on an elliptic curve with just one gate. The prototype is implemented as Golang code and is publicly accessible via Github under a GPL3.0 license. It includes a compiler that translates adomain specific language designed for this purpose efficiently into the form of a ‘quadratic arithmetic program’. This language and its compiler can be used for other types of proofsystems based on F-arithmetic circuits as well.

Die Möglichkeit, Computerberechnungen mit einem Beweis für deren korrekte Ausführung zu hinterlegen, scheint in Zeiten der oft genannten ‘Digitalisierung’ ein vielversprechendes Mittel zu sein, um es Parteien, die einander nicht trauen, zu ermöglichen sich auszutauschen. Diese Korrektheitsbeweise sind gerade im Themengebiet der Blockchain interessante und vielversprechende Kandidaten, um dortige Probleme zu adressieren. In dieser Arbeit untersuchen wir formal, was eine Blockchain im Sinne Nakamotos auszeichnet, und inwiefern sogenannte ‘Privacy Enhancing Technolgies’ in diesen dezentralen Systemen Anwendung finden. Das Hauptaugenmerk legen wir dabei auf ‘pairing-based preprocessed zero knowledge succinct non interactive arguments of knowledge’ (zkSNARKs). Wir untersuchen deren mathematische Grundlage und entwickeln unsere eigene zkSNARK Konstruktion. Diese basiert auf einer Erweiterung der gängigen F-arithmetischen Schaltung, die neben arithmetischen Operationen auch die der skalare Gruppenexponentiation auf elliptischen Kurven unterstützt. Die Implementierung ist in der Sprache Golang verfasst und unter einer GPL3.0 Lizenz auf Github zugänglich gemacht. Das Programm übersetzt eine eigens dafür entwickelte Programmiersprache in die Form eines ‘Quadratic Arithmetic Programs’ und kann daher über unsere Arbeit hinaus in Beweissystemen basierend auf F-arithmetischen Schaltungen eingesetzt werden.