11institutetext: The University of Texas at Austin, TX, USA 11email: {hegde,
rpstreit, yanni.georghiades<EMAIL_ADDRESS>22institutetext: Indian
Institute of Science, KA, India
22email<EMAIL_ADDRESS>
# Achieving Almost All Blockchain Functionalities with Polylogarithmic Storage

Parikshit Hegde 11 Robert Streit 11 Yanni Georghiades 11 Chaya Ganesh 22
Sriram Vishwanath 11

###### Abstract

In current blockchain systems, full nodes that perform all of the available
functionalities need to store the entire blockchain. In addition to the
blockchain, full nodes also store a blockchain-summary, called the _state_ ,
which is used to efficiently verify transactions. With the size of popular
blockchains and their states growing rapidly, full nodes require massive
storage resources in order to keep up with the scaling. This leads to a tug-
of-war between scaling and decentralization since fewer entities can afford
expensive resources. We present _hybrid nodes_ for proof-of-work (PoW)
cryptocurrencies which can validate transactions, validate blocks, validate
states, mine, select the main chain, bootstrap new hybrid nodes, and verify
payment proofs. With the use of a protocol called _trimming_ , hybrid nodes
only retain polylogarithmic number of blocks in the chain length in order to
represent the proof-of-work of the blockchain. Hybrid nodes are also optimized
for the storage of the state with the use of _stateless blockchain_ protocols.
The lowered storage requirements should enable more entities to join as hybrid
nodes and improve the decentralization of the system. We define novel
theoretical security models for hybrid nodes and show that they are provably
secure. We also show that the storage requirement of hybrid nodes is near-
optimal with respect to our security definitions.

###### Keywords:

Blockchains, Cryptocurrency, Storage, NIPoPoW, Hybrid Nodes, Trimming

##  1 Introduction

Blockchains enable a group of untrusting parties to securely maintain a
distributed ledger without relying on a trusted third party. Instead, the
power to decide what is recorded in the blockchain is distributed amongst a
set of decentralized nodes. This property is desirable for applications used
by a set of mutually distrustful parties, such as a digital currency. For this
reason, _cryptocurrencies_ are a fundamental application of blockchains and
are increasingly growing in popularity. In this paper, we focus on
cryptocurrencies built on top of a proof-of-work (PoW) blockchain employing
the longest chain rule. A blockchain node for a cryptocurrency typically has
the following functionalities:

  1. 1.

_Transaction validation_ : When the node receives a new transaction, it checks
if the transaction is valid with respect to the transactions already confirmed
in the blockchain.

  2. 2.

_Block validation_ : When the node receives a new block, it verifies that the
block hash is valid, all the transactions in the block are valid, and the
block otherwise follows all of the conventions imposed by the protocol.

  3. 3.

_State Validation_ : Given a summary of currency ownership in the system,
called the _state_ , the node verifies that the state is consistent with the
blockchain.

  4. 4.

_Mining_ : The node can append a block to the blockchain by verifying its
contents and producing a PoW for the block. A node which does not mine blocks
is assumed to have mining power 0.

  5. 5.

_Chain Selection_ : Given a set of conflicting chains, the node can choose the
main chain which has the most PoW. Any two honest nodes which receive the same
set of conflicting chains in the same order must select the same main chain.

  6. 6.

_Bootstrapping new nodes to the blockchain_ : A node can provide new nodes
entering the system with the blockchain.

  7. 7.

_Serving payment proofs_ : Given a transaction $tx$, the node can provide a
_proof_ of $tx$’s inclusion in the blockchain.

  8. 8.

_Verification of payment proofs_ : Given a proof of transaction $tx$’s
inclusion in the blockchain, the node can verify the correctness of the proof.

In order to have all of the functionalities above, a node must verify and
store the entire blockchain. We will refer to such nodes as _full nodes_.
Popular systems like Bitcoin and Ethereum also allow for other types of nodes
with more limited functionalities [35, 29]. For instance, _pruned nodes_
initially download the entire blockchain and verify it. However, they later
_prune_ the blockchain, meaning that they discard block data and only retain
block headers for blocks older than the most recent $k$ blocks in the
blockchain. By retaining a summary of the blockchain called the _state_ , they
can still perform all desired functionalities except for serving proofs of
payment and bootstrapping new nodes. _Lightweight nodes_ only download the
block-headers, and their only functionality is to verify payment proofs
provided by full nodes. Importantly, full nodes are necessary to bootstrap
both pruned and lightweight nodes into the blockchain.

Since full nodes need to store the entire blockchain, their resource
requirements can be high. This is an entry barrier that makes fewer nodes
participate, which leads to a centralization of trust. In this paper, we
optimize storage requirements in order to lower this entry barrier. In
deference to the storage capabilities of modern computational hardware, we
divide storage into two categories. The first is _cold storage_ , which is
accessed infrequently and is stored on disk. This includes older blocks that
are deep inside the blockchain. The second is _hot storage_ , which is
accessed frequently and is stored in memory. Naturally, the blockchain state
used to validate blocks and transactions is kept in hot storage.

In this paper, we propose a new class called _hybrid nodes_. Hybrid nodes have
all of the above functionalities except for the ability to provide payment
proofs. Importantly, hybrid nodes can bootstrap new hybrid nodes into the
system, meaning they do not depend on any other type of nodes, including full
nodes. Moreover, if $B$ is the length of the blockchain, hybrid nodes only
require $polylog(B)$ cold storage to represent the PoW of the chain. This is
achieved by a process we call _trimming_ , an extension of non-interactive-
proofs-of-proof-of-work [25] (henceforth, NIPoPoW). NIPoPoW is a protocol that
enables a prover (which is most often a full node) to provide payment proofs
of $polylog(B)$ size rather than the traditional $B$ size, but NIPoPoW still
requires the prover to store the entire blockchain. We extend these techniques
further in our trimming protocol to securely remove blocks and reduce storage.

We now comment on the _practical implications_ of our proposed protocols for
hybrid nodes. There are two main components of a blockchain with significant
storage requirements for hybrid nodes. First is the storage required to
represent the PoW of the chain, which is used by the consensus protocol. In
traditional systems, since the entire chain of block-headers must be stored,
the storage requirements for this component at the time of writing could be in
the order of 100s of megabytes for systems such as Bitcoin and Ethereum. Our
trimming protocols for hybrid nodes can decrease this requirement to the order
of 100s of kilobytes. While 100MB might not seem large, if one wishes to run a
number of blockchains on a single device then the storage requirement can
quickly multiply into the gigabytes range if methods such as _trimming_ are
not employed. Moreover, since hybrid nodes only store $polylog(B)$ number of
block headers, their storage requirement grows slower with time too. The
second component that requires storage is the blockchain state (UTXO or
account-based for cryptocurrencies). For instance, the size of Bitcoin’s UTXO
set is roughly 4GB [3]. However, some novel stateless blockchain protocols
reduce this storage requirement to the order of kilobytes by requiring clients
to provide payment proofs [1]. In Section 7 and Appendix 0.J, we show that
hybrid nodes can employ stateless blockchain protocols, thus optimizing both
their PoW and state storage.

Previous works, specifically CoinPrune and SecurePrune [28, 33], achieve the
same functionalities as hybrid nodes with lower storage requirements than full
nodes. They achieve this by storing a commitment to the blockchain-state in
the blocks and pruning blocks that are deep in the blockchain. However, their
storage requirement still scales linearly with blockchain length. Moreover,
these works provide a largely qualitative analysis of their respective
protocols. In contrast, we perform a rigorous security analysis and provide
proofs that hybrid nodes are secure.

Concurrent with the initial submission of our work, we were made aware of an
independent work that uses a modification of NIPoPoWs to obtain
polylogarithmic storage [24]. Although both protocols are similarly motivated,
we believe that our security definitions and the corresponding analysis are
novel and crucial to this area. Of particular note, we believe that security
against a trim-attack (see Section 5), is crucial for the operation of hybrid
nodes. Unlike our protocol, [24] claim to not require _optimism_ for
_succinctness_ (see further in Theorem 6.3 and Remark 1). However, we note
that it doesn’t seem economically viable for an adversary to expend resources
to simply hurt the succinctness of hybrid nodes.

We defer the discussion of other related works which aim to optimize
blockchain storage to Appendix 0.A.

We now summarize our results and outline the organization of the paper. In
section 2, we introduce the basic model and notation. In section 3, we
summarize CoinPrune and NIPoPoW, which are building blocks for our protocol.
In section 4, we explain the properties of the hybrid node’s chain and
describe the trimming protocol, though we defer the description of chain
selection and state verification protocols to Appendix 0.C due to space
constraints. In section 5, we introduce novel security definitions for hybrid
nodes, including $\mathsf{trim\mathchar 45\relax attacked}$,
$\mathsf{congruence}$, $\mathsf{state\mathchar 45\relax attacked}$, and
$\mathsf{bootstrap\mathchar 45\relax attacked}$. In section 6, we show that
hybrid nodes satisfy all the security properties with high probability, and we
also discuss the polylogarithmic storage requirement and the lower bound on
the storage requirement. For brevity, formal proofs for these results are
deferred to Appendices 0.E-0.H. In section 7, we illustrate that when combined
with stateless blockchain protocols, hybrid nodes are optimized both in terms
of cold and hot storage. And, we examine directions for future work in Section
8.

Our primary contributions are the protocols associated with the hybrid nodes
and the novel security definitions and their associated theorems. These are in
sections 4, 5 and 6.

##  2 Model and Notation

In this work, we consider a set of nodes running a PoW blockchain. We model
the system using continuous time, which accurately models systems with high
hash-rates such as Bitcoin and Ethereum[2, 15]. In this section, we restrict
the model description to the essentials required to describe our protocol.
Supplemental model details used for security analysis are deferred to Appendix
0.B.

Several communication models are considered in the literature. The simplest is
the _synchronous_ model where a block broadcast by a node at a certain time is
received by all other nodes immediately [17, 16]. Since time is continuous, no
more than one block is mined at any given time, implying only one block could
be in communication at any given time. More complicated communication models
with communication delays are also considered in the literature [30, 36]. For
the sake of simplicity, we consider the synchronous model in this paper and
leave it to future work to transfer our results to more complicated
communication models. Note that because of synchronous communication, all
honest nodes have knowledge of the same set of blocks at any given time.

#### Basic Blockchain Notation

The honest (longest-)chain at time $t$ is represented by
$\operatorname{\mathcal{C}}_{t}$. The number of blocks in
$\operatorname{\mathcal{C}}_{t}$ is called the chain-length and is denoted as
$B_{t}$. When the time $t$ is clear from context, we may drop the subscript
and refer to it as just $\operatorname{\mathcal{C}}$. Blocks in
$\operatorname{\mathcal{C}}$ are indexed as an array in a similar convention
to the Python programming language, meaning that
$\operatorname{\mathcal{C}}[i]$ is denoted as block $i$. Since it is
convenient, we refer to a block by its index $i$ and not its contents.
$\operatorname{\mathcal{C}}[0]$ is called the _genesis block_.
$\operatorname{\mathcal{C}}[i_{1}:i_{2}]$ represents the segment of the chain
from block $i_{1}$ to block $(i_{2}-1)$. If at any time an honest node hears
of another chain $\operatorname{\mathcal{D}}$ which is longer than
$\operatorname{\mathcal{C}}_{t}$, then it adopts $\operatorname{\mathcal{D}}$
as the honest chain (i.e.,
$\operatorname{\mathcal{C}}_{t^{+}}=\operatorname{\mathcal{D}}$, where $t^{+}$
indicates the time incrementally after $t$). The last common block between two
chains $\operatorname{\mathcal{C}}$ and $\operatorname{\mathcal{D}}$ is called
the _latest common ancestor_ (LCA), and is denoted as
$b=\mathsf{LCA}(\operatorname{\mathcal{C}},\operatorname{\mathcal{D}})$.
Specifically,
$\operatorname{\mathcal{C}}_{t}[:b+1]=\operatorname{\mathcal{D}}[:b+1]$, and
$\operatorname{\mathcal{C}}_{t}[b+1:]\cap\operatorname{\mathcal{D}}[b+1:]=\emptyset$.
When a new block $\bar{b}$ is appended to $\operatorname{\mathcal{C}}$, we
denote the extended chain as $\operatorname{\mathcal{C}}\bar{b}$.

In our model, hybrid nodes do not store the entire chain
$\operatorname{\mathcal{C}}_{t}$, but instead store a trimmed version which
contains fewer blocks than $\operatorname{\mathcal{C}}_{t}$. The trimming
protocol and its associated notation is described in Section 4.

#### Blockchain State

When a new transaction is submitted, a node must check if it is “valid” with
respect to the chain $\operatorname{\mathcal{C}}_{t}$. This could be
accomplished by parsing through the complete log of transactions in
$\operatorname{\mathcal{C}}_{t}$. However, due to the rapidly increasing size
of $\operatorname{\mathcal{C}}_{t}$, it is far more efficient for a node to
validate transactions against a summary of the chain called the state, and
denoted as $\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t})$.
Equivalently, we may refer to the state as
$\operatorname{\mathsf{state}}(B_{t})$, where $B_{t}$ is the length of the
chain $\operatorname{\mathcal{C}}_{t}$. Validating a transaction against
$\operatorname{\mathcal{C}}_{t}$ is equivalent to validating it with respect
to $\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t})$, so using
$\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t})$ is preferred
due to its smaller hot storage requirement. After a new block $\bar{b}$ is
added to the chain, the new state is computed as
$\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t}\bar{b})=F(\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t}),\bar{b})$,
where $F()$ is a function that applies the transactions in $\bar{b}$ to
$\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t})$. When the new
block is clear from context, we denote the function simply as
$F(\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t}))$, and when
the function is applied on $n$ sequential new blocks, we denote the operation
as
$\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t}b_{1}b_{2}\dots
b_{n})=F^{n}(\operatorname{\mathcal{C}}_{t})$. Two types of states are
popular: 1) _UTXO-based State_ : this stands for unspent transaction output,
and is used by Bitcoin. The UTXO state consists of a list of unspent coins. A
new transaction is valid with respect to the state, if it consumes one or more
of these coins, and creates new coins whose total value is no larger than the
consumed coins; 2) _Account Based State:_ This is used in Ethereum. An
account-based state consists of a vector of key-value mappings, with one
mapping corresponding to each user. The key establishes the user’s identity,
and the value establishes the balance in the user’s account. A user can issue
a transaction that transfers a part of his account’s balance to another user.

#### Interlinks

Figure 1: An example of the interlink structure (inspired by Figure 1 of
[11]). At the bottom of each block is its index, and the block’s height
signifies its superblock level. Each block has a link to the closest ancestor
at every level, which is shown by the arrows linking blocks to ancestors.
Notice all the blocks are contained in level 0, and only the genesis block is
in level 4.

In traditional blockchains like Bitcoin, each block contains a link (using a
hash) to the previous block in the chain. To enable hybrid nodes to store the
blockchain in a succinct way, we employ a clever link structure called the
_interlink_. Interlinks were introduced in [23] and further developed in [25].

In the interlink model, a block contains the following information: 1)
transactions in the block; 2) the Merkle root $x$ of all the transactions in
the block; 3) the Merkle root
$y\left(\operatorname{\mathsf{state}}(B_{t})\right)$ of the corresponding
blockchain state; 4) the block index $i$; 5) the _interlink_ , which contains
hash links to several previous blocks and is described in detail in the
following paragraphs; 6) the random nonce $\eta$; and 7) the block hash
$\mathtt{id}=H(\eta,x,y,i,\mathtt{interlink})$, where $H()$ is a hash
function. For a block to be valid, $\mathtt{id}$ must contain at least $T$
leading $0$’s. Equivalently, we say that $\mathtt{id}\leq 2^{-T}$. All the
information in the block _except_ the list of transactions is referred to as
the _block-header_. Observe that the $\mathtt{id}$ of the block can be
verified given just the block-header.

To describe the interlink, we first need to define _superblocks_. A
level-$\mu$ superblock is a block with $\mathtt{id}\leq 2^{-(T+\mu)}$. Since a
valid block satisfies $\mathtt{id}\leq 2^{-T}$, all valid blocks are level-0
superblocks. The genesis block is defined to be a superblock of every level
from $0$ to $\infty$. And, a level-$\mu$ superblock is also a
level-$\mu^{\prime}$ superblock for all $0\leq\mu^{\prime}\leq\mu$, since
$2^{-(T+\mu)}\leq 2^{-(T+\mu^{\prime})}$.

The $\mathtt{interlink}$ data-structure in a block contains a link to the
previous superblock of level $\mu$ for every level $\mu$ that is in the chain
$\operatorname{\mathcal{C}}_{t}$ up to that block. Since the previous block
will always be a superblock of level at least $0$, the interlink always
contains a link to the previous block (thus, without any further modification,
the security properties of the blockchain are unaffected). Also, since the
genesis block is of all possible levels, a link to the genesis block is always
included. A pictorial example of this is shown in Figure 1.

