preliminaries.tex

\section{Preliminaries}\label{sec:preliminaries}

In our setting the chain network consists of two
node types: The first, \emph{full nodes}, are responsible for the
verifying the chain and mining new blocks. The
second, \emph{verifiers}, connect to full nodes and wish to learn facts
about the blockchain without downloading it, such as whether a particular
transaction is confirmed. Full nodes therefore also function as
\emph{provers} for the verifiers. A verifier connects to multiple provers, at
least one of which is assumed honest.

We model full nodes according to the Backbone model~\cite{backbone}. There are
$n$ full nodes, of which $t$ are adversarial and $n - t$ honest. All
adversarial parties are controlled by one colluding adversary $\mathcal{A}$. The
parties have access to a hash function $H$ modelled as a Random
Oracle~\cite{ro}. To each novel query, the random oracle outputs $\kappa$ bits
of fresh randomness. Time is split into distinct \emph{rounds} numbered
$1, 2, \cdots$. Our treatment is in the \emph{synchronous model}, so we
assume messages \emph{diffused} (``unreliable'' broadcast) 
by an honest party at the end of a
round are received by all honest parties at the beginning of the next.
This is equivalent to a network connectivity assumption in which the round
duration is taken to be the known time needed for a message to cross the
diameter of the network. The adversary can inject messages, reorder them, sybil
attack~\cite{sybil} by creating multiple messages, but not suppress messages.

Each honest full node locally maintains a \emph{chain} $\chain$, a sequence of
blocks. As we are developing an improvement on top of SPV, we
use the term \emph{block} to mean a
\emph{block header}. Each block contains the Merkle Tree root~\cite{merkle} of
transaction data\footnote{The compression of
$\overline{x}$ is beyond the scope of our work. Vendors verifying a small number
of transactions benefit exponentially from a superlight client even without
compressing $\overline{x}$.}
$\overline{x}$, the hash $s$ of the previous block in the chain
known as the \emph{previd}, and a nonce $ctr$. Each block $b = s \conc
\overline{x} \conc ctr$ must satisfy the proof-of-work~\cite{pow} equation $H(b) \leq T$
where $T$ is a constant \emph{target}, a small value signifying the difficulty
of proof-of-work. We assume $T$ is constant throughout the execution\footnote{A
treatment of variable difficulty NIPoPoWs has been explored in the soft fork
case~\cite{dionyziz}, but we leave the treatment of velvet fork NIPoPoWs in the
variable difficulty model for future work.}. $H(b)$ is
known as the \emph{block id}.

Blockchains are finite block sequences obeying the \emph{blockchain property}:
that in every block in the chain there exists a pointer to its previous block. A
chain is \emph{anchored} if its first block is \emph{genesis}, denoted $\mathcal{G}$,
a special block known to all parties. This is the only node the verifier knows about
when it boots up. For chain addressing we use Python brackets $\chain[\cdot]$. A
zero-based positive index indicates the indexed block.
A negative index indicates a block from the end, e.g., $\chain[-1]$ is
the chain \emph{tip}. A range $\chain[i{:}j]$ is a subarray starting from
$i$ (inclusive) to $j$ (exclusive). Given chains $\chain_1, \chain_2$ and blocks
$A, Z$ we concatenate them as $\chain_1 \chain_2$ or $\chain_1 A$ (if clarity
mandates it, we use $\conc$ to signify concatenation). Here,
$\chain_2[0]$ must point to $\chain_1[-1]$ and $A$ must point to $\chain_1[-1]$.
We denote $\chain\{A{:}Z\}$ the subarray of the chain from block $A$ (inclusive) to
block $Z$ (exclusive). We can omit blocks or indices from either side of the range to
take the chain to the beginning or end respectively. As long as the blockchain
property is maintained, we freely use the set operators $\cup$, $\cap$ and
$\subseteq$ to denote operations between chains, implying that the appropriate
blocks are selected and then placed in chronological order.

