Nakamoto Consensus from Multiple Resources

Three very different blockchain designs whose main resource is disk space are Chia [10], Filecoin [17], and Spacemint [33]. The first two are deployed and running in practice, while the latter is an academic proposal.

Of the above, Chia is the only one captured by our result, i.e., it is a Nakamoto-like protocol in the fully-permissionless setting. Its weight function is ${\mathrm{\Gamma }}_{\text{Chia}}(S,V,W)=S\cdot V$ which is secure against double-spending attacks by our Thm.˜1.1.

Spacemint was an early proposal of a fully-permissionless blockchain based solely on proofs of space, and thus cannot be secure against double-spending attacks according to Thm.˜1.1. The design of Spacemint slightly defers from Nakamoto’s chain-selection rule as older blocks are given less weight than more recent ones, but even with this twist the security of Spacemint against double-spending only holds if the honest space never decreases by too much, and never increases too fast.

In contrast, Filecoin is not captured by our result because it is not fully-permissionless, but instead operates in the stronger quasi-permissionless setting (cf. [30]).⁴⁴4Filecoin is also not Nakamoto-like since it is a DAG-based protocol (using GHOST, the Greediest Heaviest-Observed Sub-Tree rule [38]) together with a finality gadget [1]. Note that the finality gadget is not essential, and GHOST is the DAG-analogue to Bitcoin’s longest/heaviest-chain rule. So, for our purposes, Filecoin could easily be modified to be Nakamoto-like (this has also been mentioned in [2]). As we’ll elaborate in §4.3, it seems running a space based chain in the quasi-permissionless setting is quite expensive as to prevent reploting parties must constantly prove they hold the committed space and this proofs need to be recorded on chain. Since Filecoin’s weight function is ${\mathrm{\Gamma }}_{\text{Filecoin}}(S,V,W)=S$, Thm.˜1.1 essentially shows that a setting stronger than the fully-permissionless one is necessary.

Let us stress that, even in the fully-permissionless setting and when only relying on space, we only rule out secure constructions of Nakamoto-like blockchains (where the weight of a chain is the sum of the weights of its blocks, and the chain selection rule picks the heaviest chain). While most fully-permissionless blockchains are of this form, this does not rule out the possibility that a completely different chain selection rule would be secure. A recent work [7] shows that, unfortunately, this is not the case, and no such chain-selection rule exists. It gives a concrete attack against any chain-selection rule, and an almost matching lower-bound, i.e., a concrete (albeit very strange) chain-selection rule for which this attack is basically optimal.

Since the production of Bitcoin mining-hardware has become increasingly centralized, one might consider combining two different PoWs, e.g., $W_1$ using SHA256 and $W_2$ using Argon2. As stated above, Thm.˜1.1 only considers one parallel work $W$, but it naturally extends to multiple resources of each type. In particular, our results capture weight functions such as $\mathrm{\Gamma }(W_1,\mathrm{\dots },W_k)$ with Condition 2 being $\alpha \mathrm{\Gamma }(W_1,\mathrm{\dots },W_k)=\mathrm{\Gamma }(\alpha W_1,\mathrm{\dots },\alpha W_k)$ for $\alpha >0$.

Prior work [18] suggested the weight function $\mathrm{\Gamma }(W_1,\mathrm{\dots },W_k)={\sum }_{i=1}^k{\omega }_i{W}_i$ with constants ${\omega }_i$. By Thm.˜1.1, this is secure against private double-spending, but not a desirable weight function in practice. Even though the constants ${\omega }_i$ can be used to calibrate the contribution of each PoW, it seems difficult to realize this in a way that would prevent miners to ultimately only invest in the cheapest PoW.

Our result show that more interesting combinations of $W_1,\mathrm{\dots },W_k$ are possible. The first draws inspiration from automated-market-makers⁵⁵5https://en.wikipedia.org/wiki/Constant_function_market_maker and is defined as

To maximize this weight function (for a given budget), one would have to invest into mining hardware for all PoWs at a similar rate.

Another option is the Leontief utilities function⁶⁶6https://en.wikipedia.org/wiki/Leontief_utilities

which ensures that all PoWs must significantly contribute.

Our work just classifies the weight functions that are secure in the sense that we get security against private double-spending whenever the honest parties control resources of higher weight (as specified by the weight function). A question that is mostly orthogonal to this work is to investigate which of those weight functions are also interesting from a practical perspective, say because they incentivize decentralization or other desirable properties. Let us observe that the class of secure weight functions does contain functions that make little sense in practice, for example the function $\mathrm{\Gamma }(V)=V$ which simply counts the number of VDF steps. A blockchain based on this weight function would be secure assuming some honest party holds a VDF that is faster than the VDF held by the adversary.

