ISS with chain quality

[LefKok]

Description

The current deduplication mechanism of ISS opens the possibility of extreme delays for targeted transactions since they have a single potential proposer per epoch. This can be a downside for blockchain applications as there are no latency guarantees and opens up MEV attacks as well as safety attacks on synchronous L2s/Rollups.

The attack is twofold, firstly Byzantine leaders can censor transactions for an epoch trivially by not proposing them. Assuming 1/3 of malicious leaders this period of censorship extends with successive Byzantine leaders with a 99.998% chance of a good proposer after 10 epochs (assuming n>31). Hence 10*Epoch_length should be the minimum contest period for L2 protocols.

This weakness can be exacerbated to full censorship assuming the adversary is mobile on a single party. This is a realistic attack by targeted botnets. In this case, given the predictability of bucket rotations, the adversary can always kill the controlling leader of a targeted transaction.

Resources

https://arxiv.org/abs/2203.05681
https://arxiv.org/abs/1906.05552
https://eprint.iacr.org/2014/765
https://arxiv.org/abs/2105.11827

Discuss when integrating with Narwhal on potential solutions

[matejpavlovic]

The usage of Narwhal can indeed probably mitigate this problem, as any block will become part of many honest nodes rather quickly, and thus committing as soon as any of these nodes commits any dependent block.

An ISS-internal solution could comprise a VRF as follows, leveraging the ISS bucket mechanism:

Note that each request is mapped to a bucket using a hash function. In basic ISS, the input to this hash function is the request identifier - a tuple of (client id, request number), where the request number is the number of requests submitted by that client so far. If we augment the input to the hash function by (1) the epoch number and (2) the hash of the output of a VRF, the assignment of requests to buckets will be changing unpredictably in every epoch. Thus, only the leader will know that it is selected to propose requests from a certain bucket in a certain epoch, until that leader makes the proposal. Once the proposal is made, it is too late to DoS the leader.

Another similar option would be to leave the assignment of requests to buckets untouched, but assign buckets to segments this way.

This approach, however, comes at the cost of the following concerns:

• The protocol must be symmetric after the leader's proposal (PBFT fulfils this condition, but, for example, HotStuff does not)
• If the ISS segments have length more than 1 (which is generally desirable for performance), the leader "reveals" its identity with the first proposal and is susceptible for DoS attacks afterwards. Liveness is still guaranteed, even with a mobile adversary, but there might still ba a significant performance impact.
• Liveness and request de-duplication becomes probabilistic. The system can probably be tuned to have one leader per bucket on expectation, but there is no deterministic guarantee when a bucket will be assigned to some leader, or that a bucket cannot be assigned to multiple leaders per epoch.