Resilient Consensus Sustained Collaboratively

Junchao Chen, Suyash Gupta^†, Alberto Sonnino^, Lefteris Kokoris-Kogias^, Mohammad Sadoghi

Exploratory Systems Lab

University of California, Davis

$^{\dagger}$University of California, Berkeley       $^{\ddagger}$ MystenLabs     $\ \ \ \ \ $ $^{\S}$ IST Austria

The recent growth of blockchain technology has accelerated research on
decentralized platforms. Initial blockchain platforms decide on what should
be added to the ledger based on Proof-of-Work () consensus protocol.
requires its participants to perform large computations and
leads to massive energy wastage. Recent blockchains aim to replace
through Proof-of-Stake () and  Malicious Fault-Tolerant () consensus protocols.
However, the safety of the ledger created by
these protocols is at the mercy of the long-term safe-keeping of the private keys of participants.
As a result, these blockchains face long-range attacks.

To ameliorate this situation, we present the design of our novel
Power-of-Collaboration () protocol, which guards existing
and  blockchains against long-range attacks. We show that
can be easily appended to existing blockchains and only marginally
degrades their throughputs.

§ INTRODUCTION

The key goal of any blockchain system is to offer its clients a transparent
and accountable ledger <cit.>. This ledger is maintained by
multiple untrusting parties (servers) that add client transactions to the ledger
in an agreed-upon order by participating in a consensus protocol that can handle
malicious behavior.
Initial blockchain systems such as Bitcoin <cit.> and Ethereum <cit.>
employed the Proof-of-Work () protocol <cit.>, which follows
a computation-oriented consensus model.  protocol requires all its participants
to compete toward solving a complex puzzle. Whichever participant solves the puzzle first,
gets to add a new entry (block) to the ledger and fetches a monetary reward.
The work done by other miners goes to waste, and therefore
protocols are infamous for massive energy wastage <cit.>.

This motivated the blockchain community to adopt two other categories of protocols:
(1) Proof-of-Stake () protocols and (2) traditional Malicious Fault-Tolerant
()[In this paper, we intentionally refrain from the commonly accepted terminology of
Byzantine behavior that may carry a negative and discriminatory connotation.
We further adhere to ACM's D&I policy, and instead of using the traditional phrase
Byzantine Fault-Tolerant (bft), we coin the term Malicious Fault-Tolerant
() to refer to protocols that can handle malicious attacks.]

consensus protocols.  protocols advocate for a stake-oriented model where the
node with the highest stake (or wealth) gets to add a new block to the ledger <cit.>.
Traditional  protocols advocate for an authenticated communication oriented architecture,
where each node gets an equal chance (a vote) to add an entry to the ledger; agreement on the
next block is reached through successive rounds of vote exchange <cit.>. There
also exists blockchains that employ both  and  for yielding efficient
consensus <cit.>. However, all of these types of protocols are vulnerable to
long-range attacks <cit.>. These long-range attacks pose
unprecedented dangers; a malicious party can re-write the full history of the ledger.

and  protocols suffer from long-range attacks as, in these
protocols, adding a new block to the ledger is computationally inexpensive. Each block
added to the ledger includes the digital signatures of a quorum of participants, which proves
that this quorum agreed to add this block to the blockchain. To perform a long-range attack on
such blockchains, an adversary needs to simply compromise the private keys of the honest participants. Unsurprisingly, stealing private keys
is a common attack, and some of these attacks have led to losses of up to $200
million <cit.>. Even if was assume there is a negligible
possibility of stealing a large number of keys, which is not the case, an adversary only needs access
to the keys of old participants. Such participants may no longer have any stake in the system,
and based on the Tragedy of Commons theory <cit.>, “rational” participants will
opt for earning incentives by simply selling their old keys to the adversary. An adversary can
use these keys to create an alternate ledger; such a long-range attack can incur catastrophic
losses for the impacted parties <cit.>. The key observation
is that unlike -chain, any chain that is constructed using  and  protocols
is not self-verifiable and self-contained and relies on long-term external safe-keeping
of private keys.

In this paper, we solve these challenges through our novel
Power-of-Collaboration () protocol[The sketch of our collaborative consensus
idea was presented as an extended abstract in <cit.>.]
that can be easily appended to existing
and  blockchains to guard their ledgers against long-range attacks.

To guarantee a tamper-proof ledger that prevents long-range attacks, like ,
terms its participants as miners and requires them to solve compute-intensive puzzles.

However, unlike ,  requires its miners to work together or collaborate
to solve the compute-intensive puzzle.
Subsequently, each miner is rewarded in proportion to the work it had agreed to complete.
As  miners do not compete with each other, no honest miner's work goes to waste.
Further, this collaboration deters malicious miners as they can neither work alone,
nor can they rewrite the ledger; malicious miners would need more computational power than the combined power
of all the honest miners.
If malicious miners decide to not collaborate with honest miners,
our  protocol quickly identifies such malicious miners and heavily
penalizes them for such behavior.

Prior attempts to eliminate long-range attacks require:
(1) appending  consensus to impacted blockchain <cit.> and
(2) keys-evolving techniques <cit.> and increasing the number
of keys an adversary needs to compromise <cit.>. Unfortunately, these solutions lead
to substantial energy wastage or delay the imminent long-range attack.

Interestingly, this ability to collaborate instead of compete comes with massive opportunities.
(1)  can sustain high throughput of the original blockchain, which
is a major win for  as -based blockchains have been shown to have extremely low throughput.
(2)  guarantees a single blockchain, which is uncommon for  as
the competition between its miners constantly forks the blockchain.
These forks can trigger attacks like selfish mining and $51\%$ <cit.> and
require -based blockchains to continuously monitor and modify the difficulty of the mining.

To show that  is effective in practice, we run a series of experiments.
The goal of our evaluation is twofold: illustrate 's adaptability and scalability.
To meet these goals we append  to a high-performance in-production blockchain platform,
masked as  due to the double-blind policy, which runs  consensus protocol.
We select 's  implementation as it adds approximately $9000$ blocks per second
on a system of $4$ replicas. At this high throughput, we show that our  can commit
$1000$ blocks per second with $64$ miners. Notice that this $1000$ blocks per second is a much
higher throughput than a majority of state-of-the-art blockchains. We prove this by extending
<cit.> framework with  against four popular blockchain systems, namely,
<cit.>,  <cit.>,  <cit.>, and  <cit.>.
This experiment affirms the high scalability of our  protocol.
Next, we list our contributions.

* We present the Power-of-Collaboration () protocol, a sybil-resistant collaborative mining, that can be appended
to existing  and  protocols to guard them against long-range attacks.

*  prevents an honest miner’s work from wasting by requiring all the miners
to collaborate on solving a complex puzzle and rewards each miner for its share of work.
This also makes it impractical for malicious
miners to rewrite the ledger, as to do so, they would need more resources than the combined
resources of honest miners.

*  quickly detects non-conforming behavior by malicious miners and penalizes
them for such activities.

§ PRELIMINARIES

We adopt the standard communication and failure model adopted by most blockchain
protocols <cit.>.
We assume the existence of a blockchain system $\Service$ of the
form $\Service = \{\Replicas{}, \Clients{} \}$. The set $\Replicas$
consists of $\n{\Replicas{}}$ replicas (or stakeholders in case of  protocols)
of which at most $\f{\Replicas{}}$ can behave arbitrarily. In a typical blockchain
system, these replicas store the state and participate in consensus. The remaining
$\n{\Replicas}-\f{\Replicas}$ are honest: they follow the protocol and remain live.
We also assume the existence of a finite set of clients $\Clients$, of which
arbitrarily many can be malicious.

Miner Staking.
Unlike -based systems, we make a similar assumption as common -based systems:
requires the knowledge of total number of miners participating in the mining process.
Each miner that wishes to participate in  mining needs to stake some of its resources.
This staking also determines the amount of collaborative work a miner has to perform
(more on this in Sections <ref> and <ref>).

We denote the set of miners as $\Miners$ and the total number of miners as $\n{\Miners{}}$,
of which at most $\f{\Miners{}}$ can act maliciously.
In Section <ref>, we show how miners can leave and join  mining.
The roles of both miners and replicas can be played by the same party, however,
for the sake of exposition, we denote miners and replicas separately.

Authenticated communication and Adversary model: replicas and miners employ
standard cryptographic primitives such as  and/or digital signatures ()
to sign messages. We denote a message $m$ signed by a replica $\Replica{}$ using
as $\SignMessage{m}{\Replica{}}$. We employ a collision-resistant
hash function $\Hash{\cdot}$ to map an arbitrary value $v$ to a constant-sized digest
$\Hash{v}$ <cit.>. Each replica/miner only accepts a message if it is

We assume the existence of a standard adversary which can corrupt arbitrary nodes,
delay and reorder messages <cit.>. Further, there exists a mechanism for the system $\Service$
to allow replicas to join or leave $\Service$, and this knowledge is percolated
to all the existing members of $\Service$. Each such system $\Service$ should provide
the following guarantees:

If two honest replicas $\Replica{1}$ and $\Replica{2}$ order transactions
$\Transaction{}$ and $\Transaction'$ at sequence numbers $k$, then $\Transaction{} = \Transaction'$.

If a client sends a transaction $\Transaction{}$, then it will eventually
receive a response for $\Transaction{}$.

Like existing  and  blockchains, we assume psuedo-anonymity
for miners in set $\Miners$; they are identified only through their public keys, which
they may hold many.
Similarly, like any  blockchain knows total number of stakeholders,
we know $\n{\Miners}$, which allows us to assign a unique identifier to each miner in the range  $[0, \n{\Miners}]$.

The anonymity for replicas depends on the blockchain system
$\Service$, for example, several  protocols need to know the identities of their
participants before the start of consensus <cit.>.
Each replica is assigned an identifier in the range of $[0, \abs{\Replicas}]$.

§ BACKGROUND

We begin by presenting the necessary conceptual background.

§.§ Proof-of-Work Consensus

Initial blockchain systems, such as  and  employ the
consensus to add transactions to the ledger. Prior to running the  protocol, each miner
[In , machines that participate in consensus are referred to as miners.]
$\Miner \in \Miners$ selects some client transactions and packs them in a block.
This block includes a header, which contains:
(i) the hash of the previous block,
(ii) the Merkle root of all transactions,
(iii) $D$, which determines the difficulty of the puzzle, and
(iv) nonce, the solution of the puzzle, among other fields <cit.>.

Computing the Merkle root of all transactions requires a miner $\Miner$ to compute a
pairwise hash from the leaf to the root. This Merkle root helps to verify if a transaction
was included to create the Merkle tree. The main challenge for any  miner is to determine
the nonce that solves the complex  puzzle, which is essentially a desired hash of the
block (having a specific number of leading zero bits). For this purpose, the miners iterate through
different nonce values and rehash the block until they reach the desired hash. Whichever
miner discovers a valid nonce first, it gets to propose the next block to be added to the chain.
The difficulty of finding the nonce is controlled through the system parameter $D$.

In blockchain systems running  consensus, forks are a common occurrence;
multiple miners may propose the next block with valid nonces at approximately the same time.
In such a case, the protocol states that each miner would only accept the first block it
receives. This could lead to temporary branches or forks, all of which have the same
previous hash. However, these systems assume that this condition would resolve as time passes
because the honest miners would stick to the longest chain—the one with the
largest number of blocks. Eventually, all the shorter forks are discarded, and only the longest
chain survives.
Consequently, to reduce the probability of forks,
-based systems periodically increase the difficulty in finding the nonce.
As a result, the  protocol is often viewed as an energy guzzler:
(1) miners need to perform massive computations to find the nonce, and
(2) only one block is added to the chain (the rest are discarded).

Considering energy costs, -based systems award their miners incentives to act honestly
and follow the protocol. Generally, there are two main sources for the awards:
winner's reward and transaction fees. The winner's reward is given to the miner
who successfully adds a new block to the chain, whereas each client pays a fee for its transaction
to be added to the block.

§.§ Proof-of-Stake Consensus

Due to the performance and energy-inefficiency limitations of the  protocol, several recent blockchain systems have advocated
a transition to the  consensus protocol <cit.>. In  protocols,
participants earn the opportunity to add the next block to the blockchain based on their invested stake.

Often, the stake is equivalent to a monetary token or currency. As a result, the higher the stake a
miner invests, the greater the opportunities it receives to add a block. Once a stakeholder
proposes the next block, all the other participants also sign this block, which acts like an agreement
among the participants.

§.§ Long-range attack on  and

Among many other challenges, the key challenge for any -based system is long-range attacks
like posterior corruption <cit.>. This attack aims to create an alternate
history by re-writing the ledger.

To do so, a malicious party tries to compromise the private keys of the honest parties.
Alternatively, an adversary can buy keys from rational old stakeholders (who no longer
have any stake in the system) by offering them incentives in exchange for their keys.
Once an adversary has access to the private keys of honest stakeholders, it can create arbitrary
blocks and sign them with the compromised keys. Next, we illustrate a
simple long-range attack.

