6.5 Distributed Random Number Generator

6.5.1 Introduction

The module presented in this specification allows for the distributed generation of randomness for the post-Coordicide IOTA network. The distributed random number generator (dRNG) protocol is divided into three phases:

1. COMMITTEE SELECTION: In the first phase, a committee of high Consensus Mana nodes is selected. The procedure is objective i.e., all of the nodes in the network reach a consensus on which nodes should be in the committee. In order for a node to be considered as a candidate to the committee, it needs to declare its willingness to participate, with a special application message. When all of the required application messages are recorded in the Tangle, the committeeNodes top consensus Mana holders among the candidates are selected as the committee. In the case where some of the required messages fail to be produced, the committee selection will consequently fail as well.

2. DKG PHASE: In the second setup phase, the committee members create a collective private key which will be used later to generate the random number, using the $(t,n)$ Distributed Key Generation (DKG), that does not rely on centralized, trusted third parties. The participation of the nodes in this phase can be publicly verified since the messages exchange takes place in the Tangle.

3. PUBLICATION PHASE: This last phase consists of the periodical publication of the beacon messages in the Tangle. A single individual beacon message should not be sufficient to reveal the random number; instead, the beacon messages from at least $t$ out of $n$ committee members are needed for the next random number being revealed. Additionally, the committee members publish a collective beacon message, which would contain the random number.

A large part of the procedures in this specification is based on the article Committee selection in DAG distributed ledgers and applications, where authors discuss multiple methods of the committee selection and applications.

6.5.2 Dependencies

The dRNG module depends on the Section 5.3 - Mana since it uses the Consensus Mana (cMana) vector as a measure of trustworthiness. Specifically, it uses the list of the top cMana holders to select a committee to produce the random numbers. During the committee selection, we do not assume a perfect agreement on the cMana values, i.e., different nodes can have slightly different perceptions of the cMana values of other nodes (due to the different local clocks). Obtaining consensus on the cMana values is the central part of this documentation.

The random numbers produced by dRNG are used in Section 6.3 - Fast Probabilistic Consensus.

6.5.3 Parameters

Table 6.5.1 dRNG parameters

Name	Type	Description	Value
rnPeriod	duration	Random number is produced everyrnPeriod seconds	20 [sec]
committeeNodes	integer	Number of nodes in the committee	10 [nodes]
committeeSeats	integer	The number of identities (seats) in the top Mana holders committee equals committeeSeats. It is different from committeeNodes because some of the nodes receive double seats in the committee.	15 [seats]
sigThreshold	integer	Signature threshold parameter (number of beacon messages needed to obtain randomness)	8 [messages] ([seats])
committeeUpdate	duration	Period of committee update	1 [day] = 86400 [sec]
applicationWindow	duration	Time window of the ''application'' message submission	120 [sec]
TIMESTAMP_CUTOFF	duration	Message timestamp cutoff (Assuming the node is in sync, the time after which point the node will receive no new messages with a particular timestamp which will be finalized)	2DLARGE +W= 90[sec]

For more information on the TIMESTAMP_CUTOFF see section Section 4.2 - Timestamps

6.5.4 Committee Selection

To select the committee based on the cMana, we need to achieve consensus on these values. To solve this problem, we use epochs a reference point which can be used to calculate the cMana values in an objective manner.

The willingness to participate in the committee is announced with a special application message, which like any other transactions in the Tangle are equipped with timestamps. Since the nodes following the protocol judge and invalidate messages which timestamps are too off, we can assume that the application messages can reliably give us a list of nodes interested in joining the committee.

The committee selection process starts at the time $t_S$ and should be done (assuming no problems occur) at the time $t_F$. The time $t_F$ is determined by the committee update time, $t_S$ depends also on the applicationWindow and TIMESTAMP_CUTOFF.

Only nodes that are in synch with the network should participate in the committee selection. If a node is out of synch (SyncStatus = FALSE) it should skip this committee selection.

6.5.4.1 Application Messages

Any node can issue an application message. Such a message would be processed by the nodes (assuming it passes the congestion control, along with other checks). However, for a low mana node, there is no incentive to apply for the committee, as the probability of being selected is very low; hence, they can decide to not take part in sending application messages. Although it is allowed, sending multiple application messages is pointless and costly due to the congestion control mechanism.

For brevity denote TIMESTAMP_CUTOFF by $\Delta_C$ and applicationWindow by $\Delta_A$. Assume that a committee should be formed at the time $t_F$ (which is known to all interested nodes; it is defined on the protocol level). Assume further that the time $t_F$ is in the epoch $E$ i.e., $t_F$ $\in$ $[t_{E-1}$,$t_E]$. Then the active consensus Mana vector from the time $t_{E-2}$ is calculated, which is the balance from two epochs before $t_F$. The committee selection process starts with the opening of the application message window at the time $t_S$, where $t_S$ = $t_F$-$\Delta_A$ -2$\Delta_C$. For as long as the application window is open, nodes can issue application messages. See the subsection "6.5.3.1 Application message sending - default algorithm" for the proposed algorithm of issuing application messages (which is not enforceable).

6.5.4.2 Application Message Sending - Default Algorithm

A node is said to be $M_\ell$ if its consensus Mana rank is less or equal to $\ell$ (node is among $\ell$ top Mana nodes). Computation of node's Mana rank is taking place with respect to the time from two epochs ago i.e., with respect to $t_{E-2}$ under the assumption that $t_S \in [t_{E-1},t_E]$.

