Evaluating a Proof-of-Greed consensus algorithm with simulation

This is a guest blog from Igor Mazurok that details research with Yevhen Leonchyk, and Tetyana Kornylova at Odessa National University.


Blockchain with AnyLogic – an introduction.

As well known, decentralized systems can offer advantages over those that are centralized, including greater scalability and reliability, but they are not well known for their speed. In relation to this, our goal was to investigate the performance demands of the increasingly popular PoS (Proof-of-Stake) consensus algorithm that is used in distributed blockchain networks and to evaluate it against a proposed Proof-of-Greed approach. This was achieved using simulation and without needing a distributed computer network.

In blockchain systems based on PoS, a harvester account is rewarded when it successfully creates a block. When a block is added to its blockchain, it contains a ledger of the most recent network transactions, and the process for generating a valid block on a PoS system is known as forging. In the standard version of the open source Nxt consensus (the first use of pure PoS), blocks are generated roughly every 60 seconds by network accounts that are open for forging. However, the method must allow for both increases and decreases in forging time when the need arises. Difficulties adjusting to these needs means selecting forge-time parameters in the existing PoS algorithm is problematic.

At the time of investigation, there were no known commission adjustment frameworks in blockchain systems. This means a user can give more or less commission than is necessary to process a transaction and that, overall, there is a transaction fee price-discovery problem. This problem is further compounded because, generally, transaction fees are paid in tokens and the value of these tokens can vary widely in relation to stable currencies over time. We propose a Proof-of-Greed method as an addition to the Nxt consensus to solve this problem. Such an approach allows the setting of fair market-based rewards for transaction processing.

Regarding these modifications, the important question of participant incentivization arises: what is the best harvester strategy for maximizing profit and decreasing stake payback time? As it turns out, optimal parameters could be obtained from simulation and, furthermore, we were able to take a deep look at new types of network attack associated with the proposed consensus algorithm changes.

Objectives of the study

Development and simulation of approaches to improve the block time characteristics of the Nxt consensus algorithm and the investigation of economic leverages.

Relevance

In recent years there has been a burst in popularity of PoS blockchain systems. Unlike systems based on PoW (Proof of Work), such as Bitcoin and Ethereum, where miners must solve complicated cryptographic puzzles in order to create blocks, in PoS-based systems the creator of the next block is chosen in a deterministic (pseudo-random) way. The probability of being chosen depends on a participant's stake, activity, and reputation. When compared with PoS, PoW consensus demands high computation capabilities and high energy expenditure to protect against a double-spending attack and the threat of centralization in mining pools. This is an increasingly severe disadvantage for some types of blockchain systems. Nowadays, PoS consensus methods, and in particular that used in Nxt, are being actively developed. Hence, there is an interest in considering newly discovered challenges and the proposal of modifications to the standard version of the Nxt consensus.

Research methods

The simulation requirements were fulfilled using AnyLogic. In particular, special models were developed to obtain the best Proof-of-Greed consensus parameters for achieving the block forging time and economic leverage objectives.

1. Block Creation (Forging)

Two values are key to determining which account is eligible to generate a block, which account earns the right to generate a block, and which block is taken to be the authoritative one in times of conflict:

Tp – previous base target;

Tb – calculated base target.

Each block on the chain has a generation signature parameter. To participate in the block forging process, an active account digitally signs the generation signature of the previous block with its own public key. This creates a 64-byte signature, which is then hashed using the SHA256 cryptographic hash algorithm. The first 8 bytes of the resulting hash are converted to a number, referred to as the account Hit.

The Hit is compared to the current target value. If the computed Hit is lower than the target, then the next block can be generated. As noted in the target value formula (see below), the target value increases with each passing second. Even if there are only a few active accounts on the network, one of them will eventually generate a block because the target value will become very large. Therefore, you can calculate the time it will take any account to forge a block by comparing the account Hit value to the target value.

The base target value varies from block to block and is derived from the previous block base target multiplied by the amount of time that was required to generate that block using a formula that ensures S0 seconds average block time over the last three blocks.

