spec: Candidate blocks (full proposed values) store

[cason]

The naming is under debate and suggestions are welcome.

In order to support the crash-recovery failure model (#578), a process must recall the values proposed or accepted during the execution of the consensus protocol. This is not a concern of the main consensus logic, as it actually operates on value IDs and relies on the component (e.g., the blockchain or application) using consensus as primitive to:

1. produce values to be proposed: getValue() primitive
2. disseminate the produced values to all processes
3. receive proposed values and validate them

The goal of this issue is to detail what information should be persisted regarding proposed and disseminated values (namely, blocks), so that to render the block propagation and its interaction with the consensus logic deterministic.

Proposer

In any round of consensus, the proposer of that round calls getValue() to retrieve the value to be proposed. This can be either a new value, to be produced, or a value proposed in a previous round that has became valid. It is up to the getValue() implementation to produce a new value or retrieve the previously proposed value (item 1. above).

The value proposed or re-proposed in that round should also be disseminated by the getValue() implementation. In fact, only when the dissemination of the proposed value is completed (item 2. above) and the value ID is computed, this method returns to the consensus implementation the information that value was produced or disseminated.

In order to ensure a proper operation of a recovered node, the getValue() output in a recovering node must be identical to the output produced during regular operation, before the crash. The values produced and/or returned by this method should therefore be persisted in a proper way. The general logic should be adapted so that a value (whose ID is) returned to consensus is previously persisted by the implementation, thus ensuring that this method becomes deterministic.

Streaming

In the case the value is streamed into multiple messages (INIT, parts, then FIN), the node should be sure that the full value is persisted before the FIN message is broadcast. This message contains the end of the value and also its ID. This way we make sure that the node can re-propose the same value when recovering from a crash.

Non-proposer

Processes that are not the proposer of a round wait to receive the proposed value for that round. This can be a new value or a re-proposed value. Both cases are treated in the same way in terms of value propagation, as in #405.

Once the full value is received by the process, possibly into multiple parts, an event is sent to the consensus logic to report the receipt of the proposed value for that round. That event plays the role of the receiving of a PROPOSAL message in the pseudo-code. In addition, this event also reports the boolean result of valid(v), i.e., it informs the consensus logic whether the received value is valid or not from the blockchain and application point of view.

From the crash-recovery support point of view, before the consensus logic is informed about the receipt of value, valid or not, for a round of consensus, this information should be persisted. Namely, the received value and its validity (boolean) should be persisted, so that during recovery the proposed value is available to the consensus logic, as long as its validity.

On the consensus side, the event received reporting the receipt and the validity or not of a value should be persisted in the consensus WAL (#469), as it might lead to consensus state transitions. This also means that, a priori, the events should not be replayed, namely, sent again to the consensus logic once the process recovers from a crash.

TODO: how about the case in which the proposed value is received, validated, and persisted, but the process crashes before the consensus logic receives, acts on, and persists this internal message?

Storage requirements

A process might need to store multiple candidate values/blocks for each height of consensus. In fact, even in a round of consensus, the process might need to consider multiple values, in the case the proposer is Byzantine.

As a result, candidate values can be uniquely identified by a key formed by <height, round, id(v)> used to store the full value v proposed at a given pending height and a round of consensus. In addition to the full value v, the process needs also to persist the (boolean) output of the valid(v) validity evaluation.

Decision

Persistence of disseminated (full) values is only relevant as long as the associated instances of consensus are pending. Once the process reaches a decision on a value and this decision is persisted on a form of block store (#580), the information regarding candidate blocks or full values for the associated height becomes irrelevant.

[cason]

Besides of better documenting the solution, can we consider it solved?