Our model captures resources that are external to the chain, i.e., physical resources. In particular, we consider disk space $S$, sequential computation $V$, and parallelizable computation $W$ where we allow multiple resources per type, e.g., $W_1$ and $W_2$.⁷⁷7These are three fundamental resources in computation, and also the most popular physical resources used for blockchains. Nevertheless, we believe our model could be extended to other external resources. Each resource is modelled as a function mapping time ${ℝ}_{\ge 0}$ to an amount ${ℝ}_{>0}$. This is expressive enough to capture, e.g., Bitcoin, any other PoW-based blockchain, or Chia.

In practice, cryptographic primitives are used to track these resources, usually Proof-of-Space (PoSpace) [15], Verifiable Delay Functions (VDFs) [9, 41, 36], and Proof-of-Work (PoW). Our modelling essentially assumes a perfect primitive, glossing over implementation details and any probabilistic nature of the resource (similar to [39]).

In practice parallel work $W$ as captured by a PoW, and sequential work $V$ as captured by a VDF are very different. $W$ is a quantitative resource in the sense that one can double it by investing twice as much, while $V$ is a qualitative resource as it measures the speed of the fastest available VDF. From the perspective of our Theorem on the other hand, $W$ and $V$ behave the same, the only thing that matters in the (proof of the) Theorem is that $W$ and $V$ are “timed” resources in the sense that their unit is something “per second”. $W$ and $S$ on the other hand are both quantitative resources, but behave very differently.

First, as described by Roughgarden and Lewis-Pye [30], stake-based blockchains do not operate in the fully-permissionless setting. Therefore, since our result targets this setting, modelling stake is not possible.

Another reason is that in our modeling we assume that parties hold some resources at some given time, for an on-chain resource like stake this is not well defined as the resource is only defined with respect to some particular chain, i.e., for different forks the parties would hold different resources at the same time. To make issues even more tricky, with stake it’s possible to obtain old keys that no longer hold any value, but still can be used in an attack [2].

Towards Thm.˜1.1, we will first consider the Continuous Chain Model. While it is a very abstract model, it is rich enough to already yield Conditions 1 and 2. In a nutshell, we assume that a chain continuously and exactly reflects the resources that were expended to create it.

Assume that the honest parties at time $t$ hold resources $S(t),W(t),V(t)$, then the chain they can create in a time window $[t_0,t_1]$ will have weight ${\int }_{t_0}^{t_1}\mathrm{\Gamma }(S(t),V(t),W(t))𝑑t$.

This continuous model avoids some issues of actual blockchains, like their probabilistic nature or network delays. For example in Bitcoin, a so called $51\%$ attack can actually be conducted with less, say, $41\%$ of the hashing power if network delays are sufficiently large. Moreover, as a Bitcoin block is found every 10 minutes in expectation, it frequently happens that no block is found in an hour at all. For this reason a block is only considered confirmed if it’s sufficiently deep in the chain. These factors only have a quantitative impact on the concrete security threshold of longest-chain blockchains and are well understood [20, 14]. The goal of this paper, however, is qualitative in nature. That is, we want to describe which weight functions are secure against private double-spending attacks as long as honest parties have sufficiently more resources than the adversary. Precisely quantifying how much security is lost due to the fact that resources are only approximately recorded, due to network delays or other aspects like double dipping attacks is not our goal.

So far we considered a strongly idealized setting where the blockchain recorded the available resources continuously and exactly, both can not be met in a practical blockchain⁸⁸8At least not if they use a quantitative resource $S$ or $W$, which only leaves $V$, but speed alone will not make a good chain. where the quantitative resource $S$ or $W$ is distributed over an a priori unlimited number of miners, but for practical reasons we only want a bounded number to actually give input to a block. In Bitcoin and Chia, it is just a single miner that finds a proof that passes some difficulty, and the frequency at which such proofs are found gives an indication of the total resource. We can get a good approximation of the resources by waiting for sufficiently many blocks or using a design where multiple miners contribute to a block, say we record some $k>1$ best proofs found since the last block in every block. In this work, we will not further deal with the fact that resources are not exactly recorded as it is not very informative for the ideal perspective we are taking. In actual constructions like Bitcoin one deals with this by requiring some time before considering blocks as confirmed. The number of blocks to wait is computed using a tail inequality, it depends on the probability of failure one can accept and on the quantitative gap one assumes between honest and adversarial resources.