Each account calculates a target value for itself, based on its current effective stake. This value is

T = Tb ⋅ S ⋅ B ,

  • T is the new target value;
  • S is the time since the last block, in seconds;
  • B is the effective balance of the account.

In a situation where multiple blocks are generated, nodes will select the block with the highest cumulative difficulty value as the authoritative block. As block data is shared between peers, forks (non-authoritative chain fragments) are detected and dismantled by examining the cumulative difficulty values stored in each fork.

2. Preforging block time

The simulation model developed with AnyLogic software can determine the optimal parameters to achieve any specified average time between blocks. The number of nodes, distributions of effective balance, and several initial parameters can also be varied in this model. Results from a simulation run can be seen in fig. 1 below, the time for the last 3 blocks (the golden line) and for the last 100 blocks (the blue line) are shown for an S0 forging time of 15 seconds with a factor = 0.765.

The average preforging block time, model A

Fig. 1. The average preforging block time, model A.

As can be seen in the figure, there is a large block time problem when preforging time is too long. Further, the Nxt team proposed alternative formulas for base target recalculating in the case of S0 = "60" seconds (model B):

Alternative formulas for the base target recalculating 1


Alternative formula for the base target recalculating 2

And if the Tb goes out of the limiting interval, set it to the limiting value:

If Tb < 0.9 ⋅ T0, set Tb = 0.9 ⋅ T0;
If Tb > 3 ⋅ T0, set Tb = 3 ⋅ T0.

Such algorithms should solve the problem of large block times for good. Also, block times will become more “concentrated”, i.e. the variance will decrease (fig. 2).

The average preforging block time, model B

Fig. 2. The average preforging block time, model B.

The simulation model developed to obtain the best parameters for any given forging time S0 and preferable minimum and maximum time limits.

The average block time depends on the number of nodes and their stake (balance) distribution. To reduce the percentage of large block times, we propose the use of asymmetrical factors, when MaxRatio is greater than MinRatio in model A. Such an approach achieves a result similar to that in model B. Moreover, it provides a greater time decrease for the next block when following a block which took a long time.

For S0 = 15 sec:

MaxRatio = 15 + 1.025 = 16.025 sec
MinRatio = 15 - 0.765 = 14.235 sec


with the recommended the initial base target

Initial base target formula

where B is the effective initial total balance and Hit is the first 8 bytes of the hash that are converted to a number (the hash is the digitally signed generation signature of the previous block).

3. Proof of greed approach

As previously stated, there are no commission adjustment frameworks in current blockchain systems. A user can give a commission that is less than required to ensure a transaction is processed or they may pay more than is necessary. As such, there is a price discovery problem. We propose a Proof-of-Greed approach as a resolution.

Instead of indicating a fixed transaction fee, a user will offer the maximum fee that he/she is able or willing to pay. Transactions transfer into the Transaction Pool and from there harvesters take transactions and form their own blocks and take their commission — as much as they want but not more than the specified maximum. Here, greed comes into play. The more a harvester takes for commission, the less the likelihood of their block being recorded on the blockchain. This is achieved with the following modification of the Nxt Consensus:

N – the number of nodes;

numTri – the number of transactions in the block from node i, i = 1,...,N;

actFeeij – how much commission node i took from the transaction j, i = 1,...,N, j = 1,...,numTri;

maxFeeij – maximum that node i can take from the transaction j, i = 1,...,N, j = 1,...,numTri;

gi – the greed of the node i, i = 1,...,N:


Modification formula of the Nxt Consensus


λi – parameter of the node i, i = 1,...,N:

λi = [ 1 + Δ ( 1 - 2gi ) ]k;

and finally

T = Tb⋅S ⋅ B ⋅ λi.

λi is a special factor, a function which depends on harvester greed and a few other parameters, which can increase or decrease the possibility of forging a block.

As a result of the blockchain network simulation, the recommended parameters for the Proof-of-Greed algorithm are:

  • Δ = 0.5;
  • k = 3.2.

