Nakamoto Consensus from Multiple Resources

Mirza Ahad Baig, Christoph U. Günther, Krzysztof Pietrzak · 2025

Read Nakamoto Consensus from Multiple Resources by Mirza Ahad Baig, Christoph U. Günther, Krzysztof Pietrzak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01448.txt.

Introduction

Mirza Baig, Christoph Günther, and Krzysztof Pietrzak ask which resource mixes can safely secure a Bitcoin-style blockchain, in a 2025 paper. Bitcoin orders its blocks by recorded work, and the longest, heaviest chain wins. Other chains use different resources: Chia records storage space and sequential computing steps alongside work. The authors study weight functions that blend space, speed, and work into one score per block.

In an idealized continuous model, they fully classify which blends are safe against private double-spending attacks. The safe ones are exactly those where the honest parties' weight beats the attacker's weight under the blend. The result draws a clean boundary for designers who want to secure new chains with cheaper or greener resource mixes.

Catalog record

CREATORMirza Ahad Baig, Christoph U. Günther, Krzysztof Pietrzak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-01448

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Nakamoto Consensus from Multiple Resources Mirza Ahad Baig, Christoph U. Günther, Krzysztof Pietrzak Abstract The blocks in the Bitcoin blockchain “record” the amount of work W W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S S (via a proof of space) and sequential computational steps V V (through a VDF). In this paper, we ask what weight functions Γ ⁡ ( S , V , W ) \Gamma(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks. We completely classify such functions in an idealized “continuous” model: Γ ⁡ ( S , V , W ) \Gamma(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the “timed” resources V V and W W , i.e., α ​ Γ ​ ( S , V , W ) = Γ ⁡ ( S , α ​ V , α ​ W ) \alpha\Gamma(S,V,W)=\Gamma(S,\alpha V,\alpha W) . This includes the Bitcoin rule Γ ⁡ ( S , V , W ) = W \Gamma(S,V,W)=W and the Chia rule Γ ⁡ ( S , V , W ) = S ⋅ V \Gamma(S,V,W)=S\cdot V . In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S S (basically, the weight should not grow too much if S S is slightly increased, say linear as in Chia). Our classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W 1 W_{1} and a memory-hard PoW W 2 W_{2} . Previous work suggested to use W 1 + W 2 W_{1}+W_{2} as weight. Our results show that using e.g., W 1 ⋅ W 2 \sqrt{W_{1}}\cdot\sqrt{W_{2}} or min ⁡ { W 1 , W 2 } \min\{W_{1},W_{2}\} are also secure, and we argue that in practice these are much better choices. 1 Introduction Achieving consensus in a permissionless setting is a famously difficult problem. Nakamoto solved it by introducing the Bitcoin blockchain [ Nak09 ] that achieves consensus on a chain of blocks by having parties expend a resource : parallelizable computation (commonly called work ). In Bitcoin, appending a block to a chain requires a proof-of-work (PoW), i.e., solving a computationally-expensive puzzle. This puzzle is designed such that each block represents the (expected) amount of computation that was expended to append it. As a consequence, each chain represents the total amount of computation required to create it. This allows for a simple consensus mechanism commonly called the longest-chain rule : Given two different chains, pick the one that required more computation to create. Note that a more accurate term is heaviest-chain rule , which we will use interchangeably throughout the paper. While this design achieves consensus, more importantly it also achieves a property called persistence [ GKL15 ] under a simple economic assumption: As long as honest parties control more than half of the computational resources committed to Bitcoin, a block that has been part of the chain for some time will always be part of the chain. Since Bitcoin blocks contain transactions, this effectively means that an adversary cannot double-spend a coin. While Bitcoin’s design is simple, its reliance on PoW has its flaws. For example, it wastes a lot of energy, and the manufacturing of the PoW hardware has become increasingly centralized. Amongst other reasons, this has lead to the development of other blockchain protocols. These protocols can be broadly categorized along three axes. The Underlying Resources Bitcoin relies on parallelizable computation, which is a physical resource . Two natural alternatives are disk space and sequential computation . A different class of resources is not physical, but on-chain [ ACL+23 , LPR24 ] . The most well-known is stake , which comprises different approaches that essentially rely on the on-chain coin balance of a party. The Consensus Design A broad distinction is between Byzantine-fault-tolerant-style (e.g., Algorand [ GHM+17 ] or Filecoin [ Fil24 ] ) and longest-chain protocols. Within themselves, longest-chain protocols differ in their fork-choice rule , which prescribes how they select the longest chain. Some are Nakamoto-like and, like Bitcoin, pick the heaviest chain, i.e., the one whose blocks cumulatively required the most resources to create (e.g., Chia [ CP19 ] ). Others rely on more complex fork-choice rules that, e.g., take into account where two chains fork (e.g., Ouroboros [ BGK+18a ] ). The Degree of Permissionlessness Roughgarden and Lewis-Pye [ LPR24 ] observe that “permissionless” is colloquially used to describe different settings that vary in how permissionless they are. Fully-permissionless protocols function obliviously to current protocol participants (e.g., Bitcoin or Chia). These differ from protocols that require some information about participants (e.g., how many coins they are staking in Algorand, or commitments to disk space in Filecoin). While the latter are still permissionless in the sense that anyone can participate, they impose stricter requirements on participants. 1.1 Our Contributions In this paper, we completely characterize the design space of Nakamoto-like protocols operating in the fully-permissionless setting using the physical resources disk space, sequential computation, and parallelizable computation that are secure against private double-spending attacks. We observe that Nakamoto-like protocols only differ in what resources their blocks record, and—especially if multiple resources are used—how they decide which of two blocks required more resources to create. We model these differences using an abstraction called the weight function \Gamma\colon\mathbb{R}^{3}\to\mathbb{R} . It takes as input the three resources possibly recorded by a block, i.e., disk space S , sequential computation V 1 1 1 Think V as in velocity of the sequential computation or V as in verifiable delay function (VDF), the cryptographic primitive usually used to capture the number of sequential computation steps. and parallelizable computation/work W , and outputs the weight \Gamma(S,V,W) of a block. In the context of weight functions, the heaviest-chain rule now picks the chain with the highest weight where a chain’s weight is defined as the sum of the weight of all its blocks. To get an intuition for the weight function abstraction, let us provide some examples. The weight function \Gamma_{\text{Bitcoin}}(S,V,W)=W describes Bitcoin (or any other similar PoW-based Nakamoto-like chain, e.g., Litecoin 2 2 2 https://litecoin.org/ ). More interesting is Chia [ CP19 ] , a Nakamoto-like chain combining disk space and sequential computation following \Gamma_{\text{Chia}}(S,V,W)=S\cdot V . Our main result, informally stated in Theorem 1.1 below, fully characterizes which weight functions result in a Nakamoto-like blockchain that is secure against private double-spending attacks [ Nak09 , DKT+20 ] in the fully-permissionless setting [ LPR24 ] . In this work we address double spending, but not economic attacks such

Read the complete text