From Game Theory to POW, POS and DPOS

No Comments 58 Views0


From Game Theory to POW POS and DPOS IMG 00

In Applied Mathematics there is a very interesting branch named Game theory. According to its literal meaning, it should be known as a theory of “game”. However, the “game” here does not refer to the scope of conventional entertainment, otherwise it will never have the values of mathematics researches. In a broad sense, the “game” is a model in which many scenarios involving strategic games can be modeled in this way.

What elements are included in the generalized game model?

  1. Rules: Firstly, games must have relevant rules which are open and transparent to all players and they cannot be modified arbitrarily. All the players must follow the rules.
  2. Players: Each player plays the role of “rational person”, who can unscrupulously maximize his own interests.
  3. Rewards and Punishments: Rewards are the motivation for each player to participate in the game. Prizes are obtained through mutual competitions. And punishment is a constraint on the players, so that everyone cannot break the rules arbitrarily.

 

A Stable Triangular Structure

Three elements interact to form a stable triangular structure.

As mentioned above, many application scenarios in the real world are applicable for this model. Such as the stock market, it has trading rules, which are protected by the law. Profits as the prizes stimulate the players to participate in the games. The investors are like the players who always try to make more money for themselves.

It’s the same with the blockchains. Once decentralization is involved, it’s necessary to create a game model.

Obtain Wallet Address for Altcoin on Cryptocurrency Exchange IMG N01

Take bitcoin as an example, the incentives are needed to be motivate all the players to maintain the account books, and the bitcoin just serves as the reward. The way to get bitcoin requires some specified rules, which is certainly open and transparent. The rules are written in the computer program in the form of code and uploaded on GitHub, so that everyone can download and view. This is the Bitcoin Protocol.

In this game model, the rule is undoubtedly the most fundamental and important part. Since all the players are very “rational” and they need to maximize their own interests, so they will try their best to find loopholes in the rules for arbitrage. Good game rule will not allow the players to get arbitrage easily, otherwise the whole system will collapse.

According to Nash equilibrium, the strategy adopted by any player is the best one against a combination of strategies by all other parties; when all other parties do not change the strategy, no party will not (or can’t) change their strategy in order to maximize their own profits. Sound very complicated? To make it simpler, when each player adopts the best strategy to play the game, the whole game will enter a dynamic balance, which is called Nash equilibrium. A good game rule will eventually bring the entire system into a Nash equilibrium, so that the entire system can be optimized for operation in such a state.

 

Game of Bitcoin Can Finally Achieve Nash Equilibrium

In such an equilibrium, each player will obediently maintain the account book(blockchain). How can they do that specifically?

First, it’s a distributed accounting system. The node controlled by every player has a set of account books and is stored in the form of blockchain.

Bitcoin is the reward for accounting. The process of coming into being is like the mining process, so the player itself is also called the “mining worker.” They will receive stable rewards for every new “mining” of a new block, which will decrease over time. The genesis block consists of 50 bitcoins and now 12.5 bitcoins.

At first glance, there’s nothing wrong with such a rule, but it is worth noting that it’s based on the blockchain, so there is no legal protection, which means there is no punishment for the violation of rules. As I’ve said before, every player will try to maximize his own benefits. So naturally someone would try to maliciously modify the account books to increase their income.

In order to solve this problem, Satoshi Nakamoto invented Proof-of-Work which is called POW. Now, let’s talk about the POW.

 

POW (Proof of Work)

Imagine that if a hacker gains less profits by tampering with the account books, he will naturally no incentive to do so. The POW mechanism is just based on such a principle.

From Game Theory to POW POS and DPOS IMG 01

Image credit: bitcoinwiki.org

Firstly, it made mining quite difficult.

Mining activity itself is, in fact, a process of looking for hash value because each block is associated with a unique hash value. Moreover, each hash value needs to conform to certain specifications. Whenever the current block is filled with a large amount of transaction information, all nodes need to create a new block to store the new transactions and find a relevant hash value.

