Consensus Messages

[liamsi]

We need to define the messages that are exchanged by nodes during consensus.

IMO, most of the messages defined by tendermint can be used and do not require any changes. The main change would be regarding the BlockID (which is used in Votes, Proposal etc).

Note that we also have a BlockId in the ll-spec which is the hash of the header basically (differently from tendermint and still different from what would be required for validators s.t. can sample for DA proofs).

My understanding is that the Proposal should contain the data root at least. IMO, it should also contain the DA header and the orig data square size. The last is optionally but it would simplify the implementation (and I don't see why it should not simply be included).

Happy to help with this as we need to define these for the implementation anyway!

[liamsi]

Here is a suggestion how it think the proposal should look like (in go syntax - the spec should contain it as a protobuf message):

type Proposal struct {
	// Fields required for tendermint consensus: 
	Type      SignedMsgType 
	Height    int64         
	Round     int32         
	PolRound  int32 
	// BlockID   becomes obsolete with the DA header included below
	// BlockID   BlockID
	Timestamp time.Time  
	Signature []byte

	// LazyLedger specific fields:

        // Needed for nodes to sample DA proofs / retrieve the whole block if they want to.
        AvailableDataHeader  AvailableDataHeader      
}

AvailableDataHeader

[liamsi]

Note, OriginalSquaresize is called availableDataOriginalSharesUsed in the spec and we need to clarify if we need to include the AvailableDataHeader or if the availableDataRoot is sufficient. I think we agree that the DA header should be part of the Proposal.

Copying over @adlerjohn's comment from discord:

I think it should include any "extra" header fields we added that can't be inferred https://github.com/lazyledger/lazyledger-specs/blob/master/specs/data_structures.md#header
So, feeHeader.tipRate, and availableDataRoot. For performance we should probably include availableDataOriginalSharesUsed too.

[liamsi]

Originally I thought the availableDataOriginalSharesUsed is also necessary in the proposal but it is not. If the AvailableDataHeader is included, the original square size can be recomputed.

[liamsi]

@adlerjohn should keep the BlockID in the Proposal? And with BlockId I mean

The block ID is a single Merkle root: the root of the block header's fields, in the order provided in the spec. The root is computed using a binary Merkle tree.

Also @marbar3778 proposed to rename the above to HeaderHash. I think that is a good idea.

As far as I understand the HeaderHash also needs to be part of the proposal as we want to sign this in a Vote essentially:

vote := &types.Vote{
	ValidatorAddress: addr,
	ValidatorIndex:   valIdx,
	Height:           cs.Height,
	Round:            cs.Round,
	Timestamp:        cs.voteTime(),
	Type:             msgType,
	// hash can be nil to "prevote nil"
	HeaderHash:       types.HeaderHash{Hash: hash}, 
}

[adlerjohn]

The block header consists of the following fields:

name	type
height	Height
timestamp	Timestamp
lastBlockID	BlockID
lastCommitHash	HashDigest
consensusRoot	HashDigest
feeHeader	FeeHeader
stateCommitment	HashDigest
availableDataOriginalSharesUsed	uint64
availableDataRoot	HashDigest
proposerAddress	Address

In addition to these, we should add a round field for consensus proposals, which is committed to in the Commit hash. While some fields can be optimized away since they can be inferred, it would probably be safer to keep them all in the proposal message as a kind of error checking. E.g. the lastBlockID can be omitted since there are no re-orgs...except if there are re-orgs (bugs, hard fork, etc.). The block ID of the current proposal can similarly be omitted, but there's no harm in including it, again as an error checking mechanism.

One thing I'm not sure of is the inclusion of the full available data header in proposals instead of only the hash. Validators should be expected to vote only when they've actually validated the whole block (all transactions + correct erasure coding), otherwise we lose the property that any invalid committed block will result in >=2/3 of stake being burned. So couldn't the proposal be simply the header hash + height + round + proposer signature, then have a sub-message type to fetch the full header, and the full available data header, and the full data? The alternative is to just put the whole header + available data header into a single message to reduce round trips, but makes the proposal message larger.

(Also as an aside: without a signature from the proposer in the header/enforced in the Commit validation logic, how do we know for sure it was actually that validator that proposed the block?)

As for re-naming: I suggest either

1. Use the name HeaderRoot, since the block ID is the Merkle root of the header. This is inline with the rest of our re-naming (-hash for hashes, -root for roots). Or,
2. Hash the header instead of Merkleizing it. I actually recommend this path Cleanup Header Hashing tendermint/tendermint#7915.

Suggested format for Proposal:

name	type
height	Height
round	Height
timestamp	Timestamp
lastHeaderHash	HashDigest
lastCommitHash	HashDigest
consensusRoot	HashDigest
feeHeader	FeeHeader
stateCommitment	HashDigest
availableDataOriginalSharesUsed	uint64
availableDataHeader	AvailableDataheader
signature	Signature

[liamsi]

Validators should be expected to vote only when they've actually validated the whole block (all transactions + correct erasure coding), otherwise we lose the property that any invalid committed block will result in >=2/3 of stake being burned.

What about the idea that validators can only decide to do data availability checks? Or at least only validate state transitions without downloading message data to verify the erasure coding? I think @musalbas feels strongly about this.

If validators have to download the whole block anyways, that would mean that we should actually keep the block gossiping routine (instead of having the validators that want to download the data pull it on demand from the network); ref: celestiaorg/celestia-core#85 and that would also be related to the ADR that @marbar3778 is working on. As far as I understood so far, forcing all validators to download all data was not an option?

then have a sub-message type to fetch the full header, and the full available data header, and the full data

Sure, that is possible and closer to the current implementation (although everything is gossiped as parts currently - so one message type for everything).

I think it alls boils down to the one question: what is the bare minimum of data a validator needs to vote on a block in LL.

If everyone needs the DA header anyways, it should be part of the Proposal message. At least I do not see any good reason to send this in a separate message IMO (and fetch the DA header separately). It's certainly possible to have a separate message type for it though but it unnecessarily complicates reasoning about this.

The alternative is to just put the whole header + available data header into a single message to reduce round trips, but makes the proposal message larger.

I think I'm in favor of this: validators receiving the Proposal can then immediately start sampling for DA proofs. Are there good reasons to not include the DA header? What is the benefit of leaner proposal message?

(Also as an aside: without a signature from the proposer in the header/enforced in the Commit validation logic, how do we know for sure it was actually that validator that proposed the block?)

The signature is part of the proposal and the header. Oh, you mean if the validators don't have the header and only do sampling?

I don't mind if the Header fields are merkelized or not. Both is good to me HeaderRoot or HeaderHash 👍🏼

[adlerjohn]

What about the idea that validators can only decide to do data availability checks? Or at least only validate state transitions without downloading message data to verify the erasure coding?

I was kind of mangling a few different things with that line of thought. The two options I had in mind were:

1. Validators literally do nothing but vote on the header hash, validity and availability be damned. In that case, including the full available data header in the proposal is not necessary. We probably don't want this, so option 2:
2. Validators vote after doing at least DAS (I said full validation above but really it should just be DAS). In that case, you should probably include the full available data header in proposals. This option is fine.

The signature is part of the proposal and the header. Oh, you mean if the validators don't have the header and only do sampling?

No, I mean our Header struct only has proposer address, but no way of proving that that validator actually proposed the block in question.

[liamsi]

No, I mean our Header struct only has proposer address, but no way of proving that that validator actually proposed the block in question.

Alright. That is also true for a vanilla tendermint Header. But the Proposal contains the proposer's signature. If >2/3 of validators signed the Proposal that should be proof enough that the proposer signed the proposal too? Is proving this later relevant for fraud proofs? Or why should the proposer's sig be part of the header?

[adlerjohn]

If >2/3 of validators signed the Proposal that should be proof enough that the proposer signed the proposal too? Or why should the proposer's sig be part of the header?

Under an honest majority, yes. But if the majority of validators are dishonest, then you need to be able to hold them accountable. If they're going to be dishonest anyways, they can bring an honest validator down with them by blaming them for proposing the block. We can avoid this by requiring that the proposer must separately vote for the block, but then they should be distributing a ConsensusVote with their proposal, not a generic signature.

[liamsi]

But if the majority of validators are dishonest, then you need to be able to hold them accountable.

Accountable by whom and what consequences would that have?

We can avoid this by requiring that the proposer must separately vote for the block, but then they should be distributing a ConsensusVote with their proposal, not a generic signature.

Not sure I'm following. The Proposal itself is a kind of Vote. Do you mean in later phases of the consensus instead (not in the Proposal)?

[adlerjohn]

Accountable by whom and what consequences would that have?

Social consensus. I'm probably overthinking this, let me get back if I can come up with some concrete attack.

[liamsi]

The last few comments here about not making an honest majority assumption and falling back to social consensus could be interesting to discuss with @milosevic / the informal team. They spent a lot of time thinking about light-client attacks and it kinda feels related.