#  Minotaur: Multi-Resource Blockchain Consensus

Matthias Fitzi  IOG<EMAIL_ADDRESS>,  Xuechao Wang  University of
Illinois Urbana-Champaign<EMAIL_ADDRESS>,  Sreeram Kannan  University
of Washington at Seattle<EMAIL_ADDRESS>,  Aggelos Kiayias  University of
Edinburgh & IOG<EMAIL_ADDRESS>,  Nikos Leonardos  University of
Athens<EMAIL_ADDRESS>,  Pramod Viswanath  Princeton University
<EMAIL_ADDRESS>and  Gerui Wang  Beijing Academy of Blockchain and Edge
Computing<EMAIL_ADDRESS>
###### Abstract.

Resource-based consensus is the backbone of permissionless distributed ledger
systems. The security of such protocols relies fundamentally on the level of
resources actively engaged in the system. The variety of different resources
(and related proof protocols, some times referred to as PoX in the literature)
raises the fundamental question whether it is possible to utilize many of them
in tandem and build multi-resource consensus protocols. The challenge in
combining different resources is to achieve fungibility between them, in the
sense that security would hold as long as the cumulative adversarial power
across all resources is bounded.

In this work, we put forth Minotaur, a multi-resource blockchain consensus
protocol that combines proof-of-work (PoW) and proof-of-stake (PoS), and we
prove it optimally fungible. At the core of our design, Minotaur operates in
epochs while continuously sampling the active computational power to provide a
fair exchange between the two resources, work and stake. Further, we
demonstrate the ability of Minotaur to handle a higher degree of work
fluctuation as compared to the Bitcoin blockchain; we also generalize Minotaur
to any number of resources.

We demonstrate the simplicity of Minotaur via implementing a full stack client
in Rust (available open source (Minotaurcode, )). We use the client to test
the robustness of Minotaur to variable mining power and combined work/stake
attacks and demonstrate concrete empirical evidence towards the suitability of
Minotaur to serve as the consensus layer of a real-world blockchain.

††journalyear: 2022

##  1\. Introduction

Resource-based Consensus. The fundamental feature of the decentralized
computing paradigm of permissionless blockchains is that participation in the
consensus protocol is enabled by proving possession of a resource. Bitcoin
pioneered this idea based on proof-of-work (PoW), and its implied energy
wastage inspired new designs based on alternative resources such as proof-of-
stake (PoS), proof-of-space (PoSp) and proof-of-elapsed-time (PoD). These
different resources cover the variegated and multidimensional forms of
‘capital’ that the participants bring. Each proof-of-X mechanism is
interesting on their merit in appropriate settings (computation in PoW, memory
and storage in PoSp and time/delay in PoD, tokens/capital in PoS). Further,
the mechanisms trigger different incentives even within the same resource
format; focusing on PoW for example, we see that the hashcash algorithm
(back2002hashcash, ) instantiated by the SHA256 function (sha256, )
implemented in Bitcoin has been replaced by others, including scrypt
(percival2016scrypt, ) and ethash (ethash, ). Each of these different proof-
of-X mechanisms have led to different, and isolated, blockchain ecosystems.

Combining different resources. Given the diversity of incentivization embodied
by different resources, it is a natural question whether it is feasible to
combine their features into a single blockchain design (e.g., hybrid PoW-PoS
permissionless blockchains). The key challenge to combining multiple resources
is in determining the exchange rate, i.e., to what extent the different
resources are translated into power of authority in the system and to extract
security from these resources in an optimal manner. Adapting the exchange rate
dynamically to the participation levels in each resource type, resulting in a
truly fungible notion of resource, is a basic and fundamental goal. By truly
fungible, we mean that the security of the multi-resource consensus protocol
is guaranteed as long as the honest players control a majority of the combined
resources that consist of each resource type in the system — concretely,
$\sum^{M}_{i=1}\beta_{i}<M/2$ where $M$ is the number of resources and
$\beta_{i}$ the adversarial power in the $i$-th resource (this property is
appropriately generalized to any linear combination in Definition 2). We note
that achieving this type of fungibility is beneficial for the security of the
underlying blockchain system as the adversary will be unable to launch a
successful attack by commanding merely $51\%$ in one of the underlying
resources. Next we give some examples of non-fungible hybrid PoW/PoS protocol
designs.

First order hybrid PoW/PoS protocols. Given the basic importance of
incorporating multiple resources in a single blockchain design, there are
several designs of hybrid PoW/PoS protocols in the literature (KinNad12, ;
BLMR14, ; FDKT+20, ; DCFZ18, ; karakostas2021securing, ). These protocols,
however, are either heuristic (lacking a formal security analysis) (KinNad12,
; BLMR14, ; DCFZ18, ), or make assumptions that break fungibility (e.g. honest
majority in stake (FDKT+20, ; DCFZ18, ; karakostas2021securing, ) and/or
static mining power (FDKT+20, )). Indeed, with sufficient assumptions the
problem of a hybrid protocol is trivially resolved. For instance, if we assume
an honest majority in stake (at all time), we can use a committee chosen
randomly from the pool of stakeholders to assist a PoW ledger by regularly
issuing checkpoints (karakostas2021securing, ). However, the security of this
scheme is solely guaranteed by the stakeholders, and the trust is entirely
supported by PoS (not from PoW).

Natural solutions. In fact, if we assume a static setting (where both the
total mining power and total ‘active’ stake are fixed and known to the
protocol designer), a simple solution is the following: PoW and PoS mining
occur in parallel; and whichever PoW or PoS succeeds first, goes ahead and
extends the longest chain. However, there does not appear to be any
straightforward (or otherwise) approach to extend this simple idea to the non-
static setting, since we can no longer normalize the stake and work in the
system when the total mining power is changing and unknown (§4). Even a
fungible combination of work (i.e., total amount of honest work is more than
total Byzantine work) emanating from two different hash functions (thus
allowing two PoW blockchains using the same longest-chain consensus protocol
to co-exist) has been unsolved.

Minotaur Protocol. In this paper we present Minotaur, a blockchain protocol
with proof of fungible work and stake. At its core, Minotaur is a longest
chain protocol that bases its block-proposer schedule on our concept of
_virtual stake_ that fuses active actual stake and work stake. The work-stake
distribution is determined per epoch by measuring the participants’
contributions in hashing power during a prior epoch. Work contribution is
achieved by concurrent PoW mining of _PoW blocks_ (similar to ‘endorser
inputs’ (kiayias2017ouroboros, ) or ‘fruits’ (pass2017fruitchains, )) to be
eventually referenced by main-chain blocks. The work-stake distribution is
then assigned proportionally to a participant’s share of endorser blocks
referenced from the main chain during that epoch; and applying the fairness
mechanisms in (GKL2015, ; pass2017fruitchains, ; kiayias2017ouroboros, ), this
assignment indeed truly represents the PoW-resource distribution among the
participants. Note that this process can be seen as a fine-grained adaptation
of PoW-based committee election such as in (PasShi16, ). Figure 1(a)
illustrates the protocol (a detailed description is given in §5).

Minotaur security is optimal. We show that Minotaur is truly fungible between
work and stake by showing it is secure when the sum of $\omega$ times the
proportion of adversarial hash power ($\beta_{w}$) and $1-\omega$ times the
proportion of the adversarial stake ($\beta_{s}$) is smaller than $1/2$, for
any $\omega\in[0,1]$, a weighing parameter of PoW/PoS (see Figure 1(b) for
$\omega=0.5$). Figure 1(b) also compares the security guarantee of Minotaur
and a couple of non fungible PoW/PoS protocols in the literature (the
checkpointed ledger (karakostas2021securing, ), the 2-hop blockchain (FDKT+20,
), and a few finality gadgets (stewart2020grandpa, ; sankagiri2020blockchain,
; buterin2017casper, ; neu2021ebb, )), with more details in Appendix A. We
give a formal security analysis in §6. The new challenge that we have to
tackle in our security analysis is to show a fairness guarantee in the work-
stake conversion (e.g., a miner with 10% mining power should gain 10% work
stake) in the non-static setting and in the presence of an adversarial
majority of mining power. This requires a new understanding of how to bound
the evolution of mining difficulty in the system compared to techniques used
in previous works and the Bitcoin blockchain, and presents a significant
barrier to surmount in our analysis. One immediate consequence is that
Minotaur can tolerate a 51% mining adversary, as long as there is a
supermajority in honest stake (and vice verse, a 51% stake adversary). We
prove our security guarantee to be optimal, see §3, in the sense that
otherwise the adversary will control the majority of the combined “resource”
in the system and an analogy of Nakamoto’s private chain attack
(nakamoto2008bitcoin, ) could break the security (formal and detailed proof in
§3). We also show that Minotaur is capable of tolerating fluctuations of work
much more effectively than Bitcoin, cf. §6.4.

(a)

(b)

Figure 1. (a) Architecture of Minotaur consensus protocol. (b) Comparison of
security regions achieved by different hybrid PoW/PoS protocols (more details
in Appendix A).

Implementation. We have implemented a prototype of a Minotaur client in about
6000 lines of Rust code (Minotaurcode, ) and provide experimental results to
evaluate the performance of Minotaur under different scenarios. We also
implemented Bitcoin/FruitChain/Ouroboros clients as benchmarks. We use that
client to validate also experimentally that Minotaur can survive more drastic
variations of network hash power, while Bitcoin/FruitChain is no longer live
under the same scenario. We also evaluate practical security concerns, like
private chain, selfish mining and spamming attacks, on our Minotaur client.
Our implementation shows that Minotaur performs well even under these attacks,
and makes a stronger case for the practical viability and robustness of the
system. Details about the implementation and the experiments are given in §7.

Motivation. Combining multiple resources helps to protect against scenarios
where the adversary may gain control over the majority of one single resource
but not over the combination of all involved resources. For instance, to
violate security in the PoW/PoS case with $\omega=0.5$, an adversary
controlling half of the hash power would now additionally need to control half
of the stake.

As a concrete example, consider the launch of a new blockchain. A PoS chain
can be easily bootstrapped with existing techniques such proof-of-burn
(karantias2020proof, ), initial coin offering (li2018initial, ) and airdrop
(airdrop, ). In contrast, the bootstrapping of a PoW chain is challenging, as
the new system would presumably start off with a relatively small total
computation power and thus be vulnerable to “$51\%$ attacks”. Especially in
view of the many PoW ledgers currently competing for the dedication of hashing
power, a large established Bitcoin miner suddenly diverting their resources to
the new system may easily result in their obtaining full control of the
system. To defend against such situations, Minotaur allows to launch a
(projected) PoW blockchain in pure PoS mode (setting parameter $\omega=0$) and
later transit into a pure PoW blockchain by gradually changing the weighing
parameter $\omega$ to a higher value (§8), thus allowing to safely ramp up the
applied hashing power until a safe level of participation has been reached.

Related work. The idea of hybrid PoW/PoS block production was first mentioned
in (KinNad12, ). A first concrete construction was given in (BLMR14, ) under
the label ‘proof of activity’, but without giving a rigorous security
analysis. Their block-production mechanism essentially extends standard
Bitcoin mining by having the mined block implicitly elect a set of
stakeholders that are required to sign the block in order to validate it.

A similar construction was proposed in (FDKT+20, ) and proven secure under a
majority of adversarial hashing power—however, their security proof still
implies an honest majority of stake. In particular, and contrary to their
initial claims, the protocol is not proven secure under the condition that
_any_ minority of the combined resources is controlled by the adversary.

The work of (FDKT+20, ) was extended in (DCFZ18, ), to adapt to dynamic
participation of both, hashing power and stake, and in (TNDF+18, ), to combine
PoW with multiple resources (rather than just PoS)—both works lack a rigorous
security analysis.

The application of PoW/PoS hybrid block production for the goal of protecting
early-stage PoW systems against initial periods of adversarial dominance in
hashing power was explored in (CXGL+18, ). They propose to start the system
with hybrid block production (where each resource contributes to a certain
fraction of the blocks) and then slowly fade out the stake contribution to
eventually turn the system into pure PoW. Also this protocol is not proven
secure.

There also exist another class of hybrid PoW/PoS protocols (neu2021ebb, ;
sankagiri2020blockchain, ; buterin2017casper, ; stewart2020grandpa, ), which
uses a BFT protocol (PoS) to build a finality gadget/layer on the top of a
Nakamoto-style longest chain protocol (PoW) to achieve important properties
such as accountability and finality. However, these protocols require an
honest majority (or even supermajority) on both the set of miners and the set
of stakeholders hence they are not fungible.

##  2\. Preliminaries

###  2.1. Security model

Time, slots, and synchrony. We consider a setting where time is divided into
discrete units called slots. Players are equipped with (roughly synchronized)
clocks that indicate the current slot. Slots are indexed by integers, and
further grouped into epochs with fixed size $R$, i.e., epoch $e$ composes of
slots $\\{(e-1)R+1,(e-1)R+2,\cdots,eR\\}$. And we assume that the real time
window that corresponds to each slot has the following two properties: (1) The
current slot is determined by a publicly-known and monotonically increasing
function of current time; (2) Each player has access to the current time and
any discrepancies between parties’ local time are insignificant in comparison
with the duration of a slot.

We describe our protocols in the now-standard $\Delta$-synchronous network
model considered in (pass2017analysis, ; garay2020full, ; david2018ouroboros,
; badertscher2018ouroboros, ), where there is an (unknown) upper bound
$\Delta$ in the delay (measured in number of slots) that the adversary may
inflict to the delivery of any message. Similar to (garay2020full, ;
pass2017analysis, ), the protocol execution proceeds in slots with inputs
provided by an environment program denoted by ${\mathcal{Z}}(1^{\kappa})$ to
parties that execute the protocol $\Pi$, where $\kappa$ is a security
parameter. The network is modeled as a diffusion functionality similar to
those in (garay2020full, ; pass2017analysis, ): it allows message ordering to
be controlled by the adversary ${\mathcal{A}}$, i.e., ${\mathcal{A}}$ can
inject messages for selective delivery but cannot change the contents of the
honest parties’ messages nor prevent them from being delivered within $\Delta$
slots of delay — a functionality parameter. Specially, for $\Delta=1$, the
network model is reduced to the so-called lock-step synchronous model, where
messages are guaranteed to be delivered within one slot.

Protocol player. The protocol is executed by two types of players, PoW-miners
(miners for short) and PoS-holders (stakeholders for short), who generate
different types of blocks, PoW blocks and PoS blocks. Note that we allow for
any relation among the sets of miners and stakeholders, including the
possibility that all players play both roles, or the two types of players are
disjoint.

Random oracle. For PoW mining, we abstract the hash function as a random-
oracle functionality. It accepts queries of the form $(\texttt{compute},x)$
and $(\texttt{verify},x,y)$. For the first type of query, assuming $x$ was
never queried before, a value $y$ is sampled from $\\{0,1\\}^{\kappa}$ and it
is entered to a table $T_{H}$. If $x$ was queried before, the pair $(x,y)$ is
recovered from $T_{H}$. In both cases, the value $y$ is provided as an answer
to the query. For the second type of query, a lookup operation is performed on
the table. Honest miners are allowed to ask one query per slot of the type
compute and unlimited queries of the type verify. The adversary
${\mathcal{A}}$ is given a bounded number of compute queries per slot and also
unlimited number of verify queries. The bound for the adversary is determined
as follows. Whenever a corrupted miner is activated the bound is increased by
1; whenever a query is asked the bound is decreased by 1 (it does not matter
which specific corrupted miner makes the query).

