Randomness

Randomization is an important feature in blockchain. The application of randomization results, such as generated random numbers, can be achieved similarly to, e.g., the election of block nodes, while trusted random numbers can provide support for numerous DApps, such as lotto, games, etc.

In many other chains, the implementation of trusted random number generation requires the use of off-chain random number generation services, such as Ethereum, which requires off-chain beacons such as Chainlink or drand to provide external randomness.

The disadvantages of relying on external beacons are that the randomness is too expensive or too slow to be generated for DApps that require higher speed random numbers; in addition, the external randomness must be sent to the contract through transactions, which complicates DApp development and user interaction.

Reliable Randomness

If a sequence is to be identified as random, it has to possess the following qualities:

• Unpredictable — The result must be unknowable ahead of time.

• Unbiased — Each outcome must be equally possible.

• Provable — The result must be independently verifiable.

• Tamper-proof — The process of generating randomness must be resistant to manipulation by any entity.

• Non-reproducible — The process of generating randomness cannot be reproduced unless the original sequence is preserved.

Weighted Threshold VUF Essentials

Here we discuss threshold VUF with an idealized key generation algorithm. The advantages of this approach, rather than immediately considering VUF keying using a DKG, is that it lets us focus on the VUF security and avoid any nuances due to the key generation phase.

An $(n, t)$ -threshold VUF scheme for a finite message space $\mathbb {M}$ is a tuple of polynomial time computable algorithms $\sum=(KeyGen, ShareSign, ShareVerify, Verify, Aggregate)$ with the following properties:

1. Setup$(1^{k}, n, w, t) \to pp$.

   $pp$ (public parameter) consists of a generator $h \in \mathbb{G}$ and a random generator $H:\{0, 1\}^{*} \to \mathbb{G}$. Let $w = [w_{1},\cdots,w_{n}]$ be the weights of the participants, $\mathbb{W} := \sum_{i \in [n]}{w_{i}}$ be the total weights, and $t$ be the threshold.

2. KeyGen$(pp) \to sk$, $\{vk_{i}\}_{i \in [n]}$, $\{sk_{i}\}_{i \in [n]}$.

   The key generation algorithm takes the public parameters then outputs:

   • a secret key $sk := h^{a}$, where $a$ is a random number in group $\mathbb{G}$

   • a vector of secret signing keys $\{sk_1, \ldots, sk_n\}$, using $H:\{0, 1\}^{*} \to \mathbb{G}$.

   • $(a_{j})_{j \in [W]}$ is derived from ShamirShare($a, t, W$)

   • a vector of verification keys $\{vk_1, \cdots, vk_n\}$, where $vk_{i} := (h^{r_{i}}, \cdots ,h^{r_{i}a_{s_{i}+w_{i}}})$

   • a vector of public keys equal to verification keys, i.e., $pk_{i} := vk_{i}, i \in [n]$.

   The public key size of a party in our weighted VUF is proportional to its weight, i.e., the public key $vk_{i}$ of party $i$ contains $w_{i} + 1$ group elements.

3. ShareSign$(m,sk_{i}) → \sigma_{i}$.

   The partial signing algorithm is a possibly randomized algorithm that takes as input a message $m$ and a secret key share $sk_i$. It generates a signature share $\sigma_{i}$.

4. ShareVerify$(m, σ_i, vk_i) \to 0/1$.

   The signature share verification function is a deterministic algorithm that takes as input a message $m$, a public key share $vk_i$, and a signature share $\sigma_i$. It outputs 1 (accept) or 0 (reject).

   The function asserts $e(h^{r_{i}}, \sigma_{i}) \stackrel{?}{=} e(h, H(m))$

5. $Aggregate(S, {(σ_i, i)}_{i \in S}) → σ/⊥$.

   The signature share combining algorithm takes as input the public key $pk$, a vector of public key shares $(pk_1, \cdots, pk_n)$, a message $m$, and a set $S$ of $t + 1$ signature shares $(\sigma_i, i)$ (with corresponding indices). It outputs either a signature $\sigma$ or ⊥.

6. Derive$(m, vk, \sigma) → \rho$.

   The output derivation algorithm is a deterministic algorithm that takes as input a public key $pk$, a message $m$, and a signature $\sigma$, and outputs the VUF output $ho$ and the proof $\pi$.

