KIP 114: Supplant DIFFICULTY opcode with RANDOM

Author	Ian, Ollie, Joseph, and Aidan
Discussions-To	https://github.com/klaytn/kips/issues/114
Status	Draft
Type	Standards Track
Category	Core
Created	2023-05-31

Simple Summary

Introduce on-chain randomness and expose it in the EVM by supplanting DIFFICULTY opcode semantics

Abstract

This standard outlines an approach for generating an on-chain random value based on digital signature. Specifically, it introduces new fields, namely randomReveal and mixHash, in the block header; randomReveal is a verifiable random number, and mixHash is a derivation from a mixture of randomReveals and additional information. They serve as an unpredictable, verifiable, and dependable source of on-chain randomness. In addition, these fields can be fetched from the EVM via RANDOM (0x44) opcode.

Motivation

An unpredictable, verifiable, and dependable on-chain randomness can be utilized in various use-cases including the protocol and applications.

Unpredictability indicates that the random should be as difficult to predict as possible.
Verifiability ensures that the random is authentic and cannot be manipulated or forged.
Dependability implies that the random is generated without trusting any external sources of randomness, such as oracles.

An example of such use-cases is the block proposer selection. An exemplary requirement can be that the next block’s proposer remains undisclosed until the latest block has been finalized, or that the proposer cannot tamper with deciding the next block’s proposer.

In this proposal, new header fields randomReveal and mixHash are introduced. randomReveal is the signature of the proposer, and randomReveals are mixed to compute mixHash, which users can use for a part of the random source. mixHash is unpredictable, verifiable, and dependable:

(Unpredictability) the signature is random and so is mixHash.
(Verifiability) the signature can be verified with the public key of the proposer, and mixHash is computed in a deterministic manner.
(Dependability) mixHash only relies on the validators.

Specification

The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in RFC 2119.

The terms hash_to_point (hereinafter referred to as hash), public key, proof-of-possession (hereinafter referred to as pop) are from the ciphersuite BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_.

Parameters

Constant	Value
`FORK_BLOCK`	TBD

Block Structure

Beginning with FORK_BLOCK, client software must set the fields in a block header:

randomReveal: 96 bytes. It must be specified in the 15th field (0-indexed) of a block header.
mixHash: 32 bytes. It must be specified in the 16th field (0-indexed) of a block header.

Block Processing

Block Proposal

Beginning with FORK_BLOCK, the proposer must fill the new fields in the block proposal:

randomReveal: The proposer must sign the hash of the proposing block number.
mixHash: The proposer must XOR the keccak256 hash of randomReveal and the previous block’s mixHash. If the previous block’s mixHash is null (e.g., previous block is before FORK_BLOCK), then use 32 bytes of zero instead.

class Header:
	parentHash:   hash
	rewardbase:   address
	root:         hash
	txHash:       hash
	receiptHash:  hash
	bloom:        bloom
	blockScore:   int
	number:       int
	gasUsed:      uint64
	time:         int
	timeFoS:      uint8
	extra:        bytes
	governance:   bytes
	vote:         bytes
	baseFee:      int

	randomReveal: bytes # new
	mixHash:      bytes # new

header.randomReveal = sign(privateKey, header.number)
header.mixHash = xor(prevHeader.mixHash, keccak256(randomReveal))

Validation

Beginning with FORK_BLOCK, validators must validate the new fields:

randomReveal
- The validators must fetch the public key and the pop of the proposer by getInfo(cnNodeId) of the BLS registry standardized by KIP-113.
- The validators must verify the validity of the proposer public key using pop as mentioned in here.
- The validators must verify if randomReveal is signed by the proposer public key.
mixHash: The validators must verify the validity of the proposed mixHash by calculating mixHash using the aforementioned mixHash algorithm.

Pseudocode

See the following pseudocode that describes the block processing in python:

DEFAULT_MIXHASH = b"\x00" * 32

