Spartan v3: Secure Proof-of-Capacity (PoC) Consensus on Substrate

We are pleased to announce that Subspace Labs has delivered the third and final milestone for our Web 3 Foundation Open Grant to bring Spartan Proof-of-Capacity (PoC) consensus to Substrate! For more information on the purpose of this grant and what PoC consensus is, please refer to the first article in this series.

In the previous milestone, we demonstrated the ability to run multiple farmers with different-sized plots on a local test network. This version of the protocol was secure in the so-called happy path, i.e., assuming that all nodes follow the proscribed protocol. For our final milestone, we have concluded a rigorous security analysis of our protocol, identified several attack vectors, and implemented the necessary countermeasures within the code for each. The result is a Nakamoto-style (longest-chain) consensus protocol that is secure against all known attacks, suggesting that it would be impossible for one to derive an advantage from an alternate implementation.

What follows is a summary of our results. For a more detailed analysis, please refer to the Milestone 3 Security Analysis Document. We are very grateful to Srivatsan Sridhar, our summer research intern on loan from Stanford University, for the hard work and deep thought he has put into this analysis over the last few months.

Lazy Farming (Sybil Resistance)

A disk-based plot consists of many millions of 4096-byte encodings, each of which is unique for a given piece of the blockchain history and farmer id (hash of their public key). The consensus audit cannot distinguish between a plot consisting of either: a) many different pieces created with one node id or b) one piece created from many different node ids (i.e., a sybil attack). Ideally, farmers would choose the former since this encourages the replicated and distributed storage of the entire blockchain history. However, a lazy farmer could save bandwidth by downloading only a single piece and encoding it under many different node ids. This strategy also allows for more efficient implementations of the compression attack, described in more detail below. Note that lazy farming is more of a concern for Subspace than Spartan, as there can only be a single genesis piece in Spartan.

Luckily we may discourage lazy farming with only a small modification to the consensus audit. Currently, we employ a global challenge, meaning all farmers on the network query their plot, or more specifically, their Binary Search Tree (BST), using the same random challenge. If, instead, we salt the challenge with the farmer id, such that each sybil identity requires a different challenge, lazy farmers will now be required to maintain a different BST and conduct a different lookup for each identity they employ. This means that a sybil farmer will see an increased computational overhead of participating in consensus linear in the degree of sybil identities it employs — for no advantage aside from some initial bandwidth.

Simulation (Nothing-at-Stake)

Blockchains which employ a Proof-of-Work (PoW) consensus puzzle, such as Bitcoin, have a property known as conservation of work, which forces any consensus node to dedicate its resources towards a single puzzle challenge. Concretely, in the event of an honest network fork, a miner cannot dedicate all of its hash power to both branches. It must either choose a single branch or somehow divide its power between them both.

Efficient consensus puzzles, such a Proof-of-Stake (PoS) and Proof-of-Capacity (PoC) do not retain this property. Instead, in the event of a fork, a farmer can trivially solve on both branches and gain an advantage in doing so. It is now well-known that this advantage is bounded by factor e, meaning that an attacker who employs this strategy could double-spend with 1/(1+e) or ~27% of the total network storage (instead of 51%). If we make simulation the default strategy, as some PoS and PoC chains have suggested, we now open the network up to a devastating balance attack, which requires even less storage.

To handle this problem, we employ the equally well-known solution, referred to as challenge recycling or c-correlation, as exemplified by Ouroborous Praos and implemented in BABE (which serves as the basis for our implementation). Instead of using the challenge for a single block (or timeslot in our case), we derive the challenge for many timeslots (in one epoch) using the same (shared) epoch randomness. To derive the randomness for the next epoch, we concatenate and hash the outputs of several of the Proofs-of-Replication (PoRs) for the previous epoch, creating a randomness beacon.

