kip | title | author | discussions-to | status | type | category | created |
---|---|---|---|---|---|---|---|
114 |
Supplant DIFFICULTY opcode with RANDOM |
Ian (@ian0371), Ollie (@blukat29), Joseph (@jiseongnoh), and Aidan (@aidan-kwon) |
Draft |
Standards Track |
Core |
2023-05-31 |
Introduce on-chain randomness and expose it in the EVM by supplanting DIFFICULTY opcode semantics
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.
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 randomReveal
s 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.
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_.
Constant | Value |
---|---|
FORK_BLOCK |
TBD |
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.
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 ofrandomReveal
and the previous block'smixHash
. If the previous block'smixHash
is null (e.g., previous block is beforeFORK_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))
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.
- The validators must fetch the public key and the pop of the proposer by
-
mixHash
: The validators must verify the validity of the proposedmixHash
by calculatingmixHash
using the aforementionedmixHash
algorithm.
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):
Beginning with FORK_BLOCK
, the RANDOM (0x44)
instruction must return the value of mixHash
of the latest block.
Note: The gas cost of the RANDOM (0x44)
opcode remains unchanged.
If FORK_BLOCK
is zero, the genesis block must have randomReveal
and mixHash
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.
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.
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.
Blocks before FORK_BLOCK
will remain the same.
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.
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
randomReveal
s in advance to predict the value ofmixHash
. - 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 validatorsC
: the number of colluding validators (N > C)x
: the number of blocks from the latest blockf
: the probability of predicting the value ofmixHash
x
blocks in advance. In other words, the probability of colluding validators becoming proposers forx
consecutive blocks.
Under random proposer selection policy, the proposer is randomly selected after each block, thus f(x, N, C) = (C/N)^x
.
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.
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(8, 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()
- consensus-specs/beacon-chain.md at dev · ethereum/consensus-specs
- EIP-4399: Supplant DIFFICULTY opcode with PREVRANDAO
Copyright and related rights waived via CC0.