Adversarial control of resources. We assume a Byzantine adversary who can
decide on the spot how many honest/corrupted miners are activated adaptively.
Note that we allow instantaneously adaptive corruption on miners, which means
that both the number of honest miners and the number of corrupted miners in
each slot are chosen by the adversary. For stakers, the adversary is only
‘moderately’ adaptive (participant corruption only takes effect after a
certain delay), just like in Ouroboros classic (kiayias2017ouroboros, ). In a
slot $r$, the number of honest miners that are active in the protocol is
denoted by $h_{r}$ and the number of all active miners in slot $r$ is denoted
by $n_{r}$. Note that $h_{r}$ can only be determined by examining the view of
all honest miners and is not a quantity that is accessible to any of the
honest miners individually. In order to obtain meaningful concentration bounds
on the number of PoW blocks in a long enough window, we set a lower bound
$\alpha_{0}$ on the fraction of honest mining power, i.e.,
$h_{r}\geq\alpha_{0}n_{r}$ for all $r$. Note that $\alpha_{0}$ does not have
to be $1/2$ as required by Bitcoin, it can be a small positive constant.
Sudden decreases of total mining power could hurt the liveness of the protocol
due to too few PoW blocks mined in one epoch. Therefore, we need to restrict
the fluctuation of the number of honest/adversarial queries in a certain
limited fashion. Suppose ${\mathcal{Z}},{\mathcal{A}}$ with fixed coins
produces a sequence of honest miners $h_{r}$, where $r$ ranges over all slots
of the entire execution, we define the following notation.

###### Definition 1 (from (garay2017bitcoin, )).

For $\gamma\in[1,\infty)$, we call a sequence $(x_{r}),r\in[LR]$, as
$(\gamma,s)$-respecting if for any set $S\subseteq[0,LR]$ of at most $s$
consecutive slots,

$\max_{r\in S}\ x_{r}\leq\gamma\min_{r\in S}\ x_{r},$

We say that ${\mathcal{Z}}$ is $(\gamma,s)$-respecting if for all
${\mathcal{A}}$ and coins for ${\mathcal{Z}}$ and ${\mathcal{A}}$, both the
sequences of $(h_{r})$ and $(n_{r})$ are $(\gamma,s)$-respecting.

Finally, Minotaur achieves consensus via proof of fungible work and stake. The
following is the formal definition of fungibility and our major assumptions on
the adversarial power.

###### Definition 2 (Fungibility of resources).

For a time window $W$, let $\beta_{s}^{W}$ be the maximum fraction of
adversarial stake in $W$, where the maximum is taken over all views of all
honest players across all slots in $W$; and let $\beta_{w}^{W}$ be the maximum
fraction of adversarial mining power over all slots in $W$ (i.e.,
$\beta_{w}^{W}=1-\min_{r\in W}h_{r}/n_{r}$). For $\theta\in[0,1]$, we say the
adversary ${\mathcal{A}}$ is $(\theta,m,\omega)$-bounded if for any time
window $W$ with at most $m$ slots, we have
$\omega\beta_{w}^{W}+(1-\omega)\beta_{s}^{W}\leq\theta$. We say a blockchain
protocol achieves fungibility of work and stake if it is secure against such
an adversary.

To keep the paper simple, the Minotaur protocol, as described, will rely on
Assumption 1 below that initializes the protocol with honest majority of
stake; however this assumption is not essential; we refer the reader to §8 for
a discussion on how to remove it.

###### Assumption 1 (Initialization).

During the initialization phase of the protocol, we assume:

  1. 1.1

The initial stake distribution has honest majority, i.e., $\beta_{s}^{0}\leq
1/2-\sigma$, where $\beta_{s}^{0}$ is the fraction of initial stake controlled
by the adversary.

  2. 1.2

We have a good estimate of the initial honest mining power $h_{1}$. In
particular, let $\tilde{h}_{1}$ be the estimate of $h_{1}$, we have
$h_{1}/(1+\delta)\gamma^{2}\leq\tilde{h}_{1}\leq\gamma^{2}h_{1}/(1-\delta)\alpha_{0}$.

Post initialization, we relax the above to our intended fungible resource
assumption described below.

###### Assumption 2 (Execution).

During the execution phase of the protocol, we assume:

  1. 2.1

Stake-work bound: The adversary ${\mathcal{A}}$ is
$(1/2-2\sigma,2R,\omega)$-bounded.

  2. 2.2

Work fluctuation bound: The environment ${\mathcal{Z}}$ is
$(\gamma,2R)$-respecting.

  3. 2.3

Work participation bound: For any slot $r\in[LR]$, $h_{r}\geq\alpha_{0}n_{r}$.

Participation model. Minotaur can be constructed based on different PoS
longest chain protocols. Various versions of Minotaur will take different
subsets of the following assumptions on the participation model:

  1. (P1)

Honest stakeholders are always online111This assumption can be easily relaxed.
Namely, it is sufficient for an honest stakeholder to come online at the
beginning of each epoch, determine whether it belongs to the slot leader set
for any slots within this epoch, and then come online and act on those slots
while maintaining online presence at least every $k$ slots. See Appendix H of
(david2018ouroboros, ) for more detail.;

  2. (P2)

Honest miners who mined PoW blocks in epoch $e$ will stay online in epoch
$e+2$;222This can be relaxed similarly as P1.

  3. (P3)

In case an honest party joins after the beginning of the protocol, its
initialization chain $\mathcal{C}$ provided by the environment should match an
honest party’s chain which was active in the previous slot.

###  2.2. Blockchain security properties

###### Notation 1.

We denote by $\mathcal{C}^{\lceil\ell}$ the chain resulting from “pruning” the
blocks with timestamps within the last $\ell$ slots. If $\mathcal{C}_{1}$ is a
prefix of $\mathcal{C}_{2}$, we write $\mathcal{C}_{1}\prec\mathcal{C}_{2}$.
The latest block in the chain $\mathcal{C}$ is called the head of the chain
and is denoted by head$(\mathcal{C})$. We denote by
$\mathcal{C}_{1}\cap\mathcal{C}_{2}$ the common prefix of chains
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$. Given a chain $\mathcal{C}$ and an
interval $S$ (or $[r_{1},r_{2}]$), let $\mathcal{C}(S)$ (or
$\mathcal{C}[r_{1},r_{2}]$) be the segment of $\mathcal{C}$ containing blocks
with timestamps in $S$ (or $[r_{1},r_{2}]$). We say that a chain $\mathcal{C}$
is held by or belongs to an honest node if it is one of the best chains in its
view.

###### Definition 3 (Common Prefix (CP)).

The common prefix property with parameter $\ell_{\rm cp}\in\mathbb{N}$ states
that for any two honest nodes holding chains $\mathcal{C}_{1}$,
$\mathcal{C}_{2}$ at slots $r_{1}$, $r_{2}$, with $r_{1}\leq r_{2}$, it holds
that $\mathcal{C}_{1}^{\lceil\ell_{\rm cp}}\prec\mathcal{C}_{2}$.

###### Definition 4 (Existential Chain Quality ($\exists$CQ)).

The existential chain quality property with parameter $\ell_{\rm
cq}\in\mathbb{N}$ states that for any chain $\mathcal{C}$ held by any honest
party at slot $r$ and any interval $S\subseteq[0,r]$ with at least $\ell_{\rm
cq}$ consecutive slots, there is at least one honestly generated block in
$\mathcal{C}(S)$.

Our goal is to generate a robust transaction ledger that satisfies persistence
and liveness as defined in (kiayias2017ouroboros, ).

###### Definition 5.

A protocol $\Pi$ maintains a robust public transaction ledger if it organizes
the ledger as a blockchain of transactions and it satisfies the following two
properties:

  * •

(Persistence) Consider the confirmed ledger $L_{1}$ on any node $p_{1}$ at any
slot $r_{1}$, and the confirmed ledger $L_{2}$ on any node $p_{2}$ at any slot
$r_{2}$ (here $u_{1}$ ($r_{1}$) may or may not equal $u_{2}$ ($r_{2}$)). If
$r_{1}+\Delta<r_{2}$, then $L_{1}$ is a prefix of $L_{2}$.

  * •

(Liveness) Parameterized by $u\in\mathbb{R}$, if a transaction tx is received
by all honest nodes for more than $u$ slots, then all honest nodes will
contain tx in the same place in the confirmed ledger.

##  3\. Impossibility result

Consider any protocol $\Pi$ executed by two types of players, miners and
stakeholders, and let $D_{\Pi}$ be the region of $(\beta_{w},\beta_{s})$ such
that $\Pi$ can generate a robust public transaction ledger under an adversary
controlling a $\beta_{w}$ fraction of mining power and a $\beta_{s}$ fraction
of stake (see Figure 1(b)).

###### Theorem 3.1.

Any two points, $X_{1}=(p_{1},q_{1})$ and $X_{2}=(p_{2},q_{2})$ such that
$p_{1}+p_{2}\geq 1$ and $q_{1}+q_{2}\geq 1$, cannot co-exist in $D_{\Pi}$.

###### Proof.

We show that if there exists a protocol $\Pi$ secure under both points $X_{1}$
and $X_{2}$, then we can use $\Pi$ to implement a robust transaction ledger
with two players, one of them being Byzantine, which is impossible.

Let Alice and Bob be two players, one of them possibly malicious. Let Alice
control a $p_{1}$ fraction of mining power and a $1-q_{2}$ fraction of stake.
Let Bob control a $1-p_{1}$ fraction of mining power and a $q_{2}$ fraction of
stake. In the case where Alice is malicious, a $p_{1}$ fraction of mining
power and a $1-q_{2}\leq q_{1}$ fraction of stake are malicious, which is
dominated by point $X_{1}$. In the case where Bob is malicious, a $1-p_{1}\leq
p_{2}$ fraction of mining power and a $q_{2}$ fraction of stake are malicious,
which is dominated by point $X_{2}$. Assuming that $\Pi$ implements a robust
public transaction ledger implies that also the protocol among the two players
does while one of them is malicious. However, by Theorem 1 in (garay2020sok,
), tolerating $f=1$ malicious player requires at least $2f+1=3$ players. This
is a contradiction. ∎

Figure 2 gives a few examples of possible maximum security regions that
satisfy the constraint by Theorem 3.1. By maximum, we mean the region cannot
be enlarged. All these regions are bounded by a non-increasing curve that is
symmetrical about the point $(1/2,1/2)$. Thus, all these security regions have
area $1/2$, which is an analogy of the $1/2$ fault tolerance in the single-
resource systems. In this work, we focus on achieving the security regions
bounded by a linear curve (the yellow and red ones in Figure 2) and leave the
achievability of other possible regions (e.g., the green and blue ones) to
future work. Note that the security region achieved by the checkpointed ledger
(karakostas2021securing, ) is also optimal (albeit not fungible), and we will
see that this region can also be achieved by Minotaur with $\omega=0$.

Figure 2. A few examples of possible security regions satisfying the
constraint by Theorem 3.1.

###### Corollary 1.

No protocol $\Pi$ can generate a robust public transaction ledger under a
$(1/2,m,\cdot)$-bounded adversary for any $m$.

Corollary 1 thus implies that Assumption 2.1 is not only sufficient but also
necessary.

##  4\. Baseline approaches

In this section, we provide a couple of natural designs of hybrid PoW/PoS
protocols, which fail to achieve the full goal of Minotaur.

Idea 1: Securing PoW chain via checkpointing. The checkpointed ledger
(karakostas2021securing, ) employs an external set of parties or a committee
chosen randomly from the pool of stakeholders to assist a PoW ledger by
finalizing blocks shortly after their creation. The finalized blocks are
called checkpoints and the final ledger is formed by the chain of checkpoints.
This mechanism can also secure a PoW ledger in the presence of adversarial
mining majorities, but the security is solely guaranteed by the external set
or the stakeholders.

Other checkpointing protocols (neu2021ebb, ; sankagiri2020blockchain, ;
buterin2017casper, ; stewart2020grandpa, ) achieve properties that are not
possible with pure PoW protocols, such as accountability and finality.
However, in contrast to our requirement to tolerate any adversarial minority
of the _combined_ resources, these protocols are based on the stronger
assumption of honest majority (or even supermajority) of _both_ the set of
miners and the set of stakeholders.

Idea 2: Smooth interpolation among PoW and PoS blocks. In the static setting
(where both the total mining power and total active stake are fixed and known
to the protocol designer), there is a simple protocol that can also achieve
the regions defined by the red line in Figure 1(b). In this protocol, PoW and
PoS mining occur in parallel, following the longest chain rule. In the
initialization phase, we tune the mining targets such that the mining rate
(i.e., number of blocks produced per unit time) of PoW blocks is $\omega f$
and the mining rate of PoS blocks is $(1-\omega)f$. In the execution phase,
whichever miners or stakeholders succeeds first, it goes ahead and extends the
longest chain which accepts both types of blocks.

Compared with a pure PoS protocol (e.g., Ouroboros Praos (david2018ouroboros,
)), the adversary has strictly smaller action space because it cannot
equivocate with the PoW blocks. Thus, the security of this protocol follows
directly from the security of Ouroboros Praos via either the forkable string
argument (badertscher2018ouroboros, ) or the Nakamoto block method developed
in (dembo2020everything, ). We remark that the existence of this simple
protocol makes the 2-hop blockchain (FDKT+20, ) less interesting as it only
works in the static setting and does not even allow weighing PoW and PoS.

However, it is very hard to extend this simple idea to the non-static setting,
particularly with variable mining power. A natural approach to support
variable mining power is to have fixed-length epochs and adjust the mining
target of PoW blocks every epoch as in Bitcoin. From the simple protocol
described above, we learn that in order to guarantee security in the non-
static setting, we need to make sure that the ratio of total mining rates of
PoW blocks and PoS blocks is a constant $\omega/(1-\omega)$ in every epoch.
However, this is impossible to achieve in the variable mining power setting
because the adversary can always decide to hide or release its PoW blocks so
that there is no way to estimate the total mining power accurately. Inaccurate
PoW mining target adjustment could lead to a different weighing parameter
$\omega$ of the security region than the desired one. More importantly, the
value of $\omega$ can be easily manipulated by the adversary (via selectively
publishing its PoW blocks), and is unknown to the honest players.

##  5\. The full protocol

In this section, we provide a detailed description of our protocol Minotaur.
The protocol is built on an epoch-based PoS longest chain protocol e.g.,
Ouroboros Classic (kiayias2017ouroboros, ), Praos (david2018ouroboros, ), or
Genesis (badertscher2018ouroboros, ). Recall that in an epoch-based PoS
protocol, time is divided into multiple epochs, each with a fixed number of
slots. In each slot, one or multiple stakeholders are selected as block
proposers by a PoS ‘lottery’ process. In this process, the probability of
being selected is proportional to the relative stake a stakeholder has in the
system, as reported by the blockchain itself. See Appendix E for more details.