At every round, every honest party attempts to \emph{mine} a block on top of
its chain. Each party is given $q$ queries to the random
oracle which it uses in attempting to mine. The adversary
has $tq$ queries per round while the honest parties have $(n - t)q$ queries per
round. When an honest party discovers a new block, they extend their chain
and broadcast it. Upon receiving a new chain $\chain'$ from the
network, an honest party compares its length $|\chain'|$ against its currently
adopted chain length $|\chain|$ and adopts the new chain if it is longer. The
honest parties control the majority of the computational
power. This \emph{honest majority assumption} states that there
is some $0 < \delta < 1$ such that $t < (1 -  \delta)(n - t)$. The protocol
ensures consensus among honest parties: There is a constant $k$, the
\emph{Common Prefix} parameter, such that, at any round, chains
belonging to honest parties share a common prefix; the chains
differ only up to $k$ blocks at the end~\cite{backbone}.
Concretely, if at some round two honest parties have $\chain_1$ and
$\chain_2$ respectively, then $\chain_1[{:}{-k}]$ is a prefix of $\chain_2$
or vice versa.

Some valid blocks satisfy the proof-of-work equation better than required. If
a block $b$ satisfies $H(b) \leq 2^{-\mu} T$ for some
$\mu \in \mathbb{N}$ we say that $b$ is a \emph{$\mu$-superblock} or a block
\emph{of level} $\mu$. The probability of a new valid block achieving level
$\mu$ is $2^{-\mu}$. The number of levels in the chain will be $\log|\chain|$
with high probability~\cite{popow}. Given chain $\chain$, we denote
$\chain\upchain^\mu$ the subset of $\mu$-superblocks of $\chain$.

\emph{Non-Interactive Proofs of Proof-of-Work} (NIPoPoW) protocols allow verifiers to
learn the most recent $k$ blocks of the blockchain adopted by an honest full
node without downloading the whole chain. The challenge lies in building a
verifier who can find the suffix of the longest chain between claims of both
honest and adversarial provers, while not downloading all block headers. Towards
that goal, the \emph{superblock} approach uses superblocks as proof-of-work samples.
The prover sends superblocks to the verifier to convince them
that proof-of-work has taken place without actually presenting all this
work. The protocol is parametrized by a constant security parameter
$m$. The parameter determines how many superblocks will be sent by the prover to
the verifier and security is proven with overwhelming probability in $m$.

The prover selects various levels $\mu$ and for each such level sends a
carefully chosen portion of its $\mu$-level \emph{superchain}
$\chain\upchain^\mu$ to the verifier. In standard chain protocols,
each block $\chain[i + 1]$ in $\chain$ points to its
previous block $\chain[i]$, but each $\mu$-superblock $\chain\upchain^\mu[i +
1]$ does not point to its previous $\mu$-superblock $\chain\upchain^\mu[i]$. It
is imperative that an adversarial prover does not reorder the blocks within a
superchain, but the verifier cannot verify this unless each $\mu$-superblock
points to its most recently preceding $\mu$-superblock. The proposal is
therefore to \emph{interlink} the chain by having each $\mu$-superblock include
an extra pointer to its most recently preceding $\mu$-superblock. To ensure
integrity, this pointer must be included in the block header and verified by
proof-of-work. However, the miner does not know which level a candidate block
will attain prior to mining it. Therefore, each block is proposed to
include a pointer to the most recently preceding $\mu$-superblock, for every
$\mu$, as illustrated in Figure~\ref{fig.hierarchy}. As these levels are
$\log|\chain|$, this only adds $\log|\chain|$ extra pointers to each block
header.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.9\columnwidth,keepaspectratio]{figures/level-shadows.pdf}
    \caption{The interlinked blockchain. Each superblock is drawn taller
    according to its achieved level. Each block links to all the blocks that are
    not being overshadowed by their descendants. The most recent (right-most)
    block links to the four blocks it has direct line-of-sight to.}
    \label{fig.hierarchy}
\end{figure}

The exact NIPoPoW protocol works like this: The prover holds a full chain
$\chain$. When the verifier requests a proof, the prover sends the last $k$
blocks of their chain, the suffix $\chi = \chain[-k{:}]$, in full. From the
larger prefix $\chain[{:}{-k}]$, the prover constructs a proof $\pi$ by sampling
superblocks as representatives of the underlying proof-of-work.
The blocks are picked as follows. The prover selects the \emph{highest}
level $\mu^*$ with at least $m$ blocks and includes all these blocks
in their proof (if no such level exists, the chain is small and can be sent in
full). The prover then iterates from level $\mu = \mu^* - 1$ down to $0$. For
every level $\mu+1$, it pinpoints the $m^\text{th}$ most recent $(\mu+1)$-superblock.
It includes all $\mu$-superblocks after it, as
illustrated in
Algorithm~\ref{alg.nipopow-prover}. Because the density of blocks roughly doubles as
levels are descended, the proof contains in expectation $2m$ blocks for each
level below $\mu^*$. As such, the total proof size $\pi \chi$, called a \emph{suffix proof},
will be
$\Theta(m\log|\chain| + k)$. Such proofs polylogarithmic in the chain
size constitute an exponential improvement over SPV clients and are
called \emph{succinct}.