Assume a  blockchain: $\block_1, \block_2, ... \block_k, ... \block_n$.
Say malicious stakeholders have access to the private keys of all the honest stakeholders and
decide to create an alternate ledger, starting from the $k$-th block.
Additionally, these malicious parties will eventually get chances to propose new blocks.
So, the blockchain at these malicious stakeholders will look as follows:
$\block_1, \block_2, ... \block_k', ... , \block_n', \block_{n+1}'$, which they will reveal to everyone.
Any new stakeholder joining this system cannot distinguish between these two chains
and will choose the longest chain. Similarly, the existing honest stakeholders will forfeit
their chain and switch to the malicious chain.

In hindsight, if the private keys of honest parties are compromised, all the bets are off.
A common assumption made by existing  and  protocols is that malicious parties
cannot impersonate honest parties. But, recent security
breaches <cit.> illustrate that
hackers can easily compromise millions of accounts, which in turn allows malicious parties to
impersonate and forge messages or blocks. Hence, we argue that the security of any ledger should not solely
rely on the security of the private keys of its administrators.

This highlights an unprecedented fragility in the design of existing  and  systems:
the only proof attached to each block is the signatures of a majority of participants.
As the consensus mechanism of these protocols is computationally cheap, any malicious party
that has access to the private keys of honest parties can trivially create an alternate ledger
or history. This is where -based systems differ; to rewrite the ledger, a malicious
party has to solve computationally expensive puzzles. Longer the blockchain, the harder to replace
existing blocks with desired blocks; not to forget that new blocks are being proposed continuously.

Existing attempts to resolve long-range attacks are either unscalable or unsecure <cit.>.
We discuss these in  <ref>.

§ POWER-OF-COLLABORATION

One possible solution to prevent long-range attacks on  and  blockchains
is to force each committed block from these chains to undergo
consensus <cit.>. However, -based chains yield extremely
low throughput, consume massive energy, and can lead to forks in the chain.
Our solution to this problem is to append our novel  protocol to an existing blockchain
system. Our  protocol offers the following appealing properties:

*  Tamper-proof ledger.
guards the ledger against long-range attacks like posterior corruption.

*  Minimal energy costs.
Unlike ,  requires miners to collaborate to solve the compute-intensive puzzle,
which prevents competition among miners, utilizes the efforts of each miner, and
helps to conserve energy.

*  No forks and selfish mining attacks.
Collaboration allows  to prevent forking of the ledger and selfish mining by malicious miners.

*  Sustainable throughput and latency.
's collaboration allows it to continue offering clients high throughput at a minimal
increase to the latency.

Transactional flow in a system $\Service$+.

Figure <ref> illustrates the transactional flow.
Each client sends its transaction to the replicas participating
in a blockchain system $\Service$. This system may run any  or  protocol
of its choice to reach consensus on the client transactions. Once the replicas commit
a batch of client transactions, they gossip this batch to the  miners.
Following this, the miners collaboratively run the  protocol
to add this batch to the tamper-proof ledger. This requires finding a valid nonce,
which they forward to the replicas.  leverages the consensus protocol run by the system
$\Service$ to select and attest a valid nonce. A selected nonce acts
as one of the transactions in the next batch, therefore, negligible overhead for
replicas of $\Service$.

Sybil Resistance.
On the one hand,  blockchains resist Sybil attacks because their miners do not benefit from creating fake identities;
the only way for a miner to propose the next block is by solving compute-intensive problem.
On the other hand, prior to any round of consensus,  blockchains verify the identities of all the participants and
blockchains require all participants to invest their monetary resources, which they cannot arbitrarily takeout.
Like , any miner that wishes to participate in  needs to invest its monetary resource, and
the value of its invested resources determines the proportion of its work and rewards.

Next, we discuss our  assuming no attacks (good case).
Later, we explain how we handle malicious attacks.

§.§ Client Transaction Ordering

Prior to running , we expect the blockchain system $\Service$ to reach
consensus on client transactions. For , the consensus run by $\Service$
is a black-box. The system $\Service$ is free to run any consensus protocol of
its choice. It needs to only provide  with committed batches of transactions.

Our use of the term “committed” implies that each committed batch of transactions
has been accepted by a quorum of replicas of $\Service$ and will persist across
adversarial failures. For instance, in  protocols like  <cit.> and
<cit.>, blocks are committed when they have quorum
certificates from $2\f{\Replicas}+1$ replicas. In several other blockchain systems,
a batch of transactions is assumed committed if it is at a specific depth in the blockchain.
A depth indicates the position of the block in the blockchain; the larger the depth of a
block $\block$, the greater the number of blocks that succeed $\block$ and the harder
it is for another fork to overtake this chain.

The assumption of  miners working with only committed batches has two advantages:
(1) It frees  from having any knowledge on the consensus run by $\Service$, and
(2)  miners will not waste their resources on batches that may not persist.

Achieving this requirement of committed blocks is also rather trivial.
We expect honest replicas to follow the protocol and only forward committed blocks to the miners.
Additionally, we require  miners to download the blocks added to the blockchain and
initiate mining on a block only if it has been committed by $\Service$.

(1.75,   1) edge ++(10, 0)
(1.75,   2) edge [blue!50] ++(10, 0)
(1.75,   3) edge ++(10, 0)
(1.75,   4) edge [yellow!50!black!30]++(10, 0);

[label,below,yshift=3pt] at (2.8, 1) Block;
[label,below,yshift=-4pt] at (2.8, 1) Creation;
[label,below,yshift=3pt] at (4.3, 1) Nonce;
[label,below,yshift=-4pt] at (4.3, 1) Discovery;
[label,below,yshift=3pt] at (5.8, 1) Nonce;
[label,below,yshift=-4pt] at (5.8, 1) Announce;
[label,below,yshift=3pt] at (7.3, 1) Nonce;
[label,below,yshift=-4pt] at (7.3, 1) Attest;
[label,below,yshift=3pt] at (8.8, 1) Consensus;
[label,below,yshift=-4pt] at (8.8, 1) in $\Service$;
[label,below,yshift=3pt] at (10.3, 1) Nonce;
[label,below,yshift=-4pt] at (10.3, 1) Attested;

[thin,draw=black!75]   (2, 1) edge ++(0, 3)
(3.5, 1) edge ++(0, 3)
(5, 1) edge ++(0, 3)
(6.5, 1) edge ++(0, 3)
(11, 1) edge ++(0, 3);
[thin,draw=black!75,dashed](8, 1) edge ++(0, 3);
[thin,draw=black!75,dashed](9.5, 1) edge ++(0, 3);

at (4.3, 2.5)

[0, 1]

[2, 3]

[4, 5]

[left] at (1.8, 1) $\Miner_3$;
[left] at (1.8, 2) $\Miner_2$;
[left] at (1.8, 3) $\Miner_1$;
[left] at (1.8, 4) $\PBFT{}$;

[->] (2, 4)
edge (3.5, 3)
edge (3.5, 2)
edge (3.5, 1);

[->] (5, 2)
edge (6.5, 3)
edge (6.5, 1);
[->] (6.5, 3)
edge (8, 4);
[->] (6.5, 2)
edge (8, 4);
[->] (6.5, 1)
edge (8, 4);
[->] (9.5, 4)
edge (11, 3)
edge (11, 2)
edge (11, 1);

protocol with miners $\Miners{} = \{\Miner_1, \Miner_2, \Miner_3\}$.
The solution space $\Slice{} = [0,5]$ is divided into three
slices $([0,1], [2,3], [4,5])$. Post creating a block, each miner
tries to discover a nonce in its slice.
Assume the valid nonce is $2$, which $\Miner_2$ discovers.

§.§ Chain Communication

Once the blockchain system $\Service$ has committed a block, we require it to forward the
committed block to  miners. A popular way to achieve this task is to use a
gossip protocol, which determines the number of parties
acting as senders and as receivers. In this paper, we assume that each replica
in $\Service$ gossips the committed block to all its neighboring miners.
Notice that existing blockchain systems like Bitcoin and Ethereum also use this
gossip protocol to exchange blocks among their nodes.
All of these systems (including ) make a simplifying assumption that each node
is connected to sufficient number of honest nodes, which helps to disseminate the messages.
An efficient alternative to gossip is the Information Dispersal Algorithm <cit.>,
while a reliable alternative to the gossip protocol is to use Reliable Broadcast <cit.>.

§.§ Collaborative Mining

Once a miner receives the next committed block from $\f{\Replicas{}}+1$ replicas in $\Service$,
it prepares for mining this block.
Essentially, an honest miner can only be certain that it is going to mine the correct next block if
it receives the same block gossiped by $\f{\Replicas{}}+1$ replicas.
Next, we explain the  protocol under the assumption that each miner knows
the next block to mine.
In case this assumption is not met, it is trivial
to resolve this situation by requiring each  miner to communicate all the committed blocks
it has received.

mining aims to reliably append the committed blocks to the ledger such that it can
withstand long-range attacks.
We term  mining as collaborative because, unlike  mining,
miners do not compete with each other to propose the next block.
As a result,  mining consumes and wastes significantly less energy.
However, like , our
also attaches a computational proof to each mined block, which proves that this block was
correctly mined.

supports collaboration by dividing the  hash computation into $\n{\Miners}$ disjoint
sub-problems and requires each miner to work on a distinct predetermined sub-problem (refer to Section <ref>). Assume $\Slice{}$
is the solution space for a  hash computation; the set of numbers a miner has to try to find a
valid nonce. In our  protocol, without the loss of generality, we divide the solution
space $\Slice{}$ into $\n{\Miners}$ equal slices, $\{ \Slice{1}, \Slice{2}, \cdots \Slice{\n{\Miners}} \}$,
such that:

$\Slice{1} \cap \Slice{2} \cap \cdots \cap \Slice{\n{\Miners}} = \varnothing$  and   $\Slice{1} \cup \Slice{2} \cup \cdots \cup \Slice{\n{\Miners}} = \Slice{}$

Our  protocol assigns slice $\Slice{1}$ to miner $\Miner_{1}$, $\Slice{2}$
to $\Miner_{2}$, and $\Slice{i}$ to $\Miner_{i}$, $i \in [1,\n{\Miners}]$.
As each miner is working on a reduced solution space, so if a  miner takes time $\tau$ to
find a valid nonce on the solution space $\Slice{}$, then in , if all the miners are
honest, the time required to find the nonce is $\BigO{\dfrac{\tau}{\n{\Miners{}}}}$.
Consequently,  leads to reduced energy consumption by collaboratively finding solutions while
eliminating the significant amount of redundant work that arises when parties compete to find
the solution.

§.§  Protocol Steps

From an outside view, our  protocol works in rounds, and within each round, each miner
attempts to find a valid nonce in its slice. There are many ways to divide the solution space
into different sizes of $\n{\Miners{}}$ disjoint slices. For example, like  <cit.>,
can assign miners with higher stakes a larger number of slices. We discuss more on
this in Section <ref>. For the sake of exposition, in the following sections,
we assume that the solution space $\Slice{}$ is deterministically divided into $\n{\Miners{}}$
disjoint equal slices by each miner.

In Figure <ref>, the solution space $\Slice{} = [0,5]$ is divided among three miners.
The three slices are: $\Slice{1} = [0,1]$, $\Slice{2} = [2,3]$, and $\Slice{3} = [4,5]$.
Assume the valid nonce $2$ lies in the slice of miner $\Miner_2$.
Once $\Miner_2$ finds the nonce, it broadcasts it to all the miners,
following which each miner requests the replicas of $\Service$ to attest this nonce.

[xscale=1.4,list/.style=minimum width=1.8cm,rectangle split, rectangle split parts=2,draw, rectangle split]

[list] (A) at (-1.2, 0) hashtwo[$\Transaction_1,\Transaction_{100}$];
[list] (B) at (0.3, 0) hashtwo[$\Transaction_{101}, \Transaction_{200}$];
[list] (C) at (1.8, 0) hashtwo[$\Transaction_{201}, \Transaction_{300}$];
[list] (D) at (3.3, 0) hashtwo[$\Transaction_{301}, \Transaction_{400}$];
[above] at (A.north) Block $1$;
[above] at (B.north) Block $2$;
[above] at (C.north) Block $3$;
[above] at (D.north) Block $4$;
(D.text west) edge[->] (C.text east)
(C.text west) edge[->] (B.text east)
(B.text west) edge[->] (A.text east)
(A.text west);

[decoration=brace,amplitude=8pt,mirror,decorate,thick,blue!50!black!90] (-1.1, -0.6) – (0.2,-0.6);

[decoration=brace,amplitude=8pt,mirror,decorate,thick,green!50!black!90] (2, -0.6) – (3.3,-0.6);

[list] (E) at (-0.5, -1.9) hashtwo[$\Transaction_{1}, \Transaction_{200}$];
[list] (F) at (2.5, -1.9) hashtwo[$\Transaction_{201}, \Transaction_{400}$];
[above] at (E.north) Blocks [$1$-$2$];
[above] at (F.north) Blocks [$3$-$4$];
(F.text west) edge[->] (E.text east);

[left] at (1.65, -0.8) $\Service$-blocks;
[left] at (1.6, -1.9) Mined blocks;