In contrast to the original Ouroboros protocols, the block-proposer schedule
accounts for both resources by means of _virtual stake_ , which is a
combination of the _actual stake_ (representing stake as in the original
protocol), and _work stake_ representing the share in block-production rights
attributed to the PoW resource.

Additionally, PoW miners participate by mining _endorser blocks_ (along the
lines of ‘endorser inputs’ (kiayias2017ouroboros, ) or ‘fruits’
(pass2017fruitchains, )). These endorser blocks are not directly appended to
the main chain, but are to be referenced by future main-chain blocks (i.e.,
PoS blocks scheduled by means of virtual stake). Each epoch is assigned a
certain amount of work stake that is assigned to the PoW miners who succeed in
mining PoW blocks; the work stake assigned to the respective miners is
proportional to their contribution of PoW blocks referenced from the main
chain during an epoch. PoS block production rights per epoch are then assigned
by considering the sum of actual stake (contributed by tokens) and work stake
(contributed by PoW blocks).

Note that the purpose of the PoW endorser blocks is to measure work fairly,
not implying that they also need to carry the ledger transactions. Transaction
inclusion is orthogonal to this aspect, and can still be implemented along the
lines of Bitcoin (transaction inclusion in the main-chain blocks) or Input-
Endorsers/FruitChain (transaction inclusion in the endorser blocks), or
variants thereof.

We now treat the underlying PoS protocol as a black-box and present the
protocol in detail. The protocol runs in fixed-time epochs with $R$ slots
each.

  * •

PoW mining: In slot $sl$ of epoch $e$, a miner mines a PoW block if

$H(pk,sl,h,mr,nonce)<T_{e},$

where $pk$ is the public key of the miner, $h$ is the hash of the last
confirmed PoS block (according to the confirmation rule of the underlying PoS
protocol), $mr$ is the Merkle root of the payload, $T_{e}$ is the mining
target in epoch $e$. Like in PoW blockchains, miners try different values of
$nonce$ to solve this hash puzzle. Following the notation in (garay2020full,
), we define the difficulty of this PoW block to be $1/T_{e}$. Besides
possible transactions, also the public key of the miner is included in the
payload. A PoW block is called recent in current slot $sl_{\rm now}$ if it
refers to a confirmed PoS block mined no earlier than slot $sl_{\rm
now}-sl_{\rm re}$, where $sl_{\rm re}$ is called the _recency parameter_.

  * •

PoS mining: in slot $sl$ of epoch $e$, one or multiple stakeholders are
selected to propose PoS blocks extending the best chain (according to the
chain selection rule). The selection of PoS block proposers uses the same
mechanism as in the underlying PoS protocol. But for each node, the
probability of being selected is proportional to its relative “virtual” stake,
instead of the relative actual stake. The virtual stake is the sum of actual
stake and work stake. At the beginning of each epoch, we set the total work
stake equal to $\frac{\omega}{1-\omega}$ times the total actual stake in the
system. And the work stake distribution used in epoch $e$ is set to be the
distribution of block difficulties from PoW blocks referred by PoS blocks in
epoch $e-2$.

  * •

Adjust the PoW mining target: For epoch $e$, $T_{e}$ is adjusted according to
$D_{e-1}^{\rm total}$ the total difficulty of PoW blocks referred by PoS
blocks in slots $[(e-2)*R-k+1,(e-1)*R-k]$, i.e., $T_{e}=f^{(w)}R/D_{e-1}^{\rm
total}$, where $f^{(w)}$ is a protocol parameter representing the expected PoW
mining rate in number of blocks per slot. (Specially, for $e=2$,
$T_{2}=f^{(w)}(R-k)/D_{1}^{\rm total}$.) Note that around the boundary of two
epochs $e-1$ and epoch $e$, the adversary has the option to use targets from
both epochs, as PoW blocks don’t have accurate timestamps.

  * •

Chain selection rule: due to a long-range attack (see Appendix C), the longest
chain rule would fail. We use the following chain selection rules, which have
different security guarantees.

    * –

maxvalid-mc (from Ouroboros Praos (david2018ouroboros, ), needs a trusted
third party for bootstrapping, i.e., assumption (P3)): it prefers longer
chains, unless the new chain forks more than $k$ blocks relative to the
currently held chain (in which case the new chain would be discarded).

    * –

maxvalid-bg (from Ouroboros Genesis (badertscher2018ouroboros, ), supports
bootstrapping from genesis block): it prefers longer chains, if the new chain
$\mathcal{C}^{\prime}$ forks less than $k$ blocks relative to the currently
held chain $\mathcal{C}$. If $\mathcal{C}^{\prime}$ did fork more than $k$
blocks relative to $\mathcal{C}$, $\mathcal{C}^{\prime}$ would still be
preferred if it grows more quickly in the $s$ slots following the slot
associated with the last common block of $\mathcal{C}$ and
$\mathcal{C}^{\prime}$.

##  6\. Security Analysis

###  6.1. Main theorems

Under different security models and assumptions, we prove the security (in
particular, persistence and liveness as defined in §2.2) of Minotaur
constructed with three various versions of Ouroboros PoS protocols.

###### Theorem 6.1.

Under Assumption 1, Assumption 2 and assumptions (P1)-(P3), when executed in a
lock-step synchronous model (i.e., $\Delta$-synchronous model with
$\Delta=1$), Minotaur constructed with Ouroboros (kiayias2017ouroboros, )
generates a transaction ledger that satisfies persistence and liveness with
overwhelming probability.

###### Theorem 6.2.

Under Assumption 1, Assumption 2 and assumptions (P1)-(P3), when executed in a
$\Delta$-synchronous model, Minotaur constructed with Ouroboros Praos
(david2018ouroboros, ) generates a transaction ledger that satisfies
persistence and liveness with overwhelming probability.

###### Theorem 6.3.

Under Assumption 1, Assumption 2 and assumptions (P1)-(P2), when executed in a
$\Delta$-synchronous model, Minotaur constructed with Ouroboros Genesis
(badertscher2018ouroboros, ) generates a transaction ledger that satisfies
persistence and liveness with overwhelming probability.

###  6.2. Security with Ouroboros

We first provide a proof sketch for Theorem 6.1. All the parameters used in
our analysis are listed in Table 1.

$h_{r}$ |  number of honest PoW queries in slot $r$
---|---
$n_{r}$ |  number of total PoW queries in slot $r$
$\alpha_{0}$ | lower bound on the fraction of honest mining power
$sl_{\rm re}$ | recency parameter for PoW blocks
$\Delta$ | network delay in slots
$\kappa$ | security parameter; length of the hash function output
$R\in\mathbb{N}$ | duration of an epoch in number of slots
$(\gamma,s)$ | restriction on the fluctuation of the number of
|  honest queries across slots (Definition 1)
$f^{(s)}$ | expected PoS mining rate in number of blocks per slot
$f^{(w)}$ | expected PoW mining rate in number of blocks per slot
$\epsilon$ | quality of concentration of random variables
$\sigma$ | PoW fairness parameter
|  & advantage of honest parties (Assumption 1.1 and 2.1)
$\delta$ |  “goodness” parameter of an epoch/slot (Definition 6)
$\lambda$ | typicality parameter of the execution
$\ell$ | minimum number of slots for concentration bounds
$L$ | total number of epochs in the execution
$\omega$ | the weighing parameter
Table 1. The parameters used in our analysis.

###### Proof sketch..

The proof relies on two important arguments:

  1. 1)

Single-epoch argument. Given honest majority in the virtual stake (normalized
work-stake + normalized actual-stake) used in one epoch, we prove the security
properties (CP and $\exists$CQ) for this single epoch. For this, we use the
so-called forkable strings technique developed in the Ouroboros papers
(badertscher2018ouroboros, ; david2018ouroboros, ; kiayias2017ouroboros, ).

  2. 2)

FruitChain argument. Given CP and $\exists$CQ of the PoS chain in an epoch, we
prove fairness of PoW blocks in this epoch, i.e., a miner controlling a $\phi$
fraction of the computational resources will contribute a $\phi$ fraction of
work.

Using these building blocks, we prove the security with maxvalid-mc
inductively. Under the honest majority assumption in the initial stake
distribution (Assumption 1.1), we can prove security of the PoS chain in
epochs 1&2\. Applying the FruitChain argument, we get fairness of PoW blocks
in epochs 1&2\. Combining with Assumption 2.1, i.e.,
$\omega\beta_{w}+(1-\omega)\beta_{s}<1$ (for any long enough window), we have
honest majority in the virtual stake distribution used in epoch 3&4\. And the
proof goes on till the last epoch (Figure 3). ∎

Figure 3. Proof sketch for §6.2.

####  6.2.1. Single-epoch security

###### Theorem 6.4 (Theorem 3 from (david2018ouroboros, )).

Let $\kappa,R,\Delta\in\mathbb{N}$ and $\sigma\in(0,1)$. Let $\beta_{v}$ be
the fraction of adversarial virtual stake satisfying

$\beta_{v}\leq 1/2-\sigma$

for some positive constant $\sigma$. Then the probability that the adversary
violates CP with parameter $\ell_{\rm cp}=\kappa$ and $\exists$CQ with
parameter $\ell_{\rm cq}=\kappa$ throughout a period of $R$ slots is no more
than $Re^{-\Omega(\kappa)}$. The constant hidden by the
$\Omega(\cdot)$-notation depends on $\sigma$.

In Minotaur, the main-chain blocks are scheduled as a function of the virtual-
stake distribution only. The Ouroboros analysis thus directly translates by
replacing its actual stake by virtual stake.

####  6.2.2. FruitChain argument

Recall that $h_{r}$ is the number of honest PoW queries in slot $r$ and
$n_{r}$ is the number of total PoW queries in slot $r$. For a set of slots
$S$, we define $h(S)=\sum_{r\in S}h_{r}$ and $n(S)=\sum_{r\in S}n_{r}$. In
order to obtain meaningful concentration bounds on the number of PoW blocks in
one epoch, there is a lower bound $\alpha_{0}$ on the fraction of honest
mining power, i.e., $h_{r}\geq\alpha_{0}n_{r}$ for all $r$.

In the analysis of this subsection, we assume the main chain (PoS chain)
satisfies properties CP with parameter $\ell_{\rm cp}=\kappa$ and $\exists$CQ
with parameter $\ell_{\rm cq}=\kappa$. By the common prefix property, for a
PoS chain $\mathcal{C}$ held by an honest node at slot $r$, the prefix
$\mathcal{C}^{\lceil\kappa}$ are stabilized, so to mine a PoW block at slot
$r$ an honest miner will refer the tip of $\mathcal{C}^{\lceil\kappa}$ as the
last confirmed PoS block. And we set the recency parameter $sl_{\rm
re}=3\kappa+\Delta$, i.e., a PoW block $B_{w}$ is recent w.r.t. a chain
$\mathcal{C}$ at slot $r$ if the confirmed PoS block referred by $B_{w}$ is in
$\mathcal{C}$ and has timestamp at least $r-3\kappa-\Delta$. With this
selection of the recency parameter, we can prove the following key property of
the protocol: any PoW block mined by an honest miner will be incorporated into
the stabilized chain (and thus never lost). We refer to this as the Fruit
Freshness Lemma—PoW blocks stay “fresh” sufficiently long to be incorporated.

###### Lemma 6.5 (Fruit Freshness).

Suppose the PoS chain satisfies properties CP with parameter $\ell_{\rm
cp}=\kappa$ and $\exists$CQ with parameter $\ell_{\rm cq}=\kappa$. Then, if
$sl_{\rm re}=3\kappa+\Delta$, an honest PoW block mined at slot $r$ will be
included into the stabilized chain before slot $r+r_{\rm wait}$, where $r_{\rm
wait}=2\kappa+\Delta$.

###### Proof.

Suppose an honest PoW block $B_{w}$ is mined at slot $r_{0}$ while the PoS
chain $\mathcal{C}_{0}$ is adopted, then $B_{w}$ will reference the tip of
$\mathcal{C}_{0}^{\lceil\kappa}$ as the last confirmed PoS block. Further, by
the $\exists$CQ property, the tip of $\mathcal{C}_{0}^{\lceil\kappa}$ has
timestamp $r_{1}\geq r_{0}-2\kappa$. By slot $r_{0}+\Delta$, all honest nodes
will receive $B_{w}$. Let $r_{2}=r_{0}+2\kappa+\Delta$ and $\mathcal{C}$ be
any chain held by an honest node at slot $r_{2}$, then again by $\exists$CQ,
there exists an honest block $B_{s}$ on $\mathcal{C}$ whose timestamp $r_{3}$
is in the interval $[r_{2}-2\kappa,r_{2}-\kappa)$. We check that $B_{w}$ is
still recent at slot $r_{3}$ as

$r_{3}-r_{1}<(r_{2}-\kappa)-(r_{0}-2\kappa)=3\kappa+\Delta=sl_{\rm re}.$

As $B_{s}$ is an honest block mined after $r_{0}+\Delta$, $B_{s}$ or an
ancestor of $B_{s}$ must include $B_{w}$. And since $B_{s}$ is stabilized in
$\mathcal{C}$ at slot $r_{2}$, we have that $r_{\rm
wait}=r_{2}-r_{0}=2\kappa+\Delta$. ∎

In a $(\gamma,s)$-respecting environment, we have the following useful
proposition.

###### Proposition 1 (Proposition 2 from (garay2020full, )).

In a $(\gamma,s)$-respecting environment, let $U$ be a set of at most $s$
consecutive slots and $S\subseteq U$. Then, for any $h\in\\{h_{r}:r\in U\\}$
and any $n\in\\{n_{r}:r\in U\\}$ we have

$\displaystyle\frac{h}{\gamma}$ $\displaystyle\leq\frac{h(S)}{|S|}\leq\gamma
h,~{}~{}~{}~{}\frac{n}{\gamma}\leq\frac{n(S)}{|S|}\leq\gamma n,$
$\displaystyle h(U)$ $\displaystyle\leq\Bigl{(}1+\frac{\gamma|U\setminus
S|}{|S|}\Bigr{)}h(S),~{}~{}~{}~{}n(U)\leq\Bigl{(}1+\frac{\gamma|U\setminus
S|}{|S|}\Bigr{)}n(S).$

Recall that $T_{e}$ is the mining target in epoch $e$ determined by the
stabilized segment of the chain from epoch $e-1$. In order to obtain
meaningful concentration bounds on the number of PoW blocks, we need $T_{e}$
to be ‘reasonable’ for each epoch. Similar to (garay2017bitcoin, ;
garay2020full, ), we define a notation of ‘good’ epochs as follows. By abuse
of notation, we write the expected PoW block rate $f^{(w)}$ simply as $f$ in
the analysis below.

###### Definition 6.

Epoch $e$ is _good_ if $(1-\delta)\alpha_{0}f/\gamma\leq
ph^{(e)}T_{e}\leq(1+\delta)\gamma f$, where $p=1/2^{\kappa}$ and
$h^{(e)}=h_{(e-1)R+1}$, i.e., the number of honest queries in the first slot
of epoch $e$. A slot $r$ is good if it is in a good epoch.

