main.tex

%\documentclass[12pt,draftcls,onecolumn]{IEEEtran}
\documentclass[conference]{IEEEtran}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{verbatim}

\newcommand{\Fp}{\mathbb{Z}_p}
\newcommand{\sk}{\texttt{sk}}
\newcommand{\pk}{\texttt{pk}}
\newcommand{\id}{\texttt{id}}
\newcommand{\seed}{\texttt{seed}}
\newcommand{\ind}{\texttt{index}}
\newcommand{\out}{\texttt{output}}
\newcommand{\cmt}{\texttt{commit}}

\newcommand{\Alloc}{\textsc{Alloc}}
\newcommand{\mask}{\textsc{mask}}
\newcommand{\func}{\textsc{func}}
\newcommand{\hash}{\textsc{hash}}

\usepackage{pgf,tikz}
\usepackage{scrextend}
\usepackage{mathrsfs}
\usepackage{cite}
\usetikzlibrary{arrows}

\title{(WIP) Dilithium: A Proof-of-Archival-Storage Consensus Protocol for Subspace}
\author{Chen Feng$^{1,}$$^{ 2}$, Dariia Porechna$^{1}$, Barak Shani$^{1,}$$^{ 3}$, and Jeremiah Wagstaff$^{1}$\\
$^1$Subspace Labs\\
$^2$University of British Columbia\\
$^3$Matter Labs
\thanks{The authors are listed in alphabetical order.}}

\IEEEoverridecommandlockouts % using \thanks{}

\begin{document}

\maketitle

\begin{abstract}
    Dilithium is a new proof-of-archival-storage consensus protocol designed to provide superior
    user experience while maintaining the highest level 
    of consensus security among existing protocols.
    Dilithium combines KZG polynomial commitment, erasure coding, and function inverting
    in a unique way to achieve unprecedented efficiency. 
    In this paper, we present the fundamental construction of Dilithium
    and outline its security proofs. We also present our initial implementation results to demonstrate the protocol's practicality.
    Our early experimental evaluations show that Dilithium can significantly enhance the user experience while maintaining strong security guarantees, making it a promising candidate for practical deployment.
\end{abstract}

\section{Introduction}

\textit{Proof-of-capacity}\footnote{We use proof-of-capacity as an abstract umbrella term, capturing proof-of-space, proof-of-storage, proof-of-replication, proof-of-space-time, proof-of-retrievability, and so on.} has emerged as an intriguing alternative to proof-of-work leader-election mechanisms. 
Unlike proof-of-work (which relies on energy-intensive computation), 
proof-of-capacity leverages disk space as the underlying resource,
thereby minimizing energy consumption. 
One of the unique advantages of proof-of-capacity over other blockchain leader-election mechanisms, such as proof-of-stake, is that it leverages an external and widely distributed resource. As a result, proof-of-capacity is more egalitarian, since it enables anyone to participate in the consensus process, regardless of their computational power or wealth.
In addition, proof-of-capacity avoids 
certain design complexities associated with proof-of-stake~\cite{blockchain_resources}, making it a compelling alternative for blockchain design.


Broadly, proof-of-capacity protocols can be divided into two categories
\begin{itemize}
    \item Proof-of-(useless)-space: Prior constructions include Spacemint~\cite{spacemint} (which is based on ``graph pebbling''~\cite{proof_of_space, pose}), Chia~\cite{chia} (which is based on inverting ``random'' functions~\cite{proof_of_space, beyond_hellman}), Spacemesh~\cite{spacemesh} (which is based on incompressible proof-of-work~\cite{post}). These constructions fill disk space with cryptographic data - chunks of bytes that are reserved exclusively for proving the ownership of data. 
    \item Proof-of-(useful)-storage: As a particular example, Filecoin~\cite{filecoin} relies on a proof-of-replication mechanism~\cite{proof_of_replication_BFisch} to store several copies of a file. Their construction is also based on graph-pebbling games, moreover for efficiency they also rely on zkSNARKs. As another example, Subspace whitepaper~\cite{subspacev1} proposes to use disk space to store the blockchain history. The original construction is based on a computation-bound function called SLOTH.
\end{itemize}
For further exploration of related works in this area, please refer to Section~1.2 of the Spacemint paper~\cite{spacemint} and Section~1 of the proof-of-replication paper~\cite{proof_of_replication_BFisch}.

Despite a large variety of existing protocols, 
we believe that an ideal proof-of-capacity protocol should not only store useful data (in particular blockchain history) but also provide a superior
user experience while maintaining the highest level of consensus security among existing protocols.
In terms of user experience, the following performance metrics are most relevant 
\begin{itemize}
    \item Initialization (or setup) time: a few hours to days (depending on the amount of disk space)
    \item Proof-generation time: less than one second
    \item Proof size: hundreds of Bytes
    \item Verification time: much less than one second, ideally in the order of milliseconds
\end{itemize}

However, these goals cannot be achieved with prior constructions including the original Subpsace protocol. This has motivated us to design a new protocol that combines three ingredients, namely, KZG polynomial commitment  \cite{KZG_paper}, erasure coding \cite{erasure}, and function inverting~\cite{beyond_hellman} in a unique way in order to address the above design challenges. 

\section{Building Blocks of Dilithium}

This section provides an in-depth review of the fundamental building blocks of Dilithium.
We present how Dilithium combines KZG polynomial commitment, erasure coding, and function inverting through a novel concept called \emph{storage coins} to achieve efficiency and security. We discuss the technical details of each building block and explain how they work together to form the overall protocol design. 

\subsection{Creating Storage Coins}

We divide a file $F$ into $n$ pieces $\{ d_0, d_1, \ldots, d_{n-1}\}$, each of equal size\footnote{We can view $F$ as the blockchain history. In general, $F$ grows over time. Here, we only consider the case that $F$ is fixed and defer the general case to our protocol specification.}. 
Without loss of generality, we view each piece as a row vector of length $\ell$ over $\Fp$  (i.e., $d_i \in \Fp^\ell$)\footnote{Here, we choose $\Fp$ because we would like to apply KZG polynomial commitment later.}.
Then, $F$ can be viewed as a matrix of size $n \times \ell$ over $\Fp$.
Alternatively, each piece $d_i$ can be viewed as a polynomial $f_i(x)$ over $\Fp$ of degree at most $\ell - 1$. 
This allows us to view $F$ as a collection of $n$ polynomials $\{ f_i(x) \}_{i = 0}^{n-1}$. 