Using interlinks, it is possible to “skip” over blocks when traversing the
blockchain. To be more specific, it is useful to define notation for
“traversing the blockchain at level-$\mu$”. For any given chain
$\operatorname{\mathcal{C}}$, the level-$\mu$ _upchain_ , denoted
$\operatorname{\mathcal{C}}\uparrow^{\mu}$, is the sequence of all level-$\mu$
superblocks in $\operatorname{\mathcal{C}}$. That is,

$\operatorname{\mathcal{C}}\uparrow^{\mu}\triangleq\left\\{b:b\in\operatorname{\mathcal{C}},\text{
and }\mathtt{id}(b)\leq 2^{-(T+\mu)}\right\\}.$ (1)

Note that although it is convenient to use set-notation to define it,
$\operatorname{\mathcal{C}}\uparrow^{\mu}$ is a sequence with the order of its
blocks being the same as they are in $\operatorname{\mathcal{C}}$. From the
definition of the interlink, each block in the upchain
$\operatorname{\mathcal{C}}\uparrow^{\mu}$ contains a reference to the
previous block in the upchain. Therefore, it is possible to traverse through
$\operatorname{\mathcal{C}}\uparrow^{\mu}$. Additionally, a chain
$\operatorname{\mathcal{C}}^{\prime}$ is called a level-$\mu$ _superchain_ if
all its blocks are level-$\mu$ superblocks. That is, if the underlying chain
of $\operatorname{\mathcal{C}}^{\prime}$ is $\operatorname{\mathcal{C}}$, then
$\operatorname{\mathcal{C}}^{\prime}\subseteq\operatorname{\mathcal{C}}\uparrow^{\mu}$.

We use square-brackets to index $\operatorname{\mathcal{C}}\uparrow^{\mu}$,
similar to a python array. However, at times it is useful to refer to blocks
in $\operatorname{\mathcal{C}}\uparrow^{\mu}$ according to the block’s index
in $\operatorname{\mathcal{C}}$. In this case, we use curly-braces to index
$\operatorname{\mathcal{C}}\uparrow^{\mu}$. This is best illustrated using an
example. Consider, $\operatorname{\mathcal{C}}=\\{0,1,2,3,4,5,6,7,8,9,10\\}$,
and let $\operatorname{\mathcal{C}}\uparrow^{\mu}=\\{0,3,4,7,10\\}$. In this
case, $\operatorname{\mathcal{C}}\uparrow^{\mu}[3:]=\\{7,10\\}$, but
$\operatorname{\mathcal{C}}\uparrow^{\mu}\\{3:\\}=\\{3,4,7,10\\}$. As a
further illustration of the upchain notation, in the blockchain in Figure 1,
$\operatorname{\mathcal{C}}\uparrow^{2}=\\{0,4,8,12\\}$.

##  3 Preliminaries

Before describing our protocol, we summarize CoinPrune [28] and NIPoPoW [25].
Our protocol builds upon both of these protocols.

#### CoinPrune

In CoinPrune, similar to our model, blocks contain commitments to the
blockchain-state. The protocol selects a _pruning point_ $k$ blocks from the
tip of the chain. All blocks after the pruning point are retained completely,
while only block headers are retained prior to the pruning point. The state of
the blockchain at the pruning point is also stored. Then, the PoW in the chain
can be established since the block headers for the entire chain are preserved.
Furthermore, since the state at the pruning point is preserved and a
commitment to it is stored in the blocks, the state corresponding to each
block after the pruning point can be recovered. Refer to Figure 2 for a visual
description.

Figure 2: An instance of CoinPrune. Complete square-boxes indicate the
complete blocks after the pruning point, and incomplete boxes indicate block-
headers of blocks before the pruning point. The variables $y_{i}$ are the
state-commitments of the respective states stored in the block headers. They
are shown separately from the block only for emphasis. The state at the
pruning point is stored, and its validity is confirmed by the state-
commitments $y_{i}$’s.

While our method for establishing the state of the blockchain is similar to
CoinPrune, we deviate in the way we establish the PoW of the chain. We note
that although CoinPrune improves storage compared to full nodes, they still
store the entire block-header chain prior to the pruning point. Thus, their
storage requirement still scales linearly in the length of the chain, albeit
the multiplicative constant may be very small. In contrast, we retain only a
subset of the block headers, leading to sublinear storage requirement in the
number of blocks in the blockchain. To accomplish this, we take inspiration
from NIPoPoW.

#### NIPoPoW

NIPoPoW is a protocol that is used to provide succinct proofs of payments to
lightweight clients. Payment proofs have two components. First, the proof
needs to establish the amount of PoW in the blockchain, and second, it needs
to contain a proof of inclusion of the payment in the chain. Traditionally,
the PoW of the chain is established by sending the entire chain of block
headers to the lightweight client. NIPoPoWs optimize this step by making the
following observation. Informally, by the property of concentration around the
means, the $\mu$-upchain $\operatorname{\mathcal{C}}\uparrow^{\mu}$ of an
underlying chain $\operatorname{\mathcal{C}}$ is such that
$2^{\mu}\lvert\operatorname{\mathcal{C}}\uparrow^{\mu}\rvert\approx\lvert\operatorname{\mathcal{C}}\rvert$
(as an illustration, in Figure 1, superblocks of level-2 appear roughly every
$2^{2}=4$ blocks). Recall that a level-$\mu$ superblock is $2^{\mu}$ times
harder to find than a regular block (i.e., a level-0 superblock). Therefore,
if
$2^{\mu}\lvert\operatorname{\mathcal{C}}\uparrow^{\mu}\rvert\approx\lvert\operatorname{\mathcal{C}}\rvert$,
then it is as hard for an adversary to create a fork around
$\operatorname{\mathcal{C}}\uparrow^{\mu}$ with level-$\mu$ superblocks as it
is to create a fork around $\operatorname{\mathcal{C}}$ with level-$0$
superblocks. Therefore, it is sufficient to just provide
$\operatorname{\mathcal{C}}\uparrow^{\mu}$ as a proof of the PoW of the chain.
For a large enough level $\mu$, $\operatorname{\mathcal{C}}\uparrow^{\mu}$ is
much smaller in size than the underlying chain $\operatorname{\mathcal{C}}$,
thus making NIPoPoWs much faster than traditional protocols.

Our protocol differs from NIPoPoWs in several ways. First, the goal of our
protocol is to optimize a hybrid node’s storage while retaining almost all of
a full node’s functionalities, while the goal of NIPoPoWs is to provide
succinct payment proofs. Second, NIPoPoWs do not optimize the prover’s storage
since the prover must still store the entire blockchain. Third, NIPoPoWs are
one-time proofs of payment, meaning they need to be generated afresh for every
new proof request, whereas our protocol proceeds in an iterative manner
throughout the blockchain’s execution. In particular, we employ different
_level ranges_ (elaborated in the next section) in order to optimize storage
throughout time, whereas NIPoPoW only uses a single level range. Fourth, since
our end goal is different, our security requirements are different from
NIPoPoWs. Lastly, we note that since our security models are different, we use
vastly different parameters in our protocol compared to NIPoPoW, and also do
novel analysis.

##  4 Trimming Protocol

In this section we describe our protocol to trim the blockchain. Other
associated protocols that compare trimmed-chains to select the main chain, and
that verify the blockchain state are described in Appendix 0.C due to lack of
space.

First, we start with an intuitive description of the trimmed chain which is
best understood by referring to the example in Figure 3. Similar to NIPoPoWs,
the high-level idea in our approach is to retain only a subset of
(super)blocks in order to represent the proof of work of the chain. Let the
trimmed chain be denoted by $\operatorname{\mathcal{P}}_{t}$ (subscript $t$
may be omitted when time is clear from context). $\operatorname{\mathcal{P}}$
is a subset of the complete blockchain $\operatorname{\mathcal{C}}$, i.e.,
$\operatorname{\mathcal{P}}\subseteq\operatorname{\mathcal{C}}$. And, it has
an associated number $B^{\prime}_{t}$ called the _trimming point_. All blocks
to the right of $B^{\prime}_{t}$ are retained, including their data and block
headers. That is,
$\operatorname{\mathcal{P}}\\{B^{\prime}:\\}=\operatorname{\mathcal{C}}[B^{\prime}:]$.
We refer to $\operatorname{\mathcal{P}}\\{B^{\prime}:\\}$ as the _untrimmed
tail_. Blocks to the left of $B^{\prime}$ may be trimmed, meaning
$\operatorname{\mathcal{P}}\\{:B^{\prime}\\}\subseteq\operatorname{\mathcal{C}}[:B^{\prime}]$.
Only the block-headers of the blocks in
$\operatorname{\mathcal{P}}\\{:B^{\prime}\\}$ are retained. The blocks that
are not in $\operatorname{\mathcal{P}}\\{:B^{\prime}\\}$ are permanently
deleted by the hybrid node. Here is where we differ from pruning. In pruning,
all the block headers are retained. In trimming, blocks are completely
deleted, including their headers.

Figure 3: An example of a trimmed chain at an honest node. Notice how it is
partitioned into distinct level ranges, each beginning once its predecessor
ends. We show a portion of the second level range,
$\operatorname{\mathcal{P}}\\{L_{f}(2):L_{l}(2)\\}$. The greyed blocks with
dashed outlines represents blocks that have been trimmed. Like Figure 1, the
height of the (super)block is its highest level. Furthermore, after the
trimming point, $B^{\prime}$, is the untrimmed tail where all the blocks are
retained.

The trimmed section of $\operatorname{\mathcal{P}}$ is further partitioned
into _level-ranges_ , each level-range corresponding to a unique level $\mu$.
A level-range is spread contiguously over a region of the blockchain, and each
level range begins at the point its predecessor ends. We denote the starts and
ends of level ranges by _level-range functions_
$L_{f}:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ and
$L_{l}:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$. We define $L_{f}(\mu)$ as the index
of the first block in level-range $\mu$. Similarly, $L_{l}(\mu)$ is the last
block in the level-range $\mu$. Beyond a certain level $\mu_{h}$, called the
highest level, the level-range functions are 0: $L_{f}(\mu)=L_{l}(\mu)=0$ for
$\mu>\mu_{h}$. Also, below a certain level $\mu<\mu_{l}$, called the lowest
level, we have $L_{f}(\mu)=L_{l}(\mu)=B^{\prime}-1$. Notice then that for
$\mu_{l}\leq\mu<\mu_{h}$, we have $L_{l}(\mu+1)+1=L_{f}(\mu)$. The level
ranges are also pictorially shown in the example in Figure 3.

At level-range $\mu$, we are primarily interested in level-$\mu$ superblocks.
As explained with the intuition of NIPoPoW, we need to weigh level-$\mu$
superblocks by $2^{\mu}$. In order to avoid confusion with PoW, which
traditionally does not look at super-levels, we call this notion of weighted
PoW simply as the _weight_ at level-$\mu$. For the level-range $\mu$, we
denote the weight-function $W(\operatorname{\mathcal{P}},\mu)$ as,

$W(\operatorname{\mathcal{P}},\mu)=2^{\mu}\lvert\operatorname{\mathcal{P}}\\{L_{f}(\mu):L_{l}(\mu)+1\\}\uparrow^{\mu}\rvert.$

Our trimming protocol in Algorithm 1 ensures that a higher level-range
precedes a lower-level range (as illustrated in Figure 3). Therefore, we can
compute the sum of work from the genesis block up to and including level range
$\mu$ by,
$S(\operatorname{\mathcal{P}},\mu)=\sum_{\mu\leq\mu^{\prime}\leq\mu_{h}}W(\operatorname{\mathcal{P}},\mu^{\prime})$.

Since hybrid nodes do not have access to the underlying chain,
$S(\operatorname{\mathcal{P}},\mu)$ can be interpreted as their estimate of
the PoW up to block $L_{l}(\mu)$. Note that
$W(\operatorname{\mathcal{P}},\mu)$ and $S(\operatorname{\mathcal{P}},\mu)$
are functions of the level-range functions as well. However, we assume that
the level-range functions are implicitly defined by
$\operatorname{\mathcal{P}}$ in order to keep the notation minimal.

1

input : $\operatorname{\mathcal{P}}$ :: My (trimmed) chain

$Q$ :: The trimming interval

$\mu_{h}$ :: Highest level-range in $\operatorname{\mathcal{P}}$

$L_{f}(),L_{l}()$ :: Level-Range functions

$g(),f(),\Delta()$ :: Protocol parameter-functions

$\mathsf{good}_{\delta,g}()$ :: Good-Superchain function (see Appendix 0.C)

2

3

4

5

6on event  _$\operatorname{\mathcal{P}}$ has grown by $Q$ blocks since the
last trimming attempt_:

7
$B^{\prime}=\operatorname{\mathcal{P}}[-1]-\Delta(\operatorname{\mathcal{P}})$

8 for  _$\mu$ from $\mu_{h}+1$ down to 1_ do

9 $g\leftarrow g(\operatorname{\mathcal{P}},\mu)$

10 $f\leftarrow f(\operatorname{\mathcal{P}},\mu)$

11 if
_$|\operatorname{\mathcal{P}}\\{L_{f}(\mu):B^{\prime}\\}\uparrow^{\mu}|\geq f$
and
$\mathtt{good}_{\delta,g}(\operatorname{\mathcal{P}}\\{L_{f}(\mu):B^{\prime}\\}\uparrow^{\mu},\mu)$_
then

12
$\operatorname{\mathcal{P}},L_{f},L_{l},\text{success}\leftarrow$trim(_$\operatorname{\mathcal{P}}$
, $L_{f}$, $L_{l}$, $B^{\prime}$, $\mu$, $g$, $f$_)

13 if  _success =1_ then

14 break

15

16

17

18 return

19

20

21

22 func  _trim(_$\operatorname{\mathcal{D}}$ , $L_{f}$, $L_{l}$, $B^{\prime}$,
$\mu$, g, f_)_:

23
$\operatorname{\mathcal{E}}\leftarrow\operatorname{\mathcal{D}}\\{L_{f}(\mu):B^{\prime}\\}\uparrow^{\mu}$

24 $A\leftarrow\operatorname{\mathcal{E}}[-f]$

25

26 for  _$\mu^{\prime}$ from $\mu-1$ to $0$_ do

27
$\alpha\leftarrow\operatorname{\mathcal{D}}\\{A:B^{\prime}\\}\uparrow^{\mu^{\prime}}$

28 $\operatorname{\mathcal{E}}\leftarrow\operatorname{\mathcal{E}}\cup\alpha$

29

30 if  _$\lvert\alpha\rvert\geq f$ and
$\mathsf{good}_{\delta,g}(\alpha,\mu^{\prime})$_ then

31 $A\leftarrow\alpha[-f]$

32

33

34

35 if  _$\lvert\alpha\rvert\geq f$ and
$\mathsf{good}_{\delta,g}(\alpha,\mu^{\prime})$_ then

36 $L_{f}(\mu^{\prime}),L_{l}(\mu^{\prime})\leftarrow B^{\prime}-1$, for all
$\mu<\mu^{\prime}$

37 $L_{l}(\mu)\leftarrow B^{\prime}-1$

38
$\operatorname{\mathcal{D}}\leftarrow\operatorname{\mathcal{D}}\\{:L_{f}(\mu)\\}\cup\operatorname{\mathcal{E}}\cup\operatorname{\mathcal{D}}\\{B^{\prime}:\\}$

39 return $\operatorname{\mathcal{D}},L_{f},L_{l},1$

40

41 else

42 return $\operatorname{\mathcal{D}},L_{f},L_{l},0$

43

44

Algorithm 1 Trimming Protocol

The trimming procedure is detailed in Algorithm 1. We briefly describe it
here. Trimming is attempted every time the chain grows by $Q$ blocks (line 1).
We call $Q$ the trimming interval. The trimming point is set by the required
chain-tail length (line 2). Given that $\mu_{h}$ is the highest level-range in
the current trimmed chain, we attempt to trim it further to level $\mu_{h}+1$.
If trimming to that level is not possible, we try to do it to one level lower
and so on (line 3). Trimming to a level $\mu$ can be attempted if the
specified range of blocks contains enough level-$\mu$ superblocks, and if the
corresponding $\mu$-upchain is good (line 6). Roughly, a $\mu$-upchain
$\operatorname{\mathcal{C}}\uparrow^{\mu}$ is good if its weight represents
the weight of the other level upchains (
$|\operatorname{\mathcal{C}}\uparrow^{\mu}|\approx
2^{(\mu-\mu^{\prime})}|\operatorname{\mathcal{C}}\uparrow^{\mu^{\prime}}|$,
$\mu^{\prime}<\mu$). For the full definition of _good-superchain_ , see
Appendix 0.C. Given condition on line 6 is satisfied, the $\mathsf{trim}$
function is called for level $\mu$ (line 7).

