preliminaries.tex

\section{Superblocks and proofs-of-proofs}

Blocks generated in proof-of-work~\cite{C:DwoNao92} systems must satisfy the
proof-of-work equation $H(B) \leq T$ where $T$ denotes the mining
target~\cite{SP:BMCNKF15} and $B$ denotes the block contents, which is a triplet
including a representation of the application data and metadata, a nonce, and a
reference to the previous block by its hash. The function $H$ is a hash
function, modelled as a random oracle~\cite{CCS:BelRog93}, which outputs
$\kappa$ bits, where $\kappa$ is the security parameter of the protocol and $T <
2^\kappa$. It sometimes happens that some blocks satisfy a stronger version of
the equation~\cite{popow}, namely that $H(B) \leq T2^{-\mu}$ for some $\mu \in
\mathbb{N}$. Such blocks are called $\mu$-superblocks~\cite{nipopows}.
It follows directly from the Random Oracle model that
$\Pr[B \text{ is a } \mu\text{-superblock}|B \text{ is a valid block}] = 2^{-\mu}$. Note that if a block is a $\mu$-superblock for some $\mu > 0$, then it is
also a $(\mu - 1)$-superblock. We denote the maximum $\mu$ of a block $B$ its
$level(B) = \lfloor \lg(T) - \lg(H(B)) \rfloor$.

The count of superblocks in a chain decreases exponentially as $\mu$ increases.
If a blockchain $\chain$ generated in an honest execution has $|\chain|$ blocks,
it only has $2^{-\mu}|\chain|$ superblocks of level $\mu$ in expectation. Hence,
the total number of levels is $\lg(|\chain|)$ in expectation. It has been
theoretically posed that the distribution of superblocks can be adversarially
biased in so-called ``badness'' attacks~\cite{nipopows} in which an adversary
reduces the density of superblocks of a particular level within a blockchain.
However, the actual distribution of superblocks in currently deployed
blockchains has not been measured. Therefore, it was previously unknown whether
such attacks are taking place in the wild. In this paper, we make empirical
measurements of superblock distributions and observe that they follow the
expectation. Hence, we conclude that widespread badness attacks have not
occurred in practice, confirming previous suspicions that such attacks are
costly to mount.

For any block $B$,
it is useful to be able to refer to its most recent preceding $\mu$-superblock
for any $\mu \in \mathbb{N}$. In addition, it is useful to include this
reference within the contents of the block to which proof-of-work is being applied
so that the miner proves that she had knowledge of the preceding superblock
when $B$ was generated. For this purpose, it has been
recommended~\cite{nipopows} that for each block $B$, instead of including only a
pointer to the previous block, $\lg(|\chain|)$ pointers will be included, one
for each level $\mu$ pointing to the most recent $\mu$-superblock preceding $B$.
Hence, under this modification, every block contains a pointer to its most
recent $0$-superblock ancestor, its most recent $1$-superblock ancestor, and so
on, of which there are $\lg(|\chain|)$. These pointers change the blockchain
into a block skiplist~\cite{skiplist,papadakis1993skip}.

These $\lg(|\chain|)$ pointers per block are called the \emph{interlink}.
One way to include them is to replace the \textsf{previd} pointer, which in
typical blockchains points to the previous block hash, with the interlink list
of block hashes to be included \emph{verbatim} in the block header.
Alternatively, the interlink list of hashes can be
organized into a compact data structure such as a Merkle tree~\cite{merkletree}
containing one leaf per superblock level $\mu$. The number
of leafs in this Merkle tree is $\lg(|\chain|)$ and its height is
$\lg\lg(|\chain|)$. Hence,
proofs-of-inclusion in this Merkle tree are of size
$\Theta(\lg\lg(|\chain|))$. The root of this Merkle tree can be included in the
block header, replacing \textsf{previd}. This is done in blockchains adopting
interlinking from genesis or through a hard fork~\cite{nimiq,ergo}.

More commonly, to avoid modifying the block header format, the interlink Merkle
tree root can be included in the block's application data. In this case, the
root of the Merkle tree appears as auxiliary data within a particular transaction
which is included in the block. If the miners of the blockchain are aware of the
interlink, then it can be required that they included it in their coinbase
transaction. The veracity of the interlink data does not need to be verified
when it is included in a block, as invalid or malicious data in the interlink
does not harm security. Hence, it is possible to include the interlink data in a user
transaction. In this case, the transaction which includes the root of the
interlink is called a \emph{velvet transaction} and its inclusion is termed a
\emph{user-activated velvet fork}~\cite{gtklocker}. In practice, this
transaction is implemented using an
\textsf{OP\_RETURN}~\cite{bartoletti2017analysis} committing to the Merkle tree
root containing the interlink list in its leafs. User-activated velvet forks
allow the adoption of a new rule without requiring miners to upgrade their
software or be aware of the change, and are hence backwards-compatible.

