Proof of Capacity (PoC) is a sound and fair consensus algorithm. Sound because it uses off the shelf equipment and does not waste energy. Fair because it has a very low entry barrier and shows a more linear scaling.
Essentially, PoC consists in storing hard to compute hashes and then reusing these hashes every time a block is to be forged. The basic idea is: the more capacity you have, more hashes you can store, higher is your commitment to the system and higher should be your reward (your chances to forge a block). Clearly, if one is able to fake capacity by whatever method — e.g. combining it with Proof of Work (PoW) — then the algorithm is no longer fair nor sound.
One can always try to emulate PoC using PoW, but for PoC to remain sound and fair that kind of emulation should be economically infeasible. However, while PoW advances continue to be governed by Moore’s law (doubling computational power every two years or so), cost per Gb of storage has not advanced at the same pace. If this trend is to remain, PoC algorithms would need updates as time goes or will cease to exist.
In this paper, I show one possible method to fake capacity for the PoC algorithm currently in use in Burstcoin and other derivative coins. For the sake of simplicity the format known as PoC1 is considered here, but it could be easily extended to fake PoC2 capacity. Finally, a simple proposal to increase the computational work per Mb of capacity ratio is given. This proposal consists of a hard-fork but keeps current plot files working. However, those willing to migrate to the proposed format will have an advantage since plots will occupy less space.
Proof of Capacity Files (plots)
Most information and images on this section come from burstwiki. I will keep the definitions minimal here, check that wiki for nomenclature and more complete explanations. The pre-computed hashes that can be used to forge blocks are stored in the so called plot files. A plot file contains many nonces, but for our analysis here we can focus on a single nonce.
Each nonce consists of 4096 different scoops. Each scoop contains 64 bytes of data holding 2 hashes. When forging a block, a scoop is chosen and the miner should read its contents. These hashes inside of each scoop should be hard to compute in real-time, thus the proof you pre-computed them and had the space to store them. The procedure to compute these hashes is as follows:
- Computing the first hash, or the last depending on how you see it (#8191):
2. Computing the second hash (#8190):
3. Computing the third hash (#8189):
4. Follow the same procedure of pre-appending resulting hashes to a new seed to compute up to hash 128th.
5. For all remaining iterations we only need 128 hashes (the last 4096 generated bytes):
6. Compute the final hash, by using all 8192 hashes and the first 16 bytes as seed:
7. Xor all other hashes individually:
8. With all this, we have all the information belonging to a nonce:
This is known as PoC1 format, I’ll avoid the PoC2 shuffle here for the sake of simplicity but without loss of generality.
All the steps shown previously are meant to avoid faking capacity. The final hash (step 6) including all previously computed hashes is to assure no one can have a particular scoop without computing the entire nonce.
Throwing away hashes, computing them as needed
Now consider the case you compute the entire nonce but store only the final hash of step 6 and do not XOR any hashes (avoid step 7). Then, let’s say the next block needs scoop 4095, this would be very cheap to compute in real time, you don’t need it on your hard drive. One just needs to go through steps 1 and 2, and then skip directly to 7, since you have the final hash stored. This would be extremely cheap because hashes #8191 and #8190 use a very small seed input. A little more effort is needed to compute scoop 4094, and increasingly more effort is needed as scoop 0 is approached.
By storing only the final hash, this method would be effective only for high scoop numbers, as the difficulty in computing lower scoop numbers increases, being scoop 0 the more costly to compute. Thus, this method would allow for faking just a small percentage of the space, requiring the dishonest miner to store most of the scoop numbers.
Another more sophisticated approach would be to store contiguous hash portions containing 128 hashes. This way you could throw away 128 hashes, then store 128 hashes, then throw away, and so on, keeping the final hash (step 6). By doing this, the storage space you need would be half the needed by an honest miner. Every time you need a hash that was thrown away, you just need to read the previous 128 hashes, then use step 5 to compute the missing hash. This would be possible because you only need the previous 128 hashes for computing a new one and not the entire nonce (assuming the final hash is available).
A simple proposal to make PoC more PoW resistant
As explained in the previous section, a possible method to fake capacity, by computing hashes on the fly, is to store contiguous sections with 128 hashes and throw away part of the hashes (not storing them). The difficulty in faking capacity this way could be much increased by a simple solution: only scoops multiple of 4 (or 2, 8, 16, etc.) would be valid for forging blocks. This could be implemented for Burstcoin with a single line of code. This hard-fork would consist in just replace line 141 of GeneratorImpl.java by:
This way, an honest miner would need to store only 25% of the currently used space and would never need to store contiguous hashes, since only this fraction of the scoops would be used to forge blocks. The one trying to fake capacity, would need to store even more information than honest miners (since 128 contiguous hashes are always needed to compute a new one), thus becoming uneconomical.
Plotting/mining software are also easily adapted to only store/read the valid scoops. An engraver/scavenger pair with this implemented is already available at:
This modified scavenger simply works either with modified or regular plots. The modified engraver also can produce regular files. However, the modified engraver accepts an additional argument for the number of scoops that should be skipped or jumped when storing the plot. For storing only multiples of 4, this would be:
engraver -j 4 [other arguments …]
Resulting “compressed” file names are appended with the number of scoops skipped this way:
With the proposed hard-fork, existing plot files continue to work as they are. Miners could “compress” (just throw away 75% of the scoops) and plot the remaining space with new nonces. Pool software can also probably be left unchanged (or updates would be minimal in case scoop numbers are computed within pool software).
A “compression” tool is not currently available to reduce the size of existing plots, but implementation is trivial and would be available if this proposal is accepted.
Proof of Capacity (PoC) can always be emulated by Proof of Work (PoW). However, in order to keep PoC sound and fair, faking capacity should not be economically viable. The current PoC algorithm implemented in Burstcoin and other derivative coins is currently subject to fake capacity. In this work a very simple solution is proposed, increasing the difficulty to dishonest miners.