ethexe: commitments architecture changes

[grishasobol]

Current approach

Currently (3633640) we have below commitments architecture:

1. Batch commitment contains:
   

   gear/ethexe/contracts/src/libraries/Gear.sol

   Lines 68 to 71 in 3633640

   	struct BatchCommitment {
   	CodeCommitment[] codeCommitments;
   	BlockCommitment[] blockCommitments;
   	}

2. Block commitment contains:
   

   gear/ethexe/contracts/src/libraries/Gear.sol

   Lines 53 to 59 in 3633640

   	struct BlockCommitment {
   	bytes32 hash;
   	uint48 timestamp;
   	bytes32 previousCommittedBlock;
   	bytes32 predecessorBlock;
   	StateTransition[] transitions;
   	}

3. Code commitment:
   

   gear/ethexe/contracts/src/libraries/Gear.sol

   Lines 47 to 51 in 3633640

   	struct CodeCommitment {
   	bytes32 id;
   	uint48 timestamp;
   	bool valid;
   	}

Problems with this approach

1. Gas allowance and off-chain transactions do not supported.
2. A lot of redundancy information if we have several block or code commitments, like:
   - timestamp - because we need timestamp only for the last block in commitments chain. And actually it's useless for codes.
   - predecessorBlock - equal for each block commitment
   - previousCommittedBlock - needed only for the first block in block commitments chain.
3. Transitions also could be optimised. For example: if we have two block commitments, and the first contains for program P transition H1 -> H2, and the second contains transition H2 -> H3, then we could make only H1 -> H3 and spend less amount of gas.

Possible solution

1. Introduce custom block to support gas-allowance and off-chain transactions:

struct GearBlock {
    bytes32 ethereum_block_hash;
    bytes32 off_chain_transactions_hash;
    uint64 gas_allowance;
}

2. Remove timestamp from code commitment (why it's possible will be explained in BatchCommitment)

struct CodeCommitment {
    bytes32 id;
    bool valid;
}

3. Remove block commitment and introduce ChainCommitment

struct ChainCommitment {
     bytes32 prev_committed_gear_block_hash; // To be sure we executes in right order
     StateTransition[] combined_transitions; // Transitions from all blocks in chain in a right order
     GearBlock[] blocks; // List of gear blocks (from oldest to newest), each `GearBlock` is emitted by router during commitBatch  
}

4. Batch commitment

struct BatchCommitment {
    // Timestamp of ethereum block for which this batch has been created
    // This timestamp is used to identify validator set to verify commitment (current or previous era)
    // We do not need timestamp for each code and block commitment now, because this timestamp must be used instead.
    uint64 createdForTimestamp;
    
    // Hash of ethereum block for which this batch has been created
    // This is used to identify whether router have to apply this batch,
    // it can be a batch from another branch and after reorg it's not actual anymore (currently we have predecessorBlock for this) 
    bytes32 createdForBlock;

    // Different commitments
    CodeCommitment[] code_commitments;
    ChainCommitment[] chain_commitment; // only 0 or 1 allowed, but this is to consider
    ValidatorsCommitment[] validators_commitment; // only 0 or 1 allowed
    ...
}

5. In router:

function commitBatch(BatchCommitment batch) {
    // Timestamp check, must be less then current and bigger then previous

    // This excludes possibility of next era validators to commit in current era 
    require(batch.createdForTimestamp < block.timstamp);

    // This excludes possibility of old era validators to commit in current era since at least one commit comes from new validators
    require(batch.createdForTimestamp > storage.last_committed_batch_timstamp);

    storage.last_committed_batch_timestamp = batch.createdForTimestamp;    

    // Check that batch has been created for block which is predecessor for current block
    require(isPredecessor(batch.createdForBlock));
    
    address[] validators = validatorsAt(batch.createdForTimestamp);    

    for c in batch.codeCommitment {
            // commit `c`
    }
    
    require(batch.chain_commitment < 2);
    if batch.chain_commitment.length == 1 {
          c = batch.chain_commitment[0];
          
          // Against the situations where two or more commitment transactions stuck in ethereum silmanteniusly.
          require(c.prev_committed_gear_block_hash == storage.last_committed_gear_block_hash);
          storage.last_committed_gear_block_hash = c.blocks[c.blocks.length - 1];

          for t in c.combined_transitions {
                // commit `t`
          }
          for b in c.blocks {
                emit BlockCommitted(b);
          }
    }
    
    //  the same for all other commitments types

    // check signatures using `validators`
}

6. In router storage, remove CommittedBlockInfo and append instead:

    struct Storage {
          ...
          uint64 last_committed_batch_timestamp;
          bytes32 last_committed_gear_block_hash;
          ...
    }

[grishasobol]

Big batch commitments

Problem

Current logic suppose, that if block producer creates a gear block and send it to other validators for execution, then block producer must create a batchCommitment, which includes freshly produced block and all other blocks which is not committed before current one. This can lead to a situation, when batch comment is too big to be applied in one ethereum block.

Solution

Allow block producer not include some blocks in a chain commitment (even this own freshly produced block). We have the same approach for code and other commitments. Also this allows to skip chain commitment at all, event if some blocks wait for commitment. The only one restriction must be that blocks in batch commitments must be from the same branch with block, for which producer published a block.

This would allow producer to control the cost of batch submission.

Example

Let's see an example.

/// For gear blocks:
/// [x] - empty block
/// [[x]] - not empty block
/// [[xc]] - committed block 

ETH BLOCKS_________[0]<-----[1]<-----[2]<-----[3]<-----[4]
GEAR BLOCKS________[0]<----[[1c]]<--[[2]]<----[3]<----[[4]]

Chain head [4] comes and producer creates a GearBlock block [[4]]. After that producer see before committing [[4]] he also have to commit [[2]], but committing both in one batch is impossible due ethereum limits. So, in this case producer could include in current batch only one block [[2]], skipping his own block [[4]] and supposing that next producer would include [[4]] in his batch. Validators which receives batch with block [[2]] are checking that [[2]] is a predecessor for currently processed [[4]] and all other usual commitment checks.

Problems

1. This proposal does not solve the problem when one gear block is too big to be applied in one ethereum block. But it does not make impossible to solve this in future adding partial commitments or something like that.
2. This approach is more actual for the time, when we would allow delayed commitments submissions (not right in the next block).

[grishasobol]

UPDATE:
Actually it's better to have (to keep) previous_committed_block_hash: H256 in BatchCommitment and remove then prev_committed_gear_block_hash from ChainCommitment