# Block Proposals - Writeup

We have been working on an exploratory project focused on adding a major new feature to Tezos -- something that we internally call "block proposals". The original idea for block proposals began as a way of realzing one of the goals of the Tezos architecture, that of allowing plugable consensus algorithms to be added to Tezos.

We were also hoping that as a side effect, this project would provide our developer(s) a hands-on way to gain a deeper understanding of the Tezos codebase.

In this document, we will first provide an explanation of the concept of block proposals, and then describe the steps we went throught and how ulitmately this work can be completed.

***

## Block proposals overview
The purpose of 'block proposals' is to change the way Tezos decides which blocks will be added to the chain, with the goal of making Tezos a better fit for the way most modern consensus algorithms are defined. Consensus algorithms can then be adopted directly, without having to first rework them to fit Tezos' architecture (and without having to adapt any correctness proofs associated with the algorithms).

The way Tezos currently works, a new block is chosen based on its fitness, and then all endorsements of the chosen block are bundled with the submission of the subsequent block.

Block proposals, on the other hand, allows multiple blocks to be simultaneously proposed and endorsed, with the choice of the fittest block made only after sufficient votes/endorsements for the block have been received.

With block proposals in place, a good number of modern consensus algorithms can be implemented within Tezos in a more direct, straight-forward way.

***

## Motivation
Most modern consensus algorithms are formulated within a common overall structure. One node, usually called the leader, submits a potential block to be added to the chain. Other nodes vote their acceptance or rejection of the proposed block. Once sufficient 'yes' votes have been received, the block is added to the chain.

Many details within the above pattern vary among the different algorithms: how leaders are chosen, what rules a voter follows for validation, the number of positive votes required, etc. What is, however, generally the same among these algorithms is the overall flow:

> *A block is proposed -->
> Nodes vote for or against the block -->
> The block is accepted or rejected as the next block*

The correctness proofs provided for each algorithm also generally depend (either explicitly or implicitly) on the above flow being followed.

Without an extra feature such as block proposals added to Tezos, it is generally not possible to directly implement these algorithms in Tezos such that the validity of the correctness proofs can be assumed. There is no way to directly allow multiple candidate blocks to be proposed, with the choice of the 'winning' block postponed until after the votes (aka endorsements) have been received.

Attempting to modify consensus algorithms to work directly with Tezos (i.e., in such a way that a single fittest block can be determined before voting is completed) can be difficult. Even if the algorithm can be adapted, proving that the modified algorithm has all the properties and guarantees of the original can also be demanding.

### Examples
Some examples of consensus algorithms that follow the high-level pattern described above:

