# Problem
Flashbots builder builds blocks by optimizing miner payout constrained by block
size and Bundles/TX conflicts. Its hard to analyze the performance block building
algorithms due to bundle/tx conflicts.

# Goal
As a builder:
- need a tool/api to analyze/discover patterns in the bundles for optimizing
payout and/or latency.
- want to know if the impact of other possible block building algorithms

# Proposal
To aid this goal, I propose the following steps:
1. Implement a replay endpoint to extract metadata and debugging information about
blocks. This will provide us with the necessary data to understand the causes
and impacts of conflicts.
2. Use the replay endpoint to profile the exclusion reasons and their impact on a
representative set of blocks. This will help us identify the most impactful
parts of the problem to prioritize.

## Block Building Replay API
The replay API will take a block and the bundles used to build it originally and rebuild the same block recording information about the performance, and results about the block-building.
- The new RPC API will be registered to the node similar to how other flashbots endpoints are added (https://github.com/flashbots/block-validation-geth/blob/8d86570c124f7a0aff2abda17f1466bdcdaac3a0/node/node.go#L563)

### Types

// For each Bundle, returns the commit results and the exclusion reason if
// it was omitted from the new block
type CommitResult struct {
	BundleHash common.Hash
	GasUsed big.Int
	EffectiveGasPrice big.Int
	///
	/// TODO: discuss what other fields are useful
	///
	SimulationDuration time.Duration
	// how much gas left in the block
	RemainingGasPool float64
	// Error that caused the Bundle to be excluded.
	ExclusionErr error
}

#### Example

res := CommitResult {
	BundleHash: order.Bundle.Hash(),
	...
	// 10% gas left in the block when this bundle was tested for committing 
	RemainingGasPool: envDiff.gasPool,
	ExclusionErr: ErrBundleUnderpays,
}

### API
- requires: a sync'd node that contains the target block state (not pruned)

func (b *ReplayBuilder) buildBlock(blockHash common.Hash, bundles []types.SimulatedBundle) map[common.Hash]CommitResult {
	// ...
}

## Profiling Conflicts
Analyzing the conflicts is crucial to optimizing the block building algorithms.
With the assumption that there are 3 types of conflicts:
1. unfit bundle/tx (low gas, bad nonce, invalid, etc.)
2. resource conflict (tx already used by another bundle)
3. state conflict (Bundle1 and Bundle2 try to alter the same part of
the chain state, e.g. same dex pool without any shared TXs)

We'd run the profiler on a representative amount of blocks to understand the
distribution of conflicts. For example, if type 3 conflicts (state conflicts)
are rare (1 out of every 10k block), we'd prioritize addressing resource
conflicts to shave latency (type 2).

On the other hand, if state conflicts are causing the greedy algorithm to leave
considerable profit on the table, we may want to further investigate the causes
of these conflicts by running the reporting API topological sort algorithm on
the block builder. This involves removing successful transactions and seeing
how the inclusion of other transactions is affected.
- The complexity being O(n!/(n-k)!) n being the candidates, k approximately
being the candidate limit due to block size limit.
* We need to confirm this by looking at the data on this (no of bundles per
block, conflicts per blocks, etc.), but will most likely infeasible.
* **UPDATE(@mmrosum):** What we're usually seeing is around 500 bundles per
block, with around 10 of them not being in conflict.

### Example topological sort execution
- **green:** included
- **red:** excluded

#### Original Block Accepted On-Chain
miner-profit: 1 ETH

  digraph {
    compound=true;
    splines=ortho;

    graph [ordering=in, rankdir=TB];
    node [];

    bundleY [shape=record, label="{Tx000|{Bundle B&#92;n|{<bb>TxB1|Tx001|TxB2}}|Tx002&#92;n|Tx003&#92;n}"]
    
    #bundle2 -> bundleY:bb;

    subgraph blockz {
        graph [ordering=in];
      label = "Block";
	bundle1 [shape=record, label="{Bundle A&#92;n|{TxA1|Tx000|TxA2}}", color=red]
    bundle2 [shape=record, label="{Bundle B&#92;n|{TxB1|Tx001|TxB2}}" color=green]
	bundle3 [shape=record, label="{Bundle C&#92;n|{TxC1|Tx003}}" color=red]
    //bundle2 -> bundle1 [style=invisible, arrowsize=0, color="#505050", margin=2];
    bundle1 -> bundle3 [style=invisible, arrowsize=0, color="#505050", margin=2];
    bundle3 -> bundle2 [style=invisible, arrowsize=0, color="#505050", margin=2];
    
        bundle2 -> bundleY:bb [color=green];
    };
  }

#### Alternative block after removing the highest priority successful commit
miner-profit: 1.1 ETH

  digraph {
    compound=true;
    splines=ortho;

    graph [ordering=in, rankdir=TB];
    node [];

    bundleY [shape=record, label="{{Bundle A&#92;n|{<bb>TxA1|Tx000|TxA2}}|{Bundle C&#92;n|{<bc>TxC1|Tx003}}|Tx002&#92;n}"]    

    subgraph blockz {
        graph [ordering=in];
      label = "Block";
	bundle1 [shape=record, label="{Bundle A&#92;n|{TxA1|Tx000|TxA2}}", color=green]
	bundle3 [shape=record, label="{Bundle C&#92;n|{TxC1|Tx003}}" color=green]
    //bundle2 -> bundle1 [style=invisible, arrowsize=0, color="#505050", margin=2];
    bundle1 -> bundle3 [style=invisible, arrowsize=0, color="#505050", margin=2];

    bundle1 -> bundleY:bb [color=green];
    bundle3 -> bundleY:bc [color=green];
    };
  }

#### Final Dependency Graph

digraph{
    bundle2 -> Tx001
    bundle3 -> Tx003
    bundle1 -> Tx000
    bundle3 -> bundle2
    bundle1 -> bundle2
}