The $\mathsf{trim}$ function is very similar to the goodness-aware
$\mathsf{Prove}$ algorithm of the NIPoPoW protocol [25, Algorithm 8]. In the
$\mathsf{trim}$ function, the $\mu$-upchain is obtained first (line 13). Next,
the $(\mu-1)$-level upchain under the last $f$ blocks of the $\mu$-level
upchain is also added (lines 17 and 18). If the $(\mu-1)$-level upchain is
good, then the $(\mu-2)$-level upchain under its last $f$ blocks is added
(lines 20 and 21). Otherwise, the $(\mu-2)$-level upchain under the last $f$
blocks of the $\mu$-upchain are added. This procedure continues until level
$0$.

At the end, the $\mathsf{trim}$ function checks if the trimming was a
“success” by checking if level 0 of the trimmed chain is good. The trim being
a success means that it is at least as hard for an adversary to create a
longer fork around the trimmed chain, as it would be to do so around the
complete chain. Intuitively, this is because the necessary levels of the
upchains in this range are good, meaning that they represent the PoW of their
corresponding downchains.

In case the trim is a success, the trim function along with the new level
range functions are returned (lines 23 to 27) indicating that the trim can be
used. Otherwise, the old trimmed chain and level range functions are returned
(lines 28 and 29).

#### Chain Selection

Hybrid nodes need to have a protocol,
$\mathsf{Compare}(\operatorname{\mathcal{C}}^{(1)},\operatorname{\mathcal{C}}^{(2)})$,
to chose the main chain given two conflicting chains,
$\operatorname{\mathcal{C}}^{(1)}$ and $\operatorname{\mathcal{C}}^{(2)}$.
Full nodes (that store the entire blockchain) simply choose the longer of the
two chains as the main chain. The chain selection protocol for hybrid nodes is
a little more complicated since they do not store the entire chain. At a high
level, they use the sum of the cumulative weight,
$S(\operatorname{\mathcal{P}},0)$, of the trimmed portion of a chain and the
length of untrimmed section of the chain as a proxy for the chain length. The
complete algorithm involves some more details which are described in full in
Appendix 0.C.2.

#### State Verification

Similar to CoinPrune [28], a short commitment to the state at the block is
stored in every block. Therefore, a hybrid node can verify the correctness of
the blockchain’s state by comparing it to the corresponding state commitment.
The protocol is called $\mathsf{state-verify}$ and is presented with more
details in Appendix 0.C.3.

#### Hybrid Node’s Functionalities

Here, we describe how a hybrid-node employing the trimming algorithm has the
functionalities claimed in Section 1. Since a hybrid node stores the state of
the blockchain at its tip, it can perform transaction validation, block
validation and state validation. Using the $\mathsf{Compare}(\cdot,\cdot)$
protocol from Appendix 0.C.2, a hybrid node can select the main chain given
competing chains. As a consequence, the node can perform mining as well.

A new node joining the system can choose the main chain using the
$\mathsf{Compare}(\cdot,\cdot)$ protocol, and verify the state using the
$\mathsf{state\mathchar 45\relax verify}$ protocol from Appendix 0.C.3. Thus,
hybrid nodes can bootstrap other hybrid nodes into the system.

The hybrid node verifies payment proofs as follows. In traditional systems
like Bitcoin, the prover provides the chain of block-headers in order to
establish the PoW, and then provides a short proof for the transaction’s
inclusion (inclusion-proof) in the chain. In NIPoPoWs the prover provides a
superchain (which is logarithmic in the size of the underlying chain) in order
to establish the PoW. In either case, the hybrid node can use the
$\mathsf{Compare}(\cdot,\cdot)$ protocol to compare the given chain
(superchain) to its own trimmed chain. If the two chains only differ near the
tail and the inclusion-proof is consistent with the provided chain, then the
hybrid node approves the prover’s payment proof. Otherwise, it returns false.

##  5 Security Definitions

#### Security from Trim Attack

Consider the dangerous attack scenario depicted in Figure 4, where the
adversary provides a trimmed-chain $\operatorname{\mathcal{P}}^{(2)}$ which is
“longer” than the honest chain $\operatorname{\mathcal{P}}^{(1)}$ (i.e.
$\mathsf{Compare}(\operatorname{\mathcal{P}}^{(1)},\operatorname{\mathcal{P}}^{(2)})=\operatorname{\mathcal{P}}^{(2)}$)
and the LCA between the two chains precedes the honest chain’s trimming point:
$b=\mathsf{LCA}(\operatorname{\mathcal{P}}^{(1)},\operatorname{\mathcal{P}}^{(2)})<{B^{\prime}}^{(1)}$.
Denote $b_{1}$ to be the (super)block after $b$ in
$\operatorname{\mathcal{P}}^{(2)}$. The honest node cannot verify the state
transition from $b$ to $b_{1}$. This is because the honest node only has
access to block headers and not the full state, meaning they can only verify
the validity of the block headers, but not of the state transition between the
blocks. Moreover, even if the honest node had access to the state at those
blocks, there may be a number of blocks between $b$ and $b_{1}$ that were
skipped during the trimming.

Figure 4: A trim-attack. The honest chain is shown in black, and adversary’s
chain in red. Complete square-boxes indicate the complete blocks beyond the
trimming point, and incomplete boxes indicate block-headers of blocks before
the trimming point. Curved arrows indicate that the corresponding blocks may
not be subsequent blocks.

Therefore, if at any time the adversary is able to create a fork as in Figure
4, they could arbitrarily alter the state of the chain to their advantage. For
instance, the adversary could transfer all of the chain’s cryptocurrency into
their own accounts. One approach to circumventing this problem is to have the
hybrid node re-download the blockchain from a full node in case it encounters
a fork preceding its trimming point. However, in that case the security of the
system would again rely on the small number of full nodes. We require that
hybrid nodes can work independently from full nodes to keep the system as
decentralized as possible. To accomplish this, we ensure that there exists no
time when an adversary is able to create a fork from beyond a hybrid node’s
trimming point.

######  Definition 1 (Attack on the trimmed Chain)

Let $\omega$ be the fixed randomness111randomness is w.r.t., the stochastic
model described in Appendix 0.B. Let
$\operatorname{\mathcal{P}}^{(1)}_{t,\omega}$ be the honest trimmed chain at
some honest node at time $t$. Let
$\operatorname{\mathcal{P}}^{(2)}_{t,\omega}$ be the adversary’s trimmed
chain. Let $B^{\prime}(\operatorname{\mathcal{P}}^{(1)})$ and
$B^{\prime}(\operatorname{\mathcal{P}}^{(2)})$ be their respective trimming
points. Let $b_{t,\omega}$ be the LCA block between them:
$b_{t,\omega}=\mathsf{LCA}(\operatorname{\mathcal{P}}^{(1)}_{t,\omega},\operatorname{\mathcal{P}}^{(2)}_{t,\omega})$.
Then, we say that the system is $\mathsf{trim\mathchar 45\relax attacked}$ if
there exists a time $t$ such that the adversarial trimmed chain is declared to
be longer than the honest trimmed chain and the LCA block is before the honest
node’s trimming point. That is,

$\displaystyle\mathsf{trim\mathchar 45\relax attacked}=\\{\omega:$
$\displaystyle\exists t\text{ s.t.
}b_{t,\omega}<B^{\prime}(\operatorname{\mathcal{P}}^{(1)}_{t,\omega}),\text{
and
}\mathsf{Compare}(\operatorname{\mathcal{P}}^{(1)}_{t,\omega},\operatorname{\mathcal{P}}^{(2)}_{t,\omega})=\operatorname{\mathcal{P}}^{(2)}_{t,\omega}\\}.$

#### Congruence

Since hybrid nodes only have access to trimmed chains
$\operatorname{\mathcal{P}}$, we need that the selection of the main trimmed-
chain made according to $\mathsf{Compare}(\cdot,\cdot)$ is in agreement with
the underlying complete chains. We formalize this by a property called
_congruence_.

######  Definition 2 (Congruence)

Given any two (complete) chains $\operatorname{\mathcal{C}}^{(1)}$ and
$\operatorname{\mathcal{C}}^{(2)}$ with corresponding trimmed chains
$\operatorname{\mathcal{P}}^{(1)}$ and $\operatorname{\mathcal{P}}^{(2)}$,
they are said to be congruent with each other if,
$\lvert\operatorname{\mathcal{C}}^{(1)}\rvert>\lvert\operatorname{\mathcal{C}}^{(2)}\rvert\implies\mathsf{Compare}\left(\operatorname{\mathcal{P}}^{(1)},\operatorname{\mathcal{P}}^{(2)}\right)=\operatorname{\mathcal{P}}^{(1)}.$

#### State Security

Hybrid nodes do not have access to transaction history preceding their
trimming point. Instead, they rely on the state at the trimming point,
$\mathsf{state}(B^{\prime}_{t})$, to compute state at the tip of the chain.
State is verified using $\mathsf{state\mathchar 45\relax verify}$ (Algorithm
3). Firstly, if the adversary launches a trimming attack (Definition 1), then
they could change the state of the blockchain arbitrarily. Additionally, the
state of the hybrid node is also attacked if at any point the adversary can
create a different state, $\mathsf{state}^{\prime}$, that also passes through
$\mathsf{state\mathchar 45\relax verify}$.

######  Definition 3 (Attack on the State)

Let $\omega$ be the fixed randomness. At some time $t$, let the trimming point
of an honest chain $\operatorname{\mathcal{P}}^{(1)}_{t,\omega}$ be
${B^{\prime}}^{(1)}_{t,\omega}$, and let its associated state be
$\operatorname{\mathsf{state}}^{(1)}({B^{\prime}}^{(1)}_{t,\omega})$. Let the
trimming point of the adversary’s chain
$\operatorname{\mathcal{P}}^{(2)}_{t,\omega}$ be
${B^{\prime}}^{(2)}_{t,\omega}$, and let its claimed state be
$\operatorname{\mathsf{state}}^{(2)}_{t,\omega}$ The state of the honest node
is said to be attacked, denoted by $\mathsf{state\mathchar 45\relax attacked}$
, if there is either a trim-attack or there exists a time $t$ such that,
$\operatorname{\mathsf{state}}^{(2)}_{t,\omega}\neq\operatorname{\mathsf{state}}^{(1)}(B^{\prime}_{t,\omega})$,
such that it verifies against the chain. Denoting,
$\operatorname{\mathcal{P}}_{t,\omega}=\mathsf{Compare}(\operatorname{\mathcal{P}}^{(1)}_{t,\omega},\operatorname{\mathcal{P}}^{(2)}_{t,\omega})$,
we define,

$\displaystyle\mathsf{state\mathchar 45\relax attacked}=\\{\omega:\omega\in$
$\displaystyle\mathsf{trim\mathchar 45\relax attacked}\\}$
$\displaystyle\bigcup\\{\omega:\exists t\text{ such that
}\mathsf{state\mathchar 45\relax
verify}(\operatorname{\mathsf{state}}^{(2)}_{t,\omega},\operatorname{\mathcal{P}}_{t,\omega})=1\\}.$

#### Bootstrapping Security

When a new (honest) node joins the system, it downloads (possibly trimmed)
copies of the blockchain from a number of other hybrid or full nodes. It then
chooses the main chain using the $\mathsf{Compare}(\cdot,\cdot)$ protocol and
then downloads and verifies the state using the $\mathsf{state\mathchar
45\relax verify}$ protocol. In order to show that it adopts the honest trimmed
chain and the honest state, we define bootstrapping security below.

######  Definition 4 (Bootstrapping Security)

A joining node is said to be securely bootstrapped into the system if, at the
point of it joining, it adopts a trimmed chain that is not
$\mathsf{trim\mathchar 45\relax attacked}$ with respect to the system’s honest
chain, and it adopts a state which is not $\mathsf{state\mathchar 45\relax
attacked}$ with respect to the system’s honest state. Otherwise, the node is
said to be $\mathsf{bootstrap\mathchar 45\relax attacked}$.

In our system model, we assume that the mining rate of the honest parties and
the adversary remains constant. This might seem to be counter-factual to
Definition 4 because it assumes that nodes can join the system. We remark that
we make the constant mining rate assumption to make the rigorous security
analysis tractable. Practically, we conjecture that if the rate of nodes
joining and leaving the system is nearly equal and small enough, then the
constant mining rate assumption is a good model for the system.

##  6 Security Results for Hybrid Nodes

The protocol has security parameters $k,k^{\prime}\in\mathbb{N}$,
$a,c\in\mathbb{R}^{+}$, and $\delta\in(0,1)$. Referring to the protocol
parameter-functions from Alogrithm 1 are defined as:
$\Delta(\operatorname{\mathcal{P}})=k^{\prime}+a\log\left(S(\operatorname{\mathcal{P}},0)+\lvert\operatorname{\mathcal{P}}\\{B^{\prime}:\\}\rvert\right)$,
$g(\operatorname{\mathcal{P}},\mu)=k+a\log S(\operatorname{\mathcal{P}},\mu)$,
and $f(\operatorname{\mathcal{P}},\mu)=c\cdot
g(\operatorname{\mathcal{P}},\mu)$. We simply state the results here without
proof. The proofs can be found in Appendix 0.E. All the results are with
respect to the stochastic model defined in Appendix 0.B.

First, we show if the honest nodes have the majority of mining power, we can
choose security parameters such that our protocol is secure against a trim-
attack.

######  Theorem 6.1 (Security of the trimmed Chain)

Assume an honest majority, $\lambda_{h}>\lambda_{a}$, where $\lambda_{h}$ and
$\lambda_{a}$ are the mining rates of the honest and adversarial nodes
respectively. Let the trimming algorithm (Algorithm 1) parameters
$k,k^{\prime},c,a,\delta$ satisfy,

$\begin{split}k^{\prime}&=k-a\log\left(((1+\delta^{2})+\delta)/\delta\right),\quad
1<(1-\delta)^{3}\frac{\lambda_{h}}{\lambda_{a}}\frac{c^{\prime}-1}{c^{\prime}}\frac{c-1-c^{\prime}}{c},\\\
1&<(1-\delta)^{5}\frac{\lambda_{h}}{\lambda_{a}}\frac{c-1}{c},\quad
a\geq\frac{8}{\delta^{2}},\end{split}$

where $2<c^{\prime}<c$ is some constant. Then222In our work,
$\operatorname{\mathsf{negl}}(k)=e^{-\Omega(k)}<\frac{1}{\mathsf{poly}(k)}$.,
$\mathbb{P}(\mathsf{trim\mathchar 45\relax
attacked})=\operatorname{\mathsf{negl}}(k).$

As a corollary to the above theorem, we can conclude the chain-selection made
by hybrid-nodes is consistent with underlying chain lengths.

###### Corollary 1

The congruence property holds except with probability
$\operatorname{\mathsf{negl}}(k)$.

######  Theorem 6.2 (State Security)

Assuming honest majority, $\lambda_{h}>\lambda_{a}$, and that the security
parameters are as in Theorem 2, then,
$\operatorname{\mathbb{P}}(\mathsf{state\mathchar 45\relax
attacked})=\operatorname{\mathsf{negl}}(k)$.

######  Corollary 2 (Bootstrapping Security)

Assume the arrival process of new nodes is independent of the randomness of
the blockchain system. If we further assume that a new node contacts at least
one honest node and that there is honest mining majority, then
$\mathsf{bootstrap\mathchar 45\relax attacked}$ occurs with probability
$\operatorname{\mathsf{negl}}(k)$.

In the next theorem, we provide an upper bound on the cold-storage required to
store the trimmed chain. This theorem relies on the assumption that a
particular kind of adversary is absent. We further comment on this in Remark
1. Additionally, we also note that the following theorem doesn’t account for
the storage required to store the state at the trimming point. We discuss
optimizing the storage for the state using stateless blockchains in Section 7.

######  Theorem 6.3 (Optimistic Succinctness)

Assuming that all the nodes are honest, the cold-storage requirements for a
hybrid node to store the trimmed-chain $\operatorname{\mathcal{P}}$ is
$O(\log^{4}B)$ with high probability in $k$. Here, $B$ is the length of the
underlying chain $\operatorname{\mathcal{C}}$.

######  Remark 1 (Need of Optimism for Succinctness)

Since our protocol is an extension of NIPoPoWs, we need to rely on optimism
for succinctness as well. In particular, note that when trimming we need to
ensure that the level ranges are “good”. We have also shown that under honest
behaviour, the sizes of the different upchains concentrate around the mean,
thus leading to good level-ranges with high probability. However, an adversary
with a small mining power could launch an attack which hampers the
concentrations around the means and thus makes good-superchains more unlikely.
This attack is formally described in [25]. We note that, just like in
NIPoPoWs, the adversary can only hurt the succinctness of our model, but not
its security. Although the economics of launching an attack on the hybrid
node’s succinctness is yet to be studied formally, we venture to guess that
such an attack wouldn’t be economically viable to the adversary.

