Achieving consensus through crypto-random leader election

[16Nh8nPXUefq9GA1L1vJW5Yse]

Achieving consensus through crypto-random leader election
One of the main issues with the solution of the Byzantine Generals’ problem implemented by Satoshi Nakamoto as the very base of the crypto-currency Bitcoin, the Proof-of-Work mechanism, is the perpetual power race it implies. One cannot be satisfied by this solution, and should work around to find another way to achieve consensus which does not rely on massive resources waste.

Recently, in have been reading a bunch of articles exploring technical innovations in order to set up the basis of the next generation of crypto-currencies and I came up with the idea of a decentralized protocol that will choose one node to forge the next block based on the mathematical properties of signatures.

Basic concept
Each block will be forged by a random node picked in the subset of registered nodes.

Registration
Each node that is willing to take part of the forging process will have to register in the block chain so every other node can acknowledge that it is competing for the forging process. This can be achieved by numerous ways such as Proof of Stake or Proof of Burn.

The preferred solution must have the following properties:
•   The subset of nodes competing to forge block N + D is known when block N is accepted. Where N is the number of the block and D is the delay between registration and effectively entering the competition.
•   The registration must have a cost so that if the node is willingly submitting an invalid block, or not taking his turn, it will suffer severe losses.

I’ll give it a try and share my version of the registration protocol.
•   There is a special address where the registration fees must be sent, let’s call it Registry.
•   Node A send X coins to the Registry, where X is a fixed amount.
•   Node B forges the block N which includes the registration transaction.
•   Node A has now the proof that he can compete for the forging of block N + D.
•   Node A takes part of the competition until it forges a block or the registration lifetime is over.
•   Node A is awarded the X coins spent for registration when it has successfully submitted a block.
•   Node B is awarded the X coins spent by Node A as registration if Node A has not successfully submitted a block during the registration lifetime, as an incentive to accept all submitted registration.

Lifetime must be long enough so that it is unlikely that the Node never had chance to forge a block. This lifetime limitation must be designed to protect benevolent nodes from bad luck, and punish malevolent nodes for submitting invalid blocks.

Leader Election
The following protocol for randomly choosing a leader in a set of node is based on a paper called Fast Asynchronous Byzantine Agreement and Leader Election with Full Information which was about cooperation between processors. I made some changes to fit the introduction of cryptographic signatures.

The main idea is:
•   Each node generate a random number
•   The node with the greatest number is the chosen one

A malevolent node could listen to what other nodes are saying and say a greater word:
•   Each node has to prove this number is random

A malevolent node could try to generate random numbers until it finds the greatest one:
•   Each node has to prove the random number is unique

The question is why should the number be random? What are the properties we want for this number:
•   Each node has to prove he owns this number
•   Each node has to prove this number is unique
•   Each node has to prove this number was created before he knew the other nodes numbers
•   Each node has to prove that he did not chose this number

I am aware that my description is not really accurate, but what is really interesting comes next:
We can use the mathematical properties of cryptographic signature to ensure the number we generate has the required properties.

Example: Leader Election for Block 100
•   Each node sign the string “Block 100” with their private key and broadcast the result
•   The node with the greatest hash forge the Block number 100 and include the signed hash of ‘Block 100’ and broadcast it
•   The other nodes will integrate the block with the greatest hash in their blockchain

This leads to interesting properties:
•   Each node knows what their number will be for every Leader Election
•   Each node ignores what the other numbers will be
•   Nobody can predict which node will be chosen without knowing all the private keys of the competing nodes
•   Each node has equal probabilities to be chosen (in theory)

Disrupting the network
This solution will also avoid synchronization issues. Let’s say you have an election between 100 nodes, if every node waits for every numbers, the network will be slow and can be disrupted if one node doesn’t send its number. Same goes with forging the block, the network won’t wait for the chosen node to submit it. What will occur is that each node will broadcast their number, if they are in something like their known top 5, they will forge a block that will be accepted by the other nodes if they don’t receive blocks forged with a better number.

