What to use as a seed for VRF random number generation?

torao commented 4 years ago

We assumed the VRF seed as a volatile value such as a block hash, but in more detail, there are several options:

Height, Time, TotalTxs
LastCommitHash // commit from validators from the last block
DataHash // transactions hashes from the app output from the prev block
ConsensusHash // consensus params for current block
AppHash // state after txs from the previous block
LastResultsHash // root hash of all results from the txs from the previous block

It seems to be possible to use fields from one or more previous blocks instead of the current one (I don't know exactly what all the fields mean). Or, we may also use a combination of them such a sha256(LastResulstHash || Height). What is the best way for VRF seed?

Security guarantee in the cryptographic context.
A method that cannot be intentionally operated by an adversary.

zemyblue commented 4 years ago

I think there will be no problem using anything like your opinion. Because these all values cannot malicious and be expected. Consider the possible case, the leader will be able to regenerate seed value many times in order to get the value that is favorable to leader.

By the way, I think the bigger problem is that in each round, each node cannot be elected leader by the percentage of its voting power. It means if A,B,C,D have 10, 20, 30, 40 voting power and 1 round produces 10 blocks, A, B, C, D should be elected 1, 2, 3, 4 times.

But I'm not sure this VRF random method can be applied to a rule like this. Otherwise, the leader cannot stop generating seed values in favor of the leader.

jckdotim commented 4 years ago

As I know, we need to avoid properties that can be edited by the previous block proposer. In this case, LastCommitHash, DataHash, AppHash, and LastResultsHash seem editable. (because BP can choose tx and validator's vote)
Height, ConsensusHash isn't editable by BP but using these only has another problem. Anyone can predict the overall timeline of every future block's seed. It means that BP can prepare account set for creating all of the future blocks.
My suggestion is sha256(ConsensusHash || Height || BP's address).

jckdotim commented 4 years ago

Let me explain more about 3. I think ConsensusHash and Height isn't editable. end BP's address isn't editable for BP herself but for the other side, they can't predict because of that property.

Let me know if I'm missing something.

zemyblue commented 4 years ago

As I mentioned before, the voting power or staking balance is very important. I don't know the VRF random is real random. The meaning is whether the output values of VRF random are evenly distributed. Only then can we know the proposer is elected evenly by their staking value each round.

So, I think it's good to use the way that combine ConsensusHash and Height and BP's address, or use previous block's some value, but evenly leader selection should be ensured.

torao commented 4 years ago

I forgot an important parameter.

VRF hash generated by previous proposer.

There still be a problem with how it is calculated in Genesis, but this is also one of the values that cannot be edited by any Proposer.

egonspace commented 4 years ago

I think LastComitHash is enough. I think it's a good idea because the provider can't make it arbitrarily, and it's not also predictable

egonspace commented 4 years ago

ConsensusHash is not a good value because it doesn't change very well.

egonspace commented 4 years ago

I was worried that the last_commit_hash value would be the same if the empty block was created, but I checked that there was a different value coming out every time.

zemyblue commented 4 years ago

As we discussed, last_commit_hash can be controlled by selecting advantageously. So we need to use other field for seed.

How about using new seed type? seed is created by using VRF with seed of previous block and add to block with proof of seed. And genesis block use block hash as seed0 exceptionally.

torao commented 4 years ago

Here, I'll summarize the process up to this point.

Requirements

The Proposer or other participants cannot set the intended value, or cannot select an advantageous value by trial and error.
It changes every time with realistic randomness, and no one can predict.
It's information that all participants can know safely.

Candidates

Value	Nature
LastCommitHash	Proposer can select a favorable value by trial and error with PreCommit combination
ConsensusHash	Does not change much
PrevVRFHash or `seed`(?)

It's possible to combine with Height or Proposer's public key to increase randomness, and also possible to make collusion choices difficult by using on two or more previous blocks.

egonspace commented 4 years ago

height0 block: seed0 height1 block: seed1 = vrf_hash(seed0, 1, proposer1_private_key) height2 block: seed2 = vrf_hash(seed1, 2, proposer2_private_key) ...

torao commented 4 years ago

Conclusion

Use the VRF output from the previous block for the next seed. And add the number of round (height?) if the n+1 round isn't completed so that it can be skipped and an n+2 Proposer and Validators can be selected.

egonspace commented 4 years ago

I reopen this issue because we have some problem in the formula seed2 = vrf_hash(seed1, 2, proposer2_private_key)

~We must know the input to verify vrf hash output. So we cannot use private key itself for the input of vrf~
Round information should be put into the input because different producers must be available for each round.

zemyblue commented 4 years ago

I suggest that message for vrf Prove function is composed of seed + height + round.

seed_n, proof = vrf_hash(hash(seed_n_1, height, round), sk)

verify

vrf_verify(hash(seed_n_1, height, round), proof, pk)

We can know the pk from block signature.

So, Block need to store seed, round and proof additionally.

egonspace commented 4 years ago

We can calculate seed_n from proof deterministically so we don't need to store seed in a block. We may just store proof and round in a block additionally.

proof_n = Prove(hash(ProveToHash(proof_n_1), height_n, round_n), sk)

// any validator can know proof_n_1 from block(n-1)
Verify(proof_n, hash(ProveToHash(proof_n_1), height_n, round_n), pk)

torao commented 4 years ago

Output β (VRF hash) can be calculated from Proof π, so it's probably possible to add the only π to the block. However, Algorand's paper §5.2 states that both β and π are included in the block.

This seed (and the corresponding VRF proof π) is included in every proposed block,

As the "don't ever take a fence down until you know the reason why it was put up" suggests, I think it's better to make sure that Algorand hasn't been doing any meaningful checks (that is, it's the same for the β generated from π) on the β contained in the proposal block before our decision.

egonspace commented 4 years ago

I analyzed the source code of Algorand. I found that in Algorand only the seed is stored in a block and proof is stored in proposal payload. https://github.com/algorand/go-algorand/blob/92b9d9a4d89560c547d8c9f56424a7fd0f25443a/agreement/proposal.go#L90

Validator verifies the proof of the proposal payload, and checks whether the seed of block is same to hash of the proof: https://github.com/algorand/go-algorand/blob/92b9d9a4d89560c547d8c9f56424a7fd0f25443a/agreement/proposal.go#L225

The reason why Algorand recorded Seed rather than Proof in the block seems that the value deciding who is the proposer is the Seed rather than Proof. But because any other validators require Proof to validate the block, proposer should have put the Proof in the proposal payload that is out of the block.

And here is another aspect whether we should record both of Seed and Proof or only Proof on the block. If we record only Proof on the block then we should define the ProofToHash algorithm in the LINE Blockchain consensus protocol so any other consensus implementations can calculate the seed hash from Proof.

This seems to be bad from that point of view because a particular vrf implementation must be specified in the protocol, but it is not possible to create an consensus protocol independently of the vrf implementation anyway. This is because nodes that use different vrf algorithms cannot reach agreement anyway.

So my conclusion, therefore, is that we can record only Proof on the block.

zemyblue commented 4 years ago

So my conclusion, therefore, is that we can record only Proof on the block.

I agree @egonspace 's opinion.

However, I have one question. Can the hash that is extracted from proof be difference each VRF library?

zemyblue commented 4 years ago

And we need to discuss about first block. In order to elect next proposer and validator, only hash is used. The proof data is used for verifying the block proposer is validate. So hash is more important data for electing proposer and validator.

I think the reason for Algorand store both hash and proof is because of the first block. This is because hash is required to generate the first block, but proof cannot be generated. If save only proof, the first block cannot elect proposer and validators, because proof for the first block cannot get.

egonspace commented 4 years ago

So my conclusion, therefore, is that we can record only Proof on the block.

I agree @egonspace 's opinion.

However, I have one question. Can the hash that is extracted from proof be difference each VRF library?

Yes it can. Prove(), ProofToHash(), Verify() all have the different output for each implementation. And unfortunately, there is no library that can be called standard. It is thought that a standard vrf implementation should come out before we publish the public blockchain. Otherwise, our consensus protocol should include the vrf implementation.

egonspace commented 4 years ago

This is because hash is required to generate the first block, but proof cannot be generated.

What does it mean? Hash is generated by Proof. If we don't have Proof we cannot generate Hash. We can make a Proof with our hands using a seed message.

If save only proof, the first block cannot elect proposer and validators, because proof for the first block cannot get.

Whether we store only Proof or both of Proof and Hash in the genesis block, we can elect new proposer in second block.

egonspace commented 4 years ago

Here my idea

if height == 1 {
    block.proof = Prove(genesis_proposer_private_key, "seed message")
} else {
    seed = ProofToHash(prevBlock.proof)
    block.proof = Prove(proposer_private_key, hash(seed, height, round))
}

zemyblue commented 4 years ago

Yes it can. Prove(), ProofToHash(), Verify() all have the different output for each implementation.

It would be a problem when creating a platform for another language. I hope the standard vrf library is implemented.

This is because hash is required to generate the first block, but proof cannot be generated.

What does it mean? Hash is generated by Proof. If we don't have Proof we cannot generate Hash. We can make a Proof with our hands using a seed message.

Yes that's right. We can use Proof when elect proposer and validator from second block. But we cannot get the proof to elect a proposer and validators for first block. So, my previous opinion is that store both proof and hash. However, now I think I can handle it even if only proof is saved to the block.

I defined how to electing a proposer and validators for first block in the #44

Finschia / ostracon