Generating Random Numbers

Overview

Random numbers are essential for many applications, including games, simulations, and secure systems. Generating random numbers in a zkWasm Rollup Application is a bit different from generating random numbers in a traditional Web2 application, it follows an interactive approach to ensure the randomness of the numbers is secure and verifiable. We will use the autocombat Game as an example to demonstrate how to generate random numbers in a zkWasm Rollup Application.

Game: autocombat

autocombat is a PVE game where players can bet on the outcome of battles between themselves and the enemy (which is controlled by the server admin). And the outcome of a battle is determined by a random number. There are several stages to generate the random number and can be summarized as follows:

Timetick 1:

Seed Commitment: The admin generates a random seed and commits to it by storing its hash, commitment = hash(seed), in the game state.

Timetick 2:

Player Signature: The player signs their bet transaction, and their signature is used to generate a random component (SR).
Seed Revelation: The admin reveals the seed by submitting it to the server.
Verification: The server verifies that the revealed seed is correct by checking that hash(seed) = commitment.
Random Number Generation: Then, a random number for the player is generated using the formula seed xor SR. This random number will be used in the next battle.

Remind that timetick is a kind of transaction that generates by the server which can be used to manage or trigger time-related operations and events.

Interaction Details

Let's examine the details of how random numbers are generated by walking through several rounds of game interactions.

First Round, First Timetick (Server Initialization and Commitment Record)

Server starts timetick without any player bets.

In zkwasm ts server, when a timetick transaction is generated, generateRandomSeed() generates a randseed and returns its 64-bit SHA256 commitment, you can refer to the code to see how it works. And specifically, in generateRandomSeed():

function randByte() {
    return Math.floor(Math.random() * 0xff); // generate a random byte between 0 and 255, this is because the randseed is a 64-bit array of bytes
}
async function generateRandomSeed() {
    let randSeed = [randByte(), randByte(), randByte(), randByte(), randByte(), randByte(), randByte(), randByte()]; // generate a 64-bit randseed
    let sha = sha256(new Uint8Array(randSeed)); // hash the randseed
    const mask64 = BigInt("0xFFFFFFFFFFFFFFFF"); // generate a 64-bit mask
    const shaCommitment = BigInt(sha) & mask64; // mask the sha to 64-bit
    const randRecord = new modelRand({
        commitment: shaCommitment.toString(),
        seed: randSeed,
    });  // create a new rand record
    await randRecord.save(); // save the rand record to the database
    return shaCommitment; // return the commitment
}

The commitment and rand seed are stored in the database and the commitment is returned to the server.

Then, application.randSeed() returns 0 (which is the initial value) and assign it to oldSeed. And we assign the 0 to seed:
```
const oldSeed = application.randSeed(); // get the old seed
const seed = 0n; // assign the seed to 0n
```
Because the oldSeed is 0, we don't need to retrive the rand generated in the previous round (because there is no previous round) so we skip the following code:
```
if (oldSeed != 0n) {
    ...
} // This is skipped
```

Then, the server signs [0n, seed, rand, 0n] and sends it to the application, the first 0n is the command which indicates timetick, the seed is the oldSeed, the rand is the new commitment, the last 0n just indicates empty:

let signature = sign(new BigUint64Array([0n, seed, rand, 0n]), SERVER_PRI_KEY);
let u64array = signature_to_u64array(signature);
application.handle_tx(u64array);

In sign, we use the server's private key to sign the transaction:

export function sign(cmd: BigUint64Array, prikey: string) {
    let pkey = PrivateKey.fromString(prikey);
    ...
    let H = cmd[0] + (cmd[1] << 64n) + (cmd[2] << 128n) + (cmd[3] << 192n); // convert the command array to a single big number
    let hbn = new BN(H.toString(10)); // convert the bigint to a BN
    let S = r.add(pkey.key.mul(new CurveField(hbn))); // sign the command
    ...
    const data = {
        msg: bnToHexLe(hbn), // convert the bigint to a hex string
        ...
        sigr: bnToHexLe(S.v), // convert the signature to a hex string
    };
    return data;
}

In signature_to_u64array, we convert the signature to a u64array:

function signature_to_u64array(value) {
    const msg = new LeHexBN(value.msg).toU64Array();
    ...
    const sigr = new LeHexBN(value.sigr).toU64Array();
    let u64array = new BigUint64Array(24);
    u64array.set(msg);
    ...
    u64array.set(sigr, 20);
    return u64array;
}