\import{./}{algorithms/alg.nipopow-prover.tex}

\vspace{-2em}

\import{./}{algorithms/alg.nipopow-maxchain.tex}

Upon receiving two proofs $\pi_1\chi_1, \pi_2\chi_2$ of this form, the NIPoPoW verifier
first checks that $\lvert \chi_1 \rvert = \lvert \chi_2 \rvert = k$ and that
$\pi_1 \chi_1$ and $\pi_2 \chi_2$ form valid chains. To check that they are
valid chains, the verifier ensures every block in the
proof contains a pointer to its previous block inside the proof through either
the \emph{previd} pointer in the block header, or in the interlink vector. If
any of these checks fail, the proof is rejected. It then
compares $\pi_1$ against $\pi_2$ using
the $\leq_m$ operator, which works as follows. It finds the
lowest common ancestor (LCA) block $b = (\pi_1 \cap \pi_2)[-1]$; that is, $b$ is the
most recent block shared among the two proofs. Subsequently, it
chooses the level $\mu_1$ for $\pi_1$ such that
$\lvert \pi_1\{b{:}\}\upchain^{\mu_1} \rvert \geq m$
(i.e., $\pi_1$ has at least $m$ superblocks of level $\mu_1$ following block
$b$) and the value
$2^{\mu_1} \lvert \pi_1\{b{:}\}\upchain^{\mu_1} \rvert$
is maximized.
It chooses a level $\mu_2$ for $\pi_2$ in the same fashion. The two proofs are
compared
by checking whether
$2^{\mu_1} \lvert \pi_1\{b{:}\}\upchain^{\mu_1} \rvert \geq
 2^{\mu_2} \lvert \pi_2\{b{:}\}\upchain^{\mu_2} \rvert$
and the proof with the largest score is deemed the winner. The comparison is
illustrated in Algorithm~\ref{alg.nipopow-maxchain}.

Blockchain protocols can be upgraded using hard or soft
forks~\cite{buterinforks}. In a \emph{hard fork}, blocks produced by
upgraded miners are not accepted by unupgraded miners. It is simplest to
introduce interlinks using a hard fork by mandating that interlink pointers are
included in the block header. Unupgraded miners will not
recognize these fields and will be unable to parse upgraded blocks.
To ensure the block header is of constant size, instead of including all these
superblock pointers in the block header individually, they are organized into a
Merkle Tree of interlink pointers and only the root of the Merkle Tree is
included in the block header. In this case, the NIPoPoW prover that wishes to
show a block $b$ in their proof is connected to its more recently preceding
$\mu$-superblock $b'$, also includes a Merkle Tree proof proving that $H(b')$ is
a leaf in the interlink Merkle Tree root included in the block header of $b$.
The verifier must additionally verify these Merkle proofs.

In a \emph{soft fork}, blocks created by unupgraded miners are not accepted by
upgraded miners, but blocks created by upgraded miners are accepted by
unupgraded miners. Any additional data introduced by the upgrade must
be included in a field that is treated like a comment by an unupgraded miner.
To interlink the chain via a soft fork, the interlink Merkle Tree root is
placed in the \emph{coinbase} transaction instead of the block header. Upgraded
miners include the correct interlink Merkle Tree root in their coinbase and validate
the Merkle Tree root of incoming blocks.
This root is easily validated because it is
calculated deterministically from the previous blocks in the chain.
Unupgraded miners ignore this data and accept the block
regardless. The fork is successful if the majority of miners upgrade.
Whenever the prover wishes to show that a
block $b$ in the proof contains a pointer to its most recently preceding
$\mu$-superblock $b'$, it must accompany the block header of $b = s \conc
\overline{x} \conc ctr$ with the coinbase transaction $\coinbase$ of $b$ as well
as two Merkle Tree proofs: One proving $\coinbase$
is in $\overline{x}$, and one proving $H(b')$ is in the interlink
Merkle Tree whose root is committed in $\coinbase$.