For brevity denote committeeNodes by $m$. If an interested node $x$ is $M_{2m}$ then it issues an application at the time $t_S$. Notice that, in general, not all of the $2m$ application messages will be sent (due to for example nodes going offline or malfunction). If less than $m$ strongly valid application messages are sent at $T_S$, the nodes that are $M_{3m}$ (but not $M_{2m}$) issue their application messages at the time $T_S- \Delta_A \frac{1}{2}$ and so on. In general, for $k>2$, if a node $x$ which is $M_{m k}$ but not $M_{m (k-1)}$, it submits a committee application whenever before the time $T_S- \Delta_A \frac{k-2}{k-1}$ there are less than $m$ strongly valid application messages with cMana greater than the cMana of node $x$.

See subsection 6.5.9 Pseudocodes for the pseudocodes of the default application message sending procedure.

If at least $m$ of the nodes sent an application message within the time interval, the committee is formed from the top $m$ Mana nodes who applied. Due to the network delay, this can be confirmed only at the time $t_S+\Delta_A+\Delta_C$.

If less than $m$ nodes send application messages, then the committee selection will fail. This is confirmed at the time $t_S+\Delta_A+\Delta_C$. In this case, the procedure should be repeated immediately, with new starting time $t'_S$ and finish time $t'_F$ such $t'_S =t_S+\Delta_A+\Delta_C$ and $t'_F=t_F+\Delta_A+\Delta_C$.

6.5.5 DKG phase

After a successful committee selection, confirmed at the time $t_S+\Delta_C+\Delta_A$ with respect to the node's local clock, the DKG phase starts. In this phase, the committee nodes exchange the Deal messages to produce a public/private collective key. There is no time window for the DKG phase and nodes should proceed with the corresponding DKG message exchange as soon as the committee selection is confirmed (time $t_S+\Delta_C+\Delta_A$). Only DKG messages with this timestamp are accepted.

If any of the committee nodes refuse to create a collective key pair by not exchanging the Deal DKG messages, the DKG phase fails. This can be confirmed at the time $t_F= t_S+2\Delta_C+\Delta_A$. Moreover, since the message exchange occurs on the Tangle, everybody can identify the nodes that caused the failure. In the case of DKG phase failure, the entire committee selection is repeated (including the application phase). New start and finish time are $t'_S = t_F= t_S+2\Delta_C+\Delta_A$ and $t'_F= t_F+2\Delta_C+\Delta_A$. The malicious node is then excluded from the new committee selection - all application messages issued by a malicious node are ignored. Ban on the committee application is lifted after a successful committee selection i.e., the committee produces its first beacon messages. In other words, if a node failed to produce a DKG message (either due to malfunction or maliciousness) it cannot apply to be in the current committee, however, it can apply in the next committee selection process.

6.5.6 Double Seats

We can increase the security of the dRNG beacon by granting double seats to half of the committee members that have the highest committee Mana. Those nodes would receive two private keys (identities) with which they sign beacon messages in the Tangle. From the technical point of view, the two seats are completely separate, and issued Beacon messages can not be combined (even though they were signed by the same node). This modification increases the amount of Mana required to "overtake" the committee, which is understood as gaining sigThreshold of seats in the committee.

The number of nodes in the committee with double seats equals $\lfloor m/2 \rfloor$ (top half of the committee nodes). The total number of identities in the committee equals $m + \lfloor m/2 \rfloor$.

6.5.7 Publication of the Random Number

The committee will collectively generate a random number based on the set of beacon messages that each node will individually produce. A single beacon message is not sufficient to reveal the random number; instead, sigThreshold or more beacon messages are needed for the next random number to be revealed.

6.5.7.1 Collective Beacon Message

To recover the random number from the individual beacon messages, all nodes in the network would need to perform Lagrange interpolation. To avoid that, we propose that the committee nodes produce a collective beacon message, which contains a pre-computed random number (meaning that the committee nodes perform the Lagrange interpolation on their own). Since the committee size is small and the expected throughput of the network is large, we require all committee members to produce this collective beacon message as soon as they receive sigThreshold individual beacon messages.

The cost of getting randomness from the collective beacon would be reduced as only (additionally to the default message checks) the signature verification would be required.

6.5.8 Duties of the Old Committee

An old committee should only stop producing randomness if another committee was successfully selected and started producing random numbers, which will be confirmed when the first collective beacon message is produced by the new committee and can be read directly from the Tangle.

6.5.9 Alternative Drng and Backup Options

To increase the liveness of the random number production multiple dRNGs may be deployed. Secondary dRNGs can be used if the primary one is not available; it is also possible that users alternate between random numbers from multiple dRNGs.

However, this discussion is out of the scope of this specification document.

6.5.10 Pseudocodes

Actions after receiving incoming transaction which is an application message:

IF (NOT IsBlacklisted(IssuingNode(tx)))
   IF (Mana(IssuingNode(tx),E-2) > Mana(My_node,E-2))
      numberValidApplicationMessagesWithManaHigherThanMine ++

Actions of a node interested in committee participation:

IF (thisNodeWantsToParticipateInDRNG)
   WaitUntil (tS)
        ell = GetManaRank(myNode,Epoch-2)
        ApplicationMessageSend(ell)

FUNCTION ApplicationMessageSend(ell)
    IF (ell <= 2m)
        SendApplicationMessage()
    ELSE
        WaitUntil(T_S- applicationWindow *[1-(floor(ell/m)-2)/(floor(ell/m)-1)])
        IF (numberValidApplicationMessagesWithManaHigherThanMine < m)
            SendApplicationMessage()

6.5.11 Payload Layout

DRNG payload layout is discussed in Section 2.3 - Standard Payloads Layout.