This technique effectively smooths out any advantage that could be gained from simulation. The higher the number of expected blocks in an epoch, the less advantage an attacker can gain from simulation. This comes at the cost of increased predictability or the ability for farmers to know if they will be elected for some future timeslot, which could be used as the basis for a bribery attack. We have chosen a parameter of 256 expected blocks, which translates to around 26 minutes of predictability while providing security up to ~47% storage adversary.

Equivocation (Block Spamming)

When a farmer is elected to produce the next block, they could confuse the network by generating many different valid blocks (perhaps consisting of different transaction sets), all sharing the same proof. This is possible because the canonical proofs and malleable transaction content are effectively segregated into two chains to prevent challenge grinding attacks. Specifically, equivocation means two or more blocks have been created with the same public key at the same timeslot.

To deter this attack, we note that it is detectable, provable, and punishable. In the PoS setting and the default BABE implementation, any node that detects this behavior can submit an equivocation report, resulting in the offending node losing a portion of their staked deposit. Since our PoC protocol is permissionless, meaning there is no notion of staking or registration to farm, we must find an alternative punishment.

Recall that we employ a local challenge to deter sybil farming, which means that each farmer should have one (or a few) unique node ids for its plot. If we have a provable equivocation report for a farmer, we can add the related farmer id to a block list against which all new proofs are screened, effectively burning their plot.

Space-Time Trade-offs (Mining PoRs)

All PoC consensus protocols are susceptible to space-time trade-off attacks, whereby an attacker tries to leverage greater computational power to appear to have more storage than an honest player. In the case of Spartan, an attacker could attempt to mine PoRs on-demand instead of following the proscribed farming strategy.

To compete on an equal footing with an honest farmer with a one TB plot of roughly 250,000,000 encodings, a miner would need to create the same number of encodings every six seconds (the block interval) on-demand. If an honest node can plot one TB in roughly 24 hours using a commodity quad-core CPU, the attacker would need roughly 14,000 times more computational power continuously. If we instead assume the honest network has one EB of storage, the attacker requires 14,000,000,000 times the computational resources of a single honest farmer.

While such an attack is certainly possible, we note that it is economically irrational. If the miner is trying to break the fairness of one-disk-one-vote, they will do so at a much lower ROI than a farmer. This is because the farmer has a one-time plotting cost. In contrast, the miner is essentially plotting continuously, at a much, much higher rate, which incurs a constant overhead cost in electricity. If the miner is instead trying to accumulate more consensus power than the honest network, perhaps to double-spend or censor transactions, a space-time trade-off attack would be much more expensive than just acquiring 51% of the storage.

Compression attack

It turns out there is a more efficient form of the space-time trade-off attack on Spartan (and Subspace), which exploits a weakness in the efficient audit based on look-up tables, or the BST. Recall that a farmer does not query its plot of encodings during the audit but only the BST of commitments to those encodings. This means that a farmer could delete its plot, still participate in the consensus audit, and quickly re-derive the encoding from some advice (i.e., the nonce or piece index) stored alongside the commitment in the BST. In Spartan, re-deriving the encoding is trivial since there is only one genesis piece. Still, even in Subspace, the attacker only requires one copy of the un-encoded blockchain history, an overhead cost that may be amortized over many plots or shared between many nodes.

A farmer who exploits this loophole can effectively compress their plot by a factor of 256 and appear to have much more storage than an honest farmer. While this still requires 256x more computation to create the plots, it breaks the fairness of one-disk-one-vote, as a compression attacker only needs .2% of the total (honest) space pledged to the network in order to double-spend. Even worse, in the case of Subspace, we lose any guarantees of replicated storage of the blockchain history, as it would be much more efficient for many compression farmers to share a single copy of the unencoded history.

To deal with this seemingly devastating attack, we begin by noting that the honest farmer has both the plot of encodings and the BST of commitments, while the attacker has only the BST of commitments. If we can somehow incorporate the plot back into consensus, perhaps at some interval, we could require the attacker to do significantly more work than the honest farmer to maintain the compression strategy.

