# Whisk: Expensive duty discovery
> **Whisk** is a single secret leader election protocol, providing proposers privacy at the protocol level. Checkout _the_ [ethresearch post](https://ethresear.ch/t/whisk-a-practical-shuffle-based-ssle-protocol-for-ethereum/11763) 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:
```python
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.
```python
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:
```python
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.
```python
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.
![](https://hackmd.io/_uploads/SyrN-Cgp3.png)
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`.
```python
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
```python
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.
<img src="https://hackmd.io/_uploads/HkH_2ybT3.png" alt="timeline" width="500"/>
.
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)

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up