search

dedis / cothority

Scalable collective authority
Other
427 stars 104 forks source link

Leader can collect txs, drop them and never create a block #1963

Open Gilthoniel opened 5 years ago

Gilthoniel commented 5 years ago

So basically we need to introduce a way for followers to detect that the leader is malicious. It's not straightforward how to do this as we don't want to open a way for attackers to trigger view changes all the time.

The first idea coming in mind would be to trigger a view change if no block have been created for a while. Even if there is no transaction and thus no block created, it's not a big deal to trigger a view change because that means there is no load in the system so the view change wouldn't slow down anything. But I'm not sure what should be the timeout because 10 or so intervals looks tiny. I guess the question is how much we accept the system to be stuck if a leader is malicious .. one hour ?

kc1212 commented 5 years ago

We had a discussion with @LefKok on this problem some time ago. IIRC, the idea was to do periodic leader rotation, i.e., every block is created periodically regardless of whether there are transactions and every subsequent block is created by the next leader in the roster list. A group of attackers can DoS the system for at most n/3 blocks. Implementing it I suspect will be tricky, especially around the timeouts.

kc1212 commented 5 years ago

Actually this paper describes a rotating leader algorithm (section IV-D) https://eprint.iacr.org/2019/676.pdf

ineiti commented 5 years ago

I know the author of the paper - where has it been submitted? I see it's quite new...

The leader should definitively be rotated on a regular basis.

Also, do the followers check now if the transactions they sent to the leader have been included? Or is that the clients' job to do?

jeffallen commented 5 years ago

Checking that txns are accepted is the responsibility of the client.

ineiti commented 5 years ago

Checking that txns are accepted is the responsibility of the client.

In both Ethereum and Bitcoin, once a transaction is submitted to the network, it will be gossipped around until it is included in a block (or until it times out, probably). This is why I thought that having the same functionality in ByzCoin might be worth it: keep sending the transactions to the leader, until the transaction is included in a block, either as being accepted, or refused.

LefKok commented 5 years ago

Censorship resistance cannot be offloaded to the clients. It works on Bitcoin or Ethereum because they are leaderless and permissionless protocols. For ByzCoin with a stable leader, this is not the case.

A simple rotating leader should suffice for static adversaries and is the simplest path. Some protocols like Tendermint and Hotstuff do it every round, but for the permissioned settings of ByzCoin we can do it every X rounds and then censored transactions will have an expected 1.5X commitment time. Could you elaborate on the exact use-case? For most applications censorship-resistance is not crucial

Other interesting ways are Threshold encryption ala Calypso (Used in Honeybadger BFT) or Leaderless consensus (https://arxiv.org/abs/1809.01620)

ineiti commented 5 years ago

@LefKok - when you write cannot be offloaded to the clients - does that mean that the nodes should take care of making sure a transaction goes in, and eventually complain that the leader did not include their transaction? In the case of ByzCoin, of course.

We're trying to figure out if the nodes should keep track of which transactions got in and which did not make it in a block. Should a node keep a transaction he sent to the leader in his list, and send it again for the next block if it hasn't been included?

LefKok commented 5 years ago

This would be a way to solve it, but a fairly complicated one since now you need to keep timers for each transaction. Instead, the elegant solution is to make sure censorship cannot happen for a long period of time.

This is achieved by making sure that transactions to be committed have an equal chance to be added (proportional to fees of course in the permissionless setting). If all leaders where honest this would be the case anyway, but a malicious leader can ignore. As a result, the solution is to either hide the transactions to be committed (Honeybadger BFT does that), make the protocol leaderless (Block-Mania does this), or switch leaders periodically (simplest to implement, but a bit slower as censorship-resistance holds only during honest leaders).