0
$\begingroup$

I just came across a blockchain concept called "Proof of Space-Time" in which participants compete to verify blocks by generating and storing essentially random data to answer essentially random cryptographic challenges. The more data they can afford to store, the higher their probability of winning a challenge.

The difference between "Proof of Space" and "Proof of Space-Time" is that the latter incorporates some way of determining when an answer was generated, and the result is that participants must continuously overwrite their storage with current random data (... which is, as a practical matter, less efficient than only generating and storing random answers one time for a given storage block).

I gather that there is some attack that makes "Proof of Space" alone insufficient, but what is it?

I.e., how can participants game the system to make it seem like they have dedicated more storage to the challenge than they actually have?

My first guess is that all computer storage – even that dedicated to other productive uses – can be sliced up to look random enough for the purposes of a proof-of-space challenge. But my first response it that could be mitigated by requiring that the answers be salted with specific data that would prevent completely arbitrary storage blocks from serving as valid answers.


The second page of the linked paper alludes to an adversarial strategy in which work (i.e., computing capacity) can be substituted for space (i.e., storage capacity). Space-Time answers can reduce the capacity for substitution, but I don't understand how that really applies.

Here's how I have tried to understand this:

  1. Network participants generate random "proofs," which are data blocks that satisfy some network parameters that make them useless for other purposes.
  2. The network issues a challenge in the form of a random number x.
  3. Each participant answers with the hash of its proof that is closest to x. The winning participant is the one with the hash closest to x, and is verified by publishing its full proof.

The security of the network depends on honest participants controlling a majority of the network's storage resources.

Substituting computing capacity for storage capacity would be an attack on this security mechanism. As I understand it: A computing attack would wait to see the challenge and would then generate proofs and then store only the best proof for the particular challenge. But how meaningful is this attack? No matter how much greater the computing capacity than the storage capacity of the network, the time to answer can be reduced so that the probability of a computing attack overwhelming stored answers is negligible.

What am I missing?

$\endgroup$
2
  • $\begingroup$ They explain their reasoning in the introduction of the paper, and highlight examples of what could go wrong with PoS -- whether you want to consider that an attack or not is up to you.... $\endgroup$
    – D.W.
    Jul 31 at 5:40
  • $\begingroup$ @D.W. I don't understand those explanations. I just elaborated the question accordingly. $\endgroup$
    – feetwet
    Jul 31 at 20:56
1
$\begingroup$

Here is a practical way to "attack" (i.e., substitute computation for storage) a static proof-of-space network: Use a deterministic random-number-generator (RNG).

Here's an example based on a RNG that produces deterministic results based on a "seed."

  1. Generate proofs using random seeds. Store each proof's hash (i.e., "answer") value. So instead of storing long proofs, only store the seed-hash pair.
  2. If a full proof is requested then regenerate it based on the seed.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.