Malicious proposers may choose VRF proof

[ulbqb]

Problem

The current ostracon allows proposers to re-propose previously proposed blocks. A vrf proof exists in the block header to determine the next height proposer. Therefore, a malicious proposer may select and re-propose a block containing his/her preferred vrf proof from past round proposed blocks.

This is still a concern. It is not yet known that this attack is possible. However, I think that concerns can be eliminated by changing the specification so that the highest round proposer creates a VRF proof.

Proposal

I would suggest the following fixes:

message Block {
  Header                      header          = 1 [(gogoproto.nullable) = false];
  Data                        data            = 2 [(gogoproto.nullable) = false];
  ostracon.types.EvidenceList evidence        = 3 [(gogoproto.nullable) = false];
  Commit                      last_commit     = 4;
  VRFParams                   last_vrf_params = 5; // new field!!
}

// new message!!
message VRFParams {
  bytes proof = 1;
}

// Header defines the structure of an Ostracon block header.
message Header {
  ...
  // *** Ostracon Extended Fields ***
  // Note that MaxHeaderSize must be modified when adding/removing fields.

  // vrf info
  // int32 round = 1000; // remove this field!!
  // bytes proof = 1001; // remove this field!!
}

Since the latest proposer creates a VRF proof, it cannot be stored in the current block. Therefore, it is stored in the next block in the same way as last_commit. VRFParams are broadcast just like BlockParts. Also, this value is managed in the internal state in the same way as commit.

Things to think about

• What problems does this attack pose?
• Is this attack possible?
• Assuming this attack is possible, is it realistic?
• Can the highest round proposer rule prevent this attack?

[ulbqb]

Is this attack possible?

I'm currently investigating. I need time because I need to understand the security of tendermint.

Assuming this attack is possible, is it realistic?

Since the proposer would benefit from becoming the original proposer, even a malicious proposer may not carry out such an attack.

Can the highest round proposer rule prevent this attack?

I don't think there are any particular concerns.

[zemyblue]

Is it possible?

I don't think it can happen because there are several confirmed blocks can't occur, so I don't think it can happen that new proposer can choose it. And if there are multiple confirmed blocks, it is subject to slashing with double signatures.

[zemyblue]

Oh, I see. This issue is a situation in same block height.

But I also this is not a problem.

Even if a malicious proposer creates a new block in a new round, it is unlikely to be controlled by a malicious validator because other valdiators who vote for it do not vote if they already know another valid_round, or vote for a new block or select other validators as well.

[torao]

Let me explain the situation in some detail.

When generating the block, for reasons of efficiency, Tendermint allows the Proposer to re-use Proposals that have passed validation in previous rounds of the same height but failed to reach agreement. It's the same behavior for Ostracon.

Ostracon then determins the Proposer for the next block based on the VRF proof associated with that block. Thus, this allows a malicious Proposer to select and re-use a Proposal from previous rounds to select a Proposer in their favour.

The "validated but not agreed proposals" known to each Validator are not the same for all Validators. This is because "no agreement reached" includes the case where "the Proposal was not received correctly". In any case, it's not expected that all Validators have all previous validated Proposals, as more than 2/3 of them were not agreed.

This makes it difficult for other Validators to determine whether the reused Proposal was arbitrarily selected or the only one known to that Proposer (it may be possible to trace back past signatures to see what Proposals were recognised by the Proposer, but a new protocol to report this would be needed).

Note, however, that there are limitations to this malicious selection.

• The VRF used for selection is uniformly random. And all of honest Proposers will try to re-use the correct Proposal they known. Thus, assuming the number of all Validators is $N$ and the round is $r$ (i.e. $r-1$ times failed to agree), the probability of selecting the desired Validator as the next Proposer is $1/N$ in most cases, and the worst-case upper bound is $(r-1)/N$.
• Even if the desired Validator can be selected as the next Proposer, it's temporary and recovers in only one round. This behavior cannot be chained to hijack the agreement, so it doesn't affect the liveness of the blockchain.
• This behavior doesn't generate malicious blocks or allow such a block to pass validation. Therefore, it doesn't affect safety.
• From a performance point of view, it doesn't matter which failed round's Proposal is selected if the Proposal is correct too.

[ulbqb]

The VRF used for selection is uniformly random. And all of honest Proposers will try to re-use the correct Proposal they known. Thus, assuming the number of all Validators is $N$ and the round is $r$ (i.e. $r-1$ times failed to agree), the probability of selecting the desired Validator as the next Proposer is $1/N$ in most cases, and the worst-case upper bound is $(r-1)/N$.

Consider the worst case of 33% being Byzantine. In this case, there is a 33% chance of producing a proof such that the next proposer is Byzantine. So if we can reuse previous proofs, the worst-case probability of agreeing on the next byzantine proposer proof at r is 1 - (0.67)^r.

[ulbqb]

I'm afraid the Byzantine proposer will last forever. This probability cannot be calculated immediately, but it is definitely increasing.

[torao]

It may be possible to slightly increase the number of failed agreement rounds, but even if Byzantine nodes occupy $f$ of the allowed upper bound in the $3f+1$ Validators, it would not be possible to control and inhibit liveness so that Byzantine Proposers are selected forever, unless the number of honest Validators falls below $2f+1$. Could you explain in what specific cases this happens?

[ulbqb]

Could you explain in what specific cases this happens?

Probability that Byzantine proposer will continue to be selected is not zero because proposer selection is random sampling. But this was an extreme example. It is a concern that more byzantine validators would be elected as proposers than the actual byzantine percent to be exact.

[ulbqb]

It was a concern that more byzantine validators would be elected as proposers than the actual byzantine percent to be exact.

I thought about what kind of problems would arise in such a situation.

1. A continuing Byzantine proposer has a negative effect on liveness.
2. If the proposer is rewarded, it can receive more rewards. Dominate the network over time.
3. Censorship can be done. A tx that the proposer doesn't like may be temporarily not processed.

1: Even if proposers are malicious, if they think rationally, they will not do anything that will damage the liveness. This will only make network unreliable and lost their assets. Reasonable thinking can ignore this.
2: Malicious proposers receive more rewards than honest proposers, so they gradually dominate the network. If there are not the rules that reward proposers, this can be ignored.
3: Censorship allows malicious proposers to make a lot of money, such as arbitrage. However, this is not resolved by this fix.

From the above it seems that modifying like proposal doesn't make much sense, at least for 1,2,3.

Are there other possible problems?

[zemyblue]

If the probability of validator being elected as proposer is determined by the ratio of staking power, it seems that byzantine can be prevented from continuing to be elected. Even if byzantine selects byzantine as the next proposer at a certain block height, it seems that the possibility of byzantine being selected as the proposer can always be reduced.