Illustrating how  $\Bsize = 2$ contiguous $\Service$-blocks produced by replicas of $\Service$
are aggregated into one mined block of .
Here, each $\Service$-block includes $100$ transactions.

Block Creation.
As stated in Section <ref>,  miners receive blocks from the replicas in $\Service$.
If system $\Service$ yields a high throughput, it can produce blocks at a much higher rate than
the  miners can mine. This will make  mining a bottleneck as the rate at which a new
mined block is added to the ledger is much lower than the rate at which $\Service$ generates
the block. To tackle this challenge, each mined block is composed of $\Bsize > 0$ committed
$\Service$-blocks.[For disambiguation, we use the term “$\Service$-blocks” to refer
to the blocks produced by replicas of $\Service$ and mined block to refer to the block produced by  miners.]
The value of $\Bsize{}$ is a protocol parameter. Another advantage of aggregating multiple
$\Service$-blocks into one mined block is that it helps to reduce the mining costs.

To maintain block ordering by $\Service$,  requires miners to only aggregate $\Bsize$
contiguous $\Service$-blocks. For the sake of discussion, let us assume that each $\Service$-block
is assigned a monotonically increasing sequence number $\Sequence$ and each mined block is
assigned a sequence number $\BlockHeight$. If the last block mined by  miners had sequence
number $\BlockHeight - 1$ and the sequence number of last $\Service$-block added to the $b$-th
block is $\Sequence-1$, then in the $\BlockHeight$-th block, each miner will aggregate the following
blocks: $\Sequence, \Sequence+1,..., \Sequence+\Bsize$ (Figure <ref>, Line <ref>).
Notice that aggregating $\Service$-blocks in this way is safe as (1) these blocks are already
committed by replicas of $\Service$, and (2) miners only aggregate consecutive blocks.

In Figure <ref>, we illustrate the difference between $\Service$-blocks and mined blocks.
The replicas of $\Service$ have committed four $\Service$-blocks starting with sequence number $1$.
Assume $\Bsize = 2$, then each  miner aggregates $2$ consecutive $\Service$-blocks into a mined block.

As each $\Service$-block contains a Merkle root of all the transactions,  miners also
generate a Merkle root for the aggregated block. This is simply the hash of the Merkle roots
of all the aggregated blocks. The only thing remaining is slice discovery. We assume that each
miner is deterministically assigned a slice (<ref>). Specifically, the $i$-th
miner $\Miner_{i}$ knows that a total of $\n{\Miners}$ miners are participating in the
protocol. It uses this information to creates $\n{\Miners}$ slices and assigns itself
the $i$-th slice $\Slice{i}$ (Figure <ref>, Line <ref>).

Nonce Discovery.
Once a miner knows its slice, it starts nonce discovery (Figure <ref>, Line <ref>).
A miner can initiate mining for the $\BlockHeight$-th block only after it knows the valid nonce ($\Nonce$)
for the $(\BlockHeight-1)$-th block (Figure <ref>, Line <ref>). To discover a
nonce, we assume that each miner $\Miner{}$ knows the characteristics of the expected hash (the number
of leading zeroes). Each miner uses this hash information to search in its slice for any value that yields
the desirable hash. This process may require $\Miner{}$ to iterate over all the possible values in its slice.

Nonce Announcement.

Once a miner $\Miner$ computes the expected hash, it creates a message NonceFind,
which includes the discovered nonce and broadcasts this message to all the miners (Figure <ref>, Line <ref>). When a miner receives a NonceFind message, it terminates
the process of nonce discovery if the received nonce is valid. Next, each miner that has access
to a valid nonce gossips this nonce to the replicas of $\Service$ (Figure <ref>,
Lines <ref>-<ref>).

Nonce Attestation.
As mentioned earlier in this section,  leverages the consensus protocol of $\Service$
to attest the nonce. Specifically, when a replica $\Replica{}$ of $\Service$ receives a matching
$\MName{NonceFind}$ message from $\f{\Miners}+1$ miners, it creates a transaction that includes
the received NonceFind message as its data. Whenever it is the turn of $\Replica{}$ to
propose a new block, and if an $\Service$-block containing the $\MName{NonceFind}$ message for the
$\BlockHeight$-th mined block is yet to be proposed, $\Replica{}$ proposes a new block that
includes this message. We expect honest replicas to prioritize nonce transactions over others
to prevent delays in adding newly mined blocks to the ledger.

Chain Append.

When a miner $\Miner$ receives the valid nonce for the $\BlockHeight$-th block from replicas
of $\Service$, $\Miner$ appends this block to its local blockchain and marks the nonce
discovery process for the $\BlockHeight$-th block as complete (Figure <ref>,
Lines <ref>-<ref>). Post this, $\Miner$ executes the
reward transactions in the block, which helps to distribute the reward
(Figure <ref>, Lines <ref>-<ref>). Finally, the miner
begins working on the next block.

Multiple Nonces.
In rare scenarios, two or more miners may find valid nonces that
help to reach the expected hash. Specifically, miners $\Miner_{i}$ and $\Miner_{j}$ may both
discover a valid nonce in their respective slices. This situation is not unique to ,
even complex  computations can have multiple solutions.

In such a situation, we need to ensure that all the miners select the same nonce. Interestingly,
ensuring this is trivial in our model as each nonce is attested by system $\Service$. If the next
proposer for an $\Service$-block receives two or more $\MName{NonceFind}$ messages with distinct
valid nonces, it selects one of them as the solution. When, eventually, this block becomes committed,
all the  miners will have access to the same nonce for block $\BlockHeight$.

§.§ Rewards

Like -based systems,  also needs to incentivize their miners for their computational
resources. However, in  systems, as miners compete with each other to propose the next block,
only the winning miner receives the rewards. Consequently, the remaining miners end up wasting their
resources and are not compensated for their efforts. In contrast,  requires miners to collaborate,
and once a block is added to the ledger, it distributes the rewards among all of them.

If $\Diamond$ is the reward for a miner to find a valid nonce in -based blockchain, then in our
protocol, each $i$-th miner $\Miner_{i}$ receives a reward $\Diamond_i$ proportional to the
size of its slice $\Slice{i}$.

$\Diamond_i = \frac{\abs{\Slice{i}}}{\abs{\Slice{}}} * \Diamond$

Like Bitcoin <cit.>, in , at the time of the creation of a mined block, each miner
in $\Miners{}$ adds $\n{\Miners{}}$ transactions to the block (includes them in the Merkle root).
These $\n{\Miners{}}$ transactions help to deterministically divide the reward among
the miners; $i$-th transaction adds the reward $\Diamond_i$ to the account of miner $\Miner_{i}$.
Hence, when the miner $\Miner_{i}$ has access to the valid nonce, its block already includes all
the transactions. Including the reward transactions in the block does not imply their execution.
Once a miner has access to the nonce attested by replicas of system $\Service$, it executes the
$\n{\Miners{}}$ transactions to update all accounts (Figure <ref>, Line <ref>).

Reward Economics.
In Section <ref>, we briefly discussed the source of miner rewards, which
are composed of transaction fees and a winner's reward. Existing blockchain systems like
Bitcoin advocates the generation of a token (cryptocurrency) that acts as the winner's reward.
We skip diving into the crypto-economics of token generation. However, the general idea behind this
token is that it is a monetary compensation for the computational resources spent by the winning miner.
Hence, we focus on the transaction fees, which are paid by each client that wants its
transactions to be processed.[Systems like Ethereum <cit.> set the maximum allowed
transaction fees.]

Miner-rolerunning at the miner $\Miner_i$ with identifier $i$
$\Miner_i$ receives $\f{\Replicas{}}+1$ matching copies of the next committed $\Service$-block (sequence $k$) such that each copy comes from a distinct replica in $\Service$

Call functions NonceCheck($k$),   SliceCheck($k$),  and NewMine().

NonceCheck$\Service$-block: identifier $k$
$k$ includes a $\MName{NonceFind}$ transaction for block $\BlockHeight$
Let $\Nonce$ be the nonce.
$\Nonce$ is valid
Add $\Nonce$ to block $\BlockHeight$ and terminate  mining for $\BlockHeight$.
Shift round $\ShiftRound > 0$
$\Slice{o} :=$ Slice which contains $\Nonce$.
$\Miners_{mal}$ = $\{ \Miner_{e} \}$, where $e = (o+l-1) \bmod \n{\Miners{}}, ~l \in [1, \ShiftRound]$
Broadcast $\SignMessage{\Message{\MName{Penalty}}{\Miners_{mal}, \BlockHeight, \ShiftRound}}{\Miner}$ to all miners.
Execute the transactions.
Add rewards to the accounts of all miners.
Run function NewMine().

$q$ was the sequence of last committed $\Service$-block in the last mined block $\BlockHeight-1$
$\Miner_i$ has $\Bsize$ committed $\Service$-blocks starting from $q+1$
Create block $\BlockHeight$ such that it includes these $\Bsize$ batches.
If no nonce found for block $\BlockHeight-1$, then create a merged block.
Set shift round $\ShiftRound = 0$ and start a timer $\delta$.
$\Slice{i}$ $:=$ Initial slice assigned to $\Miner_i$.
Run function FindNonce($\Slice{i}$).

FindNonceslice: $\Slice{i}$
Miner $\Miner_i$ tries to find a valid nonce $\Nonce$ in slice $\Slice{i}$.
$\Miner_i$ finds $\Nonce$
$\Miner_i$ broadcasts $\SignMessage{\Message{NonceFind}{\BlockHeight, \Nonce}}{\Miner_i}$ to all miners.

$\Miner_i$ receives $\SignMessage{\Message{NonceFind}{\BlockHeight, \Nonce{}}}{\Miner_j}$ from some miner $\Miner_j$
Verify the nonce and stop the Timer $\delta$.
$\Miner_i$ gossips $\SignMessage{\Message{NonceFind}{\BlockHeight, \Nonce{}}}{\Miner_i}$ to all replicas in $\Service$.

Timer $\delta$ expires while finding nonce for block $\BlockHeight$
$\Miner_i$ broadcasts $\SignMessage{\Message{Shift}{\BlockHeight, \ShiftRound{}}}{\Miner}$ to all miners.

$\Miner_i$ receives $\SignMessage{\Message{Shift}{\BlockHeight, \ShiftRound{}}}{\Miner}$ from $\f{\Miners{}}+1$ distinct miners
Create the certificate $\Certificate$ that includes $\f{\Miners{}}+1$ $\MName{Shift}$ messages.
$\Miner_i$ gossips $\SignMessage{\Message{Shift}{\BlockHeight, \ShiftRound{}, \Certificate}}{\Miner_i}$ to all replicas in $\Service$.

SliceCheck$\Service$-block: identifier $k$
$k$ includes a transaction with certificate $\Certificate$ for block $\BlockHeight$
Let $\ShiftRound$ be the shift round mentioned in $\Certificate$.
Shift round $\ShiftRound = \f{\Miners}$
Terminate  mining for $\BlockHeight$-th block.
Run function NewMine().
$\ShiftRound ++ $.
Reset timer $\delta$.
Last mined slice $\Slice{i}$
$i$ $=$ $(i+1)~\bmod~\n{\Miners}$.
Run function FindNonce($\Slice{i}$).

$\Miner_i$ receives $\SignMessage{\Message{Penalty}{\Miners_{mal}, \BlockHeight, \ShiftRound{}}}{\Miner_j}$ from $\f{\Miners{}}+1$ distinct miners
Create a penalty certificate $\PenaltyCert$ that includes $\f{\Miners{}}+1$ $\MName{Penalty}$ messages.
$\Miner_i$ gossips $\SignMessage{\Message{Penalty}{\BlockHeight, \ShiftRound{}, \PenaltyCert}}{\Miner_i}$ to all replicas in $\Service$.

miner protocol.

§ MALICIOUS ATTACKS

Unsurprisingly, the decentralized nature of blockchain systems makes them a prime target for attack
by malicious parties. By appending  to any existing system $\Service$, we subject $\Service$ to
newer attacks. As a result, in this section we enlist all the possible attacks on
$\Service$ +  and present solutions that can withstand these attacks without
degrading system performance. Following is the list of malicious attacks on .

* Miner does not participate in the  protocol.

* Long-range attacks.

* Nonce equivocation at system $\Service$.

To resolve Attack <ref>, we present our novel slice shifting protocol
that also penalizes malicious miners for their behavior. For Attack <ref>, we rely on
the equivocation resolution mechanism provided by $\Service$. All distributed systems also
need to guard against flooding or denial-of-service attacks. To prevent these attacks,
we follow the best practices suggested by prior works <cit.> and
assume that the replicas and miners use one-to-one virtual communication channels, which
can be disconnected if needed.

[thick,draw=black!75] (0.75,   0) edge ++(21.5, 0)
(0.75,   1) edge ++(21.5, 0)
(0.75,   2) edge [red] ++(21.5, 0)
(0.75,   3) edge ++(21.5, 0)
(0.75,   4) edge [yellow!50!black!30]++(21.5, 0);

