KIP 146: Unpredictable Proposer Selection

Simple Summary

An unpredictable and verifiable proposer selection policy

Abstract

This standard outlines an approach for an unpredictable proposer selection policy. A proposer is determined every block in a random manner. The randomness relies on KIP-114, thereby rendering the new policy both unpredictable and verifiable.

Motivation

Klaytn has adopted the Byzantine Fault Tolerance (BFT) consensus mechanism, where a block proposer selected by a deterministic algorithm proposes the next block. A vulnerable point of BFT is that an adversary can effectively halt the entire network by simply targeting the proposer, a.k.a. targeted DoS. What makes Klaytn even more vulnerable to a targeted DoS attack is that the current proposer selection policy enables the prediction of up to proposerUpdateInterval (3600 in case of Cypress) number of proposers in advance.

As of now, a targeted DoS is practically infeasible in Klaytn because it is a permissioned chain which allows only authorized validators to join the network. However, in a permissionless network, a targeted DoS is a viable option for attackers. A random proposer selection can increase the difficulty of the attack by introducing an uncertainty of the upcoming proposers.

Meanwhile, a few malicious validators must not be able to forge the randomness to arbitrarily determine the upcoming proposers. If not, it may increase the risk of censorship or monopolizing block rewards. Therefore, the new random proposer selection policy should be both unpredictable and verifiable.

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.

Parameters

Shuffling

A shuffling algorithm must be defined which will act as a building block of proposer and committee selection.

Fisher-Yates shuffle must be used in the below pseudocode (i.e., random.shuffle), and Golang’s RNG must be used as a pseudo random number generator internally in Fisher-Yates.

The shuffling function must be deterministic given validators and seed.

def shuffle_validators_KIP146(validators: list[int], seed: int):
    """returns a list of randomly shuffled validators.
    Keyword arguments:
    validators -- deterministically sorted list of validators.
    seed -- `mixHash[0:8]` interpreted as the bytes of a big-endian signed 64-bit integer. The `mixHash` of the previous block is used (see KIP-114).
    """
    ret = validators[:]

    random.seed(seed)
    random.shuffle(ret)
    return ret

Proposer selection

For calculating the proposer of FORK_BLOCK and afterward, the new logic must be used. This only affects the chain whose proposer selection policy is set to WeightedRandom.

Below algorithm ensures that

• The proposer must be randomly selected each block.
• The proposer must change in case of round change.
• The proposer must be selected from committee.

def proposer_selector(validators: list[int], committee_size: int, round: int, seed: int):
    """returns a proposer from validators.

    Keyword arguments:
    validators -- deterministically sorted list of validators.
    committee_size -- the value of `istanbul.sub` in ChainConfig.
    round -- the target consensus round.
    seed -- `mixHash[0:8]` interpreted as the bytes of a big-endian signed 64-bit integer. The `mixHash` of the previous block is used (see KIP-114).
    """
    return select_committee_KIP146(validators, committee_size, seed)[round % len(validators)]

Committee selection

For calculating the committee of FORK_BLOCK and afterward, the new logic must be used. This only affects the chain whose proposer selection policy is set to WeightedRandom.

This design guarantees that the given proposer address is always in the committee.

Below algorithm ensures that

• The committee must be randomly selected each block.
• The committee must not change in case of round change.
• The next round proposer must be in the committee.

def select_committee_KIP146(validators: list[int], committee_size: int, seed: int):
    """returns a committee from validators.

    Keyword arguments:
    validators -- deterministically sorted list of validators.
    committee_size -- the value of `istanbul.sub` in ChainConfig.
    seed -- `mixHash[0:8]` interpreted as the bytes of a big-endian signed 64-bit integer. The `mixHash` of the previous block is used (see KIP-114).
    """
    shuffled = shuffle_validators_KIP146(validators, seed)
    return shuffled[:min(committee_size, len(validators))]

Rationale

Using part of mixHash as a seed

As defined in KIP-114, mixHash is the result of XOR operation with a keccak256 hash. To the best of our knowledge, truncating the cryptographic hash is safe to be used for the seed of pseudo random number generator. Ethereum also uses the first eight bytes of a hash: link.

Committee remaining the same in case of round change

Unlike the previous semantic of WeightedRandom proposer selection policy, this proposal suggests a policy where the members of the committee remains the same in case of round change. This new policy addresses a potential security issue where a fork could happen even within the number of Byzantine nodes permitted by Istanbul Byzantine Fault Tolerance mechanism (i.e., one third of validators).

Side effect

Differentiation of next round proposer and next block proposer

The current algorithm for composing a committee makes sure that the proposer and the next round proposer is included in the committee. Before FORK_BLOCK, the next round proposer is equal to the next block proposer, and thus the next block proposer always ended up in the committee. However, after FORK_BLOCK, the next round proposer can be different from the next block proposer, which may result in the next block proposer not being included from the committee. This side effect does not degrade the network security; while the next proposer being in the committee could potentially be helpful to next block generation, its significance is negligible, if any.

Affecting the predictability of mixHash

Allowing a certain validator to be selected as the proposer for consecutive blocks affects the predictability of mixHash in KIP-114. See here for further details.

Backwards Compatibility

The proposer selection policy before FORK_BLOCK remains the same.

Security Considerations

Biasability

The biasability of this proposal relies on that of KIP-114, the shuffling algorithm, and the pseudo random number generator.

• KIP-114 is unbiased because keccak256 hash is.
• The shuffling algorithm Fisher-Yates is unbiased as long as the pseudo random number generator is.
• To the best of our knowledge, the Golang’s pseudo random number generator is unbiased; it uses Additive Lagged Fibonacci Generator where initial values are generated by a Linear Congruential Generator based on the user seed.

Predictability

The probability of predicting a proposer at a certain block is the maximum of the followings:

• Predictability of mixHash as specified here.
• Randomly picking one out of validators.

It implies that the probability has a lower bound of 1/N, where N is the number of validators.

Implementation

A reference implementation in Golang: link.

Note that Golang’s standard package rand.shuffle implements Fisher-Yates.

References

• Eth2 beacon chain docs
• Eth2 book
• Attacking Go’s Lagged Fibonacci Generator
• KIP-114

Copyright

Copyright and related rights waived via CC0.