sampling validators in precommit step #1355

soring323 · 2023-09-13T12:03:24Z

soring323
Sep 13, 2023

Protocol Change Proposal

Summary

Hello. I wanna use sub group of validatorSet in precommit step.
For example.
consensus/types/height_vote_set.go

func (hvs *HeightVoteSet) addRound(round int32) {
	if _, ok := hvs.roundVoteSets[round]; ok {
		panic("addRound() for an existing round")
	}
	// log.Debug("addRound(round)", "round", round)
	prevotes := types.NewVoteSet(hvs.chainID, hvs.height, round, cmtproto.PrevoteType, hvs.valSet)
        
       // precommitValset, sub group of hvs.valSet. 
	precommits := types.NewVoteSet(hvs.chainID, hvs.height, round, cmtproto.PrecommitType, precommitValset)
	hvs.roundVoteSets[round] = RoundVoteSet{
		Prevotes:   prevotes,
		Precommits: precommits,
	}
}

something like this.
In this case, valIndex of Vote message is wrong so it can be flxed again to get from precommitValSet.
Some validator will exclude in precommit voting mechanism.
Looks working correctly but I'm failing byzantian_test (consensus/byzantian_test.go), test case failed because of evidence problem.

Problem Definition

Decrease more to reduce communication complexity.

cason · 2023-09-13T12:40:45Z

cason
Sep 13, 2023

Can you define in more detail what you mean by "sub group of validatorSet"?

For understanding, the validator set defines: (i) the validators (using public validator keys) and (ii) the voting power associated to each of them.

The vote set abstraction uses the validator set (valSet field) for: (i) configuring the maximum number of votes expected, (ii) computing the total voting power of the validator set, from which what really matters is the 2/3 of it; (iii) check if an added vote belongs to one of the validator keys in the validator set.

0 replies

cason · 2023-09-13T12:41:23Z

cason
Sep 13, 2023

Looks working correctly but I'm failing byzantian_test (consensus/byzantian_test.go), test case failed because of evidence problem.

Can you be more specific? For instance, can you provide the output of the test unit that is failing?

0 replies

cason · 2023-09-13T16:26:19Z

cason
Sep 13, 2023

It's not important how to take sub group.

Actually, it is. The protocol is correct as long as a set of assumptions regarding the composition of the validator set and the distribution of voting power between correct and Byzantine processes are observed. And its based on this information that we can produce the quorums required for ensure a correct operation of the protocol. Probably it is worth noting that defining quorums based on the system size and failure assumptions is an assumption of any consensus protocol I am aware of, not only for Tendermint.

Regarding the composition of the quorums (a quorum is the minimum size of a subset of validators, weighted by voting power, which have to vote identically to enable state transitions on the consensus protocol), the main property that has to be observed is that any two quorums must have an intersection that includes a correct process. In the standard scenario, considered by the pseudo-code of Tendermint, in a system with 3f+1 processes, where we tolerate up tof processes presenting Byzantine behavior, we need any two quorums to intersect by at least f+1 processes. The simplest way to achieve this property is to make all quorums of the same size, which is 2f+1.

Adopting different quorums (sizes) for different steps or rounds of the algorithm is something never really considered for Tendermint. I mean, we are unaware of any proposal in this direction that has been evaluated and proved correct. There are, however, in the literature proposals of flexible quorums for consensus algorithm, several of them. So, this approach is feasible, in general terms, but never really considered for Tendermint.

To conclude, your proposal of having 2/3+ standard quorums for the Prevote step (equivalent to 2f+1) and smaller quorums for the Precommit step, say 2/3 (equivalent to 2f) does not observe the above mentioned core property of quorums in distributed algorithms. The reason is simple: we can have two quorums, with minimal sizes, which intersection will be entirely composed by Byzantine processes (in a system with 3f+1 processes, the minimal intersection between 2f and 2f+1 quorums contains f processes). This leads to an incorrect protocol.

0 replies

soring323 · 2023-09-13T12:53:00Z

soring323
Sep 13, 2023
Author

It's not important how to take sub group. we can take 2/3 or more small validators from hvs.valSet.
we've replaced voteSet with this sub group, so totalPower will change automatically according to them.
for example, if we have 4 validators (byzantian_test case 1), in this case, we will take 3 validators in precommit step as a sub group.

They all have same 30 as a voting power, we've changed precommit valSet as a subgroup, so total power is just 90.
There is no doubt in this part.

to avoid validator index issue in vote message, I've customized consensus/state.go file like this

