Proofs of Space

Bram Cohen, the creator of BitTorrent, gave an EE380 talk entitled Stopping grinding attacks in proofs of space. Two aspects were really interesting:

• A detailed critique of both the Proof of Work system used by most cryptocurrencies and blockchains, and schemes such as Proof of Stake that have been proposed to replace it.
• An alternate scheme for securing blockchains based on combining Proof of Space with Verifiable Delay Functions.

But there was another aspect that concerned me. Follow me below the fold for details.

I'll first outline Cohen's critiques of Proof of Work, Proof of Stake, and Proofs of Other Things, then summarize his proposed scheme combining Proof of Space with Verifiable Delay Functions (PoSp/VDF), and conclude by addressing the aspects of his talk that concerned me. I have tried to refer to quotes, concepts and slides by the time at which they appear in the video thus [MM:SS] but these times are approximate. I apologize if the quotes are mis-transcribed from the audio.

Proof of Work

The goal of PoSp/VDF is to reduce greatly the cost of verifying blocks in a blockchain. But "zero cost brings grinding attacks", in which an attacker tries lots of possibilities to find the best one. "Bitcoin fixes this by making grinding the expected behavior rather than an attack" using Proof of Work, in which peers try to invert a hash function. The computational cost of the vast number of hashes needed is the cause of Bitcoin's massive energy consumption.

Cost of rewriting attack

Cohen points out that Proof of Work is "Also susceptible to rewriting attacks". Bitcoin core describes rewriting attacks thus:

powerful miners have the ability to rewrite the block chain and replace their own transactions, allowing them to take back previous payments. The cost of this attack depends on the percentage of total network hash rate the attacking miner controls. The more centralized mining becomes, the less expensive the attack for a powerful miner.

They provide a real example:

In September 2013, someone used centralized mining pool GHash.io to steal an estimated 1,000 bitcoins (worth $124,000 USD) from the gambling site BetCoin. The attacker would spend bitcoins to make a bet. If he won, he would confirm the transaction. If he lost, he would create a transaction returning the bitcoins to himself and confirm that, invalidating the transaction that lost the bet. By doing so, he gained bitcoins from his winning bets without losing bitcoins on his losing bets. Although this attack was performed on unconfirmed transactions, the attacker had enough hash rate (about 30%) to have profited from attacking transactions with one, two, or even more confirmations.

More details of this attack are here.

Proof of Stake

Proof of Stake is an alternative consensus system for cryptocurrencies in which holders put some or all of their holdings "at stake", a process known as "bonding". Blocks of transactions are validated by a quorum of the currency "at stake". Misbehavior by holders is deterred by "slashing", miscreants lose their stake. It appears attractive, in that it can vastly reduce the energy demand of Proof of Work systems such as Bitcoin's. It is especially attractive to core team members and early adopters of a cryptocurrency, since they will be large holders and will thus be able to control the currency.

Cohen's critique of Proof of Stake starts around [8:30] and covers six main points:

• Its threat model is weaker than Proof of Work.
• Just as Proof of Work is in practice centralized around large mining pools, Proof of Stake is centralized around large currency holdings (which were probably acquired much more cheaply than large mining installations).
• The choice of a quorum size is problematic. "Too small and it's attackable. Too large and nothing happens." And "Unfortunately, those values are likely to be on the wrong side of each other in practice."
• Incentivizing peers to put their holdings at stake creates a class of attacks in which peers "exaggerate one's own bonding and blocking it from others."
• Slashing introduces a class of attacks in which peers cause others to be fraudently slashed.
• The incentives need to be strong enough to overcome the risks of slashing, and of keeping their signing keys accessible and thus at risk of compromise.
• "Defending against those attacks can lead to situations where the system gets wedged because a split happened and nobody wants to take one for the team"

Proofs of Other Things

Cohen's critique of other types of proof starts around [34:30]. The main points are:

• Peers need to be able to audit proofs locally, which isn't true of proofs of participation, importance or more nodes.
• The system needs to adjust the "difficulty" of proofs, which requires an exponential distribution of "difficulty", which these other types typically lack.

In particular, at [37:50] he critiques "proof of storage of user-supplied data" as used by services such as Maidsafe. An attacker doesn't have to store the amount of data they requested: "because you can just take a key and use it to ... generate completely fake data which everyone else has to store the data to claim their rewards later and you yourself don't have to do that, you just store the seed and there's no way to detect that because they are all supposed to be encrypted files that just look like garbage anyway".

Proof of Space and Verifiable Delay Functions

Cohen's explanation of PoSp/VDF starts at [13:32]. His summary is:

• Bring in verifiable delay functions (VDFs) and alternate between proofs of space and time
• Split between the 'trunk' of the blockchain which challenges come from and the 'foliage' which contains transactions
• Attach public keys to proofs of space so there's no choice after one wins
• Use canonical proofs of space, verifiable delay functions, and signatures
• All we have to do is invent a new proof of space algorithm, verifiable delay algorithm, and method of combining them

My understanding of PoSp/VDF may be deficient. I have read Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space, which explains the PoSp technique, but the mathematics exceed my capabilities. The VDF technique doesn't appear to have been published yet.

As I understand it, the proof of space technique in essence works by having the prover fill storage space with an array of pseudo-random points in [0,1] via a time-consuming process. The verifier can then pose to the prover a question that can be answered either by a single storage access (fast) or by repeating the process of filling the storage (slow). By observing the time the prover takes the verifier can distinguish these two cases, and thus be assured that the prover has stored the (otherwise useless) data.

As I understand it, verifiable delay functions work by forcing the prover to perform a specified number of iterations to generate a value that the verifier can quickly show is valid.

