tortoise: vote for an empty layer if multiple certificate were signed by the same committee

[countvonzero]

Description

it's possible for the network to have multiple certificates for the same layer when there is a network split.

but if the same committee signs more than one certificate, it should be considered malicious and the node should vote for an empty layer.

@dshulyak

[jonZlotnik]

How will you detect this? And can you specify what you mean be the same committee? All committee members sign both certs?

[countvonzero]

the following situations can cause multiple certificates in the network: A. malicious nodes equivocating by certifying multiple blocks B. upon a network rejoin, each split's certificate can be floating around the same network

regardless, when the node sees multiple certificates for the same layer, it re-validate all of them.

• if more than 1 certificate are valid -> make tortoise vote for an empty layer
• if only 1 certificate is valid -> make tortoise vote for that block
• if no certificate is valid -> make tortoise vote for an empty layer

[countvonzero]

implementation plan

new sqlite table certificates

• in order to track potentially multiple certificates for the same layer, a separate table certificate is used to save seen certificates for all layers.

proposed schema:

CREATE TABLE certificates
(
    layer INT NOT NULL,
    block VARCHAR NOT NULL,
    cert  BLOB,
    valid bool NOT NULL,
    PRIMARY KEY (layer, block)
) WITHOUT ROWID;

• when the block certifier receives ceritfy messages or received a synced certificate, it
  • goes through all existing certificates for the same layer, and re-validate them with the latest active set for the epoch. the validity of the old certicates are updated accordingly.
  • if the original hare output (saved without certificate) is different from the certificate, the original hare output is invalidated.
  • tortoise.OnHareOutput is called on the certified block, or on types.EmptyBlockID if more than one certificate are vaild.
• components (mesh/tortoise) that need to know about which block to apply to state/vote for calls certificates.GetHareOutput(), which either return the certified block ID, or types.EmptyBlockID when there are multiple valid certificates.

pruning certificate

see https://github.com/spacemeshos/go-spacemesh/issues/3588

[countvonzero]

@dshulyak please review ☝🏽

[dshulyak]

CREATE TABLE certificates

why not to add one more field (certificate) to blocks table? if certificate field is not null it means that block is certified and the rest is the same

valid bool,

i think this field is not necessary. if certificate is no longer valid, it can be deleted immediately. the only time when two can be stored is when both (or more) are valid, since that implies equivocation

layers.hare_output

should be possible to remove this field as well

[dshulyak]

layers.hare_output

i guess there is a case when live node has hare output, but didn't see certificate i would add one more boolean to blocks table (for example hare_output)

and we count it as a certificate for all voting purposes

[countvonzero]

i would add one more boolean to blocks table (for example hare_output) and we count it as a certificate for all voting purposes

@dshulyak we keep coming back to this topic. how do you save a valid certificate with types.EmptyBlockID if we use blocks table?

[countvonzero]

it is true that we will never save a invalid certificate. but an originally valid certificate can turn invalid when node's epoch ATXs changed. that's why i used a certificates.valid boolean instead of adding a Delete interface. but since we are going to do pruning in the future, maybe adding Delete interface is ok.

[dshulyak]

how do you save a valid certificate with types.EmptyBlockID if we use blocks table?

i forgot about it, are we doing it in the current implementation? or we don't do that for some other reasons?

but still we can drop hare_output field from layers table and store boolean in certificates

[countvonzero]

how do you save a valid certificate with types.EmptyBlockID if we use blocks table?

i forgot about it, are we doing it in the current implementation? or we don't do that for some other reasons?

that just says that the design was not intuitive.... yes, the network will generate a cert for types.EmptyBlockID if hare output an empty set.

here is a recap of the slack convo https://spacemesh.slack.com/archives/CG91F13C7/p1660817260584409

kimmy: 
question about hare certificate.
when a hare protocol completes and output empty set of proposals. no block will be generated. 
in this case, do we need to generate a certificate for that empty output?

Noam:
Yes. This will enable honest ballots to vote for the empty layer (instead of abstain for this layer 
because they didn't see Hare terminate). That way consensus can move along faster.

I'd think twice if I didn't think this is easy to implement. If I'm wrong then please say so.

Tal:
I agree with noam. It's not critical, but it is more robust (it also helps in the case where parties 
join in the middle of an epoch, since they can sync the empty layer certificates and vote correctly).

but still we can drop hare_output field from layers table and store boolean in certificates

yes. will do