Clearly, the size of the untrimmed tail is a lower bound on the cold-storage
required. In the next theorem we prove that the length of the chain tail has
to be at least $\log B$ in order to protect a hybrid node against a
$\mathsf{trim\mathchar 45\relax attack}$. This implies that our protocol is
near-optimal in terms of cold storage, since it only requires $polylog(B)$
storage.

######  Theorem 6.4 (Vulnerability of Short Tails)

Let the blockchain length be $B_{t}$ at time $t$, and the trimming point be
$B^{\prime}_{t}$. If at all times $t$,
$\operatorname{\mathbb{P}}\left(B_{t}-B^{\prime}_{t}=o(\log
B_{t})\right)>\epsilon$, for some $\epsilon>0$, then there exists an adversary
with small mining power, $\lambda_{a}<\lambda_{h}$, such that
$\operatorname{\mathbb{P}}(\mathsf{trim\mathchar 45\relax attacked})=1$.

##  7 Optimizing State Storage with Stateless Blockchains

Our trimming protocol optimizes the amount of cold storage required to
represent the PoW in the blockchain. In this section, we outline how our work
can interface with methods optimizing the storage of the _state_. Furthermore,
a detailed description is found in App. 0.J. In hybrid nodes, states need to
be stored in cold and hot storage. Along with the length of the blockchain,
the size of the blockchain-state is rapidly increasing with time. For
instance, at the time of writing Bitcoin’s UTXO state is almost 4GB in size,
which motivates lessening high storage and verification time by extending our
work to optimize both the state’s cold-storage at the trimming point, and its
hot-storage at the chain tip.

We described that storing state-commitments in the blocks enables one to
securely establish the state of a trimmed chain, by use of the
$\mathsf{state\mathchar 45\relax verify}$ protocol described in Algorithm 3.
In a different line of work, called _stateless blockchains_ , state-
commitments are used to reduce the amount of hot-storage required for
transaction validation, thus speeding up validation. We claim that when hybrid
nodes are used in stateless-blockchains, then state commitments can serve a
dual purpose: 1) they can be used to establish the state of the trimmed chain;
2) and, they can be used to perform stateless transaction validation.

Stateless validation, first proposed by Todd [38], is a scheme where nodes
validating transactions store a short cryptographic state-commitment rather
than the entire state. A client then provides a membership proof that the node
can verify against the commitment. Recently, several constructions have been
developed to perform stateless validation in both the UTXO and account-based
state models using various cryptographic primitives [10, 13, 4, 39, 34, 1,
19].

Stateless blockchains optimize hot-storage by obviating the need to store the
state at the tip of the chain in the RAM. At this point, the state at the
trimming point is still stored in the cold storage. We can use this to provide
an interface from trimming to stateless blockchains: First, if the proof for
some client becomes outdated past the trimming point because it was offline
for a long time, then the client can recompute its latest proof by querying a
hybrid node for $\operatorname{\mathsf{state}}(B^{\prime}_{t})$ and the
untrimmed chain tail. Second, if a fork in the chain makes the proofs of
several clients invalid, they can all recompute their proofs by contacting the
hybrid node similarly. In App. 0.J, we describe a way to optimize the cold-
storage of the state at the trimming point as well.

##  8 Future Directions

In this paper, we presented hybrid nodes which use trimming to optimize the
cold-storage required to represent the PoW in the chain. When used in
conjunction with stateless blockchains, we illustrated that hybrid nodes are
optimized both in terms of cold and hot storage. In this section, we lay out
some directions for future work.

We assume that there is honest majority, $\lambda_{h}>\lambda_{a}$, throughout
the execution of the blockchain protocol. Given that we use novel security
models, it will be interesting to study if it is economically viable for an
adversary to acquire massive resources in order to attain a majority mining
power temporarily, and launch an attack such as a $\mathsf{trim-attack}$.
Similarly, it will be interesting to study the economics of an adversary who
simply attempts to hurt the succinctness of hybrid nodes. In hurting the
succinctness, fewer nodes would join as hybrid nodes. Thus, an adversary could
attempt to take advantage of the reduced decentralization.

We have proved in Theorem 6.4, that our protocol is near-optimal in terms of
the storage it requires to represent a blockchain’s PoW if it is to be secure
against a $\mathsf{trim-attack}$. However, it is at the moment unclear if
further storage optimization in terms of storing the state is possible for a
node that needs to have all the functionalities of a hybrid node (without
assuming properties on the clients as we do in Section 7).

In our analysis, we assume that the block $\mathtt{id}$’s have a constant
difficulty target throughout the blockchain’s execution. It may be useful to
relax this assumption in order to make our model closer to practical systems.

Finally, our work in this paper has mainly focused on theoretical analysis. An
interesting line of work would be to implement the protocol and study the
practical gains of using hybrid nodes.

## References

  * [1] Shashank Agrawal and Srinivasan Raghuraman  “KVaC: Key-Value Commitments for Blockchains and Beyond”  In _International Conference on the Theory and Application of Cryptology and Information Security_ , 2020, pp. 839–869  Springer
  * [2] “Bitcoin Hash Rate”, Available at https://www.coinwarz.com/mining/bitcoin/hashrate-chart (2021/04/29)
  * [3] “Bitcoin UTXO size”, Available at https://tinyurl.com/cr7w2ep5 (2021/09/13)
  * [4] Dan Boneh, Benedikt Bünz and Ben Fisch  “Batching techniques for accumulators with applications to iops and stateless blockchains”  In _Annual International Cryptology Conference_ , 2019, pp. 561–586  Springer
  * [5] Joseph Bonneau, Izaak Meckler, Vanishree Rao and Evan Shapiro  “Coda: Decentralized Cryptocurrency at Scale.”  In _IACR Cryptol. ePrint Arch._ 2020, 2020, pp. 352
  * [6] Benedikt Bünz, Lucianna Kiffer, Loi Luu and Mahdi Zamani  “Flyclient: Super-light clients for cryptocurrencies”  In _2020 IEEE Symposium on Security and Privacy (SP)_ , 2020, pp. 928–946  IEEE
  * [7] Clément Canonne  “A Short Note on Poisson Tail Bounds”, Available at http://www.cs.columbia.edu/~ccanonne/files/misc/2017-poissonconcentration.pdf (2021/05/18)
  * [8] Dario Catalano and Dario Fiore  “Vector commitments and their applications”  In _International Workshop on Public Key Cryptography_ , 2013, pp. 55–72  Springer
  * [9] Weikeng Chen, Alessandro Chiesa, Emma Dauterman and Nicholas P Ward  “Reducing Participation Costs via Incremental Verification for Ledger Systems”, 2020
  * [10] Alexander Chepurnoy, Charalampos Papamanthou and Yupeng Zhang  “Edrax: A Cryptocurrency with Stateless Transaction Validation.”  In _IACR Cryptol. ePrint Arch._ 2018, 2018, pp. 968
  * [11] Stelios Daveas, Kostis Karantias, Aggelos Kiayias and Dionysis Zindros  “A Gas-Efficient Superlight Bitcoin Client in Solidity”  In _Proceedings of the 2nd ACM Conference on Advances in Financial Technologies_ , AFT ’20  New York, NY, USA: Association for Computing Machinery, 2020, pp. 132–144  DOI: 10.1145/3419614.3423255
  * [12] Amir Dembo et al.  “Everything is a race and nakamoto always wins”  In _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 859–878
  * [13] Thaddeus Dryja  “Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set.”  In _IACR Cryptol. ePrint Arch._ 2019, 2019, pp. 611
  * [14] D Dubhashi and Alessandro Panconesi  “Concentration of measure for the analysis of randomised algorithms”  In _Draft Manuscript, http://www. brics. dk/ale/papers. html_ , 1998
  * [15] “Ethereum Hash Rate”, Available at https://www.coinwarz.com/mining/ethereum/hashrate-chart (2021/04/29)
  * [16] Ittay Eyal and Emin Gün Sirer  “Majority is not enough: Bitcoin mining is vulnerable”  In _International conference on financial cryptography and data security_ , 2014, pp. 436–454  Springer
  * [17] Juan Garay, Aggelos Kiayias and Nikos Leonardos  “The bitcoin backbone protocol: Analysis and applications”  In _Annual international conference on the theory and applications of cryptographic techniques_ , 2015, pp. 281–310  Springer
  * [18] Peter Gaži, Aggelos Kiayias and Alexander Russell  “Tight consistency bounds for bitcoin”  In _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 819–838
  * [19] Sergey Gorbunov, Leonid Reyzin, Hoeteck Wee and Zhenfei Zhang  “Pointproofs: aggregating proofs for multiple vector commitments”  In _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 2007–2023
  * [20] Swanand Kadhe, Jichan Chung and Kannan Ramchandran  “SeF: A Secure Fountain Architecture for Slashing Storage Costs in Blockchains”  In _CoRR_ abs/1906.12140, 2019  arXiv: http://arxiv.org/abs/1906.12140
  * [21] Kostis Karantias, Aggelos Kiayias and Dionysis Zindros  “Compact storage of superblocks for nipopow applications”  In _Mathematical Research for Blockchain Economy_ Springer, 2020, pp. 77–91
  * [22] Assimakis Kattis and Joseph Bonneau  “Proof of Necessary Work: Succinct State Verification with Fairness Guarantees.”  In _IACR Cryptol. ePrint Arch._ 2020, 2020, pp. 190
  * [23] Aggelos Kiayias, Nikolaos Lamprou and Aikaterini-Panagiota Stouka  “Proofs of proofs of work with sublinear complexity”  In _International Conference on Financial Cryptography and Data Security_ , 2016, pp. 61–78  Springer
  * [24] Aggelos Kiayias, Nikos Leonardos and Dionysis Zindros  “Mining in Logarithmic Space” https://ia.cr/2021/623, Cryptology ePrint Archive, Report 2021/623, 2021
  * [25] Aggelos Kiayias, Andrew Miller and Dionysis Zindros  “Non-interactive proofs of proof-of-work”  In _International Conference on Financial Cryptography and Data Security_ , 2020, pp. 505–522  Springer
  * [26] Aggelos Kiayias, Andrianna Polydouri and Dionysis Zindros  “The Velvet Path to Superlight Blockchain Clients”, 2020
  * [27] Songze Li et al.  “PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously”  In _Trans. Info. For. Sec._ 16 IEEE Press, 2021, pp. 249–261  DOI: 10.1109/TIFS.2020.3009610
  * [28] Roman Matzutt et al.  “How to Securely Prune Bitcoin’s Blockchain”  In _2020 IFIP Networking Conference (Networking)_ , 2020, pp. 298–306  IEEE
  * [29] “Nodes and Clients”, Available at https://ethereum.org/en/developers/docs/nodes-and-clients/ (2021/05/20)
  * [30] Rafael Pass, Lior Seeman and Abhi Shelat  “Analysis of the blockchain protocol in asynchronous networks”  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , 2017, pp. 643–673  Springer
  * [31] D. Perard, J. Lacan, Y. Bachy and J. Detchart  “Erasure Code-Based Low Storage Blockchain Node”  In _2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)_ , 2018, pp. 1622–1627  DOI: 10.1109/Cybermatics˙2018.2018.00271
  * [32] Ravi Kiran Raman and Lav R. Varshney  “Dynamic Distributed Storage for Scaling Blockchains”  In _CoRR_ abs/1711.07617, 2017  arXiv: http://arxiv.org/abs/1711.07617
  * [33] B Swaroopa Reddy  “securePrune: Secure block pruning in UTXO based blockchains using Accumulators”  In _2021 International Conference on COMmunication Systems & NETworkS (COMSNETS)_, 2021, pp. 174–178  IEEE
  * [34] Leonid Reyzin, Dmitry Meshkov, Alexander Chepurnoy and Sasha Ivanov  “Improving authenticated dynamic dictionaries, with applications to cryptocurrencies”  In _International Conference on Financial Cryptography and Data Security_ , 2017, pp. 376–392  Springer
  * [35] “Running a Full Node”, Available at https://bitcoin.org/en/full-node (2021/05/20)
  * [36] Suryanarayana Sankagiri, Shreyas Gandlur and Bruce Hajek  “The Longest-Chain Protocol Under Random Delays”  In _arXiv preprint arXiv:2102.00973_ , 2021
  * [37] Yonatan Sompolinsky and Aviv Zohar  “Bitcoin’s security model revisited”  In _arXiv preprint arXiv:1605.09193_ , 2016
  * [38] Peter Todd  “Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments”, Available at https://petertodd.org/2016/delayed-txo-commitments (2021/05/24)
  * [39] Alin Tomescu et al.  “Aggregatable subvector commitments for stateless cryptocurrencies”  In _International Conference on Security and Cryptography for Networks_ , 2020, pp. 45–64  Springer
  * [40] Paul Valiant  “Incrementally verifiable computation or proofs of knowledge imply time/space efficiency”  In _Theory of Cryptography Conference_ , 2008, pp. 1–18  Springer

##  Appendix 0.A Other Related Works

##### Coding Based Storage Reduction

Several recent works have employed erasure-codes to reduce cold storage costs
in blockchains [31, 27, 20, 32]. The core idea in these works is that each
node stores a coded version of a random subset of the blockchain. A new
joining node can then download the coded fragments from several nodes and
reconstruct the entire blockchain. Although this does lead to a significant
reduction in storage requirements, the storage in these methods has an
information theoretic lower bound of $\Omega(B/N)$, where $B$ is the length of
the blockchain and $N$ is the number of nodes [27]. In our proposed method,
the cold storage cost scales _poly-logarithmically_ in the length of the
blockchain.

##### Incrementally Verifiable Computation

Incrementally verifiable computation (IVC) is an orthogonal approach,
initially proposed for general settings by Valiant [40]. IVC’s provide a
succinct argument of knowledge that some state is correctly computed from the
initial state of computation (and all preceding states of computation) by
performing a recursive composition of state transitions. In the context of
blockchains, [22, 5, 9] employ IVC to reduce state verification time. For the
sake of comparison, we note that these methods are based on generic
techniques, like applying a Succinct Non-interactive ARgument of Knowledge
(SNARK) on a suitable compliance predicate and recursively composing such
SNARKs, which result in concretely high overhead costs for the prover.
Furthermore, in [22], which is most directly related to our work amongst the
three, the authors acknowledge that their approach does not lessen storage
requirements of mining nodes. In contrast, the hybrid nodes which have mining
capability and more.

##### Lightweight Clients with Sublinear Complexity

Recall lightweight clients only seek to verify payment proofs. Apart from
NIPoPoW, another popular method that has sublinear complexity for lightweight
clients is _FlyClient_ [6]. It uses probabilistic block sampling and a novel
commitment scheme called merkle-mountain-ranges. FlyClient is more versatile
that NIPoPoW’s in that it doesn’t require optimism for succinctness, and it
allows for varying block difficulties. Unfortunately, at the moment, we don’t
believe the FlyClient protocol can be used for hybrid nodes. In addition to
theoretical works, there have been recent works that have also studied
practical aspects of NIPoPoW and FlyClient [21, 11, 26].

##  Appendix 0.B Additional Model Details

###  0.B.1 Communication Model

Several communication models are considered in the literature. The simplest is
the _synchronous_ model where a block broadcast by a node at a certain time is
received by all other nodes immediately [17, 16]. Since time is continuous, no
more than one block is mined at any given time, implying only one block could
be in communication at any given time. More complicated communication models
with communication delays are also considered in the literature [30, 36]. For
the sake of simplicity, we consider the synchronous model in this paper and
leave it to future work to transfer our results to more complicated
communication models.

###  0.B.2 Additional Notation

We define the notion of a _downchain_ slightly different from [23]. Let
$\operatorname{\mathcal{C}}^{\prime}\subseteq\operatorname{\mathcal{C}}\uparrow^{\mu}$
be a level-$\mu$ superchain. Let
$\operatorname{\mathcal{C}}^{\prime}[0]=\operatorname{\mathcal{C}}\uparrow^{\mu}[j]$.
Then, the corresponding downchain is defined as,

$\operatorname{\mathcal{C}}^{\prime}\downarrow\triangleq\begin{cases}\operatorname{\mathcal{C}}[\operatorname{\mathcal{C}}\uparrow^{\mu}[j-1]+1:\operatorname{\mathcal{C}}^{\prime}[-1]],&\text{if
$j>0$},\\\
\operatorname{\mathcal{C}}[:\operatorname{\mathcal{C}}^{\prime}[-1]],&\text{if
$j=0$}.\end{cases}$ (2)

###  0.B.3 Stochastic Model for the Blockchain.

