It contain list of transaction sorted by GasPrice, prepared to be included into new block. So when talking about gas it is important to make destinction between: * GasPrice or just Price: represents amount that transaction is going to pay for unit of GasSpend * GasSpend or just Gas: is amount of how much vm worked to execute this transaction. * Tx GasLimit: how much transaction is wiling to pay for execution. (GasLimit > GasPrice*GasSpend) * Block GasLimit: How full can we get our block.
Fuel as UTXO system depends on output and input of transaction and proving that child is valid and depends on some parent in transaction can be challenging. All transactios in pool are expected to be in some sense valid or better said has potential to be includable, this plays a big role on protection of spaming and on design of fuel txpool. We are building dependency structures that would describe that parent->child relationship.
From miro diagram we can see that txpool is used by: * p2p subsystem: receive/broadcast new tx. * Block importer: clean included tx * Block producer: take N number of transactions.
All Tx should be wrapped inside Arc so that we can easily move them if there is need and soo that they can be referenced in multiple places.
TxPool should be periodically flush to disk so that we can recover transactions is case of client restart. Ommited for first version.
TxPool trait is interface that TxPool is going to implement and can be found here
We will need to have at least three structures that do sorting of tx.
* by hash: Ordinary HashMap, maps hash to Tx. For fast lookup.
* by PriceSort: sorted structure that sort all transaction by GasPrice. Most optimal structure can be BinaryHeap for fast sorting/inserting but it does have some downsides when we want to remove one item. For use case when a lot of tx are going to be removed we can just recreate structure from scratch. For first interation we can use simple BTreeMap that sorts all inputs.
* by Dependency: With every fuel transaction, inputs and outputs change state and we need to be aware of it. Graph is main defensive structure behind ddos, every transaction that we include in pool should have potential to be included in next block in that sense Graph represent connection between parent and child where child is transaction that depends on execution output of parent that is found inside database or transaction pool.
Few reasonings on decision and restrains made by txpool
Visualization of dependencies between three transactions:
Problem1: T2 arriving before T1. Solution: Have restriction that broadcast of hashes need to contain ancestor hashes and they all need to be sorted by gasPrice
Problem2: if T2 gas price is higher then T1. This can be problematic on txpool with different sizes. One big enough pull could contains T1 but other one would prune it and we could not prove that T2 can be included without T1. Solution: Have restriction on linked transaction within same block so that GasPrice is strictly going down. This will effect newly create contract (created in same block) but not old one.
Usage: Insertion of new T4
Graph will be needed for relationship between dependable transactions so that if one of them get included/removed/replaced we need to know what to do with their dependent childrens.
We will need map of all outputs in same structure so that we can fast search them. That would be something like HashMap<UtxoId, CoinState> and HashMap<ContractId,ContractState> for both Coin and Contract state.
It is most straightforward one: take PriceSort and iterate over transaction. DependencyGraph inclusion garantee us that every transaction in that sorted array can be included, but only after execution that trasansaction we would be sure that is can go inside block.
Some things and ideas what we can add in future:
gas_limit*gas_price for transactions with depth one (Tx where all inputs can be found in db).