Don't Talk About It, Prove It (NiPoST)

Why does a miner need any kind of proof to join a network? To answer this we must understand that blockchains are often permissionless, and this property allows everyone to join the protocol and participate without having to identify themselves and get approval from any single, central authority. This property is also important for the decentralization of the network, because it does not limit the number of nodes that can run the protocol and duplicate the blockchains global ledger. This in turn makes the network more secure since copies of the correct state are stored in multiple locations worldwide.

Making a blockchain permissionless, however, exposes the entire network to malicious actors that wish to attack the network and potentially affect the transactions submitted and interfere with the consensus protocol for profit. Some attacks may include a small number of participants to try and fool the system and make other miners think that malicious miners have a much larger voting size than they actually do. These kinds of attacks are called Sybil attacks, the ability to forge multiple identities and use them to skew consensus to the will of the attacker.

In order to overcome Sybil attacks in a permissionless network, miners need to prove they have spent or produced a scarce resource that is hard to find in order to participate. In a way, miners spend resources to purchase “lottery tickets” to be eligible for mining.

Bitcoin overcomes these types of attacks by forcing each miner to produce a number that is an answer to a cryptographic puzzle—to find it a miner tries to output random numbers and test them against the cryptographic puzzle to see if it matches. If it does, then the miner is eligible to produce a block into the blockchain and participate in consensus. This process is the “work” in “proof of work” consensus. But this “work”, as we know well, is wasting a lot of energy and nowadays requires specialized hardware to produce.

Using storage as scarce resource is different, as it does not take a lot of energy to read from disk, and no specialized storage is needed to generate the data (at least in the Spacemesh protocol). But these properties of any storage device make it a bad candidate to replace the hard “work” a miner must do to prove its eligibility to participate in consensus. If for instance, proof of space would use simple files, malicious miners can use a file to participate in the network, and later erase it to reuse the space for another identity on the network. To overcome these easy attacks, Proof of Space must use a special type of data that will make it harder for malicious parties to forge. This special type of storage needs to be difficult to create, i.e will take significant time and resources to create, to incentivise the miner to store it, as opposed to re-creating it when needed. Another important feature the storage must have is its uniqueness to a specific miner so that malicious miners can’t exchange the files instead of creating them and also so that storage cannot be claimed by ones who did not allocate it.

And now, after we’ve laid out all the motivations Spacemesh Proof of Space must have, we can outline how Spacemesh has designed its Proof of Space protocol to accommodate these issues.

The mining process in Spacemesh is called Smeshing (our miner is fondly called Smesher). Moving forward we will use this term to describe our miner. The first thing a Smesher does when they start mining (smeshing) using PoST consensus is to construct a unique data structure on the Smeshers designated storage. This initialization process where this file is created is called “POST init”. To make the data structure unique, Spacemesh uses the nodes Identity as seed for the data structure to identify storage of a specific Smesher. This too prevents forgery of the space.

Init phase needs to take a substantial amount of energy to do so: hashes are written as data on disk. Writing POW style data to disk ensures that a minimum amount of time and energy will be required to create the POST, so that it would be irrational and not cost effective to discard this data after use, and store it for the entire time of running consensus. Another important feature this data should have is not to be compressible, since if the data can be compressed and decompressed storage can be reused. The difficulty of creating the POST, which affects how long it will take to create the data, can be adjusted without changing the size POST takes on disk or the time it takes to verify the data.

After the init phase comes the execution phase. In the execution phase, a Smesher will prove it has access to the data generated in the initialization phase. To produce such proof, a Smesher will hash the provided challenge with each data label in the initialized storage file and then will select only the hash results that are below a predefined threshold. The prover must produce at least some data leaves that match the condition. In the event that not enough indices have matched, a Smesher will do the same process again and will add some random element, usually called “salt”, to the hash. By using this proving method the protocol incentivises the miners to keep the same storage from the first execution phase, since re-creating the data again will cost significantly more money than reading the results from disk. Verifying the data is simple enough, since the algorithm is deterministic. The verifier can hash the provided data leaves with the same challenge and salt and verify that the same results are outputted. This method is done in a non-interactive way, meaning that no communication between prover and verifier is needed at time of both proof and verification.

So far we have walked through the process of how a Smesher proves that space was stored on their disk during the execution phase. But simply relying on proofs of space is not enough, since as mentioned before, Smeshers may still use the same storage to produce multiple post proofs and potentially enable a Sybil attack. Proving that storage has been stored for some time provides additional protection against such attacks. Non-interactive proof of space time must include a proof of space, as well as a proof that time has passed and the same storage still exists. This is accomplished by sending the initial challenge of the first execution phase as input to a Spacemesh time server—POET—which uses this challenge as seed for its proof of elapsed time. After the time server has generated a proof that enough time has passed, it then transmits this proof to the entire network. All Smeshers that wish to participate in the consensus process must prove that they are still in possession of the storage they have proved to have before. They can do so by using the POETs output as a new challenge to the next execution phase, where the storage will be hashed with the new challenge to provide a new set of random indices as proof. An interesting note is that according to the protocol, a miner must not necessarily prove that they have access to the same exact data it has proven before, but rather to a data of the same type and size. tThis, alongside with the fact that the data generation during the init phase is deterministic and can be re-created on demand, implies that a miner could potentially re-create the data on the fly, but this would be a much more costly operation than to keep the same storage on disk.

After the execution phase has been completed with POET output a Smesher can build a NiPoST—non-interactive proof of space time. This data structure contains all information needed to prove that a Smesher has stored the initialized storage for the required amount of time. The NiPoST struct will now contain a proof of space, the received POET proof and seed that proves enough time has passed, and a reference to previous proof of space with previous challenge. By proving that the Smesher still has access to the data and chaining it to previous POST proof, a Smesher chains proofs of space and time to create a consecutive chain of time and prevent the ability to create many proofs initially and using them when needed. The NiPoST structure is key for Smesher eligibility proof. Once created, the NiPoST is referenced in a Spacemesh activation transaction: ATX. These types of transactions are the Smeshers’ ticket to produce one or more blocks in the upcoming epoch.

Proof of space time is an innovative consensus method that aims to be more sustainable and allow a more decentralized network with more access to home miners than current POS and POW consensus blockchains. Relying on space as a scarce resource is the key to allow a low barrier to enter the protocol as a Smesher, and as a result earn Smesh from mining and transaction fees. Storage is a common resource that is both used by home users and enterprises; a common denominator found in almost all computer setups. It is a more even playing field because, aside from read and write speeds, there is no technological advantage to be gained by using different hardware—a gigabyte of storage on a gamer PC is the same as a gigabyte of storage on a server farm. Proving POST using NiPoST allows us to prove resources were allocated by a Smesher in a non-interactive way, so that all the block mesh data can be verified using only on chain proof.