[label,below,yshift=3pt] at (1.5, 0) Block [$\block_{1}$];
[label,below,yshift=3pt] at (3.2, 0) Nonce;
[label,below,yshift=-4pt] at (3.2, 0) Discovery;
[label,below,yshift=3pt] at (4.7, 0) Slice;
[label,below,yshift=-4pt] at (4.7, 0) Shift;
[label,below,yshift=3pt] at (6.25, 0) Shift;
[label,below,yshift=-4pt] at (6.25, 0) Certificate;
[label,below,yshift=3pt] at (7.74, 0) Consensus;
[label,below,yshift=-4pt] at (7.74, 0) in $\Service$;
[label,below,yshift=3pt] at (9.2, 0) Shift;

[label,below,yshift=3pt] at (10.7, 0) Nonce;
[label,below,yshift=-4pt] at (10.7, 0) Discovery;
[label,below,yshift=3pt] at (12.2, 0) Nonce;
[label,below,yshift=-4pt] at (12.2, 0) Announce;
[label,below,yshift=-4pt] at (13.8, 0) Nonce;
[label,below,yshift=3pt] at (13.8, 0) Attest;

[label,below,yshift=3pt] at (15.2, 0) Consensus;
[label,below,yshift=-4pt] at (15.2, 0) in $\Service$;
[label,below,yshift=3pt] at (16.7, 0) Nonce;
[label,below,yshift=-4pt] at (16.7, 0) Attested;
[label,below,yshift=3pt] at (18.35, 0) Penalty;
[label,below,yshift=3pt] at (19.9, 0) Penalty;
[label,below,yshift=-4pt] at (19.9, 0) Certificate;
[label,below,yshift=3pt] at (21.3, 0) Consensus;
[label,below,yshift=-4pt] at (21.3, 0) in $\Service$;

[thin,draw=black!75]   (1, 0) edge ++(0, 4)
(2.5, 0) edge ++(0, 4)
(4, 0) edge ++(0, 4)
(5.5, 0) edge ++(0, 4)
(10, 0) edge ++(0, 4)
(11.5, 0) edge ++(0, 4)
(13, 0) edge ++(0, 4)
(17.5, 0) edge ++(0, 4)
(19, 0) edge ++(0, 4);

(7, 0) edge ++(0, 4)
(8.5, 0) edge ++(0, 4)
(14.5, 0) edge ++(0, 4)
(16, 0) edge ++(0, 4)
(20.5, 0) edge ++(0, 4)
(22, 0) edge ++(0, 4);

[left] at (0.8, 1) $\Miner_3$;
[left,red] at (0.8, 2) $\Miner_2$;
[left] at (0.8, 3) $\Miner_1$;
[left] at (0.8, 4) $\PBFT{}$;

at (3.2, 2.5)

[0, 1]

[2, 3]

[4, 5]

[->] (1, 4)
edge (2.5, 3)
edge (2.5, 2)
edge (2.5, 1);

[->] (4, 3)
edge (5.5, 3)
edge (5.5, 2)
edge (5.5, 1);

[->] (4, 1)
edge (5.5, 3)
edge (5.5, 2)
edge (5.5, 1);

[->] (5.5, 3)
edge (7, 4);
[->] (5.5, 1)
edge (7, 4);

[->] (8.5, 4)
edge (10, 3)
edge (10, 2)
edge (10, 1);

[->] (11.5, 3)
edge (13, 2)
edge (13, 1);
[->] (13, 3)
edge (14.5, 4);
[->] (13, 1)
edge (14.5, 4);
[->] (16, 4)
edge (17.5, 3)
edge (17.5, 2)
edge (17.5, 1);
[->] (17.5, 3)
edge (19, 2)
edge (19, 1);
[->] (17.5, 1)
edge (19, 3)
edge (19, 2);

[->] (19, 3)
edge (20.5, 4);
[->] (19, 1)
edge (20.5, 4);

at (10.7, 2.5)

[2, 3]

[4, 5]

[0, 1]

Slice shifting procedure: assume $2$ is the valid nonce and is present in the slice
of malicious miner $\Miner_2$. $\Miner_2$ fails to broadcast $2$, which triggers slice shifting;
and with help of replicas of $\Service$, once $2$ is found, it is penalized.

§.§ Slice Shifting

Each honest  miner is expected to search for a nonce in its slice until it receives a
valid nonce from another miner or it has exhausted its slice. A malicious miner may not follow this
behavior; it may want to disrupt the process of nonce finding. If the malicious miners are fortunate
and the nonce is present in their slices, then honest miners may never receive the nonce, and
will come to a halt. We aim to quickly resolve such a situation and prevent further
performance degradation. We do so by running our novel slice shifting algorithm that switches
miner slices under failures. This is done with the aim that when an honest miner has access to the
slice held by a malicious miner, it can discover the nonce in that slice and broadcast it to other miners.

Figure <ref> illustrates the slice shifting protocol. Assume the nonce lies in
slice $[2,3]$ and miner $\Miner_2$ fails to announce the nonce. Eventually, honest miners will
timeout and trigger slice shifting protocol. These miners must create a certificate to prove that
a majority wants to do slice shifting. They send this certificate to the replicas of $\Service$
for attestation. Post this, each miner works on a new slice. Once, they discover the nonce, they
initiate the process of penalizing $\Miner_2$.

Timer Initialization.
Honest  miners, who have exhausted their slice search space and do not have a valid nonce,
need a mechanism to make progress. We follow existing  works and require each miner to set
a timer before it starts mining a slice. Specifically, each miner sets a timer $\delta$ for
the $\BlockHeight$-th block (Figure <ref>, Line <ref>)
and stops $\delta$ when it has a valid nonce for the $\BlockHeight$-th block.

Malicious Miner.
In the case $\Miner{}$'s timer $\delta$ expires before it has access to a valid nonce, $\Miner{}$
broadcasts to all the other miners that it wishes to initiate the slice shifting protocol
(Figure <ref>, Line <ref>). The slice shifting protocol runs for at
most $\f{\Miners{}}$ rounds and deterministically switches slices assigned to each miner.
A round of slice shifting only takes place when at least $\f{\Miners{}}+1$ miners request to do so.
Specifically, when a miner $\Miner_{i}$ timeouts, it creates a message
$\Message{\MName{Shift}}{\BlockHeight, \ShiftRound}$ and broadcasts this message to all the other
miners. Here, $\ShiftRound$ represents the slice shifting round, which is initially set to
zero. When $\Miner{}$ receives $\MName{Shift}$ messages from $\f{\Miners{}}+1$ distinct miners,
it requests the replicas of system $\Service$ to help reach a consensus on slice shifting
(Figure <ref>, Line <ref>). To make this request, each miner must broadcast
a certificate $\Certificate$ that includes $\f{\Miners{}}+1$ $\MName{Shift}$ messages.

Shift Attestation.
When replicas of $\Service$ receive a signed $\Certificate$ from $\f{\Miners{}}+1$  miners,
they agree to attest this slice shift. This attestation requires $\Service$ to run consensus on this
certificate $\Certificate$. It does so by adding $\Certificate$ as a transaction in the next block.
Note: consensus on $\Certificate$ is like consensus on any transaction where $\Certificate$ acts
as the transactional data. Post consensus, as mentioned in Section <ref>, all the replicas
gossip this block to the miners.

Once a miner $\Miner{}$ receives a $\Service$-block from $\f{\Replicas}+1$ replicas that includes
a committed certificate $\Certificate$, it assumes it is time to shift its slices. Following this,
it increments the shift round $\ShiftRound$ by one and mines the next slice (Figure <ref>,
Lines <ref>-<ref>). Specifically, if in shift round $\ShiftRound$, $\Miner_i$
was responsible for mining slice $\Slice{i}$, in round $\ShiftRound+1$, $\Miner_i$ will mine slice
$\Slice{j}$, where $j = (i+1) \mod \n{\Miners{}}$. Again, before mining for round $\ShiftRound+1$, $\Miner{}$
restarts the timer $\delta$ for the $k$-th block.

It is possible that the timer $\delta$ again timeouts, due to more failures. In such a case, $\Miner_i$ would
need to initiate another round of slice shifting. However, this slice shifting protocol would occur
for only $\ShiftRound = \f{\Miners}$ rounds (with high probability).

No nonce – Merge.
In -based systems like Bitcoin, it is possible that a miner may not find any valid nonce
that helps it to reach the expected hash. In such a case, the miner modifies the variable fields of the block,
such as timestamp, Merkle root, and block version, and initiates finding the nonce for this new block. This
strategy works for systems like Bitcoin as each node independently decides the contents of the block it wants
to mine next. However, in , miners mine the slices of the same block.

As a result, it is possible that even after $\ShiftRound = \f{\Miners{}}$ rounds, honest miners do not have
access to a valid nonce. Such a case takes place if no value in any slice can yield the expected hash. To
resolve this case, we require the miners to terminate their search for the nonce and initiate the merge
process. The aim of merging blocks is to increase the probability of reaching the expected hash.

For instance, for the $\BlockHeight$-th block, if a miner $\Miner{}$ receives a certificate $\Certificate$
from $\Service$ replicas, which has shift round $\ShiftRound = \f{\Miners{}}$, $\Miner{}$ concludes that
no valid nonce exists for the $\BlockHeight$-th block (Figure <ref>, Line <ref>).
Following this, $\Miner{}$ creates a new block that merges contents of the $\BlockHeight$-th and
$(\BlockHeight+1)$-th blocks (Figure <ref>, Line <ref>). This new merged block now
serves as the $\BlockHeight$-th block and miners attempt to find the nonce for this new block. The merged block
includes a Merkle root, which is the hash of all the transactions in $\BlockHeight$ and $(\BlockHeight+1)$-th blocks.

Penalty for Slice Shifting.
Frequent slice shifting due to malicious miners will be detrimental to the performance of our  protocol;
it forces honest miners to do more work and wastes their resources. To discourage malicious attacks, we
heavily penalize malicious miners. Specifically, we require each miner to track the number of
shifts ($\ShiftRound$) it took to find a valid nonce and to identify the miners that failed to perform this task.

In our  protocol, identifying malicious miners responsible for $\ShiftRound$ shifts is a trivial
task for honest miners. When a miner  receives a valid nonce for the $\BlockHeight$-th block
in shift round $\ShiftRound$ ($1 \leq \ShiftRound \leq \f{\Miners{}}$), it identifies malicious miners
based on the slice containing the valid nonce. Let $\Slice{j}$ be the slice, then:

\begin{equation*}
\Miners_{mal} = \{ \Miner_{i} \}, \text{ where } i = (j+l-1)\bmod \n{\Miners{}}, ~l \in [1, \ShiftRound]
\end{equation*}

Here $\Miners_{mal}$ is the set of malicious miners who caused $\ShiftRound$ rounds of slice shifting.
To penalize these malicious miners, we again invoke the system $\Service$. Specifically, once a
miner $\Miner{}$ has the knowledge of set $\Miners_{mal}$, it sends a
message $\Message{\MName{Penalty}}{\Miners_{mal}, \BlockHeight, \ShiftRound}$ to all the miners
(Figure <ref>, Lines <ref>-<ref>).
Once $\Miner{}$ receives Penalty messages from $\f{\Miners{}}+1$ miners,
it creates a certificate (like it created for slice shifting) that includes these Penalty
messages and broadcasts this certificate to each replica in $\Service$
(Figure <ref>, Line <ref>).

When the replicas of $\Service$ receive a $\MName{Penalty}$ certificate signed by
$\f{\Miners{}}+1$ distinct miners, they add it to a new block for consensus.
Post consensus, replicas of $\Service$ penalize malicious miners by deducting their
stakes ( <ref>).

§.§ Long Range Attacks

Next, we demonstrate the hardness of  against long range attacks.
For this, we follow Example <ref> where starting from the $k$-th block,
malicious parties want to rewrite the ledger.

To do so, malicious replicas would first create an alternate set of $\Service$-blocks
using the compromised private keys of honest parties.
Next, these malicious replicas would forward these $\Service$-blocks
to the malicious miners, who will attempt to forge the  ledger by creating new mined blocks.

Notice that existing honest miners have a local copy of the chain and
will not help malicious miners in creating these new mined blocks.

Assuming that honest miners control enough slices that cover $50\%$ of the solution space,
then malicious miners have at most a $50\%$ chance to find the nonce for each replacement
block that falls within their solution space.

Clearly, the probability of constructing consecutive blocks for malicious miners decreases exponentially.

Let, $\frac{1}{2}$ be the probability that malicious
miners find the solution for the first replacement block. So, the probability that malicious
miners find the solution for the $b$ consecutive replacement blocks is $(\frac{1}{2})^b$, we
refer to this probabilistic limit as the solution space probability bound. If $b \ge 7$,
the probability is $0.7\%$. This task becomes infeasible if the number of blocks to mine is greater
than $7$, not to mention that in parallel, the chain at the honest miners may keep growing.
Notice that in the case malicious miners do not find nonce in their solution space, their work at least doubles
(equivalent to slice shifting) as they need to search for the nonce in slices assigned to honest miners.

