Set accum of freshly added validator -(total voting power)

[liamsi]

This PR sets the Accum of a added validator to -(totalVotingPower + (totalVotingPower >> 3)) in state/execution:updateValidators.
It is a potential fix for #2718 and #2809
see: #2785 (comment)

Big thanks to @melekes for an early sanity check!

• Updated all relevant documentation in docs
• Updated all code comments where relevant
• Wrote tests
• Updated CHANGELOG_PENDING.md

[codecov-io]

Codecov Report

Merging #2785 into develop will increase coverage by <.01%.
The diff coverage is 52.38%.

@@            Coverage Diff             @@
##           develop   #2785      +/-   ##
==========================================
+ Coverage    62.69%   62.7%   +<.01%     
==========================================
  Files          212     212              
  Lines        17327   17303      -24     
==========================================
- Hits         10863   10849      -14     
+ Misses        5552    5544       -8     
+ Partials       912     910       -2

Impacted Files	Coverage Δ
state/execution.go	72.79% <52.38%> (-2.11%)	⬇️
libs/db/remotedb/remotedb.go	36.84% <0%> (-4.69%)	⬇️
consensus/reactor.go	65.64% <0%> (-0.83%)	⬇️
consensus/state.go	80% <0%> (+0.35%)	⬆️
privval/ipc_server.go	70.37% <0%> (+5.55%)	⬆️

[melekes]

🍇 🍷

[ebuchman]

This is a breaking change so will hold off on merging for now

[ValarDragon]

I still think we should multiply by a constant (maybe 2 or 3)

Without a constant, it will be advantageous to still unbond / rebond in a lot of scenarios to increase your accum.

[liamsi]

The scenario is what you describe in #2718 (comment) right?

By using a multiplicative factor, e.g. 2, this would rather mean you can split up in 3 or more validators and do a similar thing you described, is that right? I can change it to 3. And we can do a proper decoupling after launch, OK? (I find such a constant a bit weird though; we need a more solid argument for choosing 2 or 3 explaining the rational behind the choice) @ebuchman @ValarDragon @milosevic @cwgoes

[ValarDragon]

No, the attack is mitigated in all cases by using such a constant. (It is not eliminated, solely mitigated) The mitigation comes from unbonding always having a cost for a validator that would normally be proposing, whereas in the described system, there is no cost / it may be profitable to do so anyway. (As suppose your the lowest, then unbonding / rebonding still helps you become not the lowest)

The idea being simulated is when you initially bond, there is a period where you aren't eligible to propose and your accum isn't increasing, but you do contribute to total stake. Perhaps its better to just do that directly.

[liamsi]

I would propose to properly write down the math and fix this more complex attack (which involves splitting up validators) in a follow-up PR. How does that sound to you?

[ValarDragon]

I guess. I feel like its worked out in the issue, but given the discussion there perhaps I didn't explain it well enough or I'm missing something. Also correctness of the entire thing can't really be proven, since the algorithm itself is quite biasable. (We'd need a careful definition to prove any deterministic algorithm here secure) So at best it can show that it mitigates the gain from this attack. The constant was just meant as an easy way of simulating you not getting to be a proposer for the first n blocks after you bond, so that would still be better.

[cwgoes]

Hmm, how about multiply by 10 and divide by 9?

[ValarDragon]

Hrmm, we can multiply by 1.125 quite efficiently, x + (x >> 3)

[cwgoes]

that works!

[liamsi]

OK, x + (x >> 3) works but we'd need to make sure we do not overflow here. vals.TotalVotingPower() is only bound by MaxInt64 (via clipping). Computing x + (x >> 3) could potentially overflow. A consistent way to deal with this would be to clip (again) in the case of an overflow. Alternatively, we could enforce a stricter bound on totalVotingPower.

[SunSchizzzz]

[jaekwon]

let me think about this right now... it looks good, just want to double check and see if there might be unintended consequences.

[jaekwon]

It's not sufficient to set new validators to -totalVotingPower because eventually the average accum can drift negative, and even -totalVotingPower may be insufficiently negative for this to have the desired effect.

For completeness, I suggest that we also shift the accum for every IncrementAccum iteration (by the negative of the avg accum) so that at the end of IncrementAccum, the avg accum is 0 or close to 0. Then, I think we can do what is done here, setting new validators to -totalVotingPower.

Related: #2809

The adding and avg'ing should be done via Int/big.Int. The avg I think should be well within the bounds of int64...

[liamsi]

Thanks @jaekwon!

I suggest that we also shift the accum for every IncrementAccum iteration (by the negative of the avg accum)

We would need to be careful here: if the avg accum is already negative, we would be actually increasing the accum if we shift by the negative avg accum.

This means we would need to do sth along the lines of:

if avgAccum > 0 {
    // shift by negative avg accum
    val.Accum = safeSubClip(val.Accum, avgAccum)
} else {
    // shift by already negative accum
    val.Accum = safeAddClip(val.Accum, avgAccum)
}

Or am I misunderstanding this?
cc @jaekwon @cwgoes @ValarDragon

OK, NVM. After talking to Chris: substracting the avg makes more sense: the drift could be in both directions (positive or negative). I'll update the code accordingly.

[cwgoes]

We would need to be careful here: if the avg accum is already negative, we would be actually increasing the accum if we shift by the negative avg accum.

I think that is the goal here - we want to recenter the accum distribution at zero, each round. That prevents the accum from "drifting negative" and seems like it should ensure that a validator added with -total_accum is last in line (although we should more formally analyze this). If we add the accum when it is negative, we'll keep decreasing an already-negative average accum, which is not what we want.

