...by Daniel Szego
quote
"Simplicity is the ultimate sophistication."
Leonardo da Vinci

Wednesday, December 12, 2018

Pseudorandomly choosing the next leader at delegated proof of stake


Cryptographic secure random number generation is one of the biggest challenge for every blockchain protocol. It can be extremely important at different Nakamoto consensus or similar algorithms, because the next leader should be chosen with a cryptographically secure pseudorandom generator, otherwise denial of service attack can be easily carried out against the leader. At a delegated proof of stake system, however such an algorithm can be realized easily, and supposing that at least one node acts in an honest way producing real pseudorandom number, the result should be pseudorandom as well. The following algorithm sketch produces the required result:
- The actual leader node creates a private public key pairs and initiates a request for the delegate nodes producing a random number. This request also contains the public key that is actually related to the request. 
- The delegate nodes individually create a pseudorandom random number with some internal or hardware algorithm. These random numbers are encrypted by the public key of the request and spent back to the leader in an encrypted form. During this phase, the random information is encrypted, so practically, nobody can see or manipulate the exact random number. 
- The leader decrypts the with the help of the private key the random numbers and combines them into a final random number, like with the help of a similar algorithms: 

R1 XOR R2 XOR ... XOR Rn

or

sha256(... sha256(sha256(R1) XOR R2) ... XOR Rn)

at the end both the final random number and the private key is revealed in the blockchain, so everybody can proof if the choice algorithm was correct. 

If the random numbers are generated independently from each other and there is at least truly random number the result will be probably truly random as well. If the randomness of the numbers generated by the individual nodes can be checked, there can be a critpoeconomical incentive mechanism as well to reward or slash certain behaviors. 

There is one denial of service attack against the scheme though. If the leader does not reveal the information at the end of the round, like the random key or the random number at the end, a new leader should be chosen, however without the given pseudo-random number. This case requires further investigation.