7. Verify$(m, pk, \rho, \pi), pk :={vk}_{i}, i \in [n]$.

   The signature verification algorithm is a deterministic algorithm that takes as input a public key $pk$, a message $m$, and a VUF output $ho$ and proof $\pi$.

   • verify $\pi \stackrel{?}{=} (S, {\sigma_{i}}_{i \in S})$

   • run Derive of Step 6: $Derive(S, \{\sigma_{i}, vk_{i}\}_{i \in S}, m) \to \rho'$

   • check if $ho == \rho'$, and outputs 1 (accept) or 0 (reject).

---

• Unpredictable depends on below:

  • $Aggregate(S, {(σ_i, i)}_{i \in S}) → σ$ outcomes aggregated signature, which is the income of VUF output. The procedure takes place in every block's 1st transaction (Block Metadata transaction), which means not any User or Validator could predict randomness in User Transaction of the current block.

• Provable depends on below:

  • $Pr[$ShareVerify$(m, ShareSign(m,sk_i), pk_i)$ = 1] = 1$$

  • $Pr[$Verify(m, Aggregate$(\{(\sigma_{i}, i)\}_{i \in S}), pk) = 1 : \sigma_i = ShareSign(m,sk_i) ∀i \in S] = 1 − negl(λ)$

• Tamper-proof depends on below:

  • $Pr[ShareVerify(m, σ_i, pk_i) = 1] = 1$

  • $Pr[Verify(m, pk, \sigma) = 1] = 1$

• Unbiased depends on below:

  • VUF output $ho$ is unbiased if

    • derivation algorithm is unbiased

    • input$(m, pk, \sigma)$ is unbiased, e.g., use hash56(m) as input in the derivation function.

PVSS Process

Endless PVSS procedure, described as below:

1. Public Parameter Setup

   • define groups $G$ and $\hat{G}$, generator $g$, $h$ in group $G$ and $\hat g$ in group $\hat{G}$; $n$ as numbers of validators, threshold $t$

   • denote pp (public parameter) = $(g, h, \hat{g}, n, t)$, the following functions will take pp as default input parameter.

2. PVSS $KeyGen(i) \to (dk_{i}, ek_{i})$

   • the key generation protocol generates decryption key $dk_{i}$, and the corresponding encryption key $ek_{i}$

   • validator_{i}, indexed by $i, i \in n$ privately keeps $dk_{i}$, and publishes $ek_{i}$

   • denote $ek = [ek_i]_{i \in n}$

3. PVSS $Share(ek, s) \to trx$

   • leader node takes $s$ (secret) as input and generates secret shares $s_1, s_2, \cdots, s_n$

   • leader node encrypts $s_i$ share with encryption key $ek_{i}$, outputs encrypted $c_{i}$ and proof $\pi_{i}$

   • leader node generates commitment $com$ for secret shares $\{s_{i}\}, i \in n$

   • leader node commits transaction trx, taking ($com, \{c_{i}, \pi_{i}\}$) as PVSS transcript

   • commit transaction actually is $\{trx_{1}, trx_{2}, \cdots, trx_{i}\}$, Step. 5 will aggregate these separate $trx_{i}$ into one trx

4. PVSS Verify$(ek, trx) \to true/false$

   • assert $(com, c_{i}) \to true/false$

   • assert $(c_{i}, ek_{i}, \pi_{i}) \to true/false$

   check if $com$ is a commitment to valid shares of some secret $s$ and the $c_{i}$ values consist of encryptions of valid shares of the same secret

5. PVSS Agg$(trx_{1}, trx_{2}) \to trx$

   • public function Aggregate that anyone can use to aggregate two PVSS transcripts into a single transcript.

   • repeat to call Agg() to aggregate all $trx_{i}$ into one trx, to save nodes broadcast effort, also save space.

6. PVSS DecShare$(trx, i, dk_{i}) \to s_{i}$

   • take as input aggregated PVSS transcript trx, index $i$, i-th decryption key $dk_{i}$, outputs $c_{i}$

7. PVSS Recon$(ek, trx, c_{i}, \{dk_{i}\}_{i \in S}) \to s$

   • each validator node decrypts $c_{i}$ with owned $dk_{i}$ to get its share $s_{i}$, and publishes $s_{i}$ with corresponding NIZK proof $z_{i}$

   • anyone could verify $s_{i}$ with proof $z_{i}$, and if shares collected combined weight greater than threshold $t$, the original secret $s$ could be recovered.

---