Next, we re-examine
from the practical standpoint by demonstrating the actual time required to create an alternative
chain taking into account two important parameters: (1) the age of the chain $\alpha$ (in months)
and (2) the hashing power ratio of the malicious miners over the honest miners $\frac{m}{h}$.

Essentially, it takes $\alpha \times \frac{h}{m}$ months for the malicious miners to reconstruct
an $\alpha$-month-old chain given their overall hashing power ratio of $\frac{m}{h}$. For example,
if the malicious miners hold $\frac{1}{2}$ of the mining power and want to reconstruct a 1-year
old chain, it would require two years' worth of computation to mint an alternative chain of equal
length. Of course, during these two years, the original chain may continue to grow as well.
Of course, if the malicious miners have access to more resources than their honest counterparts,
then they can mine at a greater hashing power, which will allow them to re-write the ledger at a faster rate.
But, this argument holds for even  blockchains, which can be re-written with miners
having more resources than honest miners.
However, what we are able to demonstrate here is that simply compromising the
private keys of honest miner and replicas is not sufficient to launch a long range attack on

Invalid Nonce Attack.
If malicious miners have access to the private keys of honest replicas of $\Service$,
they can even forge the transactions that include nonces and slice certificates.
Such attacks will delay appending the next mined block to the chain, but cannot
force honest miners to accept an invalid nonce.

§ DISCUSSION

We now present a discussion on how  miners join a system $\Service$,
how are the accounts of miners managed, and how is the difficulty of  mining controlled.

§.§ Staking and Account Database

Like existing blockchain systems <cit.>,  needs to reward
(and penalize) miners. To do so,  makes use of the native token provided
by these blockchains (say token $\Token$).

Prior to the start of  mining, replicas of $\Service$ need to create a
-genesis block. This block stores information about the initial set of miners
that wish to participate in the  mining. Each of these miners needs to exchange their
dollars for $\Token$. Each miner $\Miner{}$ stakes a portion of its tokens $\Token_s$
to be eligible for mining. For simplicity, we assume that each miner has to stake at least
$e \cdot \Token_s$, where $e > 0$ and $e$ is a system parameter. Staking implies that
$e \cdot \Token_s$ of the miner $\Miner$ are locked prior to its participation in
mining; $\Miner$ cannot access its $e \cdot \Token_s$ till it is participating
in  mining.

We follow the practices dictated by existing blockchain systems to bootstrap
<cit.>. Each of these systems assumed that the initial founding
members of their network were honest; these members were vetted before being added to the network.
Further, these systems assume that at all times at least $2/3$-rd members are honest. For example,
Ethereum Foundation <cit.>, Avalanche <cit.>, and Cardano <cit.>,
control large stakes in their respective networks to prevent malicious attacks.
In a similar spirit, we assume that at least $51\%$ of the initial set of  miners are honest.

The replicas of $\Service$ need to include the following information to the -genesis block:
(1) total number of miners ($\n{\Miners{}}$),
(2) keys of staking and mining accounts of each miner,
(3) value of staking account of each miner, and
(4) slice identifier for each miner.
This genesis block is the first block of the mined ledger and it is added to the ledger
after replicas of $\Service$ have reached consensus on this block.

To reward or penalize miners, we assume each  miner has two accounts:
stake account and mining account. These accounts are managed as a
NoSQL database. Each account is represented as a key-value pair;
key is the public-key of a miner and value stores the number of
$\Token_s$ held by the miner. We assume that each miner has a local copy of
the account state (i.e., ledger state), and it updates the rewards or penalties
for each miner as per the protocols described in Sections <ref> and <ref>.
Whenever  miners successfully append a new block to the ledger, they are
rewarded with $\Token_{r}$. These $\Token_{r}$ are added to their mining account.
To penalize a malicious miner, $\Token_{p}$ are subtracted from its staking and
mining accounts.

§.§ Miner Reconfiguration

During the execution of our , some miners may want to join or leave the system.
To allow dynamic participation, we make a simplifying assumption that each
miner only leaves at the boundary of consensus; no miner leaves during an ongoing consensus.
This assumption is not surprising as all the  systems make a similar
assumption <cit.>. Even  systems that use a committee of stakeholders
to propose the next set of blocks require the committee members to stay until the next
committee is selected <cit.>.

If a miner $\Miner$ wants to join  mining, it creates a message
$\SignMessage{\Message{JoinMiner}{pk, \Token}}{\Miner}$ and broadcasts this message to
all the replicas of $\Service$. In these messages, $pk$ refers to the public key.
The replicas of $\Service$, on receiving a join request, are expected to prioritize this request
and run consensus on this request. Once the request is successfully committed and received
by existing miners, they initiate the process of appending this request to the ledger.
Post this, the new miner is allowed to join . In the case a new miner wants to join
the system, once the committed transaction is added to the block, each existing miner creates
staking and mining accounts for the new miner in its database. Notably, a new miner can only
join the system if any existing miner is willing to sell its slice (or part of it).

Similarly, when a miner $\Miner$ wants to leave  mining, it broadcasts a
message $\SignMessage{\Message{LeaveMiner}{pk}}{\Miner}$ to all the replicas of $\Service$.
Post appending this request and all the blocks, in which this miner has participated to
the ledger, it can leave  mining. At this point, it is safe to release the $\Token$s of
the outgoing miner. Notably, a miner can only leave the system if either an existing or new
miner is willing to purchase the slice of the miner that wishes to leave the system. Essentially,
leaving the system will be seen as a transaction in which a slice from one miner is transferred to another.

§.§ Difficulty

Difficulty is a measure of how quickly a block can be generated. It determines the computational
resources required to find a valid nonce. Specifically, difficulty states the characteristics of
the expected hash–the number of leading zeroes. The higher the difficulty, the longer the amount
of time it takes a miner to find the valid nonce.

In existing -based blockchain systems, the difficulty frequently changes (mostly increasing)
in an attempt to keep the ledger safe while reducing the probability of forks. When these systems
have lower difficulty, there is a higher probability of two or more miners reaching the valid nonce,
which leads to forks in the blockchain. Hence, by increasing the difficulty as competition increases,
these systems aim to reduce the probability of forks. For example, Bitcoin changes its difficulty
every 2016 blocks <cit.>.

Unsurprisingly, our  has a more stable difficulty as forks are eliminated.
This stable difficulty helps to substantially save computation resources and energy. Every valid
nonce is committed by consensus, which ensures that a malicious miner cannot produce a random nonce.
However, as the hardware technology improves over time, malicious miners may have access to improved
hardware. To keep up with the technological trajectory, the overall problem difficulty is expected to
increase over time. This decision to increase the difficulty will be taken by  and
systems, and all the miners will be informed via committed transactions.

§.§ Performance Analysis

We now illustrate the time and energy required by  mining, in comparison
to traditional -based mining.
We make the following simplifying assumptions:
(1) Each miner has $E$ computational resources, and
(2) Each miner can solve the hash puzzle in $\tau$ seconds.

If a system runs  mining, we conclude the following:

* Assume all miners are working in parallel.

* They all find the nonce at roughly the same time.

* Only one miner wins in proposing the block.

* Total resources consumed $= \n{\Miners} \times E$

* Total time spent $= \tau$

* Total energy $= \n{\Miners} \times E \times \tau$

If a system runs  mining, we conclude the following:

* All the miners are working on their slices in parallel.

* Only one miner finds the nonce.

* Total resources consumed $= \n{\Miners} \times E$

* Total time spent $= \tau / \n{\Miners}$

* Total energy $= E \times \tau$

This illustrates that the energy consumed by  is independent of the number of miners.

§ CORRECTNESS ARGUMENTS

We now state and prove the security properties of .
These properties hold under the standard  assumption stated in <Ref>.
Further, we assume that  is appended to a blockchain system $\Service$, which provides the
safety and liveness guarantees stated <Ref>.

adopts the same partial synchrony model adopted in most consensus systems <cit.>.
It guarantees safety in an asynchronous environment where messages can get lost, delayed or duplicated.
However, liveness is only guaranteed during the periods of synchrony <cit.>.
Additionally,  guarantees fairness for rewards and penalties only under synchrony. We present
our detailed correctness proof in Appendix <ref>, in which we proof the following
Safety, Liveness, and Fairness theorems.

No two conflicting blocks are settled by the  protocol. That is, if two honest miners $\Miner_i$ and $\Miner_j$
add blocks $\block_i$ and $\block_j$ at sequence number $\BlockHeight$, then $\block_i = \block_j$.

Each committed block at $\Service$ is eventually settled by .

No honest miner receives a penalty if (i) it can find a nonce $\Nonce$ within time $\delta$ and (ii) the network is experiencing a period of synchrony.

g     h

Peak throughput and average latency attained by different components of our  architecture.

§ EVALUATION

We implement our  protocol on top of our highly optimized  fabric
written in C++.
provides us access to highly efficient realization of  consensus,
so we only had to implement our  protocol. The simplicity of our  implementation
is evident from the fact that it has 2,400 LOC, while  has 32,215 LOC.

We also extend  benchmarking framework <cit.>
with our  protocol to illustrate that  can be attached to a wide range of leading blockchain platforms such
as  <cit.>,  <cit.>,  <cit.>,
<cit.>, and  <cit.>.
Our evaluation aims to answer the following:

* Batching and scaling of  in ? (<ref>)

* Batching and scaling of ? (<ref>)

* Failures in ? (<ref>)

*  +  versus other blockchains in terms of both performance and energy consumption? (<ref>)

* Blockchain X +  in the  framework? (<ref>)

§.§  Sustainability and Resiliency

We run experiments on Oracle Cloud Infra. (OCI);
each replica or miner uses VM.Standard2.8 architecture
($16$ cores, 8.2Gbps bandwidth, $120$ GB Memory).
For each baseline, we present their peak throughput and least latency
on a variety of cluster sizes: $16$, $32$, $64$, and $120$ nodes
(OCI limited us from reaching $128$ nodes).

We set the number of replicas and miners for  system to $120$.
We require  replicas to run consensus on a batch of $100$ transactions.
Each experiment we run for 30minutes where first 20min are for
warmup and results are collected over last 10minutes.
We average results over three runs to remove noise.
For , we require clients to sign their messages
using ED25519-based  while replicas use CMAC.
In all the systems, clients send the next transaction after receiving
confirmation that their previous block has been committed.

We serve  YCSB <cit.> transactions
from Blockbench <cit.> framework to  replicas.
These transactions are key-value store operations that access a database of
$\SI{600}{k}$ records.

We evaluate our  system against five popular blockchain systems:
<cit.>, Hyperledger Fabric <cit.>,
<cit.>,  <cit.>, and  <cit.>.
We choose to compare against these systems: (1) ,  and
are among the top ten cryptocurrencies by market capital.

(2)  version $1.1$ allows us to compare against a -based system, while
and  permit comparison against -based system.
(3)  and  are two popular permissioned blockchain systems using
Raft <cit.> and  <cit.> consensus algorithms, respectively.

* Scalability and Peak Performance of .
First, we illustrate the effect of batching transactions on  in ; in
Figures <ref>(a) and (b), we vary the batch size from $1$ to 1k.
We observe that  hits the peak throughput when batch size is $150$.
Beyond this, we observe saturation of peak throughput, while there is a significant
increase in latency. This is the case because the queues at replicas are all full and
can no longer process any newer requests, which increases the wait time for client requests.

Next, in Figures <ref>(c) and (d),
we increase the number of replicas from $16$ to $120$ and compare the scalability of
against 's linear consensus, arguably one of the most fine-tuned
state-of-the-art blockchain platform. As expected, on increasing the number of replicas,
there is a drop in the peak throughput (consequential increase in latency)
because there is a corresponding increase in the number of messages communicated per consensus.

In the case of , the no-mempool version has a much lower throughput as the implementation
bottlenecks at the primary replica, which is forced to broadcast all requests.[Based
on our communication with 's authors, we were informed that the no-mempool version
of  is unstable and has not been tested with more than $30$ replicas.]
's mempool version requires replicas to wait for 100ms or to receive 500Kb
of transactions (whichever comes first) before propagating the batch.
As a result, 's mempool variant trades latency for higher throughput.
For , we observe a linear decrease in throughput when scaling from $16$
to $120$ replicas while sustaining well over 100,000 txn/s with nearly 1 second latency
even at $120$ replicas, which even outperforms state-of-the-art  protocol
that is further enhanced with mempool.

* Performance of : Micro Benchmark.
In -based systems, difficulty ($D$) is expressed as the number of leading zeroes
in expected hash <cit.>. Larger the difficulty, the greater the number of
resources needed to find a nonce. As Bitcoin started with difficulty $D = 8$, so in this work,
we experiment $D=8$ and $D=9$. With our available computing power, larger values of $D$ require
$20+$ hours to find a valid nonce, which made the experiment infeasible financially.
Like Bitcoin, we set the number of nonce bits to $42$, which leads to a total solution
space of $2^{42}$.

