Whisk: Expensive duty discovery

Whisk is a single secret leader election protocol, providing proposers privacy at the protocol level. Checkout the ethresearch post for background

This post arises from discusing with George (@asn-d6) the solution from https://hackmd.io/@dapplion/whisk_induced_missed_slots, so it's recommended as additional background to readers

After Whisk each validator must independently perform a test to discover if it has to propose at each slot. Specifically, it has to check:

def should_k_propose_at_slot(slot, k):
    state = get_head_state_at_slot(slot)
    tracker = state.whisk_proposer_trackers[slot % WHISK_PROPOSER_TRACKERS_COUNT]
    return tracker.r_G * k == tracker.r_k_G

k is a secret scalar that allows Whisk shuffle to remain secret. Since we are adding Whisk to a live system, validators must be bootstrapped with some non-secret value (this is the bootstrapping problem, to be discussed in a later post). Therefore a validator's k has two values through a validator lifetime:

• initial public k, deterministically compute from public data
• secret validator submitted k

The initial public k is computed with get_unique_whisk_k when a validator record is created or at the whisk fork boundary. Note that the output of this function is dependent on which specific state is run against.

def get_unique_whisk_k(state, validator_index):
    counter = 0
    while True:
        k = get_initial_whisk_k(validator_index, counter)
        if is_k_commitment_unique(state, BLSG1ScalarMultiply(k, BLS_G1_GENERATOR)):
            return k  # unique by trial and error
        counter += 1

While k can be any* value, in this post we will derive k from the existing validating keypair (i.e. hashing the secret key) for simplicity and to prevent adding new key management requirements to validator setups.

So, putting it all together a validator must perform the next check on each slot:

def should_propose_at_slot(slot, keypair):
    k = derive_k_from_keypair(keypair)
    initial_k = get_unique_whisk_k(state_at_registration) # ⚠️! undefined argument
    return (
        should_propose_at_slot(slot, k)
        or should_propose_at_slot(slot, initial_k)
    )

But, how does a validator retrieve state_at_registration? A validator may have registered long in the past. For networks with large index counts the average wait to propose can be months. Moreover, how can the validator discover at which specific slot it registered? To know which state to retrieve, and to retrieve it, a validator would have access to archive data.

That's not good, does the validator have other options?

Brute force

The function get_unique_whisk_k features an infinite loop, but it can produce at most len(state.validators) different values. A validator can precompute enough k_initial values and check them all in every slot. However, it would require hundreds of thousands of G1 point multiplications for each connected index for each slot.

def should_propose_at_slot(slot, keypair):
    k = derive_k_from_keypair(keypair)
    max_counter = len(get_head_state().validators)
    initial_ks = [get_initial_whisk_k(validator_index, i) for i in range(max_counter)

    return (
        should_propose_at_slot(slot, k)
        or any(should_propose_at_slot(slot, k_i) for k_i in initial_ks)
    )

Check registered commitment

A validator can not use state data to assert which k to use on should_k_propose_at_slot. Before its first proposal (t0 in the diagram), certainly, elected proposer trackers can only include trackers created with k_initial. However, a validator can not differentiate the time ranges [t0,t1] and [t1..] with a single recent state. Since beacon states do not track proposal timings, a validator can only assert it has proposed at least once post-whisk, but not when.

Therefore, after t0, a validator without access to historical blocks must test both k and k_initial.

Problem

With the above points with can establish that for a validator without access to historical blocks and states to conclusively assert elected tracker ownership:

1. Must test k_initial in perpetuity even after its first post-Whisk block proposal
2. k_initial is a set of values of size equal to the current validator count

To solve problem 1 a validator must be able to differentiate the time ranges [t0,t1] and [t1..]. This may require persisting timing data and increasing state size. However if k_initial could be a single value, checking 2 values per slot is perfectly acceptable.

To solve problem 2 we need to satisfy the following constraints:

• k_initial value that is unique to the current set of commitments
• k_initial value that can be derived from non-historical on-chain data
• Deposit contract cannot be changed to get validators to submit more data

The current spec is problematic because to enforce uniqueness it relies on a specific state's set of commitments = historical on-chain data.

Solution

Turns out that there's one k value that:

• all validators register on-chain using the existing deposit flow
• it is guaranteed to be unique in every state
• its commitment is immutably stored on-chain

That's the validating secret key!

Each validator's public key is guaranteed to be unique and can be used for Whisk's shuffling. Note, the validating secret key allows to de-anonymize trackers almost for free so it's only suitable as the unsafe initial value.

Now apply_deposit can be simplified by getting rid of get_unique_whisk_k and simply using the pubkey as k_G.

def apply_deposit(state: BeaconState, pubkey: BLSPubkey) -> None:
        ...
        # [New in Whisk]
        state.whisk_trackers.append(WhiskTracker(BLSG1Point, pubkey))
        state.whisk_k_commitments.append(pubkey)

Consensus specs PR: https://github.com/ethereum/consensus-specs/pull/3487

Then a validator can assert elected proposer tracker ownership with a maximum of two G1 multiplications per slot

def should_propose_at_slot(slot, keypair):
    k = derive_k_from_keypair(keypair)
    initial_k = keypair.secret_key

    return (
        should_propose_at_slot(slot, k)
        or should_propose_at_slot(slot, initial_k)
    )

Also, for setups with restrictive access to a keypair secret key like the Web3Signer a validator can still check tracker ownership. Below there's a de-anonymization attack that makes the validating secret key unsuitable for whisk. But, a validator can use it as a feature to assert tracker ownership only with a single signature from the web3signer.

Appendix: Why not use validating secret as tracker secret k

Why not use a validator's secret key as the whisk k secret? This way the k_commitment k_G = k * G is the validator's pubkey public_key = secret_key * G.

If that secret signs at least one message where the message is known, the validator's tracker could be de-anonimized forever with a single pairing.

Consider:

• validator private key k
• a message (hashed to G2) H(m) * G_2 and its signature k * H(m) * G_2
• A whisk tracker (r * G_1, r * k * G_1)

You can construct the following pairing check:

e(tracker.r_G, signature) ?= e(tracker.r_k_G, message) 

e(r * G_1, k * H(m)G_2) ?= e(r * k * G_1, H(m)G_2)

r * k * e(G_1, H(m)G_2) ?= r * k * e(G_1, H(m)G_2)

Which links a tracker to the signature's author.

Appendix: get_unique_whisk_k non-determinism

Consider the following example, with 3 validators registering trackers that match the determinsitic tracker of index 2.

.

If validator at index 2 wants to compute its k_initial to discover proposer duties, it will get different results on each step of the example. Most notably the non-determinism exist also after assigning a validator's its initial_k value.

time	get_unique_whisk_k(2)
t0	k(2,0)
t1	k(2,1)
t2	k(2,1)* excludes itself from the check
t3	k(2,1)
t4	k(2,2)