introduction.tex

\section{Introduction}

Bitcoin~\cite{bitcoin} and other blockchains which use the same backbone
consensus mechanism~\cite{EC:GarKiaLeo15} use Simple Payment Verification (SPV)
to shorten the synchronization time for lightweight clients, where the clients
need to download block headers instead of whole blocks. Recently, a line of
work has introduced \emph{superlight} clients, which do not require all
blockchain headers to be downloaded, but, rather, only a sample of them. This
sample consists of blocks which happen to achieve a higher difficulty than the
required one, and are thus termed \emph{superblocks}.

By sampling the superblocks of a chain, short proofs about a blockchain can be
created, which allow a client to synchronize with the longest blockchain without
downloading all blocks. These so-called \emph{proofs of proof-of-work} contain
only a small number of cleverly chosen superblocks which compact the
proof-of-work of the blockchain into a succinct string, while maintaining the
same security level as SPV clients. However, while the protocol has even been deployed in
practice, the distribution of superblocks within a blockchain has not been
previously measured. In this paper, we provide measurements of this distribution for the
Bitcoin blockchain.

In order for superblock sampling to work, it is necessary that each block
contains, in addition to the standard pointer to its previous block, a few
select pointers to some preceding superblocks. These pointers are organized in a
special data structure, the \emph{interlink}. For relevant applications such as
superlite clients and cross-chain transfers, it is critical that the interlink
structure is compact. We measure the size of the interlink structure and provide
a simple novel optimization which can bring down its size to less than a
half. We then study the impact of this improvement on the size of proofs of
proof-of-work.

\noindent
\textbf{Related work.}
Superblocks were first observed to exist in~\cite{highway}.  The interlink data
structure was put forth in~\cite{popow}, where it was also observed that it can
be organized into a Merkle tree. Interlinks containing all the blocks of the
blockchain have been proposed in~\cite{flyclient}. Superblock interlinks have
been included from genesis in cryptocurrencies such as ERGO~\cite{ergo} and
nimiq~\cite{nimiq}. Complete blockchain interlinks have been proposed for Ethereum~\cite{eip210}. Nimiq and ERGO have independently applied interlink deduplication in practice to save space~\cite{nimiq-dev-ref,ergo}. In~\cite{nipopows}, the consumption of the interlink data to
construct Non-Interactive Proofs of Proof-of-Work was presented and concrete
numbers were given about the sizes of such proofs. They also presented a way to
construct such a structure without a soft or hard fork, but a backwards
compatible \emph{velvet fork}, which was later explored in~\cite{velvet}.
Bitcoin Cash has been velvet forked in this manner~\cite{gtklocker}. Beyond
superlight clients, another
application of NIPoPoWs are cross-chain transfers~\cite{pow-sidechains}
between proof-of-work blockchains. Comparable
constructions have also appeared for proof-of-stake
blockchains~\cite{pos-sidechains}.

\noindent
\textbf{Our contributions.} The contributions of this paper are summarized as
follows:

\begin{enumerate}
  \item We measure superblock distributions in Bitcoin. We observe that the
        distribution of superblocks follows expectation, indicating there are no
        ongoing or historical attempts to bias the distribution of superblocks
        (so-called \emph{badness} attacks~\cite{nipopows}). We are the first to
        collect any empirical measurements of superblocks on real blockchains.
  \item We describe the simple but important optimization in regards to the way
        blocks are compactly stored in an interlink tree by observing that
        duplicate pointers can be removed without harming security. As such, we
        construct interlink \emph{block sets} instead of interlink \emph{block
        lists}.\footnote{The deduplication optimization has already been
        discovered and deployed independently by the Nimiq and the ERGO
        blockchains~\cite{nimiq-dev-ref,ergo}, but with no further analysis.}
  \item We prove that our optimization reduces the number of pointers in each
        interlink by a half in expectation.
  \item We evaluate our improvement on the Bitcoin blockchain and collect
        empirical data regarding the performance of our improvement, including
        concrete sizes of NIPoPoWs built. We experimentally demonstrate that our
        optimization reduces interlink vector sizes by $79\%$ on average and
        the already very succinct NIPoPoW certificates by $25\%$ on average.
\end{enumerate}