Electing one producer and validator to use a binomial distribution

[zemyblue]

I propose a method of selecting producers and validators through a binomial distribution.
Each user has a voting power equal to his staking value, and is elected as a produer and validator for that voting power and is rewarded. In addition, producers who seek and prove users who have cheated will be rewarded additionally, and those who find cheating will be punished.

Election logic

The above formula calculates how many times the user_hash, which hashes the seed and the user's public address, is elected to the binomial distribution when it has power of k at the total power w.

Seed

Each block stores a VRF seed and proof value. With this seed, we select the producer and validator group to create the next block.
The seed of the next block is generated as a VRF hash with the seed of the previous block and the private key of the producer.

seed_n+1 = VRFpk(seed_n)

Elected Producer

How to elect Producer

The producer hashes the seed of the previous block with the public address of each user.
Hash uses a way that each value can be made random. (E.g. sha512_256 or xorshift, etc)

• The hash of the previous block's seed plus each user's public address is used as a hash.
• Calculate the probability of selecting a producer with a hash of each user by the election logic of binomial distribution formula. (The number of times to be elected as 0,1,2, ... are returned.)
• If the probability of selection is 1 or more, the user's hash and the (0… n) value are summed up to get the hash again.
  • for (i=0; i<n; i++) { user_hash_i = hashing(user_hash || i) }
• Select the producer with the largest hash among all hashes obtained from all users.

highestHash = 0
producer = nil
for (user <- all validators) {
	hash = hashFunc(seed + publicAddress)
	k = electFunc(votingPower, totalPower, expectedSize, hash)
	for (idx <- k) {
		subHash = hashFunc(hash + idx)
		if highestHash < subHash {
			highestHash = subHash
			producer = user
		}
	}
}

In this case, the producer must use expectedSize to allow more than one person to be elected.

For example, when validators toss each coin they own, they choose the producer who owns the coin with the highest issue year (or issue number) of all the coins on the face.

Elected validators

How to elect validator set

Validtaor is also elected in the same way as a producer is elected.

The difference is that a producer chooses only one user, but when a validator is elected by the election logic, it is determined to be an elected validator.

• The hashed value of the previous block's seed and each user's public address is used as the user's hash. (Use seed + “validator” + public_address to distinguish it from the producer.)
• Calculate the probability of selecting a producer with a binary hash of each user.
• If the probability of selection is 1 or more, select as a validator.

var validatorSet
for (user <- all validators) {
	hash = hashFunc(seed + “validator” + publicAddress)
	k = electFunc(votingPower, totalPower, expectedSize, hash)
	if (k > 0) {
		validatorSet.add(user)
	}
}

What is the appropriate number of validators?

However, when a collection of users selected as validators is called a validator group, an appropriate number of validators should be selected on the assumption that there is a byzantine.

If a group of honest users is called g (good) and a group of malicious users is called b (bad)

g + b = 1

The malicious group should be less than 1/3 to create a block with more than 2/3 agreement.

g > 2b
b < g/2

Then, if the group of users to be voted is t, this group should be a number where b is not two-thirds of the vote, unless at least the block is not created by a malicious group.

t >= b + g/4

If all of the selected groups are honest users, the minimum consensus can be seen.

t < g

Therefore, the minimum voting power required to create a block can proceed without difficulty at least 67% of the total voting power, and even if there are many malicious users at least 50%, the bad block can be prevented from being generated.
That is, the validator group needs to secure voting power of 50% or more of the total voting power.

• Minimum voiting power to generate blocks without problem: 67% or more
• Minimum voting power to prevent malicious block generation: 50% or more

(The expected size is to be obtained by simulation.)

Relationship between producer and validator

Producers and validators are different users because they are selected in different ways. However, a producer can also be elected as a validator by a validator's election formula.
If a producer is also elected as a validator, the reward can also receive both a reward as a producer and a reward as a validator.

