code: Stream the block when re-proposing (L16)

[ancazamfir]

cc @romac @cason @josef-widder

A proposer that hits L16 with valid value should trigger the streaming of the full block as some validators may have missed it.
In the code this means:

• the proposer should send a message to the value builder to retrieve and gossip the existing block parts from the store. This message should include the proposal_round (required in Fin signature). valid_round should come from the stored value with the block_hash hash.
  • at the host side implement

    malachite/code/crates/starknet/host/src/mock/host.rs

    Lines 130 to 135 in 221c787

    	async fn send_known_proposal(
    	&self,
    	block_hash: Self::BlockHash,
    	) -> mpsc::Sender<Self::ProposalPart> {
    	todo!()
    	}

• as the value is known the proposal message should be sent immediately in consensus (already handled)
• on the receive side the re-streamed proposal parts should be stored and muxed with the proposal it the full value has not been seen before (already handled)
• for both proposer and non-proposer we should simulate the transaction execution that would recreate the corect app state.
• if the value has been seen before the validity is known so consensus can proceed, otherwise consensus waits for the block builder for the full value (already handled)

[josef-widder]

I think this is related to #365. While @cason seems to have argued for changes in consensus (if I understand correctly), my response was that we may treat this outside of consensus. It seems related as receivers might ignore parts of blocks that they have already seen. I think it makes sense to do it this way.

[ancazamfir]

I think this is related to #365. While @cason seems to have argued for changes in consensus (if I understand correctly), my response was that we may treat this outside of consensus. It seems related as receivers might ignore parts of blocks that they have already seen. I think it makes sense to do it this way.

I feel #365 covers a wider range of cases (but not L28) and we should discuss before making changes. I am also not entirely sure how valid(v) would work as it would carry two meanings: a) value received but invalid, b) value not yet received.
In addition, as you know, we currently handle valid() outside consensus and it is the "caller" who sends (PROPOSAL(...), Validity) .

For Starknet, there is no explicit Proposal message since it is implicit from the receipt of all block parts who carry height, round, block_hash (aka id(v)) that hashes over the full block (aka v). In addition there is the Fin message that includes valid_round, for famous L28 case(*). So with all this in place we do not really need a proposal message on the wire. Instead, the value builder can construct a virtual Proposal message from the block and send it to the consensus engine. This way we do not have to change the algorithm.

We haven't yet made changes to the code for this because we need to figure out if and how we will handle both implicit (**) and explicit Proposal messages. fwiw I am also of the opinion that the handling should be done outside consensus.

Regardless the proposal message flavor, this issue applies and a solution is required for the Starknet architecture.
This issue is to handle the streaming of previously seen value (for which a polka has been seen).

There is another part to clarify, at least in my mind:

• if we do not have an explicit proposal, the nodes that have seen the value will still have to wait for its copy to be assembled in order to figure out the (PROPOSAL, hp, roundp, v, vr) part of the condition of L28, which I believe defeats some of its benefits with big values/ blocks.

(*) I think Fin should in fact include the proposal_round while the parts can be seen as containing the valid_round. This is because with L16 the old value needs to be sent out, the one previously seen (and validated) in valid_round and Fin should instead always contain proposal_round. But this is a different discussion.

(**) Currently, for explicit proposals, in the code there is a multiplexing layer that holds on to the value builder output and explicit proposal. When both are present a proposal is sent to consensus engine. I am currently working on refactoring this, mainly to remove its pollution from the driver and outside of the "engine". The multiplexing code is also buggy and am looking to correct this. But handling multiple conflicting values and proposals, matching a value with a proposal, etc proves to be pretty complex even on paper. Another incentive to remove the explicit Proposal messages (i.e. remove them from the wire but emulate them in consensus code)

[ancazamfir]

(*) I think Fin should in fact include the proposal_round while the parts can be seen as containing the valid_round. This is because with L16 the old value needs to be sent out, the one previously seen (and validated) in valid_round and Fin should instead always contain proposal_round. But this is a different discussion.

Opened #407 with some questions

[romac]

It seems like the definition of the ConsensusContext trait in Papyrus has changed since we last looked at it and imported it under the Host trait. Here is its current definition.

As far as I can tell, there is no method corresponding to send_known_proposal anymore.

[josef-widder]

We discussed related issues with @cason today, and he explained to me that upon ⟨PROPOSAL, hp, roundp, v, vr⟩ from proposer(hp, roundp) in the algorithm has two different usages:

1. to check whether the proposer proposes this value
2. to use the data in v

If you look at the algorithm, this is used four times

• Lines 22 and 28 needs both usages, that is 1. and 2.
• Lines 36 and 49 only needs 2.

So, in principle, if you re-propose, it might be enough to send a small propose message (with id(v)), that references to a block that is already gossiped. What you explained about Starknet, it seems that if we go to round 1, the proposer must re-stream everything, because they don't have this separation?

I think there are advantages of small explicit propose messages, but we need to figure out how to align this with Starknet requirements. Would be good to discuss.

[ancazamfir]

As far as I can tell, there is no method corresponding to send_known_proposal anymore.

Not sure I understand the papyrus impl. It seems that currently they just run by reading existing blocks: https://github.com/starkware-libs/sequencer/blob/395fec7473c27c6237601cc4787e7469ed42aba0/crates/sequencing/papyrus_consensus_orchestrator/src/papyrus_consensus_context.rs#L72

What you explained about Starknet, it seems that if we go to round 1, the proposer must re-stream everything, because they don't have this separation?

right. There might be a way, on the receive side we could look at Init (if sent with valid_round this could be the mini proposal)) and if we already have a value for the (height, round) and the polka for that we can assume the new proposer will send the same value. One can imagine a few ways a (re)proposer may be byzantine but couldn't figure out if it can cause any correctness or liveness problems.

I think there are advantages of small explicit propose messages, but we need to figure out how to align this with Starknet requirements. Would be good to discuss.

agreed

[josef-widder]

One can imagine a few ways a (re)proposer may be byzantine but couldn't figure out if it can cause any correctness or liveness problems.

I would say that Byzantine re-proposers are just Byzantine, and Tendermint consensus deals with that. What could happen is that the re-proposer

• puts a validRound into Init (I don't know the details there)
• and then streams a completely different block

Then there might be different correct nodes

• N1 already has the block for the validRound and ignores the stream
• N2 doesn't have the block and reads the stream

But from the Tendermint perspective, this just means that N1 and N2 receive different proposals for the same round, that is, it is just double sign on different proposals. Of course in this round there is no guaranteed decision, but this is always the case for Byzantine proposers. Safety wise, Tendermint takes care of this (e.g., for N2 there are not enough prevotes from round validRound, to make N2 prevote on the new block in line 28).

[cason]

I think that the valid round should be on Init. And I think that @matan-starkware has the same opinion.

[cason]

In general, in case of re-proposed value, I would suggest:

1. Send only id(v) and vr as part of the Init. Namely, if Init.vr >= 0 then we include id(v)
2. By construction, 2f + 1 nodes have v because they have issued (PREVOTE, hp, vr, v)
3. Other nodes should retrieve v from peers

Since we don't have 3. yet implemented and full values are broadcast, for the sake of simplicity we just send the same full value again in the case of re-proposals.

[ancazamfir]

I think that the valid round should be on Init. And I think that @matan-starkware has the same opinion.

Indeed Matan mentioned this a few days ago, sorry forgot to update the issue.