Proof of Storage to make distributed resource consumption costly.

[Razerglass]

https://bitcointalk.org/index.php?topic=731923.0

Burst coin PoC

[fivebells]

FWIW, I asked the burstcoin dev about this thread, and he said he hadn't seen it before.

[TierNolan]

It looks like the burst system is resistant to the Bloom filter attack?

They generate "plots".  These are 256kB blocks of data generated using hash(account-id | plot-nonce) as seed and hashing it over and over to expand to the 256kB.  They also mix the array with the last 32 bytes of the array.

Then, they are broken down into 4096 "scoops" of 32 bytes each.

Based on the hash(previous-block | block height), a scoop index is selected (0 - 4095).

The miner has to scan through all scoops of the same index.  I assume they store all scoops with the same index together.

The scoop is run through hash(previous-block | scoop) and then divided by the target.

This gives the number of seconds to wait until the next block (lower is better).  If you get a result of 30 seconds, then you can create a block 30 seconds after the previous block.

The more plots you have, the more likely you will get the lowest result.

This means that miners have to read 1/4096 of the data stored on the disk in order to extract the scoops.

There is no way to Bloom filter, since all scoops concatenated with info from the previous block before being passed through a hash function.  This means the value of each scoop changes on a per-block basis.

[work2heat]

This seems like a great idea. Has there been any work towards implementing it in core or elsewhere?

One implication though is that honest services which provide monitoring and statistics of the network as a whole will become much more costly. Solutions might be public key authentication of such monitoring services or else for servers to accept "read only" connections (could be http-like or normal tcp socket that is never read from).

[Taek]

How do you use that method to tell that a host is storing say, 2^12 plots (1GB)? There's no way for you to verify that the value presented by the host is the optimal value within the set of data that they are storing, except for you to somehow incentivize their finding of the optimal value. And then you have to do probabilistic analysis of repeated solutions to determine if they're scanning over the whole set each time.

As a method of consensus, this seems vulnerable because H(previous-block | block height) is something that the miner can control. If the miner is controlling 10% of the plots, but has enough time each time a block is found to grind over 100 potential values for `previous-block`, then the miner is very likely to find at least one value of `previous-block` that results in a scoop in one of the miners plots having an unexpectedly low time to produce the next block. Depending on how long it takes to scan the plots for the lowest value scoop, a miner could potentially try an enormous set of values for `previous-block`, until something is found that heavily favors the miner's plots.

The miner is then able to artificially inflate the number of plots that it appears to be storing, but only for blocks where it controls the value of `previous-block`. This means that a miner never has any incentive to use a chain produced by someone else, because they will not be able to grind over the value of `previous-block` and will be mining at a significant disadvantage compared to mining on a history composed of exclusively their blocks.