def fill_kip114_header(newHeader, prevHeader, privateKey):
    newHeader.randomReveal = calc_random_reveal(privateKey, newHeader.number)

    if newHeader.number == FORK_BLOCK:
        prevMixHash =  DEFAULT_MIXHASH
    else:
        prevMixHash = prevHeader.mixHash
    newHeader.mixHash = calc_mix_hash(prevMixHash, newHeader.randomReveal)

def calc_random_reveal(privateKey, headerNumber):
    return sign(privateKey, headerNumber)

def calc_mix_hash(prevMixHash, randomReveal):
    return xor(prevMixHash, keccak256(randomReveal))

def verify_kip114_header(newHeader, prevHeader):
    # Getting PoP information from the smart contract registry defined in KIP-113.
    [proposerPubkey, proposerPop] = get_proposer_pubkey_pop()
    # pop verify
    if not pop_verify(proposerPubkey, proposerPop):
        return False

    # signature verify
    if not verify(proposerPubkey, newHeader.number, newHeader.randomReveal):
        return False

    # mixHash verify
    if newHeader.number == FORK_BLOCK:
        prevMixHash = DEFAULT_MIXHASH
    else:
        prevMixHash = prevHeader.mixHash
    return newHeader.mixHash == calc_mix_hash(prevMixHash, newHeader.randomReveal):

EVM

Beginning with FORK_BLOCK, the RANDOM (0x44) instruction must return the value of mixHash of the current block it is executing in.

Note: The gas cost of the RANDOM (0x44) opcode remains unchanged.

Genesis Block

If FORK_BLOCK is zero, the genesis block must have randomReveal and mixHash fields.

Rationale

Names of the header fields

The naming is highly inspired by EIP-4339. We use randomReveal instead of RANDAO reveal because the randoms are generated in a different manner.

Block size increment due to new fields in the header

The size increment cost of RLP-encoded header is around 131 bytes per block, which is approximately 3.8GB per year. It is a negligible cost compared to its benefit.

BLS-based random over EC-based random

We chose BLS-based verifiable random over EC-based because:

A BLS library written in Golang is easy to find as in link, whereas it is not the case for EC-based as in link.
There is a potential consensus change based on BLS signature. Therefore, this proposal gently introduces BLS signature to the Klaytn protocol as well as adding on-chain randomness.

Backwards Compatibility

Blocks before FORK_BLOCK will remain the same.

Security Considerations

Biasability

BLS signature as well as the signing message (i.e., proposing block number) is deterministic. Thus, the proposer has no influence over the computation of mixHash. In addition, the biasability of mixHash mainly depends on that of the hash of randomReveal. To the best of our knowledge, keccak256 is not a biased hash function. Therefore, mixHash, which is the XOR of the output of keccak256 and the previous mixHash, is unbiased.

Predictability

A list of inputs influencing future randomness consists of but is not limited to the following items:

Number of colluding validators. When colluding validators become proposers of consecutive blocks, they collectively share their randomReveals in advance to predict the value of mixHash.
Proposer selection policy. This contributes to how likely the colluding validators become proposers of consecutive blocks.

Define f(x, N, C):

N: the number of validators
C: the number of colluding validators (N > C)
x: the number of blocks from the latest block
f: the probability of predicting the value of mixHash x blocks in advance. In other words, the probability of colluding validators becoming proposers for x consecutive blocks.

Under random proposer selection policy, the proposer is randomly selected after each block, thus f(x, N, C) = (C/N)^x.

Tips for application developers

The following tips attempt to reduce predictability and biasability of randomness outputs returned by RANDOM (0x44):

Make your applications rely on the future randomness with a reasonably high lookahead. Given that IBFT permits one third of the validators to be malicious, developers are advised to give a distance of 200 blocks between bidding and rolling the dice to be “95 nines” safe.

Implementation

A simulation in Python:

from blspy import PrivateKey, G1Element, G2Element, PopSchemeMPL  # blspy
from Crypto.Hash import keccak  # pycryptodome

FORK_BLOCK = 100  # TBD
DEFAULT_MIXHASH = b"\x00" * 32

