🤖Protocol

In this page, we're going to describe the process that allows a group of participants to generate the grand randomness of an epoch.

Orand is a trustless source of randomness. As a system application of Orochi Computation Layer, Orand can provide randomness for all distributed applications on Orochi Computation Layer and smart contracts on supported Layer-1 blockchains. We present the protocol in the sequences. Deliberate proofs for some properties on the cross-chain randomness of Orand such as counter-manipulation, open-sourced transparency, verifiability and high throughput will be published in recognized scientific venues. We have released Orand as an open source project. At this stage, Orand has already been implemented and under testing at https://github.com/orochi-network/orochimaru.

🤖 Protocol

Assuming there are $n$ participants (validators) denoted by $P_1, P_2, ... P_n$, each participant plays two roles in our system dealer and verifier. Each participant $P_i$ has their own key-pair $\{sk_i,pk_i\}$ and the public key $pk_i$ is available to all other participants.

Draw Phase

All participants $P_i$ will need to generate their secrets and also randomness by using Verifiable Random Function (VRF) with $x$ as the grand randomness of the previous epoch, we have $\{r_i,\pi_x\}=f_{sk_i}(x).$ In the genesis epoch, although the value $x_0$ is pseudo-random, the draw values from it $r_i$ are different because it depends on $sk_i$ from which many participants will contribute entropy to the value of $x$. And therefore hashing known public keys and then XOR them together is the fastest way to generate an initial seed for the network at the very beginning. In order words, $x$ can be generated by combining participants' hashes of public keys. Therefore, we have $x_0$ at the genesis epoch computed as follows

$$x_0=H(pk_1) \oplus H(pk_2) \oplus ... \oplus H(pk_n).$$

Split Phase

The participant $P_i$ (also known as the dealer $D_i$) will split their $r_i$ into shares $\{s_{i1}, s_{i2},...,s_{in}\}$. So in this phase we want to use a Public Verifiable Secret Sharing (PVSS) scheme to split the $r_i$ value into many shares so that at the same time it also generates $Proofs$ besides the shares $\{s_{i1}, s_{i2},.. this .,s_{in}\}$. This process aims to prepare for the shares to be distributed while ensuring that only the receiver gets the secret while all participants can verify that the shares have been transmitted. We want to use a mechanism to create a temporary black box and protect all shares and the secret value $x$. We propose to use Stadler's PVSS scheme in our protocol for this purpose.

All other participants need $t$ shares to reconstruct $r_i$, $0 \leq t \leq n$. In our protocol we choose $\frac{n}{2} < t < \frac{3n}{4}$. Then each participant can forge their message $M_{s_{ij}}$ corresponding to the share $s_{ij}$ and distribute to other participants (also known as verifier $V_i$) by

$$M*{ij}=E*{ij}(s*{ij}){+\!\!\!\!+\,}Proof*{P_i}.$$

Gossip Phase

To prevent the participant $P_i$ to deal all of their shares to the colluding party, we require all participants to draw distribution parameter $q_i$ by using VRF. Each epoch will have different $q_i$, with

$$\{q_i,\pi_{H(x)}\} = f_{sk_i}(H(x)).$$

We assume that the node id of participants is the digest of their public key

$$N_i=H(pk_i).$$

Moreover, if the share distribution $Q_{ij}$ of $s_{ij}$ is as follows

$$Q_{ij} = H(q_i{+\!\!\!\!+\,}j).$$

Then, after creating the $Q_{ij}s$, we want to distribute them to the ``nearby subset of participants'' (its neighbors) to avoid the fact that a participant can gossip all about its colluding party. Since our process is gossip-based and recorded on a gossip graph, in general, any cheat should be detected. So we adopt the XOR metric introduced in Kademlia Protocol for that purpose by setting $d_{ij}(N_i)=N_i \oplus Q_{ij}$ to be the distance between node id and share distribution. We will distribute the share corresponding $s_{ij}$ to the node which has the closest node id to $Q_{ij}$. By performing this method repeatedly, we can multi-cast the shares to all nodes in the network randomly. This process is transparent and verifiable for all participants.

Audit Phase

According to the gossip process, a given participant can reconstruct the current state of the Gossip Graph. They can perform virtual voting and find dishonest participants. The gossip process will grow the knowledge of all participants and guarantee that the share of randomness will increase over time for each participant.

If there are some dishonest participants based on the current state of all nodes, anyone can ask dishonest participants to commit the missing shares. If the share is not committed after the audit phase, the dishonest participants will be imposed with penalty.

Conclusion Phase

There are two following scenarios:

• Happy ending: All participants $P_i$ commit all their shares, then any of them could reconstruct $\{r_1, r_2,...,r_i\}$ and the grand randomness by using this simple method $R = r_1 \oplus r_2 \oplus ... \oplus r_i.$ The last process is that all participants must agree to use threshold signing and multi-party computation to commit the result to the blockchain.
• Unhappy ending: If there are insufficient shares to reconstruct randomness by any participants, all participants will lose their collateral.