Define state and state transitions of Random module

Implementation
1

Hello everyone,

Today I would like to propose a LIP for the roadmap objective “Define state model and state root”. This LIP specifies the random module.

Looking forward to your feedback!

Here is the LIP draft:

LIP: <LIP number>
Title: Define state and state transitions of Random module
Author: Iker Alustiza <iker@lightcurve.io>
        Ishan Tiwari <ishan.tiwari@lightcurve.io>
Type: Standards Track
Created: <YYYY-MM-DD>
Updated: <YYYY-MM-DD>
Requires: LIP 0022, LIP 0040

Abstract

The random module handles the validation of the inputs and computation of outputs for the commit and reveal process for a Lisk blockchain. In this LIP, we specify the state transitions logic defined within this module, i.e., the protocol logic injected during the block lifecycle, and the functions that can be called from other modules or off-chain services

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

The random module handles the validation of the inputs for the commit and reveal process introduced in LIP 0022 as well as the computation of the random seeds from that process. In this LIP we specify the properties, serialization, and default values of the random module, as well as the protocol logic processed during a block lifecycle, and the functions exposed to other modules and to off-chain services

Rationale

Random Module Store

The random module defines a random substore whose value contains the validator reveals array.
This array contains the necessary information to:

  • validate the seeds revealed by the validators as part of the commit and reveal process, and
  • compute the random seed to be used as source of randomness to re-order the generator list for a new round (both in PoA and DPoS chains) and to select the standby delegates (in certain DPoS chains as well as the Lisk mainchain).

This array has a bounded length that is given as part of the configuration of the random module. On one hand, when a new block is executed, a new element is added to this array. On the other hand, the old revealed seeds are in most of the cases deleted from the array since they are not needed anymore.

It is worth noting that random seed computation from this commit and reveal process can be used for other applications that need a source of randomness. However, this random seed has certain limitations that have to be taken into account as explained in LIP 0022. Certain applications may require a different source of randomness to be secure.

Specification

In this section, we specify the substores that are part of the random module store, and the protocol logic called during the block lifecycle.

The random module has module ID MODULE_ID_RANDOM (see the table below). It is a module with no dependencies.

Constants

Name Type Value Description
MODULE_ID_RANDOM uint32 TBD ID of the random module
STORE_PREFIX_RANDOM bytes 0x0000 Prefix of the random substore
MAX_LENGTH_REVEALS_MAINCHAIN uint32 206 Maximum length of the validatorReveals array for the Lisk Mainchain

Random Module Store

The key-value pairs in the module store are organized in the following substore.

Random Substore

Store Prefix, Store Key, and Store Value

The entry in the random substore is defined as follows:

  • The store prefix is set to STORE_PREFIX_RANDOM.
  • The store key is set to empty bytes.
  • The store value is the serialization of an object following the JSON schema seedRevealSchema presented below.
Seed Reveal Schema
seedRevealSchema = {
    type: "object",
    properties: {
        "validatorReveals": {
            type: "array",
	    "fieldNumber": 1,
            items: {
                "type": "object",
                properties: {
                    "generatorAddress": {
                        "dataType": "bytes",
                        "fieldNumber": 1
                    },
                    "seedReveal": {
                        "dataType": "bytes",
                        "fieldNumber": 2
                    },
                    "height": {
                        "dataType": "uint32",
                        "fieldNumber": 3
                    },
                    "valid": {
                        "dataType": "boolean",
                        "fieldNumber": 4
                    }
                },
                "required": [
                    "generatorAddress", 
                    "seedReveal", 
                    "height", 
                    "valid"]
            }
        },
        "required": ["validatorReveals"]
    }
 }
Properties

In this section, we describe the properties in the validatorReveals array of the seed reveal object:

  • generatorAddress: The address of the generator of the block. A valid generator address is 20 bytes long.
  • seedReveal: The value revealed by the generator of the block for the commit and reveal process. A valid seed reveal is 16 bytes long.
  • height: The height of the block where the generator added their revealed seed.
  • valid: The flag stating the validity of seedReveal for the random seed computation.

The validatorReveals array is kept ordered by increasing value of height.

Internal Functions

The random module has the following internal functions.

Hashing Function

A new hashing function, H, is defined for this module.

Parameters
  • input: A bytes value of arbitrary length.
Returns

The function returns a 16-bytes value, digest.

Execution
H(input):
    t = SHA-256(input)
    digest = trunc(t)
    return digest

where the function trunc truncates its input to the 16 most significant bytes.

isSeedValidInput

This function assesses the validity of the revealed seed as input for the random seed computation.

