0.7Eötvös Loránd University

Faculty of Informatics

Proof of All

Verifiable Computation in a Nutshell

0.5Dr. Peter Ligeti

Dr. Andreas Peter

University of Twente

Mr. Áron Szabó

0.5Mario A. Barbara

MSc. Computer Science

Budapest, 2019

Abstract Recent advances in the cryptographic field of
“Zero-Knowledge Proofs” have sparked a new wave of research, giving
birth to many exciting theoretical approaches in the last few years.
Such research has often overlapped with the need for private and
scalable solutions of Blockchain-based communities, resulting in the
first practical implementations of such systems. Many of these
innovative constructions have developed in parallel, using different
terminologies and evolving into a fragmented ecosystem, calling for
their consolidation into the more stable domain of “Verifiable
Computation”. In this master thesis I propose a unifying Verifiable
Computation model for the simplification and efficient comparison of all
cryptographic proof systems. I take advantage of this model to analyse
innovative technologies (Homomorphic Authenticators, Verifiable Delay
Functions) which developed into their own specialised domains, and I
attempt to make them more accessible for newcomers to the field.
Furthermore, I expand on the future of Verifiable Computation, Universal
proof compilers and “Proofs of All”, by approaching the
state-of-the-art zk-STARK construction from a more accessible and
informal design perspective. Thanks To
those who supported me in times of need, and to those who gave me
technical advice. In particular: Mamma e Papà, prof. Ligeti, Mathijs,
Eszter, István. Let's shoot for the moon. If we miss, we'll
still land amongst the stars.

CHAPTER: OBJECTIVES

The objective of this MSc thesis is to tackle innovative technologies
from a unifying perspective, prioritising simplicity and understanding
over obscure constructions, and benefitting further popularisation of
the cryptographic proofs domain. My main incentive for writing this
thesis is the conflict of interest that exists in the security field
between the desire to exploit innovations in cryptography for building
disruptive technologies (e.g. the “blockchain revolution”[for
a list of companies currently investing in blockchain, see
[ref-blockchain-forbes1]]), and the
complexity and knowledge barrier required to understand them, which
leads to consistent misinformation in the market (e.g. the “Bitconnect
scandal” [ref-bitconnect2]) as well as in
developer channels, and fragmentation within the research community.

The domain I target is that of cryptographic proof systems, and,
specifically, I gather them under the umbrella term “Verifiable
Computation”. There are 3 thesis objectives which this work
hopes to achieve:

* A Unifying Model

for the cryptographic Verifiable Computation domain. The idea is to
select and define the most important and comprehensive properties that
have been spread out over various VC technologies in the course of
more than 3 decades, sometimes using different names and definitions,
By using a standardised model for defining protocols, researchers can
attempt to merge the fragmented domain of cryptographic proofs, and
thus unite their efforts under a single research domain.

* Technical Analysis

of VC technologies, revisiting exciting and correlated protocols using
the unifying model. While the focus is kept only on more favoured
constructions of recent years, I wish to help new researchers get
quickly acquainted with the VC landscape, hopefully leading to further
popularisation and systemisation of the domain.

* A Simplified Guide

to understanding the VC domain and its prominent technologies. This
“layman's view” of core cryptographic properties is achieved through
uncompromisingly logical and verbose debates on each technical design,
where no assumptions are left to the imagination. While there are many
formal definitions used to organise technical details, they are always
accompanied by informal descriptions. I believe in simplifying
technical constructions as much as possible, as it is paramount to
their implementation and diffusion in the engineering field; it also
stimulates further research, as the cryptocurrency community has

This thesis is divided into 3 chapters, which reflect the objectives set
forth during the development of this work. Chapter I,
”Introduction and VC Model”, discusses the history behind
proof protocols while giving a gentle introduction to the topic,
progressively presenting my systemising model for understanding and
analysing VC protocols and properties. Chapter II,
”Non-universal VC Protocols”, introduces and gathers currently
expanding and innovative VC technologies (i.e. HAUTHs, VDFs) which have
previously been considered within separate domains, offering a
comprehensive analysis under the model provided in the first chapter.
Chapter III, ”Universal VC Compilers”, introduces to
our model and breaks down state-of-art prominent VC technology
(i.e. STARKs) which has yielded groundbreaking results, with the
potential to revolutionise the cryptographic community as well as
disrupt the cryptocurrency market itself.

CHAPTER: INTRODUCTION AND VC MODEL

Throughout the past few decades, our society has put a great deal of
effort into developing technologies upon which to build trusted
platforms and services. Along with this explosion of services, the
Internet has brought digital freedom into our daily lives. The latest
example of this is distributed networking (e.g. Bitcoin, Ethereum),
which aims to replace important societal functions. This latest trend
marks an important milestone of our globalised society: the time has
come to build trustless platforms, built upon technologies we can
all indiscriminately trust.

The services we are speaking of take electronic form and exist only in
the realm of Computer Science, which imposes restrictions on what
security and trust really mean, expressed fundamentally in the form of
Cryptography. Cryptography the art, Cryptography the science, has been
developing at an accelerated rate of research ever since human
conflict,[it appears that Caesar was also a big fan of
cryptography :)] and the need for trusted communication, has existed.
What we deal with in this thesis is “how to trust someone doing
something with some secret data”. That phrase might seem
a little vague, but I promise: it encompasses so many notions of
computer science and cryptography that it extends to virtually any
computation on paper or silicon. To define this domain, I'll use the
term “Verifiable Computation” (or VC).

In order to explain what it means to prove computation, I would
like to start by taking a brief look at the most common form of provably
secure computation since the birth of the Web: Authentication (Section
<ref>). Afterwards, I'll move on to define formally (and
informally) what generic cryptographic proofs entail (Sections
<ref>, <ref>); then how to perform
privacy-friendly computations of hidden variables using Zero-Knowledge
Proofs (Section <ref>); then, how to do this without multiple
rounds of communication (Section <ref>), more efficiently and
with less communication overheads (Section <ref>), as well as
other VC properties and open questions (Section <ref>). For
a discussion on how to put it all together in a single convenient
package, please check Section <ref> in the chapter on Universal
Verifiable Computation.

§ IDENTIFICATION SCHEMES AND AUTHENTICATION

Before we talk about Verifiable Computation, let's scale down a bit and
talk about a simpler concept: Identification Schemes. The process of
authenticating a user, which simply defines a Prover showing to a
Verifier that he knows a specific non-deterministic secret relating to
his publicly known identifier, has roughly evolved under the three
following cryptographic constructions.

§.§ Simple Password-based

In this naïve approach the Verifier doesn't trust the Prover, so he asks
him to send over the secret password (i.e. “knowledge witness”) so
that he may verify it.

\[Prover \overset{password}{\rightarrow} Verifier\]
This is an extremely
flawed protocol because:

* the whole secret is revealed to the Verifier (if the Prover actually
knows the password, that is);

* and anybody else looking at this conversation;

* the secret password needs to be well protected and stored by both

The following solutions have been devised to improve this method:

* N/A (it is a requirement of the protocol);

* secure unicast communication channels, e.g. HTTPs;

* the Server stores the password in Hash+Salt format, or Encrypted
format. This helps take stress off hacked servers whose database is
compromised, as long as the hack is detected (otherwise, the webpage
can be modified to redirect login attempts). Another solution is to
have an auxiliary check (called Two Factor Authentication, or 2FA)
using one-time tokens sent via SMS (or an app); unfortunately this is
mainly a convenient hack invented by the industry to patch up the
inherent weaknesses of this authentication approach, and it is as
secure as the device and communication used to receive the token, as
well as the token generation process itself.

Even though Simple Password-based authentication is a very
straightforward interaction (the user types into a text box) it still
conveys a false sense of security, leads to many failed login attempts
(due to typing mystakes) as well as poor password generation habits by
lazy or misinformed users.

§.§ Challenge-Response Authentication

In this approach neither party can trust the other, or the communication
channel may be unsafe, so they take advantage of any “hard
cryptographic problem” to challenge knowledge of the secret.
Essentially, Asymmetric Encryption and Signature schemes help provers
avoid revealing their secret to malicious verifiers.

\[Prover \overset{challenge}{\leftarrow} Verifier
\\Prover \overset{response}{\rightarrow} Verifier\]
(where the
challenge is a random number chosen by the Verifier, which the Prover
must use to generate as response a unique signature or reveal a random
message previously encrypted by the Verifier.)

This method is already a huge improvement over the previous one, and yet
it has received very little adoption amongst the most popular Web
services, even though it could easily be implemented through browser
plugins and software wallets. In fact, its most widespread adoption
seems to be physical authentication cards, used for traditional banking
transactions at ATMs or for authorising entry to company offices.

There is still one small issue: Challenge-Response protocols still
reveal some information, such as unique signatures or decrypted
cipher-texts. While Encryption and Signature schemes are chosen to leak
as little information as possible (e.g. Computationally
Indistinguishable from random values), there is still something to be
learned from selective forgery attacks (for signatures) and chosen
cipher-text attacks (for encryption); should the underlying
cryptographic scheme be broken, the credentials and privacy of the users
might be compromised.

§.§ Zero-Knowledge Identification

Neither party trusts the other. With this technique exactly
nothing about the secret is revealed to the Verifier, except
that it is valid. The secret to achieving this marvellous result lies
within Interactive Proof Systems and their properties, which we will
discuss in the rest of this chapter. A common approach to such protocols
is through one or more rounds of interactivity:

\[\textit{commit step}\begin{cases}Prover \overset{statement}{\rightarrow} Verifier\end{cases}
\\\ \textit{round}\ i \begin{cases}
Prover \overset{challenge}{\leftarrow} Verifier
\\Prover \overset{proof}{\rightarrow} Verifier\end{cases}\]

Alternatively, there is a field of protocols which performs transparent
preprocessing and then sends off a single large proof to be
probabilistically checked offline:

\[Prover \overset{large\ proof}{\rightarrow} Verifier\]

§ THEOREM PROVING AND INTERACTIVE PROOFS

The roots of Verifiable Computation extend all the way to Theorem
Proving, when mathematicians still wrote their proofs on paper. If we
wish to convert mathematical theorems to the domain of computer science,
we should take a look at the well fleshed out theories of NP complexity
classes; here is an informal definition of NP Theorem Proving:

NP Languages
\(Th \in NP \iff \exists \textit{ "witness" } w : \textit{ Th is "easy" to verify using } w\)

Note: You should look at the witness as a sequence of logical
deductions which start from truthful statements and lead all the way to
the theorem claim:

\[\textit{axiom(s)} \implies \overbrace{... \implies ... \implies ... }^\textit{witness} \implies Th\]

If one part of the sequence is already known to the Prover, the
witness represents the part which is not known.

This definition was extended in 1985 by
[ref-GMR854] to represent an Interactive Proof
System IP:

IP Languages

\[\textit{Given }
\begin{cases}
P_\text{UNBOUNDED}, V_\text{POLY} \in ITM \textit{ (Interactive Turing Machine)} \\
L \subseteq \{0,1\}^* \in NP-lang \\
n \textit{ input size}, c \textit{ large constant} \\
w \textit{ secret witness of P} \phantom{(??) define as set of implications…} \end{cases}
\\
\textit{Then } X \in L \iff
\\\land\begin{cases}
\textbf{Completeness} \iff \forall \textit { input } X \in L \textit{ to }(P, V): Pr[V \textit{ accepts } X] \geq 1 - \frac{1}{n^c} \\
\textbf{Soundness}\iff \forall P’_{POLY} \in ITM \land X \notin L \textit{ input to } (P', V): Pr[V \textit{ accepts } X] \leq \frac{1}{n^c} \\
\qquad\textit{or} \iff \forall P'_{POLY} \in ITM \land X \notin L \textit{ input to } (P', V):
\\\quad\qquad \Big(Pr[V \textit{ accepts } X] \geq 1 - \frac{1}{n^c} \implies
\\\qquad\qquad\exists \textit{ "Extractor" } E_{POLY} \in ITM : \exists R \subseteq \{0,1\}^*: E(X) = R(w)\Big)
\end{cases}\]
(please note that we've defined the language as NP,
but IP protocols have been shown to support even more expressive spaces
such as PSPACE or even NEXP)

These systems are often called “Proofs (or Protocols) of Knowledge”,
because the Completeness property defines a protocol (i.e. set of rules)
to follow in order to accept a given statement, and the Soundness
property implies instead the existence of some sort of “knowledge”
(also known as “witness”), needed to distinguish right from wrong. The
alternative definition of Soundness, which makes use of an Extractor
machine, is typically used to single out unique Knowledge which is
possessed by the Prover, and is useful for understanding
“Zero-Knowledge Proofs of Knowledge”. Here is a more intuitive
definition of those properties:

if the statement \(X\) is valid, then there is an “easy” way to prove
it using the protocol. The Verifier will be able to efficiently check
this in polynomial time. In order words: all valid statements are
always accepted.

if the statement \(X\) is false, then there is “almost” no way to
prove it. The Verifier only needs to trust its own knowledge and
randomness to disprove false proofs from an all-powerful Prover. In
other words: all invalid statements are always rejected.

(When discussing the Extractor, the key to understanding the
definition is that it shouldn't be possible to accept false statements,
unless the illegitimate Prover was somehow capable of extracting the
witness, or a relationship on the witness, from the statement \(X\)
itself in order to use it.)

An important security observation to make, especially when considering
the second definition for Soundness, is that there is no restriction to
the amount of “knowledge leaked” by the execution of an IP instance.
This essentially means that the Prover could naïvely just send his
secret password (i.e. witness) over, and the protocol might still be
valid. Restrictions on such flaws, as well as the importance of
Interactivity, will be added by the Zero-Knowledge definition.

A second important security observation is that the Soundness property
is so vague that it does not really provide any security guarantee that
the statement \(X \in L\) will be hard to prove for cheaters, only that
it should not be possible to prove \(X \notin L\). In fact, if the
language \(L\) trivial enough, it might even be possible to randomly
choose any \(X \in L\) and extract the witness required to prove it.
Thus, the security of our proof lies entirely within the chosen language
\(L\), which is typically based on some hard cryptographic problem such
as finding the prime factors of a large number.

NOTE: While we've defined soundness based on negligible
probability, practical constructions only require \(Pr < \frac{1}{2}\),
and repetition is employed to achieve the definition above. Also, almost
all practical systems have perfect completeness (\(Pr = 1\)).

§.§ Probabilistically Checkable Proofs

There is an alternative field of cryptographic proof systems that is
roughly equivalent to IPs, but uses different constructions:
Probabilistically Checkable Proofs (PCPs). We will not go into detail
regarding PCPs, but suffice to say that they share a lot of similarities
with IPs. The main differences in the definition are minor details
regarding specific cryptographic properties:

* Soundness: it is always computational, since the Prover is
computationally (\(P_{POLY}\)) bounded, just like the Verifier. This
is due to the fact that PCPs are not technically “proof” systems,
but “argument”-based systems.

