DoS/Extended Censorship Attack via Manipulation of Controlled Stake Distribution

Terminology

Turn: number of slots occupied by same leader

Problem

A leader minting the block whose bank state would serve as input to the stakes utilised in the following leader schedule can adaptively change their stake distribution across nodes that they control such that those nodes will be leader consecutively for a large number of blocks. They can then engage in DoS attacks and covert transaction censorship for a large number of blocks, for a timespan on the order of minutes.

The basic idea for how to achieve this is that an attacker can generate enough nodes such that either they lie dormant on either side of honest nodes in the pubkey-sorted case, or are numerous enough to fill up the requisite number of gaps in the stake-sorted case. Then, after choosing a desired subset of the uniformly pseudorandom points, which may be required to have certain properties, such as not lying on a specific subset constituting 0.03 of all stake, and for our purpose representing consecutive turns, the attacker allocates just the right amount of stake to each of their nodes so as to push nearby honest nodes out of the way of points, thus capturing all the points, with enough budget from their stake to spare.

The current implementation of leader schedule generation can be attacked as follows.

To calculate the probability that out of a sequence of n tosses of a biased coin, there exists a subsequence of k tosses which are all heads, please refer to this link.

Taken cold into python:

import math
import scipy.special as sp

def binom(n, k):
    if n >= k:
        return sp.binom(n, k)
    else:
        return 0.

def prob_reach_threshold(p, n, m):
    sum = 0
    for j in range(1, math.floor(n/m)+1):
        x1 = pow(-1, j+1)
        x2 = p + (n-j*m + 1)/j * (1-p)
        x3 = binom(n-j*m, j-1)
        x4 = pow(p, j*m)
        x5 = pow(1-p, j-1)
        sum += x1*x2*x3*x4*x5
    return sum

This produces the following result, which should be taken with a grain of salt due to numerical errors.

prob_reach_threshold(0.97, 50000., 300.)
0.14835591260356723

So the probability that for 100,000 slots, there exist a consecutive sequence of points, of length 300, drawn from the uniform distribution, that lie to the right of the 0.03 mark in the [0, 1] interval is at least 0.295.

Thus, if one has the situation where honest nodes that stake at least 20000 SOL make up less than 3% of the total stake, or 4.49% of the honest stake, an attacker with 1/3 of a total stake of 10 million can with high probability expend less than 3 million in order to push the remaining vulnerable nodes out of the way, thereby controlling leader slots for 300 consecutive turns, which is approximately 8 minutes. Thus, in approximately 0.3 of epochs, the network is prone to experiencing such an attack.

To see that the fix involving a sort by public key also does not work:

Let the number of honest nodes be 2000. Assume it is possible for an attacker to run 2001 validators, and generate pubkeys such that each of those pubkeys lie on either side of an honest node's pubkeys in the index used for WeightedIndex.

Let the total stake be 10 million SOL. Let the attacker control 1/3 of the stake. Then the attacker controls more than 3.3 million of the stake. Let 99.7% of the value of the honest nodes, i.e. 6.3 million, be controlled by validators staking less than 10000 SOL each. Let these nodes be denoted vulnerable nodes. Then, given 600 consecutive turns (4 slots/turn), with high probability an attacker only has to spend a maximum of 3 million from its staking budget in order to capture all the turns that have fallen into vulnerable nodes (expending in expectation less than 5000 SOL per vulnerable node). Then with probability of at least 0.16, an attacker can control 600 consecutive turns. So the network can be censored for 16 minutes for at least 0.997^600 = 16% of all epochs.

Edit: Actually, this proof is limited and can benefit from more work to yield an attack that can tolerate a larger amount of unfragmented stake.

With pure randomness, the probability of these scenarios happening would be (1/3)^300 and (1/3)^600, which are effectively 0.

Proposed Solutions

[1] Seed the algorithm with the hash of the stake distribution too.

This is still biasable but less exploitable than the current method. This way, to fix n turns, the attacker has no way of manipulating the stake weights without recomputing the entire leader selection algorithm, and must thus expend p^-n parallelism, where p is the proportion of stake owned by an attacker. If not a specific set of points, but rather any consecutive set of n points is all that's required, one requires less compute to get there. How much less requires a more precise routine to evaluate the probability of success.