The Endless chain has built-in provision for trusted random number generation, which can better enhance the security of services based on this type of service. At the implementation level, Endless utilizes the Weighted Publicly Verifiable Secret Sharing (wPVSS) algorithm, which can be run efficiently by each verifying node and which is aggregatable to help reduce communication overhead. Meanwhile, there is a communication-efficient aggregatable weighted distributed key generation (wDKG) generation protocol on Endless. Finally, Endless has a novel Weighted Verifiable Random Function (wVRF), which the verifying node evaluates each round, with a constant amount of communication per verifying node, rather than a linear relationship with the amount pledged by the verifier.

API Usage

Endless framework module randomness.move provide a series of function randomness APIs:

• randomness::u8_integer() returns a u8 random number, evenly samples an 8-bit from Endless Randomness

• randomness::u16_integer()

• ...

• randomness::u8_range(min_incl: u8, max_excl: u8) returns a u8 random number with specified minimal and maximum bound

• ...

• randomness::u256_range(min_incl: u256, max_excl: u256)

By repeatedly calling these functions, multiple objects can be safely sampled to generate multiple "unbiased" random numbers.

Demonstration

Endless Roll

Here we build a lottery system and pick a random winner from n participants. In the centralized world with a trusted server, the roll algorithm is the backend simply calls a random integer sampling function (random.randint(0, n-1) in Python, or Math.floor(Math.random() * n) in JS).

In Endless chain, we build a lottery move module:

module module_owner::lottery {
    // ...
 
    struct LotteryState {
        players: vector<address>,
        winner_idx: std::option::Option<u64>,
    }
 
    fun load_lottery_state_mut(): &mut Lottery {
        // authentication check 
        // return global borrow_mut LotteryState
        // ...
    }
 
    #[randomness]
    entry fun decide_winner() {
        let lottery_state = load_lottery_state_mut();
        let n = vector::length(&lottery_state.players);
        let winner_idx = endless_framework::randomness::u64_range(0, n);
        lottery_state.winner_idx = std::option::some(winner_idx);
    }
}

• let winner_idx = endless_framework::randomness::u64_range(0, n); is the randomness API call that returns a u64 integer in range [0, n) uniformly at random.

• #[randomness] enables the move compiler to check the outermost of the call stack of decide_winner is private.

Functions using randomness should be defined with private, to avoid Test and Abort attacks. decide_winner is an entry function, instead of public entry.

Security Considerations

Test and Abort Attack

If decide_winner() were accidentally marked public, malicious players can deploy their own contract to:

1. call decide_winner();

2. read the lottery result (assuming the lottery module has some getter functions for the result);

3. abort if the result is not in their favor. By repeatedly calling their own contract until a txn succeeds, malicious users can bias the uniform distribution of the winner (dApp developer’s initial design).

Under Gas Attack

Users should also put prevention of Undergassed Attack into security considerations when writing business logic.

Imagine such a dApp. It defines a private entry function for a user to:

1. toss a coin (gas cost: 9), then

2. get a reward (gas cost: 10) if coin=1, or do some cleanup (gas cost: 100) otherwise.

A malicious user can control its account balance, so it covers at most 108 gas units (or set transaction parameter max_gas=108), and the cleanup branch (total gas cost: 110) will always abort with an out-of-gas error. The user then repeatedly calls the entry function until it gets the reward.

Here are some ideas of how to prevent undergassing attacks generally:

• Make your entry function gas independent from the randomness outcome. The simplest example is to not “act” on the randomness outcome, i.e., read it and store it for later. Note that calling any other functions can have variable gas costs. For example, when calling randomness to decide which player should win, and then depositing the winnings to the winner might seem like a fixed gas cost. But, 0x1::coin::transfer / 0x1::fungible_asset::transfer can have a variable cost based on the user’s on-chain state.

• If your dApp involves a trusted admin/admin group, only allow the trusted to execute randomness transactions (i.e., require an admin signer).

• Make the path that is most beneficial have the highest gas (as the attacker can only abort paths with gas above a threshold he chooses). NOTE: that this can be tricky to get right, and the gas schedule can change, and is even harder to get right when there are more than 2 possible outcomes.

Random, but not a secret

Please keep in mind that random returned from calling the randomness API is randomness, but not a secret. The original seed in each block lies in 0x1::randomness::PerBlockRandomness which is public on the Endless chain.

Users should not try to do the following:

• Use the randomness API to generate an asymmetric key pair, discard the private key, then think the public key is safe.

• Use the randomness API to shuffle some opened cards, veil them, and think no one knows the permutation.