Now given the peak performance of  (as it was obtained in (<ref>)),
in Figures <ref>(e) and (f), we vary the block size for  to sustain
's throughput. Within each block, we increase the number of transactions committed by
from 120k to 280k. We require the miners to find nonce at $D=8$ and $D=9$.
As $D=8$ is easy to solve,  miners can find the nonce quickly and hit the peak
throughput, which is also the maximum throughput achieved by  at $128$ replicas.
For $D=9$, we observe an increase in throughput with an increase in block size until it hits
peak throughput of . This makes us conclude that our  protocol does not even
bottleneck  that even surpasses 's throughput.

Next, in Figures <ref>(g) and (h), we vary the number of  miners
from $64$ to $128$ on three different block batch sizes. We observe that by increasing the
degree of collaboration (number of miners), there is an improvement in system performance.
Further, larger batch sizes help to quickly hit the peak throughput.

* Resilience to Failures.
We measure two types of failures in our  protocol: malicious miner
and No nonce ( <ref>). In both of these experiments
(Figures <ref>(i) and (j)), we issue the failure at the $10$-th block,
which causes the honest miners to time out and start slice shifting protocol.
For the malicious miner experiment, we run  among $128$ miners, while for
the no nonce case, we run  among $16$ miners. As a result, we also select the highest
block size necessary to hit 's throughput. Despite this, both experiments have a
similar observable trend. There is a drop in throughput at block size $10$ as miners timeout.
Due to this, there is a large stack of pending transactions, which allows miners to
aggregate more transactions in their block and leads to momentary higher throughput.
However, this period soon fades away and the system reaches stable throughput.

* Comparison with Popular Blockchains.
Figures <ref>(k) and (l) show the throughput and latency
attained by four state-of-the-art blockchain systems.
Despite, fine-tuning these systems, we could not reproduce their claimed results
Prior works have also recorded such a performance gap <cit.>.
We observe that  only reaches a peak throughput of 336txn/s at $16$ nodes,
while  attains 700txn/s at $16$ nodes but drops to 70txn/s at $120$ nodes.
Similarly,  attains up to 236txn/s.
However, despite yielding the least throughput, 's throughput remains stable.

Performance of different blockchains with different applications.

§.§ Extending  Benchmark with

blockchain benchmarking suite provides access to a
unifying framework written in Golang for evaluating leading blockchain systems.
is composed of three types of nodes: primary, secondary,
and chain nodes. The primary node is responsible for generating transactions and delivering
them to the chain nodes through secondary nodes (mimicking a mempool functionality). The secondary
nodes assist the primary node in reducing resource overhead, e.g., CPU and network bandwidth,
by disseminating transactions to the chain nodes and collecting results. The chain nodes
run replication protocols (i.e., consensus). The primary node further regulates
the number of transactions per second (TPS) injected into the system, thus controlling the
transactional load.

We integrate our  protocol to five popular blockchains part of the  framework:  <cit.>,
<cit.>,  <cit.>,  <cit.>, and

Our primary goal here is to showcase that  can be easily integrated with these blockchains
and can guard them against long-range attacks with negligible effects on their performance.

To do so, we simply connect + to each of these five blockchains.

To incorporate , we developed a  that provides an interface to
send transactions from  to .
To integrate , we implemented a  agent on each chain node
that periodically fetches blocks from the local chain on the chain node through their .
Essentially, the
provides a unified entry for  to obtain the block data.
Note that in  clients submit requests in an open loop.

Experiment Setup.
For each blockchain, we run the configuration recommended by the  framework.
In their paper,  authors ran experiments on AWS C5.9xlarge (36 vCPUs and 72 GiB memory).
For each blockchain, we deploy one primary and 10 secondaries.
We ran each experiment on the workloads provided by  and quote their observed throughput (TPS):

NasDAQ (168 TPS),

Visa (1000 TPS), Fifa (3483 TPS), Dota 2 (13303 TPS), and Youtube (37976 TPS).

Experiment Results.
Figure <ref> summarizes our findings.  can sustain 1000 TPS and  only 204 TPS; their performance drops significantly when the workload increases.
attains a consistently low throughput in part due to its default block generation
period (15 seconds).  exhibits a more stable performance of
500-600 TPS across workloads. All blockchains suffer from higher latency (as expected) when
the load increases, in a sense, artificially over-saturating the system.
We observe that  can achieve a high throughput of 37,967 TPS, which nearly matching the injected load.
When  is added to any system, we observe that the throughput drops
at most by 10%-20% due to an increased communication and added network latency.
We argue that this is a negligible cost as  helps these blockchains prevent
long-range attacks, which continues to be a major vulnerability in their design.

§ RELATED WORK

has been studied extensively in the literature <cit.>.

A sequence of efforts <cit.>
have been made to reduce the communication cost of the protocols:
(1) linearizing  consensus <cit.>,
(2) optimizing for geo-replication <cit.>, and
(3) sharding <cit.>.

Nevertheless, all of these protocols face long-range attacks <cit.>.

Alternatively, prior works have focussed on designing  protocols that
permit the node with the highest stake to propose the next block <cit.>
However, even these protocols suffer from long-range attacks.

Long-range attack  <cit.> is a known attack against -based blockchain
system that cannot protect from compromised keys of old validators. Existing proposals to protect against such attacks include checkpointing <cit.>,
use of key-evolving cryptography  <cit.>,
or strict chain density statistics.
However, recent studies show that these systems are still unsafe.
As a result, recent works <cit.> have proposed anchoring  chains on a  chain and more concretely
Bitcoin <cit.>.
However, these protocols are designed ad-hoc assuming an external chain for security, and additionally, lack rigorous performance evaluations.
Combined with the fact that as we show in our experiments classic  protocols are orders of magnitude slower than permissioned ones such as
<cit.> and  <cit.> it seems that the state-of-the-art is either performant or secure against
long-range and stake-bleeding attacks. With , we show how to get the best of both worlds,
introducing a secure and performant blockchains.

§ CONCLUSIONS

We present the design of our collaborative mining architecture,
which ensures that each client transaction undergoes a  or  consensus
followed by our novel  mining. On the one hand,  mining prevents long-range
attacks as each block added to the ledger includes a solution to a compute-intensive puzzle;
miners do not waste their resources as they collaborate to solve this puzzle.
On the other hand,  or  consensus guarantees low latency response time to
clients and stable difficulty for  puzzles. This combination allows any
state-of-the-art blockchain enhanced with  to safeguard against long-rage attacks
while yielding higher throughput, lower latency, and lower energy costs compared to existing  -based systems.