I think these are some properties the proposer election algorithm ought to have (cc @ValarDragon), which it would be nice if we could test for or prove on paper:

1 Last in line

1If a validator joins the bonded set, and no other power changes happen afterwards, they will be the last in the queue to propose (all other n - 1 validators will propose first, and some may propose multiple times).

2 Consistent

If no validator power changes happen, the proposer election should be completely cyclical in some repeating period (the exact sequence of proposers repeats).

3 Fairly stake-proportional

Regardless of what other power changes happen, the fraction of proposals f by some validator V bonding at round n and unbonding at round m, at constant power p throughout, in the limit of the difference m - n to infinity, should equal p divided by the average total power over those rounds P: lim ((m - n) => ∞) f = p / P

Any other properties we think we want?

[ValarDragon]

Nice writeup @cwgoes! I don't think those properties detail the ideal stake election algorithm though.

1. Suppose a new validator comes in with 20% of all stake (or any large fraction), and there is already a validator with .1% of stake who just proposed. It doesn't make sense for the 20% to be blocked on the .1%.

• Instead what I want here is a delayed start. So a new validator first only has their stake contribute to consensus but not proposing for d blocks. Then once they get to join the proposer set, they start as if they had just proposed in the current setting, so they're at the bottom. (Similar idea as to what you had mentioned during last weeks tm call)

2. This basically discredits any/all randomized election algorithms. I think randomized algorithms are far better due to ability to prevent grinding the ordering of the proposer distribution. I don't understand why consistency is even important in a deterministic consensus algorithm.

3. I don't think this is correctly formalized. You can't take an average of infinite sequence outside of a limit. The formalization at that infinite case also isn't very informative, since you do expect your power to fluctuate alot. Additionally, you want properties to hold at smaller scales, we don't really get to make expectations all the way out to infinity. A better formalization / model in my opinion:

• Pick an epoch size e, and assume there are no power changes within an epoch. Your power in epoch i is p_i, and the total power in epoch i is P_i. Forall n \in \Nat, the fraction of blocks f you propose is epsilon(n) + \sum_i=0^n p_i / P_i, where for all n > n_0, -acceptable_rational_function(n) < delta(n) < acceptable_rational_function(n). Acceptable rational function is a rational function which approaches 0 as n increases, and this function should be such that we consider it okay as long as the deviation is bounded by plus or minus acceptable_rational(n). (If we had secure randomness, we could instead make epsilon a negligible function)

4. Unbiasability argument
   I think there needs to be some component of this. We're in a deterministic system, but we don't have to be. There are cool ways we can get secure randomness. (VDF + Avalanche RANDAO) This is clearly something that can't be done until postlaunch though.

[cwgoes]

In addition to doing this, I wonder if we should guard the input values (passed by the ABCI application) and require that the powers passed by the application sum to no more than MaxTotalVotingPower. Otherwise, if they ever did sum to more than MaxTotalVotingPower our proposer selection algorithm would no longer have the same properties (and the application might not immediately notice).

[liamsi]

I added checks for updating and adding validators in c445aa4
These checks rejects single validators whose update would exceed MaxTotalVotingPower on the fly (even if another update, say removing another validator would make this a valid update). Not sure if we should instead look on the total updates first and reject the whole set of updates instead.
Oh actually, the whole set will be rejected if updateValidators errs.

[ebuchman]

So this should be impossible now given updateValidators is supposed to prevent it, correct? Should we panic here instead to indicate this?

[liamsi]

Yes, makes sense. Thanks @ebuchman!

[ebuchman]

Shouldn't we be able to get rid of all the safe clipping now because of this max?

[melekes]

🌮

[ebuchman]

Still reviewing ... but publishing this half way

[ebuchman]

Looks good - just a few comments/suggestions left.

Thanks everyone for the help designing and reviewing this.

Last thing, I think we need more tests, especially to check that this change has the desired effect on proposer distribution and that running IncrementAccum averages the Accum distribution as expected. These tests may need to be written in the state pkg, but surely we can have some more tests about this stuff in types too.

[ebuchman]

Does this take effect in the vals? In the old code we were updating the heap again after the subtraction

[liamsi]

The heap is only there to compute mostest (which will be returned at the end of this method). In the old code the heap was updated because only after times iterations, the proposer was set (and mostest was overwritten on each iter). Now the heap is not used after the subtraction (but rebuild on every call of IncrementAccum). And yes, this should take effect on the vals (mostest is a pointer to a val in vals).

tendermint/types/validator_set.go

Lines 72 to 88 in 7213869

	validatorsHeap := cmn.NewHeap()
	for _, val := range vals.Validators {
	// Check for overflow both multiplication and sum.
	val.Accum = safeAddClip(val.Accum, safeMulClip(val.VotingPower, int64(times)))
	validatorsHeap.PushComparable(val, accumComparable{val})
	}
	// Decrement the validator with most accum times times.
	for i := 0; i < times; i++ {
	mostest := validatorsHeap.Peek().(*Validator)
	// mind underflow
	mostest.Accum = safeSubClip(mostest.Accum, vals.TotalVotingPower())
	if i == times-1 {
	vals.Proposer = mostest
	} else {
	validatorsHeap.Update(mostest, accumComparable{mostest})

[ebuchman]

So this should be impossible now given updateValidators is supposed to prevent it, correct? Should we panic here instead to indicate this?

[R-Santev]

We need to limit voting power then.

Yes, absolutely agreed. I think the existence of these clipping-arithmetic functions is not quite right, better to limit the voting power inputs and panic if we ever hit min / max values (which should never happen if we limit the inputs appropriately).

Hello! I am interested in why you think that using some type of Big.Int for Example is not right. Would you like to explain me?

Thanks in advance!