[Tendermint](https://tendermint.com/)
[PaLa](https://eprint.iacr.org/2018/981.pdf)
[Streamlet](https://eprint.iacr.org/2020/088.pdf)
[HotStuff](https://arxiv.org/abs/1803.05069)
[Tangaroa](https://www.scs.stanford.edu/14au-cs244b/labs/projects/copeland_zhong.pdfk)

At some point the state-of-the-art of these algorithms may improve significantly enough that upgrading from our current Tenderbake algorithm is indicated. Having block proposals in place will make this simpler and faster to accomplish.

See [Appendix A](#Appendix-A:-Technical-Details) for further technical details about block proposals

***

### Where we left off

We eventually decided to put this project on hold, leaving its completion to a future time or to another team. The biggest reason to not continue was coming to grips with the the amount of work required to maintain a working merge with the Tezos master branch. For our one-man team, the percentage of overhead was too great to make foward progress at a reasonable pace, and other priorities prevented us from adding more resources to this effort.

With the sucess of Tezos' Tenderbake consensus, we also realized that block proposals was not going to be seen as the highest prioirty, and there was a relatively low chance of getting this merged into the main branch any time soon.

See [Appendix B](#Appendix-B) for links to the codebase and details about what still needs to be implemented

***
## Appendix A: Technical Details
***

### Specification

#### Implementation Overview:
The following paragraphs provide a high level description of key aspects of the current POC implementation of the block proposal mechanism. A link to the current code can be found below in [Appendix B](#Appendix-B).

* Block proposals are implemented similarly to blocks, with a key difference being that some amount of validation can be postponed until after the winning block has been selected. Determining what validation can be skipped at which point in the process is still a work in progress. Avoiding unnecessary validation processing is likely to be important to maintaining good performance.

* Block proposals produce streams that can be watched, and events can be fired. This is implemented in the same way that streams of blocks are currently handled.

* There is a block proposal voter process that is implemented similarly to the (now defunct) endorser process. This process listens for block proposals and triggers voting.

* Block proposal votes are implemented as operations, very similar to endorsements.

#### Additional details

Much of the ways in which Tezos with block proposals will differ from current Tezos depends on the specific consensus algorithm that is chosen. Block proposals on its own will not change anything -- only when it is utilized by a consensus algorithm will the behavior change. Specifying the precise nature of leader selection, voting procedures, etc. cannot be done until such a choice is made.

#### New Client commands:

The following client commands will be added:

* `propose` - Submit a new block proposal
* `bake proposed` - Bake a proposed block. This specialized version of *bake* is only needed to keep the existing *bake* functionality unchanged.

#### Misc Notes
* The fitness function in Tezos can be implemented to choose the block with the most votes. A block with insufficient votes is invalid as per the specific consensus algorithm in use and should not be seen by the fitness function.
* We can leave the full validation to the bakers when the block is finally produced. This would allow propagating this operation faster
* We have needed to add new peer-to-peer messages, new types of requests, events, etc.
* When used on mainnet, any consensus algorithm implemented using block proposals will still need to use the existing PoS mechanism for quorum selection and voting power.
* For P2P, we will attempt to send the entire proposal 'header', rather than send just a hash that requires the receiver to then fetch the data

#### Optional / related changes
##### Consensus API / library
Block proposals are meant to work with one or more of the many published consensus algorithms. It should be possible to centralize the common code that is required by all such algorithms, and so design a consensus API such that multiple consensus algorithms can be implemented with minimal code duplication between them. This will allow rapid evaluation of new algorithms, and enable simpler experimentation for private chain use cases, etc.

##### Storing endorsements with the block they are endorsing
One possible change that can be implemented along with block proposals is to store endorsements as part of the current block, rather than including them in the subsequent block. Putting the endorsements into the same block they are endorsing would make the block format a bit more intuitive.

***

### Rationale
Design decisions made while building the POC reflect this set of requirements:

#### Block Proposals:
* require specific shell support
* must have a priority higher than operations
* must have guaranteed progress -- cannot be sent as 'best-effort' (e.g. the lossy manner in which operations are sent)
* must have an accompanying `vote` operation, similar to endorsements
* cannot be allowed to overwhelm validators. At a given time, only a few potential proposals should be valid.
* must be able to be authenticated
* must work with blacklisting (in the same way that blocks do)

#### Block proposal validations must ensure that:
* the proposal is signed
* the operation can legitimately be emitted
* dependencies are available

#### The role of the baker is to:
* receive block proposals
* vote on block proposals
* collect votes on block proposals
* inject actual blocks when sufficient votes have been seen

### Development cost
Though the cost of completing the block proposals code plus implementing an initial consensus algorithm will not be insignificant, the benefit of this approach should be fully realized when integrating a new consensus algorithm is desired. Adding a second algorithm should be markedly less effort then integrating another algorithm in the manner or Tenderbake.

### Alternatives to Block Proposals
One alternative to implementing block proposals would be to research / prove some notion of equivalence between Tezos' fitness / endorsement process and the block selection process employed by one or more consensus algorithms. It might be possible to find a general equivalence between a class of consensus algorithms (as opposed to e.g., a Tenderbake-specific proof)

***
### Backwards Compatibility
Most of the work for block proposals involves adding new features to the Tezos codebase that will not by executed by existing branches. For common features that need some modification (e.g. baking), the existing code will be left unchanged, as to avoid any unplanned impact. This will involve some small amount of code duplication - if desired it can be removed at a later date.

### Security Considerations
As block proposals are meant to work with one of the published consensus algorithms, it is of course necessary to ensure that whatever algorithm is chosen meets the required security and reliability requirements for Tezos.

We must also verify that blocks produced through an altered flow via block proposals still execute all the required validations.

***

## Appendix B
Here is a [link to the repo](https://gitlab.com/oxheadalpha/tezos/-/tree/block-proposals-staging) for this project The most recent branch is `block-proposals-staging`, and the commit hash as of this writing is `9f71cbcb18473bcdb335ebfd611a45f7854a1b3f`.

The commit hash for the state of the Tezos repo which was most recently merged into our code is `7146825c1524c7b227d41101b2fb8599999aec81`
#### What still needs to be done
* Complete the work on the voting operations, including verifying they can be properly received.
* Change the existing fitness function to check that sufficient votes have been received.
* The current baking rights behavior needs to be replaced - all bakers should be potential 'leaders', the choice of which is determined by the consensus algorithm.
* Implemement an initital test consensus algorthim, and verify the full cycle of block proposal, voting, and baking the winning block works correctly and performs reasonalbly.
* While attempting to emulate Tenderbake's 'pre-application' of blocks as a model for block proposal validation, a failure was introduced that still needs to be tracked down.

#### Some categories of changes, files, etc.

Overall, the diff shows x number of files changed, but here are some categories of files/changes to help make some sense of the picture:

##### New client commands
* Create a block proposal
*Command: "block-proposal-create for <baker-name>"*
*[Link to the code:](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_delegate/baking_commands.ml#L236)*
* Bake a block proposal block
*Command: "block-proposal-bake for <baker-name>"*
*[Link to the code:](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_delegate/baking_commands.ml#L259)*
* Vote on a block proposal
*Command: "block-proposal-vote for <baker-name>"*
*[Link to the code:](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_delegate/baking_commands.ml#L284)*
##### Block proposals voting

* Primary source file: [link to the code:](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_delegate/client_baking_votes.ml)
* New block proposal vote operation type: [link to the code:](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_protocol/operation_repr.ml#L56)
* Running the voter daemon: [link to the code](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_delegate/baking_commands.ml#L461)

##### RPC Handlers
* Propse Block RPC definition: [link to the code](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/lib_shell_services/block_services.ml#L842)
* Block proposal monitoring RPC definition: [link to the code]()
##### Block proposal notifications
* Requesting block proposal monitoring [link to code:](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_delegate/client_baking_blocks.ml#L205)
* Creating the stream of block proposals: [link to the code](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_delegate/client_daemon.ml#L164)
* Received a block proposal notification, begin voting: [link to the code:](https://gitlab.com/oxheadalpha/tezos/-/blob/block-proposals-staging/src/proto_alpha/lib_delegate/client_baking_votes.ml#L110)