validatorNum: int = 3
proposerBLSPrivKeys: list[PrivateKey] = [
    PrivateKey.from_bytes((i + 1).to_bytes(32, byteorder="big"))
    for i in range(validatorNum)
]  # b"\x00..\x01", b"\x00..\x02", ...
proposerBLSPublicKeys: list[G1Element] = [i.get_g1() for i in proposerBLSPrivKeys]
proposerAddrs: list[str] = [
    str(i + 1).zfill(40) for i in range(validatorNum)
]  # "0x00..1, 0x00..2, ..."


# Block header. Only relevant fields are shown here.
class Header:
    number: int = 0  # Block number
    randomReveal: bytes
    mixHash: bytes
    proposer: str

    def __init__(self, number: int, randomReveal: bytes = b"", mixHash: bytes = b""):
        self.number = number
        self.randomReveal = randomReveal
        self.mixHash = mixHash
        self.proposer = proposerAddrs[number % validatorNum]

    def __repr__(self):
        return "number: {}\n\nrandomReveal ({} bytes): {}\n\nmixHash ({} bytes): {}".format(
            self.number,
            len(self.randomReveal),
            self.randomReveal,
            len(self.mixHash),
            self.mixHash,
        )


class BlsPublicKeyInfo:
    publicKey: bytes
    pop: bytes

    def __init__(self, publicKey, pop):
        self.publicKey = publicKey
        self.pop = pop


# A BLSRegistry that supports the interface IKIP-113 (https://github.com/klaytn/kips/blob/main/KIPs/kip-113.md)
class BLSRegistry:
    mapping = {}

    def __init__(self):
        for i, proposerAddr in enumerate(proposerAddrs):
            pop = bytes(PopSchemeMPL.pop_prove(proposerBLSPrivKeys[i]))
            self.mapping[proposerAddr] = BlsPublicKeyInfo(
                bytes(proposerBLSPublicKeys[i]), pop
            )

    def getInfo(self, addr: str) -> BlsPublicKeyInfo:
        return self.mapping[addr]


def is_kip114_fork_enabled(num) -> bool:
    return FORK_BLOCK <= num


# dummy function for fetching the proposer secret key
# in implementation, this should be fetched from a file
def get_proposer_private_key(num) -> PrivateKey:
    proposerIdx = num % validatorNum
    return proposerBLSPrivKeys[proposerIdx]


def fill_kip114_header(newHeader, prevHeader, privateKey):
    newHeader.randomReveal = calc_random_reveal(privateKey, newHeader.number)

    if newHeader.number == FORK_BLOCK:
        prevMixHash = DEFAULT_MIXHASH
    else:
        prevMixHash = prevHeader.mixHash
    newHeader.mixHash = calc_mix_hash(prevMixHash, newHeader.randomReveal)


def calc_random_reveal(sk, num) -> bytes:
    msg = block_num_to_bytes(num)
    return bytes(PopSchemeMPL.sign(sk, msg))


def calc_mix_hash(prevMixHash, randomReveal) -> bytes:
    return xor(prevMixHash, keccak256(randomReveal))


def gen_next_header(prevHeader) -> Header:
    nextBlockNum = prevHeader.number + 1
    newHeader = Header(nextBlockNum)
    if is_kip114_fork_enabled(nextBlockNum):
        privateKey = get_proposer_private_key(nextBlockNum)
        fill_kip114_header(newHeader, prevHeader, privateKey)

    return newHeader


def keccak256(msg) -> bytes:
    keccak256 = keccak.new(digest_bits=256)
    keccak256.update(msg)
    return keccak256.digest()


def block_num_to_bytes(num) -> bytes:
    return num.to_bytes(32, byteorder="big")


def xor(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))