###### Proposition 2.

Under a $(\gamma,2R)$-respecting environment, if slot $r$ is a good slot in
epoch $e$, then $(1-\delta)\alpha_{0}f/\gamma^{2}\leq
ph_{r}T_{e}\leq(1+\delta)\gamma^{2}f$.

###### Proof.

By the definition of a good epoch, we have $(1-\delta)\alpha_{0}f/\gamma\leq
ph^{(e)}T_{e}\leq(1+\delta)\gamma f$. And under a $(\gamma,2R)$-respecting
environment and the fact that slot $r$ is in epoch $e$, we know $1/\gamma\leq
h_{r}/h^{(e)}\leq\gamma$. Therefore, $(1-\delta)\alpha_{0}f/\gamma^{2}\leq
ph_{r}T_{e}\leq(1+\delta)\gamma^{2}f$. ∎

Now, we prove fairness of PoW blocks in any large enough window, i.e., a miner
controlling a $\phi$ fraction of the computational resources will contribute a
$\phi$ fraction of work. We first give a form definition of fairness.

###### Definition 7.

We say that ${\mathcal{H}}$ is a _$\phi$ -fraction honest subset_ if miners in
${\mathcal{H}}$ (that may change over time) are honest and
$n^{{\mathcal{H}}}_{r}>\phi n_{r}$ for any slot $r$, where
$n^{{\mathcal{H}}}_{r}$ is number of queries in ${\mathcal{H}}$ at slot $r$.

###### Definition 8 (Fairness).

We say that the protocol has _(approximate) $(W_{0},\sigma)-$fairness_ if, for
any $\phi$, $\alpha_{0}\leq\phi<1$, any $\phi-$fraction honest subset
${\mathcal{H}}$, and any honest miner holding chain $\mathcal{C}$ at slot $r$
and any interval $S_{0}\subseteq[0,r]$ with at least $W_{0}$ consecutive
slots, it holds that the PoW blocks included in $\mathcal{C}(S_{0})$ mined by
${\mathcal{H}}$ have total difficulty at least $(1-\sigma)\phi d$, where $d$
is the total difficulty of all PoW blocks included in $\mathcal{C}(S_{0})$.

Define the random variable $D_{r}$ equal to the sum of the difficulties of all
PoW blocks computed by honest miners at slot $r$. And for fixed $\phi$ and
$\phi-$fraction honest subset ${\mathcal{H}}$, define the random variable
$D^{{\mathcal{H}}}_{r}$ equal to the sum of the difficulties of all PoW blocks
computed by miners in ${\mathcal{H}}$ at slot $r$. For a set of slots $S$, we
define $D(S)=\sum_{r\in S}D_{r}$, $D^{{\mathcal{H}}}(S)=\sum_{r\in
S}D^{{\mathcal{H}}}_{r}$, and $n^{{\mathcal{H}}}(S)=\sum_{r\in
S}n^{{\mathcal{H}}}_{r}$. For a set of $J$ adversarial queries, define the
random variable $A(J)$, as the sum of difficulties of all the PoW blocks
created during queries in $J$.

Next we define the notion of typical executions, which will be shown to occur
with overwhelming probability.

###### Definition 9 (Typical execution).

An execution $E$ is _typical_ if the following hold

(a) For any set $S$ of at least $\ell$ consecutive good slots,

$\displaystyle D(S)<(1+\epsilon)ph(S).$

(b) For any set $S$ of at least $\ell$ consecutive good slots, let $J$ be the
set of adversarial queries in $S$. If we further know each query in $J$ made
at slot $r$ with target $T$ satisfies $(1-\delta)\alpha_{0}f/\gamma^{2}\leq
pn_{r}T\leq(1+\delta)\gamma^{2}f/\alpha_{0}$, then

$D(S)+A(J)<(1+\epsilon)p(h(S)+|J|).$

(c) For any set $S$ of at least $\ell/\phi$ consecutive good slots,

$D^{{\mathcal{H}}}(S)>(1-\epsilon)pn^{{\mathcal{H}}}(S).$

To obtain meaningful concentration, we should be considering a sufficiently
long slot sequence of at least

$\ell\triangleq\frac{2(1+\epsilon/3)}{\epsilon^{2}\gamma^{3}(1-\delta)\alpha_{0}f}\lambda,$

where $\lambda$ is called the typicality parameter of the execution.

For our analysis to go through, the protocol parameters should satisfy certain
conditions which we now discuss. First, we will require that the number $\ell$
defined above and the security parameter $\kappa$ are appropriately small
compared to $R$, the duration of an epoch.

(C1)
$R-3\kappa-\Delta\geq\ell/\alpha_{0}\geq\frac{\gamma}{\epsilon}(4\kappa+\Delta).$

Note that (C1) implies $R\geq(4\kappa+\Delta)/\epsilon$. Second, the slack
variables $\epsilon$ and $\delta$ should satisfy

(C2) $4\epsilon\leq\delta\leq 1.$

Next we bound the probability of an atypical execution (Lemma 6.6) and show
that all epochs are good in a typical execution by induction (Lemma 6.7).
Therefore, all epochs are good with overwhelming probability.

###### Lemma 6.6.

For an execution $\mathcal{E}$ of $LR$ slots, in a $(\gamma,2R)$-respecting
environment, the probability of the event “$\mathcal{E}$ is not typical” is
bounded by $\mathcal{O}(LR)e^{-\lambda}$.

###### Lemma 6.7.

For a typical execution in a $(\gamma,2R)$-respecting environment, all epochs
are good.

The proofs of Lemma 6.6 and Lemma 6.7 are in Appendix D. In order to address
the dependency among PoW successes in the variable mining difficulty setting,
the proof of Lemma 6.6 uses martingale arguments (from (garay2020full, )) to
provide useful bounds on the relevant random variables. The proof of Lemma 6.7
uses an induction argument to show that if all previous epochs are good, then
the progress of the adversary in the next epoch will be bounded and as a
result the next epoch is also good.

Finally, we prove the FruitChain/fairness argument.

###### Theorem 6.8 (Fairness).

For a typical execution in a $(\gamma,2R)$-respecting environment, the
protocol with recency parameter $sl_{\rm re}=3\kappa+\Delta$ satisfies
$(W_{0},\sigma)-$fairness, where $W_{0}=\ell/\alpha_{0}+3\kappa+\Delta$ and
$\sigma=4\epsilon$.

###### Proof.

Fix $\phi$, a $\phi-$fraction honest subset ${\mathcal{H}}$, and an honest
node holding chain $\mathcal{C}$. Let $S_{0}=\\{u:r_{1}\leq u\leq r_{2}\\}$ be
a window of at least $W_{0}$ consecutive slots. Let $\mathcal{C}(S_{0})$ be
the segment of $\mathcal{C}$ containing PoS blocks with timestamps in $S_{0}$,
let ${\mathcal{B}}$ be all PoW blocks included in $\mathcal{C}(S_{0})$, and
$d$ be the total difficulty of all PoW blocks in ${\mathcal{B}}$. The proof of
Lemma 6.7 observes the following facts to be used below:

  * •

Fact 1. For any PoW block $B\in{\mathcal{B}}$, $B$ is mined after
$r_{1}-4\kappa-\Delta$.

  * •

Fact 2. For any PoW block $B\in{\mathcal{B}}$, $B$ is mined before
$r_{2}+\kappa$.

  * •

Fact 3. If a PoW block $B$ is mined by ${\mathcal{H}}$ after $r_{1}$ and
before $r_{2}-3\kappa-\Delta$, then $B\in{\mathcal{B}}$.

Now, let $S_{1}=\\{u:r_{1}-(4\kappa+\Delta)\leq u\leq r_{2}+\kappa\\}$,
$S_{2}=\\{u:r_{1}\leq u\leq r_{2}-(3\kappa+\Delta)\\}$, and $J$ be the set of
adversary queries associated with ${\mathcal{B}}$ in $S_{1}$. Then by Fact 1
and Fact 2, we have that all PoW blocks in ${\mathcal{B}}$ are mined in
$S_{1}$; by Fact 3, we have that all PoW blocks mined by ${\mathcal{H}}$ in
$S_{2}$ are in ${\mathcal{B}}$. Similar to the arguments in Lemma 6.7, for
each query in $S_{1}$ made by either an honest node or the adversary at slot
$r$ in epoch $e$, the target $T$ must satisfy
$(1-\delta)\alpha_{0}f/\gamma^{2}\leq
pn_{r}T\leq(1+\delta)\gamma^{2}f/\alpha_{0}$.

Further note that, to prove $\sigma$-fairness, it suffices to show that

$D^{{\mathcal{H}}}(S_{2})\geq(1-\sigma)\phi(D(S_{1})+A(J)).$

Under a typical execution, we have

$D^{{\mathcal{H}}}(S_{2})>(1-\epsilon)pn^{{\mathcal{H}}}(S_{2})\geq(1-\epsilon)\phi
pn(S_{2}),$

and

$D(S_{1})+A(J)<(1+\epsilon)p(h(S_{1})+|J|)=(1+\epsilon)pn(S_{1}).$

By our choice of $W_{0}$, we have $|S_{2}|\geq\ell/\alpha_{0}\geq\ell/\phi$.
Furthermore, we may assume $|S_{2}|\leq 2R$. This is because we may partition
$S_{2}$ in parts such that each part has size between $\ell/\alpha_{0}$ and
$2R$, sum over all parts to obtain the desired bound. Then by Proposition 1,
we have

$\displaystyle n(S_{1})$ $\displaystyle\leq(1+\frac{\gamma|S_{1}\setminus
S_{2}|}{|S_{2}|})n(S_{2})$
$\displaystyle\leq(1+\frac{\gamma(8\kappa+2\Delta)}{\ell/\alpha_{0}})n(S_{2})$
$\displaystyle\overset{(C1)}{\leq}(1+2\epsilon)n(S_{2}).$

Finally, by setting $\sigma=4\epsilon$, we conclude the proof. ∎

####  6.2.3. Lifting argument from single-epoch to multiple-epoch

Theorem 6.4 gives bounds for CP and $\exists$CQ for a single-epoch run of the
protocol with static stake distribution and perfect randomness. We now
conclude our proof of Theorem 6.1 by showing that these blockchain properties
hold throughout the whole lifetime of the system consisting of many epochs.

###### Theorem 6.9 (Restatement of Theorem 6.1).

Fix parameters $\kappa$, $\lambda$, $\ell$, $\gamma$, $\sigma$, $\epsilon$,
$\delta$, $R$ and $L$ satisfying conditions (C1) and (C2). Under Assumption 1,
Assumption 2 and assumptions (P1)-(P3), when executed in a lock-step
synchronous model (i.e., $\Delta$-synchronous model with $\Delta=1$), Minotaur
constructed with Ouroboros generates a transaction ledger that satisfies
persistence and liveness throughout a period of $L$ epochs (each with $R$
slots) with probability $1-RL(e^{-\Omega(\kappa)}+e^{-\lambda})$.

This part of the analysis proceeds similarly as in Section 5 of
(kiayias2017ouroboros, ) and hence we only sketch it in Appendix D. Applying
the improved analysis in (bkmqr2020, ) (instead of the one in
(kiayias2017ouroboros, )), we obtain the refined bound
$1-RL(e^{-\Omega(\delta^{3}\kappa)}+e^{-\lambda})$ for the statement of
Theorem 6.9. In Appendix F, we analyze a private-chain attack and show a
corresponding lower bound. It reveals that $\delta^{2}\kappa$ needs to be
bounded below by a constant and, consequently, the dependency on $\delta^{3}$
cannot be improved much further.

###  6.3. Security with Ouroboros Praos/Genesis

By maxvalid-bg, an honest node prefers longer chains, if the new chain
$\mathcal{C}^{\prime}$ forks less than $k$ blocks relative to the currently
held chain $\mathcal{C}$. If $\mathcal{C}^{\prime}$ did fork more than $k$
blocks relative to $\mathcal{C},\mathcal{C}^{\prime}$ would still be preferred
if it grows more quickly in the $s$ slots following the slot associated with
the last common block of $\mathcal{C}$ and $\mathcal{C}^{\prime}$. In this
section, we analyze the security of the protocol with maxvalid-bg, but drop
assumption (P3) (i.e., allow bootstrapping from genesis).

###### Proof sketch.

This part is identical to the analysis in Ouroboros Genesis (Section 4.3-4.4
of (badertscher2018ouroboros, )), so we only sketch it here. The proof
proceeds in two steps:

  1. 1)

For an honest node $h_{1}$ that is always online, we show that when replacing
maxvalid-mc with maxvalid-bg, the overall execution of the protocol in
$h_{1}$’s view remains the same except with negligible probability. That is to
show that with overwhelming probability, whenever $h_{1}$ receives a new chain
$\mathcal{C}^{\prime}$ that forks more than $k$ blocks from $h_{1}$’s local
chain $\mathcal{C}$, $h_{1}$ will always favor $\mathcal{C}$, i.e.,
$\mathcal{C}$ grows more quickly than $\mathcal{C}^{\prime}$ in the first $s$
slots right after the fork.

  2. 2)

For a newly joined node $h_{2}$, we consider a ‘virtual’ node $h_{2}^{\prime}$
that holds no stake, but was participating in the protocol since the beginning
and was honest all the time. Then we show $h_{2}$ will always adopt the same
chains as $h_{2}^{\prime}$ after joining the network.∎

###  6.4. Comparison to Bitcoin

In this paragraph, we observe that Minotaur (when executed in the pure PoW
case, $\omega=1$) is more robust against fluctuations in PoW participation
than Bitcoin. In particular, we demonstrate that Bitcoin may not enjoy
liveness if the number of parties is allowed to halve every two weeks—while
Minotaur does. The theoretical results of this section are accompanied by
experiments; see §7.2 and Figure 5. We point out that although Bitcoin mining
power has gone up exponentially since its inception, other PoW blockchains
that use the same difficulty adjustment rule may experience such drops in
mining power.333For example, ETC dropped from 19 TH/s to 1.5 TH/s in 7 months
period https://2miners.com/etc-network-hashrate, but more impressively ERGO
dropped from 23.65 to 0.5 TH/s in just 2 weeks’ time https://2miners.com/erg-
network-hashrate.

Consider Bitcoin for the case that, initially, there are $n$ honest parties
and that the target is $T$. Using the model and notation of (garay2017bitcoin,
) with $q=1$, $m$ is the number of blocks in an epoch and $p=1/2^{\kappa}$.
Thus, each slot is successful with probability $f=1-(1-pT)^{n}\approx pTn$. We
will show that for $s=\lfloor m/pTn\rfloor$, liveness may fail in a
$(2,s)$-respecting environment. In such an environment, the adversary is
allowed to halve the number of parties every $s\approx m/f$ slots (note that
$m/f$ is the expected duration of an epoch, which for Bitcoin is two weeks).