Parameters
  • generatorAddress: A 20-bytes value with the address of the generator of a certain block.
  • seedReveal: A 16-bytes value with the seed revealed by the generator of a certain block.
Returns

This function returns true if seedReveal is valid input for the random seed computation, otherwise, false.

Execution
isSeedValidInput(generatorAddress, seedReveal):
    let seedObject be an element in validatorReveals array
    let lastSeed be the seedObject with the largest seedObject.height and seedObject.generatorAddress == generatorAddress
    if not lastSeed:
        return false
    if lastSeed.seedReveal == H(seedReveal):
        return true
    return false

Protocol Logic for Other Modules

The random module exposes the following logic to other modules.

isSeedRevealValid

This function assesses the validity of the seedReveal property of a block.

Parameters
  • generatorAddress: A 20-bytes value with the address of the generator of a certain block.
  • seedReveal: A 16-bytes value with the seed revealed by the generator of a certain block.
Returns

This function returns true if seedReveal was correctly revealed, otherwise, false.

Execution

It is specified as:

isSeedRevealValid(generatorAddress, seedReveal):
    let seedObject be an element in validatorReveals array
    let lastSeed be the seedObject with the largest seedObject.height and seedObject.generatorAddress == generatorAddress
    if not lastSeed:
	     return true
    if lastSeed.seedReveal == H(seedReveal):
        return true
    return false

getRandomBytes

This function is used to return the random seed as a 32-bytes value.

Parameters
  • height: An integer with the height of a certain block.
  • numberOfSeeds: An integer with the number of seeds to consider for the computation.
Returns

randomSeed: A 32-bytes value representing the random seed.

Execution

It is specified as:

getRandomBytes(height, numberOfSeeds):
    randomSeed = H(height + numberOfSeeds)
    let currentSeeds be an array with every seedObject element in validatorReveals so that height <= seedObject.height <= height + numberOfSeeds 
    for every seedObject element in currentSeeds:
        if seedObject.valid == true:
    	 randomSeed = randomSeed XOR seedObject.seedReveal
    return randomSeed

Endpoints for Off-Chain Services

The random module exposes the following function.

IsSeedRevealValid

This function has exactly the same logic, inputs and outputs as the isSeedRevealValid function specified in the previous section.

Protocol Logic During Block Lifecycle

After Genesis Block Execution

After the genesis block g is executed, the following logic is executed:

  • Set the validatorReveals array to an empty array.

Block Verification

As part of the verification of a block b, the following checks are applied. If the checks fail the block is discarded and has no further effect. This logic is not called during the block creation process.

Let blockAssetBytes be the bytes included in the block asset for the random module:

  1. Let blockAssetObject be the deserialization of blockAssetBytes according to blockHeaderAssetRandomModule in the Block Initialization subsection.
  2. Validate blockAssetObject.seedReveal as specified in the section “Validating New Block Header Property” of LIP 0022 (same logic as isSeedRevealValid function above).

After Block Execution

After a block b is executed, the following logic is applied:

  • While the size of the validatorReveals array is larger than MAX_LENGTH_VALIDATOR_REVEALS, delete the element of validatorReveals array with the smallest value of height.

    • By construction this should be the first element of the validatorReveals array.
    • The value of the MAX_LENGTH_VALIDATOR_REVEALS constant is given in the initial configuration of the random module. It should be set as twice the maximum length of the chains validator set. For Lisk mainchain, MAX_LENGTH_VALIDATOR_REVEALS = MAX_LENGTH_REVEALS_MAINCHAIN.

  • Add a new element to the validatorReveals array with the following content:

    • seedReveal = blockAssetObject.seedReveal
    • generatorAddress = b.header.generatorAddress
    • height = b.header.height
    • valid = isSeedValidInput(b.header.generatorAddress, blockAssetObject.seedReveal)

    where the isSeedValidInput is the internal function specified above.

Block Creation

Block Initialization

The asset data created by the random module contains a serialized object following the blockHeaderAssetRandomModule schema where the property seedReveal, the seed revealed by the block generator, is set by the module. This can be done by implementing the hash onion algorithm introduced in the Appendix B of LIP 0022.

blockHeaderAssetRandomModule = {
   "type": "object",
   "properties": {
       "seedReveal": {
           "dataType": "uint64",
           "fieldNumber": 1
       }
   },
   "required": ["seedReveal"]
}

Backwards Compatibility

This LIP defines a new store interface for the random module, which in turn will become part of the state tree and will be authenticated by the state root. As such, it will induce a hardfork.

1 Like
2

I created a pull request for this proposal in the LIPs repository: Add LIP "Define state and state transitions of random module" by IkerAlus · Pull Request #95 · LiskHQ/lips

3

The PR has been merged.