To make this attack more computationally expensive, the pseudorandom function can be made expensive, for instance by utilising a memory-hard hash function or simply repeating the hash function many times as is allowed in a slot time, or a combination of the two.

For instance, at 80 bits of security, the maximum n of turns that can be captured by an attacker with 1/3 of the stake is 50. So that's 80s or 1min 20 seconds of blackout.

If we do not require a specific set of points, and are happy with any set of n consecutive points landing in attacker controlled nodes, we gain an attack advantage. For instance, if there are only 12,500 turns in an epoch, we already obtain

prob_reach_threshold(0.33333, 12500., 50.)
1.1557201911988424e-20

Which is a 10^4 improvement over 10^-24~2^-80, or shaving 13 bits off the security in the static case.

These are very rough estimates. To properly estimate security, one must write a more accurate evaluator of the probability in question.

Still we have fewer assumptions than in the above two attacks - anyone can carry out the attack, regardless of the distribution of the stakes in the honest nodes. So in fact, this may make this scheme less secure in some sense.

To make the search task even more difficult, the seed can also be hashed together with the last blockhash. This is to prevent an early head start based on a static bank. So an attacker would have to carry out a parallel search attack in 400ms.

The total hash power for bitcoin at peak hash is about 100 Exahash for SHA256. This is about 2^65 hashes/s. If we can use a hashing algorithm that takes 200ms to compute on a single core, say, some number of iterations of RandomX, the total hash power of the bitcoin network would be about 2^42 hashes/second. So for any conceivable attack today, we probably need at most 60 bits of security.

[2] An alternate approach to this is to lock in the stake weights in the past, and use a future blockhash as the seed for the WeightedIndex. This provides the same properties and is probably cleaner to implement. The attack then involves grinding the previous blockhash.

[3] To increase security further, another method can be to use a PoW hash generation specifically for the seed. It must hash the previous blockhash, and difficulty can be set so that one of the validators can propose a winning hash within a small number of blocks. The current leader can choose to include any winning hash. This will make grinding attacks N times harder, where N is the parallelism of all validators. However, this introduces complexity. Further, it will still be computationally intensive and halt network throughput during that period.

But if we have 10,000 validators, and we stipulate a recommended use of 1 core, and with high probability, one in 10,000 miners will find a hash within 200ms, we can dilute an attacker's effective parallelism by 10,000x.

[4]

Recommended Option:

Utilise true pseudorandomness, e.g. via threshold BLS. This has liveness as long as 1/2 (stake-weighted) of honest validators are online, when utilising a (n/3+1, n)-BLS threshold signature.

RANDAO + VDF in the Ethereum case has a very poor maximum lag time (4 minutes+ for Eth's 8s epoch times or 50+ seconds for Solana's leader rotation, given 1.33x VDF advantage) due to requiring the RANDAO reveal period to take place over multiple leader turns due to risk of censorship. Hence, my take is it is unsuitable for time-sensitive protocols like challenge-response.

In contrast, I believe the threshold BLS scheme can possibly lead to <1s maximum lag time, and more likely 400ms. However, communication complexity will inevitably increase with number of nodes.

Nevertheless, even if we assume a redudancy of 4 for a protocol like gossip, one only requires 12.2 Mbps of bandwidth to produce a new source of randomness every block. However, gossip consumes a lot of upload bandwidth. To reduce upload bandwidth consumption, the network can assign random sets of accumulator nodes so that it is improbable that none of them are honest, to be accumulator beacons. Their job is to receive shares and to broadcast randomness to the rest of the network. The broadcast only involves a single signature, hence gossip is an acceptable protocol for it. This increases the critical path by 2, but cuts upload bandwidth from O(n) to a constant or logarithmic factor. For instance, in the n=20,000 case, choosing 80 random beacons makes the probability than an attacker controls all beacons smaller than 2^-120. The beacons will however need a download bandwidth of ~19.2Mbps. The beacon schedule should be rotated similarly to the leader schedule.

A threshold version of RANDAO reveal would have similar liveness properties as threshold BLS.

The threshold BLS method has some level of complexity: a trusted setup is required to scale to 1000s of validators, while a VSS-based DKG must be executed every epoch.

My suggestion, if scale is required and the trusted setup can be made cheap enough (completed within 24 hours), is to get all major validators to perform it periodically, say every 3 months, to reflect a changing validator pool and increase confidence in the trusted setup by its recency.

solana-labs / solana