A series of in-depth articles overviewing the technologies utilized by the Dusk Network protocol.
Welcome to our brand new series! In recent months, our communication channels have been bombarded with questions about the technical side of the project, which inspired us to start a series covering the technologies that have become the cornerstone of our protocol. However, before we begin, the reader has to be made aware of the following:
This article contains mathematical formulas. Stick with us! They don’t bite. We will guide you through.
Introduction
“I think zero knowledge proofs are one of the most amazing notions in computer science, what we have done is to combine it with another notion - that it’s easier to prove that a computation can be done correctly than it is to actually compute it.” — Rafael Pass
Zero-knowledge proofs are a type of interactive proofs where a prover can prove the knowledge of value x without revealing additional information about the value.
Aside from the standard requirements for the fulfilment of two properties:
1. Completeness and
2. Soundness,
zero-knowledge proofs have to satisfy a third property - zero knowledge.
Completeness is satisfied when a verifier can be convinced that the statement is true if the statement is indeed true, soundness is satisfied when no cheating prover can convince a verifier that the statement is true, except with negligible probability if the statement is false and zero knowledge is satisfied when a verifier cannot determine any additional information apart from the fact that the statement is true.
Originally discovered in the 80s, zero-knowledge proofs have gone through multiple breakthroughs throughout the past 3 decades. Before looking into the nits and grits, the reader has to be briefed on problem classes in computational complexity theory relevant to the discussed topic.
P vs NP
A deterministic system is a system in which no randomness is involved, it always produces the same output from a given starting condition or initial state.
P is a class of decision problems which can be solved via a deterministic Turing Machine in polynomial time (more on that later).
NP is a class of decision problems which cannot be solved via a deterministic Turing Machine in polynomial time but has a proof which can be produced in polynomial time. NP decision problems can be solved via a non-deterministic Turing Machine in Polynomial time.
NP-complete is a class of decision problems which can define every other NP class problem.
Zero-knowledge proofs rely on the fact that it is unknown whether NP class problems can be solved quickly, which forms the basis of the P vs NP problem, an unsolved fundamental problem of mathematics (one of the seven Millennium Problems!). If P = NP is ever to be proven to true, then almost the entire field of cryptography would instantly be rendered insecure.
Back to the mysterious-sounding Turing Machines and time complexity. Due to the difficulty of creating models based on the real-world machines, mathematicians have defined an abstract machine, known as Turing Machine. Named after Alan Turing, the famous British mathematician and computer scientist, Turing Machine has an infinite memory tape which is used to read and write data on a set of predefined rules. Turing machines can be deterministic (DTM) and non-deterministic (NTM). A DTM can only perform one action per step, based on the latest symbol read by the tapehead and the current state of the machine. On the other hand, an NTM can perform numerous actions per step. The amount of time a Turing Machine requires to solve a certain problem is defined by time complexity. While there are numerous time complexity classes defined, we are only concerned with polynomial time complexity. The algorithm is deemed to be solvable in polynomial time if the required number of steps to complete an algorithm for a certain output is no more than O(n^k), where k is the security parameter of the algorithm and n is the complexity of the input.
History
Now that the reader understands how the problems are defined, time to shift our attention to the history of zero-knowledge proofs and why decision problem classes are important. I was not lying when I said that zero-knowledge proofs have gone through multiple breakthroughs relevant to our use case.
Firstly, Goldreich et al had produced a zero-knowledge proof for a graph-colouring problem. Because the graph-colouring problem is an NP-complete, every NP problem can be reduced to a graph-colouring problem in polynomial time, resulting in a zero-knowledge proof capable of producing proofs for any NP class problem. Secondly, Fiat and Shamir had defined a technique known as Fiat-Shamir heuristic, designed to convert an interactive proof of knowledge scheme into a non-interactive one. Micali et al had proposed a scheme alternative to Fiat-Shamir heuristic, which utilized a common reference string (CRS) and is beyond the scope of these series. Thirdly, Bitansky et al had defined a protocol called Succinct Non-Interactive Adaptive Argument of Knowledge (SNARK) for NP class, which was eventually adapted to zero-knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARKs) for the ZCash implementation. Fourthly, Benedikt Bünz et al, had presented Bulletproofs, a zero-knowledge protocol which requires no trusted setup.
Elliptic Curves
To understand curve pairings and zk-SNARKs, the reader has to first fathom the beauty of elliptic curves.
Elliptic curves are algebraic plane curves defined over a field (more on that later). Funnily enough, elliptic curves have almost nothing to do with ellipses, aside from a very loose connection which is beyond the scope of these series. A short Weierstrass form equation of the elliptic curve is:
However, aside from a Weierstrass form, elliptic curves can be defined in multiple birationally equivalent forms. In layman terms, birational equivalence is a term that defines two isomorphic (one-to-one corresponding) geometric objects as identical. Secp256k1, an elliptic curve utilized in Bitcoin, looks the following way when plotted over a field of real numbers:
Unfortunately, real numbers have almost no practical application in modern cryptography, so mathematicians resort to using finite fields (a set of finite number of elements) with a prime or power of prime order (number of elements in the finite field). When secp256k1 is applied over a finite field, a curve plot looks drastically different:
Elliptic curve group operations (the operations are not identical to their arithmetic equivalents and represent an abstract generalization) include addition, subtraction and multiplication. A set of points on a curve plotted over a finite field has to include a group identity point - O (akin 0 being an identity element of arithmetic addition; i.e. 5 + 0 = 5, 14 +0 = 14, etc.). Due to the use of the finite fields, the curve operations adhere to the rules of modular arithmetics and “wrap around” the order of the field:
Finally, the reader has to be made aware of two types of point additions on an elliptic curve. The first one being an addition of two distinct points on a curve (P and Q):
and the second one being an addition of a point to itself:
Elliptic curve multiplication can be effectively described as repeated addition a point - 4 P = P ⊕ P ⊕ P ⊕ P.
Part II will continue exploring elliptic curves, as well as introducing curve pairings, zk-SNARKs and Bulletproofs. Do not forget to subscribe to our publication to make sure that you don’t miss the continuation of the first in-depth overview of the series!
How to learn more about Dusk Network
Dusk’s technology disintermediates regulated (financial) markets. Our infrastructure tackles the challenge at the deepest layer. With Dusk you are in charge of your securities from start to finish. You can issue, register, and trade digital securities while complying with all regulatory requirements.
Please consider joining us at the following media:
Website: https://www.dusk.network
FAQ: https://www.dusk.network/faq
Telegram: https://t.me/dusknetwork
Twitter: https://twitter.com/duskfoundation