In order to study the behavior of the blockchain, we consider a stochastic
model for the blockchain which has been used previously in the literature to
study blockchain security [12, 18, 37]. The stochastic model allows us to
abstract away the cryptographic details of PoW mining and focus specifically
on the dynamics of the blockchain growth. In particular, we model PoW mining
as calls to an ideal random functionality. At each query, independent of
everything else, the ideal functionality returns “success” with a small
probability $p$ and “failure” otherwise. After describing our protocol and its
analysis, we interpret our results under popular cryptographic models such as
the model used by Pass., et al [30] and the Bitcoin Backbone Model [23] in
Section 0.I.

Since we use a continuous time model, we represent mining as a Poisson process
as has been used in previous works [18, 12]. Let $\Omega$ be the sample-space,
and let $\omega\in\Omega$ denote an outcome (also called fixed randomness).
Let the overall mining process of honest nodes be a Poisson process of rate
$\lambda_{h}$ and let the adversary’s mining be a Poisson process of rate
$\lambda_{a}$. The honest and adversarial processes are independent of each
other. Honest blocks add their mined blocks to the tip of their longest chains
and immediately broadcast the block. However, the adversary could add their
mined block at any point on the chain. Moreover, the adversary may choose to
keep their mined blocks secret and broadcast them at any future time of their
choice. Once a block is broadcast, all the honest nodes receive it
immediately. Honest nodes are said to have a _majority_ if
$\lambda_{h}>\lambda_{a}$.

Observe that a level-$\mu$ superblock is $2^{\mu}$ times harder to find than a
regular block. In other words, a regular block is a level-$\mu$ superblock
with probability $2^{-\mu}$. Therefore, the arrival process for honest
(adversarial) level-$\mu$ superblocks is a Poisson process of rate
$\lambda_{h}/2^{\mu}$ ( $\lambda_{a}/2^{\mu}$). Here as well, the honest and
adversarial arrival processes are independent of each other. However, we note
that the arrival processes for honest (adversarial) level-$\mu_{1}$ and
level-$\mu_{2}$ superblocks are not independent even if $\mu_{1}\neq\mu_{2}$.
This is because a level-$\mu_{1}$ superblock is also a level-$\mu_{2}$
superblock if $\mu_{1}\geq\mu_{2}$.

Next, we also capture the state-commitment process using the ideal random
functionality. Recall that we include the Merkle-root
$y(\operatorname{\mathsf{state}})$ of the $\operatorname{\mathsf{state}}$ at
that point in the block header. An adversary could attempt to produce a
malicious state,
$\operatorname{\mathsf{state}}^{\prime}\neq\operatorname{\mathsf{state}}$,
which also produces the same Merkle-root $y(\operatorname{\mathsf{state}})$.
During this attempt, the adversary would query the tuple
$(\operatorname{\mathsf{state}}^{\prime},y(\operatorname{\mathsf{state}}))$ to
the random functionality and receive “success” with a very small probability
$q$ and “failure” otherwise, independently of everything else. If the
adversary receives a success, we say
$\operatorname{\mathsf{state}}^{\prime}\equiv\operatorname{\mathsf{state}}$.
Here, $q$ can be assumed to be very small compared to the block success
probability $p$. This is because a block requires only the first $T$ bits of
the hash-string to be $0$, whereas in the case of the malicious state, the
entire hash-string has to match the original commitment $y$. In other words,
the adversary must find a _collision_ on the hash function used in the Merkle
tree, which is assumed to occur only with negligible probability with respect
to $p$. Assume that the adversary tries to find a malicious state at the tip
of the chain at some time $t$. By time $s\geq t$, let $N_{t}(s)$ denote the
number of subsequent blocks’ states for which the adversary’s malicious state
sequence is equivalent to, i.e.,

$F^{n}(\operatorname{\mathsf{state}}^{\prime}(\operatorname{\mathcal{C}}_{t}))\equiv
F^{n}(\operatorname{\mathsf{state}}(\operatorname{\mathcal{C}}_{t}))\quad,\text{for
all }0\leq n<N_{t}(s).$

Then, $N_{t}(s)$ is a Poisson process of rate $\lambda_{s}$, where
$\lambda_{s}<<\lambda_{a}$ because $q<<p$.

##  Appendix 0.C Our Protocols: Further Details

The notion of a superchain’s weight being approximately equal to the PoW of
the corresponding downchain was formalized as _superquality_ in [25]. Adding
to this idea, we define a notion of a dominant superchain below.

#### Good Superchain

First, we require that every sufficiently large suffix of the upchain weighs
at least $(1-\delta)$ times the amount of PoW of its corresponding downchain.

######  Definition 5 (Superquality)

Let $\operatorname{\mathcal{C}}$ be a blockchain, and
$\operatorname{\mathcal{C}}\uparrow^{\mu}$ be its level-$\mu$ upchain.
$C\uparrow^{\mu}$ is said to have $(\delta,g)$ superquality, for $\delta>0$
and $g\in\mathbb{N}$, if for all $g^{\prime}\geq g$, the following is true:

$\displaystyle\lvert\operatorname{\mathcal{C}}\uparrow^{\mu}[-g^{\prime}:]\rvert\geq(1-\delta)2^{-\mu}\lvert\operatorname{\mathcal{C}}\uparrow^{\mu}[-g^{\prime}:]\downarrow\rvert.$

Next, we define a dominant superchain.

######  Definition 6 (Dominant Superchain)

Consider a
$\mu$-superchain $\operatorname{\mathcal{C}}^{\prime}$ of an underlying chain,
$\operatorname{\mathcal{C}}=\operatorname{\mathcal{C}}^{\prime}\downarrow$,
and parameter $g\in\mathbb{N}$. $\operatorname{\mathcal{C}}^{\prime}$ is said
to be a dominant superchain with parameter $g$ if the following is true. Let
$\operatorname{\mathcal{P}}^{\prime}\subseteq\operatorname{\mathcal{C}}$ be
any trimmed chain with associated level range functions $L^{\prime}_{f}$ and
$L^{\prime}_{l}$. Let, $\mu_{1}\leq\mu^{\prime}\leq\mu$, and
$L^{\prime}_{f}(\mu^{\prime})\leq l\leq L^{\prime}_{l}(\mu^{\prime})$. Then,

$\begin{split}2^{\mu_{1}}\lvert\operatorname{\mathcal{P}}^{\prime}\\{l:&L^{\prime}_{l}(\mu^{\prime})+1\\}\uparrow^{\mu_{1}}\rvert\\\
+&\sum_{\mu^{\prime\prime}<\mu^{\prime}}2^{\mu^{\prime\prime}}\lvert\operatorname{\mathcal{P}}^{\prime}\\{L^{\prime}_{f}(\mu^{\prime\prime}):L^{\prime}_{l}(\mu^{\prime\prime})+1]\uparrow^{\mu^{\prime\prime}}\rvert\geq
2^{\mu}g,\end{split}$ (3)

implies that,

$\lvert\operatorname{\mathcal{P}}^{\prime}\uparrow^{\mu}\rvert\geq 1.$

As intuition, first note that $\operatorname{\mathcal{C}}^{\prime}$ and
$\operatorname{\mathcal{P}}^{\prime}$ have the same underlying downchain. We
are interested in the weight of $\operatorname{\mathcal{P}}^{\prime}$ to the
right of a block $l$ in level range $\mu^{\prime}$. For reasons that will be
clear from our trimming and chain-compare protocols (Algorithms 1 and 2), we
allow weighing the first level range $\mu^{\prime}$ using a different level
$\mu_{1}\leq\mu^{\prime}$. Then, the dominant-superchain property says that if
$\operatorname{\mathcal{P}}^{\prime}$ has a weight that is large enough, then
it contains at least 1 level-$\mu$ superblock.

A superchain is a _good-superchain_ if it has superchain quality and is a
dominant superchain.

######  Definition 7 (Good Superchain)

A $\mu$-superchain $\operatorname{\mathcal{C}}^{\prime}$ of an underlying
chain
$\operatorname{\mathcal{C}}=\operatorname{\mathcal{C}}^{\prime}\downarrow$, is
a good-superchain, denoted
$\mathtt{good}_{\delta,g}(\operatorname{\mathcal{C}}^{\prime},\mu)$, if it
satisfies superquality with parameters $(\delta,g)$ and is a dominant
superchain with parameter $g$.

Intuitively, if all the respective quantities above are equal to their mean
values, then $\operatorname{\mathcal{C}}\uparrow^{\mu}$ is a good superchain.
As long as an adversary does not try to violate the concentration around the
means, a superchain is a good superchain with high probability. The proof for
superquality can be found in [25]. The proof for dominant superchain property
can be found in Appendix 0.G.

###  0.C.1 Trimming

With the notion of a good superchain defined, our trimming protocol
description from Section 4 can be completed by specifying the parameter
functions used in Algorithm 1. We next describe our trimming protocol. The
protocol has security parameters $k,k^{\prime}\in\mathbb{N}$,
$a,c\in\mathbb{R}^{+}$, and $\delta\in(0,1)$. The length of the untrimmed tail
that is left untouched is dictated by the function
$\Delta(\operatorname{\mathcal{P}})$. If we denote $B^{\prime}$ to be the old
trimming point, then let333Unless otherwise mentioned, logarithms are to the
base $e$.,

$\Delta(\operatorname{\mathcal{P}})=k^{\prime}+a\log\left(S(\operatorname{\mathcal{P}},0)+\lvert\operatorname{\mathcal{P}}\\{B^{\prime}:\\}\rvert\right).$
(4)

When $\operatorname{\mathcal{P}}\\{:B^{\prime}\\}$ is trimmed to a certain
level $\mu$, we first ensure that the relevant upchain is a good superchain.
The parameter $g$ used here for level $\mu$ is given by,

$g(\operatorname{\mathcal{P}},\mu)=k+a\log S(\operatorname{\mathcal{P}},\mu).$
(5)

Apart from requiring that the $\mu$-upchain is a good-superchain, we require
that there are “enough” number of superblocks of that level $\mu$. This is
given by

$f(\operatorname{\mathcal{P}},\mu)=c\cdot g(\operatorname{\mathcal{P}},\mu)$
(6)

We require the functions $\Delta,g$ and $f$ to depend on the logarithm of the
estimated PoW to obtain strong concentration bounds, which achieves security
properties. As far as we know, this notion was first used to obtain strong
security for blockchains in [37] where the authors call it “logarithmic
waiting time”.

###  0.C.2 Comparing Work in trimmed Chains

Hybrid nodes need to have a protocol,
$\mathsf{Compare}(\operatorname{\mathcal{C}}^{(1)},\operatorname{\mathcal{C}}^{(2)})$,
to chose the main chain given two conflicting chains,
$\operatorname{\mathcal{C}}^{(1)}$ and $\operatorname{\mathcal{C}}^{(2)}$.
Full nodes (that store the entire blockchain) simply choose the longer of the
two chains as the main chain. The chain selection protocol for hybrid nodes is
a little more complicated since they do not store the entire chain. At a high
level, they use the sum of the cumulative weight,
$S(\operatorname{\mathcal{P}},0)$, of the trimmed portion of a chain and the
length of untrimmed section of the chain as a proxy for the chain length.
Next, we explain this algorithm more formally.

Let $\operatorname{\mathcal{P}}^{(1)}$ and $\operatorname{\mathcal{P}}^{(2)}$
be two trimmed chains with underlying (complete) chains
$\operatorname{\mathcal{C}}^{(1)}$ and $\operatorname{\mathcal{C}}^{(2)}$. We
need a protocol,
$\mathsf{Compare}(\operatorname{\mathcal{P}}^{(1)},\operatorname{\mathcal{P}}^{(2)})$,
that outputs $\operatorname{\mathcal{P}}^{(1)}$ if
$\lvert\operatorname{\mathcal{C}}^{(1)}\rvert>\lvert\operatorname{\mathcal{C}}^{(2)}\rvert$,
otherwise it outputs $\operatorname{\mathcal{P}}^{(2)}$. We allow error with
small probability given by the security definitions in Section 5.

The protocol is shown in Algorithm 2 and we summarize it here. First, only the
parts of the chains after their LCA block need to be compared (line 1). The
algorithm assigns weights to each chain, denoted
$\mathsf{Weight}(\operatorname{\mathcal{P}})$, and declares the chain with the
higher weight the winner (line 5). The weight is assigned to (the non-common
part of) a trimmed chain as follows. If the chain doesn’t have a long enough
untrimmed tail, then its weight is set to 0 (line 8). If the LCA block $b$ is
after the trimming point, then the weight is set to the number of blocks after
$b$ (lines 11 and 12). Otherwise, the level range in which $b$ lies is
computed (line 14). For the first level range, a set $M$ of levels is formed
with enough number of superblocks of that level (line 16). Then, the highest
PoW among the upchains in set $M$ is considered (line 17). For all subsequent
level-ranges, the PoW corresponding their level is added (lines 18 to 20). At
the end, the PoW of the untrimmed-tail is added and returned (line 22).

1

input :
$\operatorname{\mathcal{P}}^{(1)},L_{f}^{(1)},L_{l}^{(1)},{B^{\prime}}^{(1)}$
:: Chain 1

$\operatorname{\mathcal{P}}^{(2)},L_{f}^{(2)},L_{l}^{(2)},{B^{\prime}}^{(2)}$
:: Chain 2

2

3

4

5

6$b=\mathsf{LCA}(\operatorname{\mathcal{P}}^{(1)},\operatorname{\mathcal{P}}^{(2)})$

7
$W^{(1)}=\textnormal{{Weight}}(\operatorname{\mathcal{P}}^{(1)},L_{f}^{(1)},L_{l}^{(1)},{B^{\prime}}^{(1)},b)$

8
$W^{(2)}=\textnormal{{Weight}}(\operatorname{\mathcal{P}}^{(2)},L_{f}^{(2)},L_{l}^{(2)},{B^{\prime}}^{(2)},b)$

9

10 return argmax$(W^{(1)},W^{(2)})$

11

12

13func  _Weight(_$\operatorname{\mathcal{P}}$ , $L_{f}$, $L_{l}$ $B^{\prime}$,
$b$_)_:

14

15 if  _$\lvert\operatorname{\mathcal{P}}\\{B^{\prime}:\\}\rvert
<\Delta(g(\operatorname{\mathcal{P}},0)+\lvert\operatorname{\mathcal{P}}\\{B^{\prime}:\\}\rvert)$_
then

16 return $0$

17

18

19

20 if  _$b\geq B^{\prime}$_ then

21 return $\lvert\operatorname{\mathcal{P}}\\{b:\\}\rvert$

22

23

24

25 $\hat{\mu}\leftarrow$ such that $L_{f}(\hat{\mu})\leq b\leq
L_{l}(\hat{\mu})$

26

27

28
$M=\Big{\\{}\mu^{\prime}:\lvert\operatorname{\mathcal{P}}\uparrow^{\mu^{\prime}}\\{b:L_{l}(\hat{\mu})+1\\}\rvert\geq
f(\operatorname{\mathcal{P}},\hat{\mu})\Big{\\}}$

29 $W=\max_{\mu^{\prime}\in
M\cup\\{0\\}}\Big{\\{}2^{\mu^{\prime}}\lvert\operatorname{\mathcal{P}}\uparrow^{\mu^{\prime}}\\{b:L_{l}(\hat{\mu})+1\\}\rvert\Big{\\}}.$

30

31 for  _$\mu$ from $\hat{\mu}-1$ to $0$_ do

32 if
_$\lvert\operatorname{\mathcal{P}}\uparrow^{\mu}\\{L_{f}(\mu):L_{l}(\mu)+1\\}\rvert\geq
f(\operatorname{\mathcal{P}},\mu)$_ then

33
$W=W+2^{\mu}\lvert\operatorname{\mathcal{P}}\uparrow^{\mu}\\{L_{f}(\mu):L_{l}(\mu)+1\\}\rvert.$

34

35

36

37 return $W+\lvert\operatorname{\mathcal{P}}\\{B^{\prime}:\\}\rvert$

38

39

Algorithm 2 $\mathsf{Compare}(\cdot,\cdot)$ Protocol to compare work in
trimmed chains

The $\mathsf{Compare}(\cdot,\cdot)$ algorithm is used in two ways. First, by
hybrid-nodes to compute the main chain when they receive another (trimmed)
chain which is not the same as their trimmed chain. Second, by new hybrid-
nodes to bootstrap into the system. The new node receives (trimmed) chains
from other nodes, and then calls $\mathsf{Compare}(\cdot,\cdot)$ on pairs of
chains, until it is left with 1 winner.

###  0.C.3 State Verification

Similar to CoinPrune [28], a short commitment to the state at the block is
stored in every block. Therefore, a hybrid node can verify the correctness of
the blockchain’s state by comparing it to the corresponding state commitment.
The protocol is called $\mathsf{State-Verify}$ and is presented with more
details in Algorithm 3, and it is summarized in the following paragraph.

