Fast Finality: Proof of Space-Time [Deprecated] – NEAR Protocol

In this paper we introduce a fork choice rule and a Sybil resistance mechanism that are currently proposed to be used in NEAR Protocol {{This is an ongoing research. NEAR will initially launch without Proof-of-Space-Time.}}. We compare it to three approaches to Sybil resistance and fork choice rules: Proof-of-Work with the heaviest chain, as initially introduced in the Bitcoin paper [1], (Delegated) Proof-of-Stake with the longest chain, for example see Ouroboros [2], and (Delegated) Proof-of-Stake with BFT consensus, for example see ByzCoin [3].We begin by surveying the existing fork choice rules and Sybil resistance mechanisms on several dimensions.

1.1 Desired Properties

1.1.1 Resilience to Long-Range Attacks

Proof-of-Work with the heaviest chain fork choice rule has a very desirable property that no matter what malicious actors do, unless they control more than 50% of the hash power, they cannot revert a block that was finalized sufficiently long ago.Proof-of-Stake systems do not have the same property. In particular, after the block producers that were creating blocks at some point in the past get their staked tokens back, the keys that they used to create blocks no longer have value for them. An adversary can attempt to buy such keys for a price significantly lower than the amount of tokens that was staked when the key was used to produce blocks. Since, unlike in Proof-of-Work, Proof-of-Stake has no mechanism to force a delay between produced blocks, the adversary can then in minutes create a chain that is longer than the canonical chain, and have such chain chosen by the fork choice rule.There are two primary ways to get around this problem:Weak subjectivity. Require that all the nodes in the network periodically check what is the latest produced block, and disallow reorgs that go too far into the past. If the nodes check the chain more frequently than the time it takes to unstake tokens, they will never choose a longer chain produced by an adversary who acquired keys for which the tokens were unstaked.The weak side of the weak subjectivity approach is that while the existing nodes won’t be fooled by the attacker, all the new nodes that spin up for the first time will have no information to tell which chain was created first, and will choose the longer chain produced by an attacker. To avoid it, they need to somehow learn off-chain about the canonical chain, effectively forcing them to identify someone whom they trust in the network.Forward-secure keys. Another approach is to make the block producers destroy the keys that they used to produce blocks immediately or shortly after the blocks were produced. This can be done by either creating a new key pair every time the participant creates blocks, or by using a construction called Forward-secure keys, which allows a secret key to change while the public key remains constant.This approach relies on nodes being honest and following protocol strictly. There’s no incentive for them to destroy their keys, since they know in the future someone might attempt to buy them, thus the key has some non-zero value. While it is unlikely that a large percentage of block producers at a certain moment all decide to alter their binaries and remove the logic that wipes the keys, a protocol that relies on the majority of participants being honest has different security guarantees than a protocol that relies on the majority of participants being reasonable. Proof-of-work works for as long as more than half of the participants are reasonable and do not cooperate, and it is desirable to have the fork choice rule and a Sybil resistance mechanism that have the same property.We propose to use Proof-of-Space-Time (see e.g. [4]) that, like Proof-ofWork, makes use of some scarce resource (in this case space) and requires the adversary to control more than 50% of that resource in the network to carry out a reorg, which provides the same security guarantees against long range attacks as Proof-of-Work.

1.1.2 Environment Friendliness

Bitcoin and Ethereum miners spend multiple terrawatt hours of electricity per year to carry out Proof-of-Work computation, severely damaging the environment.While Proof-of-Stake improves significantly on it and has practically no imprint on the environment, it has other disadvantages described in the surrounding subsubsections, since participants do not use any scarce resource to secure the chain.Proof-of-Space-Time is a significantly more environment-friendly version of the Sybil resistance mechanism than Proof-of-Work that does take advantage of a scarce resource, namely space, but doesn’t consume much electricity, since hard drives do not need electricity to store information.

1.1.3 Time to Finality

