Blockchain Formation Algorithm

People often turn to me for advice if they are somehow related to technologies that work on the blockchain. I decided to write this article to help those who are already working or planning to start working on projects based on a distributed database and blockchain.

I will describe the option of forming the blockchain, which is used in Dcoin . To use it, you must have confidence that the nodes will not be able to multiply uncontrollably.

In Dcoin, nodes cannot multiply uncontrollably because every miner is a living person who has proved to other miners that he is a man and he has no clones. The word "miner" here, most likely, does not really fit, but it so happened that I use it in this way.
')
Each time after creating a new block, miners are distributed in levels.

Suppose that at the 0th level there was a miner with ID 1056. Then the level distribution will look like this:
0: 1056
1: 1057, 1058
2: 1059, 1060, 1061, 1062
N: 1056+ (2 ^ N) -1 -> 1056 + ((2 ^ N) -1) * 2

How is the ID determined, which is at the 0th level, I will tell you a little later.

Each miner creates a special key pair for the node, the public key is written to the blockchain, and the private key is stored on the node and is used to sign the blocks.

The block has the following structure:

Field	Description	The size
BLOCK_ID	Block sequence number	4 bytes
TIME	The time when the block was created	4 bytes
USER_ID	ID of the user who created the block	5 bytes
LEVEL	The level at which the miner was at the time of block creation	2 bytes
SIGN	Signature from (TYPE, BLOCK_ID, PREV_BLOCK_HASH, TIME, USER_ID, LEVEL, MRKL_ROOT) made with the node-key	From 128 bytes to 512 bytes
TRANSACTIONS	Transactions	Up to 3Mb

Time

When a new block is received, the time of its generation is checked, which is indicated by the node that created this block. When checking the time, the number of seconds spent on generation, checking and waiting at the level is taken into account.

120 seconds after the signing time of the last block, the miner node at the 0th level creates a block, recording transactions that have accumulated in it.

If for some reason the miner node from the 0th level did not send a block to the network, then after 120 seconds (if 120 seconds did not pass, then all the nodes wait for the block from the 0th level) the node can be signed by the nodes from the 1st level etc. If a node from level 0 wakes up and starts sending out its block to everyone, then it will have a chance to “push through” it only if the majority of nodes have not yet received the next block.

Division into levels is necessary in order that blocks could be added in predicted time intervals . With each level increases the likelihood that it will be living nodes that will generate and sign a new unit.

Hash comparison

If the block is signed by miners' nodes, for example, from the 2nd level, you get 4 valid blocks that divide the entire network into 4 segments, and all segments will be sure that they have the right block and the right chain of blocks.

In order to avoid such segmentation, the search for the smallest hash from user_id, block_id, prev_head_hash is used.



Thus, when a node receives, for example, 4 blocks from miners from the same level, it will choose the one that has the smallest hash and ignores the remaining 3. In this case, the ID of the compared blocks must be equal.

Manipulations with hash are impossible, since there is no data to change.

The process of finding the block with the smallest hash initially occurs between nodes of the same level for 5 to 8192 seconds, depending on the level. Thus, in most cases, blocks with the smallest hash already selected fall into the general network.

A miner that is at level 0 is defined like this:

$ctx = hexdec(substr($hash, 0, 6)); $hi = $ctx / 127773; $lo = $ctx % 127773; $x = 16807 * $lo - 2836 * $hi; if ($x <= 0) $x += 0x7fffffff; $level_0_miner_id = (($ctx = $x) % ($max_miner_id + 1)); $level_0_miner_id = ($level_0_miner_id==0)?1:$level_0_miner_id; 

Where $ hash = sha256 (sha256 (user_id, block_id, prev_head_hash))), $ max_miner_id is the sequence number of the last registered miner, prev_head_hash is the previous hash from user_id, block_id, prev_head_hash.

Thus, it is impossible to make the blocks sign some definite miners, since There is no value that can be manipulated to change the hash (based on which the miners are distributed by levels). Due to this, the described variant of blockchain formation can be used in practice.