Using c-correlation with proof of space

Research
1

This post initiates the research on using ‘‘c-correlation randomness’’ with proof-of-space protocols. The analysis below:

  1. Highlights the differences between a c-correlation proof-of-stake protocol and a c-correlation proof-of-space protocol.
  2. Demonstrates that the security analysis of the proof-of-space component cannot ignore the broader context of how it interplays with the blockchain design.

Background

  • Common blockchains use each and every block as a source of randomness that is used as a ‘‘challenge’’ for creating the next block.
  • Nothing-at-stake is a type of attack applicable when the process of creating a valid block is fairly easy. It applies to both proof-of-stake/space protocols, as once a participant is eligible to create a block, they can use this eligibility to create many blocks at the same height (all with them same ‘‘winning ticket’’). Then has more than one ‘‘winning ticket’’, they can (privately) simulate different chains, revealing the one that gives some kind of advantage in creating subsequent blocks.
  • It is known that, without other mitigations, the network remains secure against such an attack if the attacker has less than 27% of the total allocated resource (stake/space).
  • In the context of proof of stake, this paper gives a formal analysis on c-correlation randomness: the challenges for block creation are updated every c blocks. When c=1 we get the standard every block has a different challenge.
  • The paper also proposes a notion called s-truncation as the fork choice rule. It addresses grinding on coin ownership, and applicable since coins (and their owners) are internal to the system.

Stake vs. Space
The first observation we make is that correlated randomness seems to fit proof-of-stake systems better than system based upon proof of space. The reason is that stake is internal to the system, thus fixing the randomness also determines, among the capped stake, who will be the block winners. In other words, the set of ‘‘lottery tickets’’ is fixed per challenge.
Space, on the other hand, is external to the system. As such, it is ‘uncapped’, as more space can join the system at any given time, generating more lottery tickets. While c-correlation would prevent farmers from grinding on their block content, it won’t prevent farmers from ‘‘grinding on their space’’. This means that even though the challenge is fixed for c blocks, in theory farmers still have the opportunity for manipulation in order to win the next block slots. In other words, the (fixed) randomness does not necessarily determines who will be the block winner.

We note that an exception is the SpaceMesh proof-of-space protocol, where in order to participate in the consensus protocol, farmers need to ‘‘register’’ their space.

Proof of Space Security Analysis
Continuing the line above, since proof-of-space-based systems require a plotting phase, where some data is written to the farmer’s drive, farmers may attempt to create (some of) this data on demand, instead of actually storing it on disk. This may lead to a situation where a farmer wins block slots more frequently than the proportion of space they contribute to the system’s security.

A standard approach in addressing such a situation is to design the system such that this behaviour is irrational. That is, to show that the cost of creating on demand plots until a winning ticket is found is higher than the cost of (plotting once and) actually storing the data until a winning ticket is obtained. Since winning tickets are chosen uniformly at random among the lottery tickets, it is the same as analysing the cost of obtaining a single lottery ticket per challenge in both strategies.

With a fixed challenge for c consecutive blocks, each on-demand plotting gives c lottery tickets, thus making this strategy more appealing, as the plotting cost is amortized among c tickets.
On the other hand, with the honest strategy of storing data there is no real difference – with challenge either every block or every c blocks, the farmer stores the data for the duration of c blocks and obtains c lottery tickets, so the cost per ticket remains the same.

Specifically for the Subspace protocol, since replotting is part of the protocol, using c-correlation may lead to a slight deviation from the protocol: c blocks before the replotting event, farmers will already know if their tickets win or lose, and thus can delete their plot before the intended time.

4 Likes
2

This is an interesting observation.
At the same time I don’t think it is a significant incentive as replotting interval should be much larger than c.

The only time when farmer would want to do this is when your plot is about to be expired. If we make it such that we don’t know if plot expired til the very last moment, then there will be no reason to delete the plot early.

At the same time we’d probably want to let farmer know about this in advance, so that they have new sector ready before the old one expires so that they don’t waste space with already expired sectors (though replotting of one sector shouldn’t take a lot of time, thus shouldn’t be a big loss).