ISS with chain quality #91
Replies: 3 comments 2 replies
-
|
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:
|
Beta Was this translation helpful? Give feedback.
-
|
I am not clear on how you propose to use the VRF? Why can't the adversary evaluate it before the epoch start? |
Beta Was this translation helpful? Give feedback.
-
|
Exactly, that's the high-level idea. The leader sends out a proposal and attaches a proof that it indeed has a right to make this proposal. Nobody else can know who the rightful proposer is until the proposal is out. Similarly to Algorand or Flightpath. |
Beta Was this translation helpful? Give feedback.
-
|
A more general thought on the issue: (d, k)-mobile adversaryAny (multi-)leader-based protocol, where there exists a request r, such that at most k leaders are responsible for proposing r at any given time, is vulnerable to an adversary that is mobile on k parties, as long the adversary is fast enough. By fast enough, we mean that the adversary can learn enough in advance which leaders will become responsible for proposing r, and can start controlling these leaders by the time they can propose r (or, more generally, perform any task that only the leader can perform with respect to r). Let d be the time the adversary needs to switch from one node to another d and let us define such an adversary as (d,k)-mobile. Vulnerability of leader-based protocolsIn classic single-leader protocols like PBFT, k = 1 (as there is only a single leader at a time) and the time the adversary has to switch from one party to another is at least as long as the view change timeout. Thus, PBFT is vulnerable to a (view-change-timeout, 1)-mobile adversary. With ISS, even though multiple leaders can propose in parallel, for any request r, there is only a single leader at a time that can propose r (to improve performance by preventing the proposing of duplicate requests). The adversary has the whole epoch to switch from one node to another, making ISS vulnerable to a (duration-of-epoch, 1)-mobile adversary. Mitigation in ISSHowever, giving up (at least partly) the duplication prevention mechanism of ISS, we can effectively reduce the set of adversaries ISS is vulnerable to. We can increase k by allowing, at any point in time, a request to be proposed by k leaders instead of just one. While potentially introducing up to k-fold request duplication and thus reducing performance, this approach makes ISS only vulnerable to a (duration-of-epoch, k)-mobile adversary. In combination with optimistic techniques for mitigating request duplication during failure-free execution, such an approach might increase ISS' resilience without too severe of an impact on general performance. |
Beta Was this translation helpful? Give feedback.
-
|
We are in total agreement, this is why we left the deduplication to the client/application layer for Narwhal. If the client needs censorship resistance it can duplicate widely (even f+1) and pay more fees whereas if the client wants low fees it sends the transaction to a single leader who might or might not add it to the DAG. My sense is that the way forward is some combination of random assignment (either through VRF or through a randomness beacon) coupled with the relaxation of the strict single proposer per epoch |
Beta Was this translation helpful? Give feedback.
-
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
Beta Was this translation helpful? Give feedback.
All reactions