Proof-of-Work systems, such as Bitcoin or Ethereum, and non-BFT Proof-ofStake systems require one to wait for a substantial time before they become sufficiently certain that a block that includes a transaction they care about is final. In Bitcoin it is common to wait for six blocks, which takes on the order of one hour.Proof-of-Stake systems that use a BFT consensus to finalize each block, on the other hand, have very fast finality. Once a block is produced and is agreed upon with the BFT consensus, unless a large percentage of the stake is slashed, the block is irreversible.

1.1.4 Cost to Revert Finalized Block

Proof-of-Stake systems that use BFT consensus have significantly higher cost of reverting a recently finalized block than Proof-of-Work or non-BFT Proof-of-Stake systems. Specifically, within a particular epoch (where epoch is loosely defined as a time span during which the validator set was constant) for a block to be reverted one third of the stake needs to be slashed, which often means that something on the order of 10%-20% of all the circulating tokens need to get burnt. In the Proof-of-Work system just the recent rewards need to be paid for, which is generally significantly smaller amount of value.However, as discussed above, reverting a block that was finalized long ago could cost very little in a Proof-of-Stake system, while in Proof-of-Work system the cost of the reorg increases over time.In the construction we propose, creating a short reorg once a block is finalized would cost at least one third of the total stake slashed, similar to Proof-of-Stake with a BFT consensus. On the other hand, creating a long reorg will cost the accumulated rewards for all the space-time proofs. The cost of the latter, while it is less than the cost of making a short range reorg, increases over time after the drop that occurs when finalized block tokens are unstaked.

1.1.5 Availability

Proof-of-Work and Proof-of-Stake systems that use some sort of heaviest chain fork choice rule remain available even if a large percentage of block producers simultaneously disappear. Achieving the same property in constructions that use BFT consensus is significantly harder.BFT consensus protocols and BFT finality gadgets in the context of blockchains are primarily designed in the context of a single permissioned set of n validators that doesn’t change over time and has at least

[ lfloor 2n/3 + 1 rfloor ]

validators online at any point. We discuss in detail the implications of validator set changes and possibility of more than

[ lceil n/3 − 1 rceil ]

validators simultaneously going offline for safety and liveness of blockchain protocols in section 1.2.1.

1.1.6 Incentives for Pooling

Existing Proof-of-Work approaches provide high incentive for miners to pool. Since each block produced is a lottery, and the number of blocks produced per unit of time is relatively low, for most miners the expected time before they win the lottery at least once is huge. The miners would gladly trade a small percentage of the expected value for reduced variance, and thus they choose to join a pool instead of mining themselves.Miners that mine via pools often get the hash to mine on top from the pool instead of watching the network themselves and choosing the heaviest chain known to them. Thus, a set of pools that collectively control more than half of the hash power can perform short time reorgs by sending a hash that doesn’t correspond to the heaviest chain to their workers.Currently for both Ethereum and Bitcoin the number of pools that need to collude to perform such an attack doesn’t exceed five, thus posing major centralization concerns.Proof-of-Space-Time differs from Proof-of-Work in that designing it as a lottery is very hard. The particular construction that we present here doesn’t have a lottery, and makes pooling of Proof-of-Space-Time practically impossible.

1.1.7 Permissionlessness

While a contentious topic, it can be argued that Proof-of-Stake systems are not permissionless in the same sense as Proof-of-Work systems, since for someone to become a block producer, they generally need to submit a staking transaction, and the transaction needs to be settled, thus effectively requiring the block producer to get permission from the existing blockchain users to start producing blocks.In the context of NEAR Protocol the transactions are not included in the blocks, and are instead grouped into so-called chunks that blocks consist of, see the details in [5]. Producing invalid chunks must be a slashable behavior, and thus we depend on Proof-of-Stake for the chunk production, and cannot have permissionlessness in the Proof-of-Work sense. As such, having permissionlessness was not a design goal for the construction presented here.The construction can be changed in such a way that the block production is done by the participants identified by Proof-of-Space-Time instead of the participants identified by Proof-of-Stake, thus at least partially introducing permissionlessness in the same sense as in Proof-of-Work, but this is outside of the scope of this document.