The POW mechanism aims to make such a hash value uneasy to be found. How is that realized specifically?

So, we need to use the SHA256 function, which was also introduced in our articles before. It’s featured with the evenly distributed value range and there is no way to reverse it.

The hash value we hope to obtain is the output of such a function. Its input contains information about all the blocks (such as creation time, block height, transaction information, etc.), we set it as x. Moreover, there are other variables such as the previous hash value (prev hash) and an independent variable (Nonce). So, the formula is:

Hash Value = SHA256(x, prev hash, Nonce)

Of course, the block information x is invariant. The prev hash which represents the previous hash value is also invariant. The only variable is Nonce, so Nonce is the solution of this function.

What standard does the output Hash Value need to meet? Satoshi Nakamoto defined a threshold which specified that the output must be less than this value. Since the output is completely random, it can only be solved by violence.

The subtlety of this design is that this threshold can be adjusted automatically. The lower threshold, the more difficult it is to solve.

That’s the whole process of “mining”, and the players themselves are also known as mining workers.

If the hacker tampers with the transaction information then, the output hash will be changed immediately beyond the specified range, and all subsequent block hash values will also be changed correspondingly.

From Game Theory to POW POS and DPOS IMG 02

Therefore, in order to repair the hash value of this series of blocks, it is necessary to repeat the complicated solving processes. That’s to say, for hackers, the cost of tempering with the account books will be greater than that of ordinary mining.

If the hacker has spent great efforts tempering with the blockchains, can he really be able to gain profits? Certainly not, because he has just changed the blockchain in the local node. To make the transactions on the chain confirmed, he must synchronize this chain to most nodes. Moreover, it’s hard to say whether other mining workers will agree on the tempered chain.

How can the other mining workers make the judgment?

They focus on the length of the chain. The longer chain, the higher POW. So, other mining workers will choose the longest chain for synchronization, which is also the origin of the Proof of Work (POW) mechanism.

Therefore, as far as the hacker is concerned, when he is mining in the tampered blockchain, other mining workers have already mined new blocks, so his chain will be shorter and abandoned by other nodes. Unless he can obtain more than 51% of the hashrate to catch up with the total blocking speed in other nodes, he would be doomed to fail in the end. To obtain 51% of the hashrate demands huge costs, including hardware and electricity. The hacker apparently has no incentive to do so.

Of course, POW is not perfect. One of the biggest problems is the huge hash consumption, most of which is spent in meaningless arithmetic solutions. In terms of resources, that’s a big waste. Ben Laurie, the founder of Apache, once complained that bitcoin mining had consumed 5% of the electricity in UK.

From Game Theory to POW POS and DPOS IMG 03

The quantum computer in the future is likely to surpass most current computers to carry out 51% hash attack.

Therefore, in response to these shortcomings, some new blockchain games have emerged correspondingly.

 

POS (Proof of Stak)

POS is short for Proof of Stake.

Stake is the share of holding tokens. Unlike POW, every player provides the share of tokens as the standard for verification instead of the proof of mining work.

From Game Theory to POW POS and DPOS IMG 04

Image credit: qtum.org

Simply speaking, the bigger share the player owns, the more blocks he can mine, which means that if a hacker intends to tamper with the account book, he must first purchase 51% of the token share. So, it greatly increases the cost of hacking. If the hacker has owned a 51% share, he will not conduct malicious tempering since he has been the biggest shareholder of the game and launching attacks means committing suicide.

Compared with POW, the advantage is that in the process of block production, each node does not need complicated solution, thus greatly saving the power consumption. It also means that each player can generate multiple blocks within a short time. The choice of block is determined by the number of tokens held by the player in this game. The one holding the most shares is selected to produce blocks with the right of “coinage”. So, the role the player plays will no longer be a “mining worker” but a “coin manufacturer.”