This work was supported in part by (1) Oracle Cloud Credits and
related resources provided by the Oracle for Research program and (2) the
NSF STTR under Award Number 2112345 provided to Moka Blox LLC.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abraham, Nayak, Ren, and XiangAbraham
et al2021]
authorpersonIttai Abraham, personKartik
Nayak, personLing Ren, and personZhuolun Xiang.
Good-Case Latency of Byzantine Broadcast: A
Complete Categorization. In booktitleProceedings of the
2021 ACM Symposium on Principles of Distributed Computing (Virtual Event,
Italy) (seriesPODC'21). publisherAssociation
for Computing Machinery, addressNew York, NY, USA,

[Amir, Danilov, Kirsch, Lane, Dolev,
Nita-Rotaru, Olsen, and ZageAmir et al2006]
authorpersonYair Amir, personClaudiu
Danilov, personJonathan Kirsch, personJohn Lane,
personDanny Dolev, personCristina Nita-Rotaru,
personJosh Olsen, and personDavid Zage.
Scaling Byzantine Fault-Tolerant Replication to
Wide Area Networks. In booktitleInternational Conference on
Dependable Systems and Networks (DSN'06). pages105–114.

[Amiri, Agrawal, and El AbbadiAmiri
et al2021]
authorpersonMohammad Javad Amiri,
personDivyakant Agrawal, and personAmr El Abbadi.
booktitleSharPer: Sharding Permissioned Blockchains
Over Network Clusters.
publisherAssociation for Computing Machinery,

authorpersonDerek Andersen.
titleWell-known vulnerability in private keys likely
exploited in $160M Wintermute hack.

[Androulaki, Barger, Bortnikov, Cachin,
Christidis, De Caro, Enyeart, Ferris, Laventman, Manevich, Muralidharan,
Murthy, Nguyen, Sethi, Singh, Smith, Sorniotti, Stathakopoulou, Vukolić,
Cocco, and YellickAndroulaki et al2018]
authorpersonElli Androulaki, personArtem
Barger, personVita Bortnikov, personChristian
Cachin, personKonstantinos Christidis, personAngelo
De Caro, personDavid Enyeart, personChristopher
Ferris, personGennady Laventman, personYacov
Manevich, personSrinivasan Muralidharan, personChet
Murthy, personBinh Nguyen, personManish Sethi,
personGari Singh, personKeith Smith,
personAlessandro Sorniotti, personChrysoula
Stathakopoulou, personMarko Vukolić,
personSharon Weed Cocco, and personJason Yellick.
Hyperledger Fabric: A Distributed Operating
System for Permissioned Blockchains. In
booktitleProceedings of the Thirteenth EuroSys Conference.
publisherACM, pages30:1–30:15.

[Antoniadis, Desjardins, Gramoli, Guerraoui,
and ZablotchiAntoniadis et al2021]
authorpersonKarolos Antoniadis,
personAntoine Desjardins, personVincent Gramoli,
personRachid Guerraoui, and personIgor Zablotchi.
Leaderless Consensus. In
booktitle41st IEEE International Conference on Distributed
Computing Systems. publisherIEEE, pages392–402.

authorpersonJohn Armstrong.
titleAWS Encryption Keys Compromised in OneLogin Data

[Aublin, Guerraoui, Knezevic, Quéma, and
VukolicAublin et al2015]
authorpersonPierre-Louis Aublin,
personRachid Guerraoui, personNikola Knezevic,
personVivien Quéma, and personMarko Vukolic.
The Next 700 BFT Protocols.
journalACM Trans. Comput. Syst.
volume32, number4 (year2015),

[Azouvi, Danezis, and NikolaenkoAzouvi
et al2020]
authorpersonSarah Azouvi, personGeorge
Danezis, and personValeria Nikolaenko.
Winkle: Foiling Long-Range Attacks in
Proof-of-Stake Systems. In booktitleProceedings of the 2nd
ACM Conference on Advances in Financial Technologies.
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, pages189–201.

[Azouvi and VukolićAzouvi and
authorpersonSarah Azouvi and personMarko
Vukolić. year2022.
Pikachu: Securing PoS Blockchains from Long-Range
Attacks by Checkpointing into Bitcoin PoW using Taproot.
journalarXiv preprint arXiv:2208.05408

[Baudet, Ching, Chursin, Danezis, Garillot, Li,
Malkhi, Naor, Perelman, and SonninoBaudet et al2019]
authorpersonMathieu Baudet, personAvery
Ching, personAndrey Chursin, personGeorge Danezis,
personFrançois Garillot, personZekun Li,
personDahlia Malkhi, personOded Naor,
personDmitri Perelman, and personAlberto Sonnino.
State machine replication in the libra blockchain.
journalThe Libra Assn., Tech. Rep

[Bentov, Lee, Mizrahi, and RosenfeldBentov
et al2014]
authorpersonIddo Bentov, personCharles Lee,
personAlex Mizrahi, and personMeni Rosenfeld.
Proof of Activity: Extending Bitcoin's Proof of
Work via Proof of Stake [Extended Abstract]y.
journalSIGMETRICS Perform. Eval. Rev.
volume42, number3 (datedec
year2014), pages34–37.

[Bitcoin WikiBitcoin Wiki2023]
authorpersonBitcoin Wiki.

[Blass and KerschbaumBlass and
authorpersonErik-Oliver Blass and
personFlorian Kerschbaum. year2020.
BOREALIS: Building Block for Sealed Bid Auctions
on Blockchains. In booktitleASIA CCS '20: The 15th
ACM Asia Conference on Computer and Communications Security.
publisherACM, pages558–571.

titleAssets Explorer.

[Castro and LiskovCastro and Liskov2002]
authorpersonMiguel Castro and
personBarbara Liskov. year2002.
Practical Byzantine Fault Tolerance and Proactive
journalACM Trans. Comput. Syst.
volume20, number4 (year2002),

authorpersonJPMorgan Chase.
titleQuorum Whitepaper.

[Chen, Gupta, Rahnama, and SadoghiChen
et al2022]
authorpersonJunchao Chen, personSuyash
Gupta, personSajjad Rahnama, and personMohammad
Sadoghi. year2022.
Power-of-Collaboration: A Sustainable Resilient
Ledger Built Democratically.
journalIEEE Data Eng. Bull.
volume45, number2 (year2022),

[Clement, Kapritsos, Lee, Wang, Alvisi, Dahlin,
and RicheClement et al2009a]
authorpersonAllen Clement, personManos
Kapritsos, personSangmin Lee, personYang Wang,
personLorenzo Alvisi, personMike Dahlin, and
personTaylor Riche. year2009a.
Upright Cluster Services. In
booktitleProceedings of the ACM SIGOPS 22nd Symposium on
Operating Systems Principles. publisherACM,

[Clement, Wong, Alvisi, Dahlin, and
MarchettiClement et al2009b]
authorpersonAllen Clement, personEdmund
Wong, personLorenzo Alvisi, personMike Dahlin, and
personMirco Marchetti. year2009b.
Making Byzantine Fault Tolerant Systems Tolerate
Byzantine Faults. In booktitleProceedings of the 6th USENIX
Symposium on Networked Systems Design and Implementation.
publisherUSENIX, pages153–168.

[Cooper, Silberstein, Tam, Ramakrishnan, and
SearsCooper et al2010]
authorpersonBrian F. Cooper, personAdam
Silberstein, personErwin Tam, personRaghu
Ramakrishnan, and personRussell Sears.
Benchmarking Cloud Serving Systems with YCSB. In
booktitleProceedings of the 1st ACM Symposium on Cloud
Computing. publisherACM, pages143–154.

[Dang, Dinh, Loghin, Chang, Lin, and OoiDang
et al2019]
authorpersonHung Dang, personTien Tuan Anh
Dinh, personDumitrel Loghin, personEe-Chien Chang,
personQian Lin, and personBeng Chin Ooi.
Towards Scaling Blockchain Systems via Sharding.
In booktitleProceedings of the 2019 International Conference
on Management of Data. publisherACM, pages123–140.

[David, Gaži, Kiayias, and RussellDavid
et al2018]
authorpersonBernardo David, personPeter
Gaži, personAggelos Kiayias, and
personAlexander Russell. year2018.
Ouroboros Praos: An Adaptively-Secure,
Semi-synchronous Proof-of-Stake Blockchain. In
booktitleAdvances in Cryptology – EUROCRYPT 2018,
editorpersonJesper Buus Nielsen and
personVincent Rijmen (Eds.). publisherSpringer
International Publishing, addressCham, pages66–98.

[de Vriesde Vries2018]
authorpersonAlex de Vries.
Bitcoin's Growing Energy Problem.
journalJoule volume2,
number5 (year2018), pages801–805.

[Deirmentzoglou, Papakyriakopoulos, and
PatsakisDeirmentzoglou et al2019]
authorpersonEvangelos Deirmentzoglou,
personGeorgios Papakyriakopoulos, and
personConstantinos Patsakis. year2019.
A survey on long-range attacks for proof of stake
journalIEEE Access  volume7
(year2019), pages28712–28725.

[Diem AssociationDiem
authorpersonDiem Association.
titleDiem BFT.

[Dinh, Wang, Chen, Liu, Ooi, and TanDinh
et al2017]
authorpersonTien Tuan Anh Dinh, personJi
Wang, personGang Chen, personRui Liu,
personBeng Chin Ooi, and personKian-Lee Tan.
BLOCKBENCH: A Framework for Analyzing Private
Blockchains. In booktitleProceedings of the 2017 ACM
International Conference on Management of Data. publisherACM,

[Drijvers, Gorbunov, Neven, and WeeDrijvers
et al2020]
authorpersonManu Drijvers, personSergey
Gorbunov, personGregory Neven, and personHoeteck
Wee. year2020.
Pixel: Multi-signatures for Consensus. In
booktitle29th USENIX Security Symposium (USENIX Security
20). publisherUSENIX Association, pages2093–2110.

[El-Hindi, Binnig, Arasu, Kossmann, and
RamamurthyEl-Hindi et al2019]
authorpersonMuhammad El-Hindi, personCarsten
Binnig, personArvind Arasu, personDonald Kossmann,
and personRavi Ramamurthy. year2019.
BlockchainDB: A shared database on blockchains.
journalProceedings of the VLDB Endowment
volume12, number11 (year2019),

[Eyal and SirerEyal and Sirer2018]
authorpersonIttay Eyal and
personEmin Gün Sirer. year2018.
Majority is Not Enough: Bitcoin Mining is
journalCommun. ACM volume61,
number7 (datejun year2018).

authorpersonMatt Franklin.
A survey of key evolving cryptosystems.
journalInternational Journal of Security and
Networks volume1, number1-2 (year2006),

authorpersonMatthew K. Franklin.
A survey of key evolving cryptosystems.
journalInt. J. Secur. Networks
volume1, number1/2 (year2006),

[Gaži, Kiayias, and RussellGaži
et al2018]
authorpersonPeter Gaži, personAggelos
Kiayias, and personAlexander Russell.
Stake-bleeding attacks on proof-of-stake
blockchains. In booktitle2018 Crypto Valley conference on
Blockchain technology (CVCBT). IEEE, pages85–92.

[Gaži, Kiayias, and RussellGaži
et al2018]
authorpersonPeter Gaži, personAggelos
Kiayias, and personAlexander Russell.
Stake-Bleeding Attacks on Proof-of-Stake
Blockchains. In booktitle2018 Crypto Valley Conference on
Blockchain Technology (CVCBT). pages85–92.

[Gilad, Hemo, Micali, Vlachos, and
ZeldovichGilad et al2017]
authorpersonYossi Gilad, personRotem Hemo,
personSilvio Micali, personGeorgios Vlachos, and
personNickolai Zeldovich. year2017.
Algorand: Scaling Byzantine Agreements for
Cryptocurrencies. In booktitleProceedings of the 26th
Symposium on Operating Systems Principles. publisherAssociation
for Computing Machinery, addressNew York, NY, USA,

[Golan Gueta, Abraham, Grossman, Malkhi,
Pinkas, Reiter, Seredinschi, Tamir, and TomescuGolan Gueta
et al2019]
authorpersonGuy Golan Gueta, personIttai
Abraham, personShelly Grossman, personDahlia Malkhi,
personBenny Pinkas, personMichael Reiter,
personDragos-Adrian Seredinschi, personOrr Tamir,
and personAlin Tomescu. year2019.
SBFT: A Scalable and Decentralized Trust
Infrastructure. In booktitle49th Annual IEEE/IFIP
International Conference on Dependable Systems and Networks.

[Gramoli, Guerraoui, Lebedev, Natoli, and
VoronGramoli et al2012]
authorpersonVincent Gramoli, personRachid
Guerraoui, personAndrei Lebedev, personChris Natoli,
and personGauthier Voron. year2012.
titleDiablo-v2: A Benchmark for Blockchain Systems.

[Gueta, Abraham, Grossman, Malkhi, Pinkas,
Reiter, Seredinschi, Tamir, and TomescuGueta et al2019]
authorpersonGuy Golan Gueta, personIttai
Abraham, personShelly Grossman, personDahlia Malkhi,
personBenny Pinkas, personMichael Reiter,
personDragos-Adrian Seredinschi, personOrr Tamir,
and personAlin Tomescu. year2019.
Sbft: a scalable and decentralized trust
infrastructure. In booktitle2019 49th Annual IEEE/IFIP
international conference on dependable systems and networks (DSN). IEEE,

[Gupta, Hellings, and SadoghiGupta
et al2021]
authorpersonSuyash Gupta, personJelle
Hellings, and personMohammad Sadoghi.
booktitleFault-Tolerant Distributed Transactions on
publisherMorgan & Claypool Publishers.

[Gupta, Rahnama, Hellings, and SadoghiGupta
et al2020]
authorpersonSuyash Gupta, personSajjad
Rahnama, personJelle Hellings, and personMohammad
Sadoghi. year2020.
ResilientDB: Global Scale Resilient Blockchain
journalProc. VLDB Endow. volume13,
number6 (year2020), pages868–883.

authorpersonAaron Holmes.
title533 million Facebook users' phone numbers and
personal data have been leaked online.

[Katz and LindellKatz and Lindell2014]
authorpersonJonathan Katz and personYehuda
Lindell. year2014.
booktitleIntroduction to Modern Cryptography
(edition2nd ed.).
publisherChapman and Hall/CRC.

[King and NadalKing and Nadal2012a]
authorpersonSunny King and personScott
Nadal. year2012a.
titlePPCoin: Peer-to-Peer Crypto-Currency with

[King and NadalKing and Nadal2012b]
authorpersonSunny King and personScott
Nadal. year2012b.
Ppcoin: Peer-to-peer crypto-currency with
journalself-published paper, August
volume19, number1 (year2012).

[Kogias, Jovanovic, Gailly, Khoffi, Gasser, and
FordKogias et al2016]
authorpersonEleftherios Kokoris Kogias,
personPhilipp Jovanovic, personNicolas Gailly,
personIsmail Khoffi, personLinus Gasser, and
personBryan Ford. year2016.
Enhancing bitcoin security and performance with
strong consistency via collective signing. In booktitle25th
usenix security symposium (usenix security 16). pages279–296.

[Kohlweiss, Madathil, Nayak, and
ScafuroKohlweiss et al2021]
authorpersonMarkulf Kohlweiss, personVarun
Madathil, personKartik Nayak, and personAlessandra
Scafuro. year2021.
On the Anonymity Guarantees of Anonymous
Proof-of-Stake Protocols. In booktitle42nd IEEE Symposium
on Security and Privacy. publisherIEEE,

[Kotla, Alvisi, Dahlin, Clement, and
WongKotla et al2009]
authorpersonRamakrishna Kotla, personLorenzo
Alvisi, personMike Dahlin, personAllen Clement,
and personEdmund Wong. year2009.
Zyzzyva: Speculative Byzantine Fault Tolerance.
journalACM Trans. Comput. Syst.
volume27, number4 (year2009),

[Kuhring, István, Sorniotti, and
VukolićKuhring et al2021]
authorpersonLucas Kuhring, personZsolt
István, personAlessandro Sorniotti, and
personMarko Vukolić. year2021.
StreamChain: Building a Low-Latency Permissioned
Blockchain For Enterprise Use-Cases. In booktitle2021 IEEE
International Conference on Blockchain (Blockchain).

[Lekssays, Sirigu, Carminati, and
FerrariLekssays et al2022]
authorpersonAhmed Lekssays, personGiorgia
Sirigu, personBarbara Carminati, and personElena
Ferrari. year2022.
MalRec: A Blockchain-Based Malware Recovery
Framework for Internet of Things. In booktitleProceedings
of the 17th International Conference on Availability, Reliability and
Security (Vienna, Austria) (seriesARES '22).
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, Article articleno99,
numpages8 pages.

[Liu, Viotti, Cachin, Quéma, and
VukolicLiu et al2016]
authorpersonShengyun Liu, personPaolo
Viotti, personChristian Cachin, personVivien
Quéma, and personMarko Vukolic.
XFT: Practical Fault Tolerance beyond Crashes. In
booktitleProceedings of the 12th USENIX Conference on
Operating Systems Design and Implementation. publisherUSENIX
Association, addressUSA, pages485–500.

[Loghin, Dinh, Maw, Gang, Teo, and OoiLoghin
et al2022]
authorpersonDumitrel Loghin, personTien
Tuan Anh Dinh, personAung Maw, personChen Gang,
personYong Meng Teo, and personBeng Chin Ooi.
Blockchain Goes Green? Part II: Characterizing the
Performance and Cost of Blockchains on the Cloud and at the Edge.
journalarXiv preprint arXiv:2205.06941

[Madsen, Gaub, Kirkbro, and DeboisMadsen
et al2019]
authorpersonMads Frederik Madsen,
personMikkel Gaub, personMalthe Ettrup Kirkbro, and
personSøren Debois. year2019.
Transforming Byzantine Faults using a Trusted
Execution Environment. In booktitle15th European Dependable
Computing Conference. pages63–70.

authorpersonSatoshi Nakamoto.
titleBitcoin: A Peer-to-Peer Electronic Cash System.

[Nambiampurath and BairdNambiampurath and
authorpersonRahul Nambiampurath and
personKyle Baird. year2023.
title2,000 Crypto Private Keys Stolen From Edge Wallet.

[Naumenko, Maxwell, Wuille, Fedorova, and
BeschastnikhNaumenko et al2019]
authorpersonGleb Naumenko, personGregory
Maxwell, personPieter Wuille, personAlexandra
Fedorova, and personIvan Beschastnikh.
Erlay: Efficient Transaction Relay for Bitcoin.
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, pages817–831.

authorpersonKrzysztof Okupski.
titleBitcoin Developer Reference.

[Ongaro and OusterhoutOngaro and
authorpersonDiego Ongaro and personJohn
Ousterhout. year2014.
In Search of an Understandable Consensus
Algorithm. In booktitleProceedings of the 2014 USENIX
Conference on USENIX Annual Technical Conference.
publisherUSENIX, pages305–320.

authorpersonMichael O Rabin.
Efficient dispersal of information for security,
load balancing, and fault tolerance.
journalJournal of the ACM (JACM)
volume36, number2 (year1989),

[Rahnama, Gupta, Sogani, Krishnan, and
SadoghiRahnama et al2022]
authorpersonSajjad Rahnama, personSuyash
Gupta, personRohan Sogani, personDhruv Krishnan,
and personMohammad Sadoghi. year2022.
RingBFT: Resilient Consensus over Sharded Ring
Topology. In booktitleProceedings of the 25th
International Conference on Extending Database Technology.
publisherOpenProceedings.org, pages2:298–2:311.

authorpersonTeam Rocket.
booktitleSnowflake to Avalanche: A Novel Metastable
Consensus Protocol Family for Cryptocurrencies.
typeTechnical Report.

[Rondanini, Carminati, Daidone, and
FerrariRondanini et al2020]
authorpersonChristian Rondanini,
personBarbara Carminati, personFederico Daidone,
and personElena Ferrari. year2020.
Blockchain-based controlled information sharing in
inter-organizational workflows. In booktitle2020 IEEE
International Conference on Services Computing (SCC).

[Ruan, Dinh, Lin, Zhang, Chen, and OoiRuan
et al2021]
authorpersonPingcheng Ruan, personTien
Tuan Anh Dinh, personQian Lin, personMeihui Zhang,
personGang Chen, and personBeng Chin Ooi.
LineageChain: a fine-grained, secure and efficient
data provenance system for blockchains.
journalVLDB J. volume30,
number1 (year2021), pages3–24.

[Ruan, Dinh, Loghin, Zhang, and ChenRuan
et al2022]
authorpersonPingcheng Ruan, personTien
Tuan Anh Dinh, personDumitrel Loghin, personMeihui
Zhang, and personGang Chen. year2022.
booktitleBlockchains: Decentralized and Verifiable
Data Systems.

[Sartakov, Brenner, Mokhtar, Bouchenak, Thomas,
and KapitzaSartakov et al2018]
authorpersonVasily A. Sartakov, personStefan
Brenner, personSonia Ben Mokhtar, personSara
Bouchenak, personGaël Thomas, and
personRüdiger Kapitza. year2018.
EActors: Fast and flexible trusted computing using
SGX. In booktitleProceedings of the 19th International
Middleware Conference, editorpersonPaulo Ferreira
and personLiuba Shrira (Eds.). publisherACM,

[Shen, Tian, Chen, Chen, Wang, Xu, Xia, and
YanShen et al2020]
authorpersonYouren Shen, personHongliang
Tian, personYu Chen, personKang Chen,
personRunji Wang, personYi Xu, personYubin
Xia, and personShoumeng Yan. year2020.
booktitleOcclum: Secure and Efficient Multitasking
Inside a Single Enclave of Intel SGX.
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, pages955–970.

[Sheng, Wang, Nayak, Kannan, and
ViswanathSheng et al2021]
authorpersonPeiyao Sheng, personGerui Wang,
personKartik Nayak, personSreeram Kannan, and
personPramod Viswanath. year2021.
BFT Protocol Forensics. In
booktitleCCS '21: 2021 ACM SIGSAC Conference on
Computer and Communications Security. publisherACM,

[Sit, Bravo, and IstvánSit
et al2021]
authorpersonMan-Kit Sit, personManuel
Bravo, and personZsolt István.
An Experimental Framework for Improving the
Performance of BFT Consensus for Future Permissioned Blockchains. In
booktitleProceedings of the 15th ACM International
Conference on Distributed and Event-Based Systems (Virtual Event, Italy)
(seriesDEBS '21). publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

[Stathakopoulou, Pavlovic, and
VukolićStathakopoulou et al2022]
authorpersonChrysoula Stathakopoulou,
personMatej Pavlovic, and personMarko Vukolić.
State Machine Replication Scalability Made Simple.
In booktitleProceedings of the Seventeenth European
Conference on Computer Systems. publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

[Tas, Tse, Yu, and KannanTas
et al2022]
authorpersonErtem Nusret Tas, personDavid
Tse, personFisher Yu, and personSreeram Kannan.
Babylon: Reusing Bitcoin Mining to Enhance
Proof-of-Stake Security.
journalarXiv preprint arXiv:2201.07946

authorpersonHarald Vranken.
Sustainability of bitcoin and blockchains.
journalCurrent Opinion in Environmental
Sustainability  volume28 (year2017),

authorpersonGavin Wood.
Ethereum: A secure decentralised generalised
transaction ledger.

[Yin, Malkhi, Reiter, Gueta, and AbrahamYin
et al2019]
authorpersonMaofan Yin, personDahlia
Malkhi, personMichael K. Reiter, personGuy Golan
Gueta, and personIttai Abraham.
HotStuff: BFT Consensus with Linearity and
Responsiveness. In booktitleProceedings of the ACM
Symposium on Principles of Distributed Computing. publisherACM,

[Yuan, Xia, Chen, Zang, and XieYuan
et al2018]
authorpersonRui Yuan, personYubin Xia,
personHaibo Chen, personBinyu Zang, and
personJan Xie. year2018.
ShadowEth: Private Smart Contract on Public
journalJ. Comput. Sci. Technol.
volume33, number3 (year2018),

[Zhang, Xu, Xu, Tang, and ChoiZhang
et al2019]
authorpersonCe Zhang, personCheng Xu,
personJianliang Xu, personYuzhe Tang, and
personByron Choi. year2019.
GEM$^2$-Tree: A Gas-Efficient Structure for
Authenticated Range Queries in Blockchain. In booktitle2019
IEEE 35th International Conference on Data Engineering (ICDE).

§ CORRECTNESS ARGUMENTS

We now state and prove the security properties of .
These properties hold under the standard  assumption stated in <Ref>.
Further, we assume that  is appended to a blockchain system $\Service$, which provides the
safety and liveness guarantees stated <Ref>.

adopts the same partial synchrony model adopted in most consensus systems <cit.>.
It guarantees safety in an asynchronous environment where messages can get lost, delayed or duplicated.
However, liveness is only guaranteed during the periods of synchrony <cit.>.
Additionally,  guarantees fairness for rewards and penalties only under synchrony.

§.§ Safety Argument

We argue the safety of  by relying on the agreement property of the system $\Service$.

No two conflicting blocks are settled by the  protocol. That is, if two honest miners $\Miner_i$ and $\Miner_j$
add blocks $\block_i$ and $\block_j$ at sequence number $\BlockHeight$, then $\block_i = \block_j$.

Assume that honest miners $\Miner_i$ and $\Miner_j$ added two conflicting blocks $\block_i$ and $\block_j$ at sequence number $\BlockHeight$.
We know that each mined block has $\Bsize$ contiguous $\Service$-blocks (<ref>).
So each mined block, including $\block_i$ and $\block_j$ have the same number of $\Service$-blocks.
As both conflicting blocks $\block_i$ and $\block_j$ have the same sequence number $\BlockHeight$, it is safe to assume that mined blocks at
sequence number $ \le \BlockHeight-1$ have the same set of $\Service$-blocks.
This implies that $\block_i$ and $\block_j$ have at least one distinct $\Service$-block.
Miners $\Miner_i$ and $\Miner_j$ must have received this distinct $\Service$-block from replicas of $\Service$.
This can only happen if replicas of $\Service$ committed two distinct blocks at the same sequence number.
But, this is a contradiction as we assume that $\Service$ guarantees a globally consistent view of the transactions.

Similarly, each miner submits a $\MName{NonceFind}$ message to replicas in $\Service$ when it has access to a valid nonce.
The replicas of $\Service$ add this message as a transaction in the next $\Service$-block.
Assume that this $\MName{NonceFind}$ message is in blocks $\block_i$ and $\block_j$ and it is the transaction
on which miners differ.
If this is the case, then replicas of $\Service$ committed different nonce in their $\Service$-blocks.
This contradicts the correctness guarantees provided by $\Service$.

§.§ Liveness Argument

We argue about the liveness of  during periods of synchrony.

An honest miner eventually receives the $k$-th $\Service$-block committed by an honest replica.

We argue this lemma by induction over the serialized communication of committed $\Service$-blocks.
Assuming a history of $k-1$ committed $\Service$-blocks for
which this property holds, we consider the $k$-th committed $\Service$-block.
When an honest replica has a committed $\Service$-block, it reliably broadcasts that block to the miners.
It is thus guaranteed that an honest miner will receive all the committed $\Service$-blocks.

The inductive base case involves assuming that all replicas are initialized with a committed genesis ($k=1$) block, which we can ensure axiomatically.

The first time an honest miner $\Miner_i$ obtains the $\BlockHeight$-th block containing $\sigma > 0$ committed $\Service$-blocks,
it searches for a valid nonce $\Nonce$ in slice $\Slice{i}$.

Upon receiving the $k$-th committed $\Service$-block for the first time, correct miners
call the function $\MName{NewMine}$
either through function NonceCheck (Line <ref> of <Ref>) or SliceCheck (Line <ref> of <Ref>).

If neither of these calls succeed, then NewMine (Line <ref>) is directly called (Line <ref>).
The function NewMine checks if there are $\sigma > 0$ $\Service$-blocks
available, since the last $\Service$-block added to the ledger, for mining.
If so, $\Miner_i$ aggregates these $\Service$-blocks into mined block $b$ (Line <ref>) and calls FindNonce (Line <ref>) to search for a nonce in slice $\Slice{i}$.

If a correct miner does not find a valid nonce $\Nonce$ in slice $\Slice{i}$ to settle block $b$ within time $\delta$, another miner eventually tries it.

While finding nonce, if the timer $\delta$ expires for an honest miner,
it broadcast a message $\textsc{Shift}$ to other miners.
When it receives $\textsc{Shift}$ message from $\f{\Miners}+1$ miners
it creates a certificate $\Certificate$ comprising of these $\MName{Shift}$
messages and broadcasts this $\Certificate$ to all the replicas.
When an honest replica receives $\Certificate$ from at least $\f{\Miners}+1$,
it proposes it in the next block.

The liveness property of $\Service$ ensures that these messages are
eventually committed, and <Ref> ensures that
honest miners are eventually notified of the commit.

On receiving a committed $\Service$-block with a certificate $\Certificate$,
an honest miner $\Miner_i$ calls function SliceCheck.
In this function, $\Miner_i$ resets its timer
(Line <ref> of <Ref>)
and restarts the nonce finding process in slice $\Slice{j}$
(with $j = (i+1)~\bmod~\n{\Miners}$, see Line <ref> of <Ref>)
if it has not already attempted to find a slice for $\f{\Miners}+1$.
Otherwise, it assumes that no nonce can be found for this block and starts a new mining.

As a result, honest miners keep shifting and searching for each other nonces until they are all found.

All honest miners settle block $b$ if a valid nonce $\Nonce$ for block $b$ exists.

When an honest miner $\Miner_i$ finds a nonce $\Nonce$,
it broadcasts $\Nonce$ to the other miners (Line <ref> of <Ref>).
Following this, each miner submits $\Nonce$ to the replicas of $\Service$
(Line <ref> of <Ref>).
The liveness property of $\Service$ ensures that $\Nonce$ is eventually committed
by all honest replicas.

<Ref> then ensures that all honest miners obtain the
corresponding committed $\Service$-block.

We conclude the proof by noting that if the $\Service$-block contains a valid
nonce $\Nonce$, correct miners will settle $b$ (Line <ref> of <Ref>).

Each committed block at $\Service$ is eventually settled by .

Through the liveness property of $\Service$ and <Ref>, we conclude that each honest miner eventually
obtains a block committed by replicas of $\Service$.

<Ref> then ensures that the miner searches for a valid nonce $\Nonce$ to settle this committed $\Service$-block as part of a block $b$.

Finally, an honest miner can find a nonce in its slice $\Slice{i}$ within time $\delta$ with non-zero probability.
If it doesn't, <Ref> ensures that other honest miners will try it again until they succeed.

As a result, correct miners eventually find a nonce $\Nonce$ for block $b$ in their slice within time $\delta$.
<Ref> then ensures that all correct miners use $\Nonce$ to settle block $b$ and thus the committed $\Service$-block.

§.§ Fairness Argument

We argue that  is fair and no correct miners are penalized during periods of synchrony.

There cannot be a penalty certificate $\SignMessage{\Message{Penalty}{\BlockHeight, \ShiftRound{}, \Certificate}}{\Miners}$ unless the timer $\delta$
of at least one honest miner expires.

We start by assuming that there exists a penalty certificate $\SignMessage{\Message{Penalty}{\BlockHeight, \ShiftRound{}, \Certificate}}{\Miners}$
the timers of none of the honest miners have expired.
As each penalty certificate needs signatures of at least $\f{\Miners}+1$ miners and at most $\f{\Miners}$ miners are malicious,
such an assumption is a contradiction.

No honest miner receives a penalty if (i) it can find a nonce $\Nonce$ within time $\delta$ and (ii) the network is experiencing a period of synchrony.

Let's assume an honest miner $\Miner_i$ receives a penalty based on shift round $r$ (Line <ref> of <Ref>).

This implies the existence of a penalty certificate (Line <ref> of <Ref>) including miner $\Miner_i$ in its list of miners to penalize.

<Ref> states that this certificate can only exist if the timer $\delta$ of at least one honest  miner expires.

However, since the $\f{\Miners{}}+1$ miners are honest, they only try to penalize $\Miner_i$ if they did not receive its nonce before $\delta$.

This implies that either miner $\Miner_i$ did not find its nonce before $\delta$ (which is a direct contradiction of assumption (i)), or that its nonce did not reach the $\f{\Miners{}}+1$ honest miners before their timer expires (which is a direct contradiction of assumption (ii)).