def verify_kip114_header(header, prevHeader) -> bool:
    if not is_kip114_fork_enabled(header.number):
        return True

    # pop verify
    blsPublicKeyInfo = BLSRegistry().getInfo(header.proposer)
    publicKey = G1Element.from_bytes(blsPublicKeyInfo.publicKey)
    pop = G2Element.from_bytes(blsPublicKeyInfo.pop)
    if not PopSchemeMPL.pop_verify(publicKey, pop):
        return False

    # signature verify
    msg = block_num_to_bytes(header.number)
    sig = G2Element.from_bytes(header.randomReveal)
    if not PopSchemeMPL.verify(publicKey, msg, sig):
        return False

    # mixHash verify
    if header.number == FORK_BLOCK:
        # prevHeader mixHash does not exist, so fill with default
        prevMixHash = DEFAULT_MIXHASH
    else:
        prevMixHash = prevHeader.mixHash
    return header.mixHash == calc_mix_hash(prevMixHash, header.randomReveal)


def main():
    header = Header(FORK_BLOCK - 2)
    prevHeader = header
    N = 10
    # print header numbers in [FORK_BLOCK - 1, FORK_BLOCK + N]
    for _ in range(N + 2):
        header = gen_next_header(header)
        print(header)
        verified = verify_kip114_header(header, prevHeader)
        assert verified
        print("verified:", verified)
        print("=" * 80)
        prevHeader = header


main()

Test Cases

Proposer secret key:   0x6c605527c8e4f31c959478801d51384d690a22dfc6438604646f7709032c893a
Previous MixHash:      0x8019df1a2a9f833dc7f400a15b33e54a5c80295165c5953dc23891aab9203810
Block number:          31337
Expected Msg:          0x0000000000000000000000000000000000000000000000000000000000007a69
Expected RandomReveal: 0xadfe25ced45819332cbf088f01cdd2807686dd6309b11d7440237dd623624f401d4753747f5fb92374235e997edcd18318bae2806a1675b1e685e792abd1fbdf5c50ec1e148cc7fe861984d8bc3204c1b2136725b
Expected MixHash:      0x8772d58248bdf34e81ecbf36f28299cfa758b61ccf3f64e1dc0646687a55892f

Testing the Python simulation above:

sk = PrivateKey.from_bytes(unhexlify("6c605527c8e4f31c959478801d51384d690a22dfc6438604646f7709032c893a"))
prevMix = unhexlify("8019df1a2a9f833dc7f400a15b33e54a5c80295165c5953dc23891aab9203810")
num = 31337

msg = block_num_to_bytes(num)
reveal = calc_random_reveal(sk, num)
mix = calc_mix_hash(prevMix, reveal)
assert hexlify(msg) == b"0000000000000000000000000000000000000000000000000000000000007a69"
assert hexlify(reveal) == b"adfe25ced45819332cbf088f01cdd2807686dd6309b11d7440237dd623624f401d4753747f5fb92374235e997edcd18318bae2806a1675b1e685e792abd1fbdf5c50ec1e148cc7fe861984d8bc3204c1b2136725b
assert hexlify(mix) == b"8772d58248bdf34e81ecbf36f28299cfa758b61ccf3f64e1dc0646687a55892f"

KIP 114: Supplant DIFFICULTY opcode with RANDOM

Simple Summary

Abstract

Motivation

Specification

Parameters

Block Structure

Block Processing

Block Proposal

Validation

Pseudocode

EVM

Genesis Block

Rationale

Names of the header fields

Block size increment due to new fields in the header

BLS-based random over EC-based random

Backwards Compatibility

Security Considerations

Biasability

Predictability

Tips for application developers

Implementation

Test Cases

References

Copyright

KIP 114: Supplant DIFFICULTY opcode with RANDOM Source

Simple Summary

Abstract

Motivation

Specification

Parameters

Block Structure

Block Processing

Block Proposal

Validation

Pseudocode

EVM

Genesis Block

Rationale

Names of the header fields

Block size increment due to new fields in the header

BLS-based random over EC-based random

Backwards Compatibility

Security Considerations

Biasability

Predictability

Tips for application developers

Implementation

Test Cases

References

Copyright

KIP 114: Supplant DIFFICULTY opcode with RANDOM