Definition of Robustness

[saltiniroberto]

The Consensus Protocol must guarantee the Robustness property as defined below.

This definition of robustness for the IBFT protocol is based on the definition of robustness for public transaction ledgers provided in Garay et al in "The Bitcoin Backbone Protocol: Analysis and Applications". For the purpose of this definition, the position of a transaction within the transaction ledger implemented by the IBFT protocol is defined as a pair with the first component corresponding to the height of the block including the transaction and the second component corresponding to the position of the transaction within the block.

Robustness Property The IBFT protocol implements a robust distributed permissioned transaction ledger with immediate finality and t-Byzantine-fault-tolerance if, provided that no more than t validators are Byzantine, it guarantees the following two properties:

• Persistence: If an honest node adds transaction T in position i of its local transaction ledger, then (i) T is the only transaction that can ever be added in position i by any other honest node, (ii) T will eventually be added to the local transaction ledger of any other honest node.
• Liveness: Provided that a transaction is submitted to all honest validators, then the transaction will eventually be included in the distributed permissioned transaction ledger.

Finality The definition of persistence provided above implies Immediate Finality, i.e. every block created must be final.

Note: This issue is somehow related to #1 but differ in the intent. The intent of #1 is to explain why this definition was chosen, whereas the purpose of this issue is to provide the definition.

[drequinox]

This definition is subjective and does not capture all required properties. Instead of using this definition could we just simply say that the consensus algorithm must provide liveness and safety and then define the properties of safety and liveness separately. This approach will ensure that we can reason about the properties logically and extensively. There seems to be an overlap in the definition (ii) of persistence and liveness, therefore we should restructure and add more elements to it to make it clearer.

[drequinox]

Regarding finality, The implied definition seems OK, but should we differentiate here between immediate finality and probabilistic finality and provide some attributes which could clarify what type of finality we mean here, e.g., irrevocability is one of the attributes of finality. Again the aim is to be 100% clear about the requirements.

[saltiniroberto]

@drequinox Would you be able to outline which of the required properties are not captured by this definition?

Regarding the overlap between persistence and liveness, please see issue #1

[drequinox]

I think we should clearly define the properties that we need from our protocol. We must remove ambiguity and individually identify all features of our protocol, which will help us to design and reason about these properties easily and more logically. In the current definition of 'robustness', I see overlaps in the description, which leads to uncertainty. I propose that we look at the basics. Fundamentally we need two guarantees from our protocol, liveness and safety. we can define safety requirements (at minimum) as

Agreement — Two different processes decide the same block.

Validity — An honest validator must have proposed the decided block, and the proposal itself must be a valid block.

Integrity — A process only decides for a block at most once (in a round)

For liveness, we need to ensure that our protocol always terminates. i.e. formally

Termination — Each honest process must decide (ensuring progress)

We then need to define invariants for all these properties and then show that our protocol ensures them. If we want our protocol to be useful, we must start from the basics.

[saltiniroberto]

The proposed definition of Validity does not really work as it is impossible to detect whether a block was proposed by an honest or malicious node. All that we can do is check whether it is valid. However, an empty block is a valid block. This means that we could end up in a chain where we only have empty blocks.

This is one of the reasons why the definition of Robustness is expressed by referring to transactions rather than blocks. Blocks are just a device used to batch transactions together to improve efficiency. However, what we ultimately care is the order of the transactions. Also, we should leave any mentions of round out of the picture in the definition as the fact that we use round is an implementation detail.

If we want to decompose the proposed definition of Robustness in sub-properties then I propose that we formulate them in the following way

Agreement: if an honest node adds transaction T1 in position i of its blockchain and another node adds transaction T2 in the same position i of its local blockchain, then the two transactions must be the same, i.e. T1 = T2.

Validity: Only valid transactions are added to the local blockchain of honest nodes.

Integrity: Once a transaction T is added in position i of the local blockchain of an honest node, transaction T will never be removed, replaced or changed of position.

Liveness: If a transaction is sent to all honest validators, then that transaction is eventually added to the local blockchain of all honest nodes.

We can then add another requirement stating that transactions must be organised in blocks according to the Ethereum protocol.

[drequinox]

The proposed definition of Validity does not really work as it is impossible to detect whether a block was proposed by an honest or malicious node. All that we can do is check whether it is valid. However, an empty block is a valid block. This means that we could end up in a chain where we only have empty blocks.

Let me rephrase. An honest and valid node must have proposed the block that all validators have agreed. i.e. the final decided block must not have been submitted by a faulty node. If it were, then we would have rejected it. The block that eventually makes it to the blockchain must be valid. I understand we cannot detect if the sender is byzantine or not, but we can always make sure by validating the block that if it has indeed come from a valid validator (i.e. do not accept blocks randomly from any node) and blocks conform to our definition of a valid block. I think an empty block is a valid block so this is not a concern, as long as it is correct, it's okay.

This is one of the reasons why the definition of Robustness is expressed by referring to transactions rather than blocks. Blocks are just a device used to batch transactions together to improve efficiency. However, what we ultimately care is the order of the transactions.

Transaction order is a different problem as compared to block ordering. Transaction order is simple sorting usually by nonce and price after a miner picks up the transactions. A block is what validators need to agree on.

Also, we should leave any mentions of round out of the picture in the definition as the fact that we use round is an implementation detail.

As far as I can see, all BFT protocols have been view-based, are we proposing a different approach here?

If we want to decompose the proposed definition of Robustness in sub-properties then I propose that we formulate them in the following way

As a universal rule, we must work on what is proposed by a proposer, i.e. a block, not a transaction.

Agreement: if an honest node adds transaction T1 in position i of its blockchain and another node adds transaction T2 in the same position i of its local blockchain, then the two transactions must be the same, i.e. T1 = T2.

In a blockchain, blocks are added, which contain transactions. Transaction order is a different problem as compared to block ordering. Transactions are already ordered in a block by a miner and are proposed as a block by a proposer, ensuring that whatever order (based on sorting algorithms) the transactions has been ordered in by the miner, remains the same when all other validators accept and writes the proposed block in their local blockchain. We are not trying to solve a transaction consensus problem here, this is a consensus problem on a block (composed of transactions), not on individual transactions.

Validity: Only valid transactions are added to the local blockchain of honest nodes.

I suggest we change it to, only valid blocks . . . . , because Transaction validation occurs at the transaction pool level already, block validation and agreement is what we need. Integrity: Once a transaction T is added in position i of the local blockchain of an honest node, transaction T will never be removed, replaced or changed of position.

Blockchain consensus algorithms decide on a proposal i.e a block of transactions proposed by a proposer, not a transaction. Also, the proposed definition needs to be revised as it appears more like an overlap between immutability (removed, replaced, modified) property and proposed integrity property. Integrity from a consensus protocol point of view simply means that a node makes a decision at most once. From a transaction point of view, immutability and finality properties should be considered

Liveness: If a transaction is sent to all honest validators, then that transaction is eventually added to the local blockchain of all honest nodes.

A proposal made by a proposer in a blockchain consensus algorithm is a block, not a transaction. The protocol must decide on a block, not a transaction. We can then add another requirement stating that transactions must be organised in blocks according to the Ethereum protocol.

This is already the case, we decide on blocks, not transactions.

[kubasiemion]

As agreed on 06.11.2019

[kubasiemion]

REJECTED