These parameters were adjusted to protect from a zero-fee attack. Thus, a few nodes, which create blocks for free, cannot get control of the system (fig. 3). In this simulation, the first 10 harvesters do not take fees at all and have effective balances of 250,000 tokens; the last 10 harvesters take maximum fees and have effective balances of 1,000,000 tokens. The remaining 280 nodes have stakes and values of greed which are distributed linearly.

The zero-fee attack

Fig. 3. The zero-fee attack.

As a result, the first 10 nodes (and even the first 50 nodes which take small fees) do not produce most of the blocks. Here we assume that earned tokens are not added to effective balances. Otherwise, the influence of the first harvesters will be even more reduced.

On the other hand, such altruistic nodes can help to protect against a large-stake attack of greedy harvesters. In fig. 4, the last 10 harvesters take maximum fees and have huge effective balances of 10,000,000 tokens each. The rest of the 290 harvesters have stakes from 250,000 to 1,000,000 and their greed is distributed from 0 to 100 % linearly.

The large stake attack

Fig. 4. The large stake attack.

It can be seen that very greedy nodes with huge stakes cannot impose their rules on the entire system. Thus, Proof-of-Greed stimulates the harvesters to work for a modest fee.

4. Incomes of harvesting blockchain nodes

With the proposed Proof-of-Greed modification to the Nxt consensus mechanism, harvesters independently make decisions about what proportion of commission fee to take for forging a block. This may lead to the fact that some nodes will charge the maximum fee for the creation of a block in order to quickly pay back their initial stake. But the more a harvester takes, the less possibility that his/her block will be recorded on the blockchain. This is achieved by modifying the Nxt consensus mechanism. Also, nodes can choose to take the minimum fee per block, in the expectation that processing a greater number of blocks will provide greater profits than with the aforementioned approach. Thus, the problem is to find the fee nodes should charge in order to maximize profit and cover their initial stake as quickly as possible.

In the figure below, the chart shows the earnings of each node (without initial stake), the initial stake of each node is 250,000, and double the initial stake is 500,000. Thus, meeting the 250,000 line and 500,000 line on the graph means that nodes have paid off their initial stake once or twice respectively.

In fig. 5 the initial values of the effective node balances (stakes) equal 250,000 tokens. The payment that the nodes charge for the creation of a block is distributed linearly from 20 to 100 percent of the maximum possible across 300 nodes. As a result of this experiment, it can be seen that the first 100 nodes paid off their stake earlier than others.

The case of equal initial balances (stakes)

Fig. 5. The case of equal initial balances (stakes).

In this simulation, the payment proportions that the nodes charge for the creation of a block are distributed linearly from 20 to 100 percent of the maximum fee possible across 300 nodes (fig. 6). The initial values of the node stakes are distributed linearly from 1,000,000 to 250,000 over the 300 nodes in the same order.

The case of different balances and proportions of fees

Fig. 6. The case of different balances and proportions of fees.

As a result, it was determined that with different initial rates for the nodes, the optimal amount of commission ranges from 30 to 40 percent of the maximum possible. This ensures maximum profit and the fastest stake payback according to the Proof-of-Greed approach.

Conclusions

This Proof-of-Greed modification proposal for the Nxt consensus mechanism solves some of the general incentivization and reward problems that exist in distributed systems based on blockchain technology. The best parameters to decrease the variance of block forging time were obtained using simulation software. Further to that, the simulation showed that the Proof-of-Greed consensus approach can provide market-based commission fees for network transactions and also guard against some network attacks. Finally, we were also able to make recommendations on harvester node performance in relation to achieving the fastest stake payback period. Even though the simulation was only carried out for the Nxt algorithm, we see prospects for Proof-of-Greed in other similar PoS systems where the problems of transaction cost optimization arise.


You can download from ResearchGate Igor Mazurok, Yevhen Leonchyk, and Tetyana Kornylova's original paper.

Verwandte Posts