/ CONTRACT: cs.privValidator is not nil.
func (cs *State) signVote(
	msgType cmtproto.SignedMsgType,
	hash []byte,
	header types.PartSetHeader,
) (*types.Vote, error) {
	// Flush the WAL. Otherwise, we may not recompute the same vote to sign,
	// and the privValidator will refuse to sign anything.
	if err := cs.wal.FlushAndSync(); err != nil {
		return nil, err
	}

	if cs.privValidatorPubKey == nil {
		return nil, errPubKeyIsNotSet
	}

	addr := cs.privValidatorPubKey.Address()
	valIdx, _ := cs.Validators.GetByAddress(addr)

	if msgType == cmtproto.PrecommitType {
		valIdx, _ := cs.Validators.PrecommitSe.GetByAddress(addr)
		if valIdx < 0 {
			return nil, fmt.Errorf("validator %v not in precommit validator set", addr)
		}
	}

	vote := &types.Vote{
		ValidatorAddress: addr,
		ValidatorIndex:   valIdx,
		Height:           cs.Height,
		Round:            cs.Round,
		Timestamp:        cs.voteTime(),
		Type:             msgType,
		BlockID:          types.BlockID{Hash: hash, PartSetHeader: header},
	}

	v := vote.ToProto()
	err := cs.privValidator.SignVote(cs.state.ChainID, v)
	vote.Signature = v.Signature
	vote.Timestamp = v.Timestamp

	return vote, err
}

In this case, validators which don't included to sub group, will not make vote at precommit step.
It's okay.

In byzantian test case 1, I'm getting timeout issue. Of course at block height 2, duplicated prevote doesn't success in consensus so did not more state machine to precommit step.
But I'm getting time out issue.

0 replies

alijnmerchant21 · 2023-09-13T13:09:59Z

alijnmerchant21
Sep 13, 2023

Thanks @dedicatedDev for opening this issue. I understand your attempt to - At the Precommit step, take more smaller subgroup than the prevote validator group.

What I don't understand is the what you are trying to achieve by this change. To me it seems unreasonably complicated to change the protocol. Even if were done (again fairly complicated) it would also introduce liveliness and security issues.

Again, if we could understand the final goal, we might be able to suggest alternatives.

0 replies

soring323 · 2023-09-13T13:23:36Z

soring323
Sep 13, 2023
Author

final goal, we wanna decrease telecommunication complexity and link 1k+ validators

0 replies

soring323 · 2023-09-13T17:45:53Z

soring323
Sep 13, 2023
Author

okay, but I guess quorum is defined as a 2/3 of total power + 1 in current implementation.
if we replace hvs.valSet's group, in this case, it is change automatically in current implementation.
so what kind of quorum, it's not important I guess. if we replace valSet with sub group, protocol automatically change quorum according to the formula and it's also 3f+1 voting.
About weight problem, in test case, you've used same weight so I guess I don't see any kind of issue of that.

And then, prevote, and precommit is separately independently so if we use different quorum or not, it doesn't affect pervious step at all.

0 replies

alijnmerchant21 · 2023-09-14T11:34:49Z

alijnmerchant21
Sep 14, 2023

This is an interesting conversation and I suggest we convert this issue into an discussion and brainstorm further.

0 replies

melekes · 2023-11-07T08:50:13Z

melekes
Nov 7, 2023
Collaborator

There are, however, in the literature proposals of flexible quorums for consensus algorithm, several of them

Indeed, for example: https://fpaxos.github.io/

final goal, we wanna decrease telecommunication complexity and link 1k+ validators

That's a great goal 👍 We're (@informalsystems) working on reducing the amount of data sent between peers, specifically block parts and mempool transactions (see https://forum.cosmos.network/t/proposal-cosmos-hub-adopt-the-skip-block-sdk/11641/35?u=melekes).

As for your proposal, I'd love to see a prototype (plus a TLA+ spec to ensure correctness and liveness properties) for an algorithm you've described. Do you have time to work on this?

1 reply

soring323 Jan 8, 2024
Author

yep, I've already fully implemented this.
I've checked with the current cosmos SDK, it working well

sampling validators in precommit step #1355

Uh oh!

soring323 Sep 13, 2023

Protocol Change Proposal

Summary

Problem Definition

Replies: 9 comments · 1 reply

Uh oh!

cason Sep 13, 2023

Uh oh!

cason Sep 13, 2023

Uh oh!

cason Sep 13, 2023

Uh oh!

Uh oh!

soring323 Sep 13, 2023 Author

Uh oh!

alijnmerchant21 Sep 13, 2023

Uh oh!

soring323 Sep 13, 2023 Author

Uh oh!

soring323 Sep 13, 2023 Author

Uh oh!

alijnmerchant21 Sep 14, 2023

Uh oh!

melekes Nov 7, 2023 Collaborator

Uh oh!

soring323 Jan 8, 2024 Author

soring323
Sep 13, 2023

Replies: 9 comments 1 reply

cason
Sep 13, 2023

cason
Sep 13, 2023

cason
Sep 13, 2023

soring323
Sep 13, 2023
Author

alijnmerchant21
Sep 13, 2023

soring323
Sep 13, 2023
Author

soring323
Sep 13, 2023
Author

alijnmerchant21
Sep 14, 2023

melekes
Nov 7, 2023
Collaborator

soring323 Jan 8, 2024
Author