Specifically, we modify the commitment scheme from one based on a simple hash of the encoding to one based on a hash-based message authentication code (HMAC) of the encoding and a random nonce. We then require that farmers periodically re-commit to their plots with a new random nonce derived from the blockchain itself. For example, once every week, a farmer would need to read its encodings from disk and compute a new BST based on the new nonce. This would incur a negligible overhead cost for the honest farmer and could also be amortized over the course of the interval. The compression attacker (who has deliberately discarded their plots) cannot re-commit without first re-plotting and must now continuously plot (or mine) to maintain their advantage.

Selection of the proper re-commitment interval (referred to as an eon) is critical to the success of this countermeasure, which we refer to as salted trees. This effectively boils down to the specifics of the encoding algorithm, estimating lower bounds on encoding throughput based on hardware assumptions and estimates of the continuous electricity costs of mining vs. the amortized cost of storage hardware. If the eon is too large, the compression attack may be an economically rational strategy. At the same time, if it is too small, we burden the honest network with additional overhead, which will impact usability and raise the barrier to adoption for farming.

Research into this area is ongoing, though an initial interval need not be decided until network launch. This interval may also be adjusted, either through a soft fork or some dynamic on-chain adjustment (similar to a work-difficulty reset) to maintain a constant cost of the compression attack, based on the amount of space pledged to the network.

History Rewriting (Long-Range Attacks)

It is worth briefly mentioning the long-range attack, though this will be covered in much more detail in a future post. In this attack, a farmer creates a deep fork in the chain and creates an alternate history that is longer, or more specifically heavier, than the honest chain. This fork may then be used to trick new nodes joining the network into following and contributing storage power towards the alternate history. In PoC blockchains, this attack may be carried out with only the average amount of space since the fork, which could be much smaller than 51% of the storage now.

If Subspace were to be an independent blockchain, this challenge would need to be resolved within the protocol itself. However, since Subspace aims to launch as a parachain on the Polkadot Network, this problem is resolved by the shared security afforded by the Polkadot Relay Chain. Since each parachain commits its block header to the relay chain, which is recorded in each corresponding relay chain block, a successful long-range attack would need to be carried out on both the Subspace Parachain and the Polkadot Relay Chain simultaneously. Since the cost of reverting the relay chain is currently several billion dollars, this is assumed to be unlikely.

Guaranteeing Safety & Liveness

Given the following assumptions:

1. Spartan (and Subspace) may be treated as a secure extension of a Nakamoto-style or longest-chain consensus protocol, originating with Bitcoin under PoW, extended to Ouroboros Praos under PoS, as (largely) implemented in BABE and refactored for Spartan PoC.
2. The evaluation of the plot (or, more specifically, the BST) can be modeled as a random oracle, similar to evaluating a hash function in PoW or evaluating a verifiable random function (VRF) in PoS.
3. The countermeasures described above provide security against the sybil, simulation, equivocation, space-time trade-off, compression, and long-range attacks.

Then it follows that no single economically rational adversary with less than 47% of total network storage may attack the safety (i.e., double-spend) or liveness (i.e., censor transactions) of the protocol.

Next Steps for Subspace

Now that we have a secure PoC implementation in Substrate, the critical next step for our project will be to implement the full protocol as described in our technical white paper:

1. Upgrading the base consensus layer from a useless proof-of-space (Spartan) to a useful proof-of-storage (Subspace).
2. Extending the farmer to operate as a node in the Distributed Storage Network (DSN), ensuring the blockchain history is actually available.
3. Implementing a decoupling of consensus and execution within the client to alleviate farmers of the burden of maintaining the state and computing the state transitions for each new block.

We have also launched a private test for Spartan, which we will soon be opening up to a larger audience along with access to our internal Discord server.

Many thanks for all of the great feedback and support we have received over the last three months from the teams at Parity and the Web3 foundation regarding the design and implementation for Spartan and the many nuances of Substrate!