empirical.tex

\section{Empirical analysis of improvement}

In order to empirically assess the space efficiency of our improvement, we
measured the size of the interlink data structure in the case of interlink
\emph{lists}, the previously proposed format, and in the case of interlink
\emph{sets}, our newly proposed format. We performed our measurements on the
mainnet for both Bitcoin and Litecoin. Our results are illustrated in
Figure~\ref{fig.set-list-vector-comparison} and are similar for both of these
coins. The figures assume that both coins have been velvet forked from their
genesis blocks to include the particular interlink vector format. This is
indicative of the future performance of velvet forking each blockchain to add
the respective interlink vector format.

The new data structure format yields savings of approximately $79\%$ on average.
Based on the theoretical analysis of Section~\ref{sec.construction}, we expect
to see approximately an improvement of $50\%$ in this structure. The extra
$29\%$ is due to the historical explosion of difficulty in the mining power in
both cryptocurrencies. The increased difficulty causes a lower variable
difficulty target, meaning that the lowest portions of the superblock levels
remain unoccupied, but are still accounted for in the interlink vector list
approach.

\begin{figure}
   \centering
   \subcaptionbox[]{%
      \centering
      Bitcoin
   }
   [
       0.80\textwidth
   ]
   {
       \includegraphics[width=0.85 \textwidth]
       {figures/interlink-vector-blocklist-vs-blockset.pdf}
   }
   \vskip 0pt
   \subcaptionbox[]{%
      \centering
      Litecoin
   }
   [
       0.80\textwidth
   ]
   {
       \includegraphics[width=0.85 \textwidth]
       {figures/interlink-vector-blocklist-vs-blockset-litecoin.pdf}
   }
   \caption{A comparison of interlink vector sizes for interlink block lists and interlink block sets in two popular blockchains (lower is better)}
   \label{fig.set-list-vector-comparison}
\end{figure}

Based on the sizes attained in the interlink vector of the Bitcoin blockchain,
we organized the interlink vector into Merkle trees for both the list and the
set structure and created proofs-of-inclusion of which we measured the size. The
sizes of the inclusion proofs for the two constructions are illustrated in
Figure~\ref{fig.set-list-proof-comparison}, while the percentile savings are
illustrated in Figure~\ref{fig.set-list-proof-comparison-savings}.

\begin{figure*}[h]
\begin{center}
  \includegraphics[width=0.95\textwidth]{figures/interlink-proof-list-vs-set.pdf}
  \caption{A comparison of a proof-of-inclusion size in the case of interlink block lists and interlink block sets in Bitcoin (lower is better)}
  \label{fig.set-list-proof-comparison}
  \end{center}
\end{figure*}

\begin{figure*}[h]
\begin{center}
  \includegraphics[width=0.95\textwidth]{figures/interlink-proof-savings-from-blockset.pdf}
  \caption{Percentile savings of the block set construction compared to the
           block list construction.}
  \label{fig.set-list-proof-comparison-savings}
  \end{center}
\end{figure*}

\begin{table}[h!]
  \begin{center}
    \begin{tabularx}{\textwidth}{|c|YY|YY|c|}
      \hline
      & \multicolumn{2}{c|}{\bf Interlink size}
      & \multicolumn{2}{c|}{\bf Proof-of-inclusion size}
      & \textbf{NIPoPoW size}\\
      & blockhashes & bytes & hashes & bytes & KB\\
      \hhline{------}
      \textbf{Interlink lists}&
      43.12 & 1380 & 5.7 & 183 & 65.7\\
      \hline
      \makecell{\bf Interlink sets}&
      9.04 & 289 & 3.6 & 116 & 49\\
      \hline
    \end{tabularx}
    \vspace{10pt}
    \caption{A comparison of the two interlink constructions in terms of size.}
    \label{tab.savings}
  \end{center}
\end{table}

We summarize the savings of our construction in Table~\ref{tab.savings}. The
table was constructed by inspecting the Bitcoin
blockchain at the time of writing. The interlink size column shows the average
interlink vector size, in the number of block hashes and in concrete bytes assuming
the \texttt{SHA256} function is used (as in Bitcoin). The proof-of-inclusion
size column shows the average size of a Merkle proof-of-inclusion, in the number
of hashes and in bytes, when the interlink vector is compacted into a Merkle
tree using \texttt{SHA256}. Finally, the NIPoPoW size column
shows the size of a NIPoPoW in kilobytes (excluding the last $k$ blocks of the
chain which must be sent \emph{verbatim} irrespectively of which synchronization protocol is used). The NIPoPoW sizes are
calculated assuming Bitcoin had included the respective interlink Merkle tree
root in their headers since genesis. We measured the size of suffix-proof
NIPoPoWs based on the recommended parameter $m = 15$~\cite{nipopows} assuming a
chain size of $|C| = 563{,}451$. The number of blocks in a NIPoPoW is $(m(\lg
|C| - \lg m) + 1.5m) = 250$ in expectation. For the final size calculation of
the NIPoPoW, we included all the data required: The proofs-of-inclusion (based
on the size given on the previous column) and the block headers needed (80 bytes
per block). Our results indicate $79\%$ savings in the interlink sizes and
$25\%$ savings in the NIPoPoW sizes.