However, the mechanism also has its shortcoming, that is, the bookmaker with the most chips will monopolize the coinage, which is obviously unfair. So, there are two solutions:

Ⅰ. The Act of Coin Age

The so-called coin age refers to the time period of holding the token.

Since each block has a time stamp, the time of each transaction in the block also matches the blocking time. In other words, you can get the coin age by subtracting the target block time from the current block time. Therefore, we use the number of blocks as the unit of the coin age, and the minimum value is 1.

By introducing coin age as another parameter of the proof of stake, it is possible to restrain the monopoly of big chip banker. It’s like the formula of POW, except that the multiplication of the coin age and the share of equity is used as the threshold.

Hash Value <= Coin Age * Stake

So, the larger coin Age, the larger multiplication (the threshold) of the target, which means it’s easier to find a block.

After finding this block, the player gets the right to create a new block and Coin Age will automatically set as 0. It’s equivalent to entering the freezing period then and the player has no way to get the right to create blocks. Generally, the freezing period will last from 1 day to 90 days. The value of Coin Age can be restored only after the thawing.

This method is very effective in restricting the monopoly of big bankers on the coinage rights. As the originator of POS, PeerCoin just adopts such a method.

Ⅱ. Randomized Block Selection

This method introduces a random number evenly distributed in the interval [0,1].

Suppose there are N players, every time when “coin creator” is selected, a random number is assigned to each player. Suppose the random number is U while the player’s token share is S, the player with the largest S/U will entitled with the coinage right.

This method is a pseudo-random process. Although there is an evenly distributed random number which will affect the outcome, the players with larger shares are more likely to be selected as the coin creators. And the tokens held by every player is open to the public, so basically every player can predict who will be selected.

The most representatives adopting this algorithm include Nxt and Black Coin.

From Game Theory to POW POS and DPOS IMG 06

Since POS can save the hash, the transaction fee will be lower than that of POW. For the users, it’s a good thing.

Of course, it has defects also. For instance, it’s more likely to be attacked by DOS because multiple blocks can be generated within a short time. Even without DOS, since the participation costs for the players have been reduced, more nodes will join in the coinage, so the network efficiency will correspondingly reduce.

To solve this problem, some people have proposed the improved POS algorithms, DPOS is the most representative one.

 

DPOS (Delegated Proof of Stake)

This mechanism is like the US electoral system, in which several super nodes are selected by voting and only these super nodes can conduct mining.

EOS is just a typical representative.

Where are the Mainstream Cryptocurrencies Heading to IMG 06

EOS will select 21 super nodes and 100 spare nodes. All these 21 super nodes are responsible for the verification, recording and block production of all transactions.

As for voting, the owner of each EOS has voting rights. They must vote with their own EOS tokens and one EOS for 30 votes. These 30 votes must be given to different candidates, which means that each candidate can get no more than one vote within one round. 30 votes are certainly enough, so they don’t have to worry about whom to vote for. As a feedback, the selected super node needs to share the rewards to those who voted for them.

The advantage is that it can greatly increase the transaction speed and avoid the network congestion because there are only 21 nodes. The selected nodes are generally the elite nodes. Firstly, they have very good hardware —- the miners, the team must have a certain level of technology, and more importantly, the team members are very reliable. The existence of 21 nodes as decentralization can also be checked and balanced with each other.

In fact, with careful observation, we will find that this kind of gameplay is slowly moving closer to the centralization, which is a balance between complete centralization and complete decentralization. It also conforms to the “impossible triangle” theory proposed by Vitalik Buterin: when current blockchain cannot achieve Scalability, Decentralization and Security simultaneously, only two of them can be realized. Therefore, in actual applications, it is necessary to make appropriate trade-off based on actual situations. DPOS is a kind of concession for “decentralization.”

 

Dear readers, you can also rack your brains and think about what kind of games can be played with regard to the blockchain?

Leave a Reply