The attack proceeds in stages of $s$ slots, during which the adversary does
not mine nor delays messages. Thus, in the beginning of each slot all parties
have a chain of the same length. The adversary halves the number of parties at
the beginning of each stage. Let $N_{i}$ denote the number of honest parties
in stage $i$, with $N_{0}=n$ and $N_{i}=n/2^{i}$ for $i>0$. The expected
number of successful slots in stage $i$ is

$s\cdot[1-(1-pT)^{N_{i}}]<spTN_{i}=\frac{spTn}{2^{i}}\leq\frac{m}{2^{i}}.$

Consider the stage $j$ for which

$k-1<\frac{m}{2^{j}}\leq 2(k-1).$

The expected number of blocks computed in the first $j$ stages is

$\frac{m}{2}+\frac{m}{2^{2}}+\cdots+\frac{m}{2^{j}}=m-\frac{m}{2^{j}}<m-k+1$

and at most $k-1$ in stage $j+1$. Recalling that the median of a binomial
distribution with mean $\mu$ is at most $\lceil\mu\rceil$, we obtain that with
probability at least $1/4$ at most $m$ blocks have been computed by the end of
stage $j+1$ and at most $k-1$ of them have been computed in the last stage.
Assuming the liveness parameter $u<s$, any transaction provided to all honest
parties for the first $u$ slots of the final stage, will be in depth less than
$k$. It follows that liveness does not hold in the final stage of the attack.

###### Proposition 6.10.

Bitcoin’s ledger does not satisfy liveness in a $(2,s)$-respecting
environment, for any $u<s$ and $s<m/pTn$.

In contrast, Minotaur does not suffer from such fluctuation. Intuitively, this
is because it inherits its security from the underlying proof-of-stake
protocol. In particular, the epochs are of fixed duration, implying that
target recalculation occurs regularly. This is evident from Condition C1,
which allows much greater values for $R$ and $\gamma$.

##  7\. Experiments

We implemented a prototype instantiation of a Minotaur client in Rust and the
code can be found at (Minotaurcode, ). We also implemented Bitcoin, FruitChain
and Ouroboros clients as benchmarks. Particularly, for better comparison we
implemented the variable difficulty version of FruitChain recently proposed in
(wang2021securing, ), which uses the same difficulty adjustment as Bitcoin. In
this section, we briefly describe the architecture of our implementation and
present experimental results to evaluate the concrete performance of Minotaur
under different scenarios.

###  7.1. Architecture

We implemented the Input-Endorsers/FruitChain variant of Minotaur, where
transactions are exclusively included in the PoW blocks. In this way, Minotaur
can potentially achieve optimal throughput up to the capacity of the network
as shown by the implementation of Prism (yang2019prism, ), a pure PoW
consensus protocol with similar blockchain structure. The system architecture
is illustrated in Figure 4. Functionally it can be divided into the following
three modules:

  1. (1)

Block Structure Manager, which maintains the client’s view of the blockchain,
and communicates with peers to exchange new blocks.

  2. (2)

Miner, which assembles new PoW blocks.

  3. (3)

Staker, which assembles new PoS blocks.

The goal of a Minotaur client is to maintain up-to-date information of the
blockchain. They are stored in the following three data structures:

  1. (1)

Block Structure Database, stores the graph structure of the blockchain (i.e.,
a directed acyclic graph (DAG) formed with PoW and PoS blocks).

  2. (2)

Memory Pool, stores the set of transactions that have not been mined into any
PoW block.

  3. (3)

PoW Block Pool, stores the set of PoW blocks that have not been referenced by
any PoS block.

At the core of the Block Structure Manager is an event loop which sends and
receives network messages to/from peers, and a worker thread pool which
handles those messages. When a new block arrives, the worker thread first
checks its proof-of-work/proof-of-stake, and if valid, then proceeds to relay
the block to peers that have not received it. Next, the worker thread checks
whether all blocks referenced by the new block, e.g. its parent, are already
present in the Block Structure Database. If not, it buffers the block in an
in-memory queue and defers further processing until all the referenced blocks
have been received. Finally, the worker validates the block (e.g., verifying
transaction signatures), and inserts the block into the Block Structure
Database. If the block is a PoW block, the Block Structure Manager checks the
Memory Pool against the transactions in this new block and removes any
duplicates or conflicts from the Memory Pool, and also puts the block into the
PoW Block Pool.

The Miner module assembles new PoW blocks. It is implemented as a busy-
spinning loop. At the start of each round, it polls the Block Structure
Database and the Memory Pool to update the block it is mining. When a new PoW
block is mined, it will be inserted into the Block Structure Database, then
sent to peers by the Block Structure Manager. The Memory Pool and PoW Block
Pool will also be updated accordingly.

The Staker module works similarly, but assembles new PoS blocks. At the start
of each round, it polls the Block Structure Database and the PoW Block Pool to
update the block it is assembling. When a new PoS block is generated, it will
be inserted into the Block Structure Database, then sent to peers by the Block
Structure Manager. The PoW Block Pool will also be updated accordingly.

Block Structure Database Block Structure manager Staker Miner Memory Pool PoW
Block Pool New BlocksNew Transactions

Figure 4. Architecture of our Minotaur client implementation.

###  7.2. Performance under variable mining power

In §6.4, we have seen that Minotaur can survive more drastic variations of
network hash power. We design the following experiment on our
Minotaur/Bitcoin/FruitChain codebase to verify this argument.

Recall that all three protocols have epoch-based target adjustment rules,
varying the difficulty target of block mining based on the median inter-block
time from the previous epoch. However, the epoch length in Minotaur is defined
as a fixed number of slots instead of a fixed number of blocks (e.g., 2016
blocks in Bitcoin). This definition makes sense in Minotaur because the main-
chain blocks, which are PoS blocks, always have accurate timestamps (even if
they are proposed by an adversary). In this experiment, we will see that this
small change allows Minotaur to enjoy better liveness than Bitcoin and
FruitChain when the total mining power is decreasing.

In our experiment, we set the epoch length in Bitcoin/FruitChain to be 400
blocks and the expected duration of an epoch is 2 minutes; while the epoch
length of Minotaur is 2 minutes and the expected number of blocks in a epoch
is 400 blocks. Then Bitcoin, FruitChain and Minotaur are experiencing the same
mining power variation, i.e., starting with an insufficient mining rate (100
blocks per minute) and then halving the mining rate every epoch (2 minutes in
the experiments). From Figure 5, we can see that the mining target never has a
chance to be adjusted in Bitcoin/FruitChain as the length of the main chain
can never reach 400 blocks, which leads to a liveness failure; while the
mining targets are adjusted every epoch (2 minutes) in Minotaur to make sure
that the number of PoW blocks referenced by the main chain grows linearly.

Figure 5. Behavior of Bitcoin, FruitChain and Minotaur under decreasing mining
power. When the total mining power is halved every two minutes, the main
chains of Bitcoin and FruitChain stop growing as they can never reach the
epoch size (400 blocks), while the number of PoW blocks referenced by the main
chain grows linearly in Minotaur.

###  7.3. Performance under attacks

In the following experiments, we evaluate how Minotaur performs in the
presence of active attacks. Specifically, we consider three types of attacks:
private chain, spamming and selfish mining attacks. At a high level, a private
chain attack aims to violate the persistence of the protocol. Spamming attack
aims to reduce network throughput, while selfish mining aims to compromise the
PoW fairness of the protocol (i.e., reducing the work stake of honest miners).

Private chain attack. In a private chain attack, an attacker tries to
privately generate an alternate chain faster than the public honest chain to
displace a confirmed block (nakamoto2008bitcoin, ) (e.g., a block buried
$k$-deep in the longest chain). In a pure PoW/PoS protocol (e.g.,
Bitcoin/Ouroboros), an attacker with majority of mining/stake power can always
succeed with the private chain attack, no matter how large the confirmation
depth is. In contrast, Minotaur can survive such an attack, as long as the
honest players control a majority of the combined resources.

To verify this key security property, we implemented the private chain attack
on our code base, where an attacker can have various combinations of stake and
mining power. The experiments of the private chain attack are as follows: the
attacker (with $\beta_{s}$ fraction of stake and $\beta_{w}$ fraction of
mining power) tries to generate a private chain starting at a specific block
(e.g., the first block in some epoch) to overwrite the honest public chain
when the private chain becomes longer. We run the attack for one epoch and
count the length of the longest private chain (pruning honest blocks in the
prefix if there is any) whose length is no less than that of the honest chain
generated at the same time. Note that the maximum length of the private chain
in a successful attack reflects the minimum confirmation depth that is needed
to guarantee security of the protocol. We chose $\omega=0.5$ with a total PoS
block rate being 1.58 block/s and a total PoW block rate being 2.70 block/s
for Minotaur. Parameters $\beta_{s}$ and $\beta_{w}$ are both iterated in
$[0,1]$ with a step size of $0.1$ for Minotaur experiments, and we present the
results as a 2D heatmap in Figure 6. We also launched the same attack on
Ouroboros Praos (Bitcoin resp.), where the attacker controls $\beta_{s}$
fraction of stake ($\beta_{w}$ fraction of mining power resp.) and the results
are shown as 1D heatmaps in Figure 6. In these experiments, block generation
is set to the same rate as PoS block rate in Minotaur experiments. For each
data point, we repeated the experiments 10 times and took an average to
minimize randomness effects. From Figure 6 we observe that as long as
$\beta_{s}+\beta_{w}<1$, the attacker can only succeed with very short private
chain even when either $\beta_{s}$ or $\beta_{w}$ is close to 1, while
Ouroboros Praos and Bitcoin would need $\beta_{s}<0.5$ and $\beta_{w}<0.5$
respectively. This provides empirical evidence that Minotaur is better than
pure PoW or PoS protocols in term of security.

Figure 6. Longest private chain in private attacks with various adversarial
stake fraction $\beta_{s}$ and adversarial mining power fraction $\beta_{w}$
on Minotaur, Ouroboros Praos, and Bitcoin. When $\beta_{s}+\beta_{w}<1$ and
either $\beta_{s}$ or $\beta_{w}$ is close to 1, the private chain in Minotaur
is way shorter, meaning that it remains secure whereas Ouroboros Praos and
Bitcoin are insecure.

Spamming attack. In a spamming attack, attackers flood the network with
conflicting transactions. Among a bunch of conflicting transactions, at most
one of them could be executed successfully. For example, in an account model,
transactions with identical sender and nonce are conflicting transactions.
Compared to Bitcoin, the Input-Endorsers/FruitChain variant of Minotaur cannot
ensure that no conflicting transactions enter the transaction ledger since PoW
are mined before picked by main chain. Therefore, goodput (i.e., throughput of
successfully executed transactions) of Minotaur transaction ledger will be
comprised if conflicting transactions enter PoW blocks. To mitigate this
attack, we propose a spam filter that operates as follows: a miner validates
transactions with respect to the transaction ledger, PoW blocks that haven’t
been picked by main chain, and preceding pending transactions of this miner.
In this way, if one of the conflicting transactions enters a PoW block and
propagated throughout the network before other conflicting ones enter a PoW
block, miners will filter out other conflicting transactions and increase
goodput.

We implemented the spam filter and did experiments with four nodes in a line
topology. Our metrics is normalized spam, which is the count of unsuccessfully
executed transactions normalized by the count of transactions in ledger. In
our experiments, we make transaction generators create conflicting
transactions on purpose, and send them to two nodes sitting at the ends of the
line topology. And other nodes receive non-conflicting transactions. Hence,
without any spam precaution, normalized spam is $0.25$. We set the block
generation rate to be $0.44$ block/s for PoS blocks and $1.39$ block/s for PoW
blocks. The results of our experiments with additional peer-to-peer latency is
shown in Figure 7, and we observe that although normalized spam increases as
additional latency increases, it is still lower than that without spam filter.
The highest spam in our experiments is $0.063$, far lower than $0.25$. Noticed
that in that experiment we apply an additional peer-to-peer latency of $0.3$s,
which is larger than most peer-to-peer latency in Bitcoin and Ethereum
(kim2018measuring, ). This means that our spam filter can reduce spam to a
minimal effect.

Figure 7. Normalized spam in 4-node experiments with additional peer-to-peer
latency. Spam is reduced mostly under various additional latencies.

Selfish mining attack. It has been known that Bitcoin is vulnerable to the
selfish mining attack (nayak2016stubborn, ; sapirshtein2016optimal, ;
eyal2014majority, ), where a selfish miner withhold its mined blocks and
release them later at an appropriate time to take the place of honest blocks
in the longest chain. This attack hurts the fairness of the protocol, in the
sense that the selfish miner with $\beta_{w}$ fraction of mining power can
have more than $\beta_{w}$ faction of blocks in the main chain so that it will
reap higher revenue. The FruitChain protocol (pass2017analysis, ) was proposed
as a solution to selfish mining. We observe that the selfish mining attack
will not work on Minotaur Since it has similar blockchain structure as
FruitChain. Moreover, Minotaur will achieve fairness even when $\beta_{w}\geq
0.5$ (as long as there is an honest super-majority in actual stake), while
FruitChain would fail. To verify these observations, we implemented the
following selfish mining attacks on our Bitcoin/FruitChain/Minotaur code base:

  * •

On Bitcoin: The selfish miner always mines on the block at the tip of the
longest chain, whether the chain is private or public. Upon successful mining,
the adversary maintains the block in private to release it at an appropriate
time. In particular, when an honest miner publishes a block, the selfish miner
will release a previously mined block at the same level (if it has one).

  * •

On FruitChain: The selfish miner plays the same withholding-and-releasing
strategy on its main-chain blocks as above, while its main-chain blocks
contain fruits mined by itself exclusively.

  * •

On Minotaur: The selfish miner plays the same withholding-and-releasing
strategy on its PoS blocks as above, while its PoS blocks contain PoW blocks
mined by itself exclusively.

We assume honest nodes will choose the attacker’s block with probability $p$
whenever there is a tie. In our experiments, we set $p>0.5$ to simulate the
case that the attacker has better network connection than honest nodes so its
blocks are usually transmitted faster. Table 2 presents fractions of PoW
blocks (or fruits) in the main chain of Bitcoin/FruitChain/Minotaur under
various adversarial power (combinations of $\beta_{w}$ and $p$). On Minotaur,
the attacker controls $1/3$ of the virtual stake, i.e.,
$\omega\beta_{w}+(1-\omega)\beta_{s}=1/3$, where $\beta_{s}$ is the fraction
of the actual stake controlled by the attacker. In Table 2, we can see that
Bitcoin is indeed vulnerable to selfish mining, meaning that the attacker has
more fraction of PoW blocks in the main chain (and thus more block rewards in
Bitcoin) than its fraction of mining power, particularly when $\beta_{w}\geq
0.5$; and FruitChain only resists the attack when $\beta_{w}<0.5$. Meanwhile,
in Minotaur, the attacker can only have $\beta_{w}$ faction of PoW blocks in
the main chain, no matter how much mining power it has (even when
$\beta_{w}\geq 0.5$), and how the network favors it. This property is crucial
to the security of Minotaur as we have seen in §6.2.2.