Cohen describes how these two techniques work together in a blockchain at about [22:38]:

• To use in a blockchain, each block is a proof of space followed by a proof of time which finalizes it.
• To find a proof of space, take the hash of the last proof of time, put it on a point in [0,1], find the closest proof of space you can to that.
• To find the number of iterations of the proof of time, multiply the difference between those two positions by the current work difficulty factor and round up to the next integer.
• The result of this is that the best proof of space will finish first, with the distribution of arrival times of finalizations the same as happens in a proof of work system if resources are fixed over time.
• The only discretion left on the part of farmers is whether to withhold their winning proofs of space.

In other words, the winning verification of a block will be the one from the peer whose plot contains the closest point, because that distance controls how long it will take for the peer to return its verification via the verifiable delay function. The more storage a peer devotes to its plot, and thus the shorter the average distance between points, the more likely it is to be the winner because its proof of space will suffer the shortest delay.

Just as with Bitcoin's Proof of Work, farming pools would arise in PoSp/VDF to smooth out income. The pool would divide up [0,1] among its members.

Concerns

One aspect of the talk that concerned me was that Cohen didn't seem well-informed about the landscape of storage. Here are a few quotes:

• 
  

  120

  $38.7B

  $0.320

  693

  $26.8B

  $0.039

  40

  $0.65B

  $0.016

  [50:00] "people spend like $150B/year on storage media". Robert Fontana and Gary Decad of IBM report that in 2016 the total revenue of storage media vendors (excluding optical) was $66B. But Cohen is only interested in hard disk, which they report had 2016 revenue of $26.8B.
• Cohen's first slide claims "Storage is an over $100 billion a year industry with about 50% utilization". The vast majority of hard disks are now purchased by cloud companies. The idea that, for example, Amazon Web Services has purchased twice as much hard disk as it needs is ludicrous.
• [43:50] "You have this thing where mass storage medium you can set a bit and leave it there until the end of time and its not costing you any more power. DRAM is costing you power when its just sitting there doing nothing". A state-of-the-art disk drive, such as Seagate's 12TB BarraCuda Pro, consumes consumes about 1W spun-down in standby mode, about 5W spun-up idle and about 9W doing random 4K reads. Clearly, PoSp/VDF takes energy, just a lot less energy than Proof of Work. Cohen might argue that, since PoSp/VDF expects to use the empty 50% of drives that store actual user data, the energy cost is zero. But these drives are not just part empty, they are in standby much of the time too. Using them for Proof of Space means they are active somewhat more of the time, because they have to wake up from standby at least once every block time. They are thus consuming energy that the owner has to pay for. Also, the drives are typically warranted not "until the end of time" but only for 5 years.
• There is another economic impact. The consumer drives I believe he is thinking about are intended for consumer workloads, and are thus designed to be idle much of the time. They are specified with a "rated workload". The 12TB BarraCuda Pro specifies:
  

  Maximum rate of 300TB/year. Workloads exceeding the annualized rate may degrade the drive MTBF and impact product reliability. The Annualized Workload Rate is in units of TB per year, or TB per 8760 power on hours.

  Thus the drive is specified to average no more than about 35GB/hr over its lifetime. The drive has a maximum sustained transfer rate of 0.238GB/s or 857GB/hr. So the drive is designed for a duty cycle of about 4%. The Proof of Space workload would increase the drives' duty cycle somewhat, since it requires a few disk accesses per block time. It would thus wear the drives out somewhat faster, imposing further costs on the storage owner.

• 

  Write endurance vs. cell size

  [51:30] "my understanding is that the overwriting limits on flash has gotten better over time". As flash has added more bits per cell, the write endurance has decreased, as shown in the table. Enterprise flash obscures this unfortunate fact by over-provisioning cells, spreading the writes across more cells, but this is costly.

Another aspect of the talk that concerned me was that, as I understand it, Cohen's vision is of a PoSp/VDF network comprising large numbers of desktop PCs, continuously connected and powered up, each with one, or at most a few, half-empty hard drives. The drives would have been purchased at retail a few years ago. The desktop PC is a declining market, and the devices such as laptops, smartphones, tablets and small form-factor PCs that are displacing it use flash storage, are intermittently connected, and asleep whenever possible. Thus Proof of Space addresses a declining market. The edge of the Internet has changed since Cohen invented BitTorrent.

Source

These changes have affected the market for hard disk. Flash is increasingly destroying the markets for enterprise drives, and for 2.5" laptop drives. One the other hand, "The Cloud" has increased demand for "nearline" and consumer 3.5" drives. They are purchased in bulk at prices far lower than retail by customers such as Amazon, who cannot afford to have 50% of their investment in storage media sitting empty. Nevertheless, the small proportion of their total inventory that is empty on average gives them much more empty storage than any retail customer.

Cohen's first slide claims "As long as rewards are below depreciation value it will be unprofitable to buy storage just for farming" Suppose a network matching Cohen's vision existed, how would economies of scale affect it? The cloud companies' empty drives are brand new, purchased in bulk direct from the manufacturer at a huge discount. That is three reasons why they would have much lower cost per byte than the drives in the network nodes. If the cloud companies chose to burn-in their new drives by using them for Proof of Space they would easily dominate the network at almost zero cost.

Once again Economies of Scale in Peer-to-Peer Networks was prophetic.

PS - I have not had time to analyze in detail the FileCoin proposal, which has some similarities to PoSp/VDF. It has many significant differences, in that it stores user data rather than verifies transactions, uses a combined Proof of SpaceTime rather than separate proofs, and employs bonding and slashing. It also appears to depend upon Lightning-style off-chain payment channels.