[torao]

if highestHash < subHash {

It's a very low probability but when the same subHashes are got and in case highestHash == subHash, the one that comes first in the list of validators has an advantage.

if k > 0 {

I think it's could be a good idea. It's difficult to explain but I have a question for a long time where nodes with many stakes likely to be selected at high frequency and high redundancy. I feel this advantage of frequency × redundancy seems to be excessively. Fundamentally, I think only high-frequency selection should be necessary.

(I'm still reading this but submit it here to save this text.)

[torao]

Question: It looks like only a Proposer who draws a binomial-distributed lottery knows which node won or lose. How can we verify that the node not announced by the Proposer didn't win the role of Validator? Unless it broadcasts all of the random numbers generated for all nodes, it seems that a malicious Proposer could exclude particular nodes that have won as the next Validator.

[zemyblue]

Question: It looks like only a Proposer who draws a binomial-distributed lottery knows which node won or lose. How can we verify that the node not announced by the Proposer didn't win the role of Validator? Unless it broadcasts all of the random numbers generated for all nodes, it seems that a malicious Proposer could exclude particular nodes that have won as the next Validator.

I want to use the validator set of the base Tendermint. This validator set is deterministic and can know every nodes. And my suggestion is to select some validator set from this validator set of tendermint. So any node can't insert or remove any node by themself even if new producer.

[torao]

The previous question was my misunderstanding that the previous Proposer picks-up the next height's Proposer and ValidatorSet. Correctly, only the VRF Hash is stored in a block, and all nodes will pick-up the Proposer and ValidatorSet from VRF hash and their internal state using the above loops.

[zemyblue]

The previous question was my misunderstanding that the previous Proposer picks-up the next height's Proposer and ValidatorSet. Correctly, only the VRF Hash is stored in a block, and all nodes will pick-up the Proposer and ValidatorSet from VRF hash and their internal state using the above loops.

Yes, that's right. So every node can know same producer and validator set if the round is equalized.

[torao]

Regarding the issue pointed out in #22 in a recent discussion, "the number of multiple-winning for a node can exceed the Byzantine assumption", this is a common problem with an algorithm that allow multiple winners. So I think this is also applied to this binomial-based algorithm.

For instance, assuming a practical blockchain network with about 25 ValidatorSet, the BFT assumption is n=8, therefore a node or nodes with stakes greater than or equal to 8 may get 1/3 n+1 opportunities in consensus. Considering the total amount of stakes, nodes with stakes greater than n=8 are not uncommon cases.

[zemyblue]

Regarding the issue pointed out in #22 in a recent discussion, "the number of multiple-winning for a node can exceed the Byzantine assumption", this is a common problem with an algorithm that allow multiple winners. So I think this is also applied to this binomial-based algorithm.

For instance, assuming a practical blockchain network with about 25 ValidatorSet, the BFT assumption is n=8, therefore a node or nodes with stakes greater than or equal to 8 may get 1/3 n+1 opportunities in consensus. Considering the total amount of stakes, nodes with stakes greater than n=8 are not uncommon cases.

Yes, if the byzantine is lower than 1/3 among total validators and select some validators without don't using all validator, the case that the byzantine is greater than 1/3 in the selected validators may be exist. And both #22 and #23 have this problem.

We can't avoid this situation and can't protect. So, I think we should be reinforced with the algorithm that detect the validator who make this problem, and punish more powerful.

In this suggested algorithm, the byzantine producer can start to make this problem, since the producer and validator set is selected by different way. And the byzantine validator set should give the help for it. And the block fork by this problem is difficult to keep over the 3 block. Because the byzantine producer can't recognize the producer of next 2 block. So if the producer of next 2 block is honest validator and detect the byzantine validator's illegal, the honest validator can punish the byzantine producer and validator sets. Therefore, I think the situation can be receovered.

[zemyblue]

We decide to use #22.
So this issue is closed.