* Non Interactivity: such protocols don't require any
interactivity by default (IPs need the Fiat-Shamir extension discussed
later); instead, the Prover preprocesses the original language
statement to generate a (typically large) proof to send off to the
Verifier for inspection. This notion will be defined in Section

* Transparency: such systems do not employ interactivity because
everything is prepared in a trustless fashion. The Verifier will be
able to use (public) randomness to analyse a few elements of the given
proof. This notion will be defined in Section <ref>.

* Verifier Efficiency: these protocols are required to be
efficient by default. This is due to the groundbreaking results
emerging from the PCP Theorem
finalised in '98 by Aurora et al., which led to the conferring of the
Gödel Prize for multiple cryptographers having worked on it throughout
the 90s. This notion is defined in Section <ref> through
proof succinctness and verifier scalability.

In practice, PCP systems make heavy use of polynomial arithmetisation,
making them better suited for Universal VC systems, as seen in
Chapter 3; IPs, instead, typically focus on constructions based on
specific problem isomorphisms. An extension of PCPs called Interactive
Oracle Proofs (IOPs) [ref-IOP9], which
combines them with IPs, can be found in state-of-the-art Universal VC
systems and I mention it in Section <ref>).

§ TYPES OF KNOWLEDGE

The issue with most weak cryptographic authentication methods is that
some uniquely identifiable knowledge about the secret is somehow
“leaked” during the authentication process. Intuitively, we would like
to reduce this “knowledge leakage” as much as possible. In order to do
so, we must first understand what possessing “knowledge” truly means.
Let us define two major scenarios where knowledge is typically conveyed:

* Communication:

the Prover has chosen (or is in possession of) some non-deterministic
private value which the Verifier needs to solve some other publicly
known problem (likely published by the Prover and verified by a
Trusted Authority). The only way for this value to be known is through
the Prover himself.

* Computation:

the Verifier would like to extract some knowledge from a given hard
problem, but is too computationally bounded to be able to do so. Given
enough computational power, any Prover would be able to extract the
required knowledge and convey it to the Verifier.

Knowledge seems to be strictly related to the act of communicating some
value which is the result of a computation that was either too difficult
or even impossible for the Verifier to perform. In other words,
knowledge is transferred between two communicating parties if and only
if the output of their interaction was the result of an infeasible
computation for one or both of the parties.[An interesting note
here is that transferring random bits does not typically convey any
information, since any party can generate randomness by itself (being
an ITM). This may seem counterintuitive, but those random bits would
only convey knowledge if related to some pre-defined public statement
or problem which the Verifier cannot solve by himself.] Here is an
informal definition:

Knowledge Complexity KC

\[\textit{Given }
\begin{cases}
P_\text{UNBOUNDED}, V_\text{POLY} \in ITM \\
L \in IP(P,V) \\
f: \mathbb{N} \to \mathbb{N} \land f \textit{non-decreasing} \\
n \textit{ input size}
\end{cases}
\\
\textit{Then } KC_L(f(n)) \iff \vphantom{\textit{ (i.e. the knowledge complexity of L is f(n)) }}
\land \begin{cases}
\textbf{i. } X \in L, X \textit{ \underline{only} input to} (P,V) \\
\textbf{ii. } P \textit{"communicates"} \leq f(n) \textit{ bits of "knowledge"}
\end{cases}\]

Whenever we have \(KC_L(0)\), that means we can only convey one bit of
knowledge with our protocol: \(X \overset{?}{\in} L\).

§ ZERO-KNOWLEDGE INTERACTIVE PROOFS

If we embed \(KC_L(0)\) into the notion of IP, we get the following:

ZKIP Languages

