RCP-241101A: Consensus ordering v2

[dr-orlovsky]

author: @dr-orlovsky
layers: consensus
breaking: consensus, api
requires: RCP-241024A
supersedes: RCP-241013A, RCP-240731A

Background

Consensus ordering is a way how we deterministically define a order in which contract operations are validated and added to the contract state. The details of the current procedure and discussion can be found in RCP-241013A and RCP-240731A.

Motivation

Assume a sequence of state transitions StA, StB, StC, with each one following transition spending inputs of the previous one. Let us name the corresponding witness transactions WtxA, WtxB, WtxC. Lets assume these transactions are otherwise unrelated (i.e. they do not spend outputs of each other neither directly or indirectly, i.e. do not belong to the same transaction graph onchain). In this case, a re-org may happen such that WtxC will be included in a block before WtxB, putting StC in a consensus ordering before StB, making StB state either invalid - or requiring a validation algorithm to include state from arbitrary state transition, including unvalidated ones. This is in fact a side-channeling which makes it really hard to formally ensure and audit that all state transitions are validated in the right way.

The problem is doubled by the fact that one contract may operate over multiple chains.

Proposal

1. Make contracts chain-specific, excluding cross-chain race conditions (as required by RCP-241024A)
2. Use a block height of a witness transaction as a base for the ordering
3. For the protection from re-orgs, as well for the operation ordering within the same block, use a PoW, such that the number of zero bits (divided by a chain-specific factor) is added to the block height value and the resulting sum is used for the final consensus ordering of the operations.
4. Evaluate state of the contract using consensus ordering, requiring inputs for the operation to come from already validated operations - or fail otherwise.
5. Blockchain-specific parameter of the safe number of blocks (amount of PoW units to add) must be a consensus parameter defined at the level of single-use seal type.

Example

Order = height + pow / factor

	Height	PoW	Order
StA	1	0	1
StB	21	0	21
StC	20	1	22
StD	30	0	30

Rationale

The proposed approach allows to run all parts of the validation and contract state computation in one go, without an introduction of any side-channel information which may potentially skip the normal validation flow. It is also easy to audit.

The use of PoW value instead of nonce is needed to prevent malicious actors from using high value for the nonce, requiring beneficiaries to wait a long time before being able to use assets in a secure way.

PoW is divided over a blockchain-specific factor since each blockchain has a different block production time, and thus a different amount of work would be needed

[dr-orlovsky]

After a discussion on a call with @nicbus @zoedberg @St333p @fedsten I have clarified the following part of the proposal:

5. Blockchain-specific parameter of the safe number of blocks (amount of PoW units to add) must be a consensus parameter defined at the level of single-use seal type.

[nicbus]

Thinking about this, I see some issues.

1. Everyone needs to validate the consensus ordering for all transitions, otherwise malicious actors might complete a transfer with less than the required PoW (e.g. 0) and later recipients wouldn't have a way to tell if the ordering is correct (a reorg could then put the witness TX for an RGB transition before the one creating its input, burning assets).

2. If everyone needs to validate the final consensus ordering (which includes the PoW) a reorg could change the "distance" (the blockchain-specific parameter) between two transitions to less than the required value, breaking future validation.

3. Even if no reorg happens, if a series of consecutive transfers is attempted while not enough blocks are mined to keep a "safe distance", each successive transfer in the chain would need to increase the PoW, quickly getting it to a point where it becomes infeasible and further transfers would need to wait for several blocks to be mined in order to proceed, reducing usability.

Some examples to clarify the mentioned points, assuming the contract commits to a blockchain-specific parameter of 3 and that StA inputs have 3+ confirmations already.

1. if only the consensus ordering for the last transition is validated

   initial situation:

   	Height	PoW	Order
   StA	21	0	21
   StB	22	0	22
   StC	22	3	25

   malicious actors create and accept StB with incorrect PoW 0 (it should have been 3), then spend (in StC) to a honest actor that can't detect the anomaly, because he'll be only validating StC (which has the correct amount of PoW)

   after a reorg:

   	Height	PoW	Order
   StA	21	0	21
   StB	20	0	20
   StC	22	3	25

   after the reorg StB could be ordered before StA, burning assets

2. if everyone validates consensus ordering, a reorg could break validation even if PoW is correctly used

   initial situation:

   	Height	PoW	Order	Distance
   StA	21	0	21	3+
   StB	21	3	24	3
   StC	21	6	27	3

   PoW has been used correctly by all actors

   after a reorg:

   	Height	PoW	Order	Distance
   StA	21	0	21	3+
   StB	20	3	23	2
   StC	21	6	27	4

   after the reorg the "distance" between StA and StB would be only 2 and validation would fail

3. close-distance consecutive transfers increase the required PoW

   	Height	PoW	Order
   StA	21	0	21
   StB	21	3	24
   StC	21	6	27
   StD	22	8	30
   StE	22	11	33

   the amount of required PoW increases, quickly becoming unsustainable

[dr-orlovsky]

Yes, I agree this seems to be a problem. I think I have come to understanding how we can live without any consensus ordering at all; working on proof of concept.