We note here that the permissionlessness of Proof-of-Work is also somewhat exaggerated. Consider figure 1. A malicious miner or a pool that controls a large percentage of the hash power, say 20%, can choose to censor small block producers that have, say, 1% of the hash power. By censoring their blocks the malicious miner loses on the order of 1% reward, while the target miner loses on the order of at least 4% of the reward (and likely more). Assuming that the margin of mining on top of the cost of electricity is less than 4% the target miner will be losing money, and will eventually be forced to stop mining, effectively increasing the reward for all the remaining miners, including the attacker, by 1% in the future. Thus, big miners can and have an incentive to censor small players, and thus arguably Proof-of-Work systems are not truly permissionless either.

1.2 BFT Finality, Validator Rotation and Availability

When desigining Proof-of-Stake blockchains that rely on a BFT consensus it is generally desirable that if a block is finalized by such a consensus, it cannot get reverted unless a very large percentage of the stake is slashed.Many BFT protocols provide this guarantee for as long as the validator set is constant and at least

[ lfloor 2n/3+ 1 rfloor ]

of validators are online at any given moment.

1.2.1 BFT Finality and Validator Rotation

The problem with validator set rotation in general is that, if two consecutive validator sets do not have a large overlap, the latter validator set can pretend, without any risk of being slashed, that they didn’t see a block finalized by the previous validator set. This problem has at least two different solutions. One solution is to prevent large validator set changes by only allowing up to some percent of validators to change between two consecutive validator sets. Another approach is to force both validator sets to finalize a block during a transition between the two sets.

1.2.2 BFT Finality and Availability

A bigger and more fundamental problem is how to handle situations when for some reason more than

[ lceil n/3−1 rceil ]

validators simultaneously went offline. For example, in a blockchain in which there are multiple clients this can occur if one of the major clients hits a bug and a large percentage of validators simultaneously disconnect.We survey here three approaches used by Cosmos, Polkadot and Ethereum Serenity. Cosmos uses BFT consensus as the primary fork choice rule: the canonical chain is the longest chain that only consists of finalized blocks. Polkadot and Ethereum Serenity use a non-BFT fork choice rule (respectively BABE and LMD GHOST), as well as a BFT finality gadget (respectively GRANDPA and Casper FFG).

  • Cosmos approach. Cosmos heavily favors consistency, and thus if more than[ lceil n/3−1 rceil ]validators simultaneously go offline, the chain stalls. If the validators have crashed unrecoverably, the only way to resume the chain is via a hard fork.
  • Polkadot approach. In Polkadot the underlying non-BFT consensus BABE will continue operating even if a very large percentage of validators went offline, but the BFT finality gadget GRANDPA stalls until the validators of the last set that needed to finalize a block get back online. Similarly, if the validators have crashed unrecoverably, currently the finality gadget can only be resumed via a hard fork, but the chain will continue producing blocks via BABE. Since in Polkadot many components rely on blocks being finalized, this approach heavily favors consistency.
  • Ethereum Serenity approach. Serenity heavily favors availability. In Serenity the underlying non-BFT consensus LMG GHOST will continue producing blocks even if a very large percentage of validators goes offline. Their BFT finality gadget Casper FFG will stall if more than dn/3 − 1e validators are offline, however the offline validators will slowly lose their stake, and at some point will drop out, bringing the system into a state in which at least b2n/3 + 1c validators are online, at which point Casper FFG will resume finalizing blocks. Note that since the two validator sets can greatly differ in this case, a block that was previously finalized can now become orphaned with nobody being slashed, as shown on figure 2.

Generally we argue that favoring availability over consistency is preferred, since clients that want to have consistency can always choose to locally treat an available chain as consistent. For example, in the case of Ethereum Serenity, a client can choose not to respect any blocks that are produced by a committee that differs greatly from the last committee which finalized a block (and thus locally stall the chain). In such an event if a sufficient number of clients are concerned with the committees being different, and have a reason to believe that a finalized block was reverted in the process, they can choose to reach a social consensus and still perform a hard fork.In this document we present an approach that favors consistency, and leave exploring exact changes necessary to make it favor availability for future work, see section 4.1.

Related Articles

Back to top button

Adblock Detected

Please consider supporting us by disabling your ad blocker