After a new node adopts a trimmed chain $\operatorname{\mathcal{P}}$ with
trimming point $B^{\prime}$, it needs to download the state,
$\operatorname{\mathsf{state}}(B^{\prime})$, at its trimming point. Since all
blocks to the right of the trimming point are retained, the node can compute
all the states corresponding to blocks in the untrimmed tail. In order to
verify the state, the node checks whether the Merkle-root of the computed
state for each block in the untrimmed tail matches its corresponding Merkle-
root $y$ stored within the block-header. If the Merkle-roots do not match at
any block in the untrimmed tail, then the algorithm returns False. This is
shown in Algorithm 3.

1

input : $\operatorname{\mathcal{P}}$ :: trimmed chain

$B^{\prime}::$ trimming point

$\operatorname{\mathsf{state}}(B^{\prime})$ :: State at trimming point

2

3

4

5for  _$i$ from $0$ to $B-B^{\prime}$_ do

6 Compute $\operatorname{\mathsf{state}}(B^{\prime}+i)$

7 if  _$\mathsf{Merkle-root}(\operatorname{\mathsf{state}}(B^{\prime}+i))\neq
y(B^{\prime}+i)$_ then

8 return False

9

10

11 return True

12

Algorithm 3 $\mathsf{State-Verify}$ Protocol to verify the state of a trimmed
chain

##  Appendix 0.D Poisson Process Preliminaries

$X$ is a Poisson random variable with rate $\lambda$, denoted $X\sim
Poisson(\lambda)$, if its probability distribution satisfies,

$\operatorname{\mathcal{P}}(X=x)=e^{-\lambda}\frac{\lambda^{x}}{x!},\quad\text{for
}x\in\mathbb{Z}^{+}.$

Let $A(t)$ be a random process indexed by time $t\geq 0$. Denote
$A(t_{1},t_{2})=A(t_{2})-A(t_{1})$, where $t_{2}\geq t_{1}$. $A$ is a Poisson
point process (or simply, Poisson process) of rate $\lambda$, denoted as
$A\sim PPP(\lambda)$, if,

$A(t)\sim Poisson(\lambda t),\text{for all }t\geq 0,$

and for disjoint intervals $(t_{1},t_{2})$ and $(t_{3},t_{4})$,

$A(t_{1},t_{2})\text{ is independent of }A(t_{3},t_{4}).$

Since the range of $A$ is the positive integers, and can be shown to be non-
decreasing with time, it can be thought of as a counting process. We also note
the fact the time between two successive events in $A$ is called the
interarrival time, and it is distributed as an exponential random variable of
rate $\lambda$.

First, we recall concentration bounds for a Poisson random variable, without
proof. The proof is obtained by applying Chernoff Bound [7].

###### Lemma 1

Let $X\sim Poisson(\lambda)$, for some $\lambda>0$. Then, for any $x>0$,

$\displaystyle\operatorname{\mathbb{P}}(X\geq\lambda+x)$ $\displaystyle\leq
e^{-\frac{-x^{2}}{2(\lambda+x)}},$
$\displaystyle\operatorname{\mathbb{P}}(X\leq\lambda-x)$ $\displaystyle\leq
e^{-\frac{-x^{2}}{2(\lambda+x)}}.$

In the following lemma, we upper bound and lower the time required for $n$
events to occur in a Poisson process.

###### Lemma 2

Let $A\sim PPP(\lambda)$. Let $T$ be a random variable indicating the time
taken for $n$ events to occur in the Poisson process. That is, $A(T)=n$. Then,
except with probability $e^{-n\frac{{\delta^{\prime}}^{2}}{2}}$,
$T\leq\frac{n(1+\delta^{\prime})}{\lambda}$. Similarly, except with
probability $e^{-n\frac{{\delta^{\prime}}^{2}}{2}}$,
$T\geq\frac{n(1-\delta^{\prime})}{\lambda}$.

###### Proof

Recall that in Poisson point process, interarrival times are i.i.d.,
exponential. Therefore, for $X_{1},\dots,X_{n}\stackrel{{\scriptstyle
iid}}{{\sim}}exp(\lambda_{1})$, $T\stackrel{{\scriptstyle
d}}{{=}}\sum_{i=1}^{n}X_{i}$. We can use Chernoff bound on $T$ as follows:

$\displaystyle\operatorname{\mathbb{P}}\left(T\geq\frac{n(1+\delta^{\prime})}{\lambda_{1}}\right)$
$\displaystyle\leq
e^{-n\sup_{s>0}\left(\frac{s(1+\delta^{\prime})}{\lambda_{1}}+\log(1-s/\lambda_{1})\right)},$
$\displaystyle=e^{-n(\delta^{\prime}-\log(1+\delta^{\prime}))},$
$\displaystyle\leq e^{-n\frac{{\delta^{\prime}}^{2}}{2}}.$

The upper bound is obtained similarly.

###### Lemma 3

Let $A_{1}\sim PPP(\lambda_{1})$ and $A_{2}\sim PPP(\lambda_{2})$ be
independent Poisson point processes, where $\lambda_{2}<\lambda_{1}$.

Assume that $A_{1}$ observers $n$ events in a certain time range. Then,
$A_{2}$ observes at most $(1+\delta^{\prime})^{2}\lambda_{2}/\lambda_{1}n$
events except with probability
$2e^{-\frac{n\lambda_{2}}{2\lambda_{1}}{\delta^{\prime}}^{2}}$.

Similarly, assuming that $A_{2}$ observers $n$ events, $A_{1}$ observes at
most $(1+\delta^{\prime})^{2}\lambda_{1}/\lambda_{2}n$ events except with
probability $2e^{-\frac{n}{2}{\delta^{\prime}}^{2}}$.

###### Proof

From Lemma 2, the time required from process $A_{1}$ to observe $n$ events is
upper bounded by $n(1+\delta^{\prime})/\lambda_{1}$ except with probability
$e^{-n{\delta^{\prime}}^{2}/2}$. So, over this range of time, except with
probability $e^{-n\frac{{\delta^{\prime}}^{2}}{2}}$, $A_{2}$ is stochastically
upper bounded by $Y\sim
Poisson\left(n\frac{\lambda_{2}(1+\delta^{\prime})}{\lambda_{1}}\right)$. Now,
applying the bound for a Poisson random variable from Lemma 1,

$\displaystyle\operatorname{\mathbb{P}}\left(Y\geq\frac{n\lambda_{2}}{\lambda_{1}}(1+\delta^{\prime})^{2}\right)$
$\displaystyle\leq\exp\left(-\frac{n\left(\frac{\lambda_{2}(1+\delta^{\prime})}{\lambda_{1}}\right)^{2}{\delta^{\prime}}^{2}}{2n\frac{\lambda_{2}}{\lambda_{1}}(1+\delta^{\prime})^{2}}\right),$
$\displaystyle=\exp\left(-\frac{n\lambda_{2}}{2\lambda_{1}}{\delta^{\prime}}^{2}\right).$

Therefore, over the time when $A_{1}$ observes $n$ events,
$A_{2}\leq(1+\delta^{\prime})^{2}\lambda_{2}/\lambda_{1}n$ except with
probability $2e^{-\frac{n\lambda_{2}}{2\lambda_{1}}{\delta^{\prime}}^{2}}$.

The other bound is obtained similarly.

###### Lemma 4

Let $A_{1}\sim PPP(\lambda_{1})$ and $A_{2}\sim PPP(\lambda_{2})$ be
independent Poisson point processes, and $A=A_{1}+A_{2}$. Given that over some
range of time $A=n$, then
$A_{1}\leq\frac{n\lambda_{1}}{\lambda_{1}+\lambda_{2}}(1+\delta^{\prime})$
except with probability
$e^{-\frac{n\lambda_{1}}{3(\lambda_{1}+\lambda_{2})}\frac{{\delta^{\prime}}^{(2)}}{3}}$.

###### Proof

Given $A$, $A_{1}$ behaves like a binomial random variable:
$(A_{1}\big{|}A=n)\sim\mathtt{Bin}\left(n,\frac{\lambda_{1}}{\lambda_{1}+\lambda_{2}}\right)$.
Therefore, the upper bound on $A_{1}$ is obtained by using the standard
Chernoff bound for binomial random variables.

##  Appendix 0.E Security Proofs

Let’s recall the notation. $\operatorname{\mathcal{P}}^{(1)}$ is the honest
trimmed chain and $\operatorname{\mathcal{P}}^{(2)}$ is the adversarial chain.
The underlying chains be $\operatorname{\mathcal{C}}^{(1)}$ and
$\operatorname{\mathcal{C}}^{(2)}$ respectively. Their respective trimming
points are ${B^{\prime}}^{(1)}(t)$ and ${B^{\prime}}^{(2)}(t)$, and their
respective chain lengths are $B^{(1)}$ and $B^{(2)}$. Let
$b=\mathsf{LCA}(\operatorname{\mathcal{P}}^{(1)},\operatorname{\mathcal{P}}^{(2)})$.
And,
$b^{\prime}=\mathsf{LCA}(\operatorname{\mathcal{C}}^{(1)},\operatorname{\mathcal{C}}^{(2)})$.
Trivially, $b^{\prime}\geq b$. Observe that $b^{\prime}$ and $b$ may not be
equal because the trimmed chains may skip blocks and thus have an earlier LCA
block.

$L^{(1)}(\cdot)$ is the level range function for
$\operatorname{\mathcal{P}}^{(1)}$, and $L^{(2)}$ for
$\operatorname{\mathcal{P}}^{(2)}$. Denote,

$\displaystyle\mu^{(1)}\text{ such that }L^{(1)}(\mu^{(1)}+1)<b\leq
L^{(1)}(\mu^{(1)}),$ $\displaystyle\mu^{(2)}\text{ such that
}L^{(2)}(\mu^{(2)}+1)<b\leq L^{(2)}(\mu^{(2)}).$

From the method by which $\mathsf{Weight}()$ function in Algorithm 2 chooses
levels, for the level ranges of $\mu^{(1)}$ and $\mu^{(2)}$, the
$\mathsf{Weight}()$ function might use levels $\hat{\mu}^{(1)}\leq\mu^{(1)}$
and $\hat{\mu}^{(2)}\leq\mu^{(2)}$ respectively (see line 16 and 17 of
Algorithm 2). For subsequent level ranges, the corresponding levels are used
by $\mathsf{Weight()}$ (see line 20).

First, we bound the gap between the LCA of the pruned chains, $b$, and the LCA
of the underlying chains, $b^{\prime}$.

###### Lemma 5

Denote,

$\displaystyle M=\max$
$\displaystyle\Bigg{\\{}\;2^{\hat{\mu}^{(1)}}g\Big{(}\operatorname{\mathcal{P}}^{(1)},\mu^{(1)}\Big{)},\quad
2^{\mu^{(1)}-1}g\Big{(}\operatorname{\mathcal{P}}^{(1)},\mu^{(1)}-1\Big{)}\;\Bigg{\\}}.$

$M$ essentially indicates the maximum of PoW of the first and second level
ranges of the honest trimmed chain.

Let $b^{\prime}$ be in the ${\mu^{\prime}}^{(2)}$-level range in
$\operatorname{\mathcal{P}}^{(2)}$. That is,

$L^{(2)}({\mu^{\prime}}^{(2)}+1)<b^{\prime}\leq
L^{(2)}({\mu^{\prime}}^{(2)}).$

If ${\mu^{\prime}}^{(2)}=\mu^{(2)}$, then,

$2^{\hat{\mu}^{(2)}}\lvert\operatorname{\mathcal{P}}^{(2)}\\{b+1:b^{\prime}+1\\}\uparrow^{\hat{\mu}^{(2)}}\rvert\leq
M.$

Otherwise,

$\displaystyle 2^{\hat{\mu}^{(2)}}$
$\displaystyle\lvert\operatorname{\mathcal{P}}^{(2)}\\{b+1:L(\mu^{(2)})+1\\}\uparrow^{\hat{\mu}^{(2)}}\rvert$
$\displaystyle+\sum_{\mu^{(2)}>\mu>{\mu^{\prime}}^{(2)}}2^{\mu}W^{(2)}(\operatorname{\mathcal{P}}^{(2)},\mu)$
$\displaystyle+2^{{\mu^{\prime}}^{(2)}}\lvert\operatorname{\mathcal{P}}\\{L({\mu^{\prime}}^{(2)})+1:b^{\prime}+1\\}\uparrow^{{\mu^{\prime}}^{(2)}}\rvert\leq
M.$

The above two equations essentially convey that the weight of the adversary’s
trimmed chain $\operatorname{\mathcal{P}}^{(2)}$ between $b$ and $b^{\prime}$
is upper bounded by $M$.

######  Proof (Proof of Lemma 5)

This is a direct consequence of the dominant-superchain property.

Next, we upper bound the weight of a trimmed chain.

###### Lemma 6

Let $\operatorname{\mathcal{C}}$ be a blockchain and
$\operatorname{\mathcal{P}}$ be its corresponding trimmed chain produced by
Algorithm 1. Let $\delta\leq 1/\sqrt{2}$. If
$\lvert\operatorname{\mathcal{C}}\rvert=B$, then except with probability
$\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-1}}$,
$S(\operatorname{\mathcal{P}},0)+\lvert\operatorname{\mathcal{P}}\\{B^{\prime}:\\}\rvert\leq((1+\delta)^{2}+\delta)B$.

###### Proof

Let $\mu$ be the highest level with
$S(\operatorname{\mathcal{P}},\mu)\geq\delta B$. This means that, for all
$\mu^{\prime}\leq\mu$,

$\lvert\operatorname{\mathcal{P}}\\{L_{f}(\mu^{\prime}):L_{l}(\mu^{\prime})+1\\}\uparrow^{\mu^{\prime}}\rvert\geq
k+a\log(\delta B).$

By Lemma 3, we get that for every $\mu^{\prime}\leq\mu$,

$\lvert\operatorname{\mathcal{P}}\\{L_{f}(\mu^{\prime}):L_{l}(\mu^{\prime})+1\\}\uparrow^{\mu^{\prime}}\rvert\leq(1+\delta^{2})\left(L_{l}(\mu^{\prime})-L_{f}(\mu^{\prime})+1\right),$

except with probability

$2e^{-\frac{k+a\log(\delta
B)}{2}{\delta}^{2}}=\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2}}.$

From Lemma 9, the number of level-ranges in $\operatorname{\mathcal{P}}$ is at
most $\log B/\log 2$, except with probability
$\operatorname{\mathsf{negl}}(k)/B^{a/4}$. Therefore, by a union bound,

$S(\operatorname{\mathcal{P}},0)+\lvert\operatorname{\mathcal{P}}\\{B^{\prime}:\\}\rvert\leq((1+\delta)^{2})+\delta)B,$

except with probability,

$\log
B\cdot\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2}}+\frac{\operatorname{\mathsf{negl}}(k)}{B^{a/4}}=\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-1}}.$

Next, we prove Theorem 2.

###  0.E.1 Proof of Theorem 1

######  Proof (Proof of Theorem 2)

The proof is by induction on the length of the honest blockchain $B^{(1)}$.

As the base case, consider $B^{(1)}=ck$. Since no trimming has occurred up to
this point, the probability of a trim-attack up to this point is 0.

As the induction hypothesis, assume that up to chain-length $B$, the adversary
wasn’t able to create a fork from beyond a honest node’s trimming point. That
is,

$\begin{split}\forall t&\text{ such that
}B^{(1)}_{t}<B,\mathsf{Compare}\left(\operatorname{\mathcal{P}}^{(1)}_{t},\operatorname{\mathcal{P}}^{(2)}_{t}\right)=\operatorname{\mathcal{P}}^{(2)}_{t}\text{
implies that }\\\
&\mathsf{LCA}\left(\operatorname{\mathcal{P}}^{(1)}_{t},\operatorname{\mathcal{P}}^{(2)}_{t}\right)\geq
B^{(1)}_{t}-\Delta(S(\operatorname{\mathcal{P}}^{(1)}_{t},0)+\lvert\operatorname{\mathcal{P}}\\{{B^{\prime}}^{(1)}_{t}:\\}\rvert).\end{split}$
(7)

For the induction step, consider a time $t$ when the length of the honest
chain is $B_{t}^{(1)}=B$. As a contradiction, assume that the adversary has
created a secret chain $\operatorname{\mathcal{P}}^{(2)}_{t}$ such that,
$\mathsf{Compare}\left(\operatorname{\mathcal{P}}^{(1)},\operatorname{\mathcal{P}}^{(2)}\right)=\operatorname{\mathcal{P}}^{(2)}$,
and
$b=\mathsf{LCA}\left(\operatorname{\mathcal{P}}^{(1)},\operatorname{\mathcal{P}}^{(2)}\right)<B-\Delta(S(\operatorname{\mathcal{P}}^{(1)}_{t},0)+\lvert\operatorname{\mathcal{P}}\\{{B^{\prime}}^{(1)}_{t}:\\}\rvert)$.

We now split into two cases based on the location of $b$:

##### Case 1: $b\geq\delta B$

By superchain quality of $\operatorname{\mathcal{P}}^{(1)}$, we have,