It is useful to be able to prove that a block $B$ contains a pointer to a
particular ancestor $B'$ in its interlink. This statement is proven by a full
node who holds all blockchain data, the \emph{prover} $P$, to a superlight
\emph{verifier} $V$ who holds only the header of block $B$. This proof is
straightforward. The header of block $B$ contains the Merkle tree root of the
transactions tree $mtr_1$ and is hence known to $V$. First, a Merkle
tree proof-of-inclusion $\pi_1$ proves that $mtr_1$ contains the velvet transaction
$tx$. The velvet transaction $tx$ commits to auxiliary data which includes the
interlink Merkle tree root $mtr_2$.
Secondly, another Merkle tree proof-of-inclusion $\pi_2$ proves that $mtr_2$
contains the hash of $B'$. While we cannot improve the size of $\pi_1$, in this
paper we describe the improvement in the size of $\pi_2$.

Superblock pointers can be used to traverse the blockchain from the tip back to
Genesis in a manner which skips some unnecessary intermediary blocks and
includes others. The idea is to convince a superlight verifier $V$, which only
has access to the Genesis block, that a particular blockchain is the longest one
without presenting all block headers. Blocks of interest that are part of the
longest chain can then be revealed to $V$ in order to convince them that a
particular transaction has been confirmed. In order to do that, $P$ finds a
succinct sample of blocks and places it in chronological order. That sample is
chosen such that each next block within the sample contains a pointer to its
immediate ancestor within the sample by a commitment in the interlink vector.
The prover $P$ sends each block of the sample to $V$, along with a
proof-of-inclusion for the respective pointer. The verifier $V$ can check if the
correct pointer has been included. By cleverly choosing which blocks to collect,
a full node can prove to a superlight node that the currently adopted longest
blockchain is the claimed one without presenting the whole blockchain. Hence,
instead of transmitting data linear in the chain size $\Theta(|\chain|)$ as SPV
clients do, it is sufficient to transmit succinct certificates which are only of
size $\Theta(\emph{poly}\log(|\chain|))$. Such certificates are called
Non-Interactive Proofs of Proof-of-Work~\cite{nipopows}. In this paper, we are
not concerned about the mechanism by which the NIPoPoWs protocol samples blocks,
but only the number of blocks in these samples and the sizes of their
proofs-of-inclusion, which we optimize here.

The NIPoPoWs protocol is parameterized by a security parameter $m$. The number
of blocks $|\pi|$ in a given Non-Interactive Proof of Proof-of-Work sample is as
follows. For each superblock level $\mu \in \mathbb{N}$, consider the
blocks in the honestly adopted blockchain $\chain$. Among these, some
are of level $\mu$, so denote the count of $\mu$-level superblocks in $\chain$
as $|\chain\upchain^\mu|$. If $|\chain\upchain^\mu| \geq m$, then we call $\mu$
an \emph{included level}. Consider the maximum included level $\max\mu$. It has
been proven~\cite{nipopows} that $\max\mu = \lg(|\chain|) - \lg(m)$. The proof
$\pi$ contains $1.5m$ blocks for the maximum included level and $m$ additional blocks for
each lower level in expectation. Hence the number of blocks in a NIPoPoW is
$|\pi| = 1.5m + m \max\mu = 1.5m + m(\lg(|\chain|) - \lg(m))$. For each of
these blocks, the proof contains the block hash and the respective
proofs-of-inclusion for the pointer to the preceding ancestor. In this paper, we
optimize the size of these proofs-of-inclusion, which gives a direct improvement
to the size of such proofs $\pi$. We note that, in our proposed construction,
we do not decrease the number of required blocks in $\pi$, only the bytes that
need to be transmitted for it on the network.

The size of these proofs is critical. As the majority of the time needed for
mobile wallets to perform the initial synchronization with the network is spent
on downloading block headers from the network, bringing down the proof size
directly improves the performance of superlight clients. In the context of
cross-chain transfers~\cite{pow-sidechains}, these proofs are posted and
persistently stored in smart contracts~\cite{buterin,wood} within blockchains
which function as SPV verifiers for other blockchains~\cite{christoglou}.
Improving their size has direct financial impact
on the protocol, as a larger size incurs a larger gas cost for storage purposes
in case such proofs are stored within Ethereum.