Attacker’s power | Fraction of PoW blocks
---|---
$\beta_{w}$ | 0.75 | 0.67 | 0.50 | 0.33 | 0.25
$p=1$ | Bitcoin | 0 | 0 | 0.007 | 0.513 | 0.669
FruitChain | 0 | 0.007 | 0.011 | 0.661 | 0.739
Minotaur | 0.248 | 0.332 | 0.498 | 0.665 | 0.746
$p=0.7$ | Bitcoin | 0 | 0.001 | 0.098 | 0.618 | 0.72
FruitChain | 0 | 0.003 | 0.056 | 0.665 | 0.753
Minotaur | 0.248 | 0.333 | 0.499 | 0.666 | 0.750
Table 2. Fractions of honest PoW blocks (or fruits) in the main chain under
selfish mining attacks in Bitcoin/FruitChain/Minotaur. In these experiments,
the attacker controls $\beta_{w}$ fraction of mining power and the tie
breaking rule favors the attacker’s block with probability $p$.

##  8\. Discussion

Variable weighing parameter. In our security analysis, we assume a fixed
weighing parameter $\omega$ through the whole execution of the protocol.
However, we point out that $\omega$ can change over time as long as we put
proper assumptions on the adversarial stake/mining power. Suppose $\omega(e)$
is the weighing parameter of epoch $e$, i.e., the ratio of work stake and
actual stake in epoch $e$ is set to be $\omega(e)/(1-\omega(e))$. Note that
the function $\omega(e)$ may be decided by the protocol designers and hard-
coded in the genesis block, but the players can also reach an agreement (off-
chain) to update it by doing a soft fork.

We give a brief security sketch, deferring the full analysis to future work.
Recall that, in our protocol, the virtual stake of a player in epoch $e$
composes of two parts: the actual stake drawn from the last PoS block in epoch
$e-2$; and the work stake that is proportional to the amount of work it
produced during epoch $e-2$. Thus, to guarantee the security in epoch $e$, we
need the adversary to be $(1/2-2\sigma,2R,\omega(e))$-bounded (see Def. 2) in
epoch $e-2$ and epoch $e-1$. And similarly, the adversary needs to be
$(1/2-2\sigma,2R,\omega(e+1))$-bounded in epoch $e-1$ and epoch $e$.
Therefore, the adversarial stake/mining power must be restricted by both above
bounds for epoch $e-1$. As long as $\omega(e+1)$ does not differ too much from
$\omega(e)$, this restriction on the adversary is reasonable to assume, and
the weighing parameter can transit smoothly from $\omega(e)$ to $\omega(e+1)$.
Figure 8 gives an example of how the assumptions shift when $\omega(e)$ is
updated at the onset of epoch $e_{0}+1$.

Figure 8. An example of variable weighing parameter $\omega$ in Minotaur.
Suppose the value of $\omega$ changes from $1/2$ to $2/5$ at the onset of
epoch $e_{0}+1$. Then the adversarial stake/mining power needs to be
restricted below the red line in epochs $e\leq e_{0}-1$ and below the blue
line in epochs $e\geq e_{0}-1$. In particular, the adversary is restricted by
both lines in epoch $e_{0}-1$. When $\omega$ changes smoothly over time, it is
reasonable to assume exactly this.

We point out that such flexible weighing between work and stake is very useful
in practice. For example, in general, PoS blockchains are easy to launch with
existing techniques, such as proof- of burn (karantias2020proof, ), initial
coin offering (li2018initial, ) and airdrop (airdrop, ). Therefore, Minotaur
can be launched as a pure PoS blockchain and later transit into a hybrid
PoW/PoS one or a pure PoW blockchain. In addition, the security of Minotaur
can be enhanced by assigning higher weight to the more decentralized resource.

Removing the initial constraint. As discussed in §2, we use an honest majority
of stake without relying on PoW for the two initial epochs. We note that we
can relax this initial constraint harmonizing even the initial two epochs with
the rest of the execution by employing the smooth-interpolation technique (§4,
Idea 2) where work blocks are mined based on $2$-for-$1$ PoW (garay2020full, )
producing both, main-chain blocks (at a rate defined by $\omega$) and endorser
blocks (at a sufficient rate to guarantee fairness). This allows to start the
protocol with any initial weighing by means of $\omega$. We do not pursue this
further as, (I) for most practical purposes we expect the present construction
to be sufficient as is (namely it will be reasonable to launch Minotaur with
PoW “turned off”, at $\omega=0$ and then begin to incrementally adjust
$\omega$ to higher values at some time after two epochs), and, (II) as
explained in §4, the analysis of the variation described above that allows
$\omega>0$ from launch will follow in a straightforward manner from the
forkable string analysis and input-endorser technique of
(kiayias2017ouroboros, ; badertscher2018ouroboros, ) as well as the fairness
argument of (pass2017fruitchains, ). This is because the main difficulty in
the analysis of PoW/PoS hybrid protocols is dealing with variable difficulty —
and adopting the $\omega=0$ convention for the initial two epochs allows us to
focus on that.

Generalization to multiple resources. Following the idea in (TNDF+18, ),
Minotaur can be extended to more than two resources. In contrast to their
construction, this is achievable without fundamentally changing the structure
of the protocol.

Assume $M\geq 1$ different resources, and for each such resource, an
independent lottery mechanism among the contributors to assign ‘successes’
proportionally to a party’s ratio of the total contributed resource. Defining
a fixed amount of virtual stake $V$ and weights $\omega_{i}>0$,
$\sum_{i=1}^{M}\omega_{i}=1$, we have resource $i$ control $\omega_{i}\cdot V$
of the virtual stake. During each epoch $e$, the different lotteries are run
concurrently, wherein each success allows for the release of a respective
block (to be eventually picked up by a block of the main chain), tied to the
respective resource.

Main-chain block leadership for epoch $e+2$ is assigned to resource $i$ based
on relative virtual stake $\omega_{i}$, and further split among the
contributors of that resource based on their production of respective
‘resource blocks’ during epoch $e$. Naturally, this protocol tolerates

(1) $\sum_{i=1}^{M}\omega_{i}\beta_{i}<\frac{1}{2}\,,$

where $\beta_{i}\in[0,1]$ is the fraction of resource $i$ held by the
adversary. A pictorial example for $M=3$ is given in Figure 9.

Although the underlying blockchain protocol is PoS-based, stake (in the
classical, non-virtual sense) is not required to be one of the $M$ resources,
i.e., the protocol can be run solely on virtual stake. Also, full adversarial
control of some of the resources can be tolerated as long as Eq. (1) is
satisfied.

Finally, note that the resources can also be of the same type, e.g., Minotaur
can combine work emanating from different hash functions such as SHA$256$,
scrypt, and ethash—answering an open question raised in §1.

$1$$\beta_{1}\ [\omega_{1}=\frac{1}{4}]$$1$$\beta_{2}\
[\omega_{2}=\frac{1}{3}]$$1$$\beta_{3}\ [\omega_{3}=\frac{5}{12}]$ Figure 9.
Tolerable resource corruption for
$\mathbf{\omega}=(\frac{1}{4},\frac{1}{3},\frac{5}{12})$. The volume enclosed
by the gray surfaces is tolerated by the protocol:
$\sum_{i=1}^{3}\omega_{i}\beta_{i}<\frac{1}{2}$.

Fairness with respect to the combined resources. Fairness with respect to PoW
blocks (Definition 8) is a crucial property of Minotaur to guarantee fair
assignment of work stake to the miners. However, this is not sufficient for
aspects like fair reward sharing (pass2017fruitchains, ), since, for this
purpose, fairness needs to be achieved for overall block production with
respect to the _combined_ resources. We note that fairness with respect to the
combined resources can be achieved by scheduling endorser blocks for every
involved resource, _including stake_. A given epoch reward can now be shared
by assigning an $\omega_{i}$ fraction of the reward to the contributors of the
$i$-th resource, and distributing each such fraction proportionally to the
parties’ contributions of endorser blocks for that resource.

Comparison to state-of-the-art protocols.  In comparison to previous hybrid
PoW-PoS protocols, (FDKT+20, ) already generalized the conditions under which
a permissionless blockchain can be securely operated by combining PoW and PoS.
Our paper improves over (FDKT+20, ) by demonstrating how to tolerate a
strictly better bound, i.e., _any_ adversarial minority of the combined
resources, and furthermore proving this bound tight, thus settling the hybrid
PoW-PoS question.

We also note that Minotaur’s performance is comparable to previous state-of-
the-art protocols:

$\bullet$ _State-of-the-art PoS_. As Minotaur resembles a PoS protocol (while
operating on virtual stake derived from PoW), the only overhead it introduces
over its underlying PoS protocol is the extra (insignificant) effort required
for virtual-stake conversion—which impacts system throughput or transaction
latency only marginally. The performance of our explicit Minotaur
construction, based on Ouroboros, is thus directly inherited from the
Ouroboros protocol.

$\bullet$ _State-of-the-art PoW_. Note that Nakamoto-style PoS mimics the
workings of PoW Nakamoto consensus and thus yields similar stochastics as in
the PoW case, and thus also comparable performance characteristics.

##  9\. Acknowledgements

We would like to thank Thomas Kerber and Alexander Russell for insightful
discussions.

This research is supported in part by the US National Science Foundation under
grants CCF-1705007 and CNS-1718270 and the US Army Research Office under grant
W911NF1810332.

## References

  * (1) Airdrop.  https://en.bitcoinwiki.org/wiki/Airdrop.
  * (2) Back, A. Hashcash—a denial of service counter-measure.
  * (3) Badertscher, C., Gaži, P., Kiayias, A., Russell, A., and Zikas, V. Ouroboros Genesis: Composable proof-of-stake blockchains with dynamic availability.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (2018), pp. 913–930.
  * (4) Bentov, I., Lee, C., Mizrahi, A., and Rosenfeld, M. Proof of activity: Extending bitcoin’s proof of work via proof of stake [extended abstract] y.  ACM SIGMETRICS Performance Evaluation Review 42, 3 (2014), 34–37.
  * (5) Blum, E., Kiayias, A., Moore, C., Quader, S., and Russell, A. The combinatorics of the longest-chain rule: Linear consistency for proof-of-stake blockchains.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020 (2020), S. Chawla, Ed., SIAM, pp. 1135–1154.
  * (6) Buterin, V., and Griffith, V. Casper the friendly finality gadget.  arXiv preprint arXiv:1710.09437 (2017).
  * (7) Chen, L., Xu, L., Gao, Z., Lu, Y., and Shi, W. Protecting early stage proof-of-work based public blockchain.  In 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W) (2018), IEEE, pp. 122–127.
  * (8) David, B., Gaži, P., Kiayias, A., and Russell, A. Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2018), Springer, pp. 66–98.
  * (9) Dembo, A., Kannan, S., Tas, E. N., Tse, D., Viswanath, P., Wang, X., and Zeitouni, O. Everything is a race and nakamoto always wins.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (2020), pp. 859–878.
  * (10) Duong, T., Chepurnoy, A., Fan, L., and Zhou, H.-S. Twinscoin: A cryptocurrency via proof-of-work and proof-of-stake.  In Proceedings of the 2nd ACM Workshop on Blockchains, Cryptocurrencies, and Contracts (2018), pp. 1–13.
  * (11) Duong, T., Fan, L., Katz, J., Thai, P., and Zhou, H.-S. 2-hop blockchain: Combining proof-of-work and proof-of-stake securely.  In European Symposium on Research in Computer Security (2020), Springer, pp. 697–712.
  * (12) Ethereum.  Ethash.  https://web.archive.org/web/20220105100244/ https://eth.wiki/en/concepts/ethash/ethash, 2022.
  * (13) Eyal, I., and Sirer, E. G. Majority is not enough: Bitcoin mining is vulnerable.  In International conference on financial cryptography and data security (2014), Springer, pp. 436–454.
  * (14) Feller, W. An Introduction to Probability Theory and Its Applications, Volume 2.  An Introduction to Probability Theory and Its Applications. Wiley, 1967\.
  * (15) Garay, J., and Kiayias, A. Sok: A consensus taxonomy in the blockchain era.  In Cryptographers’ Track at the RSA Conference (2020), Springer, pp. 284–318.
  * (16) Garay, J., Kiayias, A., and Leonardos, N. The bitcoin backbone protocol with chains of variable difficulty.  In Annual International Cryptology Conference (2017), Springer, pp. 291–323.
  * (17) Garay, J. A., Kiayias, A., and Leonardos, N. The bitcoin backbone protocol: Analysis and applications.  In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II (2015), E. Oswald and M. Fischlin, Eds., vol. 9057 of Lecture Notes in Computer Science, Springer, pp. 281–310.
  * (18) Garay, J. A., Kiayias, A., and Leonardos, N. Full analysis of nakamoto consensus in bounded-delay networks.  IACR Cryptol. ePrint Arch. 2020 (2020), 277.
  * (19) Karakostas, D., and Kiayias, A. Securing proof-of-work ledgers via checkpointing.  In 2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC) (2021), IEEE, pp. 1–5.
  * (20) Karantias, K., Kiayias, A., and Zindros, D. Proof-of-burn.  In International Conference on Financial Cryptography and Data Security (2020), Springer, pp. 523–540.
  * (21) Kiayias, A., Russell, A., David, B., and Oliynykov, R. Ouroboros: A provably secure proof-of-stake blockchain protocol.  In Annual International Cryptology Conference (2017), Springer, pp. 357–388.
  * (22) Kim, S. K., Ma, Z., Murali, S., Mason, J., Miller, A., and Bailey, M. Measuring ethereum network peers.  In Proceedings of the Internet Measurement Conference 2018 (2018), pp. 91–104.
  * (23) King, S., and Nadal, S. Ppcoin: Peer-to-peer crypto-currency with proof-of-stake.  self-published paper, August 19, 1 (2012).
  * (24) Li, J., and Mann, W. Initial coin offering and platform building.  SSRN Electronic Journal (2018), 1–56.
  * (25) Minotaur.  Rust implementation of the minotaur consensus protocol.  https://github.com/xuechao2/Minotaur.
  * (26) Nakamoto, S. Bitcoin: A peer-to-peer electronic cash system.  Decentralized Business Review (2008), 21260.
  * (27) Nayak, K., Kumar, S., Miller, A., and Shi, E. Stubborn mining: Generalizing selfish mining and combining with an eclipse attack.  In 2016 IEEE European Symposium on Security and Privacy (EuroS&P) (2016), IEEE, pp. 305–320.
  * (28) Neu, J., Tas, E. N., and Tse, D. Ebb-and-flow protocols: A resolution of the availability-finality dilemma.  In 2021 IEEE Symposium on Security and Privacy (SP) (2021), IEEE, pp. 446–465.
  * (29) NIST.  Fips 180-2.  http://csrc.nist.gov/encryption/tkhash.html, 2002.
  * (30) Pass, R., Seeman, L., and Shelat, A. Analysis of the blockchain protocol in asynchronous networks.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2017), Springer, pp. 643–673.
  * (31) Pass, R., and Shi, E. Hybrid consensus: Efficient consensus in the permissionless model.  Cryptology ePrint Archive (2016).
  * (32) Pass, R., and Shi, E. Fruitchains: A fair blockchain.  In Proceedings of the ACM Symposium on Principles of Distributed Computing (2017), pp. 315–324.
  * (33) Percival, C., and Josefsson, S. The scrypt password-based key derivation function.  IETF Draft URL: http://tools. ietf. org/html/josefsson-scrypt-kdf-00. txt (accessed: 30.11. 2012) (2016).
  * (34) Sankagiri, S., Wang, X., Kannan, S., and Viswanath, P. Blockchain cap theorem allows user-dependent adaptivity and finality.  arXiv preprint arXiv:2010.13711 (2020).
  * (35) Sapirshtein, A., Sompolinsky, Y., and Zohar, A. Optimal selfish mining strategies in bitcoin.  In International Conference on Financial Cryptography and Data Security (2016), Springer, pp. 515–532.
  * (36) Shevtsova, I. G. Moment-type estimates with an improved structure for the accuracy of the normal approximation to distributions of sums of independent symmetric random variables.  Theory of Probability & Its Applications 57, 3 (2013), 468–496.
  * (37) Stewart, A., and Kokoris-Kogia, E. Grandpa: a byzantine finality gadget.  arXiv preprint arXiv:2007.01560 (2020).
  * (38) Thai, P., Njilla, L., Duong, T., Fan, L., and Zhou, H.-S. A generic paradigm for blockchain design.  In Proceedings of the 15th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (2018), pp. 460–469.
  * (39) Wang, X., Muppirala, V. V., Yang, L., Kannan, S., and Viswanath, P. Securing parallel-chain protocols under variable mining power.  arXiv preprint arXiv:2105.02927 (2021).
  * (40) Yang, L., Bagaria, V., Wang, G., Alizadeh, M., Tse, D., Fanti, G., and Viswanath, P. Prism: Scaling bitcoin by 10,000 x.  arXiv preprint arXiv:1909.11261 (2019).