So far, we discussed an abstract model where the chain continuously and exactly records resource expenditure.

In §4 we discuss a model closer to a real blockchain, where blocks arrive in discrete time slots. We still assume the block exactly records the resources $W$ and $V$. In particular, a block produced during some timespan $[a,b)$ records $W_{\mathrm{■}}={\int }_a^{b}W(t)𝑑t$ and $V_{\mathrm{■}}={\int }_a^{b}V(t)𝑑t$. For the space we assume that the block records $S(t)$ at some point . The reason for this difference is that $W$ and $V$ are resources that are measured per second (e.g., hashes/s or steps/s), so integration over time is well-defined. One the other hand, a proof of space gives a snapshot of the space $S(t)$ available at some point $t$ during block creation. To be on the safe side, we simply assume that the adversary can choose the time $t$ where its space was maximal, while for the honest parties we assume $t$ is the time when $S(t)$ was minimal.

We show (Theorem 4.9) that the classification of secure weight functions basically carries over to this discrete setting as long as the resources don’t vary by too much within the block arrival time. But our main motivation to consider the discrete model is to discuss the issue of replotting attacks in §4.3, which only make sense in a discrete setting.

Recently, Roughgarden and Lewis-Pye [30] (an updated version of [29]) presented many (im)possibility results about permissionless consensus. They consider a resource-restricted adversary where resources can be external or on-chain resources. External resources are modelled by so-called permitter oracles, whose outputs depend on the amount of resources the querying party has at the time of the query. An important part of their work is a classification of the permissionlessness of consensus protocols:

• $\mathrm{■}$

  Fully-permissionless protocols are oblivious to its participants (e.g., Bitcoin).

• $\mathrm{■}$

  Dynamically-available protocols know a dynamic list of parties, which may be a function of the past protocol execution (e.g., parties who staked coins), the participants are a subset of this list, and at least one honest member of this list participates.

• $\mathrm{■}$

  Quasi-permissionless protocols are similar to dynamically-available protocols, but make the stronger requirement that all honest members of the list participate. Note that such protocols differ from permissioned ones, which also have a list of parties, but where the list cannot depend on the past protocol execution.

For example, a result of theirs states that no deterministic protocol solves Byzantine agreement in the fully-permissionless setting, even with resource restrictions.

Two preceding works modelling abstract resources are Terner [39] and Azouvi et al. [2]. Terner [39] considers an abstract resource that essentially is a black-box governing participant selection. They give a consensus protocol that can be instantiated with any such resource satisfying certain properties (e.g., resource generation must be rate-limited relative to the maximum message delay). Both [39, 2] consider only a single resource and not combination of multiple resources.

Azouvi et al. [2] use the abstraction of resource allocators (similar to permitter oracles in [30]) to build a total-ordered broadcast protocol. They describe the properties a resource allocator must fulfill (e.g., honest majority), and construct resource allocators for the resources stake, space¹⁰¹⁰10Their space allocator lies in the quasi-permissionless model, thus not conflicting with our results., and work. As part of this, they classify resources as external vs. on-chain (they call it virtual), and burnable vs. reusable (space and stake are reusable whereas work is not) and discuss trade-offs between different types of resources, e.g., on-chain resources are susceptible to long-range attacks. A limitation of [2] is that total resource is a priori known and fixed. In our model all resources can vary and are known only when the blocks are created.

We give a selection of well-known permissionless blockchain designs, describing the weight function or – for non-Nakamoto-like protocols – resource ($S$, $V$ and $W$ as before, and stake St) and degree of permissionlessness (fully-permissionless, dynamically-available, or quasi-permissionless): Bitcoin [31] (fp, $W$), Chia [10] (fp, $S\cdot V$), Filecoin [17] (qp, $S$), Ethereum [42] (da/qp,¹¹¹¹11Depending on whether the network is synchronous/partially-synchronous [30]. St), Algorand [24] (qp, St), Ouroboros [27, 12, 3] (da/qp, St), Snow White [11] (da, St).

Multiple combinations of proof-of-stake (PoStake) and PoW, e.g., [28, 8, 18] exist (all either da or qp). [18] is the only fungible protocol, i.e., it is secure as long as the adversary controls less than half of all stake and work cumulatively (essentially mapping to $\mathrm{\Gamma }(\text{St},W)=\text{St}+W$). Their protocol handles multiple PoStake and multiple PoW resources, thus capturing $\mathrm{\Gamma }(W_1,W_2)=W_1+W_2$, which we discussed in §˜1.2.