$\begin{split}S(\operatorname{\mathcal{P}}^{(1)},\mu^{(1)})&\geq(1-\delta)b,\\\
&\geq(1-\delta)\delta B.\end{split}$ (8)

Moreover, since $\operatorname{\mathcal{P}}^{(2)}$ shares blocks with
$\operatorname{\mathcal{P}}^{(1)}$ up to block $b$, we have,

$\begin{split}S(\operatorname{\mathcal{P}}^{(2)},\mu^{(2)})&\geq(1-\delta)b,\\\
&\geq(1-\delta)\delta B.\end{split}$ (9)

As a consequence of Lemma 5, the weight of $\operatorname{\mathcal{P}}^{(2)}$
between blocks $b$ and $b^{\prime}$ is upper bounded by $M$.

Next, we define a block $b^{\prime\prime}\geq b^{\prime}$ which is such that
all level ranges in $\operatorname{\mathcal{P}}^{(2)}\\{b^{\prime\prime}:\\}$
are of size at least
$c^{\prime}g(\operatorname{\mathcal{P}}^{(1)},\mu^{(1)})$, for some
$1<c^{\prime}<c$. In order to ensure this, $b^{\prime\prime}$ can be defined
as,

$b^{\prime\prime}=\begin{cases}b^{\prime},&\text{if
}\lvert\operatorname{\mathcal{P}}^{(2)}\\{b^{\prime}+1:L_{l}({\mu^{\prime}}^{(2)})+1\\}\uparrow^{{\mu^{\prime}}^{(2)}}\rvert\\\
&\quad\geq c^{\prime}(k+a\log((1-\delta)\delta B)),\\\
L^{(2)}_{l}({\mu^{\prime}}^{(2)})+1,&\text{otherwise},\end{cases}$ (10)

where ${\mu^{\prime}}^{(2)}$ is the level range in which block $b^{\prime}$
resides in $\operatorname{\mathcal{P}}^{(2)}$. If $b^{\prime}>b$, then
${\mu^{\prime}}^{(2)}\leq\max\\{{\hat{\mu}}^{(1)},\mu^{(1)}-1\\}$. Therefore,
the weight of $\operatorname{\mathcal{P}}^{(2)}$ between $b^{\prime}$ and
$b^{\prime\prime}$ is upper bounded by $c^{\prime}M$.

Let $b^{*}$ be the earliest block such that all blocks in
$\operatorname{\mathcal{P}}^{(2)}\\{b^{*}+1:\\}$ were mined by the adversary.
Then, by the induction hypothesis,

$b^{*}-b^{\prime\prime}\leq\Delta(S(\operatorname{\mathcal{P}}^{(1)}_{t},0)+\lvert\operatorname{\mathcal{P}}^{(1)}_{t}\\{{B^{\prime}}^{(1)}:\\}\rvert).$

The above statement is proved as follows. Assume there was a time $t^{*}$ when
$b^{*}$ was in a honest node’s chain, but at a later time $t$ the block after
$b^{\prime\prime}$ in $\operatorname{\mathcal{P}}^{(2)}_{t}$ is not in the
honest node’s chain $\operatorname{\mathcal{C}}_{t}$. By the induction
hypothesis,

$\begin{split}b^{*}-b^{\prime\prime}&\leq\Delta(S(\operatorname{\mathcal{P}}^{(1)}_{t^{*}},0)+\lvert\operatorname{\mathcal{P}}^{(1)}_{t^{*}}\\{{B^{\prime}}^{(1)}:\\}\rvert),\\\
&\leq\Delta(S(\operatorname{\mathcal{P}}^{(1)}_{t},0)+\lvert\operatorname{\mathcal{P}}^{(1)}_{t}\\{{B^{\prime}}^{(1)}:\\}\rvert).\end{split}$

Given, $k^{\prime}=k-a\log\left(((1+\delta^{2})+\delta)/\delta\right)$.
Therefore, from Lemma 6, except with probability
$\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-1}}$,

$\Delta(S(\operatorname{\mathcal{P}}^{(1)}_{t},0)+\lvert\operatorname{\mathcal{P}}^{(1)}_{t}\\{{B^{\prime}}^{(1)}:\\}\rvert)\leq
g(\operatorname{\mathcal{P}}^{(1)},\mu^{(1)}).$

Therefore,

$\mathsf{Weight}(\operatorname{\mathcal{P}}^{(2)},b^{*})\geq\frac{c^{\prime}-1}{c^{\prime}}\frac{c-1-c^{\prime}}{c}\mathsf{Weight}(\operatorname{\mathcal{P}}^{(1)},b).$

Since, each level range in $\operatorname{\mathcal{P}}^{(2)}\\{b^{*}:\\}$
contains at least $g(\operatorname{\mathcal{P}}^{(1)},\mu^{(1)})$ number of
corresponding superblocks, we have that except with probability
$\operatorname{\mathsf{negl}}(k)\log B/B^{a\delta^{2}/2}$, the time required
$T$ required by the adversary is lower bounded as,

$T\geq\frac{(1-\delta)}{\lambda_{a}}\frac{c^{\prime}-1}{c^{\prime}}\frac{c-1-c^{\prime}}{c}\mathsf{Weight}(\operatorname{\mathcal{P}}^{(1)},b).$

In this time, except with probability
$\operatorname{\mathsf{negl}}(k)/B^{a\delta^{2}/2}$, the honest chain growth
is lower bounded as,

$\lvert\operatorname{\mathcal{C}}\\{b:\\}\rvert\geq(1-\delta)^{2}\frac{\lambda_{h}}{\lambda_{a}}\frac{c^{\prime}-1}{c^{\prime}}\frac{c-1-c^{\prime}}{c}\mathsf{Weight}(\operatorname{\mathcal{P}}^{(1)},b).$

We know from superquality property that
$\mathsf{Weight}(\operatorname{\mathcal{P}}^{(1)},b)\geq(1-\delta)\lvert\operatorname{\mathcal{C}}\\{b:\\}\rvert$.
Therefore, we reach a contradiction if,

$(1-\delta)^{3}\frac{\lambda_{h}}{\lambda_{a}}\frac{c^{\prime}-1}{c^{\prime}}\frac{c-1-c^{\prime}}{c}>1.$
(11)

##### Case 2: $b<\delta B$

The reason to consider this case separately is because when $b<\delta B$, the
corresponding level-range containing $b$ may not have enough number of blocks
for us to obtain a strong concentration bound. Therefore, we jump ahead to a
level which contains enough superblocks. Let ${\tilde{\mu}}^{(2)}$ be the
highest-level in $\operatorname{\mathcal{P}}^{(2)}$ such that,

$S(\operatorname{\mathcal{P}}^{(2)},{\tilde{\mu}}^{(2)})\geq\delta B.$

In case $b^{\prime}$ falls in the level range of $\tilde{\mu}^{(2)}$ or below,
then the same analysis for Case 1 holds. In particular, if the relation in
(11) is satisfied, we reach a contradiction except with probability
$\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-1}}$.

Otherwise, if $b^{\prime}$ falls in a level-range higher than
$\tilde{\mu}^{(2)}$, we set,

$b^{\prime\prime}=L^{(2)}_{f}(\tilde{\mu}^{(2)}).$

Since $b<\delta B$, we have,

$\begin{split}\mathsf{Weight}(\operatorname{\mathcal{P}}^{(2)},b^{\prime\prime})&\geq(1-\delta)\mathsf{Weight}(\operatorname{\mathcal{P}}^{(2)},b),\\\
&\stackrel{{\scriptstyle(x)}}{{\geq}}(1-\delta)\mathsf{Weight}(\operatorname{\mathcal{P}}^{(1)},b),\\\
&\stackrel{{\scriptstyle(y)}}{{\geq}}(1-\delta)^{3}B.\end{split}$

(x) follows because we assume that $\operatorname{\mathcal{P}}^{(2)}$ beats
$\operatorname{\mathcal{P}}^{(1)}$. (y) follows by superchain quality of the
honest chain and the fact that $b<\delta B$.

By the same argument of the induction hypothesis used in Case 1, except with
probability $\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-1}}$,
$(c-1)/c$ fraction of the blocks in
$\operatorname{\mathcal{P}}^{(2)}\\{b^{\prime\prime}:\\}$ were mined by the
adversary. Again, except with probability
$\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2}}$, by the time that
the adversary mines those blocks, the length of the honest chain would be,

$\lvert\operatorname{\mathcal{C}}\\{b+1:\\}\rvert\geq(1-\delta)^{5}\frac{\lambda_{h}}{\lambda_{a}}\frac{c-1}{c}B.$

The above equation is a contradiction if,

$(1-\delta)^{5}\frac{\lambda_{h}}{\lambda_{a}}\frac{c-1}{c}>1.$ (12)

End Case 2

There are at most $B-\Delta(\operatorname{\mathcal{P}}^{(1)})$ unique choices
that can be made for block $b$. For each choice, the conclusions of Case 1 and
Case 2 hold except with probability
$\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-1}}$. Therefore,
taking a union bound over all choices of $b$, the conclusions hold except with
probability $\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-2}}$.
This completes the induction step.

The induction step at chain-length $B$ is violated with probability
$\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-2}}$. Therefore,
summing over all chain lengths, we have,

$\begin{split}\operatorname{\mathbb{P}}(\mathsf{trim-
attacked})&\leq\sum_{B=1}^{\infty}\frac{\operatorname{\mathsf{negl}}(k)}{B^{a\delta^{2}/2-2}},\\\
&=\operatorname{\mathsf{negl}}(k),\end{split}$ (13)

where the last equation follows since $a\delta^{2}/2-2\geq 2$.

###  0.E.2 Proofs of Other Theorems:

######  Proof (Proof of Corollary 1)

We have proved in Theorem 2 that the adversary cannot create a longer fork
from before a honest node’s trimming point except with probability
$\operatorname{\mathsf{negl}}(k)$. Since a honest node retains all blocks
after the trimming point, comparing two trimmed chains that differ only after
the trimming point is equivalent to comparing the underlying chains (see line
11 and 12 in Algorithm 2).

######  Proof (Proof Sketch of Theorem 6.2)

In order to pass through the $\mathsf{state-verify}$ protocol in Algorithm 3,
the adversary has to produce a malicious state at the trimming point of an
honest node, such that it verifies against all the states corresponding to the
untrimmed chain tail. In Section 0.B.3, we explained that the adversary’s
process of generating a malicious state sequence is a Poisson process of rate
$\lambda_{s}$, where $\lambda_{s}<<\lambda_{a}$. Therefore, from the same
argument as in Theorem 2, we can prove that there exists no time when the
adversary can create such a malicious state.

######  Proof (Proof of Corollary 2)

This is a corollary of Theorems 2 and 6.2. Since, the probability that there
exists a time when the system is either
$\mathsf{trim-attacked}$ or $\mathsf{state-attacked}$ is very small, the
probability that an arriving node sees the system attacked in either way is
negligible in $k$.

######  Proof (Proof Sketch of Theorem 6.3)

Assume that all relevant quantities concentrate strongly around their means.
First, the highest level-range would be $\mu_{h}=O(\log B)$. This is because,
a level $\mu_{h}$ is $2^{\mu_{h}}$ times harder to find than a level-0
superblock.

Next, a level range of level-$\mu$ would contain at most $O(\log B)$
$\mu$-superblocks. Because, if there were more, then it could be trimmed to
level-$(\mu+1)$. Since we also retain suffixes of length $O(\log B)$ blocks of
every lower level, level-range $\mu$ would contain about $O(\log^{2}B)$
blocks. Adding across all the $\mu_{h}$ number of level ranges, the trimmed
portion of $\operatorname{\mathcal{P}}$ would contain about $O(\log^{3}B)$
blocks. And, the untrimmed tail would contain at most $O(\log B)$ blocks.

Since an interlink contains a link to the previous superblock of every level,
the size of the interlink would be $O(\log B)$, thus making the size of each
block $O(\log B)$. Therefore, the total storage requirement would be
$O(\log^{4}B)$. These statements are proved more rigorously in appendix 0.H.

##  Appendix 0.F Trimming Attack

Here we prove Theorem 6.4.

######  Proof (Proof of Theorem 6.4)

Let $f(x)=c_{0}\log(1+x)$, for some small constant $c_{0}$. Define a sequence
$\left(\alpha_{i}\right)_{i}$ as follows:

$\begin{split}\alpha_{0}&=0,\\\ \alpha_{1}&=1,\\\
\alpha_{i}&=2f\left(\sum_{j=1}^{i-1}\alpha_{j}\right),\quad i\geq
2.\end{split}$

The adversarial attack follows a sequence of attempts. The
$i\textsuperscript{th}$ attempt begins when
$\lvert\operatorname{\mathcal{C}}_{t}\rvert=\sum_{j=0}^{i-1}\alpha_{j}$. At
this point, the adversary abandons the previous attempt and starts mining on a
secret chain $\operatorname{\mathcal{D}}_{t}$ forking away from
$\operatorname{\mathcal{C}}_{t}$ at this tip. The attempt lasts until one of
$\operatorname{\mathcal{C}}_{t}$ or $\operatorname{\mathcal{D}}_{t}$ reach a
length of $\left(\sum_{j=0}^{i}\alpha_{j}\right)+1$. If
$\operatorname{\mathcal{D}}$ reaches the length first, then the adversary
waits until $\operatorname{\mathcal{C}}$ reaches a length of
$\sum_{j=0}^{i}\alpha_{j}$, at which point it publishes
$\operatorname{\mathcal{D}}$. Since, $\operatorname{\mathcal{D}}$ will be
longer than $\operatorname{\mathcal{C}}$, the honest nodes will adapt
$\operatorname{\mathcal{D}}$. The fact that this is a successful trimming
attack follows from the following claim:

###### Claim 0.F.1

For all large enough $i$, $\alpha_{i}\geq f(\sum_{j=1}^{i}\alpha_{j})$

From the definition of the attack, the length of the honest chain when
adversary publishes his secret chain is $\sum_{j=1}^{i}\alpha_{i}$. Recall,
$f(\sum_{j=1}^{i}\alpha_{i})$ is an upperbound on the number of blocks between
the trimming point and the tip of the chain for the honest node, since
$B-B^{\prime}=o(\log B)$. Therefore, the above claim shows that the adversary
has successfully created a fork from before a trimming point of any node. To
prove the claim, for large enough $i$ we have,

$\displaystyle\alpha_{i}$
$\displaystyle=f\left(\sum_{j=1}^{i-1}\alpha_{j}\right)+f\left(\sum_{j=1}^{i-1}\alpha_{j}\right),$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}f\left(\sum_{j=1}^{i-1}\alpha_{j}\right)+f(\alpha_{i}),$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}f\left(\sum_{j=1}^{i}\alpha_{j}\right).$

(a) follows because $2c_{0}\log(z)\leq z$. (b) follows by the sub-additivity
of $\log(1+z)$.

The below two claims are needed to compute the probability of a successful
attack attempt.

###### Claim 0.F.2

$\alpha_{i}\leq c_{1}\log i$, for all $i\geq 2$ and $c_{1}=1+4c_{0}$.

Assuming $c_{0}\leq 1/4$, $1\leq c_{1}\leq 2$. We will prove the above claim
by induction. As the base case,
$\alpha_{2}=2c_{0}\log(1+\alpha_{1}1)=2c_{0}\log 2\leq c_{1}\log 2$. Assume
that the claim is true for all $j\leq i-1$. Then,

$\displaystyle\alpha_{i}$
$\displaystyle=2c_{0}\log\left(1+\sum_{j=1}^{i-1}\alpha_{j}\right),$
$\displaystyle\leq 2c_{0}\log(1+(i-1)c_{1}\log i),$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2c_{0}\log(ic_{1}\log i),$
$\displaystyle=2c_{0}\log i+2c_{0}\log c_{1}+2c_{0}\log\log i,$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2c_{0}\log i+2c_{0}\log
i+\log i,$ $\displaystyle=(4c_{0}+1)\log i.$

(a) follows since $c_{1}\geq 1$. (b) follows since $i\geq 2\geq c_{1}$.

The probability of the adversary’s $i\textsuperscript{th}$ attempt succeeding
is $e^{-c_{2}\alpha_{i}}$, for some constant $c_{2}$ [37].

###### Claim 0.F.3

$\sum_{i=1}^{\infty}e^{-c_{2}\alpha_{i}}=\infty$.

To prove the claim,

$\displaystyle\sum_{i=2}^{\infty}e^{-c_{2}\alpha_{i}}$
$\displaystyle=\sum_{i=2}^{\infty}e^{-2c_{0}c_{2}\log(1+\sum_{j=1}^{i-1}\alpha_{i})},$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sum_{i=2}^{\infty}e^{-\log(1+\sum_{j=1}^{i-1}\alpha_{j})},$
$\displaystyle=\sum_{i=2}^{\infty}\frac{1}{1+\sum_{j=1}^{i-1}\alpha_{j}},$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\sum_{i=2}^{\infty}\frac{1}{1+\sum_{j=1}^{i-1}c_{1}\log
i},$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\sum_{i=2}^{\infty}\frac{1}{1+c_{1}i\log
i},$ $\displaystyle=\infty.$