We assume that each farmer creates a farmer ID $\id$ uniformly at random over some domain. For example, $\id$ can be a (cryptographic) hash output of a farmer's public key $\pk$ (i.e., $\id = H(\pk)$).
We also assume that each farmer selects $m$ pieces (out of $n$ pieces) in a random yet \emph{verifiable} way based on its farmer ID.
We denote these $m$ pieces (or equivalently, polynomials) by $\{g_0^{\id}(x), \ldots, g_{m-1}^{\id}(x) \}$.
For example, each $g_i^{\id}(x)$ can be selected as $f_{(\id + i)\% n}(x)$, where $\% n$ is the mod $n$ operation\footnote{By abuse of notation, we convert $\id$ (from its domain) into an integer here.}.
As another example\footnote{This example corresponds to a standard coupon collector's problem. In order to make sure that every piece is selected by some farmer, we need a total of $O\left( \frac{n \ln n}{m} \right)$ farmers.}, each $g_i^{\id}(x)$ can be selected as $f_{H(\id, i)\% n}(x)$.

We are now ready to explain how a farmer creates storage coins. Let
\[
F^{\id}(x) = \begin{bmatrix} g_0^{\id}(x)\\ g_1^{\id}(x)\\  \vdots \\ g_{m-1}^{\id}(x) \end{bmatrix}
\]
be a column vector of $m$ polynomials. 
Then, we can evaluate $F^{\id}(x)$ at the following $\ell$ points: $\id$, $\id + 1$, $\ldots$, $\id + \ell - 1$\footnote{Again, by abuse of notation, we convert $\id$ into an element in $\Fp$.}.
Each evaluation $F^{\id}(\id + j)$ is a column vector of length $m$ over $\Fp$. We  call it a {\bf storage coin}
associated with $\id$ at point $\id + j$.
For the purpose of efficiency, a farmer can evaluate $\ell$ points simultaneously for every polynomial $g_i^{\id}(x)$
by using some fast polynomial-evaluation algorithms with $\mathcal{O}(\ell \log^2(\ell))$ complexity.
Alternatively, we can evaluate $F^{\id}(x)$ at another set of $\ell$ points: $\id$, $\id \cdot \omega$, $\ldots$, $\id \cdot \omega^{\ell - 1}$, where $\omega$ is a primitive root of unity over $\Fp$ with $\omega^\ell = 1$ or $\omega^{2 \ell} = 1$.


Why is a storage coin useful? If we collect all $\ell$ storage coins associated with $\id$, we can recover $F^{\id}(x)$ through polynomial interpolation.
In particular, if we collect all $\ell$ evaluation points for some polynomial $g_i^{\id}(x)$, we can recover $g_i^{\id}(x)$ through polynomial interpolation.
(There are some fast algorithms for polynomial interpolation with $\mathcal{O}(\ell \log^2(\ell))$ complexity.)
In other words, storage coins allow us to recover some pieces of the file $F$ efficiently. Hence, they represent {\bf useful storage} for $F$.

How can a farmer prove to some verifier that a storage coin $F^{\id}(\id + j)$ at point $\id + j$ is created correctly? This is a standard polynomial commitment problem. For example, we can use the
KZG commitment scheme. Let $A_i$ be the KZG commitment of $f_i(x)$ for $i \in \{0, 1, \ldots, n-1\}$. 
We consider the following two cases.
\begin{enumerate}
    \item The verifier knows $\{ A_i \}_{i = 0}^{n - 1}$. In this case, the farmer just needs to create a KZG proof for the polynomial evaluation $g_i^{\id}(x)$ at point $\id + j$, because the verifier can check whether the choice of polynomial $g_i^{\id}(x)$ is correct. For example, if $g_i^{\id}(x)$ is selected as $f_{(\id + i)\% n}(x)$, the verifier can check whether the KZG proof is consistent with $A_{(\id + i)\% n}$. 
    \item The verifier doesn't know any $A_i$. In this case, we can create a KZG commitment $T$ for $\{ A_i \}_{i = 0}^{n - 1}$ and then give $T$ to the verifier\footnote{Since $A_i$ is not an element in $\Fp$, we cannot apply KZG directly. Instead, we need to hash $A_i$ so that $H(A_i) \in \Fp$.}.  The farmer needs to provide two KZG proofs: one for the polynomial evaluation $g_i^{\id}(x)$ at point $\id + j$ and the other for the correctness of $g_i^{\id}(x)$. (That is, $g_i^{\id}(x)$ is chosen correctly according to our rule. For example, the commitment of $g_i^{\id}(x)$ is indeed $A_{(\id + i)\% n}$, which can be proven by using $T$.)
\end{enumerate}

\subsection{Creating Random Challenges}

We start with a high-level overview. At each time slot (say, one second), every farmer observes some global randomness (also referred to as the global challenge). 
Based on this global challenge, each farmer determines exactly one storage coin (out of $\ell$ storage coins) to scan. Since a storage coin contains $m$ elements in $\Fp$, this gives a farmer $m$ ``tickets'' to win the lottery. A ticket is called a winning ticket if it is ``close enough'' to the global challenge (in terms of the Hamming distance or some other distance).

More formally, let $\mathcal{C}_t$ be the global challenge at time slot $t$. Then, each farmer computes
\[
H(\mathcal{C}_t, \id) \mbox{ mod } \ell
\]
in order to decide which storage coin to scan.
For example, if 
\[
H(\mathcal{C}_t, \id) \mbox{ mod } \ell = j,
\]
then the farmer will scan $F^{\id}(\id + j)$, hoping to find a winning ticket (out of $m$ tickets). 
Alternatively, if $\mathcal{C}_t$ and $\id$ share the same domain, each farmer can simply compute
\[
\mathcal{C}_t \oplus \id \mbox{ mod } \ell
\]
to decide which storage coin to scan, since $\oplus$ operation is easier than $H(\cdot)$ operation. 
Once a farmer finds a winning ticket, it can produce a new block.
Clearly, this leader-election mechanism is in spirit similar to proof-of-work (one CPU, one vote) and proof-of-stake (one coin, one vote).

In the above construction, anyone in the system can figure out whether a particular farmer has a winning ticket, because all the operations depend on the farmer's public key $\pk$ (through $\id$) but not on the secret key $\sk$.  
The construction can be made privacy-preserving as follows. 
Each farmer creates a {\bf local challenge} by signing the global challenge $\mathcal{C}_t$ with its secret key $\sk$. Based on its local challenge, each farmer determines exactly one storage coin (in the same way as before) to find a winning ticket that is close enough to its local challenge. A farmer reveals its local challenge only after a winning ticket is found.

\subsection{Masking Storage Coins}

The previous construction is susceptible to the so-called on-the-fly computing attacks. Specifically, an attacker can store only one copy of $F$
and then ``emulate'' as many farmer IDs as possible by using its computation rather than storage resource.
Essentially, a storage coin $F^{\id}(\id + j)$ is a collection of $m$ polynomial evaluations at point $\id + j$, which can be computed on the fly. 

In order to mitigate this attack, we propose to ``mask" storage coins via function inverting. 
Consider a family of functions $\func_{\seed}: \mathcal{D}_k \to [2^k]$, where $\mathcal{D}_k$ is the domain\footnote{Two examples of $\mathcal{D}_k$ will be given in the next section.} and 
$[2^k] = \{0, 1, \ldots, 2^k - 1 \}$ is the co-domain. Note that both domain $\mathcal{D}_k$ and co-domain $[2^k]$  depend on the parameter $k$.

For simplicity, we assume that $\func_{\seed}(\cdot)$ is surjective in this section (which will be relaxed in later sections). This allows us to define a ``right inverse'' $\mask_{\seed}: [2^k] \to \mathcal{D}_k$ of $\func_{\seed}$ such that for any $\ind \in [2^k]$, we have
\[
\func_{\seed}\left( \mask_{\seed}(\ind) \right) = \ind. 
\]
Essentially, $\mask_{\seed}(\ind)$ returns a pre-image of $\ind$ under $\func_{\seed}$.


Next, we explain how to mask a storage coin
\[
F^{\id}(\id + j) = \begin{bmatrix} g_0^{\id}(\id + j)\\ g_1^{\id}(\id + j)\\  \vdots \\ g_{m-1}^{\id}(\id + j) \end{bmatrix}.
\]
We denote by $\cmt\left(g_i^{\id}(x)\right)$ the KZG commitment of $g_i^{\id}(x)$.
For each $g_i^{\id}(x)$, we set
\[
\seed = \id \oplus H\left( \cmt\left(g_i^{\id}(x)\right) \right).
\]
Then, for any $j \in [2^k]$, we compute $g_i^{\id}(\id + j) \oplus H\left( \mask_{\seed}(j) \right)$ as a masked version of $g_i^{\id}(\id + j)$, denoted by $\tilde{g}_i^{\id}(\id + j)$.
Applying this procedure to all $\{ g_i^{\id}(\id + j) \}_{i = 0}^{m - 1}$, we obtain a {\bf masked storage coin}.
As we will soon see, for the purpose of efficiency, a farmer can mask $\ell$ points for a polynomial $g_i^{\id}(x)$ and then move to another polynomial, say $g_{i+1}^{\id}(x)$.
Alternatively,
we can use $H\left( \mask_{\seed}(j) \right)$ to mask $g_i^{\id}(\id \cdot \omega^j)$ instead of $g_i^{\id}(\id + j)$, where $\omega$ is a primitive root of unity\footnote{In the C-KZG library, $\omega$ is chosen such that $\omega^{2 \ell} = 1$.}.

Why is the masking function $\mask_{\seed}(\cdot)$ useful? First, the attacker has to invert $m$ functions on-the-fly in order to emulate a masked  storage coin. This requires excessive space-time resources, as we will see later.
Second, the attacker cannot reuse its space-time resources to emulate different farmer IDs. In particular, even if two farmer IDs have a same polynomial in common, the attacker still needs to invert two different functions (because of the difference in $\seed$). 


\subsection{Putting Everything Together}

We are now ready to put all the building blocks together. Recall that the file $F$ consists of $n$ pieces $\{d_i\}_{i = 0}^{n-1}$, which can be viewed as $n$ polynomials $\{ f_i(x) \}_{i = 0}^{n-1}$. Recall that
$A_i$ is the KZG commitment of $f_i(x)$ and $T$ is the KZG commitment of $(H(A_0), \ldots, H(A_{n-1}))$. We assume that $T$ is public information.
Let $\pi_i$ be the KZG proof for $H(A_i)$. With $\pi_i$, anyone in the system can verify whether $A_i$ is consistent with the public information $T$.

Each farmer generates a key pair $(\sk, \pk)$ and derives its farmer ID $\id$ (e.g., $\id = H(\pk)$).
With a given $\id$, the farmer selects $m$ polynomials $\{g_i^{\id}(x) \}_{i = 0}^{m - 1}$ and retrieves their KZG commitments $\{\cmt\left(g_i^{\id}(x) \right \}_{i = 0}^{m - 1}$
together with the proofs with respect to $T$. Then, the farmer creates $\ell$ storage coins 
$\{ F^{\id}(\id + j) \}_{j = 0}^{\ell - 1}$ and generates their masked versions by using the function $\mask_{\seed}(\cdot)$ as described before.
Finally, the farmer stores $\ell$ masked storage coins as well as some metadata (i.e., $m$ commitments $\{\cmt\left(g_i^{\id}(x) \right \}_{i = 0}^{m - 1}$ together with their proofs).
This process is often called {\bf plotting} in the literature.

Recall that a global challenge $\mathcal{C}_t$ is generated at time slot $t$, based on which each farmer selects one masked storage coin and collects $m$ lottery tickets from it. If a farmer finds a winning ticket, it has to prove the following
\begin{itemize}
    \item the winning ticket (say, $\tilde{g}_i^{\id}(\id + j)$) is indeed close enough to $\mathcal{C}_t$
    \item the unmasked element ${g}_i^{\id}(\id + j)$ is correct
\end{itemize}
This process is called {\bf farming} in the literature. 

The above construction provides a new leader-election mechanism, which can be combined with some longest-chain protocol to produce a consensus algorithm.
A diagram of the above construction will be provided at the end of this paper to better illustrate the interaction of different building blocks.

% \subsection{Advantages of Our Construction}

% Here, we summarize several advantages of our proposed construction before conducting a formal analysis.
% \begin{enumerate}
%     \item The use of storage coins enlarges the design space. In PoR, a file is the smallest unit. In the ECP paper, a RS coded piece is the smallest unit. In our construction, a polynomial coded piece is the smallest unit.
%     \item The enlarged design space makes it easier for us to choose good parameters.
%     \item The usefulness of storage coins can be verified through standard KZG, which implies low communication and fast verification.
%     \item Unlike proof-of-replication, farmers have more incentives to store encodings $\{ R_j(\id) \}_{j = 1}^L$ because these encodings are lottery tickets (which are hard to compute on-the-fly).
%     \item Once a farmer has one storage coin, it can participate in the lottery.
%     \item Storage coins support a dynamic setting.
%     \item The size of a storage coin is relatively small, making it easier to apply slow encoding. I suspect that even the second solution described above might be sufficient.
% \end{enumerate}




\section{Extensions}

Our basic construction assumes that $\func_{\seed}(\cdot)$ is surjective. In this section, we explain how to relax this assumption with erasure coding through two examples.

% relies on an ``ideal'' function $\mask(\cdot)$ that has three properties. The first two properties are easy to achieve, but not the third one. Indeed, we don't have a concrete example of $\mask(\cdot)$ at the time of writing. Instead, we have a weaker version of $\mask(\cdot)$ in which the third property is relaxed. In this version, $\seed$ and $k$ determine a random function $h(\cdot)$ that requires a significant amount 
% of space to invert, and the output of $\mask(\cdot)$ is a pre-image of $\ind$ under $h$. Since the pre-image (of $\ind$ under $h$) can be empty or a set with multiple elements, the output of $\mask(\cdot)$ is not always a single value. We would like to show that this is not an issue.
% To this end, we consider three possible examples of $\mask(\cdot)$.

\noindent {\bf Example 1:} Construct $\func_{\seed}: [2^k] \to [2^k]$ as 
\[
\func_{\seed}(x) = \hash(\seed \| x),
\]
where $\|$ denotes concatenation and $\hash: [*] \to [2^k]$ is a cryptographic hash function.
Then, under the random oracle model, for any given $\seed$, $\func_{\seed}: [2^k] \to [2^k]$ is a random function 
that maps an input in $[2^k]$ to an output uniformly chosen from $[2^k]$.

Let $\ind \in [2^k]$. We have the following two cases.
\begin{enumerate}
    \item $\ind$ has at least one pre-image under $\func_{\seed}$. In this case, $\mask_{\seed}(\ind)$ is well defined and we simply mask $g_i^{\id}(\id + \ind)$ as we did before.
    \item $\ind$ has no pre-image under $\func_{\seed}$. In this case, $\mask_{\seed}(\ind)$ doesn't exist and we cannot mask $g_i^{\id}(\id + \ind)$, leavng it unmasked.
\end{enumerate}
Then, for each storage coin $F^{\id}(\id + \ind)$ at point $\id + \ind$, we only store its masked elements (and discard its unmasked elements).

Previously, we need a total of $\ell$ storage coins (in order to recover the original pieces). How many storage coins do we need now?
Clearly, this number $L$ should be between $\ell$ and $2^k$ (i.e., $\ell < L \le 2^k$).
In fact, this question is closely related to the balls-and-bins problem. 
Suppose that we have $2^k$ balls and $2^k$ bins with each ball placed into a bin uniformly at random and independent of each other.
Then, the fraction of empty bins is approximately $\frac{1}{e}$ for large $2^k$.
In other words, the fraction of non-empty bins is approximately $1 - \frac{1}{e}$.
This implies that $\frac{\ell}{L} \ge 1 - \frac{1}{e}$ if we would like to have at least $\ell$ non-empty bins out of the first $L$ bins. 
In fact, the probability of an ``error event'' (of having fewer than $\ell$ non-empty bins out of the first $L$ bins) can be approximately bounded by $\exp\left(- 2^k D_{KL}(1 - \ell/L, 1/e) \right)$. The larger $L$ is, the larger the term $D_{KL}(1 - \ell/L, 1/e)$ is, and the smaller the error probability.
This can be used as a guideline for choosing $L$.

%To see this, on the one hand, the fraction of empty bins is approximately $1/e$ for large $k$, and on the other hand, the fraction of non-empty bins should be no smaller than $\ell/2^{k}$ in order to ``mask'' $\ell$ polynomial evaluations.
%(To do: cite more results here.)

%A concern here: the variance creates grinding opportunities (because the number of tickets is no longer fixed). Luckily, we can show that the variance is indeed small.

\noindent {\bf Example 2:} Let $p: [2^k] \to [2^k]$ be a random permutation. Define the domain $\mathcal{D}_k \subset [2^k] \times [2^k]$ as the set 
\[
\{ (x_1, x_2) : p(x_1) = \pi\left( p(x_2) \right) \},
\]
where $\pi$ can be any involution without a fixed point (e.g., flipping all the bits).
Construct $\func_{\seed}: \mathcal{D}_k \to [2^k]$ as 
\[
\func_{\seed}(x_1, x_2) = \hash(\seed \| x_1 \| x_2).
\]

In Example~2, we can view any $(x_1, x_2) \in \mathcal{D}_k$ as a ball and so
our analysis for Example~1 still applies here. 
Note that $\mask_{\seed}(\cdot)$ here returns an element in $\mathcal{D}_k$ instead of $[2^k]$.
%Also, a pre-image of $h(\cdot)$ is of the form $(x, x')$ rather than $x$ only, because otherwise the verifier has to find $x'$.

There are some interesting space-time lower bounds in the literature 
related to Examples~1 and 2. 

\noindent {\bf Lower Bound 1:}
For any oracle-aided algorithm $\mathcal{A}$, it holds that for most random functions
$\func: [2^k] \to [2^k]$, if $\mathcal{A}$ is given advice (that can arbitrarily depend on $\func$)
of size $S$, makes at most $T$ oracle queries and inverts $\func$ on $\epsilon 2^k$ values, we have
\begin{equation}
    S \cdot T \in \Omega\left(\epsilon 2^k \right).
\end{equation}


\noindent {\bf Lower Bound 2:}
For any oracle-aided algorithm $\mathcal{A}$, it holds that for most functions
$\func: \mathcal{D}_k \to [2^k]$ constructed in Example~2, if $\mathcal{A}$ is given advice (that can arbitrarily depend on $\func$)
of size $S$, makes at most $T$ oracle queries and inverts $\func$ on $\epsilon 2^k$ values, we have
\begin{equation}
    S^2 \cdot T \in \Omega\left(\epsilon^2 2^{2k} \right).
\end{equation}

However, Lower Bound~2 only applies when $T \le \left(2^k/4 e \right)^{2/3}$. This restriction seems to be mostly related to the proof technique. Here, we conjecture that it still holds even when $T > \left(2^k/4 e \right)^{2/3}$.

Let us compare these two lower bounds. For simplicity, we set $\epsilon = 1$ and $S = \sqrt{2^k}$. Then, Lower Bound~1 says that 
$T \in \Omega\left(\sqrt{2^k} \right)$ and Lower Bound~2 states that $T \in \Omega\left( 2^k \right)$.
That is, Lower Bound~2 requires significantly longer time $T$ under the same amount of space $S$, because the function in Example~2 is more complicated than that in Example~1.
Intuitively, we can achieve a better lower bound 
\[
S^q \cdot T \in \Omega\left(\epsilon^q 2^{qk} \right)
\]
with $q \ge 3$ if we make the function $\func$ even more complicated. A particular approach is given in~\cite{beyond_hellman}, which is the key idea behind the Chia project.

% {\bf Example 3:} $h(\cdot)$ is constructed via Chia PoS tables. In this example, an output is of the form $(x_1, x_2, \ldots, x_{64})$. Assume that all seven functions $f_1(x), \ldots, f_7(x)$  are random functions.
% Then, for any \emph{weakly distinct} tuple $(x_1, x_2, \ldots, x_{64})$, the probability it passes the challenge is $2^{-64k}$.
% Note that in Example~2, for any \emph{weakly distinct} tuple $(x_1, x_2)$, the probability it passes the challenge is approximately $2^{-2k}$. Therefore, our analysis for Example~2 is a good approximation.

Finally, recall that the number of storage coins $L$ satisfies $\ell < L \le 2^k$. Since we need to invert $\func(\cdot)$ on $L$ values (for $\ind \in \{0, 1, \ldots, L - 1 \}$), we can rewrite the above lower bound in a simpler form 
\begin{equation}\label{eq:general_bound}
    S^q \cdot T \in \Omega\left(L^q \right).
\end{equation}

In the plotting phase, we essentially find pre-images of all $L$ values  and then XOR a pre-image of $\ind$ (if it exists) with the corresponding polynomial evaluation at $\id + \ind$. 
This corresponds to one extreme case of the space-time lower bound where we set $S = L$.
On the other hand, on-the-fly computing corresponds to the other extreme case where we set $S = 1$ and obtain $T \in \Omega\left(L^q \right)$.


% We now understand the extensions of our basic construction. Before conducting a formal analysis, let us present several possible attacks and their mitigation methods in order to better understand our construction.

% {\bf Attack 1:} If $\mask_{\seed}(\cdot)$ returns multiple outputs, an attacker can produce multiple tickets instead of one.

% \begin{itemize}
%     \item Mitigation Method 1: If the verifier can figure out which output is the first, then this issue can be resolved.
%     \item Mitigation Method 2: We allow the farmers to produce multiple tickets from multiple outputs. This introduces some randomness, which can be bounded by using the analysis above.
% \end{itemize}

% {\bf Attack 2:} The attacker stores the Chia PoS tables on disk instead of the masked storage coins.

% \begin{itemize}
%     \item Mitigation Method 1: We can choose $k$ so that Chia PoS tables are sufficiently larger than the corresponding masked storage coins.
%     \item Mitigation Method 2: We estimate the amount of additional disk look-ups and then use an economic security argument.
% \end{itemize}

% {\bf Attack 3:} The attacker stores the Chia PoS tables on memory.

% \begin{itemize}
%     \item We show that the memory storage cost is larger than the disk storage cost.
% \end{itemize}

% {\bf Note:} Both Attack 2 and Attack 3 can be well mitigated by using a large $k$. However, we have some practical upper bound on $k$. So, we need a {\bf tight analysis} to show that a relatively small $k$ is still OK.

% {\bf Attack 4:} The attacker exploits the case of expiring pieces. Since this case is not considered in our current model and analysis, there might be some potential attacks here.

%{\bf Attack 5:} On DSN load balancing.




\section{Security Analysis}

In this section, we conduct an initial security analysis based on the previous space-time lower bound.
Our key observation is twofold. First, the previous lower bounds capture the amount of resources one needs 
to have in order to emulate storage coins. Second, our new construction can be analyzed
by using the general framework proposed by Kiffer, Neu, Sridhar, Zohar, and Tse~\cite{blockchain_capacity}.

\subsection{System Model}

The protocol proceeds in slots of duration $\tau$. For simplicity, we consider a fixed set of $N$ farmers with equal capability. We
are particularly interested in the large system regime $N \to \infty$. In each slot, each farmer can win the lottery with probability $\rho / N$,
independently of other farmers and slots, where $\rho$ is a system parameter. When a malicious farmer wins the lottery at slot $t$, it can create multiple blocks, which is a behavior called equivocations. Note that equivocations never happen in proof-of-work protocols (when $\tau \to 0$) but can appear in our construction as explained in~\cite{blockchain_capacity}. 
A malicious farmer can emulate storage by launching Hellman attacks (as explained in~\cite{beyond_hellman}) or it can simply follow our proof-of-archival-storage construction but deviate from the longest-chain protocol (say, launching nothing-at-stake attacks).
We assume that the fraction of malicious farmers is at most $\beta$. Here, $\beta$ can be viewed as a security threshold indicating the maximum fraction of malicious farmers a system can tolerate.

\subsection{Emulating Storage Coins}

The previous lower bound \eqref{eq:general_bound} suggests the following. In order to emulate $L$ storage coins of a farmer (i.e., emulating a farmer ID), one needs $mS$
amount of space and makes at most $mT$ oracle queries with $S^q \cdot T \in \Omega\left(L^q \right)$ (where $m$ is the number of pieces a farmer stores as defined before). 
This allows us to compare our construction with Chia, since the lower bound \eqref{eq:general_bound} applies to both.
Using our notation, the parameter setup in Chia can be described as $k = 32$, $L = 2^{32}$, $m = 1$, and $q = 7$. 
In our setup, we can choose $k = 22$, $L = 2^{22}$, $m = 2^{10}$, and $q = 10$ to conduct a fair comparison, 
because the required disk space is proportional to $m L$.
Under the above setups, on-the-fly computing requires at most $T$ oracle queries to emulate a farmer ID in Chia with $T \in \Omega\left( 2^{224} \right)$,
while it requires at most $2^{10} T'$ oracle queries in our construction with $T' \in \Omega\left( 2^{220} \right)$. 
Similarly, an attacker $\mathcal{A}$ with space $S$ needs to make at most $T$
oracle queries in order to emulate  a farmer ID in Chia with $S^7 \cdot T \in \Omega\left( 2^{224}  \right)$, whereas an attacker $\mathcal{A}'$ with space $m {S}^{\frac{7}{10}}$
needs to make at most $m T'$ oracle queries in our construction with $S^7 \cdot T' \in \Omega\left( 2^{220}  \right)$.
This implies that our construction is comparable to Chia (under appropriate parameter selection) in terms of mitigating Hellman attacks for emulating storage.

Next, we would like to point out that  our construction enjoys efficient plotting. With a relatively small $k$, all the plotting operations in our construction can be done in memory, thereby eliminating the so-called ``sort on disk'' operation---the bottleneck of the Chia plotting algorithm. This enables us to achieve significantly shorter initialization time than Chia.

Finally, we would like to comment on the memory access. It is well known that Hellman attacks require a large amount of memory access. How can we derive a tight lower bound on the memory access? We aim to answer this question for Hellman attacks as well as other similar attacks (e.g., the one based on rainbow tables) as our future work. We believe that a lower bound on memory access better captures the ``hardness'' of emulating storage in our setup.

\subsection{Consensus Security}

We notice that our proof-of-storage construction is compatible with the general framework proposed in~\cite{blockchain_capacity}\footnote{Indeed, we have confirmed this with one of the authors of the paper.}. This allows us to apply the Theorem~2 of~\cite{blockchain_capacity} to our construction, obtaining the following security result.
For all $\beta < \frac{1}{2}$ and system parameters $\rho, \tau$ satisfying the condition (16) in~\cite{blockchain_capacity}, our proof-of-storage longest-chain consensus protocol with equivocation removal is secure. By investigating condition (16), we notice that we can achieve a higher security threshold $\beta$ than Chia due to our new lottery design and the use of equivocation removal. We will provide an in-depth discussion  in a more elaborated version of this work.

\subsection{Discussion}

The analysis above shows that in order to participate in the consensus protocol, a farmer can choose between different resources, namely storage $S$ or oracle queries $T$ that capture the amount of computation needed in order to participate in the lottery. Note that with a correct choice of function $\func$, the latter also requires a substantial amount of memory access.

We now turn to discuss how we design the system such that rational farmers always prefer to allocate the storage resource to the system, rather than the computation resource or a combination of both. This not only ensures that the protocol does not degrade into proof-of-work, but also eases the analysis as it allows us to focus on a single resource, namely storage. The full version of this work will give a rigorous justification.

First we reiterate that since the $\mask_{\seed}(\cdot)$ function depends on the farmer ID, creating any $2$ different plots requires running the function twice as many, thus expending the resources needed to run $\mask_{\seed}(\cdot)$. Moreover, notice that the seed depends also on the particular position $j$ in the column vector $F^{\id}$ (that is, on $g_i^{\id}(x)$), thus even for a fixed $\id$, any change to the plot requires expending the resources needed to run $\mask_{\seed}(\cdot)$.\footnote{We explain that even though the presentation above assumes the $m$ selected pieces $d_i$ of $F$ are stored in one plot, in practice we divide them into several \emph{sectors}, each with its own \emph{sector id}, and so a farmer could try many sector id's. The comment above explains that for each of these attempts, the farmer would have to pay the cost of running $\mask_{\seed}$. The plotting protocol is still deterministic, as describes above, so one could not create $2$ different sectors with the same farmer id and sector id.}

Secondly, recall that the function $\mask_{\seed}$ is parameterized by a ``difficulty'' parameter $k$. We can therefore set $k$ high enough such that creating plots ``on the fly'' is not profitable, compared to creating a single plot and storing it, which requires running $\mask_{\seed}$ only once.

In more detail, we measure the cost of storing a single piece of (masked) information $d_i$ in between challenges $\mathcal{C}_t$.\footnote{We do not discuss here the methods of cost measuring, but we highlight that one can think of the alternative cost a farmer with, say, 100GB has for some period of time, given the market for storage. We can then derive the corresponding values for the size of any $d_i$ and the challenge slot duration. We remark that this cost should also take into account the operational cost, like electricity.}\footnote{We would like also to consider the cost of obtaining the storage device in first place, assuming the farmer did not have free space -- the reason is to explain that the ``attacker'' may use their funds to buy storage. This should be a negligible cost in the long run, and we do not discuss it here. This is also the case for running $\mask_{\seed}$ in the (honest) protocol.} A single piece $d_i$ gives some amount $c$ (e.g. $c=1$) of lottery tickets per challenge $\mathcal{C}_t$.

Then, we measure the cost of running $\mask_{\seed}$ with parameter $k$ once. Running $\mask_{\seed}$ once enables to produce a single masked piece $d_i$.\footnote{Here we assume that the dishonest farmer has the entire file $F$ unmasked, hence she can draw any piece $d_i$, and assign it no extra cost (as this can be amortised among all of the attacker IDs).} This gives the farmer $c$ lottery tickets per challenge $\mathcal{C}_t$ as well. Since we have control over $k$, we can make sure that the latter cost is significantly higher than the former, thus making protocol deviation an irrational strategy.


\section{Initial Experimental Results}

In this section, we present the initial Rust implementation results of our proposed construction. 
Our evaluations were obtained on common consumer hardware - Apple M1Pro 2021, 10 cores (8 performance and 2 efficiency) and 16 GB memory.
We evaluate the performance of each component as well as the entire construction.  Our early evaluation results are encouraging, and we believe that there is still room for further optimization. 

For the KZG polynomial commitment, we currently derived public parameters locally for testing purposes only. We chose $\ell = 2^{15}$ so that the size of $d_i$ is 1MiB. 
The following four operations are required to implement KZG polynomial commitment. The evaluation results are provided below.
\begin{itemize}
    \item Converting $d_i$ into $f_i(x)$ through inverse FFT $\approx 1.6 ms$
    \item Computing the commitment $A_i$ of $f_i(x)$ $\approx 40 ms$
    \item Creating a single KZG proof for $f_i(x)$ $\approx 40 ms$
    \item Verifying a single KZG proof $\approx 865 \mu s$
\end{itemize}

We implemented the function-inverting component by using Chia PoS tables with $k = 20$, $L = 2^{16}$, and $q = 7$.\footnote{We will try other parameters (such as $k = 22$ and $q = 10$) as our next steps.} We converted their code from C++ to Rust and did various optimizations.  We have the following evaluation results
\begin{itemize}
    \item Generating $7$ function tables $\approx 325 ms$
    \item Masking $2^{15}$ points of a polynomial $\approx 7.3 ms$
    \item Constructing a Chia proof-of-space $\approx 186 ns$
    \item Verifying a Chia proof-of-space $\approx 25 \mu s$
\end{itemize}   
Our implementation achieved orders-of-magnitude improvement over Chia's C++ implementation. We will explain the reasons for this improvement in a more elaborated version of this work.

Finally, we report the evaluation results of the entire construction for leader election (without the longest-chain consensus).
\begin{itemize}
    \item Plotting phase with $m = 1000$ $\approx 300 s$
    \item Scanning a single storage coin $\approx 580 \mu s$
    \item Recovering a polynomial $\approx 880 ms$
    \item Proving a winning ticket $\approx 970 ms$
\end{itemize}
The plotting phase shows consistent usage of 3 GB of memory, suggesting that we can further increase $k$ and $q$.
Scanning a storage coin is a simple operation, only involving reading the coin from disk.
Recovering a polynomial is a complicated process, involving reading from disk all the storage coins that contain chunks of it, re-generating the Chia function tables,  XOR-unmasking, and erasure code recovery.
Proving a winning ticket consists of three steps: recovering the ``winning'' polynomial, computing a Chia proof-of-space, and creating a KZG proof. The first step is the bottleneck, and the other two steps are quite efficient.


\begin{comment}
\section{Combining Consensus Analysis with Economic Analysis}

Aim: to show that the cost of participation in the consensus protocol is lowest when following the protocol (dedicating storage for plotting).

Expense tokens: for formality we use the abstract notion of "expense tokens" to represent the cost of participation in farming.

Method: the analysis is reduced to measuring the cost of obtaining a single ``lottery ticket''.

Framework: we adopt the random-oracle model, and assume the hash functions being used in the protocol are random oracles. Hence, sectors are independent and so the analysis for a single sector suffices.

{\bf Claim I:} Consider a farmer with $r$ sectors. For any $c$, let $C_{r-1}$ be the cost of obtaining $c(r-1)$ lottery tickets in the 'first' $r-1$ sectors. Then, the cost of obtaining $c$ tickets in the remaining sector is $C_{r-1}/r$. In other words, the farming-costs per sector are equal.

(we also need to show that the protocol is "cryptographically secure" in the sense that one has to plot in order to obtain a ticket, that is one cannot break the system and obtain tickets without plotting)

{\bf Claim II:} Farmers needs to plot sectors in order to participate in consensus.


\textbf{Part I: abstract MASK function}

\textbf{Framework}

- We assume that the adversary has the entire raw history (archived), and assign it a negligible cost / we don't consider it to be part of the available storage $S$ (the reason is that for any history size, $S$ can be arbitrary large, making the history size insignificant).

- The plotting function MASK is parameterized by a value $k$. Running MASK with larger $k$ costs more expense tokens.

- We treat MASK as a black box. That is, one cannot "open" it, but only enter inputs and receive outputs. Hence, for a fixed $k$, MASK has a fixed cost per invocation.



We explain that any deviation from the (farming) protocol results in creating more sectors, hence running MASK more times.

{\bf Claim III:} Consider a farmer $F$ with storage $S$ and let $r = S/(sector-size)$. Suppose that a sector gives $c$ tickets per challenge/slot. For any challenge, if $F$ obtains more than $cr$ tickets, then $F$ created more than $r$ sectors.

{\bf proof sketch:} The protocol is designed such that any deviation requires running MASK, essentially creating a new plot.


{\bf Claim IV:} Suppose that a sector gives $c$ tickets per challenge. Let $T_S$ be the cost of obtaining $c$ lottery tickets with a single sector following the farming protocol. Let $T^*$ be the cost of obtaining $c$ lottery tickets in a hybrid strategy that combines storage and compute. Then $T^* \geq T_S$.**

** we eventually want to show that there is order(s) of magnitude difference such that if storage cost raises, the claim still holds.


{\bf Proof outline:}

Consider the hybrid strategy:

- By Claim II, since the farmer obtains $c$ tickets, it has to create at least one sector.

- By the proof of Claim III, since the farmer does not follow the farming protocol it must create at least another sector, resulting in running MASK.

- MASK is parameterized by a ''difficulty'' parameter $k$. As $k$ grows, running MASK costs more tokens (recall that also the honest party has to run it once per plotting phase).

- We can set $k$ large enough s.t. running it twice costs (significantly) more than $T_S$.

\textbf{Discussion:} The previous claim shows that the marginal cost of farming honestly, once a sector is created, is lower than (seleting and) creating another sector. This is because obtaining more tickets per challenge requires running MASK, which is designed to consume more tokens. Hence, it is best to run MASK (plot sectors) as little as possible, and only pay the ongoing cost. 

This, however, does not take into account a farmer that consumed all of its storage and still has tokens to spare. We would like to show that in this case the farmer better purchase more disk space and follow the farming protocol (assuming the amount of tokens left is not negligible). The modification to the claim above is very little, where we make sure that $k$ is large enough to account for this extra cost, amortised on the potential sectors.




\textbf{Part II: the actual MASK function}



\textbf{Part III: 'security' of the PoAS in the concrete blockchain design}
(if we see fit this may be combined with Part II)


Comments (for ourselves as we discuss this):

- The only subtle issue is that some costs are amortised among many sectors, like the hardware (even though compute hardware is modeled to be 0 cost for the attacker).

- How we measure cost: we have the freedom to define "cost of storage" as we wish, but we should make sure that it is well defined. Since hardware storage and plotting is amortised among many challenges, the formal definition should not depend on these.

- explain what we mean by cost of storage: keep abstract -- the cost captures "whatever the overall cost is": includes HD cost, plotting -- we can break into fixed + ongoing costs

- if we succeed in making the claim generic enough then the conclusion holds for \textit{any time frame} in which the (honest) farmer decide to spend their entire token budget (that is, the honest farmer can plot a single sector and let it consume expense token "slowly" or she can plot as many sectors as the storage he has let her, consuming more tokens).
\end{comment}


\section*{Acknowledgement}
The authors would like to thank Nazar Mokrynskyi for his impressive Rust implementation of the proposed construction. The authors would also like to thank
Shashank Agrawal and Joachim Neu for fruitful discussions throughout this project. CF would like to thank Khadijeh Bagheri, Hoang Dau, and Hassan Khodaiemehr for their useful comments on a draft version of this work.

\begin{thebibliography}{9}

\bibitem{beyond_hellman}
Abusalah H., Alwen J., Cohen B., Khilko D., Pietrzak K., and Reyzin L.
\emph{Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space}
Advances in Cryptology -- ASIACRYPT 2017, pp. 357–379.

\bibitem{pose}
Ateniese, G., Bonacina, I., Faonio, A., and Galesi, N.
\emph{Proofs of Space: When Space Is of the Essence}
SCN 2014: Security and Cryptography for Networks, pp. 538–557.

\bibitem{blockchain_resources}
Azouvi S., Cachin C., V. Le Duc, Vukolic M., and Zanolini L.
\emph{Modeling Resources in Permissionless Longest-chain Total-order Broadcast}
arXiv:2211.12050 [cs.CR],
https://doi.org/10.48550/arXiv.2211.12050.

\bibitem{spacemesh}
Bentov I., Loss J., Moran T., and Shani B.
\emph{The Spacemesh Protocol: Tortoise and Hare Consensus… In… Space}
https://spacemesh.io/blog/spacemesh-protocol-v1.0/,
https://drive.google.com/file/d/18I9GPebWqgpvusI1kMnAB9nayBbL-1qN/view.

\bibitem{chia}
Cohen B., and Pietrzak K.
\emph{The Chia Network Blockchain}
https://docs.chia.net/green-paper-abstract/,
https://docs.chia.net/assets/files/Precursor-ChiaGreenPaper-82cb50060c575f3f71444a4b7430fb9d.pdf.

\bibitem{proof_of_space}
Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak
\emph{Proofs of Space}
Advances in Cryptology -- CRYPTO 2015, pp. 585–605.

\bibitem{proof_of_replication_BFisch}
Fisch B. \emph{PoReps: Proofs of Space on Useful Data} Cryptology ePrint Archive, Paper 2018/678, 2018. [Online]. Available: https://eprint.iacr.org/2018/678.

\bibitem{KZG_paper}
Kate A., Zaverucha G., and Goldberg I.  \emph{Polynomial commitments} Technical report, 2010. CACR 2010-10, Centre for Applied Cryptographic Research, University of Waterloo.

\bibitem{blockchain_capacity}
Kiffer L., Neu J., Sridhar S., Zohar A., Tse D.
\emph{Security of Blockchains at Capacity}
Cryptology ePrint Archive, Paper 2023/381,
https://eprint.iacr.org/2023/381.

\bibitem{erasure}
Li J., and Li  B. \emph{Erasure coding for cloud storage systems: A survey} in Tsinghua Science and Technology, vol. 18, no. 3, pp. 259-272, June 2013.

\bibitem{post}
Moran T., and Orlov I.
\emph{Simple Proofs of Space-Time and Rational Proofs of Storage}
Advances in Cryptology -- CRYPTO 2019, pp. 381–409.

\bibitem{spacemint}
Park S., Kwon A., Fuchsbauer G., Ga\u{z}i P., Alwen J., and Pietrzak K.
\emph{SpaceMint: A Cryptocurrency Based on Proofs of Space}
Cryptology ePrint Archive, Paper 2015/528,
https://eprint.iacr.org/2015/528.

\bibitem{filecoin}
Protocol Labs
\emph{Filecoin: A Decentralized Storage Network}
https://filecoin.io/filecoin.pdf.

\bibitem{subspacev1}
Wagstaff J.
\emph{Subspace: A Solution to the Farmer’s Dilemma}
https://subspace.network/news/subspace-network-whitepaper,
%\text{https://assets.website-files.com/61526a2af87a54e565b0ae92/617759c00edd0e3bd279aa29_Subspace_%20A%20solution%20to%20the%20farmer%27s%20dilemma.pdf}.

%\bibitem{rainbow_table}



\end{thebibliography}


\begin{figure*}
\definecolor{wwccqq}{rgb}{0.4,0.8,0.} %blockchains color
\definecolor{qqqqcc}{rgb}{0.,0.,0.8} %MASK
\definecolor{dcrutc}{rgb}{0.8627450980392157,0.0784313725490196,0.23529411764705882} %KZG proofs
\definecolor{ccffcc}{rgb}{0.8,1.,0.8} %Farmers
\definecolor{ffzzqq}{rgb}{1.,0.6,0.} %H color
\definecolor{qqzzff}{rgb}{0.,0.6,1.} %Commit
\begin{addmargin}[-1em]{0em}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm]
\clip(-2.614586914064175,-20.15503204157287) rectangle (17.039468142260514,2.5412428722987683);
\fill[line width=2.pt,fill=black,fill opacity=0.05] (0.6650403483010345,2.252882635736503) -- (2.269953999116951,2.252882635736503) -- (2.269953999116951,1.4245401062831302) -- (0.6650403483010345,1.4245401062831302) -- cycle;
%===================================
\fill[line width=2.pt,fill=black,fill opacity=0.05] (1.818,-6.45) -- (2.9,-6.45) -- (2.9,-8.3) -- (1.818,-8.3) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (1.9400,-11.15) -- (2.9,-11.15) -- (2.9,-13) -- (1.9400,-13) -- cycle;
%===================================
\fill[line width=2.pt,fill=black,fill opacity=0.05] (0.6650403483010345,1.0793973856775576) -- (2.269953999116951,1.0793973856775576) -- (2.269953999116951,0.2510548562241848) -- (0.6650403483010345,0.2510548562241848) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (0.7180048123904461,-0.5927331001421212) -- (2.322918463206361,-0.5927331001421212) -- (2.322918463206361,-1.421075629595494) -- (0.7180048123904461,-1.421075629595494) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (2.9840182861914197,2.252882635736503) -- (4.588931937007336,2.252882635736503) -- (4.588931937007336,1.4245401062831302) -- (2.9840182861914197,1.4245401062831302) -- cycle;
\fill[line width=2.pt,color=qqzzff,fill=qqzzff,fill opacity=0.1] (5.418945120976323,2.2142330034383306) -- (7.723858771792239,2.2142330034383306) -- (7.723858771792239,1.3858904739849578) -- (5.418945120976323,1.3858904739849578) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (2.9646934700423326,1.0547440344931456) -- (4.569607120858249,1.0547440344931456) -- (4.569607120858249,0.22640150503977274) -- (2.9646934700423326,0.22640150503977274) -- cycle;
\fill[line width=2.pt,color=qqzzff,fill=qqzzff,fill opacity=0.1] (5.360970672529065,0.9967695860458878) -- (7.665884323344981,0.9967695860458878) -- (7.665884323344981,0.168427056592515) -- (5.360970672529065,0.168427056592515) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (2.9840182861914197,-0.5685405220301103) -- (4.588931937007336,-0.5685405220301103) -- (4.588931937007336,-1.3968830514834831) -- (2.9840182861914197,-1.3968830514834831) -- cycle;
\fill[line width=2.pt,color=qqzzff,fill=qqzzff,fill opacity=0.1] (5.360970672529065,-0.5878653381791974) -- (7.665884323344981,-0.5878653381791974) -- (7.665884323344981,-1.4162078676325702) -- (5.360970672529065,-1.4162078676325702) -- cycle;
\fill[line width=2.pt,color=ffzzqq,fill=ffzzqq,fill opacity=0.1] (8.745715532151925,2.252882635736503) -- (10.350629182967838,2.252882635736503) -- (10.350629182967838,1.4245401062831302) -- (8.745715532151925,1.4245401062831302) -- cycle;
\fill[line width=2.pt,color=ffzzqq,fill=ffzzqq,fill opacity=0.1] (8.758877888902111,1.0135856019266232) -- (10.363791539718024,1.0135856019266232) -- (10.363791539718024,0.18524307247325034) -- (8.758877888902111,0.18524307247325034) -- cycle;
\fill[line width=2.pt,color=ffzzqq,fill=ffzzqq,fill opacity=0.1] (8.718004812390424,-0.5927331001421212) -- (10.322918463206337,-0.5927331001421212) -- (10.322918463206337,-1.421075629595494) -- (8.718004812390424,-1.421075629595494) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (12.742240963545123,2.352882635736501) -- (13.247154614361039,2.352882635736501) -- (13.247154614361039,-1.4754598937168613) -- (12.742240963545123,-1.4754598937168613) -- cycle;
\fill[line width=2.pt,color=qqzzff,fill=qqzzff,fill opacity=0.1] (14.099803567248562,0.8880549125817581) -- (16.404717218064505,0.8880549125817581) -- (16.404717218064505,0.05971238312838523) -- (14.099803567248562,0.05971238312838523) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (0.718791425238348,-3.5114097527777703) -- (2.323705076054254,-3.5114097527777703) -- (2.323705076054254,-4.339752282231143) -- (0.718791425238348,-4.339752282231143) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (4.067221140513448,-3.20994488658799) -- (6.3721347913293815,-3.20994488658799) -- (6.3721347913293815,-4.6382874160413605) -- (4.067221140513448,-4.6382874160413605) -- cycle;
\fill[line width=2.pt,color=dcrutc,fill=dcrutc,fill opacity=0.1] (10.456149422292592,-2.1695557595211077) -- (11.161063073108538,-2.1695557595211077) -- (11.161063073108538,-3.997898288974477) -- (10.456149422292592,-3.997898288974477) -- cycle;
\fill[line width=2.pt,color=dcrutc,fill=dcrutc,fill opacity=0.1] (11.219002673448236,-2.188051617467356) -- (11.923916324264182,-2.188051617467356) -- (11.923916324264182,-4.016394146920725) -- (11.219002673448236,-4.016394146920725) -- cycle;
\fill[line width=2.pt,color=dcrutc,fill=dcrutc,fill opacity=0.1] (12.557843292172995,-2.171104267863247) -- (13.262756942988942,-2.171104267863247) -- (13.262756942988942,-3.999446797316616) -- (12.557843292172995,-3.999446797316616) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.55] (10.407049543911524,-4.545281720780878) -- (13.31196319472746,-4.545281720780878) -- (13.31196319472746,-4.773624250234253) -- (10.407049543911524,-4.773624250234253) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (0.008660190017908853,-6.43434762492424) -- (1.815765821324768,-6.43434762492424) -- (1.815765821324768,-8.262690154377612) -- (0.008660190017908853,-8.262690154377612) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (0.12987894392951116,-11.161879027476715) -- (1.9369845752363686,-11.161879027476715) -- (1.9369845752363686,-12.990221556930091) -- (0.12987894392951116,-12.990221556930091) -- cycle;
\fill[line width=2.pt,color=qqqqcc,fill=qqqqcc,fill opacity=0.1] (0.147195908774024,-9.32628075395817) -- (1.752109559589928,-9.32628075395817) -- (1.752109559589928,-10.154623283411542) -- (0.147195908774024,-10.154623283411542) -- cycle;
\fill[line width=2.pt,color=wwccqq,fill=wwccqq,fill opacity=0.1] (-0.5024902877693558,-14.732608826535447) -- (-1.0960736538904081,-15.103598430361114) -- (-1.0715789154979827,-15.803151506598658) -- (-0.45350081098450445,-16.131714979010535) -- (0.14008255513654805,-15.760725375184869) -- (0.11558781674412272,-15.061172298947325) -- cycle;
\fill[line width=2.pt,color=wwccqq,fill=wwccqq,fill opacity=0.1] (2.7587997933661246,-14.739901776026734) -- (2.165216427245082,-15.1108913798524) -- (2.1897111656375126,-15.810444456089936) -- (2.8077892701509857,-16.139007928501805) -- (3.401372636272028,-15.768018324676138) -- (3.3768778978795977,-15.068465248438603) -- cycle;
\fill[line width=2.pt,color=wwccqq,fill=wwccqq,fill opacity=0.1] (6.8818880632113295,-14.610078361458243) -- (6.288304697090288,-14.98106796528391) -- (6.312799435482719,-15.680621041521444) -- (6.930877539996192,-16.009184513933313) -- (7.524460906117234,-15.638194910107647) -- (7.4999661677248035,-14.938641833870111) -- cycle;
\fill[line width=2.pt,fill=black,fill opacity=0.05] (10.512485726572443,-14.431068034658) -- (15.3195913578793,-14.431068034658) -- (15.3195913578793,-16.259410564111377) -- (10.512485726572443,-16.259410564111377) -- cycle;
\draw [line width=2.pt] (0.6650403483010345,2.252882635736503)-- (2.269953999116951,2.252882635736503);
\draw [line width=2.pt] (2.269953999116951,2.252882635736503)-- (2.269953999116951,1.4245401062831302);
\draw [line width=2.pt] (2.269953999116951,1.4245401062831302)-- (0.6650403483010345,1.4245401062831302);
\draw [line width=2.pt] (0.6650403483010345,1.4245401062831302)-- (0.6650403483010345,2.252882635736503);
\draw (1.2808113853875651,2.123340145473461) node[anchor=north west] {$d_0$};
\draw [line width=2.pt] (0.6650403483010345,1.0793973856775576)-- (2.269953999116951,1.0793973856775576);
\draw [line width=2.pt] (2.269953999116951,1.0793973856775576)-- (2.269953999116951,0.2510548562241848);
\draw [line width=2.pt] (2.269953999116951,0.2510548562241848)-- (0.6650403483010345,0.2510548562241848);
\draw [line width=2.pt] (0.6650403483010345,0.2510548562241848)-- (0.6650403483010345,1.0793973856775576);
\draw [line width=2.pt] (0.7180048123904461,-0.5927331001421212)-- (2.322918463206361,-0.5927331001421212);
\draw [line width=2.pt] (2.322918463206361,-0.5927331001421212)-- (2.322918463206361,-1.421075629595494);
\draw [line width=2.pt] (2.322918463206361,-1.421075629595494)-- (0.7180048123904461,-1.421075629595494);
\draw [line width=2.pt] (0.7180048123904461,-1.421075629595494)-- (0.7180048123904461,-0.5927331001421212);
\draw (1.2217901990322357,-0.6580098004023876) node[anchor=north west] {$d_{n-1}$};
\draw (1.2808113853875651,0.944312877220389) node[anchor=north west] {$d_1$};
\draw [line width=2.pt] (2.9840182861914197,2.252882635736503)-- (4.588931937007336,2.252882635736503);
\draw [line width=2.pt] (4.588931937007336,2.252882635736503)-- (4.588931937007336,1.4245401062831302);
\draw [line width=2.pt] (4.588931937007336,1.4245401062831302)-- (2.9840182861914197,1.4245401062831302);
\draw [line width=2.pt] (2.9840182861914197,1.4245401062831302)-- (2.9840182861914197,2.252882635736503);
\draw [line width=2.pt,color=qqzzff] (5.418945120976323,2.2142330034383306)-- (7.723858771792239,2.2142330034383306);
\draw [line width=2.pt,color=qqzzff] (7.723858771792239,2.2142330034383306)-- (7.723858771792239,1.3858904739849578);
\draw [line width=2.pt,color=qqzzff] (7.723858771792239,1.3858904739849578)-- (5.418945120976323,1.3858904739849578);
\draw [line width=2.pt,color=qqzzff] (5.418945120976323,1.3858904739849578)-- (5.418945120976323,2.2142330034383306);
\draw [line width=2.pt] (2.9646934700423326,1.0547440344931456)-- (4.569607120858249,1.0547440344931456);
\draw [line width=2.pt] (4.569607120858249,1.0547440344931456)-- (4.569607120858249,0.22640150503977274);
\draw [line width=2.pt] (4.569607120858249,0.22640150503977274)-- (2.9646934700423326,0.22640150503977274);
\draw [line width=2.pt] (2.9646934700423326,0.22640150503977274)-- (2.9646934700423326,1.0547440344931456);
\draw [line width=2.pt,color=qqzzff] (5.360970672529065,0.9967695860458878)-- (7.665884323344981,0.9967695860458878);
\draw [line width=2.pt,color=qqzzff] (7.665884323344981,0.9967695860458878)-- (7.665884323344981,0.168427056592515);
\draw [line width=2.pt,color=qqzzff] (7.665884323344981,0.168427056592515)-- (5.360970672529065,0.168427056592515);
\draw [line width=2.pt,color=qqzzff] (5.360970672529065,0.168427056592515)-- (5.360970672529065,0.9967695860458878);
\draw [line width=2.pt] (2.9840182861914197,-0.5685405220301103)-- (4.588931937007336,-0.5685405220301103);
\draw [line width=2.pt] (4.588931937007336,-0.5685405220301103)-- (4.588931937007336,-1.3968830514834831);
\draw [line width=2.pt] (4.588931937007336,-1.3968830514834831)-- (2.9840182861914197,-1.3968830514834831);
\draw [line width=2.pt] (2.9840182861914197,-1.3968830514834831)-- (2.9840182861914197,-0.5685405220301103);
\draw [line width=2.pt,color=qqzzff] (5.360970672529065,-0.5878653381791974)-- (7.665884323344981,-0.5878653381791974);
\draw [line width=2.pt,color=qqzzff] (7.665884323344981,-0.5878653381791974)-- (7.665884323344981,-1.4162078676325702);
\draw [line width=2.pt,color=qqzzff] (7.665884323344981,-1.4162078676325702)-- (5.360970672529065,-1.4162078676325702);
\draw [line width=2.pt,color=qqzzff] (5.360970672529065,-1.4162078676325702)-- (5.360970672529065,-0.5878653381791974);
\draw (3.2580211282911002,2.1517671905924417) node[anchor=north west] {$f_0(x)$};
\draw (3.198999941935771,-0.67684961662758515) node[anchor=north west] {$f_{n-1}(x)$};
\draw (3.2580211282911002,0.944312877220389) node[anchor=north west] {$f_1(x)$};
\draw (5.3,2.040156283291213) node[anchor=north west] {KZG Commit};
\draw (5.3,0.8611290150381405) node[anchor=north west] {KZG Commit};
\draw (5.3,-0.7305577971035068) node[anchor=north west] {KZG Commit};
\draw (1.398853758098224,0.4484694711495653) node[anchor=north west] {$\vdots$};
\draw (3.6416588396007414,0.4189937894432385) node[anchor=north west] {$\vdots$};
\draw (6.356633411945894,0.3895181077369117) node[anchor=north west] {$\vdots$};
\draw [line width=2.pt,color=ffzzqq] (8.745715532151925,2.252882635736503)-- (10.350629182967838,2.252882635736503);
\draw [line width=2.pt,color=ffzzqq] (10.350629182967838,2.252882635736503)-- (10.350629182967838,1.4245401062831302);
\draw [line width=2.pt,color=ffzzqq] (10.350629182967838,1.4245401062831302)-- (8.745715532151925,1.4245401062831302);
\draw [line width=2.pt,color=ffzzqq] (8.745715532151925,1.4245401062831302)-- (8.745715532151925,2.252882635736503);
\draw [line width=2.pt,color=ffzzqq] (8.758877888902111,1.0135856019266232)-- (10.363791539718024,1.0135856019266232);
\draw [line width=2.pt,color=ffzzqq] (10.363791539718024,1.0135856019266232)-- (10.363791539718024,0.18524307247325034);
\draw [line width=2.pt,color=ffzzqq] (10.363791539718024,0.18524307247325034)-- (8.758877888902111,0.18524307247325034);
\draw [line width=2.pt,color=ffzzqq] (8.758877888902111,0.18524307247325034)-- (8.758877888902111,1.0135856019266232);
\draw [line width=2.pt,color=ffzzqq] (8.718004812390424,-0.5927331001421212)-- (10.322918463206337,-0.5927331001421212);
\draw [line width=2.pt,color=ffzzqq] (10.322918463206337,-0.5927331001421212)-- (10.322918463206337,-1.421075629595494);
\draw [line width=2.pt,color=ffzzqq] (10.322918463206337,-1.421075629595494)-- (8.718004812390424,-1.421075629595494);
\draw [line width=2.pt,color=ffzzqq] (8.718004812390424,-1.421075629595494)-- (8.718004812390424,-0.5927331001421212);
\draw (9.366713916067694,0.3895181077369117) node[anchor=north west] {$\vdots$};
\draw (9.248671543357034,2.152815827179788) node[anchor=north west] {$H$};
\draw (6.356633411945894,0.3895181077369117) node[anchor=north west] {$\vdots$};
\draw (9.248671543357034,0.944312877220389) node[anchor=north west] {$H$};
\draw (9.248671543357034,-0.66527666174656557) node[anchor=north west] {$H$};
\draw [line width=2.pt] (12.742240963545123,2.352882635736501)-- (13.247154614361039,2.352882635736501);
\draw [line width=2.pt] (13.247154614361039,2.352882635736501)-- (13.247154614361039,-1.4754598937168613);
\draw [line width=2.pt] (13.247154614361039,-1.4754598937168613)-- (12.742240963545123,-1.4754598937168613);
\draw [line width=2.pt] (12.742240963545123,-1.4754598937168613)-- (12.742240963545123,2.352882635736501);
\draw (8.097758409428112,2.524426734481017) node[anchor=north west] {$A_0$};
\draw (8.127269002605775,1.3274967394026374) node[anchor=north west] {$A_1$};
\draw (8.127269002605775,-0.0716153809116045) node[anchor=north west] {$A_{n-1}$};
\draw (12.701410945143804,1.1037885589267157) node[anchor=north west] {\huge${||}$};
\draw (-1.6112267460235754,-0.35261711785799033) node[anchor=north west] {$\textrm{File}\,\, F$};
\draw [line width=2.pt,color=qqzzff] (14.099803567248562,0.8880549125817581)-- (16.404717218064505,0.8880549125817581);
\draw [line width=2.pt,color=qqzzff] (16.404717218064505,0.8880549125817581)-- (16.404717218064505,0.05971238312838523);
\draw [line width=2.pt,color=qqzzff] (16.404717218064505,0.05971238312838523)-- (14.099803567248562,0.05971238312838523);
\draw [line width=2.pt,color=qqzzff] (14.099803567248562,0.05971238312838523)-- (14.099803567248562,0.8880549125817581);
\draw (14.065472383560034,0.7137506065065066) node[anchor=north west] {KZG Commit};
\draw [line width=2.pt] (-1.757137164734643,1.4158566638357204)-- (-1.6987728137797875,1.468183323312486)-- (-0.8353829324131352,1.466170759486456)-- (-0.7911065282404861,1.4440325574001331)-- (-0.4731214437278277,1.1179972175833583)-- (-0.46104606077164956,1.0817710687148292)-- (-0.46411549876557334,-0.19677167547108)-- (-0.5092897728764969,-0.257004040952312)-- (-1.7049022276789376,-0.25399242267824995)-- (-1.7620790914452753,-0.18986681019888074);
\draw [line width=2.pt] (-0.8353829324131352,1.466170759486456)-- (-0.8375561647492082,1.143398456486299)-- (-0.7863586540901606,1.0801544727310066)-- (-0.46104606077164956,1.0817710687148292)-- (-0.4731214437278277,1.1179972175833583)-- (-0.7911065282404861,1.4440325574001331);
\draw [line width=2.pt] (-1.5730935591951942,1.1031592540250585)-- (-1.1382254455513623,1.1031592540250585);
\draw [line width=2.pt] (-1.5702512839426204,0.8582032161437834)-- (-1.294550584442935,0.8582032161437834);
\draw [line width=2.pt] (-1.5674090086900465,0.64503257220073)-- (-0.6493541021086218,0.6421902969481561);
\draw [line width=2.pt] (-1.1865441248451214,0.8525186656386357)-- (-0.6436695516034723,0.8525186656386357);
\draw [line width=2.pt] (-0.9250548016083053,0.42333510249995854)-- (-0.6436695516034723,0.42333510249995854);
\draw [line width=2.pt] (-1.578778109700342,0.4347042035102522)-- (-1.0302189859535469,0.43186192825767833);
\draw [line width=2.pt] (-1.5674090086900465,0.22153355956720056)-- (-0.6493541021086218,0.21584900906205284);
\draw [line width=2.pt] (-0.9278970768608792,0.00552064037157507)-- (-0.6408272763508984,0.00552064037157507);
\draw [line width=2.pt] (-1.757137164734643,1.4158566638357204)-- (-1.7620790914452753,-0.18986681019888074);
\draw [->,line width=1.2pt] (-0.4427398226884476,0.6443777038342358) -- (0.6650403483010345,1.900490753524851);
\draw [->,line width=1.2pt] (-0.4427398226884476,0.6443777038342358) -- (0.6650403483010345,0.6652261209508694);
\draw [->,line width=1.2pt] (-0.4427398226884476,0.6443777038342358) -- (0.7180048123904461,-1.0069043648688094);
\draw [->,line width=1.2pt] (2.269953999116951,1.8214542349795373) -- (2.9840182861914197,1.8219772023981164);
\draw [->,line width=1.2pt] (2.269953999116951,0.6824832569811488) -- (2.9646934700423326,0.6830273361324082);
\draw [->,line width=1.2pt] (2.322918463206361,-0.9914589379558745) -- (2.9840182861914197,-0.9816047853917738);
\draw [->,line width=1.2pt] (4.588931937007336,1.8425163050775915) -- (5.418945120976323,1.8425163050775915);
\draw [->,line width=1.2pt] (4.569607120858249,0.6250528876851487) -- (5.360970672529065,0.6241521358079796);
\draw [->,line width=1.2pt] (4.588931937007336,-0.998231668838109) -- (5.360970672529065,-0.998231668838109);
\draw [->,line width=1.2pt] (7.723858771792239,1.803866672779419) -- (8.745715532151925,1.8088148456479303);
\draw [->,line width=1.2pt] (7.665884323344981,0.578042621438291) -- (8.758877888902111,0.5715533111303248);
\draw [->,line width=1.2pt] (7.665884323344981,-0.9789068526890219) -- (8.718004812390424,-0.9789068526890219);
\draw [->,line width=1.2pt] (10.350629182967838,1.8351395591483044) -- (12.742240963545123,1.8351395591483026);
\draw [->,line width=1.2pt] (10.363791539718024,0.5847156678805128) -- (12.742240963545123,0.584715667880511);
\draw [->,line width=1.2pt] (10.322918463206337,-0.9595820365399366) -- (12.742240963545123,-0.9552800718914014);
\draw [line width=2.pt] (0.718791425238348,-3.5114097527777703)-- (2.323705076054254,-3.5114097527777703);
\draw [line width=2.pt] (2.323705076054254,-3.5114097527777703)-- (2.323705076054254,-4.339752282231143);
\draw [line width=2.pt] (2.323705076054254,-4.339752282231143)-- (0.718791425238348,-4.339752282231143);
\draw [line width=2.pt] (0.718791425238348,-4.339752282231143)-- (0.718791425238348,-3.5114097527777703);
\draw(-1.3516472915661355,-3.9312889331087435) circle (0.8257876327575664cm);
\draw [rotate around={39.98584609827348:(-1.6387362409560138,-4.172064335406262)},color=ccffcc,fill=ccffcc,fill opacity=0.55] (-1.6387362409560138,-4.172064335406262) ellipse (0.4209857891167758cm and 0.19192752649100409cm);
\draw [rotate around={-87.50012133744015:(-1.3205479483627034,-3.552947353841951)},color=ccffcc,fill=ccffcc,fill opacity=0.5] (-1.3205479483627034,-3.552947353841951) ellipse (0.4071361259806713cm and 0.17669855066785153cm);
\draw [rotate around={-43.20217596951604:(-1.0418350441774817,-4.166115743049433)},color=ccffcc,fill=ccffcc,fill opacity=0.5] (-1.0418350441774817,-4.166115743049433) ellipse (0.4133921347367967cm and 0.20248823488347825cm);
\draw(-1.383500194901587,-7.052873459983158) circle (0.8257876327575682cm);
\draw [rotate around={39.985846098273385:(-1.6705891442914862,-7.293648862280692)},color=ccffcc,fill=ccffcc,fill opacity=0.55] (-1.6705891442914862,-7.293648862280692) ellipse (0.42098578911676676cm and 0.19192752649100034cm);
\draw [rotate around={-87.50012133744228:(-1.3524008516981691,-6.674531880716382)},color=ccffcc,fill=ccffcc,fill opacity=0.5] (-1.3524008516981691,-6.674531880716382) ellipse (0.4071361259806343cm and 0.17669855066782242cm);
\draw [rotate around={-43.20217596951334:(-1.0736879475129417,-7.287700269923865)},color=ccffcc,fill=ccffcc,fill opacity=0.5] (-1.0736879475129417,-7.287700269923865) ellipse (0.4133921347368415cm and 0.20248823488351209cm);
\draw (-1.552205559668246,-4.886628917695585) node[anchor=north west] {$\vdots$};
\draw (15.670512635620934,0.03580992726099008) node[anchor=north west] {$T$};
\draw (-2.165353864155552,-2.37486620071352) node[anchor=north west] {$Farmers$};
\draw (-0.46031361209465216,-2.993855516546383) node[anchor=north west] {$sk$};
\draw (-0.4308030189169874,-3.435990742141285) node[anchor=north west] {$\large{pk}$};
\draw [->] (0.14468004123469402,-3.862757891982654) -- (0.718791425238348,-3.8713403810010814);
\draw (0.6676630809002593,-3.653893468966592) node[anchor=north west] {$\texttt{id} \,\,Gen$};
\draw [line width=2.pt] (4.067221140513448,-3.20994488658799)-- (6.3721347913293815,-3.20994488658799);
\draw [line width=2.pt] (6.3721347913293815,-3.20994488658799)-- (6.3721347913293815,-4.6382874160413605);
\draw [line width=2.pt] (6.3721347913293815,-4.6382874160413605)-- (4.067221140513448,-4.6382874160413605);
\draw [line width=2.pt] (4.067221140513448,-4.6382874160413605)-- (4.067221140513448,-3.20994488658799);
\draw (4.497466041753017,-3.318088015315978) node[anchor=north west] {$\mathrm{Choosing}$};
\draw (4.438444855397688,-3.830747559204553) node[anchor=north west] {$m \,\,\mathrm{from} \,\,n$};
\draw [->,line width=1.2pt] (2.323705076054254,-3.9255810175044568) -- (4.067221140513448,-3.924116151314675);
\draw [line width=1.2pt] (4.914588620718506,1.8425163050775915)-- (4.9200755693330835,0.6246539748059976);
\draw [line width=1.2pt] (4.9200755693330835,0.6246539748059976)-- (4.914588620719098,-0.998231668838109);
\draw [->,line width=1.2pt] (4.914588620719098,-0.998231668838109) -- (4.91458862071899,-3.20994488658799);
\draw [line width=1.2pt] (8.083935756984307,1.8056102862072694)-- (8.093109316976628,0.5755061055407052);
\draw [line width=1.2pt] (8.093109316976628,0.5755061055407052)-- (8.083742996686935,-0.9789068526890219);
\draw [line width=1.2pt] (8.083742996686935,-0.9789068526890219)-- (8.083742996687723,-2.00163077182214);
\draw [line width=1.2pt] (8.083742996687723,-2.00163077182214)-- (5.541640556071092,-2.00163077182214);
\draw [->,line width=1.2pt] (5.541640556071092,-2.00163077182214) -- (5.5416405560710915,-3.20994488658799);
\draw [line width=2.pt,color=dcrutc] (10.456149422292592,-2.1695557595211077)-- (11.161063073108538,-2.1695557595211077);
\draw [line width=2.pt,color=dcrutc] (11.161063073108538,-2.1695557595211077)-- (11.161063073108538,-3.997898288974477);
\draw [line width=2.pt,color=dcrutc] (11.161063073108538,-3.997898288974477)-- (10.456149422292592,-3.997898288974477);
\draw [line width=2.pt,color=dcrutc] (10.456149422292592,-3.997898288974477)-- (10.456149422292592,-2.1695557595211077);
\draw (10.635669422707275,-2.2390607470629058) node[anchor=north west] {$\rotatebox{270}{\footnotesize{KZG\, Proof}}$};
\draw [line width=2.pt,color=dcrutc] (11.219002673448236,-2.188051617467356)-- (11.923916324264182,-2.188051617467356);
\draw [line width=2.pt,color=dcrutc] (11.923916324264182,-2.188051617467356)-- (11.923916324264182,-4.016394146920725);
\draw [line width=2.pt,color=dcrutc] (11.923916324264182,-4.016394146920725)-- (11.219002673448236,-4.016394146920725);
\draw [line width=2.pt,color=dcrutc] (11.219002673448236,-4.016394146920725)-- (11.219002673448236,-2.188051617467356);
\draw [line width=2.pt,color=dcrutc] (12.557843292172995,-2.171104267863247)-- (13.262756942988942,-2.171104267863247);
\draw [line width=2.pt,color=dcrutc] (13.262756942988942,-2.171104267863247)-- (13.262756942988942,-3.999446797316616);
\draw [line width=2.pt,color=dcrutc] (13.262756942988942,-3.999446797316616)-- (12.557843292172995,-3.999446797316616);
\draw [line width=2.pt,color=dcrutc] (12.557843292172995,-3.999446797316616)-- (12.557843292172995,-2.171104267863247);
\draw (11.993156708879852,-2.292768927538827) node[anchor=north west] {$\cdots$};
\draw (11.432455438504222,-2.2390607470629058) node[anchor=north west] {$\rotatebox{270}{\footnotesize{KZG\, Proof}}$};
\draw (12.73092153832147,-2.2390607470629058) node[anchor=north west] {$\rotatebox{270}{\footnotesize{KZG\, Proof}}$};
\draw [shift={(10.731878967772666,-0.8955384492527699)},line width=1.2pt]  plot[domain=-1.590139330894294:1.5514533226954996,variable=\t]({1.*0.2248722100159012*cos(\t r)+0.*0.2248722100159012*sin(\t r)},{0.*0.2248722100159012*cos(\t r)+1.*0.2248722100159012*sin(\t r)});
\draw [shift={(10.739409756709932,0.6105059301922924)},line width=1.2pt]  plot[domain=-1.5625703161724944:1.5790223374172987,variable=\t]({1.*0.2005699950464014*cos(\t r)+0.*0.2005699950464014*sin(\t r)},{0.*0.2005699950464014*cos(\t r)+1.*0.2005699950464014*sin(\t r)});
\draw [shift={(11.424653656488621,-0.9508950963672769)},line width=1.2pt]  plot[domain=-1.6427801689606198:1.4988124846291733,variable=\t]({1.*0.20389622902873325*cos(\t r)+0.*0.20389622902873325*sin(\t r)},{0.*0.20389622902873325*cos(\t r)+1.*0.20389622902873325*sin(\t r)});
\draw [line width=1.2pt] (10.741059629012518,0.4099427211177)-- (10.73622840061631,-0.6707083060971553);
\draw [line width=1.2pt] (10.737759884407346,0.8110691392668848)-- (10.7284477331482,1.8351395591483042);
\draw [line width=1.2pt] (11.439318218301674,-0.7475269011179488)-- (11.432812621046226,0.584715667880512);
\draw [->,line width=1.2pt] (10.72752953492902,-1.1203685924083846) -- (10.737911132371794,-2.1695557595211077);
\draw [->,line width=1.2pt] (11.409989094675568,-1.154263291616605) -- (11.422370868697564,-2.188051617467356);
\draw [line width=1.2pt] (12.117212202466108,-1.7304731781563678)-- (12.117221975932841,-0.9563914613770921);
\draw [line width=1.2pt] (12.117212202466108,-1.7304731781563678)-- (12.845948235442878,-1.7304731781563678);
\draw [->,line width=1.2pt] (12.845948235442878,-1.7304731781563678) -- (12.857334321625657,-2.171104267863247);
\draw [line width=2.pt] (10.407049543911524,-4.545281720780878)-- (13.31196319472746,-4.545281720780878);
\draw [line width=2.pt] (13.31196319472746,-4.545281720780878)-- (13.31196319472746,-4.773624250234253);
\draw [line width=2.pt] (13.31196319472746,-4.773624250234253)-- (10.407049543911524,-4.773624250234253);
\draw [line width=2.pt] (10.407049543911524,-4.773624250234253)-- (10.407049543911524,-4.545281720780878);
\draw [->] (10.78614413545985,-3.997898288974477) -- (10.789850228133698,-4.545281720780878);
\draw [->] (12.89679028425521,-3.999446797316616) -- (12.894042938370596,-4.545281720780878);
\draw [->] (11.54100231592634,-4.016394146920725) -- (11.544105500091865,-4.545281720780878);
\draw [line width=1.2pt] (11.734066087103551,-5.485858517750604)-- (11.728942813032173,-4.773624250234253);
\draw (13.586728740473745,-4.29711528356905) node[anchor=north west] {Concat};
\draw (2.992425789692118,-3.193855516546383) node[anchor=north west] {$\texttt{id}$};
\draw [line width=1.2pt] (11.734066087103551,-5.485858517750604)-- (9.897109404327585,-5.492784790268936);
\draw [line width=1.2pt] (9.40563626580837,-6.0012052783922565)-- (15.472348846776628,-5.982714621646019);
\draw [line width=1.2pt] (9.40563626580837,-6.0012052783922565)-- (9.40563626580837,-3.967523325898978);
\draw [->,line width=1.2pt] (9.40563626580837,-3.967523325898978) -- (6.3721347913293815,-3.984470675503087);
\draw (11.899730861123504,-4.950823464044971) node[anchor=north west] {$(\pi_0,\pi_1,\ldots,\pi_{n-1})$};
\draw [->,line width=1.2pt] (6.117850442610861,-2.543945959153679) -- (6.1042318152870365,-3.20994488658799);
\draw [line width=1.2pt] (6.117850442610861,-2.543945959153679)-- (9.897109404327585,-2.543945959153679);
\draw [line width=1.2pt] (9.897109404327585,-2.543945959153679)-- (9.897109404327585,-5.492784790268936);
\draw [line width=1.2pt] (4.840093381637474,-4.6382874160413605)-- (4.840093381637475,-5.443378839719823);
\draw [rotate around={0.3951370425074505:(6.398167685017601,-6.269999299157492)},line width=1.2pt] (6.398167685017601,-6.269999299157492) ellipse (1.2418422928372648cm and 0.18010813509358264cm);
\draw [line width=1.2pt] (5.156388895571184,-6.277038762322351)-- (5.14553759410949,-6.775559943446546);
\draw [line width=1.2pt] (5.138059938569738,-7.239174586911266)-- (5.14553759410949,-6.775559943446546);
\draw [line width=1.2pt] (7.636285359219043,-6.247754858205767)-- (7.6355968888474575,-6.775559943446546);
\draw [line width=1.2pt] (7.6355968888474575,-7.239174586911266)-- (7.6355968888474575,-6.775559943446546);
\draw [rotate around={0.39513704250753223:(6.39055361115457,-6.796673658889347)},line width=1.2pt] (6.39055361115457,-6.796673658889347) ellipse (1.2418422928371189cm and 0.18010813509355666cm);
\draw [rotate around={0.4270686677848574:(6.389374180674065,-7.25634592812916)},line width=1.2pt] (6.389374180674065,-7.25634592812916) ellipse (1.247467142335559cm and 0.1761794829972632cm);
\draw (6.563207564189547,-7.627867316383978) node[anchor=north west] {Storage};
\draw [->,line width=1.2pt] (5.480821080884512,-4.6382874160413605) -- (5.497313687419389,-6.152111622452225);
\draw [->,line width=1.2pt] (6.1042318152870365,-4.6382874160413605) -- (6.121877887913505,-6.096266814503579);
\draw [line width=1.2pt] (4.840093381637475,-5.443378839719823)-- (0.9091423619326653,-5.429963663942398);
\draw (1.8431927397834946,-5.6813857347588534) node[anchor=north west] {$\{\mathrm{Commit}(g_i^{\texttt{id}}(x)\}_{i=0}^{m-1}$};
\draw (6.1336969710118815,-4.945580281108239) node[anchor=north west] {$\{\pi_i^{\texttt{id}}(x)\}_{i=0}^{m-1}$};
\draw (0.48402536959061826,-4.6739693738070105) node[anchor=north west] {$F^{\texttt{id}}(x)=\{g_i^{\texttt{id}}(x)\}_{i=0}^{m-1}$};
\draw [line width=2.pt] (0.008660190017908853,-6.43434762492424)-- (2.905765821324768,-6.43434762492424);
\draw [line width=2.pt] (2.905765821324768,-6.43434762492424)-- (2.905765821324768,-8.262690154377612);
\draw [line width=2.pt] (2.905765821324768,-8.262690154377612)-- (0.008660190017908853,-8.262690154377612);
\draw [line width=2.pt] (0.008660190017908853,-8.262690154377612)-- (0.008660190017908853,-6.43434762492424);
\draw [line width=2.pt] (0.12987894392951116,-11.161879027476715)-- (2.9369845752363686,-11.161879027476715);
\draw [line width=2.pt] (2.9369845752363686,-11.161879027476715)-- (2.9369845752363686,-12.990221556930091);
\draw [line width=2.pt] (2.9369845752363686,-12.990221556930091)-- (0.12987894392951116,-12.990221556930091);
\draw [line width=2.pt] (0.12987894392951116,-12.990221556930091)-- (0.12987894392951116,-11.161879027476715);
\draw [line width=2.pt,color=qqqqcc] (0.147195908774024,-9.32628075395817)-- (1.752109559589928,-9.32628075395817);
\draw [line width=2.pt,color=qqqqcc] (1.752109559589928,-9.32628075395817)-- (1.752109559589928,-10.154623283411542);
\draw [line width=2.pt,color=qqqqcc] (1.752109559589928,-10.154623283411542)-- (0.147195908774024,-10.154623283411542);
\draw [line width=2.pt,color=qqqqcc] (0.147195908774024,-10.154623283411542)-- (0.147195908774024,-9.32628075395817);
\draw (0.2725571491236124,-9.484835263882566) node[anchor=north west] {MASK};
\draw (0.17087706510331247,-6.524607549361311) node[anchor=north west] {$F^{\texttt{id}}(\texttt{id}+0)$};
\draw (0.17087706510331247,-7.633110499320711) node[anchor=north west] {$F^{\texttt{id}}(\texttt{id}+l-1)$};
\draw (0.7791313013672653,-6.873072546900501) node[anchor=north west] {$\vdots$};
\draw [->,line width=1.2pt] (0.9091423619326653,-5.429963663942398) -- (0.9122130056713385,-6.43434762492424);
\draw [->,line width=1.2pt] (0.9122130056713385,-8.262690154377612) -- (0.9091423619326648,-9.32628075395817);
\draw [->,line width=1.2pt] (0.9423802043201331,-10.155936367059587) -- (0.9437762916216945,-11.161879027476715);
\draw (0.27087706510331247,-11.22914366749258) node[anchor=north west] {$\tilde{F}^{\texttt{id}}(\texttt{id}+0)$};
\draw (0.27087706510331247,-12.278695254039326) node[anchor=north west] {$\tilde{F}^{\texttt{id}}(\texttt{id}+l-1)$};
\draw (0.8381524877225947,-11.607084346738096) node[anchor=north west] {$\vdots$};
\draw [line width=1.2pt] (2.9369845752363686,-12.062050292203403)-- (6.329352358265721,-12.062361199391471);
\draw [->,line width=1.2pt] (6.329352358265721,-12.062361199391471) -- (6.335428311825565,-7.432759469007388);
\draw (2.9071079943621767,-7.215207772495403) node[anchor=north west] {Storage Coins};
\draw (3.06552907824094,-11.059705938206463) node[anchor=north west] {Masked Storage};
\draw (3.56552907824094,-11.559705938206463) node[anchor=north west] {Coins};
\draw [dash pattern=on 7pt off 7pt] (-2.3184831408875706,-2.243010366626785)-- (9.117383698232567,-2.209008202862692);
\draw [dash pattern=on 7pt off 7pt] (9.117383698232567,-2.209008202862692)-- (9.100066733388052,-13.222597843973947);
\draw [dash pattern=on 7pt off 7pt] (9.100066733388052,-13.222597843973947)-- (-2.329130063991557,-13.222597843973947);
\draw [dash pattern=on 7pt off 7pt] (-2.329130063991557,-13.222597843973947)-- (-2.3184831408875706,-2.243010366626785);
\draw (-2.171928016399205,-9.1900784468193) node[anchor=north west] {$\mathbf{\rotatebox{270}{\huge{Plotting}}}$};
\draw [->] (13.247154614361039,0.51860659936446) -- (14.099803567248562,0.5236738738497664);
\draw [line width=1.2pt] (15.45109180068545,0.05971238312838523)-- (15.472348846776628,-5.982714621646019);
\draw [line width=2.pt,color=wwccqq] (-0.5024902877693558,-14.732608826535447)-- (-1.0960736538904081,-15.103598430361114);
\draw [line width=2.pt,color=wwccqq] (-1.0960736538904081,-15.103598430361114)-- (-1.0715789154979827,-15.803151506598658);
\draw [line width=2.pt,color=wwccqq] (-1.0715789154979827,-15.803151506598658)-- (-0.45350081098450445,-16.131714979010535);
\draw [line width=2.pt,color=wwccqq] (-0.45350081098450445,-16.131714979010535)-- (0.14008255513654805,-15.760725375184869);
\draw [line width=2.pt,color=wwccqq] (0.14008255513654805,-15.760725375184869)-- (0.11558781674412272,-15.061172298947325);
\draw [line width=2.pt,color=wwccqq] (0.11558781674412272,-15.061172298947325)-- (-0.5024902877693558,-14.732608826535447);
\draw [line width=2.pt] (-0.46225350351725947,-15.417811581828872)-- (-0.45350081098450445,-16.131714979010535);
\draw [line width=2.pt] (0.11558781674412272,-15.061172298947325)-- (-0.46225350351725947,-15.417811581828872);
\draw [line width=2.pt] (-1.0960736538904081,-15.103598430361114)-- (-0.46225350351725947,-15.417811581828872);
\draw [line width=2.pt,color=wwccqq] (2.7587997933661246,-14.739901776026734)-- (2.165216427245082,-15.1108913798524);
\draw [line width=2.pt,color=wwccqq] (2.165216427245082,-15.1108913798524)-- (2.1897111656375126,-15.810444456089936);
\draw [line width=2.pt,color=wwccqq] (2.1897111656375126,-15.810444456089936)-- (2.8077892701509857,-16.139007928501805);
\draw [line width=2.pt,color=wwccqq] (2.8077892701509857,-16.139007928501805)-- (3.401372636272028,-15.768018324676138);
\draw [line width=2.pt,color=wwccqq] (3.401372636272028,-15.768018324676138)-- (3.3768778978795977,-15.068465248438603);
\draw [line width=2.pt,color=wwccqq] (3.3768778978795977,-15.068465248438603)-- (2.7587997933661246,-14.739901776026734);
\draw [line width=2.pt] (2.7990365776182227,-15.425104531320162)-- (2.8077892701509857,-16.139007928501805);
\draw [line width=2.pt] (3.3768778978795977,-15.068465248438603)-- (2.7990365776182227,-15.425104531320162);
\draw [line width=2.pt] (2.165216427245082,-15.1108913798524)-- (2.7990365776182227,-15.425104531320162);
\draw [line width=2.pt,color=wwccqq] (6.8818880632113295,-14.610078361458243)-- (6.288304697090288,-14.98106796528391);
\draw [line width=2.pt,color=wwccqq] (6.288304697090288,-14.98106796528391)-- (6.312799435482719,-15.680621041521444);
\draw [line width=2.pt,color=wwccqq] (6.312799435482719,-15.680621041521444)-- (6.930877539996192,-16.009184513933313);
\draw [line width=2.pt,color=wwccqq] (6.930877539996192,-16.009184513933313)-- (7.524460906117234,-15.638194910107647);
\draw [line width=2.pt,color=wwccqq] (7.524460906117234,-15.638194910107647)-- (7.4999661677248035,-14.938641833870111);
\draw [line width=2.pt,color=wwccqq] (7.4999661677248035,-14.938641833870111)-- (6.8818880632113295,-14.610078361458243);
\draw [line width=2.pt] (6.922124847463428,-15.295281116751667)-- (6.930877539996192,-16.009184513933313);
\draw [line width=2.pt] (7.4999661677248035,-14.938641833870111)-- (6.922124847463428,-15.295281116751667);
\draw [line width=2.pt] (6.288304697090288,-14.98106796528391)-- (6.922124847463428,-15.295281116751667);
\draw [rotate around={-1.7357045889282945:(0.7967117976492252,-15.424084707107058)},line width=2.pt] (0.7967117976492252,-15.424084707107058) ellipse (0.37660499237995737cm and 0.1559970026432568cm);
\draw [rotate around={-1.735704588928295:(1.6141893574682438,-15.414288415682424)},line width=2.pt] (1.6141893574682438,-15.414288415682424) ellipse (0.3766049923799657cm and 0.15599700264325742cm);
\draw [line width=2.pt] (0.9043602792450214,-15.426161191923018)-- (1.4792178444310435,-15.413702283027277);
\draw [rotate around={-1.7357045889285956:(3.954940161897829,-15.488537737509448)},line width=2.pt] (3.954940161897829,-15.488537737509448) ellipse (0.376604992380349cm and 0.15599700264341798cm);
\draw [rotate around={-1.735704588928596:(4.772417721716719,-15.47874144608481)},line width=2.pt] (4.772417721716719,-15.47874144608481) ellipse (0.3766049923799701cm and 0.15599700264325805cm);
\draw [line width=2.pt] (4.062588643493532,-15.490614222325402)-- (4.637446208679551,-15.47815531342966);
\draw [line width=2.pt] (10.512485726572443,-14.431068034658)-- (15.3195913578793,-14.431068034658);
\draw [line width=2.pt] (15.3195913578793,-14.431068034658)-- (15.3195913578793,-16.259410564111377);
\draw [line width=2.pt] (15.3195913578793,-16.259410564111377)-- (10.512485726572443,-16.259410564111377);
\draw [line width=2.pt] (10.512485726572443,-16.259410564111377)-- (10.512485726572443,-14.431068034658);
\draw [->,line width=1.2pt] (10.512485726572443,-15.375765630046162) -- (7.515276804786475,-15.375903219725872);
\draw [->,line width=1.2pt] (12.16849885849944,-18.129954592421402) -- (12.16274693346384,-16.259410564111377);
\draw [line width=2.pt] (0.9676011334750672,-12.949511714742727)-- (0.9599720716506476,-13.585706836181355);
\draw [line width=1.2pt] (12.087593087927958,-13.633187038880157)-- (0.9599720716506476,-13.585706836181355);
\draw [->,line width=1.2pt] (12.087593087927958,-13.633187038880157) -- (12.093549454253832,-14.431068034658);
\draw (-2.348991575465193,-14.670382066180974) node[anchor=north west] {$\mathbf{\rotatebox{270}{\huge{Farming}}}$};
\draw [dash pattern=on 7pt off 7pt] (-2.3949156311918123,-19.967829269453112)-- (-2.3842687080878284,-13.988241792105951);
\draw [dash pattern=on 7pt off 7pt] (15.530539693513044,-19.88337610457736)-- (15.540623562569204,-14.004480444837371);
\draw [dash pattern=on 7pt off 7pt] (-2.3842687080878284,-13.988241792105951)-- (15.540623562569204,-14.004480444837371);
\draw [dash pattern=on 7pt off 7pt] (-2.3949156311918123,-19.967829269453112)-- (15.530539693513044,-19.88337610457736);
\draw (0.8415126557631945,-16.224280008757942) node[anchor=north west] {Blockchain};
\draw (5.5303368029712825,-16.50004750998835) node[anchor=north west] {Winner allowed to };
\draw (10.488116456818952,-19.123383181851434) node[anchor=north west] {Global Challenge };
\draw (11.845603742991528,-18.33278295871734) node[anchor=north west] {$C_t$};
\draw (11.16686009990524,-14.790457971021391) node[anchor=north west] { \large    Check the };
\draw (5.235230871194635,-17.03060978070223) node[anchor=north west] {produce a new block at time slot $t$};
\draw (10.98979654083925,-15.37997160514793) node[anchor=north west] {\large winning conditions};
\draw (5.289357989326611,-15.267312061259353) node[anchor=north west] {$\cdots$};
\end{tikzpicture}
\end{addmargin}
\end{figure*}



\end{document}

\section{Economic Security Analysis}

%\subsection{System model}

{\bf Outline:} We can use a hardware architecture model to reason about economic security. In particular, we will focus on the memory IO and Hash computation (modelled as an oracle access). We will model the energy cost as a linear combination of the memory IO and oracle access and then derive a lower bounder for the energy cost. We will then include the setup cost. Similar models have already been used in Ling Ren's PhD thesis and other works.



{\bf Intuition:} First of all, we consider three very simple cases.
\begin{itemize}
    \item If an attacker generates the Chia PoS tables on the fly, then the memory IO is lower bounded by the size of the tables.
    \item If an attacker stores the Chia PoS tables on memory, then the memory storage cost is higher than the disk storage cost.
    \item If an attacker stores the Chia PoS tables on disk, then we can make the size of tables larger than the masked storage coins.
\end{itemize}

Next, for Hellman's attacks, we can lower bound their memory IO and computational costs.
Here, we need to consider more general attacks because the attacking goal here is to minimize the total cost.

{\bf Proof Sketch:} Our proof is based on the following ingredients. 

\begin{itemize}
    \item Space-time tradeoff lower bound (from the ``Beyond Hellman'' paper): 
    any adversary who gets $S$ bits of auxiliary information, makes at most $T$
    oracle queries, and inverts $h(\cdot)$ (defined in Example~2 above) on an
    $\epsilon$ fraction of outputs must satisfy $S^2 \cdot T \in \Omega(\epsilon^2 N^2)$ (where $N$
    is the domain size and $N = 2^k$ in our notation).
    \item Energy cost in the parallel random oracle model (from the ``Bandwidth-Hard Functions'' paper): a formal definition of energy costs is given based on a simple memory-cache model.
\end{itemize}

Roughly, $S$ bits of auxiliary information can be computed in cache and then transferred to memory (which incurs memory IO with a unit cost $c_b$), and $T$ oracle queries can be charged with a unit cost $c_r$.
This allows us to evaluate the energy cost for any adversary. Note that this cost depends on $k$, which can be adjusted so that the cost is higher than the energy cost of honest farmers.

\section{Consensus Security Analysis}

Our key inspirations are the following.

\begin{itemize}
    \item When considering longest-chain protocols, Proof-of-Stake (PoS) is less secure than PoW as it presents many additional vulnerabilities (such as long-range attacks). 
    \item The best we can show is that Proof-of-Archival-Storage (PoAS) stands in the middle.
\end{itemize}

\subsection{System model}

%On Explicit Constructions of Extremely Depth Robust Graphs
%ZigZag horizontal DRG + vertical DRG
%Temporary Block Withholding Attacks on Filecoin's Expected Consensus

The protocol proceeds in slots of duration $\tau$ (where $\tau$ is one second in our PoAS setup). For simplicity, we consider a fixed set of $N$ nodes with equal capability. We
are interested in the large system regime $N \to \infty$. In each slot, each node can win the lottery with probability $\rho / N$,
independently of other nodes and slots. When a malicious node wins the lottery at slot $t$, it can create multiple blocks, which is a behavior called equivocations. (Note that equivocations never happen in PoW but can appear in PoS and PoAS.)




\subsection{Proof outline}


Following the paper ``Security of Blockchains at Capacity'' (which is available online),  we can define \emph{good} slots, \emph{bad} slots, and \emph{empty} slots based on which we can reason about the consensus security in a rigorous way. Roughly speaking, for any given fraction $\beta$ of malicious nodes, we can find protocol parameters $\tau$  and $\rho$ such that the system is secure. 
Note that the security proof assumes that certain download rules are used by the underlying P2P network. This assumption is reasonable because the download rules are relatively easy to implement.

Next, we need to understand how to emulate storage coins so that a malicious node can win the lottery with probability $\rho / N$.
Essentially, it is a function inverting problem. One can compute the function table at the very beginning and then store the entire table in SSD (in the form of transformed pre-images). Alternatively, one can compute the function table and then only store part of the table in SSD (in any form).
I feel that we just need to focus on the block production opportunity (BPO). In particular, each BPO implies some space-time tradeoff. This completes the proof.

\subsection{Intuitions}
Here, we will explain why the above proof outline works. The BPO is defined as a pair $(p, t)$ where node $p$ wins the lottery associated with slot $t$ and so is eligible to produce a block. To track the system evolution, we can introduce two random variables $H_t$ and $A_t$ denoting the number of honest and adversarial BPOs in slot $t$, respectively. For simplicity, we assume that blocks in one chain must come from increasing slots. This can be achieved by imposing a constraint on the longest chain protocol. In addition, we assume that honest nodes download at most one block per BPO. This can be achieved by using some specific download rule (called equivocation removal policy) proposed in the paper ``Security of Blockchains at Capacity''.

Following the footsteps of the paper, we can define empty slots and non-empty slots. For a non-empty slot, we can classify it into a good slot or a bad slot. In other words, the proof steps of ``Security of Blockchains at Capacity''  are compatible with our construction. 

Finally, we have the following observations.
\begin{itemize}
    \item The parameter $\rho$ doesn't depend on the adversarial action (assuming that the common randomness is not affected by adversarial action). This is because a transformed pre-image is a ticket and only the number of pre-images matters. 
    \item The proof in ``Security of Blockchains at Capacity'' is based on a counting argument that captures a large range of attacks.
\end{itemize}

Therefore, we only need to understand the ``cost'' of emulating a node that wins the lottery with probability $\rho / N$. 

\textbf{OLD version}

Ideally, we want to show that an adversary with a percentage of \emph{storage} lower than $\beta$ cannot break the consensus (assuming that $\tau$ and $\rho$ are chosen in the right way). If we only consider adversaries with storage, then it should follow from the previous analysis. Since adversaries can use a wide range of attacks/resources, we would like to model the adversary capabilities by \emph{disruption tokens}. We then proceed as follows.

{\bf Proof Sketch:} We first show that any deviation from the (farming) protocol results in ``work'', i.e. running the MASK function. The protocol is design this way so it should be fairy straightforward. Ideally we would like to show that the adversary would need to have a complete execution of MASK, but since they can store some parts of the PoS table (in the concrete choice of MASK), this is not possible. Yet, ideally we could show that this is the best the adversary can do. If we succeed, it would give us a lower bound on how much work the adversary should do in order to construct a plot on demand (how many tokens it has to spend). (of course, an adversary can stop creating a table in the middle, but this would result in not having a full plot, and thus affect the probability of success, so it should be easy to handle).

Secondly, our aim is to show that the cost of making plots on demand is higher than storing it. Cost here should be modeled by disruption tokens. As an abstract analysis what we want to show (though it will probably be an assumption in the proof) is that \emph{for some system parameters} ``storage requires less disruption tokens than MASK''.  Finally we would like to show that it holds asymptotically. The conclusion is that an adversary with a fixed budget of disruption tokens can do ``the most harm'' if they spend it all on storage, then we fall into the analysis above.

In the actual implementation of the protocol, one would need to associate cost for storage, cost for MASK, and to argue that in those specific parameters the inequality holds.