If you are the chosen one but you submit an invalid block, the second best block will be accepted if valid. If you are the one and don’t submit block, same result.

Block forging rate
Since there are no time consuming operations, the rate at which blocks must be forged should be fixed by the network.

Pitfalls
The fact that each node knows what their number will be for each block, means that they also know the probability to be the chosen one. So they can maximize the probability to be picked, and someone with high computing power could mine for high probability private for one given block and then try a double spending attack creating a side chain made with N consecutive chosen nodes. Wich implies adding a minor proof of work with number.

Sources

WHAT PROOF OF STAKE IS AND WHY IT MATTERS
by VITALIK BUTERIN on AUGUST 26, 2013
http://bitcoinmagazine.com/6528/what-proof-of-stake-is-and-why-it-matters/

PROOF OF BURN
Internet – Early 2012 ?
https://en.bitcoin.it/wiki/Proof_of_burn

FAST ASYNCHRONOUS BYZANTINE AGREEMENT AND LEADER ELECTION WITH FULL INFORMATION
Bruce Kapron ∗ David Kempe † Valerie King ‡ Jared Saia § Vishal Sanwalani – SODA 2008
http://webhome.cs.uvic.ca/~val/Publications/asynch07.pdf



Author : 16Nh8nPXUefq9GA1L1vJW5YsekWXnWPe1b

[1714092958]

1714092958

[1714092958]

1714092958

[1714092958]

1714092958

[jonald_fyookball]

Sounds similar to nxt

[benjyz]

Each node has to prove this number is random

this is impossible, unless you run trusted computing hardware. but I doubt using trusted computing hardware for cryptocurrencies will ever be a good idea.

actually Bitcoin is the first example of a perfect random generator, as the state is entirely public, but no single entity can effect it. if you take for instance the sha256 of tomorrow's Financial Times headline that would be close to random, but it can't be proven that nobody bribed the editor.

[16Nh8nPXUefq9GA1L1vJW5Yse]

Nxt Leader election protocol
•   Nodes willing to participate in the election must declare themselves as “active”
•   Based on the last block you get BASE_TARGET and GENERATION_SIGNATURE.
•   For each Active Node calculate SHA256 (GENERATION_SIGNATURE, PUBLIC_KEY) as HIT value.
•   For each Active Node calculate BASE_TARGET * ACCOUNT_BALANCE as STATIC_TARGET value.
•   Node with lowest HIT/STATIC_TARGET ratio will forge the next block.

Differences with Nxt
Nxt is proof of stake, so probability of being chosen will increase with the number of coin you hold. The randomness in Nxt comes from the signature of the last block. No action from the Active Nodes is needed to determine the node that will forge the next block. But I wonder what happens if the designed Node doesn’t take his turn. Does the entire network wait for him and after a while says “ok let’s skip this block and go to the next one”. But if they do, they don’t have a new block signature and if they take the old one, the same node will be elected. So they have to pick the second best ratio. To prevent this to slow the whole network, the 3 best ratios should submit a forged block and let the network integrate the good one in the blockchain. Same goes with the proposed protocol.

The Nxt protocol seems secure but I think there might be a pitfall in that the Node forging the block will know which Node will forge the next block and could mine, by integrating transaction with random message, to find a block signature that will make another compromised Node the chosen one.

Whereas in the proposed protocol, the other Nodes cannot predict who will be chosen, because they don’t know the private keys of all the Active Nodes. The protocol is designed to work without full information. None knows you are the chosen one until you broadcast your signed number, and if you don’t broadcast it, it will make no difference for them, you just have lost some money.

Sources

TRANSPARENT MINING, OR WHAT MAKES NXT A 2ND GENERATION CURRENCY
Come-from-Beyond - December 09, 2013
https://bitcointalk.org/index.php?topic=364218.0