[13] combine PoStake with sequential computation to create a dynamically-available protocol.

Ignoring difficulty, Bitcoin assigns unit weight to every block whose hash surpasses a threshold. [26] analyze other functions assigning weight to block hashes. They suggest using a function that grows exponentially, but is capped at a certain value, which depends on the maximum network delay.

Various works analyze specific blockchains, mostly Bitcoin (or similar PoW chains) [19, 34, 35, 37, 20], but also longest-chain protocols in general [14]. These generally give quantitative security thresholds (i.e., what fraction of adversarial resources is tolerable) depending on, e.g., maximum message delay. We again remark that our work has a different aim, namely a qualitative description of weight functions, disregarding precise security thresholds.

To model this attack, we first consider the time frame of the attack. The attack starts (i.e., the adversary forks the chain) at time $0$, and the adversary publicly publishes its private chain at time $T_{\mathrm{𝖾𝗇𝖽}}$. So the attack spans the time interval $[0,T_{\mathrm{𝖾𝗇𝖽}}]$. During this time, the resources available to the honest parties are given by the resource profile ${ℛ}^{\mathscr{H}}$, and they use them to build the honest chain profile $𝒞{𝒞}^{\mathscr{H}}$ in the following way:

That is, the honest chain $𝒞{𝒞}^{\mathscr{H}}$ correctly reflects the resources available to honest parties, and also precisely keeps track at which point in the resources were available.¹⁴¹⁴14While this is by construction in our idealized model, timestamps are generally accurate in longest-chain blockchains – even if a not-too-powerful adversary tries to disrupt them [40].

The adversary’s resources are ${ℛ}^{𝒜}$, and they use them to build the chain profile $𝒞{𝒞}^{𝒜}$.¹⁵¹⁵15In general, we use the superscripts ${}^{\mathscr{H}}$ and ${}^{𝒜}$ to denote the honest parties and the adversary, respectively. In contrast to the honest parties, the adversary may deviate from the protocol and cheat. First, they may simply not use some of the resources available to them. Second, and more importantly, since the adversary creates the fork in private, the chain $𝒞{𝒞}^{𝒜}$ may not correctly reflect at what time the resources were available. In essence, the adversary can alter the time by stretching and squeezeing it. For example, in Bitcoin the adversary may mine a block in $100$ minutes but pretend to have mined it within $10$ minutes.

We model this time manipulation by a function $\varphi (t)$ describing the squeezing/stretching factor at any point in time. At time $t$, $\varphi (t)>1$ represents squeezing, stretching, and $\varphi (t)=1$ no alteration. Altering the time affects, e.g., the length of the interval $[0,T_{\mathrm{𝖾𝗇𝖽}}]$. To this end, we introduce the altered time function $\mathrm{𝖠𝖳}$ (and its inverse ${\mathrm{𝖠𝖳}}^{-1}$)¹⁶¹⁶16${\mathrm{𝖠𝖳}}^{-1}$ exists because $\frac{1}{\varphi (u)}>0$ for all $u$, so ${\int }_0^t\frac{1}{\varphi (u)}𝑑u$ is a monotonically increasing function of $t$ with co-domain $[0,\mathrm{𝖠𝖳}(T_{\mathrm{𝖾𝗇𝖽}})]$. to translate between time before and after squeezing/stretching. For example, ${\tilde{T}}_{\mathrm{𝖾𝗇𝖽}}=\mathrm{𝖠𝖳}(T_{\mathrm{𝖾𝗇𝖽}})$, resulting in the interval $[0,{\tilde{T}}_{\mathrm{𝖾𝗇𝖽}}]$.¹⁷¹⁷17We use $\stackrel{~}{}$ to denote time after squeezing/stretching.

Altering time affects how $𝒞{𝒞}^{𝒜}$, which covers the time interval $[0,{\tilde{T}}_{\mathrm{𝖾𝗇𝖽}}]$, reflects resources. For the resources $V$ and $W$, altering time cannot change the cumulative amount (e.g., in Bitcoin it cannot change the number of found blocks and thus work performed). Therefore, $V$ and $W$ must be multiplied by $\varphi$. That is, at altered time $\tilde{t}\in [0,{\tilde{T}}_{\mathrm{𝖾𝗇𝖽}}]$, $𝒞{𝒞}^{𝒜}$ records the resource $\varphi (t)V^{𝒜}(t)$ and $\varphi (t)W^{𝒜}(t)$. The disk space $S$ behaves differently. As long as it is available, it can be reused [2], so it does not accumulate (unlike $V$ and $W$). As a consequence, altering time just changes when space was available. Thus, at altered time $\tilde{t}\in [0,{\tilde{T}}_{\mathrm{𝖾𝗇𝖽}}]$, $𝒞{𝒞}^{𝒜}$ records $S({\mathrm{𝖠𝖳}}^{-1}(\tilde{t}))$.