## Appendix

##  Appendix A Security regions of hybrid protocols in Figure 1b

We give details of the security regions plotted in Figure 1(b). Recall that
$\beta_{w}$ is the proportion of adversarial hash power and $\beta_{s}$ is the
proportion of the adversarial stake (or the proportion of Byzantine nodes if a
permissioned BFT protocol is adopted).

2-hop blockchain. We derived the security region from the assumptions in
Theorem 2&3 of (FDKT+20, ). When $\Delta=0$ (which gives the largest security
region), the security proof of (FDKT+20, ) assumes
$(1-\beta_{w})(1-\beta_{s})>\beta_{s}$, i.e.,
$\beta_{s}<\frac{1-\beta_{w}}{2-\beta_{w}}$ implying $\beta_{s}<1/2$.

Checkpointed ledger. (karakostas2021securing, ) uses a synchronous BFT
protocol (with $1/2$ fault tolerance) to regularly issuing checkpoints on a
PoW longest chain. The protocol is proven to be safe and live when
$\beta_{s}<1/2$.

Finality gadgets. (neu2021ebb, ; sankagiri2020blockchain, ; buterin2017casper,
; stewart2020grandpa, ) use an asynchronous/partial synchronous BFT protocol
(with $1/3$ fault tolerance) to build a finality gadget/layer on the top of a
PoW longest chain to achieve important properties such as finality (a.k.a
deterministic safety under asynchrony) and accountability. These protocols are
proven to be safe and live when $\beta_{s}<1/3$ and $\beta_{w}<1/2$.

##  Appendix B Mathematical facts

###### Theorem B.1 (from (garay2020full, )).

Let $(X_{1},X_{2},\ldots)$ be a martingale with respective the sequence
$(Y_{1},Y_{2},\ldots)$, if an event $G$ implies $X_{k}-X_{k-1}\leq b$ and
$V=\sum_{k}var[X_{k}-X_{k-1}|Y_{1},\ldots,Y_{k-1}]\leq v$, then for non-
negative $n$ and $t$

$\displaystyle P(X_{n}-X_{0}\geq t,G)\leq
e^{-\frac{t^{2}}{2v+\frac{2bt}{3}}}.$

The following is known as the Berry-Esseen Theorem. See (feller2, ) as a
standard reference and (shevtsova, ) for improvements with respect to the
constant 1/2.

###### Theorem B.2.

Let the $X_{i}$ be independent variables with common distribution such that
$\mathbb{E}[X_{i}]=\mu$, $\mathbb{V}[X_{i}]=\sigma^{2}>0$,
$\mathbb{E}[|X_{i}-\mu|^{3}]=\rho<\infty$. If $F_{n}$ is the distribution of
$(X_{1}+\cdots+X_{n}-\mu n)/\sqrt{n\sigma^{2}}$ and $\Phi$ the standard
normal, then

$|F_{n}(x)-\Phi(x)|\leq\frac{\rho}{2\sigma^{3}\sqrt{n}},\quad\text{for all $x$
and $n$.}$

##  Appendix C A long range attack

We point out that Minotaur is insecure with the longest chain rule due to a
long range attack. Let the weighing parameter $\omega=0.5$ and define $f$ to
be PoS block production rate by a stakeholder who controls all actual stake in
the system. Suppose the adversary controls 0.8 fraction of stake and 0.1
fraction of mining power at some slot (not at the beginning of the execution),
then after behaving honestly for some time, the adversary will control 0.8
fraction of actual stake and 0.1 fraction of work stake at the beginning of
some epoch $e$. Now, the adversary starts to grow a private chain
$\mathcal{C}_{1}$, while honest nodes grow a public chain $\mathcal{C}_{2}$.
Suppose $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ include the same set of
transactions. Then at the beginning of epoch $e+2$, the adversary will control
0.8 fraction of actual stake and all the work stake (after normalization) on
its chain $\mathcal{C}_{1}$ because $\mathcal{C}_{1}$ only refers adversarial
PoW blocks in epoch $e$. So the growth rate of $\mathcal{C}_{1}$ after epoch
$e+2$ will be $0.8f+f=1.8f$. Similarly, at the beginning of epoch $e+2$,
honest nodes will control 0.2 fraction of actual stake and all the work stake
(after normalization) on the chain $\mathcal{C}_{2}$ and the growth rate of
$\mathcal{C}_{2}$ after epoch $e+2$ will be $0.2f+f=1.2f$. Therefore,
$\mathcal{C}_{1}$ will catch up with $\mathcal{C}_{2}$ eventually if the
longest chain rule is adopted. See Figure 10.

This long range attack is similar to the stake grinding attack on Ouroboros
and it can be prevented by the new chain selection rules maxvalid-mc and
maxvalid-bg. For maxvalid-mc, honest nodes won’t accept $\mathcal{C}_{1}$
because it forks too long from $\mathcal{C}_{2}$; for maxvalid-bg, honest
nodes won’t accept $\mathcal{C}_{1}$ because it grows slower than
$\mathcal{C}_{2}$ in epoch $e$ (right after the fork).

Figure 10. A long range attack on the longest chain rule.

##  Appendix D Proof for §6

###### Proof of Lemma 6.6.

The proof for (a) is the same as part (a) of Theorem 1 in (garay2020full, ).
For (b), by the condition, for each query in $S$ made by either an honest node
or the adversary at slot $r$ in epoch $e$, the target $T$ must satisfy
$(1-\delta)\alpha_{0}f/\gamma^{2}\leq
pn_{r}T\leq(1+\delta)\gamma^{2}f/\alpha_{0}$ Therefore, the proof is also
similar to part (a) of Theorem 1 in (garay2020full, ).

For (c), let the execution be partitioned into parts such that each part has
at least $\ell/\phi$ and at most $s=2R$ slots. We prove that the statement
fails with a probability less than $e^{-\lambda}$ for each part. Let $J$
denote the queries made by $\mathcal{H}$ in slots $S$. We have
$|J|=n^{\mathcal{H}}(S)=\phi n(S)$. For $k\in[|J|]$, let $Z_{i}$ be the
difficulty of any block obtained from query $j\in J$ and we write
$\mathcal{E}_{j-1}$ for the execution just before this query. Then

$\displaystyle X_{0}=0$ $\displaystyle
X_{k}=\sum_{i\in[k]}Z_{i}-\sum_{i\in[k]}\mathbb{E}[Z_{i}|\mathcal{E}_{i-1}]$

is a martingale with respect to $\mathcal{E}_{0},\ldots,\mathcal{E}_{k}$. We
have

$\displaystyle X_{k}-X_{k-1}$
$\displaystyle=X_{k}-\mathbb{E}[X_{k}|\mathcal{E}_{k-1}]=Z_{k}-\mathbb{E}[Z_{k}|\mathcal{E}_{k-1}]$
$\displaystyle\leq\frac{1}{T_{k}}=\frac{ph_{k}}{ph_{k}T_{k}}\leq\gamma^{3}ph(S)/(1-\delta)\alpha_{0}f|S|$
$\displaystyle\leq\gamma^{3}pn(S)/(1-\delta)\alpha_{0}f|S|:=b.$

Similarly

$\displaystyle V$
$\displaystyle=\sum_{k}var[X_{k}-X_{k-1}|\mathcal{E}_{k-1}]\leq\sum_{k}\mathbb{E}[Z_{k}^{2}|\mathcal{E}_{k-1}]$
$\displaystyle=\sum_{k}pT_{k}\frac{1}{T_{k}^{2}}\leq\gamma^{3}p^{2}|J|h(S)/(1-\delta)\alpha_{0}f|S|$
$\displaystyle\leq\gamma^{3}p^{2}|J|n(S)/(1-\delta)\alpha_{0}f|S|:=v.$

Let the deviation $t=\epsilon p|J|=\epsilon\phi pn(S)$, then we have
$b=\frac{\gamma^{3}t}{(1-\delta)\alpha_{0}\epsilon\phi f|S|}$ and
$v=\frac{\gamma^{3}t^{2}}{(1-\delta)\alpha_{0}\epsilon^{2}\phi f|S|}$. Using
the minimum value of $|S|$ is $\ell/\phi$ and applying Theorem B.1 to
$-X_{|J|}$, we have

$\displaystyle
P[D(S)<(1-\epsilon)pn^{\mathcal{H}}(S)]\leq\exp({-\frac{\epsilon
t}{2b(1+\epsilon/3)}})\leq\exp({-\lambda}).$

This concludes the proof.

∎

###### Proof of Lemma 6.7.

We prove the lemma by induction. For epoch $e=1$, it is trivial to just set
$T_{1}=f/p\tilde{h}_{1}$ by Assumption 1.2. Now we assume all epochs are good
until epoch $e-1$ ($e\geq 2$), we will show epoch $e$ is good.

Let $S_{0}=\\{u:r_{1}\leq u\leq r_{2}\\}$ be the window that will be used to
determine $T_{e}$, i.e., $r_{1}=\max{(0,(e-2)R-\kappa)}+1$ and
$r_{2}=(e-1)R-\kappa$. Let $\mathcal{C}(S_{0})$ be the segment of
$\mathcal{C}$ containing PoS blocks with timestamps in $S_{0}$, let
${\mathcal{B}}$ be all PoW blocks included in $\mathcal{C}(S_{0})$, and $d$ be
the total difficulty of all PoW blocks in ${\mathcal{B}}$. Then we have the
following facts:

  * •

Fact 1. For any PoW block $B\in{\mathcal{B}}$, $B$ is mined after
$r_{1}-4\kappa-\Delta$. Indeed by recency condition, $B$ must refer to a
confirmed PoS block $B_{s}$ with timestamp at least $r_{1}-sl_{\rm re}$. By
$\exists$CQ, the last honest ancestor block of $B_{s}$ has timestamp at least
$r_{1}-sl_{\rm re}-\kappa$. So $B$ must be mined after $r_{1}-4\kappa-\Delta$.

  * •

Fact 2. For any PoW block $B\in{\mathcal{B}}$, $B$ is mined before
$r_{2}+\kappa$. Indeed the PoS block (denoted as $B_{s}$) including $B$ has
timestamp at most $r_{2}$, and again by $\exists$CQ, the first honest
descendant block of $B_{s}$ has timestamp at most $r_{2}+\kappa$. So $B$ must
be mined before $r_{2}+\kappa$.

  * •

Fact 3. If a PoW block $B$ is mined by an honest miner after $r_{1}$ and
before $r_{2}-3\kappa-\Delta$, then $B\in{\mathcal{B}}$. Indeed, by
$\exists$CQ, the last honest block in $\mathcal{C}(S_{0})$ has timestamp at
least $r_{2}-\kappa$. Hence by Lemma 6.5, all honest PoW blocks mined after
$r_{1}$ and before $r_{2}-\kappa-r_{\rm wait}$ will be included into a PoS
block in $\mathcal{C}(S_{0})$.

Let $S_{1}=\\{u:r_{1}-(4\kappa+\Delta)\leq u\leq r_{2}+\kappa\\}$,
$S_{2}=\\{u:r_{1}\leq u\leq r_{2}-(3\kappa+\Delta)\\}$, and $J$ be the set of
adversary queries associated with ${\mathcal{B}}$ in $S_{1}$. Then by Fact 1
and Fact 2, we have all PoW blocks in ${\mathcal{B}}$ are mined in $S_{1}$; by
Fact 3, we have all PoW blocks mined by honest nodes in $S_{2}$ are in
${\mathcal{B}}$. Hence, $D(S_{2})\leq D_{e-1}\leq D(S_{1})+A(J)$. By
Proposition 2, for each query in $S_{1}$ made by an honest node at slot $r$ in
epoch $e$, the target $T$ must be $T_{e}$, so we have
$(1-\delta)\alpha_{0}f/\gamma^{2}\leq ph_{r}T\leq(1+\delta)\gamma^{2}f$. For
each query in $J$ made by the adversary at slot $r$ in epoch $e$, the target
$T$ may be either $T_{e-1}$ or $T_{e}$, still we have
$(1-\delta)\alpha_{0}f/\gamma^{2}\leq ph_{r}T\leq(1+\delta)\gamma^{2}f$ in
both cases (under a $(\gamma,2R)$-respecting environment). By the fact that
$\alpha_{0}n_{r}\leq h_{r}\leq n_{r}$, we have
$(1-\delta)\alpha_{0}f/\gamma^{2}\leq
pn_{r}T\leq(1+\delta)\gamma^{2}f/\alpha_{0}$.

Under a typical execution, we have

$D(S_{2})>(1-\epsilon)ph(S_{2}),$

and

$\displaystyle D(S_{1})+A(J)$ $\displaystyle<(1+\epsilon)p(h(S_{1})+|J|)$
$\displaystyle=(1+\epsilon)pn(S_{1})\leq(1+\epsilon)ph(S_{1})/\alpha_{0}.$

Therefore, by Proposition 1, we have

$(1-\epsilon)ph^{(e)}|S_{2}|/\gamma<D_{e-1}^{\rm total}<(1+\epsilon)\gamma
ph^{(e)}|S_{1}|/\alpha_{0}.$

By the difficulty adjustment rule, we have $T_{e}=f|S_{0}|/D_{e-1}^{\rm
total}$. Then $T_{e}$ can be bounded as follows:

  * •

Lower bound:

$\displaystyle ph^{(e)}T_{e}$
$\displaystyle\geq\frac{|S_{0}|}{(1+\epsilon)|S_{1}|}\frac{\alpha_{0}f}{\gamma}\geq\frac{(1-\epsilon)|S_{0}|}{|S_{0}|+5\kappa+\Delta}\frac{\alpha_{0}f}{\gamma}$
$\displaystyle\geq\frac{(1-\epsilon)(R-\kappa)}{R+4\kappa+\Delta}\frac{\alpha_{0}f}{\gamma}\overset{(C_{1})}{\geq}\frac{(1-\epsilon)(R-\epsilon
R)}{R+\epsilon R}\frac{\alpha_{0}f}{\gamma}$
$\displaystyle\geq(1-\epsilon)^{3}\frac{\alpha_{0}f}{\gamma}\geq(1-4\epsilon)\frac{\alpha_{0}f}{\gamma}\overset{(C_{2})}{\geq}(1-\delta)\frac{\alpha_{0}f}{\gamma}.$

  * •

Upper bound:

$\displaystyle ph^{(e)}T_{e}$
$\displaystyle\leq\frac{|S_{0}|}{(1-\epsilon)|S_{2}|}\gamma
f=\frac{|S_{0}|}{(1-\epsilon)(|S_{0}|-3\kappa-\Delta)}\gamma f$
$\displaystyle\leq\frac{R-\kappa}{(1-\epsilon)(R-4\kappa-\Delta)}\gamma
f\overset{(C_{1})}{\leq}\frac{R}{(1-\epsilon)(R-\epsilon R)}\gamma f$
$\displaystyle=\frac{1}{(1-\epsilon)^{2}}\gamma
f\leq\frac{1}{1-2\epsilon}\gamma f\leq(1+4\epsilon)\gamma
f\overset{(C_{2})}{\leq}(1+\delta)\gamma f.$

This concludes the proof. ∎

###### Proof sketch of Theorem 6.9.

When moving from the single-epoch setting to the multiple-epoch setting, two
new aspects need to be considered.

  * •

Virtual stake distribution updates. For epochs $e=1,2$, the virtual stake has
the same distribution as the initial stake. Since we assume the initial stake
has honest majority (Assumption 1.1), by Theorem 6.4, CP and $\exists$CQ are
guaranteed in epochs $1\&2$. For epoch $e\geq 3$, the virtual stake of a node
$h$ composes of two parts, the actual stake recorded on the blockchain up to
the last block of the epoch $e-2$ (by Ouroboros (kiayias2017ouroboros, )) and
the work stake decided by the amount of work $h$ has contributed in epoch
$e-2$. Let $S_{s}$ and $S_{w}$ be the total actual stake and total work stake
in epoch $e$. Recall that we set $\omega S_{s}=(1-\omega)S_{w}$ in Minotaur,
i.e., the total virtual stake is $S_{v}=S_{s}/(1-\omega)$. Denote that the
adversary controls $\beta_{s}S_{s}$ actual stake and let $\beta_{w}$ be
maximum fraction of adversarial mining power in epoch $e-2$, i.e.,
$\beta_{w}=1-\min_{r\in[(e-3)R+1,(e-2)R]}{(h_{r}/n_{r})}$. By Assumption 2.1,
we have $\omega\beta_{w}+(1-\omega)\beta_{s}\leq 1/2-2\sigma$. And by Theorem
6.8, honest nodes control at least $(1-\sigma)(1-\beta_{w})S_{w}$ work stake
for epoch $e$. Therefore, the virtual stake controlled by the adversary is at
most

$\displaystyle\;\;\;\;\beta_{s}S_{s}+(1-(1-\sigma)(1-\beta_{w}))S_{w}$
$\displaystyle=((1-\omega)\beta_{s}+\omega(\beta_{w}+\sigma(1-\beta_{w}))))S_{v}$
$\displaystyle\leq(1/2-\sigma)S_{v}.$

Therefore, by an induction argument, we can guarantee an honest majority in
the virtual stake for all epochs. The analysis critically relies on the fact
that the CP property is immutable: specifically, when all honest parties agree
on a common prefix $\mathcal{C}^{(t)}$ at some slot $t$ and, as maxvalid-mc
can only revise the last $k$ blocks of a currently adopted chain,
$\mathcal{C}^{(t)}$ will be a prefix of all future chains held by the honest
parties. Check the proof of Theorem 5.3 in (kiayias2017ouroboros, ) for
details.

  * •

Randomness updates. Every epoch needs new public randomness to be used for
sampling slot leaders from the above virtual stake distribution. In Ouroboros
(kiayias2017ouroboros, ), elected slot leaders (one per slot) from epoch $e-1$
runs a publicly verifiable secret sharing (PVSS) protocol to generate the
randomness for epoch $e$. The core idea is the following: given that we have
guaranteed that an honest majority among elected leaders in epoch $e$ will
hold with very high probability, we have that the PVSS protocol suitably
simulates a beacon with the relaxation that the output may become known to the
adversary before it is known to the honest parties. However, as long as the
distribution of virtual stake is determined prior to this leakage, the
sampling of leaders in epoch $e$ will still be unbiased.

At last, by our definition, the CP property with parameter $\ell_{cp}=\kappa$
is equivalent to the persistence of the ledger (when the confirmed ledger is
defined as $\mathcal{C}^{\lceil\kappa}$). Meanwhile, the CP property with
parameter $\ell_{cp}=\kappa$, together with the $\exists$CQ property with
parameter $\ell_{cq}=\kappa$, implies liveness with parameter $u=2\kappa$.
Indeed, for a chain $\mathcal{C}$ held by an honest node at slot $r$, there
must be at least one honest block $B^{*}$ in $\mathcal{C}^{\lceil\kappa}$ with
timestamp in $[r-2\kappa,r-\kappa]$ (by $\exists$CQ), then any transaction
that appears before $r-2\kappa$ should be included by either $B^{*}$ or its
ancestors, thus the transaction should be confirmed (by CQ/persistence). ∎

##  Appendix E Details on the Ouroboros Protocol Family

We give a summary of the different PoS protocols we explicitly base our
generic hybridization construction on in the main part of the paper, Ouroboros
Classic (kiayias2017ouroboros, ), Praos (david2018ouroboros, ), and Genesis
(badertscher2018ouroboros, ). In order of this sequence, each version of the
protocol gives stronger security guarantees.

We first give quick summaries of the respective protocol guarantees and their
underlying assumptions. Finally, in Appendix E.1, we give a more detailed
description of Ouroboros Praos as the reference protocol; and sketch how the
other variants differ from it.

##### Ouroboros Classic.

Classic is secure against a minority of adversarially controlled stake under
the following assumptions:

:

Network. The communication network is synchronous.

:

Corruption. The adversary is ‘moderately’ adaptive (participant corruption
only takes effect after a certain delay).

:

Stake shift. There is an upper bound on the stake shift, i.e., the stake
distribution among the stake holders does not change too fast.

:

Offline tolerance. The protocol participants only go offline for short periods
of time.

##### Ouroboros Praos assumptions:

Praos is secure against a minority of adversarially controlled stake under the
following assumptions:

:

Network. The communication network is semi-synchronous, i.e., that the network
delay is bounded bu some delay $\Delta$ not known to the participants.

:

Corruption. The adversary is fully adaptive.

:

Stake shift. As in Classic.

##### Ouroboros Genesis assumptions:

Classic is secure against a minority of adversarially controlled stake among
all participants who are active in the system—under the following assumptions:

:

Network. As in Praos.

:

Corruption. As in Praos.

:

Offline tolerance. The protocol participants can join later during any stage
of the protocol, or go offline for extended periods of time during
participation.

###  E.1. Ouroboros Praos

The protocol proceeds in epochs of $R$ slots, each slot representing a given
‘unit of time’, say, $1$ second of the protocol run-time. For ease of
exposition, let the genesis block represent epoch $0$ of the protocol. We now
describe how the protocol operates per epoch $e>0$.

##### Slot-leader election.

During each slot $\mathrm{sl}_{j}$, a slot-leader election is held among the
stakeholders, and a winning stakeholder is allowed to publish a new block
associated with this slot.

The slot-leader election during epoch $e$ is based on the stake distribution
at the end of epoch $\max(0,e-2)$, i.e., the stake distribution that results
after the processing of the last block of epoch $e-2$ (or the stake
distribution from the genesis block).

Let $\alpha_{i}$ be the relative stake held by stake holder $\mathsf{P}_{i}$
(holding $\alpha_{i}\cdot S$ of the total stake $S$) at the end of epoch
$\max(e-2,0)$. Per slot, the probability $p_{i}$ for stakeholder
$\mathsf{P}_{i}$ to be a block leader is defined as

(2)
$p_{i}=\phi_{f}(\alpha_{i})\stackrel{{\scriptstyle\triangle}}{{=}}1-(1-f)^{\alpha_{i}}$

for some appropriate _active-slots coefficient_ $f$ (the probability that,
among the total stake, at least one slot leader is elected during any given
slot).

Slot leadership is pseudo-randomly assigned based on the _epoch nonce_ $\eta$,
a seed calculated in epoch $e-1$ (as described further below). To become a
slot leader for slot $\mathrm{sl}_{m}$, the stakeholder $\mathsf{P}_{i}$
evaluates a verifiable random function (VRF) (bound to a public key registered
by $\mathsf{P}_{i}$) $(y,\pi)=\mathsf{VRF}_{i}(\eta,\mathrm{sl}_{m})$. Slot
leadership is satisfied iff

$y\stackrel{{\scriptstyle!}}{{<}}T\stackrel{{\scriptstyle\triangle}}{{=}}2^{\ell_{\mathsf{VRF}}}\cdot\phi_{f}(\alpha_{i}),$

where $\mathsf{VRF}_{i}$ produces outputs of $\ell_{\mathsf{VRF}}$ bits, and
$T$ is a threshold to enforce the desired probabilities.

##### Block production.

Besides a hash of its predecessor and the payload, a block contains

  * •

the slot number $m$;

  * •

the above proof of leadership $(y,\pi)$ (such that $y<T$);

  * •

an additional, independent, VRF output $(y_{\rho},\pi_{\rho})$ contributing to
the epoch-nonce generation; and

  * •

a signature on $(m,(y,\pi),(y_{\rho},\pi_{\rho}))$ by $\mathsf{P}_{i}$ of a
key-evolving signature scheme (KES).444The stakeholders update the private
keys of their KES instance after every slot.

##### Block settlement.

A block is considered settled if it sits at least $k$ blocks deep in a node’s
main chain where $k$ is the _prefix parameter_ of the protocol.

##### Chain selection rule: maxvalid-mc.

Upon the arrival of a new block, each node chooses, as their main chain, the
longest chain that does not fork from the previous main chain by more than $k$
blocks where $k$ is the prefix parameter.

##### Epoch-nonce generation.

The epoch nonce $\eta$ for epoch $e>1$ is computed as a hash of all VRF
outputs $y_{\rho}$ included in the blocks of the main chain up to $2/3$ of
epoch $e-1$. The epoch nonce for epoch $e=1$ is included in the genesis block.

###  E.2. Differences in Classic and Genesis

##### Classic.

The main difference to Praos is that the epoch randomness is obtained from a
coin-flip protocol based on a publicly verifiable secret sharing protocol—with
the disadvantage that the leader schedule is public and thus allows for
adaptive corruption.

##### Genesis

Genesis differs from Praos by applying a different chain selection rule to
allow protocol participants to be offline for extended periods of time. The
modified chain-selection rule maxvalid-bg works as follows: A longer chain is
adopted if

  * •

it forks from the current main chain by at most $k$ blocks; or

  * •

if forks by more than $k$ blocks but contains more blocks in the $s$ slots
following the last common block of the main chain and the longer chain.

##  Appendix F Analysis tightness

The analysis of our main security theorem, Theorem 6.1, draws from
(kiayias2017ouroboros, ). A more careful and improved analysis appears in
(bkmqr2020, ), from which we may obtain the refined bound
$1-RL(e^{-\Omega(\delta^{3}\kappa)}+e^{-\lambda})$ for the statement of
Theorem 6.1. In this section we analyze a private chain attack and show a
corresponding lower bound. It reveals that $\delta^{2}\kappa$ needs to be
bounded below by a constant and, consequently, the dependency on $\delta^{3}$
cannot be improved much further.

###### Proposition 3.

Common prefix does not hold against a $(1/2-\delta,m,\omega)$-bounded
adversary, for $\delta\leq 1/\sqrt{\ell_{\rm cp}}$ and sufficiently large
$\ell_{\rm cp}$.

###### Proof.

The adversary follows the protocol using his mining power to produce PoW
blocks. The attack begins when the virtual stake of the adversary is
$\omega\beta_{w}+(1-\omega)\beta_{s}\geq\frac{1}{2}-\delta$.

Define the random variable $X_{i}$ taking values in $\\{-1,0,1\\}$ according
to who produced blocks of height $i$. If it was the adversary only, then
$X_{i}=1$; if both the adversary and honest parties, then $X_{i}=0$; if honest
parties only, then $X_{i}=-1$. Let $p=1-(1-f)^{1/2+\delta}$ and
$q=1-(1-f)^{1/2-\delta}$. We have

$\displaystyle\Pr[X_{i}=-1]=p(1-q)/f,\quad$
$\displaystyle\Pr[X_{i}=1]=q(1-p)/f,\quad\text{and}\quad$
$\displaystyle\Pr[X_{i}=0]=pq/f.$

Note that the adversary will create a fork of length $k$, if
$X_{1}+\cdots+X_{k}\geq 0$. We will use the Berry-Esseen bound to lower bound
the probability he succeeds. To that end we compute

$\displaystyle\mu$
$\displaystyle=\mathbb{E}[X_{i}]=(q-p)/f=[(1-f)^{1/2+\delta}-(1-f)^{1/2-\delta}]/f$
$\displaystyle=[(1-f)^{1+\delta}-(1-f)^{1-\delta}]/[f(1-f)^{1/2}]$
$\displaystyle>[(1-f)^{1+\delta}-(1-f)^{1-\delta}]/f>-2\delta,$
$\displaystyle\sigma^{2}$
$\displaystyle=\mathbb{E}[X_{i}^{2}]-\mu^{2}=1-pq/f-\mu^{2}>1-f-4\delta^{2},$
$\displaystyle\rho$
$\displaystyle=\mathbb{E}[|X_{i}-\mu|^{3}]<(1+2\delta)^{3}.$

Observe that for $\delta\leq 1/3$ and $f\leq 1/9$.

Let $F_{k}=(X_{1}+\cdots+X_{k}-\mu k)/\sqrt{k\sigma^{2}}$. By the Berry-Essen
Theorem we have that, for $\delta\leq 1/\sqrt{k}$,

$\displaystyle\Pr\Bigl{[}F_{k}\geq-\mu k/\sqrt{k\sigma^{2}}\Bigr{]}$
$\displaystyle\geq\Phi^{c}\bigl{(}3)-O\bigl{(}k^{-1/2}\bigr{)}.$

∎

Although it might be possible to strengthen the above attack and analysis to
obtain slight improvements, it remains an open question whether the
exponential drop in the probability of security failure is in the order of
$\delta^{3}\kappa$ or $\delta^{2}\kappa$.