Editor's note: This article is from Hash Future, author: Chen Zhijia, Meng Yize, Jiang Zewu, published with authorization.

Since the first bitcoin was mined in 2009, the blockchain industry has gradually expanded into a huge global market. In addition to BTC, various blockchain projects such as LTC, ETH, and EOS are emerging in an endless stream. At present, there are more than 110,000 ERC20 token projects on Ethereum alone; and there are countless companies that have released project white papers.

POW (Proof of Work) Consensus Algorithm

Bitcoin implements a point-to-point electronic payment system, and the birth of this distributed system depends on its POW (proof of work) consensus algorithm. At present, the vast majority of blockchain projects with main chains still use POW or the improved POW consensus algorithm, and only some projects use algorithms such as POS (Proof of Equity) or DPOS (Proxy Proof of Equity).

POW brings a concise and effective consensus generation mechanism to distributed ledgers, but it also creates some problems: in the process of calculating the hash function, a lot of energy is wasted——

According to reports, in 2017, the amount of electricity wasted due to Bitcoin mining exceeded the annual electricity consumption of Denmark. [1] In addition, due to the generation of chips such as ASICs, Bitcoin is also facing the challenge of increasing centralization. The current state of Bitcoin has come a long way from Satoshi Nakamoto's earliest designs.

The POS and DPOS mechanisms also have the problem of centralization, and the voting process is often cumbersome. The two are obviously not the best solution. It is worth mentioning that there have been some blockchain projects on the market that adopted schemes such as "trading is mining", "locking is mining", "insurance is mining", and "mining is mining".But in essence, these projects only issue ERC20 tokens on Ethereum. Since there is no main chain, these projects do not require a consensus mechanism; the so-called mining scheme is essentially an airdrop scheme, which is an incentive method and has no necessary connection with the core technology of the blockchain.

To really solve the problems of wasting energy and centralization derived from POW, and develop diversified mining solutions, at least the following series of technical problems need to be solved:

(1) If it does not consume a lot of work, what is the proof that the user has paid the price?

(2) How is this proof verified?

(3) How to determine the winner of the mining competition?

(4) How to avoid the fork of the main chain, etc.?

Proof of Space, proof of space

In the process of technological progress, the PoSpace scheme has made important explorations. PoSpace is Proof of Space, proof of space. PoSpace intends to replace the PoW mechanism in Bitcoin and become a new type of consensus mechanism solution.

This solution has already been implemented in some blockchain projects. It takes the hard disk space paid by the user as the proof of payment, and occupies the hard disk space by downloading files. The larger the occupied space, the greater the user's payment.

PoSpace can bring the following benefits: greatly reduce the waste of resources; after the user pays for the hard disk space at one time, no additional payment is required for subsequent mining, etc. According to the calculations of some teams, user behavior in PoSpace can be regarded as an expansive game model. As time goes by, more and more users will join in. [1]

In order to deal with the problem of falsification of hard disk space, PoSpace divides nodes into two roles: certifier and verifier. The prover is an ordinary node and needs to store large information data (such as 100G), while the verifier stores the database and a small part of the prover's stored information for verification.

When a user/certifier joins the network for the first time, he needs to store some data with a specific sequence according to the selected storage space (the stored data is determined by the user's public key, so the data of each user is different). These data are stored in a directed acyclic graph structure, and the association relationship between each data block is sent to the verifier in the form of a Merkle tree.

In this way, the verifier can know from the public key which data is stored by the prover, and from the sent Merkle tree to know how the data is stored.

In the verification phase, the verifier sends a "challenge" to the prover. The challenge is for the prover to store some random combination of data blocks. The prover needs to generate the hash value corresponding to the combined data according to the challenge information, and return it to the verifier, who will verify whether the hash value is correct.

Since the challenge is a random combination of data, slightly different data will result in completely different hash values. Therefore, the prover must indeed store the data block specified by the "challenge" in order to generate the correct hash value. Since the verifier has stored a complete database, he can also verify the hash value sent back by the prover.

It is possible for the prover to store only a small part of the data and still pass the verifier's challenge (the small part of the data stored by the prover happens to include the combination of data included in the challenge). However, as the "challenge" process is repeated many times, the probability of the prover generating correct feedback by storing a small amount of data drops significantly.

Therefore, the cheating behavior of the prover can be avoided by multiple verifications. This is the space confirmation process in PoSpace.

The solution to the "mass function"

With the method of verifying the user's storage space, there are still some ways to determine the winner of the mining competition. A more reasonable way should be that miners with larger storage space are more likely to win the mining competition. PoSpace achieves this goal by designing a "quality function".

The "quality function" needs to maintain a certain degree of randomness, and at the same time distinguish the probability of each miner winning according to the size of the contribution space. Therefore, a simplified method is to respond to the challenge of the verifier, and the hash value (a string of numbers) fed back by the miner is directly used as a random amount, and the string of numbers is increased or decreased according to the space occupied by the miner. For example, if the total storage space of the miners is N, the hash value is squared N times to obtain the quality function. In this way, the larger the storage space of the miners, the smaller the value of the quality function. We can stipulate that in a single mining competition, the miner with the smallest mass function wins.

But there is still a problem at this time:

Since the miners do not need to make subsequent payments during the mining process after paying for the hard disk space at one time, there is no cost to participate in the mining competition, and there is almost no cost for the main chain fork. In order to avoid chaos such as double spending caused by random forks of miners, we still need a rule to determine that a certain chain is the only chain, and all users only record this unique chain, which is the real consensus.

Since each block is mined by the miner with the smallest "mass function", a natural idea is to use the quality function to determine the unique main chain. We set a quantity i, and stipulate that the mass function of the previous i blocks from the latest block is added to obtain the total mass function of the chain. The chain with the smallest total quality function can be determined as the main chain. On this basis, in order to emphasize that the earlier blocks account for a higher proportion, a discount function can be added to reduce the early blocks (to improve its importance).

Summarize

Summarize

PoSpace uses physical hard disk space as a proof of payment, which solves the problem of continuous waste of a large amount of resources in Bitcoin, and at the same time can establish an electronic payment system with the same function as Bitcoin.

PoSpace can be considered as a major advancement of the consensus mechanism based on POW. But at the same time, there are still some problems in PoSpace: for example, the introduction of the role of the checker increases the risk of the system; how to design and arrange the checker is still a problem; there is a risk of centralization as evidenced by hard disk space , because a small number of people can use huge financial resources to purchase a large amount of hard disk space, continue to monopolize mining, and cause similar "51% attacks". Satoshi Nakamoto's vision of "a CPU chip represents an individual, and each individual has equal mining opportunities" is still difficult to realize.

But it has to be said that PoSpace's ideas have provided us with a lot of inspiration, such as verifying the price paid by users in a random way; determining the way to win the mining competition by designing a block quality function; Main chain fork, etc. Following this line of thought, it is entirely possible for us to develop consensus mechanisms that adapt to different usage scenarios, such as "Proof of Attention", "Proof of Time", etc.

references:

references:

[1]Park S, Pietrzak K, Alwen J, et al. Spacecoin: A cryptocurrency based on proofs of space[R]. IACR Cryptology ePrint Archive 2015, 2015. 

[2] Dziembowski S, Faust S, Kolmogorov V, et al. Proofs of space[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2015: 585-605.