Let us illustrate the stretching and squeezing from Def.˜3.10 by the example of Bitcoin and Chia in Figures 1 and 2.

We now have all ingredients to define when a weight function is secure against PDS attacks. On a high level, the definition states that an adversary having resources of less weight than the honest parties¹⁸¹⁸18Clearly, a PDS attack always works when the adversary has a resource advantage. cannot create a private chain that is heavier than the honest parties one – even by manipulating time. In more detail, “less weight” means that the adversary has at most equal weight at every point in time (Equation 1), and in some interval it has strictly less (Equation 2).

Without any extra assumptions, replotting leads to attacks in the discrete model. For the sake of example, consider Chia’s weight function $S\cdot V$, which is secure according to Thm.˜4.9. Assume replotting takes time $\rho =2$, $S^{𝒜}=V^{𝒜}=1$ and $S^{\mathscr{H}}=V^{\mathscr{H}}=1.1$ (this gap suffices since both profiles are $1$-smooth), and consider the timespan $[0,6]$. The honest parties create $5$ blocks with a cumulative weight of $6\cdot (1.1\cdot 1.1)\approx 7.3$. The adversary creates one block in which it replots once. Assuming that the adversary cannot do anything else while replotting (i.e., it can only gain $V$ for $4$ time), the weight of the block is $4\cdot (2\cdot 1)=8$. Note that this attack generalizes to other weight functions $\mathrm{\Gamma }$ and other values of $\rho$.

One way to disincentive replotting in the discrete model is bounding the total weight of a block $b$. Consider that the protocol keeps track of a difficulty $D$ that is periodically adjusted so that roughly one block is created per time unit (e.g., in Bitcoin the difficulty is reset once every two weeks so blocks arrive roughly every 10 minutes). Further, let $\eta \ge 1$ be a protocol parameter (to be set later). Then, the protocol bounds the weight of blocks as $D\le \mathrm{\Gamma }(b)\le \eta \cdot D$ (abusing notation of $\mathrm{\Gamma }$ slightly).

If we now set , it is not hard to see that replotting does not help: Replotting even once requires $\rho$ time, and the resulting adversarial block has at most weight. Meanwhile, the honest parties produce around $\rho$ blocks, each of weight at least $D$; so in total $\rho \cdot D$.

Note that this argument requires $D$ to stay fixed, an attacker might still be able to create a heavier chain over a long period of time that spans several epochs (where the difficulty is reset once every epoch).

Chia [32] with its weight function $\mathrm{\Gamma }(S,V)=S\cdot V$ uses a similar idea, but it tracks the difficulty of the space and VDF separately. The block arrival time is only determined by the VDF difficulty, which is nice as VDF speed hardly fluctuates at all over time.

One can generalize this idea to any weight function that can be written as $\mathrm{\Gamma }(𝑺,𝑽,𝑾)={\mathrm{\Gamma }}_1(𝑺)\cdot {\mathrm{\Gamma }}_2(𝑽,𝑾)$. Now one would require that each block that records resources $𝒗,𝒘,𝒔$ must satisfy ${\mathrm{\Gamma }}_2(𝒗,𝒘)=D$. One doesn’t need to put an additional upper bound on the space ${\mathrm{\Gamma }}_1(𝒔)$ if ${\mathrm{\Gamma }}_1$ is subhomogenous, i.e., for any $\alpha >1$ we have ${\mathrm{\Gamma }}_1(\alpha 𝒔)\le \alpha {\mathrm{\Gamma }}_1(𝒔)$ (Chia does both, it is (sub)homogenous and has an upper bound).

As mentioned, the above solutions don’t formally prevent replotting attacks that range over many epochs. In practice that might not be such a big issue, as extremely long range attacks are not really practical: they require a lot of resources for a long period of time, and thus are expensive to launch. Moreover it might be difficult to convince honest parties to accept a very long fork as it’s such an obvious attack. It still would be interesting to understand whether it’s possible to formally achieve security against replotting attacks, we leave this for future work.