Skip to content

Latest commit

 

History

History
317 lines (220 loc) · 13.3 KB

lip-0046.md

File metadata and controls

317 lines (220 loc) · 13.3 KB
LIP: 0046
Title: Define state and state transitions of Random module
Author: Iker Alustiza <[email protected]>
        Ishan Tiwari <[email protected]>
Discussions-To: https://research.lisk.com/t/define-state-and-state-transitions-of-random-module
Status: Draft
Type: Standards Track
Created: 2021-06-30
Updated: 2023-01-30
Requires: 0022, 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 genesis block processing, common block processing, 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 during block processing, the genesis block processing, 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 PoS chains) and to select the standby validators (in certain PoS 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 processing and genesis block processing.

The Random module has name MODULE_NAME_RANDOM (see the table below). It is a module with no dependencies.

Constants and config parameters

We define the following constants:

Name Type Value Description
Constants
MODULE_NAME_RANDOM string "random" Module's name.
SUBSTORE_PREFIX_RANDOM bytes 0x0000 Prefix of the random substore.
ADDRESS_LENGTH uint32 20 Length in bytes of type Address.
SEED_LENGTH uint32 16 Length in bytes of a valid seed revealed.
Config parameters Mainchain value
MAX_LENGTH_VALIDATOR_REVEALS uint32 206 Maximum length of the validatorReveals array.

Type Definition

Name Type Validation Description
Address bytes Must be of length ADDRESS_LENGTH. Address of an account.

Random Module Store

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

Random Substore

Substore Prefix, Store Key, and Store Value

The entry in the random substore is defined as follows:

  • The substore prefix is set to SUBSTORE_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.
  • Notation: For the rest of this proposal, let validatorReveals be the entry in the random substore, deserialized using seedRevealSchema schema.
Seed Reveal Schema
seedRevealSchema = {
    "type": "object",
    "required": ["validatorReveals"],
    "properties": {
        "validatorReveals": {
            "type": "array",
            "fieldNumber": 1,
            "items": {
                "type": "object",
                "required": [ "generatorAddress", "seedReveal", "height", "valid"],
                "properties": {
                    "generatorAddress": {
                        "dataType": "bytes",
                        "length": ADDRESS_LENGTH,
                        "fieldNumber": 1
                    },
                    "seedReveal": {
                        "dataType": "bytes",
                        "length": SEED_LENGTH,
                        "fieldNumber": 2
                    },
                    "height": {
                        "dataType": "uint32",
                        "fieldNumber": 3
                    },
                    "valid": {
                        "dataType": "boolean",
                        "fieldNumber": 4
                    }
                }
            }
        }
    }
 }
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.
  • seedReveal: The value revealed by the generator of the block for the commit and reveal process.
  • 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. It receives as input a bytes value of arbitrary length and returns the first SEED_LENGTH bytes of its SHA-256 hash.

Execution
def H(input: bytes) -> bytes:
    t = SHA-256(input)
    digest = t[0:SEED_LENGTH]
    return digest

isSeedValidInput

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

Parameters
  • generatorAddress: The address of the generator of a certain block.
  • seedReveal: A SEED_LENGTH-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
def isSeedValidInput(generatorAddress: Address, seedReveal: bytes) -> bool: 
    lastSeed = last element seedObject in validatorReveals array with seedObject.generatorAddress == generatorAddress
    if not lastSeed:
        return False
    if lastSeed.seedReveal == H(seedReveal):
        return True
    return False

Commands

This module does not define any command.

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: The address of the generator of a certain block.
  • seedReveal: A SEED_LENGTH-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:

def isSeedRevealValid(generatorAddress: Address, seedReveal: bytes) -> bool:
    lastSeed = last element seedObject in validatorReveals array with 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 SEED_LENGTH-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 SEED_LENGTH-bytes value representing the random seed.

Execution

It is specified as:

def getRandomBytes(height: uint32, numberOfSeeds: uint32) -> bytes:
    randomSeed = H(height + numberOfSeeds)
    currentSeeds = [seedObject for seedObject in validatorReveals if 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.

Genesis Block Processing

The following step is executed as part of the genesis block processing, see the LIP 0060 for details.

Genesis State Initialization

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

  • Create the entry in the random substore as specified above.
  • Set the validatorReveals array in the store value of the random substore to an empty array.

Block Processing

The following steps are executed as part of the block processing, see LIP 0055 for details.

Assets Verification

As part of the verification of the assets property 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. The property blockAssetObject.seedReveal has to have a length of SEED_LENGTH bytes.

After Transactions Execution

After all the transactions of a block b are 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.
  • 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 Generation

Assets Insertion

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",
   "required": ["seedReveal"],
   "properties": {
       "seedReveal": {
           "dataType": "bytes",
           "length": SEED_LENGTH,
           "fieldNumber": 1
       }
   }
}

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.

Reference Implementation

TBA