And you can record that the msg is in the first 4 elements of the u64array, which is 0-3, and the sigr is in the last 4 elements of the u64array, which is 20-23.

And in handle_tx:

pub fn handle_tx(params: Vec<u64>) -> u32 {
    let user_address = [params[4], params[5], params[6], params[7]]; // get the user address
    let command = [params[0], params[1], params[2], params[3]]; // get the command and the parameters, here will be [0n, seed, rand, 0n]
    let sig_r = [params[20], params[21], params[22], params[23]]; // get the sig_r
    let transaction = $T::decode(command); // decode the command
    transaction.process(&user_address, &sig_r) // process the transaction
}
    ```
We can see that the command is `[0n, seed, rand, 0n]`, and the sig_r is the signature of the command. They are retrived through their positions in the u64array. Remind the Transaction struct is defined in `state.rs` as:
```rs
pub struct Transaction {
    pub command: u32,
    pub data: [u64; 3],
}

This matches the command [params[0], params[1], params[2], params[3]], as the command in Transaction is the first element of the u64array, and the data is the next 3 elements of the u64array. In Transaction implementation, we can call self.command and self.data to get the command and the data.

State updates rand_commitment to the new commitment

In process function of state.rs, we can see that the rand_commitment is updated to the new commitment in the Timetick transaction through state.rand_commitment = self.data[1];:

pub fn process(&self, pid: &[u64; 4], sigr: &[u64; 4]) -> u32 {
    if self.command == TIMETICK {
        let state = unsafe { &mut STATE };
        state.counter += 1;
        let rand = self.data[0]; // get the new commitment
        let mut hasher = HASHER.clone();
        hasher.update(rand.to_le_bytes()); // hash the new commitment
        let v = hasher.finalize(); // get the hash result
        let checkseed = u64::from_be_bytes(v[24..32].try_into().unwrap()); // get the checkseed
        if state.rand_commitment !=0 {
            unsafe { zkwasm_rust_sdk::require(state.rand_commitment == checkseed) };
        } // verify the rand, which is skipped here because the rand_commitment is 0 (initial value)
        state.rand_commitment = self.data[1]; // update the rand_commitment to the new commitment
        ...
    }
    ...

Now we set the rand_commitment to the new commitment, this is the foundation of the verification of the next round.

Application

You may notice that the server calls the application to get the states of the game through application.FUNCTION_NAME(). Typically, these functions are defined in the implementation of the state struct in the state.rs file of the application and actually, they are implementations of zkWasm Rest Server's ABI.

Second Round, Second Timetick (Commitment Verification and Random Number Generation)

Server executes another timetick, just like the first round.
Generates new randseed and commitment through let rand = await generateRandomSeed();, now the rand is the new commitment.
Retrieves previous rand_commitment:
```
let oldSeed = application.randSeed();
```

Retrieves previous randseed from database using the commitment as key:

if (oldSeed != 0n) {
    const randRecord = await modelRand.find({
        commitment: oldSeed.toString(),
    });
    seed = randRecord[0].seed.readBigInt64LE();
}

Signs [0n, previous_randseed, new_commitment, 0n] as the same way as the first round and send it to the application.

Verifies hash(previous_randseed) = previous_commitment:

In process function of state.rs, we can see that the previously generated randseed, which indicates by the rand, is verified through unsafe {zkwasm_rust_sdk::require(state.rand_commitment == checkseed)};:

pub fn process(&self, pid: &[u64; 4], sigr: &[u64; 4]) -> u32 {
    let state = unsafe { &mut STATE };
    state.counter += 1;
    let rand = self.data[0];
    let mut hasher = HASHER.clone();
    hasher.update(rand.to_le_bytes());
    let v = hasher.finalize();
    let checkseed = u64::from_be_bytes(v[24..32].try_into().unwrap()); // get the commitment of the previous randseed as the same way when the server generates the new commitment
    if state.rand_commitment !=0 {
        unsafe { zkwasm_rust_sdk::require(state.rand_commitment == checkseed) };
    } // verify the rand
    ...
}

Updates rand_commitment to new_commitment, this is for the next round's verification of randseed generated in this round:
```
state.rand_commitment = self.data[1]; // update the rand_commitment to the new commitment
```
Settles using previous_randseed, after the verification, the previously generated randseed is used to generate the random number for the player:
```
unsafe { STATE.settle(rand) };
```
In settle function, we can see that the random number is generated through let final_rand = game.rand ^ rand:
```
pub fn settle(&mut self, rand: u64) {
    for game in self.games.iter_mut() {
        let final_rand = game.rand ^ rand;
        game.settle(final_rand);
    }
    self.games = vec![];
}
```
8. You may notice that we haven't mentioned the game.rand appears in the settle function. This is the Player's random number generated from their signature. Let's see how it works.

Second Round (Player Interaction)

This is still the second round, but here we will see how the player's random number is generated.

Player can start to play the game by signing transaction data [command, bet, 0n, 0n] by calling place function of api.js:

 async place(bet) {
     let nonce = await this.getNonce();
     let processStamp = await this.rpc.sendTransaction(new BigUint64Array([createCommand(nonce, CMD_PLACE, 0n), bet, 0n, 0n]), this.processingKey);
 }

And in the process function of state.rs, we can see that the player's random number is generated through let rand = sigr[0] ^ sigr[1] ^ sigr[2] ^ sigr[3];:
```
 pub fn process(&self, pid: &[u64; 4], sigr: &[u64; 4]) -> u32 {
     if self.command == PLACE {
         let rand = sigr[0] ^ sigr[1] ^ sigr[2] ^ sigr[3];
         self.place(self.data[0], &pid, rand)
     }
     ...
 }
```
Remind that the sigr is the signature of the transaction data [command, bet, 0n, 0n]. Therefore, we got the player's random number generated from their signature.

Now we take a look at the place function of state.rs, we can see the rand is stored in the game record through let game = Game::new(&player, place, rand);:

 pub fn place(&self, place: u64, pkey: &[u64; 4], rand: u64) -> u32 {
     let mut player = CombatPlayer::get_from_pid(&CombatPlayer::pkey_to_pid(pkey));
     match player.as_mut() {
         None => ERROR_PLAYER_NOT_FOUND,
         Some(player) => {
             if player.data.placed != 0 {
                 return PLAYER_IN_GAME;
             } if player.data.power == 0 {
                 return PLAYER_IS_DEAD;
             } else {
                 let game = Game::new(&player, place, rand);
                 unsafe { STATE.new_game(game) };
                 player.data.placed = place;
                 player.store();
                 return 0
             }
         }
     }
 }

Now we can retrieve the player's random number from the game record through let player_rand = game.rand;. And this shall answer the question that how the player's random number is generated and how the final random number is generated in settle function:

pub fn settle(&mut self, rand: u64) {
    for game in self.games.iter_mut() {
        let final_rand = game.rand ^ rand;
        game.settle(final_rand);
    }
    self.games = vec![];
}

Understanding the Random Number Generation Mechanism

How Randomness is Achieved

The final random number is generated through XOR operation between two components:

The player's random number (derived from transaction signature)
The server admin's random number

This dual-source approach ensures true randomness through several security measures.

Server Admin's Random Number Security

While the admin knows their generated random number, they cannot manipulate it
Security is achieved through commitment mechanism:
- Admin must commit to the random number before revealing it
- Commitment (hash) is stored in the game state
- Later revelation must match the commitment
- Any attempt to change the number would be detected through hash verification

Player's Random Number Security

Players can calculate their own random number from their signature, but cannot predict the final random number since the server admin's random number is only revealed in the next timetick transaction.
The player's random number is maintained through:
- Transparent signature calculation process and can be verified.
- Cannot be altered after submission

Combined Randomness Through XOR

The XOR operation between these two sources creates unpredictability
Neither party can determine the final random number
Even if one party knows their random number component, they cannot predict or manipulate the outcome

Preventing Manipulation Through Timing (Timetick)

A critical aspect of the system is preventing manipulation through careful timing of operations:

Sequential Submission:
- Players submit their random number component (through place operation) before seeing the admin's random number.
- Admin's random number is only revealed in the next timetick
- This prevents players from choosing their random number based on known admin values
Settlement Timing:
- Settlement cannot occur in the same timetick (Server submits the commitment) as the player's place operation, this is because the server's random number is revealed in the next timetick.
- Must wait for next timetick when:
  - Admin reveals the previous commitment's random number
  - New commitment is created for future rounds

Round Structure:

Round N / Timetick N:
- Player submits their random component
- Admin commits to new random number

Round N+1 / Timetick N+1:
- Admin reveals previous round's random number
- Settlement occurs using XOR of:
  - Player's submitted random (from Round N)
  - Admin's revealed random (committed in Round N-1)