Random Producer Selection for the Catalyst Network

Randomness or thereby lack of in computer science is a major point in the design of many systems. Highly random PRNG’s are utilised in many cryptographic schemes as well as in many other systems. However, when they go wrong critical flaws in software and security can occur.

One of the most infamous examples of a failure due to this is the case of Sony where the “randomness” of the randomly generated numbers for the elliptic curve cryptography used in the generation of public/private key pairs was not random enough. This meant that the private key for users could be recovered.

Furthermore, there is the case of NIST allegedly inserting back doors into the PRNG’s used for generating certain elliptic curves. [1]

When setting out to design Catalyst, we designed a new type of consensus we call Probabilistic Byzantine Fault Tolerant. You can read more about Catalyst and our consensus mechanism in our “What is Catalyst” blockchain live developer den video https://www.youtube.com/watch?v=lnG3vvZMSSU

The idea was to solve the blockchain trilemma of security, decentralisation and scalability. In order to achieve this, the consensus had to deterministically choose random nodes from the network to validate for given cycles. But implementing true randomness that is deterministic across the network and can not be gamed is a whole other set of challenges.

Random producer selection is a key element of the security of the network. An assailant who could predict an efficient method for gaining entry to the producer pool (the nodes performing the work for a given cycle) could potentially mount a 51% attack against the network without a user needing more than 50% of the network power (or in Catalysts case population of the network). This is due to that malicious actor being able to create an unrepresentative bias towards their population of nodes when going through the producer selection process. This leads to the question of how can you select a group of peers from a network at random without any members being able to game the system. Other requirements are that there is minimal communication, and the process is non-interactive.

NB: Producers are the equivalent to miners on the Catalyst network. Workers are nodes that demonstrate their wish to work by going through the selection process discussed here. More can read about the Catalyst network here and here.

This led us to research on RANDAO [2]. RANDAO is a DAO (decentralised autonomous organisation) that anyone can participate in, and the random number is generated by all participants together [3]. The process of which is relatively simple. In a group of peers, each one thinks of a number, then declares the number. These numbers are summed to create a global random number from which you can perform checks to see for example who was closest to that number.

From this idea of mass input into the generation of a random number, we can develop a weighting system where the nodes who are randomly generated number is closest to the global random number are selected to become producers and perform work for the ledger for a cycle(s). The producers send their random numbers to the global state of the ledger. The global state will be able to generate a global random number and determine the nodes selected.

This gives us the following scheme:

• Each node n in the worker pool N generates a random number r.
• To this random number the hash of the previous ledger state, D, must be added.
• n then creates a hash of the combined random number H(r+D).
• Each n must then send their value r to the global state.
• If they do not send their r value they are not eligible to become a producer node.
• Each n in N sends their H(r + D) to the global state. This creates the global random value R. This is done through the addition of all the random numbers.
• The global state must determine:

1. Whether n did submit all correct information. i.e. r, and H(r +D).
2. That n did, in fact, use the D value when generating the random number. This is done by taking the r value submitted by the user and hashing with D.
3. Ensuring n has paid a sufficient stake to take part in the selection process.
4. Validating that each worker n has only distributed one random number to the smart contract.

• Failure of any one of these points means the submission of a random number from n will not be accepted and any stake made will be lost.
• This global random number can be used to determine the producers for the next cycle(s).
• This is done by determining the nodes that have a H(r + D) closest to the R value.

Following these steps a random number can be generated from a pool of nodes. This method provides a number with high randomness due to the nature of hashing functions, because it is by any currently known algorithms impossible to predict the digest of a hashing function from a given input on well-implemented hashing functions. This means that no matter what the random value selected by a node they will not be able to predict the output.

To demonstrate this random selection a proof of concept can be found here, along with a short paper further detailing the selection mechanism. Further, research around Catalyst can be found here.

Joseph Kearney is a Blockchain and DLT Specialist at Atlas City who are the creators of the Catalyst Network. He holds an MSc in Computer Science from the University of Kent.

This article has been edited by NshCore and sourced by all the team members of Catalyst Network. Follow us @nshcore @Joseph_Kearney @catalystnetorg on twittsr

[1] K. Zetter, ”How a Crypto ‘Backdoor’ Pitted the Tech World Against the NSA” https://www.wired.com/2013/09/nsa-backdoor/ 24/09/2013

[2] B. Skvorc, “Two point oh: Randomness.” https://our.status.im/two-point-oh-randomness/ 07/05/2019.

[3] randao, “randao.” https://github.com/randao/randao/ 26/03/2019.