Introduce randomness into proposer selection?

[melekes]

"The round-robin algorithm is deterministic for choosing the next leader. So even if there is a timeout, the attacker will know exactly who will be the next proposer and then just direct all his bots to simultaneously attack that proposer and keep doing this in sequence." Joe765 on https://riot.im/app/#/room/#cosmos:matrix.org

[adrianbrink]

@sunnya97

[srmo]

I‘d like to add my previous comment:
Interesting point. A non-deterministic rotation also mitigates potential scenarios in which clients try to gain an advantage via short routes to a validator(s mempool) - i.e. proposer to have their transaction being favored by the proposer.
Which could also be mitigated by adding a randomized tx selection logic from the mempool.
Seeing that the "TM in a nutshell" speaks of customizable "mempool-selection-logic" for the proposer, which isn't there yet.

If mempool inclusion depends on the order when a tx is seen first on a node (i.e. checkTx decision), then the proposer rotation needs to be randomized.

[KrzysiekJ]

Seems related to #574. If ABCI server creators want to reward validators for availability, then one way of doing this is to reward block proposer (after #338 is fixed). It is therefore important that proposer selection is unbiasable and evenly distributed.

[robertdavid010]

Fairly straight forward to create simple lottery based on commit-block hash(-1).

Reduce validator public key and block hash to common base, and make a best match.

[KrzysiekJ]

Block hash can be manipulated and therefore it is not a good entropy source.

[robertdavid010]

Ok good to know. Certainly an immutable source of entropy must exist in the blockheader though. I will keep an eye out.

[robertdavid010]

BTW for clarification, which blockhash can be manipulated? Certainly none stored in the permanent blockchain and used as reference, or is this a seperate blockId??

[KrzysiekJ]

Block hash cannot be manipulated after block is confirmed, but it can be manipulated beforehand, for example by adjusting the set of transactions.

[robertdavid010]

Ok. This is why i suggested using the previous block hash. ie. the most recent immutable block in the blockchain. This should be trustable pre-proposal?

[adrianbrink]

The problem is that the current proposer could adjust the block in a way to give himself a higher chance of being selected.

[robertdavid010]

With the hash output being random for any current state, the best any validator could do would be to "brute force" a better result. Would this not mean somehow intentional disruption of proposal process? If every validator tries to brute force it, no transactions get processed, so no point in brute forcing?

[robertdavid010]

As far as I can tell, the only way to exploit it would be as a proposer, and noncing the current block state to try and get a subsequent blockhash which would again make you the proposer. However there is no direct advantage or incentive to this, so it's hard to see much affect of even a hostile actor (you end up where you started, with a deterministic round initiator), while to non-hostile actors there is incentive to honestly participate in the lottery to the extent it does increase the robustness of the network. Am I correct?

[adrianbrink]

I would say that a hostile actor has all incentive to try and brute-force it to become the next proposer again. It would enable him to order transactions on the next block too. Of course, this becomes super obvious if done repeatedly, but if a proposer only does this every 1000 blocks he can use it to manipulate the transaction ordering for the application (example a DEX and the proposer every once in a while can cheat the system for extra profit).
This would be a significant change and we need to be completely sure that there is no way to game it.

[melekes]

@srmo good point! we're planning to add some kind of priority field so the mempool could sort its txs

[robertdavid010]

Sounds very good. TBH in evangelizing for Tendermint, much technical resistance based on this issue in general for BFT. I suggest a solution would go a long way to broader acceptance of Tendermint. It seems the only problem to solve is whether or not the source of "entropy" in proposer selection is fully known prior to block publishing by consensus round. If this can be prevented, the the "simple lottery" concept could work?

[robertdavid010]

Transaction payload is considered primary source of non-determinism in lottery systems like Bitcoin PoW. Added nonce is controllable (deterministic) aspect. I suppose what is needed is second/unpredictable source of entropy... Interesting aspect of other BFT's (what I understand original Ripple protocol did), is provable consensus on transactions(?) not just blocks(?). AFAIK, Ripple votes on each transaction. If transaction ordering could be "fixed" (ei. added transacition merkle tree) woud this eliminate "transaction ordering manipulation"? Essentially an added proof of "mempool state" among validators.

[HoOngEe]

What do you think of the randomized leader election proposal? The CodeChain team is considering to introduce randomized leader election in Tendermint.

[melekes]

https://medium.com/cypher-core/tendermint-2019-criticize-by-creation-not-by-finding-fault-ae49fb54f757?

[erikgrinaker]

https://medium.com/codechain/tenderand-randomized-leader-election-in-tendermint-a3663d863479

[ValarDragon]

I'm unaware of any deterministic leader election algorithm that maintains some strong notion of fairness in the presence of weight changes at the moment. (Our current one does not)

Strongly in favor of randomized proposer election, with the sequence of subsequent proposers known {N} blocks ahead of time!

[cmwaters]

Does randomized proposer election become easier with epoch-based validator sets (in terms of achieving fairness)?

[olahouze]

Hi

The solution "randomized proposer election" is implemented in which version of tundermint?

[ValarDragon]

Does randomized proposer election become easier with epoch-based validator sets (in terms of achieving fairness)?

Nope! Its pretty easy to get fairness without epochs in the randomized case. (What you'd do is define a lagged fairness property. e.g. if I get a stake update in block N, I have a fair probability for this in block N + k, for a fixed k.)

This is because using randomness, at block N, you can sample a proposer for height N+k independent of all past samplings, and this sample can be perfectly Uniform wrt the stake distribution at height N.