\[\textit{Given }
\begin{cases}
P_\text{UNBOUNDED}, V_\text{POLY} \in ITM \textit{ (Interactive Turing Machine)} \\
L \subseteq \{0,1\}^* \in NP-lang
\end{cases}
\\
\textit{Then } X \in L \iff
\\\land\begin{cases}
\textbf{Completeness}\\
\textbf{Soundness}\\
\textbf{Zero-Knowledge}
\\\iff \forall V'_\text{POLY} \in ITM:
\exists \textit{ "Simulator" } S_\text{POLY} \in ITM: \textit{Tx}(S(V')) \approx \textit{Tx}(P,V) \\
\quad\implies \textbf{Deniability}
\end{cases}\]

Or, more intuitively:

The idea is that no extra knowledge can be extracted from a legitimate
valid interaction (i.e. leading to an accepting state), as long as it is
“indistinguishable” from a forged valid interaction. In fact, there
should be an efficient Simulator algorithm to simulate a valid
interaction's transaction record \(Tx\) even when the simulating
Verifier \(V'\) doesn't have access to the Prover's real witness. The
Simulator can generate \(Tx(S(V'))\) either by executing many protocol
runs until an accepting state is met, or just by deducing the correct
statement \(X\) starting from any final accepting state (known as
“rewind-ability”). I will elaborate later on what
“indistinguishable” (i.e. \(\approx\)) means in Section

The reason that this simulator-based definition leads to
privacy-friendly (i.e. non witness-leaking) protocols is because there
can be no witness Extractor for legitimate transcripts, since they're
indistinguishable from forged transcripts, which are assumed to lack any
witness at all. In other words: the protocol's soundness needs to
rely entirely on interactivity and randomness!

Zero-Knowledge also implies Deniability:

A Transaction record from a valid ZKIP interaction does not constitute
an independent proof of knowledge. No external third parties can watch
(or be given) a valid ZKIP communication and infer that the Prover
really has a witness for \(X\in L\), because the interaction may have
been simulated. Only the original parties of the ZKIP communication can
verify that it is indeed legitimate, because they know that the messages
were not forged when challenging each other.

The trick to actually achieving Zero-Knowledge in a meaningful manner
lies within the combination of Interactivity and Randomness.
The two parties cannot use a Challenge-Response protocol, because the
response to the challenged question is rather unique, regardless of the
chosen challenge. However, if the response were to be randomly selected
(i.e. challenged) out of a random distribution of values selected by the
Prover, it would not contain any meaningful information. In order for
such a protocol to be sound, only a legitimate Prover would be
always able to calculate the required response: a deterministic
relationship (selected using the Verifier's random challenge) on a
statement \(Y\), randomly derived from the original statement
\(X\).[there can also be multiple \(Y\) statements derived from
\(X\) at the same time, for efficiency purposes.] Interactivity is
required because, regardless of the chosen challenge, the Prover's set
needs to be random for each protocol execution.

Finally, the same security assumption of IPs apply to ZKIPs: the
difficulty of proving \(X \in L\) lies in the chosen language \(L\) and
its cryptographic hardness assumptions.

NOTE: alternative definitions have been used in the past to
describe zero-knowledge, such as “witness preservation” and “witness
indistinguishability”, but the one given here is the strongest one and
the current standard.

NOTE2: if you would like an alternative informal explanation of
ZKIP protocols, I highly recommend the beautiful paper by Quisquater et
al. [ref-Quisquater9010] on the metaphor of
the “Ali Baba Cave”. One important feasibility result for ZKIP proofs,
based on finding Hamiltonian cycles in graphs, was given by Blum in 1986

§.§ ZKIP as a solution to malicious

Zero-Knowledge proofs are regarded as being an extremely powerful tool
to convert malicious actors into semi-honest actors. A researcher first
builds a protocol which is shown to be secure when all parties (or
eavesdroppers) are semi-honest (i.e. they always follow the protocol's
rules); then, any party sending messages is required to provide proofs
that they were generated following protocol requirements. Since each
proof is Zero-Knowledge, the security of the original protocol is not
compromised. Because each message must be accompanied by a proof,
malicious attackers have no choice but follow the rules of the protocol,
or just abort. While there is a computational cost to be paid per proof,
Universal VC systems (discussed in Chapter 3) are a convenient and
efficient solution for adding such capabilities.

§.§ Types of Zero-Knowledge

We previously defined a Simulator capable of generating fake valid
protocol which are also indistinguishable from legitimate valid runs:
\(Tx(S(V')) \approx Tx(P,V)\).

There are currently 4 different classifications of indistinguishability

* Perfect: there exists a Simulator which produces communication
transcripts identically distributed to the legitimate
distribution of valid transcripts between \((P,V)\).

* Statistical: there exists a Simulator which produces
communication transcripts identically distributed to the
legitimate distribution of valid transcripts between \((P,V)\), except
for a constant (i.e. “small”) number of exceptions.

* Computational (default): there exists a Simulator which
produces communication transcripts not-identically distributed
to the legitimate transcripts produced between \((P,V)\), but it is
believed to be computationally infeasible to detect such

* Not Known (No Use): there does not exist a Simulator but the
communication Transactions are still believed to leak nothing about
the witness.

NOTE: the “Not Known” type of indistinguishability does
not satisfy full Zero-Knowledge requirements, and it also implies
Non-Deniability. See the next section.

§ NON INTERACTIVITY AND DIGITAL SIGNATURE

We have covered the basics of Zero-Knowledge Proofs, and we've seen that
two essential aspects are randomness and interactivity. Well,
what if the Prover and Verifier's interactivity in the real world is
effectively limited? For example, they may not be online at the same
moment, or the Prover might want to pre-process multiple proofs by
himself. Is it even possible to have “Non-Interactive” Zero-Knowledge
Proofs (NIZK)?

In 1987 an article by Israeli researchers Fiat and Shamir
[ref-FS8712] proposed a heuristic to solve the
aforementioned problem. The key takeaway here is that, while
Zero-Knowledge is not deemed to exist without Interactivity, we can
adopt the famous Random Oracle Model (ROM)
[ref-ROM13] assumption to make use of an
interacting “oracle” party which will supply us with “public-coin”
random challenges for our protocol. If we assume that cryptographic Hash
functions correctly implement a Random Oracle, we can employ them as
universal and passive Verifiers to participate in our proof, thus

Fiat-Shamir Heuristic
the Verifier selects a challenge \(e = H(pp)\), where \(H\) is a strong
cryptographic hash function implementing a Public-Coin Random Oracle,
and \(pp\) are the public parameters of the problem and the current
protocol execution (including the Prover's randomness)

As can be easily be understood, everyone with the same Hash function
also has access to the same challenges. Which means that they can
validate the lack of bias within the selection of random challenges,
hence the legitimacy of the proof. Since this check can be performed
independently after the execution of a NIZK, once the recorded
communication trace is given the proof can essentially be verified by
anybody. This is what it means for the protocol to become
“Non-Interactive”, while still retaining Interactivity in the
ROM model.

On a final security note, while the lack of bias in the selection of
challenges is apparent, the challenges are still selected based on the
Prover's random inputs. These can be biased and, since interactivity is
outsourced to the Oracle, an illegitimate Prover can mount an
offline attack to keep simulating protocol runs until he finds
lucky challenges he can satisfy. Therefore, to prevent cheating from the
Prover, we must exponentially decrease the error rate for Soundness to
brute-force levels
(i.e. \(\epsilon = 2^{-256} \iff Pr[V \textit{ accepts } X] \leq \frac{1}{2^{256}}\)).
This would imply that if a Prover does not have unlimited resources
(like in a real-life scenario, but unlike the formal ZKIP definition),
then he should not be able to come up with a simulated NIZK valid
protocol run.

§.§ Flawed NIZK Zero-Knowledge and

The last remark noted that we're preventing Provers from being able to
simulate protocol runs. Does this also mean that the Zero-Knowledge
property is broken? Well, yes, but actually no. There does not seem to
be a definitive answer in the cryptographic community as to whether
Zero-Knowledge is truly preserved for the Fiat-Shamir heuristic (a good
debate on this can be found in
[ref-fiatshamirisalie14]), but \(KC_L(0)\) is
believed to hold as long as the ROM model holds. The Zero-Knowledge
property for a Fiat-Shamir NIZK is currently classified as “Not Known”
(see the relevant subsection).

As an important consequence of the fact that NIZK proofs can be
validated by anybody with a transcript of the communication, the
Deniability property is broken:

\[NIZK \implies \textbf{Non-Deniability} \centernot\implies\textbf{Deniability}\]

This has the downside that any third parties can detect whether a proof
was legitimate or not. While this may not seem like such a big deal,
uniquely identifying logins (i.e. Identity Proofs) in censorship states
can pose a real threat to human rights. It is best to use pseudonymous
identities and de-anonymising networks when using NIZK technology
(e.g. ZCash) under such harsh regimes.

§.§ Digital Signature Algorithm

An important upside of NIZKs of Knowledge is that they can be extended
from one-shot Identification Schemes to one-shot Digital Signature

DSA Fiat-Shamir Heuristic
the Verifier selects a challenge \(e = H(pp, m)\), where all parameters
are the same as the standard Fiat-Shamir Heuristic, and \(m\) is the
message that the Prover wants to sign.

The “signature” is, of course, actually just a proof of Knowledge
which ties the Identification proof to the presence of a specific
message in the Verifier's challenge. This suffices to show that the
Prover knows the witness for his identity, and that he is committing to
using randomness (i.e. challenges) derived from a specific message.

§ PERFORMANCE THROUGH SCALABILITY

Over the years, as cryptographers struggled to develop Zero-Knowledge VC
protocols for practical use cases, a few more properties on
performance requirements were devised[A result of this
approach can be seen in the the PCP field of proof protocols.]. These
properties are especially relevant for comparison of recent Universal VC
systems, such as the ones mentioned in Section
<ref>, which tend to make compromises in the
name of expressiveness.

If outsourcing verifiable computations is to be seen as a commodity,
then they have to be fast to verify. This requirements boils down to two
main properties: there should be an exponential gap between the protocol
execution complexity of the Prover and Verifier (where the Verifier
takes less time), and the proof size should be small enough that the
Verifier can read it. Furthermore, Provers of the past often required
hundreds of gigabytes and weeks just to process simple proofs, we'd like
to avoid that as well. Formally:

Fully Scalable Proof

\[Given
\begin{cases}
P_\text{POLY}, V_\text{POLY} \in ITM \textit{ (Interactive Turing Machine)} \\
(x, y, f) = X \in L,\\
y = f(x),\ O_y(\Delta)\\
\end{cases}, \\\textit{Then}\ X \in L \implies \land
\begin{cases}
\mathbf{Completeness}\\
\mathbf{Soundness}\\
\mathbf{Prover\ Scalability}\ \iff O_P(\Delta + polylog(\Delta))\\
\mathbf{Verifier\ Scalability}\ \iff  O_V(polylog(\Delta))\\
\mathbf{Proof\ Succinctness}\ \iff \forall \pi = Tx(P, V): O_{|\pi|}(polylog(|x|))
\end{cases}\]

Intuitively, we want to validate proofs \(\pi\) much faster than
it takes the Verifier to actually check the statement himself, and
without excessive overhead for the Prover. Also, the communication
complexity for such protocols should be always be well within acceptable

It is important to note that most protocols don't achieve such
results, so the actual definitions are typically relaxed based on the
current best solution in that field. For the STARK protocol analysed in
this thesis I'll use as satisfying prover-scalability requirement a
quasilinear Prover \(O_P(\Delta \cdot polylog(\Delta))\), which can
yield acceptable concrete performance results in most cases.

NOTE: often verifier-scalability and proof-succinctness are
regarded together as “verifier efficiency”. For extra confusion,
sometimes researchers also use the term “succinctness” to refer to one
or both properties, or just scalability in general. Sometimes a fully
scalable system is called doubly scalable, or just scalable.

§ OTHER VC PROPERTIES

Finally, some further non-essential but highly appreciated
properties are added, which increase the reliability and flexibility of
a proof system, allowing it to be used in more demanding use-cases:

\(Tx(P \gets V) \in \textit{public random coins}\) ; i.e. the
Verifier only ever sends messages taken from a randomness source that is
also available to the Prover.

This property was first conceived with Arthur-Merlin (AM) protocols
[ref-ArthurMerlin216]), which were proven to
be equivalent in expressiveness to IP protocols that had separate
randomness sources for the two parties; it was first called
“transparency” in [ref-ArthurMerlin317].
Transparency is typically present in all PCP-family protocols.

The reason that this property is “transparent” is because as long as
the Prover and Verifier have access to the same randomness source, there
can be no trusted or trapdoor-derived setup for the underlying
protocol[all setups are either deterministic, or public-coin
non-deterministic.]. Because trust is eliminated, the security of the
protocol cannot be compromised as it does not depend on any specific
party, only mathematics. Transparency has also become a matter of
interest lately, due to the increased popularity of zk-SNARK
constructions (see Section <ref>), which are
infamous for their trusted setups and less suitable for decentralised,
trustless settings.

\(L \iff NP-lang\) ; i.e. the protocol language supports
statements taken from any NP computation.

This property is extremely useful for implementing basic cryptographic
proving primitives that can be applied to computations of
Turing-complete machines. The utility of such Universal VC protocols
lies with the convenience of being able to freely design an application,
and then automatically generate proofs for the actions performed by said
application. This topic is widely discussed in Chapter 3.

Post-Quantum Safety
the protocol makes use of cryptographic assumptions which are not
shown to be compromised by Quantum algorithms.

Finally, a couple of open questions which have been less (if at
all) studied in popular VC constructions:

the proofs of different statements can be efficiently combined, or
extended into more complex ones.

a single proof can be generated using multiple inputs taken from
different Provers. Achieving such a property for Zero-Knowledge
protocols would be akin to achieving Multi-Party Computation.

CHAPTER: NON-UNIVERSAL VC PROTOCOLS

In the decades leading up to the introduction of practical Universal
VCs, most protocols only dealt with either secret proving or specialised
computational proofs. Common tools to achieve this were either
Interactivity (and isomorphic problems) or Homomorphic Encryption, or
both. In this chapter I will evaluate two innovative fields of
cryptography which have a strong correlation with universal VC
solutions: Homomorphic Authenticators and Verifiable Delay Functions.
While they have mostly been developed under different contexts, they
share many of the fundamental properties introduced in the VC Model
chapter. Homomorphic Authenticators deal with outsourced (homomorphic)
computation and VDFs deal with scalable computation; both yield
interesting protocols which can be adapted, with a little expertise,
into practical ad-hoc applications.

I will carefully evaluate the properties achieved by each construction,
trying to understand the cryptographic design behind it without
sacrificing the simplicity of our VC Model. This aim of this chapter is
to alleviate the fragmentation and complexity of the fields which stand
below Universal VC solutions, showing that they can be useful starting
points for achieving richer VC constructions. Further non-universal VC
protocols will be discussed in the conclusive remarks of this chapter.

§ HOMOMORPHIC AUTHENTICATORS

Homomorphic Authenticators (HAUTHs) stem from an interesting and active
area of research, with recent publications being in 2018. The incipit of
this field lies with Homomorphic Signature schemes, which were
originally rejected by cryptographers due to their implicit
susceptibility to forgery attacks. These schemes were brought up again
by Rivest, and formalised by Johnson et al in
2002[ref-Johnson0218], to include better
definitions for security against forger (i.e. Random Forgery attacks).

Multiple researchers followed down this path, coming up with innovative
constructions for validating outsourced computations
(e.g. cloud computing). An initially successful design
[ref-Gennaro1219] (in terms of VC features)
relied on fully homomorphic MAC constructions using polynomials. These
MACs would then be sent to a server (i.e. Prover), which would leverage
their homomorphic properties to generate computational proofs on the
given data. This way, homomorphism can be used to yield valid isomorphic
problems, akin to the concepts introduced in Chapter 1. The big
advantages of this technique, compared to IPs, are: outsourced proving,
proof composition, and efficiency for really big problem sizes. In fact,
a core feature of Hom.Authenticators is that a Prover can upload really
large databases to the Verifier, and then delete them; the
Authenticators themselves will be sufficient to verify the validity of
any computation on this data.

The polynomial-based construction was then extended by
[ref-Fiore1620] to support inputs for multiple
clients, which would grant a simil multi-party property. This was
achieved by adding a form of homomorphism to the keys themselves, and
then allowing the Verifiers to merge them during the verification phase.
Other forms of publicly verifiable schemes were provided (based on
lattices), but they proved to be very complex and inefficient. In order
to make the construction more practical, Fiore et
al.[ref-Fiore1321] managed to achieve verifier
scalability, albeit sacrificing the universality of the protocol. This
modification used a combination of polynomials and additive group
schemes with bilinear pairings for multiplication. Finally, public
verifiability and zero-knowledge were added just now in 2018 by
Schabhüser et al.[ref-SBB1822]. Public
verifiability is achieved by building a homomorphic signature scheme out
of the homomorphic MACs; simil ZK was achieved through a property known
as “context-hiding”.

In this section I will provide the following content: an overview of
Homomorphic Authenticator protocols and commonly used syntax for this
field (Section <ref>); the basic homomorphic components
behind them (Section <ref>); a basic MAC construction
construction (Section <ref>); an extension to multiple
clients participating in the protocol (Section <ref>);
and finally support for verifier scalability (Section

§.§ Protocol Syntax

Let's consider the protocol as a 3-step proof, which makes it simpler to
compare it with other VC technologies. We wish to prove \(f(x)=y\), the
construction is as follows:

\[client\ Verifier \overset{\sigma_x}\longrightarrow server\ Prover\\
client\ Verifier\ \overset{\sigma_y}\longleftarrow server\ Prover\\
check(\sigma_y) \overset{?}= True\]
Here is the sequence of steps which
the parties go through, in a basic construction:

* Preparing the Authenticator: The Verifier needs to convert
his message \(x\) into a Homomorphic Authenticator \(\sigma_x\), which
is a MAC or Signature made using a secret key \(sk\). First, the
client generates a unique label \(L\) relating to the message \(x\),
e.g. “message #1” or “message x on time 10:54”. The label is then
converted into a random value \(r\), required for the security of the
scheme, using a keyed one-way PRF[for example, a seeded PRNG
constructed from a keyed cryptographic hash function such as

\[r \gets PRF_K(L)\]
A Homomorphic MAC (HMAC) is typically built using
polynomial interpolation:

\[\sigma_x \gets p = (p_0, p_1) = (x, (r-x)/sk) = Interpolate((0, x), (sk, r))
\\ with\ p(i) = p_0 + p_1 i\]
Since it's more common to define a
function as composition of multiple inputs,
i.e. \(f(x_1, x_2, ...) = y\), then this HMAC interpolation process
can be repeated for each input message, and each message \(x_i\) will
be associated with a different label \(L_i\):

\[\sigma_x \gets (\sigma_1, \sigma_2, ...) = (p_1, p_2, ...)\]

* Generating an Authenticator-based proof: The Prover then uses
the MAC/Signature scheme to convert function \(f\) into a sequence of
homomorphic operations on \(\sigma_x\). After these operations have
been performed, they will yield a valid MAC/Signature \(\sigma_y\),
which is considered as proof for this protocol. First, the server
converts the function \(f\) into a Turing-complete sequence of HMAC
operations, e.g. \(f_+\) or \(f_\times\) for the polynomial
\[f \implies (f_+, f_\times, ...)\]
These operations are
applied in sequence to \(\sigma_x\), with a resulting Authenticator
polynomial called \(\sigma_y\):

\[\sigma_y \gets (f_+, f_\times, ...) (\sigma_x)\]

* Verifying the proof's validity: The Verifier uses the
protocol's verification function, this is a crucial step in the
construction of the protocol which establishes our soundness property.
To verify whether a given \(\sigma_x\) is a valid Authenticator
polynomial, the client needs to check whether evaluation on the secret
key \(sk\) yields a value consistent with the input label(s):

\[\sigma_x(sk) \overset{?}= r\]
(we will discuss why in detail
later.) Which means that any homomorphic derivate of \(\sigma_x\)
will necessarily yield an equivalent homomorphic derivate of \(r\)
when evaluated on \(sk\):
\[\sigma_y(sk) \overset{?}= f( r )\]

For compatibility's sake, and to help newcomers to the field follow the
original papers better, let us also display the domain-specific
syntax for the Homomorphic Authenticators domain[\(ek\) is a
protocol-abstracted evaluation key, but it is not typically present in
most constructions and it can be representative of the public scheme
parameters; \(\sigma_i\) is computed for each input message \(m_i\).]:

\[(sk, ek) \gets Keygen(\lambda)
\\\sigma_i \gets Auth(sk, m_i, L_i)
\\\sigma \gets Eval(ek, f, \sigma_i ...)
\\\{0,1\} \gets Ver(sk, f, L_i ..., \sigma, m_i ...)\]

In the next subsections, we will see how to enhance this simple protocol
to include multiple VC features.

§.§ Adding Completeness

As described in the previous section, we seek full homomorphism in order
to achieve completeness:

a Signature/MAC scheme \(Sig\) is operator \(\odot\) homomorphic

\[\iff \exists \textit{ operator }\otimes: y=Sig(x) \land y'=Sig(x') \implies y \otimes y' = Sig(x \odot x')\]

Full Homomorphism
a signature/MAC scheme \(Sig\) is fully homomorphic

\[\iff additively\ homomorphic \land multiplicatively\ homomorphic
\\\iff \exists \oplus \textit{ operator }, \odot \textit{ operator}: y = Sig(x) \land y'=Sig(x') \\\implies y \odot y' = Sig(x \cdot x') \land y \oplus y' = Sig(x + x')\]

Finding a fully homomorphic scheme is essential to achieve
universality, so the researchers found a mathematical object
(polynomials) which supported both additive and multiplicative
composition, and then built an authentication scheme on top of it. Given
\(c \in \mathbb{Z}\) and polynomials \(p\) and \(q\) such that

\[\begin{cases}
p = (p_0, p_1, ...) \in F[x]\ \ \big(\textit{ with }n = degree(p),\ |p|=n+1\big)  \iff p(x) = \sum_{i=0}^n p_i \cdot
\\q \in F[x]\ \big(\textit{with }m = degree(q)\big)
\end{cases}\]
, the following additive and multiplicative polynomial
operators are given:
\[\begin{aligned}
p+q &\overset{def}= \forall_{i=0}^{max(n,m)}{p_i + q_i}
\\p+c &\overset{def}= (p_0 + c,\ \ \forall_{i=1}^{n}{p_i})
\\p \times q &\overset{def}= \forall_{i=0}^{n+m}{\sum_{j=0}^{i}{p_j \cdot q_{i-j}}}
\\p \times c &\overset{def}= \forall_{i=0}^n  pi \cdot c
\end{aligned}\]
Of course, these two operations are only a minor part
out of all those which have been defined by mathematicians in the coming
ages; however, it is a widely known Computer Science fact that these two
operations suffice to describe any boolean circuit, and thus fully
homomorphic signature schemes are Turing-complete.

Now that we've defined the basic building blocks for our protocol, let's
show that these two operations hold for any polynomial evaluation:

\[p(x) + q(x) = \sum_{i=0}^{n} {p_i x^i} + \sum_{i=0}^{m}{q_i x^i} = \sum_{0}^{min(n,m)}{p_i x^i} + \sum_{min(n,m)+1}^{max(n,m)}{p_i  x^i} + \sum_0^{min}{q_i  x^i} + \sum_{min+1}^{max}{q_i  x^i}
\\=\sum_0^{min}{p_i x^i + q_i x^i} + \sum_{min+1}^{max}{p_i x^i + q_i x^i} = \sum_0^{max} {p_i x^i + q_i x^i} = \sum_0^{max}{(p_i+q_i) x^i} = (p+q)(x)\]

\[p(x) \cdot q(x) = \sum_0^n {p_i x^i} + \sum_0^m {q_i x^i} = \sum_0^n {\sum_0^m {p_i x^i \cdot q_j x^j}} = \sum_0^n {\sum_0^m {p_i q_i x^{i+j}}}
\\=… = \sum_0^{n+m} \Big({x^i \cdot \sum_{0}^i {p_j \cdot q_{i-j}}}\Big) = (pq)(x)\]

§.§ Adding Soundness

Our interest here lies in two considerations:

* building a MAC out of polynomials

* making sure that we can take advantage of the operations explained in
the previous section to achieve a fully homomorphic MAC

Since preserving the full homomorphism is important, we can start from
step (2) and build our way towards step (1). Let's consider the
following relationships on polynomials:
\[\begin{aligned}
p(x) + q(x) &= (p+q)(x)\\
p(x) \cdot q(x) &= (pq)(x)
\end{aligned}
\ \iff\
\begin{aligned}
Eval(x, p) + Eval(x, q) &= Eval(x, p+q)\\
Eval(x, p) \cdot Eval(x, q) &= Eval(x, pq)
\end{aligned}\]
If we tried to represent this as a more traditional
Encryption/Signature scheme, it might look like this:

\[Sig(sk, p) + Sig(sk, q) = Sig(sk, p+q)\\
Sig(sk, p) \cdot Sig(sk, q) = Sig(sk, pq)\]

We can, therefore, understand that we should use the secret key instead
of the x-coordinate, and the homomorphisms should still hold. Thanks to
the Completeness properties achieved above, operating on a polynomial
has the effect of operating on all its points at the same time; which
means that interpolating two polynomials on the same x-coordinates
allows us to combine them to operate on their y-coordinates:

\[\begin{aligned}
p = Interpolate((0, m_1) (1, m_2) (2, m_3))\\
q = Interpolate((0, m_4) (1, m_5) (2, m_6))\\
(p+q)(0) = m_1 + m_4\\
(p+q)(1) = m_2 + m_5\\
(p \cdot q)(2) = m_3 \cdot m_6
\end{aligned}
\implies
\begin{aligned}
\sigma_p = Interpolate((sk, m_1))\\
\sigma_q = Interpolate((sk, m_2))\\
(\sigma_p+\sigma_q)(sk) = \sigma_p(sk) + \sigma_q(sk) = m_1 + m_2\\
(\sigma_p \cdot \sigma_q)(sk) = \sigma_p(sk) \cdot \sigma_q(sk) = m_1 \cdot m_2
\end{aligned}\]
The polynomial \(\sigma_p\) is already very close to a
homomorphic MAC (\(sk\) is the secret key, and \(m_1\) is the message
being signed), but we mustn't disclose the \(sk\) x-coordinate to
anyone. There are two problem:

* if we disclose the message being signed, something usually allowed by
signature and MAC schemes, then someone could figure out our secret
key \(sk\).[as long as the degree of the polynomial is higher
than 0, which we will see is a useful thing to have]

* to protect against oracle attacks we should add randomness to the
scheme (as well as prove that it is secure against Random Forgery).

To address both problems at the same time, we will move the message
\(m\) to a known x-coordinate, while using a random value for our \(sk\)
\[\sigma = Interpolate((0, m), (sk, r))\]
It is paramount
to avoid disclosing \(r\), so it must always be stored privately by the
signer and associated with the message being signed. Since this is often
an inconvenient constraint for the user of MAC, the user instead chooses
a unique label \(L\) associated with the signature on \(m\) at that
specific point in time (e.g. “m  time”), and
randomises it using a keyed one-way PRF (e.g. a cryptographic PRNG or a
keyed cryptographic hash function). The following is the HMAC
construction for signing (m, L) using private keys (sk, K):

\[r = PRF_K(L)\\
\sigma = Interpolate((0,m), (sk, r))\]
This construction is also shown
in [ref-Gennaro1219] to be secure
(sound) against Random Forgery attacks, as long as the label L is
never re-used.

Please note that, since our signatures are still just polynomials, our
completeness property from the previous section still holds:

\[{\left.\begin{aligned}
\sigma_1 \gets Interpolate((0, m_1), (sk, r_1)) \land r_1 \gets PRF_K(L_1)\\
\sigma_2 \gets Interpolate((0, m_2), (sk, r_2)) \land r_2 \gets PRF_K(L_2)
\end{aligned}\right\rbrace}
\\\implies
\begin{aligned}
(\sigma_1 + \sigma_2)(0) = \sigma_1(0) + \sigma_2(0) = m_1 + m_2 \\
(\sigma_1 \cdot \sigma_2)(sk) = \sigma_1(sk) + \sigma_2(sk) = r_1 \cdot r_2
\end{aligned}\]

§.§ Adding Multiple Clients

In order to support multiple clients, we will have to change both the
homomorphism and the MAC constructions. For the new homomorphism, we
will take advantage of another property about polynomials: they can be
multi-variate. In fact, a polynomial \(p(x)\) can support
full-homomorphism just as much as \(p(x,y)\) can. This is intuitive if
you remap \(x\) as a composition between two other variables. Given
\(c \in \mathbb{Z}\) and univeriate polynomials \(p\) and \(q\)

\[\begin{cases}
p = (p_0, p_1, ...) \in F[x]\ \ \big(\textit{ with }n = degree(p),\ |p|=n+1\big)  \iff p(x) = \sum_{i=0}^n p_i \cdot
\\q \in F[y]\ \big(\textit{with }m = degree(q)\big)
\end{cases}\]
, the following additive and multiplicative polynomial
operators are given:
\[\begin{aligned}
p+q &\overset{def}= \forall_{i=0}^{max(n,m)}{p_i + q_i}\ \textit{(for missing values, $p_i=0$ and $q_i=0$)},
\\ &\textit{with }max(m,n)=\textit{degree}(p+q),\ |p+q| = 2max(m,n))
\\p+c &\overset{def}= \textit{same as univariate homomorphism}
\\p \times q &\overset{def}= \forall_{i=0}^{n+m} \forall_{j=0}^{i} p_j \cdot q_{i-j}\ \textit{(coefficients for $x^j y^{I-j}$)},
\\ &\textit{with }m+n = degree(p \times q), |p \times q| = |m+n|^2
\\p \times c &\overset{def}= \textit{same as univariate homomorphism}
\end{aligned}\]
Note: the size of the multiplicative homomorphism
result can be further compressed down to
\(|p \times q| = \sum_0^{m+n} i + 1 = m^2 + n^2\), and even more using
techniques described in [ref-Fiore1620]

Now that we have modified our polynomials (while still retaining
completeness) we can construct a Multi-Key Fully-Homomorphic MAC out of
different separate keys:
\[\sigma_p = Interpolate_X((sk_1, m_1))
\\\sigma_q = Interpolate_Y((sk_2, m_2))
\\(\sigma_p + \sigma_q)(sk_1, sk_2) = \sigma_p(sk_1) + \sigma_q(sk_2) = m_1 + m_2
\\(\sigma_p \sigma_q)(sk_1, sk_2) = \sigma_p(sk_1) * \sigma_q(sk_2) = m_1 \cdot  m_2\]

Clearly both keys are required for the final evaluation step, hence,
verification of any signature requires that the Verifiers share their
secret keys, or perform a MPC computation; Fiore et
al. [ref-Fiore1620] take the simpler approach,
and have the parties share all the secrets. Because of this, scheme is
actually a MAC and not a digital signature, just like the previous
construction. If we group the keys like \(sk = (sk_1, sk_2)\), we can
perform the evaluation on the keys exactly like the main protocol syntax

Of course, we should harden our primitive MAC using the same
randomisation process as before, revealing only the signed message for
the \(0\) x-coordinate:
\[r = PRF_{K_i}(L)
\\\sigma_i = Interpolate((0, m), (sk_i, r))\]
If we wish to adjust the
syntax to the final step of the protocol, it'll look like this:

\[sk = (sk_0, sk_1, ..., sk_\textit{last party})\ \textit{(all participants)}
\\r = (r_0, r_1, ..., r_\textit{last message})\ \textit{(all messages)}
\\\sigma_y(sk) \overset{?}= f(r)\]
This construction is also shown to be
sound in [ref-Fiore1620], in a way that is
similar to the previous one.

§.§ Adding Verifier Scalability

The scheme obtained so far has a lot of nice properties, such as
outsourced proving and support for large inputs, but it imposes a big
toll on the Verifier: the client must compute the function on an
alternative set of inputs (the labels) each time he wishes to validate a
computation. In short, the scheme is not verifier scalable. In
this step, we will essentially change the construction of our Hom.MAC
into [ref-Fiore1321], incorporating
polynomials into additive groups. Before we do that, however, let's
consider what we're going to need: amortisation.

§.§.§ What is Amortisation?

The final verification step, essentially, requires receiving the
evaluated Authenticator \(\sigma_y\) from the Prover, and then checking
it against a constant \(f(r)\) evaluated by the Verifier. Wouldn't it be
nice to re-use \(f(r)\) for multiple executions of the protocol?

Unfortunately, security assumptions from
[ref-Gennaro1219] for the soundness of our
basic HMAC require that \(r\) always be randomly chosen, even for
multiple signatures on the same message — therefore, \(L\) needs to be
randomly chosen as well. What we can do is split \(L\) into a changing
part \(\Delta\), and a constant part \(l\): \(L = (l, \Delta)\); this is
also called a “Multi-Label” by the authors. These multi-labels might
look a little like this:

* \(L = (\textit{”message m”}, \textit{”at time 12:54”})\), so that
\(f\) can be computed on messages of the same nature (i.e. index in a
database), but changing over time; or

* \(L = (\textit{“message m at time 8am”}, \textit{”on day 08/12/2019”})\),
so that \(f\) can be computed on the same set of messages (i.e. a
single row indexed in a database), but changing over dates.

While \(f(r) = f(PRF_K(L))\) will still change across multiple execution
runs, we might find a way to precompute \(C=f(PRF_K(l))\), and then
efficiently add the component \(\Delta\) later on:

\[f(r) = Load(C, \Delta)\]
Assuming the function \(Load\) has an
exponentially lower complexity than \(f\), the check should also be
verifier scalable.

In order to actually build the \(Load\) function, we'll have to somehow
pull the \(\Delta\) out of \(f\):

\[f(r) = f(PRF_K(L)) = f(PRF_K((l, \Delta))) \implies \exists f’:f’(PRF_K(l), \Delta) = Load(f(PRF_K(l), \Delta)\]

This act of “pulling out” a value is exactly what full homomorphism
allows us to achieve for a function \(g\):

\[\exists g’: E(g(x, y)) = g'(E(x), E(y))\]
Unfortunately, while \(f\)
may operate on polynomials, \(L\) is not one. In fact, even \(PRF\)
operates on specific values (you may think of them as numbers, but a
string is also valid input to a hash function), and returns a value as
well. In order to “pull \(\Delta\) out”, we will perform two tricks:

* transform \(l\) into a 1st degree polynomial, whose variable
represents \(\Delta\)

* convert \(PRF\) into its equivalent sequence of operators \(PRF'\) for
the homomorphic signature scheme

We can then evaluate this polynomial on \(\Delta\):

\[Load(f(PRF_K(l), \Delta) \overset{def}= f(PRF’_K(l))(\Delta)\]
this approach certainly works, \(PRF'\) would probably be cumbersome to
evaluate on polynomials, especially when \(PRF\) is actually a keyed
hash-function such as Keccak256[ref-keccak23].
Instead, the researchers came up with a more efficient construction,
which manages to first evaluate the \(PRF\) on simple values, and then
convert it into a polynomial:

\[r_1 = PRF1_K(l)
\\r_2 = PRF2_K(\Delta)
\\PRF_K((l, \Delta)) \overset{def}= r_1 \oplus r_2\]
actual operation to merge \(PRF1\) and \(PRF2\) is not really a XOR,
but another trickery defined on top of additive groups. The cost for
\(PRF’\) is \(O_{f\ amortised}(|r_1|)\), so \(O(1)\) for the 2nd
degree restriction that was added by the authors, as we will see
later.] \(PRF1\) and \(PRF2\) are defined similarly to the original

* transform \(r_1\) into a 1st degree polynomial whose variable
represents \(\Delta\)

* convert \(PRF\) into its equivalent sequence of operators \(PRF’\) for
the homomorphic signature scheme

* The new check becomes (after amortisation):

\[r_1 \overset{\textit{amortised}}= PRF1_K(l)
\\r_2 = PRF2_K(\Delta)
\\f(r) = Load(r_1, r_2) = PRF’(r_1, r_2)
\\\sigma_y(sk) \overset{?}= f(r)\]

The construction provided by the authors for \(PRF'\) requires the use
of additive groups, therefore we will adapt the rest of our homomorphism
construction to this requirement.

§.§.§ Amortized Completeness

Now that we have obtained amortisation, we just need to move our
previous HMAC, based on polynomials, to an additive group
\(\mathbb{G}\):

\[\sigma \overset{def}= Interpolate((0, m) (sk, r)) = p = (p_0, p_1) = (m,  (r - m)/sk)
\\\iff \sigma_\mathbb{G} \overset{def}= Interpolate_\mathbb{G}((0, m) (sk, r)) = p_\mathbb{G} = (g^{p_0}, g^{p_1}) = (g^m, g^{(r-m)/sk})\]

As can be seen, we just simply move all the polynomial coefficients into
the group generator's exponent. All polynomial homomorphisms only need
to work on the exponents; given \(c \in \mathbb{Z}\) and polynomials
\(p\) and \(q\):
\[\begin{cases}
p_\mathbb{G} = (g^{p_0}, g^{p_1}, ...) \in G[x]\ \ \big(\textit{with }n=deg(p_\mathbb{G}),\ |p_\mathbb{G}| = n + 1\big)
\\q_\mathbb{G} \in G[x]\ \big(\textit{with }m= deg(q_\mathbb{G})\big)
\end{cases}\]
the following additive and multiplicative group-polynomial
operators are given:
\[\begin{aligned}
p+q &\overset{def}= \forall_{i=0}^{max(n,m)}{p_i + q_i}
\\p+c &\overset{def}= (p_0 + c,\ \ \forall_{i=1}^{n}{p_i})
\\p \cdot q &\overset{def}= \forall_{i=0}^{n+m} {\sum_{j=0}^{i}{p_j \cdot q_{i-j}}}
\\p \times c &\overset{def}= \forall_{i=0}^n  pi \cdot c
\end{aligned}\implies
\begin{aligned}
p_\mathbb{G} + q_\mathbb{G} &\overset{def}= \forall_{i=0}^{max(n,m)} g^{p_i+q_i} = \forall_{i=0}^{max(n,m)} {(g^{p_i} \cdot g^{q_i})}
\\p_\mathbb{G}+c &\overset{def}= (g^{p_0+c}, \forall_{i=1}^{n} g^{p_i}) = ((g^{p_o})^c, \forall_{i=1}^{n} g^{p_i})
\\p_\mathbb{G} \cdot q_\mathbb{G} &\overset{def}= \forall_{i=0}^{n+m} \sum_{j=0}^{i} g^{p_j \cdot q_{i-j}} = \forall_{i=0}^{n+m} \sum_{j=0}^{i} (g^{p_j})^{q_{i-j}}
\\&= \forall_{i=0}^{n+m} \sum_{j=0}^{i} (g^{p_i})^{dlog(g^{q_{i-j}})}
\\p_\mathbb{G} \times c &\overset{def}= \forall_{i=0}^n g^{p_i \cdot c} = \forall_{i=0}^n (g^{p_i})^c
\end{aligned}\]
Completeness is straightforward and leverages the same
concepts mentioned previously. Evaluation is also pretty simple:

\[p_\mathbb{G} = (g^{p_0}, g^{p_1}, g^{p_2}) \in G[x]
\\p_\mathbb{G}(x) = g^{p_0 + p_1 x + p_2 x^2} = g^{\sum_0^n {p_i x^i}} = \prod_0^n g^{p_i \cdot x^i} = \prod_0^n (g^{p_i})^{x^i} = g^{p_0} \cdot (g^{p_1})^x \cdot (g^{p_2})^{x^2}\]

As can be noticed, the multiplicative homomorphism requires that we use
\(dlog\) to compute the multiplication between any two elements of
\(\mathbb{G}\). However, for security purposes, the authors decided to
integrate our polynomial-based fully-homomorphic scheme into groups
where the Discrete Logarithm Problem would hold. The alternative is to
apply a bilinear mapping in order to simulate (and obtain) up to one
multiplicatively homomorphic operation:

\[e: \mathbb{G} \times \mathbb{G} \to \mathbb{G}_T,\ e(g^a, g^b) = e(g,g)^{ab} = g_t^{ab},\ g_t = e(g,g),
\\\langle g \rangle = \mathbb{G},\ \langle g_t \rangle = \mathbb{G}_T\]

In particular, two choices were made:

* Use an additive group with just one bilinear mapping. This effectively
limits \(f\) to only functions of 2nd degree, thus also eliminating
the scheme's previous universality claim.

* There are a couple of small changes to the group-polynomials'
definition when applied to our HMAC scheme:

* \(r\) is actually calculated a little differently, as its \(dlog\)
(calculated by the client) is used instead; it should still hold as
valid entropy source, see the paper for more

* the very fist coefficient of any polynomial \(p_\mathbb{G}\)
(i.e. \(g^{p_0}\)), is actually set to \(p_0\). This makes
multiplication for two polynomials of first degree a little more
efficient, because
\[p_\mathbb{G} \overset{def}= (g^{p_0},\ g^{p_1})
\\q_\mathbb{G} \overset{def}= (g^{q_0},\ g^{q_1})
\\p_\mathbb{G} \times q_\mathbb{G} = (g^{p_0 q_0},\ g^{p_1 q_0 + q_1 p_0},\ g^{p_1 q_1}) = ((g^{p_0})^{q_0},\ (g^{p_1})^{q_0}  \cdot (g^{q_1})^{p_0},\ (g^{p_1})^{q_1})
\\\qquad\qquad= ((g^{p_0})^{dlog(g^{q_0})},\ (g^{p_1})^{dlog(g^{q_0})} \cdot (g^{q_1})^{dloq(g^{q_0})},\ (g^{p_1})^{dlog(g^{q_1})})
\\\qquad\qquad= (e(g^{p_0},\ g^{q_0}),\ e(g^{p_1},\ g^{q_0}) \cdot e(g^{q_1},\ g^{q_0}),\ e(g^{p_1},\ g^{q_1}))\]

\[p_\mathbb{G} \times q_\mathbb{G} = (p_0 q_0,\ g^{p_1 q_0 + q_1 p_0},\ g^{p_1 q_1}) = ((p_0 q_0,\ (g^{p_1})^{q_0} \cdot (g^{q_1})^{p_0},\ (g^{p_1})^{q_1})
\\\qquad\qquad= ((p_0 q_0,\ (g^{p_1})^{q_0} \cdot (g^{q_1})^{p_0},\ (g^{p_1})^{dlog(g^{q_1})})
\\\qquad\qquad= ((p_0 q_0,\ (g^{p_1})^{q_0} \cdot (g^{q_1})^{p_0},\ e(g^{p_1},\ g^{q_1}))\]

§.§.§ Amortized Soundness and

The construction of the HMAC follows the same idea as in the previous
ones, so I will be brief.
\[\begin{aligned}
r &= PRF_K(L)\ \quad\textit{($L$ is a full multi-label)}
\\\sigma_x  &= Interpolate_\mathbb{G}((0, m) (sk, r))
\end{aligned}\]
Then, \(f(x)\) gets evaluated by mapping \(f\) to its
counterpart \(f’\) using the group homomorphisms:
\(\sigma_y = f'(\sigma_x)\). And, finally, the check is the same because
it leverages polynomial evaluation within the additive
\[\sigma_y(sk) \overset{?}= f(r)\]

Scalable Verifier
in the multi-client or the multi-message construction, the idea is
that all \(L_i\) have the same \(\Delta\), the \(Load\) function only
takes 1 value, so its complexity is \(O_V(1)\)

§ VERIFIABLE DELAY FUNCTIONS

Verifiable Delay Functions (VDFs) are currently a very active research
area in the cryptocurrency community, but they have actually been around
for a long time, with a formal definition given only in 2018 by
[ref-BBBF1824]. Until recently, researchers
had been toying with many different constructions, trying to find
adequate “time-lock puzzles”. In 1996 Rivest et
al. [ref-RSW9625] introduced a mathematical
problem which seemed to exhibit interesting properties, with relation to
time delaying functionality, previously only briefly considered in naïve
PoW-like schemes by researchers such as Merkle

The main objective is to come up with a cryptographic proof of elapsed
time, i.e. a delay. Researchers figured that a universal reference for
measuring the passage of time could be represented by the maximum speed
at which a single operation can be processed on a circuit (of any kind),
so they set out to find “sequential functions” – i.e. which could
only be computed on a single cpu core one operation at a time. This idea
can be seen as a PoSW, “Proof of Sequential Work”; we will discuss
later the implications for this construction.

Once such a “time-lock puzzle” (or PoSW) was found, the need emerged
for an efficient verification mechanism, to relieve the Verifier
from the burden of wasting the same amount of time as the Prover just to
check that he did indeed compute the right result. This would allow for
efficient outsourcing of elapsed time, which may sound like a useless
tool, but it can lead to surprisingly innovative solutions in the
time-agnostic world of computer science. Attempts to find such
verifier scalable PoSWs lasted for years, with some improved but
incomplete results in 2015 [ref-LW1527] and
2018 [ref-BBBF1824], culminating with two
complete solutions that same year by Wesolowski
[ref-Wes1828] and Pietrzak

The recent rush of new research in this field is probably due to the
increased popularity of Blockchain technology (see use-cases in Section
<ref>), and a formal definition for these systems was
finally given by [ref-BBBF1824] under the new
name “Verifiable Delay Functions”. We will be mainly considering
Wesolowski's scheme in this section, with some references to Pietrzak's.
A good comparison of the two schemes is also provided in

§.§ Utility

The issue of time synchronisation has long plagued electronic computers
which interact on the Internet. To solve synchronisation between honest
parties, a hardware clock (or constant delay networks) might suffice,
but malicious parties would still be able to report incorrect
timestamps. Most importantly, the issue of time synchronisation also
extends to time delay proving. There are two main ways to detect such
malicious attempts:

* Distributed consensus mechanism.

This idea basically adapts the concept of a trusted third party to a
scenario where no such party exists (or at least it is not recognised
as such by all honest parties).Trust is distributed amongst all the
parties (according to some satisfactory proportion or relation), and
the validity of a claim is based on whether it is the most supported
one by the network.

In order for this system to work there needs to be a majority of
parties incentivised to act honestly, which is commonly achieved by
distributing trust amongst a large number of independently motivated
parties, all interested in using the same protocol (e.g. pseudonymous
Bitcoin users participating from all around the world). Also, the
network itself needs to always be available to all parties
(i.e. censorship resistant), otherwise honest parties might be unable
to stave off false claims by supporting only the correct ones.

* Use a universal time delay measurement reference.

This would be some sort of event occurring in our world which can be
universally verified just based on the laws of physics. The Prover
would perform some sort of action or operation over a period of time,
and it would automatically reflect on some object in the universe in
such a way that it would be infeasible to replicate the same exact
object without the same period of time having elapsed.

Of course, these two systems can be combined into a single solution –
Bitcoin makes both use of the PoW system as well as the distributed
consensus model – VDFs, instead, take the second approach and try to
find a trustless and convenient solution to measure the passage of time.

A commonly proposed universal time delay source is “maximum computation
speed”, as in the fastest way that a specific computation can be
performed in any implementation of any computational model in the world.
This is deemed as “universal” because, if no participant in the
world can perform a certain computation faster than the expected amount
of time, it can be used as a universal time delay reference for humans.

§.§ Use-Cases

VDF schemes are particularly interesting because reliable and efficient
time delay outsourcing leads to innovative computer science
applications. The original applications were of cryptographic value:

* timed encryption: also known as “time capsules”, they would
allow for self-decrypting messages through a “timed key escrow”
[ref-timedkeyescrow232]) mechanism, where a
Trapdoor-VDF would reveal the key after some elapsed time. Timed
encryption can be leveraged to build scheduled payments: one
could prepare multiple transactions in advance, and they would
self-decrypt in due time. At any moment prior to the deadline, the
owner can invalidate the payments. Timed encryption can be used for
many scenarios, such as timed top secret archives, in order
to guarantee security and transparency for a country's intelligence

* timed commitments: using timed encryption as a building
block, one can build self-revealing commitment
schemes[ref-timedcommitments33], which can
be used for lots of protocols, including auction bidding:
everyone commits during the first phase, and in the second phase the
bids self-reveal. Timed commitments can also be used for other
voting protocols, where the vote is revealed after the voting
has taken place.

* slow-timed hash functions: delay functions are interesting
alternatives to classic iterated hashing techniques and Key Derivation
Functions, with the advantage of being scalable and
sequential. They can be used for password storage,
when the password are generated by humans, in order to stave off
brute-force pre-image attacks. Compared to classic techniques (such as
scrypt), VDFs do not leverage memory, instead relying on
sequentiality. Initial slow-timed hash function constructions were the
precursors to what eventually became “Verifiable Delay Functions” in

In practice, the ability for VDFs to generate public random numbers
(when given a biased entropy source) can be the basis for achieving
Transparency in many other protocols, such as a lottery. Over the last
few years, there has also been increased interest in adapting VDFs to
cryptocurrencies, where the lack of a trusted third party is a common

* transparent public PRNG beacon: The main properties of random
numbers is that they're both unpredictable and their generation
is unbiased. Classic solutions to generating public random
numbers on the blockchain have been to either: take block hashes, or
use MPC computations [ref-BGB1734]. The
problem is that repeating MPC computations is highly inconvenient (all
parties must be online at the same time and perform hefty
computations), and that block hashes are subject to the biased
selection of transactions by PoW miners.

Using VDFs as “slow-timed hash functions”, we can generate random
numbers on the blockchain which remain secret for a short period of
time. The main idea is that we can use transaction history as an
(unpredictable) entropy source[the entropy for a Bitcoin
block hash (approx 10 minutes of transaction time) was estimated to
be \(\approx 70\) bits in 2015 by
[ref-BCG1535], and it is based directly on
the difficulty of the mining problem. On Ethereum, blocks are
published \(\approx 40\) times more frequently (i.e. around \(15\)
seconds per transaction) [ref-BGB1734],
which entails lower entropy for each block hash.], and then remove
the bias introduced by miners by using VDFs. The VDF inputs are block
hashes, and the outputs are our random numbers: the miners can bias
the inputs only up to the block's confirmation time (not just its
publication), after which they cannot be changed. If the VDF delay is
longer than an input block's confirmation time, then the outputs will
become unbiased because the miners won't be able to evaluate and
change them at the same time. Of course, it is important to accurately
measure the maximum block confirmation time for the blockchain at
hand, after which any miner attack becomes infeasible, and set it to
be smaller than the VDF delay.

* transparent lottery systems: much like Randomness Beacons,
lottery systems require the selection of a random number only after
all relevant actions (i.e. the betting) have taken place. The trick is
the same, and players are given less time to bet than it takes to
figure out the random number, fixed at the beginning of the
computation by using block hashes. I've implemented a prototype
trapdoor version of such a protocol myself, on Ethereum
Kovan[ref-traplottery36]. Of course, the
lottery game could take advantage of a Randomness Beacon and just give
players \(n\) blocks' time to bet, taking as winning number the
Beacon's output of the \(n\)-th block's hash after the start of the

* improved blockchain efficiency: arguably one of the biggest
issues cryptocurrencies have right now is the incredible waste of
resources used for mining in PoW-based blockchains. There are entire
mining farms which combined consume as much energy as a small country,
all for the purpose of making Bitcoin run. The Ethereum2.0 research
team is experimenting with PoS (Proof of Stake) consensus protocols,
where a new leader is randomly chosen to publish each block, without
the need for wasteful mining. VDFs can be used for this purpose
because their output is deterministic, but can still be used to choose
leaders in a fair (pseudo-random) fashion.

Comparing the Nakamoto hash inversion puzzle (used in Bitcoin,
BitGold, and others) with VDFs, leader selection would be akin to
fixing a PoW output from the start, and then running many parallel
processes to brute force the input space. The advantage for PoW
schemes is that they are verifier scalable, because other users
can quickly check that the correct pre-image was found. However, the
price to pay for fair currency distribution starting from a given
biased state (i.e. the previous block's hash) is a non-deterministic
search by exhaustion, which results in huge energy consumptions. VDFs
can remove the same bias present in block hashes, while still being
verifier scalable and deterministic. That's
because we fix the input instead of the output, and then proceed
sequentially with the computation: only one person needs to calculate
and publish the proof. This leads to a drastic reduction in resource
wastage, and is a highly anticipated feature of the Ethereum
blockchain.[of course, the consensus protocol also requires
incentivising users towards a unified blockchain state. In PoW
consensus protocols, miners are incentivised to mine for the longest
chain, or they risk wasting time and money; but in PoS consensus
protocols, leaders can generate multiple chains without wasting any
time. One of the suggested solutions is to force cheating leaders to
lose money, but the details are still being fleshed out for

Other interesting applications of VDFs have been identified for more
ambitious scenarios, such as Web3 and SWARM-like
[ref-SWARM37] solutions. An example is
proof of “age”, where the minimum age of a given file can be
proven to show that some information was indeed known ahead of
time[this can be regarded as the opposite of showing that a
given file is recent, such as what what abductors used to do when
taking a photo of their captives along with the daily newspaper.].

§.§ A Language for Time

But how to measure time in the time-agnostic world of computers? We
could try to equate cpu cycles and operations to the flow of time,
measuring them with a \(\textit{ real-time}\to\mu\textit{-time }\)
formula. There are a couple of issues with this approach:

* \(\mu\textit{-time}\neq\textit{ real-time}\)

Algorithms are not an immediately useful tool for measuring time,
since time runs by itself and they don't. Users might use our protocol
for measuring time, but we cannot ask them to run it indefinitely.
This means that we need to adapt our language to measuring time
delays, and not time; as long as the algorithm runs, a delay will be
measured! We won't be able to prove something like “this message at
13:54 on 1/1/2019”, but we might be able to prove something like
“this message took one week to process”. As long as the message is
unique, we can also prove “this message is from more than a week

* \(\mu\textit{-time}\neq\textit{universal}\)

The flow of time has the nice property of being the same for everyone:
nobody can speed it up or slow it down! However, this does not apply
to computers – anyone with more money can buy more processors, and
then use them to parallelise and speedup most computations.

For this reason, we aim to find sequential computations which cannot
be parallelised, such that money will not be a factor when measuring
the flow of time; thus making our protocol fair and transparent for
all users.

Now that we've identified the main issues, let's discuss the
main properties that we want for a statement \(X \in L\):

* Sequential

In order to build a reliable language for measuring time delays, we
wish to base it on sequential computations. This is because the time
spent computing paralelisable algorithms varies wildly according to
the amount of money invested: a poor individual with a single 10€
processor will run a Bitcoin mining algorithm orders of magnitude
slower than a rich company with 1000x times the same amount of
processors; this makes for unreliable time delay measurement, hence
unfair VDF protocols.The same does not occur when comparing processor
frequencies: average processors on the market lie at around 1GhZ
speeds, while the fastest ones in the world at 9GhZ – just a factor
of ten! As long as we account for maximum 10GhZ speeds in our
sequential computation, our delay measurements should apply to
everyone: nobody will be able to complete the VDF faster than the
expected amount of time, although some might take a little longer.

This solution, however, is not without flaws. An alternative to
sequentiality, frequently used in Cryptography for KDFs and password
storage, has been to employ algorithms which require using large
amounts of memory in order to greatly increase the cost for achieving
parallelised computation. Two successful examples of this are
scrypt[ref-scrypt38], commonly used
for password-based key-derivation-functions, and
Ethash[ref-ethash39], used for the
Ethereum cryptocurrency's PoW. Another issue is with the assumption
that the difference between the world's average processor speed and
the world's fastest one is “small”, and that specialised hardware
implementations (e.g. ASICs) cannot improve this margin by a
substantial amount. These assumptions are currently being researched
by the Chia Foundation and the Ethereum foundation

* Deterministic

Since we're trying to measure effective time delays, and not average
ones, our scheme cannot rely on well studied PoW protocols. The issue
being that they're typically probabilistic (as well as paralelisable):
a problem with an estimated difficulty of 1 hour might end up taking 1
second, just out of sheer luck! A deterministic computation would give
us a guarantee as to the number of performed computations, hence, the
minimum elapsed time.

§.§ Building a SPoW Protocol

The major idea behind the success of current VDFs is the specific
protocol language designed by Rivest et al. in
[ref-RSW9625], based on repeated squaring in
RSA groups. This time-delay language will become the basis for improved
VDF protocols, here is its definition:

\(\textit{Time-Lock Puzzle } TL(\Delta, \lambda, \mu)\)

\[\Big\{ (x,y) \mid y \gets \overbrace{(\mu \circ \mu \circ … \circ \mu)}^\textit{T times} (x), T \gets \Delta \cdot \frac{sec}{\Omega_{\mu_\lambda}},\ \Omega_y(\Delta), \
\\T \in \mathbb{Z}, \Delta \in \textit{seconds}, \mu: D \to C, x \in D_\lambda,\ y \in C_\lambda\Big\}\]
the practical scenarios, \(T\) is typically determined heuristically
according to the specific implementation, or based on concrete metrics
of the basic \(\mu\) operation. A typical example provided by most
researchers in their academic articles is \(T \gets 2^{40}\), however,
concrete time measurements are not typically discussed.]

Rivest et al. [ref-RSW9625] believed their
language contained intrinsic sequentiality properties, and based their
“time-lock” protocol on it. Given the difficulty of estimating a
function \((\Delta, \lambda) \to T\)[since there can be many
other costs associated with usage of SPoWs (such as network
transmission), they are not well suited for precise time measurements.
It's best to choose delays which range from a few minutes to hours or
days.], the puzzle was simply based on any \(T\) directly:

RSW96 \(TL(T, \lambda, \mu)\)

\[\Big\{ (x, y, N) \mid y \gets x^{2^T} \pmod N,\ \mu = x \mapsto x^2 \pmod N,\ \Omega_y(\Delta),\
\\T \in \mathbb{Z},\  N \in_R RSA_\lambda \textit{ modulus},\ x \in \mathbb{Z}_N^*,\ \lambda_{RSA} \textit{ derived from }\lambda\Big\}\]
is the security parameter in bits for the RSA group. From \(\lambda\)
we typically derive \(\lambda_{RSA}\), according to conventions based
on statistical brute-force attacks shared by the cryptographic
community. Today it is believed that
\(\lambda=100 \implies \lambda_{RSA} = 2048\), but this assumption may
change in the future, or have changed already.]

Clearly, calculating a power \(2^T\) which is huge (e.g. \(T=2^{40}\))
is not feasible, so we will not be able to employ classic modular
exponentiation techniques; two known techniques are shown in the
completeness proof. Here is the protocol we can derive from the

\(SPoW\)

\[\textit{Given }
\begin{cases}
L \equiv TL(T, \lambda, \mu) \subseteq \{0,1\}^* \in NP \\
T \in \mathbb{Z} \textit{ timing parameter}\\
\lambda \textit{ security parameter in bits}\\
\mu: \textit{squaring in $RSA_\lambda$}\\
N \textit{ RSA modulus}
\end{cases}\]

\[\textit{And }X \in L \iff
\land\begin{cases}
\textbf{Complete }\\
\textbf{Sound }
\end{cases}\]

The protocol is clearly complete, since the repeated \(\mu\) operation
does yield a correct \(y\):

\[\forall X \in L,\ (x, y, N) = X: Pr[y = x^{2^T} \pmod N] = 1\]
the algorithm for computing \(y\) being:
\[\begin{cases}
x \overbrace{\to x^2 \to x^{2^2} \to x^{2^3} \to … \to}^\textit{$T$ group squarings} x^{2^T} \pmod N \textit{ (order is unknown)}
\\
e \gets 2^T \pmod{\phi(N)} \land  x^e = x^{2^T} \pmod N \textit{ (order is known)}
\end{cases}\]
[in a typical SPoW scenario, the RSA group order
\(\phi(N)\) is not known to the Prover.]

(i.e. \(X \in L\) means that \((x,y)\) are correct, and
that \(\Omega(T)\) time was spent. The second algorithm for calculating
\(y\) is particularly important, since it implies knowledge of the RSA
trapdoor and private key).

The actual soundness for this language's claim to being a universal
time-delay reference (i.e. sequential and deterministic computation) is
not proven, but it does rely on two assumptions:

\[\forall X \notin TL(x): Pr[y = x^{2^T}] = \textit{negl}(\lambda)\]

if cracking RSA is hard and all TL puzzles can only be
solved in minimum T time without \(\phi(N)\) and
\(X \notin TL\) but the puzzle solved means that it took less than T
time, then the puzzle was solved with \(\phi(N)\),
then the prover had to have cracked RSA, which has negligible
probability! In order words:
\[{\left.\begin{aligned}
Pr[\exists \textit{"extractor"}\ E_{POLY}: \phi(N) \gets E(N)] = negl(\lambda)
\\ \forall x \in \mathbb{Z}_N^*: \Omega_{x^{2^T}\ w/out\ \phi(N)}(T \cdot \mu_\lambda)
\\ \Big(X \notin TL \land y = x^{2^T} \implies \Omega_{y}(< T \cdot \mu_\lambda)\Big)
\end{aligned}\right\rbrace}\land\implies
\\\Omega_y = \Omega_{x^{2^T}\ w/\ \phi(N)}(< T \cdot \mu_\lambda) \implies \exists \textit{"extractor"}\ E_{POLY} \iff
\\negl(\lambda) = Pr[\exists E: \phi(N) \gets E(N)] =  Pr[y = x^{2^T} \land w/out\ \phi(N)] = Pr[y = x^{2^T} \land X \notin L]\]

The soundness of the protocol relies on the usage of groups of unknown
order, and the inability to reverse a cryptographic one-way
function.[we will discuss another groups of unknown order
\(\mathbb{G}(\sqrt{q})\) in the subsection on transparency Section
<ref>.] In particular, two assumptions are
required for this protocol to work:

* Cracking RSA is hard (i.e. extracting \(\phi(N)\) from \(N\))

This assumption has been upheld by the cryptographic community
for decades, only being proven invalid within the still developing
context of Quantum Computers.

* There is no faster way to solve the puzzle w/out \(\phi(N)\) than with
\(\Omega(T)\) sequential \(RSA_\lambda\) group squarings
(i.e. \(\mu_\lambda\))

This was not proven in th original '96 paper by Rivest et
al.[ref-RSW9625], but it is believed to be
true by all subsequent authors (inluding
[ref-Wes1828] and others).

No specific construction for the protocol is provided[actually,
[ref-RSW9625] only states the language
\(TL\), and assumes that protocols based on its time-delaying
sequentiality will be sound. A construction is only provided for a
timed encryption use case.], but you could think of it as
something similar to Homomorphic Authenticators:

\[client\ Verifier \overset{\sigma_x}\longrightarrow server\ Prover\\
client\ Verifier\ \overset{\sigma_y}\longleftarrow server\ Prover\\
check(\sigma_y) \overset{?}= True
\\\textbf{or}\\
Verifier \overset{TL(T, \lambda, \mu),\ N,\ x}\longrightarrow Prover\\
Verifier\ \overset{y}\longleftarrow Prover\\
y \overset{?}= x^{2^T}\]

§.§.§ A note on Trapdoor-SPoWs and

So, whoever owns the RSA private key also knows \(\phi(N)\), and can
therefore invalidate the protocol and spoof proofs at will. This does
not preclude utility: the Prover may not be given the key anyway, or the
trapdoor may be used to generate “time-capsules”. In “time-capsule”
constructions the owner of the private key can take advantage of his
Trapdoor-SPoW to quickly calculate the output of a unique
\(X \in L\), and use it as OTP key to encrypt some secret message: all
others will have to wait before they can decipher his message.

At the same time, using RSA groups necessarily requires us to generate
private keys. If we wish for others to use our SPoW in a trustless
(transparent) fashion, what can we do to prove we did not keep
nor use the private keys? We will delve deeper into this topic in
Section <ref>.

§.§ “Compressing” Time

Now that we've build our SPoW universal time-delay reference, we can
proceed towards refining it. While the protocol does allow us to prove
time delays, it also requires the Verifier to wait the same amount of
time as the Prover (unless he has access to the RSA trapdoor, which is
not a scenario we wish to focus on). This can be a limiting factor for
computer applications, where performance is essential. If an auction
lasting 1 hour takes place between 100 participants we want the bids to
be revealed as soon as the auction ends, but our SPoW protocol requires
each participant to wait 100 hours before they can be sure of the
winning party. Research into (verifier) scalable SPoW protocols,
also known as VDF protocols, has recently resulted in two competing

* Cut-&-Choose:

Wesolowski came up with a proof
[ref-Wes1828] which shares some similarities
with the Schnorr \(\Sigma\text{-Protocol}\). The idea is to
“generate”[we don't actually generate all the possible
problems in practice, but only the one that will be needed. For the
purposes of this discussion, however, it does not make any
difference.] many problems isomorphic to the original SPoW, and then
solve the one chosen randomly by the Verifier. Concretely, the
isomorphic problems are derived from the SPoW output, making sure that
they still preserve the protocol's witness (i.e. that there have been
numerous sequential squarings starting form the input). This way, each
available isomorphic problem will be made dependent on the original
SPoW problem, while having the property of being much faster to check.
When the Verifier randomly selects and validates one of these
isomorphic problems he can be confident that, as long as the check
succeeds, the Prover has surely waited the correct amount of time
calculating the SPoW. The “Cut & Choose” approach was perhaps first
employed, informally, by Rabin in 1979

* Recursive Cut-&-Choose:

Pietrzak came up with another innovative protocol
[ref-Piet1829] that instead shares
similarities with the famous Graph-Isomorphism ZKIP feasibility
result, in that soundness is improved over multiple rounds of the
protocol. The protocol makes use of an intermediate execution trace
derived from the SPoW computation, where each state is made dependent
not on the input and output, but on another state that occurred just a
little earlier within the computation. When the Verifier recursively
validates these intermediate results, reaching the very first one, the
proof becomes sound. The protocol is still Cut-&-Choose, because
during each round the Verifier can select amongst many problems
isomorphic to the current state. While this technique requires
multiple rounds, increasing the verification costs, the prover
overhead is almost completely gone (unlike in the Wesolowski
protocol). The use of an “execution trace” to prove computations is
also found in STARKs, analysed in Chapter 3.

We will be discussing only the Wesolowski VDF due to its verifier
scalability; however, the second one is just as valid due to its
additional prover scalability improvement. The interesting aspect
of Pietrzak's approach is that it is better suited for time-sensitive
scenarios (e.g. PRNG beacons), where the Prover wants to submit his
result quickly and the Verifier can spare extra storage for longer
proofs. Other interesting but less successful approaches are discussed
in [ref-BBBF1824], and include making use of
SNARKs (see Section <ref>), as well as inversion
of permutation polynomials, and modular square root constructions.

§.§ Building a VDF Protocol

To build an efficient protocol we need to find a problem that is
isomorphic to our SPoW, but which is also fast to check, or
verifier scalable. Consider the main delaying factor in the SPoW
problem, \(x^{2^T} \pmod N\): the exponent \(2^T\) is way too large to
compute and store (for values such as \(T=2^{40}\)), so we need to use
our sequential repeated squaring method. Likewise, if we choose another
large exponent, the problem will stay the same. Say we decompose our
exponent into
\[\exists r \in_R Z_\lambda: 2^T = q \cdot r\]
Then, if we
assume \(\lambda \approx 100\), the value \(q\) is still very
large[the symbol \(q\) is chosen in
[ref-Wes1828] because it the “quotient”
for \(2^T / r\).], and \(x^q \pmod N\) is nearly just as hard to
compute as the original problem. So the new problem is of similar nature
as the old one, but is it isomorphic? Here's the twist, we will use a
different check function from the one in our SPoW: instead of

\[x^{2^T} \overset{?}= y \pmod N\]
We'll use

\[(x^q)^r \overset{?}= y \pmod N\]
The idea is to have the Verifier
randomly choose \(r\) after \(y\) has been submitted by the
Prover, and then wait for \((x^q)\) to be submitted by the Prover. Thus,
the Verifier only needs to perform one efficient calculation, and he can
check whether the two values \(x^q\) and \(y\) are consistent with each
other. This also has the effect of suggesting that a \(T\)-time
time-puzzle was solved, as we will discuss later in the soundness
proof, but there are still a few details to be ironed out before we can
be satisfied.

Two more security devices need to be added to this construction. The
first deals with a detail in the soundness proof, whereby we
choose a prime random value \(r \in_R PRIME_{2\lambda}\) instead of a
normal integer, which also changes the construction slightly because
\(2^T = q \cdot r + \textit{residue}\). Intuitively, this gives the
Prover more control over the check because he is not only bound to
values that might be unrelated to the SPoW (if the Prover is malicious),
but he can also factor in the input (e.g. \(x^\textit{residue}\), see
below) of the SPoW to force \(x^q\) to be chosen correctly. For related
reasons, [ref-Wes1828] also requires that we
modify our RSA group to be \(RSA_\lambda/\{\pm 1\}\). The second
observation is more of a practical requirement: since inputs for the
SPoW should be unique and randomly chosen across different protocol
executions, it is better to remove the bias of the input \(x\) by
calculating a new input \(x’ \gets H(x)\), with hash function
\(H: \{0,1\}^* \to RSA_\lambda/\{\pm 1\}\).[the hash function
can be something like
Keccak256[ref-keccak23], adapted to provide
enough \(\lambda_{RSA}\) bits, such as by iterating inputs through a
counter in a PRNG-like construction.] If this is not performed, any
biased input \(x_2 = x_1^\alpha\) can be exploited to speed-up the
computation by using a previous SPoW output and taking advantage of the
group's commutative properties:
\(x_2^{2^T} = (x_1^\alpha)^{2^T} = (x_1^{2^T})^\alpha = y_1^\alpha \pmod N\).

Finally, a note on efficiency — is it possible for the Prover to
generate the auxiliary value \(x^q\) faster than using again the
repeated squaring method, such as by taking advantage of the
relationship it has with \(x^{2^T}\)? In fact, it is, and
[ref-Wes1828] takes
\(x^q \gets x^{\lfloor\frac{2^T}{r}\rfloor}\) (the flooring is due to
the prime divisor); algorithms are discussed in the completeness
proof. Now that we've discussed how to build the protocol, here is the
construction for a \(VDF(x,y,N)\):
\[Verifier \xleftarrow{y} Prover\\
Verifier \xrightarrow{r} Prover\\
Verifier \xleftarrow{\pi} Prover\\
\pi^r x’\ ^\textit{residue} \overset{?}= y
\\\textit{where}\begin{cases}
x’ = H(x)\\
y = (x’)^{2^T} \pmod N\\
r \in_R PRIME_{2\lambda}\\
\pi = x’^{\lfloor 2^T/r \rfloor}\\
\ \textit{residue} = 2^T \pmod r\\
\end{cases}\]

\[\forall (x,y,N) = X \in VDF: Pr[\pi^r x’\ ^\textit{residue} \pmod N = y] = 1\]

This is straightforward when expanding the formula:

\[\pi^r  x'\ ^\textit{residue} = (x'\ ^{\lfloor 2^T / r \rfloor})^r  x'\ ^\textit{residue} = (x'\ ^q)^r  x'\ ^\textit{residue} \\= x'\ ^{qr + \textit{residue}} = x'\ ^{2^T} = y\]

And \(x'^{\ q}\) is calculated using
\[\begin{cases}
x'\ ^q = x'\ ^{\frac{2^T -\textit{residue}}{r}} = x'\ ^{\frac{2^T - (2^T \mod r)}{r}}= x'\ ^{\lfloor 2^T / r\rfloor} \gets \mathcal{A}(x', r, T) \ \textit{(order is unknown)}\\
x'\ ^q,\ q \gets (2^T - \textit{residue})r^{-1} \pmod{\phi(N)}\ \textit{(order is known)}
\end{cases}\]

\(\mathcal{A}\) is chosen to be the “on-the-fly long division
algorithm”, with worst complexity of \(O(2T)\), but an improved
algorithm in [ref-Wes1828] reaches
\(O(T/log(T))\), and can also be parallelised.

Just as the SPoW, this protocol can be broken if the order of the group
\(\phi(N)\) is known to the Prover. Trapdoor-VDFs are still useful, as
mentioned before, when the owner of the private RSA key is not the VDF's

\[\forall X \notin VDF: Pr[\pi^r x’\ ^\textit{residue} = y] = \textit{negl}(\lambda)\]

if cracking RSA is hard, and breaking the
Adaptive Prime Roots assumption is hard, and \(X \notin VDF\)
but the check succeeds means that either the Prover spent less than
\(\Omega(T)\) time or he chose the wrong language parameters for
\((y, \pi)\), then one of two cases holds:

* if the problem was solved in less than \(T\) steps then RSA was
broken, which is assumed to be improbable;

* if the problem was solved with wrong protocol parameters
\((y, \pi)\) and they're correlated by an exponent \(r\) in the check,
then \(\pi\) had to have been based off of \(y\)[\(\pi\) was
necessarily chosen after \(y\) because the relationship between the
two requires a parameter \(r\) that needs to be given by the
Verifier, and an honest Verifier wouldn't have continued the
protocol without having been given a \(y\) first. So \(y\) cannot be
based off of \(\pi\) in an attack against our adaptive protocol.]
(see below for exact relationship) and the exponent removed (i.e. an
exponent-root was calculated), but removing any prime exponent
requires calculating any prime root for a value in the group, which
breaks the Adaptive Prime Roots assumption, which is assumed to be of
negligible probability.

In other words:
\[{\left.\begin{aligned}
Pr[\exists \textit{"extractor"}\ E_{POLY} \in ITM: \phi(N) \gets E(N)] = negl(\lambda)
\\ \textbf{Adaptive Prime Roots Assumption} \\\iff \forall \alpha \in RSA_\lambda(N),\ \alpha \notin \{0, \pm 1\}, r \in_R PRIME_{2\lambda}: \\Pr[\exists \textit{"Extractor"} E'_{POLY} \in ITM: \sqrt[r]{\alpha} \pmod N \gets E'(\alpha)] = negl(\lambda)
\\ \forall x \in \mathbb{Z}_N^*: \Omega_{x^{2^T}\ w/out\ \phi(N)}(T \mu_\lambda)
\\ \Big[\forall x', y, \pi \in RSA_\lambda(N)/\{\pm 1\}, r \in PRIME_{2\lambda}: \\\pi^r x'\ ^\textit{residue} \pmod N = y \implies \pi = \sqrt[r]{y x'\ ^{-\textit{residue}}} \pmod N\Big]
\\ \Big[X \notin TL \land \pi^r x’\ ^\textit{residue} = y \implies \textbf{(c1)  } \Omega_{y}(< T \mu_\lambda) \lor \textbf{(c2)  } \lnot(y = x'\ ^{2^T} \land \pi = x'\ ^q)\Big]
\end{aligned}\right\rbrace}\land
\\\implies\begin{cases}
\Omega_y = \Omega_{x^{2^T}\ w/\ \phi(N)}(< T \mu_\lambda) \xLeftrightarrow{\textit{same as SPoW soundness}} Pr = \textit{negl}(\lambda)\ \textit{\textbf{(case 1)}}\\
(y \neq x'\ ^{2^T} \lor \pi \neq x'\ ^q) \land \pi = \sqrt[r]{y x'\ ^{-\textit{residue}}} \pmod N\ \textit{\textbf{(case 2)}}
\\\implies \exists \alpha \in RSA_\lambda(N)/\{\pm 1\}: y \gets x^{2^T} \alpha \land \pi \gets x^q \sqrt[r]\alpha \implies \exists \textit{"Extractor"} E'_{POLY}
\\\iff negl(\lambda) = Pr[\exists E'_{POLY}] = Pr[\pi^r x’\ ^\textit{residue} = y \land (y \neq x'\ ^{2^T} \lor \pi \neq x'\ ^q)]
\\\qquad\qquad\qquad= Pr[\pi^r x’\ ^\textit{residue} = y \land X \notin L]
\end{cases}\]

The soundness of the protocol relies on the same assumptions as the SPoW
protocol, as well as the inability to find prime roots in groups of
unknown order. In particular, two assumptions are required for this
protocol to work:

* Cracking RSA is hard

* There is no faster way to solve the puzzle w/out either breaking the
underlying SPoW time-lock puzzle, or breaking the Adaptive Roots
Assumption. It is an open question whether this assumption can
be reduced directly to the RSA hardness one, but it feels like a
natural outcome and it would be a nice security improvement.

There are two main attacks that the Adaptive Prime Roots Assumption
takes care of, when an attacker is targeting our VDF protocol. Let us
also omit any residues for the sake of keeping things simple. First,
the attacker could guess the expected Verifier's choice of \(r\), and
subsequently choose a random value \(\pi\) and set \(y = \pi^r\). This
is easily staved off by using a bruteforce-resistant security
parameter (e.g. \(2^{256}\)), for example based off of our RSA
parameter \(2\lambda \approx 200\). The second attack deals with the
reason as to why we choose \(r\) to be prime, and not just any random
number from \(\mathbb{Z}_{2\lambda}\). The reason is that if \(r\)
turns out to be a smooth-integer, then the attacker could choose
\(y = \alpha^B\), for random \(\alpha\) and \(B\) the product of many
prime powers (up to some limit); then,
\(\pi = \sqrt[r]{y} = \alpha^{B/r} \pmod N\) with
\(B/r \pmod {\phi(N)} = B/r\) if there is no residue, hence there is
no need to know the group order to calculate the root because we don't
need to work within the group. If the \(r\) is prime, then there is a
really high probability that there will be a residue left, with an
exception for the unlikely scenario where it is chosen to be equal to
one of \(\phi(N)\)'s factors.

This protocol is fully succinct, because it is both verifier

\[O_V(polylog(T)) \Longleftarrow O_V(2 \cdot \lambda) = O_V(2)\]
and it
has a succinct proof

\[O_{|\pi|}(|x| = \lambda_{RSA}))  \Longleftarrow O_{|\pi|}(1 \cdot \lambda_{RSA} + 1 \cdot \lambda) = O_{|\pi|}(1 \cdot \lambda_{RSA})\]

Specifically, the checking algorithm for the Verifier \(V\) only
requires two (\(\pi^r\) and \(x'\ ^{\textit{residue}}\)) small
\(RSA_\lambda\) group exponentiations, which require respectively
\(|r|\) and \(|\textit{residue}|\) group-squarings using the
“square-and-multiply” algorithm, and a group multiplication to put
them together for the equality check. As for the messages required to
complete the proof, only \(\pi\) and \(r\) need to be transferred, the
first one is just a group element and the second one is much smaller
(due to the fact that \(\lambda_{RSA}\) is derived from \(\lambda\))

§.§ Eliminating Trust Issues

Now that we've achieved such a cool protocol, let's address a final
issue: how to make multiple parties use the same VDF without fear of
cheating? Alternatively, how to achieve transparency?

The only construction we've mentioned so far, using RSA groups, clearly
requires someone to generate private keys which, as we've seen earlier,
can be used to break the protocol. What we really need are techniques to
prevent anyone from owning the private key, so that nobody even has the
chance to cheat. Here are a three strategies discussed by

* Alternative modulus generation: There is an approach to
generating RSA groups, presented by
[ref-Sander9942], which aims to completely
skip the private key generation by randomly selecting a large modulus
which can satisfy RSA requirements with high probability. If this
modulus is indeed large and chosen randomly, nobody should be able to
extract \(\phi(N)\) from it. While this method is the simplest and
most efficient way to patch our protocol, it does not always lead to
correct RSA groups and it is believed to severely damage VDF
sequentiality requirements, leading to more efficient \(\mu_\lambda\)
implementations. Thus, it might break SPoW soundness assumptions and
cannot be used reliably.

* MPC-based RSA setup: a popular solution to solving trust
issues is, as we've discussed already, distributing trust. As it so
happens, secure Multi-Party Computation protocols (e.g. Yao's garbled
circuits [ref-twompc43] and secret sharing
with arithmetic circuits[ref-multimpc44])
would allow multiple participants to jointly generate a provably valid
RSA modulus, without leaking the private key to anyone; a technique
for this is presented in [ref-Boneh9745].
Such MPC-based approaches are practical enough that they were also
employed by the ZCash cryptocurrency
[ref-Zcash46] for its setup.

Unfortunately, this method is secure only if at least one party in the
computation is honest, which means that all (independent) parties
interested in using the transparent VDF protocol should
participate in the setup phase, to be sure that it is trust-less.
However, in blockchain scenarios multiple parties join the protocol
long after the initial setup phase — which means that some degree of
trust is involved. As long as the number of (independent) parties
participating in the MPC is a significant portion of the total number
of VDF users, this method is convenient and reliable.

Since MPC setups do involve the generation of secret random values,
they cannot be considered strictly transparent, according to
the definition we gave in our VC model. However, they do provide a
strong form of trust reduction through distribution — which is
commonly cited as being the core of Bitcoin's “trustless” design. We
can consider them to be a weaker form of transparency, perhaps
called “trustlesness”.

* Alternative Groups: a newer approach, given by
[ref-Wes1828] in his VDF construction, has
been to replace RSA with a trapdoor-free multiplicative group, also
called “Class Group of an Imaginary Quadratic Field”
[ref-Buchmann8847] (adaptation to RSA
presented in [ref-BBHM0248]). This approach
promises to be uncompromising, since the group order is not known even
to the party setting it up. However, this method still requires
someone to generate the public parameters, so there is an assumption
to be made: no other setup procedure for these groups needs to allow
for a Trapdoor, so either the known setup procedure is the only one
available, or any other procedure cannot leak the group order. Given
that these groups have not yet been sufficiently studied by the
cryptographic community, this method can be considered to be less
reliable. It is, however, a very interesting topic for future
research, and it provides an innovative solution to the problem at

§.§.§ A note on VDFs as transparency

Given that VDFs can be used to build trustless Randomness Beacons, and
that these short-term[i.e. they cannot be used, once revealed,
for new protocol executions; for example, in a lottery system you may
only use numbers which have will be revealed after the bidding phase
is over. Because of this, you will need to keep using “fresh” beacon
outputs.] random numbers can be used to setup other cryptographic
protocols in a transparent fashion, it is imperative that VDFs
themselves be transparent as well. However, one does not need to go
overkill with the setup procedure — if the protocols which make use of
the Randomness Beacon have less or equal security requirements than that
of the VDF (i.e. the number of participants in the MPC phase is still
significant compared to the total number of users of the protocol), the
MPC setup procedure is still good enough for their purpose. In fact,
there are current plans [ref-ethereumvdfmpc40]
to implement a blockchain-wide VDF for the Ethereum cryptocurrency,
rather than as an isolated third-party instance, such that all the
“smart contracts” (i.e. subprotocols) running within Ethereum already
lie within its security requirements.

§ CONCLUSION

We've seen two very powerful techniques for building VC protocols: (1)
arithmetisation, used in Homomorphic Authenticators for outsourcing
small-degree computations; (2) interactivity and randomness, used in
VDFs for “compressing” computations and measuring time. It is my
belief that while many non-universal VC protocols have been considered
as part of separate fields, we should try to converge them under the
domain of Verifiable Computation, to compare them and understand the
most efficient designs behind specific cryptographic VC properties. Such
designs can later be abstracted and employed for building more
expressive protocols, as demonstrated by the execution trace idea found
in both Pietrzak's VDF protocol and many other Universal VC protocols
(e.g. STARKs), discussed in the next chapter.

Unfortunately, and due to time constraints, this chapter only barely
scratches the surface of all non-universal proof protocols that have
been built over the past decades, so I leave as an open question the
analysis and unification of the remaining ones. To motivate the reader
in that direction, allow me to acknowledge other very interesting and
influential systems:

* Sigma Protocols: \(\Sigma\text{-Protocols}\) is the field
representative of traditional Zero-Knowledge Interactive Proof
systems, which were developed decades ago with the intent of building
more practical constructions through the use of relaxed VC properties.
This is an extensive field, focusing primarily on public key
authentication, seeing the likes of the famous Schnorr Identification
and Signature scheme. Protocols from this field share many properties
with the universal proof systems discussed in the next chapter. The
Ring-based Learning With Errors scheme found in
[ref-Benhamouda1549] is an interesting
recent development in this field.

* Proof of Work: this field was made popular by the deployment
of the Bitcoin cryptocurrency, which uses it for its transactions
(i.e. proofs). A lot of research from the cryptocurrency communities
has gone into extending this field with more efficient constructions,
resulting in improved consensus solutions for decentralised-trust
protocols. A notable evolution of this field is VDF protocols, which
we analysed in this chapter.

* (RSA) Accumulators[an interesting starting point for
the reader might be
[ref-AccumulatorSoK50], which offers a
systemisation of this field, including constructions not based on
hidden order groups.]: this interesting field, whose protocols
implement very efficient operations for checking membership of an
element in a set, typically makes use of hidden order groups
(e.g. RSA). Such constructions can also support other set operations,
such as union and intersection. This field comes closest to
implementing the universality property found in Universal VC
schemes presented in the next chapter. Fun fact: Zerocoin, the
precursor to the Zerocash protocol that the Zcash
[ref-Zcash46] cryptocurrency implements, was
actually based upon RSA Accumulators.

* Attribute Based Encryption (ABE): such systems take advantage
of user identities to establish public key pairs, which offers the big
advantage of being able to send a single message to a specific
hierarchy of users without needing to collect many different keys. The
use of a public authority (i.e. Trusted Third Party) is typically
required, and almost all such systems employ homomorphic encryption,
used to build complex relationships between messages and identity

CHAPTER: UNIVERSAL VC COMPILERS

A revolution in the applicative world of cryptography, first with
Blockchain technology and now with Zero-Knowledge proofs, has been
developing over the last decade. The success achieved by these protocols
is starting to spark excitement, in the hopes that it could change not
just our societal functions (e.g. cryptocurrencies vs traditional fiat
money), but also the way we interact online and develop software. The
main goal of these efforts has been that of developing innovative
cryptography to help us regain trust in a trustless world, to help us
base all our communications on verifiable statements: to build a
“Proof of All”.

So far we've discussed the basic building blocks for cryptographic
proofs, and how specialised protocols can be designed to handle private
or computationally-sensitive scenarios. One common characteristic, and
potential downside, of using such non-universal protocols is that
adapting them to particular use-cases requires technical know-how;
compromises (in terms of VC properties) are often also required to
retain efficiency or privacy. In this chapter we will be taking a step
towards an uncompromising solution, and the jack-of-all-trades when it
comes to Zero-Knowledge proofs, Universal VC protocols. These
systems do not only protect the privacy of their users, but they can
also guarantee the integrity of any computation. Because such protocols
can be used to generate proofs based on any other program, automatically
and without much technical know-how, I call them Universal Proof

The focus of the chapter will be understanding and designing the
fundamentals of a protocol which marks a breakthrough in the field of VC
technology: zk-STARKs. While this construction is fairly recent,
it is the result of many years of research and has already been well
received by the cryptographic community. This system is the first
concretely efficient (i.e. suited for realistic usage)
Universal VC compiler that is also post-quantum safe, and does not
require any form of trusted setup (i.e. it can be used out-of-the-box,
unlike zk-SNARKs). Towards the end of the chapter we will also mention
alternative systems to zk-STARKs that have been developed in recent

§ ZK-STARKS

What are zk-STARKs? Glad you asked:

* zk, as in zero-knowledge and privacy-preserving;

* Scalable, or efficient, as proving requires little increased
overhead, generated proofs are relatively “small” (or acceptable) in
size, and verification takes exponentially less time than executing
computations naïvely (i.e. almost instantly, even for very heavy

* Transparent, as in there is no requirement for a trusted setup,
like in zk-SNARK systems;

* ARgument, as in a computationally secure cryptographic proving
scheme achieving completeness and soundness for a specific language;

* of Knowledge, as in based on statements with relation to
publicly known information (see more in Section <ref>).

But most importantly of all, (zk)STARKs are Universal Verifiable
Computation systems. Unfortunately, these definitions are not sufficient
to build or understand such systems. The construction by Ben-Sasson et
al. presented in [ref-STARK51] is fairly
complex, filled with engineering-specific details (the protocol was
designed to be concretely efficient), and overall tough to digest even
for cryptography students. For these reasons, and following the goals of
the thesis, I chose to focus on design principles, foregoing formal
proofs in favour of a simplified understanding. In this section I will
break down the core concepts of zk-STARKs, showing how a general purpose
computational-integrity statement can be converted into a proof.

In Section <ref> I will give an overview of how we're
going to approach building a STARK. Each step of our design represents a
problem instance that abstracts the following step, thus providing a
useful overview for breaking down STARKs. By taking a stricter
mathematical formalisation of the initial problem statement and
following the given reduction steps, it is possible to synthesise the
protocol into a single statement, comparable to that provided within the
original paper.[the original paper in
[ref-STARK51] also formalises and takes care
of multiple engineering optimisations, which I only briefly touch upon
later on. These details can be considered to be essential for the
implementation of a practical STARK and are an important contribution
to the achievements of the paper, as well as the basis for the
official open-source implementation provided by the authors in

Each later subsection will present: the main objective of a universal VC
system (Section <ref>); the intermediate arithmetisation process
required to break down normal computations into usable components
(Section <ref>); \(2POLY\), the name I give to the core
subprotocol used by STARKs to implement a VC proof (Section
<ref>); concrete performance results achieved by STARKs
through interactivity, and security (i.e. soundness) assumptions
(Section <ref>); the privacy extension to convert
STARKs into zk-STARKs (Section <ref>); \(FRI\), the
subprotocol used by \(2POLY\) for probabilistic degree testing (Section

§.§ The Main Design

The single most important tool which is used by all known Universal V.C.
systems is that of arithmetisation. It is the process of
converting a question on the integrity of a general purpose calculation
into a mathematical statement which we can manipulate through
cryptographic means. For zk-STARKs this is the polynomial
comparison problem, for their zk-SNARk predecessors it is
quadratic arithmetic programs, but similar ideas arise in all the
competing universal VC protocol systems, exhibiting varying approaches:
homomorphic cryptography, multiparty computation, probabilistic
checkable proofs, and interactive proofs. The original problem statement
provided here is reduced (not without any assumptions, as we will see
later) to an algebraic statement on polynomials, for which we actually
have a working cryptographic protocol. It is the final problem of
polynomial comparison on which we will focus our cryptographic tools
deriving from PCPs and IPs, the rest is mostly arithmetisation.

First, we will informally introduce the main problem of Computational
Integrity and Privacy which we are trying to solve (Section
<ref>); then we will perform a few arithmetisation steps which
bring us closer to a formal statement on polynomials (Section
<ref>); then, we will present the core polynomial comparison
and proximity testing protocols used by zk-STARKs (Section

Here is an overview of the problems addressed by our design, in
increasing order of specialisation:

[b]0.18Arithmetisation Step     [b]0.24Problem     [b]0.24Description     [b]0.24VC Benefit[t]0.181     [t]0.24Generic Statement     [t]0.24Was the output of this computation, within the specified
time-frame, correct?     [t]0.24Universality[t]0.182     [t]0.24Computational Integrity&Privacy Statement     [t]0.24Is it true that Output=Program(Input) within T steps?     [t]0.24Universality[t]0.183     [t]0.24Algebraic Problem     [t]0.24\(f(x) \overset{?}= y\), \(O_f(T)\)     [t]0.24Universality[t]0.184     [t]0.24Execution Trace Algebraic Problem     [t]0.24\(ee \overset{?}\in \mathscr{C}\), \(ee \textit{ execution trace}\),
\(\mathscr{C} \textit{ constraints}\), \(|ee| = T+1\)     [t]0.24Soundness (\(2POLY\) call format), Scalability[t]0.185     [t]0.24Polynomial Comparison Problem     [t]0.24\(f(x) \overset{?}= g(x)\), \((f,g) \in \mathbb{F}[x]\),
\(deg(f) = deg(g)\)     [t]0.24Soundness (check), Zero-Knowledge, Scalability
(engineering optimisations), Transparency

§.§ Original Problem Statement

We're looking to build a system which can represent any VC problem,
i.e. a “Proof of All” system; before building it we need to define it,
in order to state our requirements and boundaries. The researchers
behind zk-STARKs provide a language to define any trustless computation,
called Computational Integrity and Privacy (CIP) problem
statements. Such statements represent the state of the art of what
current cryptographic proof systems can achieve in any computational

First off, let's clarify the name “computational”. With this name, we
simply wish to allow the system's users to make statements regarding any
sort of general purpose computation. The universality property of
our VC model suffices to satisfy this requirement. Here are the main
properties defining CIP problem statements:

* Integrity

In order to trust the output of a specific computation, we need to
consider that a Prover may be incentivised to cheat. We can think of
income tax statements, for example, where a citizen is trying to
perform tax evasion by submitting false claims regarding his income.
To prevent this, and to trust the validity of the Prover's claim, we
need to somehow “bind” the computation's output to the actual
requirements of the computation. I also informally consider this to be
the binding property of a CIP statement, and it can be
accomplished through the completeness and soundness
properties which we defined in our VC model.

* Privacy

What happens if the output of a specific computation can be revealed,
but not its input? Consider a scenario in which I'm buying drinks at a
bar and I need to provide identification to the bartender, so that he
may check that I am of legal age to drink alcohol, but I do not want
to reveal anything else about my age, name, nationality, height, or
gender. To allow a Prover to make such a privacy-friendly claim, we
need to somehow “hide” our computation's inputs (i.e. my personal
details, in the given example) from the Verifier. I informally
consider this to be the hiding property of a CIP
statement, and it can be accomplished through the VC model's
zero knowledge, transparency, and post-quantum
safety properties.

The transparency requirement is necessary in contexts where I want
anybody to be able to verify my claim, at any point in time, without
the need for a trusted setup phase. Post-quantum resistance is also
important in any cryptographic system meant to stand the test of time,
thus becoming a reliable standard for the protection of data many
decades (if not centuries) down the road.[note, the main
assumptions made by zk-STARKs are: (1) the existence of
cryptographic One-Way hash functions; (2) the Random Oracle Model.
These assumptions are amongst the oldest to exist in cryptography,
and they have defied all sorts of cryptanalysis, including recent
Quantum computer developments.]

* Efficiency

Along with the previous two fundamental properties, Ben-Sasson et
al. mention this additional and more practical requirement. We are
concerned with the realisation of concrete systems, which can be used
under realistic and fair conditions, using hardware that is commonly
available to any average Prover or Verifier.

Assume you're tasked with extracting all the facial images of people
passing through an airport on a specified date, and then matching them
against a known-criminals' database, as part of a police
investigation. You wish to provide the list of matches as evidence for
a court hearing, but the court is skeptical of your work and wishes to
double-check the results. If the computation took 20 hours to
complete, will the court need to take just as long to verify your

Universal zero-knowledge proof systems of the past were actually very
burdensome in this regard, easily requiring terabytes of memory for
even the simplest calculations; the most efficient proof systems were
Sigma protocols, but they were only appropriate for very specialised
computations. To make our system actually usable, we need to somehow
reduce its impact to be minimal for the Prover, and actually even
convenient (i.e. much faster than normal execution) for the Verifier.
With regards to the communication complexity of our system, it should
stay within acceptable levels of Internet communication.[for
example, proving a single CIP statement typically requires the
transfer of a few hundred bytes with zk-SNARK systems, and a few
hundred kilobytes with zk-STARK systems. Considering that a CIP
statement can be used to further compress other CIP statements, both
complexities are acceptable even for repeated use in space-sensitive
environments, such as decentralised Blockchains.] To realise this
CIP property, we will have to implement multiple properties of our VC
model: prover scalability, verifier scalability,
proof succinctness, and non-interactivity[the
main strategies we will use to get all these properties are: (1)
arithmetisation; (2) random querying. In alternative systems, such
as zk-SNARKs, homomorphic encryption is also used, with a boost in
efficiency but a loss in privacy (specifically, transparency).].
With regards to non-interactivity, it is an important efficiency
measure because it allows using our system even when neither party can
communicate at the same moment. The proofs can be batched in advance,
and sent off for inspection at a later time.

Finally, we can formalise our system's language to be

Is it true that Output=Program(Input) within T steps?

\[\iff \Big\{  (P, T, x, y) \bigm\vert y = P(x),\  \textit{ “Program” } P \in ITM,\ O_P(T \textit{ steps})  \Big\}\]
here represents a state change within the program. When comparing with
other systems, it is useful to convert a step to the number of CPU
cycles that are required for each state change after converting the
program into a binary circuit. If it is hard to identify a specific
state, then every single instruction can be interpreted as a step,
with the state being the totality of the program's variables.]

A state-of-the-art system proving that \(X \in CIP\) needs to implement
the following VC properties:

* universality (it's intrinsic)

* completeness

* soundness

* zero-knowledge

* scalability

Additionally, zk-STARKs also implement

* non-interactivity

* transparency

* post-quantum safety

§.§.§ A few notes on Program Specifications

I would like to take a moment to debate on the utility of CIP statements
in real-life scenarios. In general, the problem we're trying to solve is
not always related to a specific program, as much as it is to a specific

Generic Statement
was the output of this computation, within the specified
time-frame, correct?

Given such a generic requirement, it may not always be necessary to
start execution of a STARK from the CIP statement of a binary program.
The requirements for the computation may, in fact, already be defined by
human generated program specifications, which document the
desired functionality of the program being analysed. While such
documentation is often seen underdeveloped (or lacking) even in the
biggest software projects – since unit test-cases are a cheaper
alternative – it can still serve as a concise and efficient definition
for the core functionality of a specific computation. In fact, it allows
us to skip the CIP's binary program conversion phase, and directly use
our program specification for the intermediate arithmetisation phases.

Here are two example scenarios, one which appeals to program
specifications and one which appeals to CIP statements on binary

* Copyright-Protected Streaming: a cloud provider's technician is
tasked with adding DRM to their video streaming service, in order to
comply with a recently approved European Copyright Directive. The only
issue is that the service specialises on streaming encrypted videos,
as an added privacy benefit. The technician immediately thinks to use
his favourite zero-knowledge universal VC proof system, zk-STARKs, so
as to retain privacy of the streams and minimise the impact of the new
feature on the service's performance. In this scenario the constraints
are very simple: each source file needs to be checked against a list
of blacklisted files, then it is encrypted and checked against the
corresponding stream.

While the technician could write a program to do this, compile it, and
send it over to the clients so that they can generate CIP-based
proofs, there are several downsides: (1) waste of resources, as
developing and deploying consumer-level applications can take a lot of
man hours; (2) bugs, as traditional testing does not typically
guarantee that the security specifications are met by the program with
a high degree of certainty; (3) performance hit for the clients,
because full arithmetisation of a stateful binary program can lead to
much more complex constraints and larger execution traces than is
really necessary, also leading to bloated proof sizes; (4) last but
not least is security, because the users are asked to trust that
executing a binary program will not compromise the confidentiality of
their files[note that even if the program was released as
open source, it still takes a much longer time to analyse thousands
of lines of code (also including libraries) rather than just a few
lines of specification requirements.].

A much smarter solution is that of taking advantage of appropriately
documented program specifications for the requirements of the DRM
feature, and sending those off to the clients in a standardised
format. The streaming service's users can then take advantage of
trusted zk-STARK implementations to build proofs based upon a very
small set of constraints.

* CTF Challenge: in “Capture The Flag” competitions,
participants typically take part in jeopardy-style cybersecurity games
where they must solve multiple challenges to score points. One popular
category of these challenges, known as “Pwning”, requires that
participants discover a vulnerability hidden somewhere within a given
program; to verify that a player has exploited the program
successfully, instead of just manually bypassing the security checks
through binary editing, the program is uploaded to a sandboxed server
and players are restricted to feeding it input through an internet

In all common recurrences of this scenario, a few issues arise: (1) a
server with high computational and bandwidth capacities needs to be
rented to host the vulnerable program; (2) the vulnerable program also
needs to be sandboxed or virtualised to protect the server's
integrity, leading to further impacts on computational requirements;
(3) in case of oversights made during setup of the sandbox, the server
itself may become vulnerable, leading to a potential compromise of the
whole competition[a well justified concern when dealing with