Checkpointing challenges

[sergefdrv]

This is a continuation of the discussion started at #215 (reply in thread).

[sergefdrv]

Thanks for the details, I updated my understanding for the problem (sorry if still irrelevant). According to MinBFT paper, a Checkpoint message conveys UI_latest (latest executed request) and UI_j (UI for Checkpoint message from backup replica). The checkpoint operation proceeds to be executed at the point when f+1 Checkpoint messages are collected, so only message logs for replicas whose Checkpoint messages are included in the checkpoint certificate are justified with the UI_j. The remaining n-f-1 replicas' message logs are not justified.

How we handle the remaining (arrived late) Checkpoint messages seems not documented in the paper, but adding them to the checkpoint certificate afterward and/or updating internal state about other replicas' latest UI values might be a possible direction?

As justified in 845bc82, the current implementation assumes that Checkpoint messages are to be signed with regular signatures rather than certified with USIG, i.e. there is no UI_j in Checkpoint messages.

But let's suppose we change it back and do certify Checkpoint messages with USIG. What still makes me particularly unsure here is that UI_j is not confirmed by a quorum of at least f+1 replicas. So a Byzantine replica can generate, selectively distribute, and then discard any message before assigning UI_j to the Checkpoint message. Suppose it generates the following sequence of messages:

...
<COMMIT cv=97 replica=2 proposal=<PREPARE cv=100 replica=1 view=1 client=0 seq=41>>
<COMMIT cv=98 replica=2 proposal=<PREPARE cv=101 replica=1 view=1 client=0 seq=42>>
<VIEW-CHANGE cv=99 replica=2 newView=2 vcCert=<quorum=[0 2]>>
<CHECKPOINT cv=100 repllica=2 view=1 cv_latest=100 state_hash=...>

The question here is: How can we guarantee that the Commit message with cv=98 from this Byzantine replica cannot cause inconsistent request execution if a quorum of Checkpoint messages referring to cv_latest=100 justifies the discarded messages as if the immediate previous message was a Commit referring to the primary's Prepare message with cv=100? Remember that after the first view change, UI counters may diverge in different replicas.

[nhoriguchi]

Let me share my ideas ...

I think that in the above scenario the View-Change message and the Checkpoint message are incorrect ones intentionally generated by Byzantine replica 2. The View-Change message can be rejected by correct replicas because there's no Req-View-Change message and correct replicas are still in view 1. If the Checkpoint message from replica 2 is incorrect, other correct replicas should exchange Checkpoint messages with correct cv_latest (maybe 101 in this situation?), so the incorrect Checkpoint message should be safely ignored in quorum of Checkpoint messages.

Considering that we have Req-View-Change (just hidden in "...") and the system is during view change (there's no New-View message so view change is not finished yet), this is a race situation between view change and checkpoint. I think that view-change is mandatory operation so it can't fail. Then If checkpoint can fail, checkpoint request during view change can be rejected or postponed until the running view change operation completes.

[sergefdrv]

message are incorrect ones intentionally generated by Byzantine replica 2

Yes, we assume that replica 2 is Byzantine, so it can do anything.

there's no Req-View-Change message

I omitted it because it is not certified by USIG. Suppose, replica 2 generates it, but only includes it inside its ViewChange message (note vcCert=<quorum=[0 2]>).

incorrect Checkpoint message should be safely ignored

Imagine that replica 2 generates all these messages, but first only sends the Commit messages. Moreover, it chooses not to send the last Commit message with cv=98 to selected replicas. Assume that all replicas execute the request client=0 seq=41, then generate and send their Checkpoint messages for view=1 cv_latest=100. Suppose further that those replicas, which have not received the last Commit message from replica 2, time out and start view change at this point; at the same time, the remaining replicas collect a commit quorum for client=0 seq=42, execute the request and remain in view 1. It may take some time for those two groups of replicas to hear from each other. In the meantime, the Byzantine replica 2 constructs a checkpoint certificate from its own Checkpoint message and f Checkpoint messages from other replicas, discards all previously generated messages, generates another ViewChange message with cv=101, and sends that to the new primary. Note that replica 2 does not have to reveal the discarded messages to the new primary since it presents a valid checkpoint certificate "justifying" the missing older messages.

For those replicas that have not received the last Commit message from the replica 2, it will appear as if the replica 2 only generated the latter ViewChange message, so it effectively hides the fact that it has generated the last Commit message. The new primary may collect a new-view certificate composed of ViewChange messages without any Prepare/Commit for client=0 seq=42, including the latter ViewChange message from replica 2. Thus the request client=0 seq=42 executed by some correct replicas in view 1 may not propagate to the new view 2.

[sergefdrv]

In a slightly modified scenario, the message log of replica 2 may appear for different replicas in two different ways.

...
<COMMIT cv=97 replica=2 proposal=<PREPARE cv=100 replica=1 view=1 client=0 seq=41>>
<COMMIT cv=98 replica=2 proposal=<PREPARE cv=101 replica=1 view=1 client=0 seq=42>>

...
<COMMIT cv=99 replica=2 proposal=<PREPARE cv=100 replica=1 view=1 client=0 seq=41>>
<CHECKPOINT cv=100 repllica=2 view=1 cv_latest=100 state_hash=...>
<VIEW-CHANGE cv=101 replica=2 newView=2 vcCert=<quorum=[0 2]>>

[sergefdrv]

Note how VIEW-CHANGE cv=101 replica=2 supported by a checkpoint certificate for view=1 cv_latest=100 effectively hides COMMIT cv=98 replica=2.