(a) follows since $c_{0}$ can be made as small as desired. (b) follows from
Claim 0.F.2. (c) can be verified to diverge using the integral test.

Since the attack-attempts are carried over disjoint sections of the
blockchain, all the attempts are mutually independent. Therefore, from Claim
0.F.3 and the second Borel-Cantelli Lemma, we have,

$\operatorname{\mathbb{P}}(\mathsf{trim-attacked})=1.$

##  Appendix 0.G Dominant Superchain

We will use the following concentration bound for sums of independent, but not
necessarily identically distributed, Bernoulli random variables. It can be
proved by an elementary application of Chernoff bound and can be found in
[14].

###### Lemma 7

Let $\\{X_{i}\\}_{i=1}^{n}$ be a sequence of independent random variables with
$X_{i}\sim Bernoulli(p_{i})$. Let $S_{n}=\sum_{i=1}^{n}X_{i}$, and
$s_{n}=\sum_{i=1}^{n}p_{i}$. Then, for $0<\varepsilon<1$,

$\operatorname{\mathbb{P}}\left(S_{n}\leq(1-\varepsilon)s_{n}\right)\leq
e^{-\frac{\varepsilon^{2}}{2}s_{n}}.$

We now prove the high likelihood of dominant superchains.

###### Lemma 8

Let $\operatorname{\mathcal{C}}$ be a blockchain and
$\operatorname{\mathcal{C}}\uparrow^{\mu}$ be its corresponding level-$\mu$
upchain. Then, for any $k\in\mathbb{N}$ and $g\geq
k+a\log(\lvert\operatorname{\mathcal{C}}\rvert)$. Then, if $a\geq 8$,
$\operatorname{\mathcal{C}}\uparrow^{\mu}$ is a dominant superchain with high
probability in $k$ and $\lvert C\rvert$.

###### Proof

Consider a starting block $b_{1}\geq\operatorname{\mathcal{C}}[0]$ and ending
block $b_{2}\leq\operatorname{\mathcal{C}}[-1]$.

First, observe that if
$\operatorname{\mathcal{C}}[b_{1}:b_{2}+1]\uparrow^{\mu}\geq 1$, then any
trimmed chain $\operatorname{\mathcal{P}}$ starting at $b_{1}$ and ending at
$b_{2}$, and with its highest level range being at most $\mu$, will contain at
least one level-$\mu$ superblock. This is because a level-$\mu$ superblock,
call it $b_{3}$, is also a level-$\mu^{\prime}$ superblock for any
$\mu^{\prime}\leq\mu$. Therefore, the interlink data-structure ensures that a
there is a level range $\mu^{\prime}$, which contains a link to $b_{3}$.

Let $\operatorname{\mathcal{P}}^{\prime}$ be the trimmed chain of the highest
weight starting at $b_{1}$ and ending at $b_{2}$, and with its highest level-
range being at most $\mu$. Assume that it satisfies the premise as defined in
equation 3. That is,

$\begin{split}2^{\mu_{1}}\lvert\operatorname{\mathcal{P}}^{\prime}\\{l:&L^{\prime}_{l}(\mu^{\prime})+1\\}\uparrow^{\mu_{1}}\rvert\\\
+&\sum_{\mu^{\prime\prime}<\mu^{\prime}}2^{\mu^{\prime\prime}}\lvert\operatorname{\mathcal{P}}^{\prime}\\{L^{\prime}_{f}(\mu^{\prime\prime}):L^{\prime}_{l}(\mu^{\prime\prime})+1]\uparrow^{\mu^{\prime\prime}}\rvert\geq
2^{\mu}g.\end{split}$

It is useful re-arrange the equation by dividing both sides by $2^{\mu}$.

$\begin{split}2^{\mu_{1}-\mu}\lvert\operatorname{\mathcal{P}}^{\prime}\\{l:&L^{\prime}_{l}(\mu^{\prime})+1\\}\uparrow^{\mu_{1}}\rvert\\\
+&\sum_{\mu^{\prime\prime}<\mu^{\prime}}2^{\mu^{\prime\prime}-\mu}\lvert\operatorname{\mathcal{P}}^{\prime}\\{L^{\prime}_{f}(\mu^{\prime\prime}):L^{\prime}_{l}(\mu^{\prime\prime})+1]\uparrow^{\mu^{\prime\prime}}\rvert\geq
g.\end{split}$ (14)

Given that a block is a level-$\mu^{\prime\prime}$ superblock, let $X$ be an
indicator variable for it also to be a level-$\mu$ superblock. Then,
$\operatorname{\mathbb{P}}(X=1)=2^{\mu^{\prime\prime}-\mu}$. Therefore, we can
associate a sequence of Bernoulli random variables $\\{X_{i}\\}_{i=1}^{n}$
with $\operatorname{\mathcal{P}}$, where $X_{i}$ indicates whether the the
$i\textsuperscript{th}$ superblock as taken in (14) is a level-$\mu$
superblock. Denoting $\operatorname{\mathbb{P}}(X_{i}=1)=p_{i}$, equation (14)
says that,

$s_{n}=\sum_{i=1}^{n}p_{i}\geq g.$

Now, using Lemma 7, we can lower bound $S_{n}=\sum_{i=1}^{n}X_{i}$, as,

$\begin{split}\operatorname{\mathbb{P}}(S_{n}\leq 1)&\leq
e^{-\frac{(1-1/g)^{2}}{2}g},\\\ &\leq e^{-g/4},\\\
&\leq\frac{\operatorname{\mathsf{negl}}(k)}{B^{a/4}},\end{split}$

where we denote $B=\lvert C\rvert$. There are totally $B$ ways to choose
$b_{1}$, and then $B-b_{1}$ ways to choose $b_{2}$. Therefore, there are
totally at most $B^{2}$ ways to choose $b_{1}$ and $b_{2}$. Taking a union
bound over all possible starting points $b_{1}$ and ending points $b_{2}$, we
conclude there exists at least one level-$\mu$ superblock in
$\operatorname{\mathcal{C}}$ with high probability if $a\geq 8$.

##  Appendix 0.H Succinctness

###### Lemma 9

When the length of the blockchain $\operatorname{\mathcal{C}}$ is $B$, the
highest-level of superblock in the corresponding trimmed chain
$\operatorname{\mathcal{P}}$ is at most $\log B/\log 2$ except with
probability $\operatorname{\mathsf{negl}}(k)/B^{a/4}$.

###### Proof

Let $\mu=\log B/\log 2$. Then, weight of 1 level-$\mu$ superblock is
$2^{\mu}=B$. Therefore, $g(\operatorname{\mathcal{P}},\mu)\geq B$.

Also, $\lvert\operatorname{\mathcal{C}}\uparrow^{\mu}\rvert\sim Poisson(1)$.
Therefore, applying the Poisson concentration bound,

$\displaystyle\operatorname{\mathbb{P}}\left(\lvert\operatorname{\mathcal{C}}\uparrow^{\mu}\rvert\geq
g(\operatorname{\mathcal{P}},\mu)\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}\left(\lvert\operatorname{\mathcal{C}}\uparrow^{\mu}\rvert\geq
1+(k-1)+a\log B\right),$ $\displaystyle\leq e^{-\frac{k-1+a\log B}{4}},$
$\displaystyle=\frac{\operatorname{\mathsf{negl}}(k)}{B^{a/4}}.$

The proof is complete by observing that if
$\lvert\operatorname{\mathcal{C}}\uparrow^{\mu}\rvert<g(\operatorname{\mathcal{P}},\mu)$,
then the chain won’t be trimmed to this level.

Next, we show that individual level ranges aren’t too big.

###### Lemma 10

Let $\operatorname{\mathcal{P}}$ be a trimmed chain of an underlying chain
$\operatorname{\mathcal{C}}$ obtained by the trimming protocol. Let $L_{f}$
and $L_{l}$ be the associated level range functions. Then, for every level
$\mu$,
$\lvert\operatorname{\mathcal{P}}\\{L_{f}(\mu)+1:L_{l}(\mu)\\}\uparrow^{\mu}\rvert\leq
4f(\operatorname{\mathcal{P}},\mu)$, with high probability.

###### Proof

As a contradiction, assume that there were a level $\mu$, such that
$\lvert\operatorname{\mathcal{P}}\\{L_{f}(\mu)+1:L_{l}(\mu)\\}\uparrow^{\mu}\rvert\leq
4f(\operatorname{\mathcal{P}},\mu)$. Then, from Lemma 3, with high
probability, we would have
$\lvert\operatorname{\mathcal{P}}\\{L_{f}(\mu)+1:L_{l}(\mu)\\}\uparrow^{\mu+1}\rvert\leq
f(\operatorname{\mathcal{P}},\mu)$. This means that the trimming protocol
would have trimmed this range to level $\mu+1$.

Now we are ready to prove the optimistic succinctness theorem.

######  Proof (Proof Theorem 6.3)

From Lemma 9 we know that the highest level is $O(\log B)$ with high
probability. And, from Lemma 10, the number of $\mu$-level superblocks in
level range $\mu$ is $O(\log B)$ with high probability.

According to the construction of level range $\mu$ in the trimming protocol,
it contains $O(\log B)$ superblock of level-$\mu^{\prime}$ for each level
$\mu^{\prime}<\mu$. Therefore, each level range contains $O(\log^{2}B)$ blocks
with high probability. And, since there are at most $O(\log B)$ level ranges,
the number of blocks in the trimmed section of $\operatorname{\mathcal{P}}$ is
$O(\log^{3}B)$ blocks. Since, the untrimmed tail consists of $O(\log B)$
blocks, $\operatorname{\mathcal{P}}$ totally contains $O(\log^{3}B)$ blocks.

Each block has the interlink, which in turn contains a link to the previous
superblock of every level. Since there are at most $O(\log B)$ level of
superblocks, the size of the interlink is $O(\log B)$. This makes the overall
size of $\operatorname{\mathcal{P}}$ as $O(\log^{4}B)$.

##  Appendix 0.I Our Protocol in the Random Oracle Model

In our analysis, we have modelled PoW mining as calls to an ideal random
functionality which returns a “success” with a small probability, and
“failure” otherwise, independent of everything else. However, in current PoW
systems, mining is performed by making calls to a random oracle hash function,
$H:\\{0,1\\}^{*}\to\\{0,1\\}^{\kappa}$, where $\kappa$ is a security
parameter. Since the output space of $H$ is finite, we cannot have our
formulation of $\mathsf{trim-attacked}$ in Definition 1 as a security model.
This is because $\mathsf{trim-attacked}$ considers time from $0$ to infinity,
during which time the hash function $H$ is going to experience collisions with
probability 1. In particular, in order to ensure that $H$ doesn’t experience
collisions with high probability, one can only run the blockchain for
$\mathsf{poly}(\kappa)$ time (or, $\mathsf{poly}(\kappa)$ rounds in the
discrete time model)444$\mathsf{poly}(\kappa)$ means polynomial in $\kappa$..

In [30], the authors denote our ideal random functionality as
$\mathcal{F}_{tree}$. They prove that when a blockchain is run for
$\mathsf{poly}(\kappa)$ rounds, the $\mathcal{F}_{tree}$ model and the random
oracle model are statistically close (see Lemma 5.1 in [30]). Using this, they
prove that if a blockchain protocol is secure under the $\mathcal{F}_{tree}$
model, it is secure under the random oracle model for $\mathsf{poly}(\kappa)$
number of rounds as well. We can employ this result in transferring our
security definitions in Section 5 to the more realistic random oracle model
for hashing. For example, Theorem 2 would imply that an adversary without a
majority of the mining power cannot create a longer-fork from before a honest
node’s trimming point at any point during the $\mathsf{poly}(\kappa)$ rounds
of blockchain execution (instead of infinite number of rounds). Similar
arguments hold under the Bitcoin Backbone model[23] as well.

##  Appendix 0.J Optimizing Storage with Stateless Blockchains

Our trimming protocol optimizes the amount of cold storage required to
represent the PoW in the blockchain. In this section, we describe how our work
can be interfaced to other methods that optimize the storage of the _state_.
In hybrid nodes, states need to be stored both in cold and hot storage. The
state at the trimming point, $\operatorname{\mathsf{state}}(B^{\prime}_{t})$,
needs to be stored in cold-storage in order to recover the state at the chain
tip when forks are created. Conversely, the state at the tip of the chain,
$\operatorname{\mathsf{state}}(B_{t})$, needs to be stored in hot-storage in
order to perform transaction and block validation. Along with the length of
the blockchain, the size of the blockchain-state is also rapidly increasing
with time. For instance, at the time of writing Bitcoin’s UTXO state is almost
4GB in size, which motivates lessening high storage and verification time
burdens by extending our work to optimize both the state’s cold-storage at the
trimming point, and its hot-storage at the chain tip.

So far, we have described that storing state-commitments in the blocks enables
one to securely establish the state of a trimmed chain, by use of the
$\mathsf{state\mathchar 45\relax verify}$ protocol described in Algorithm 3.
In a different line of work, called _stateless blockchains_ , state-
commitments are used to reduce the amount of hot-storage required for
transaction validation, thus speeding up validation. In this section, we
illustrate that when hybrid nodes are used in stateless-blockchains, then
state commitments can serve a dual purpose: 1) they can be used to establish
the state of the trimmed chain; 2) and, they can be used to perform stateless
transaction validation.

Stateless validation, first proposed by Todd [38], is a scheme where nodes
validating transactions store a short cryptographic state-commitment rather
than the entire state. A client then provides a membership proof that the node
can verify against the commitment. Recently, several constructions have been
developed to perform stateless validation in both the UTXO and account-based
state models using various cryptographic primitives [10, 13, 4, 39, 34, 1,
19]. As an example, the following is how stateless validation of an account-
based state would work via _vector commitments_ , a primitive allowing one to
commit to an ordered sequence of values in a way that allows one to later open
the commitment at a specific position in the sequence, with proof that the
$i^{th}$ value is the $i^{th}$ committed message (see [8]). Suppose an account
is represented by a tuple of the form mapping a public key to a balance:
$(pk_{i},v_{i})$, and that party 1 want to transfer an amount $m$ to party 2.
Then, the transaction submitted by party 1 takes the form
$tx=(pk_{1},v_{1},pk_{2},m,\pi,\sigma)$ where $pk_{1}$ is the public key of
the source account, $pk_{2}$ is the public key of the destination account,
$v_{1}$ is the initial balance of $pk_{1}$, $m$ is the amount being
transferred, $\pi$ is a proof of membership of $(pk_{1},v_{1})$ in the
commitment, and $\sigma$ is a signature of $(v_{1},pk_{2},m,\pi)$ under
$pk_{1}$. In order to validate a transaction, a node checks that $m<v_{1}$,
the validity of the signature, and the validity of the proof with respect to
the public commitment $y(B_{t})$. If the checks passes, the commitment is
updated to reflect the change in the two accounts: $(pk_{1},-m)$ and
$(pk_{2},+m)$. With each such update, users update their proofs $\pi$ so that
they remain valid with respect to the latest commitment.

As a first step, observe that stateless blockchains optimize hot-storage by
obviating the need to store the state at the tip of the chain in the RAM. At
this point, the state at the trimming point is still stored in the cold
storage. We can use this to provide an interface from trimming to stateless
blockchains: Firstly, if the proof for some client becomes outdated past the
trimming point because it was offline for a long while, then the client can
recompute its latest proof by querying a hybrid node for
$\operatorname{\mathsf{state}}(B^{\prime}_{t})$ and the untrimmed chain tail.
Secondly, if a fork in the chain makes the proofs of several clients invalid,
they can all recompute their proofs by contacting the hybrid node similarly.

Now, we describe a way to optimize the cold-storage of the state at the
trimming point as well. In order to do this, we need to make an assumption on
the clients. At every point, the client needs to store its membership proof
corresponding to every block in the untrimmed tail of hybrid nodes. This
enforces a couple of constraints on clients. First, the storage requirements
of a client would scale logarithmically in the length of the blockchain as
well, since the length of the chain-tail grows logarithmically. Second, the
clients need to be online very often so that their proofs never get outdated.
If this is too cumbersome, clients can alternatively delegate the job of
saving and updating proofs to proof-serving nodes [10]. In this case, the
hybrid node need not store the entire state at the trimming point either. This
is because, even in the event that a fork is created in the untrimmed-tail,
all the clients would have their proofs corresponding to the forking point. In
this case, a joining hybrid node would no longer need to use the
$\mathsf{state\mathchar 45\relax verify}$ protocol, since just the state
commitment suffices. The rest of the hybrid node’s protocols proceed as
before.