search

LLFourn / bdk_core_staging

Staging area for bdk_core initial development
15 stars 12 forks source link

Super-issue regarding transaction history consistency #120

Open evanlinjin opened 1 year ago

evanlinjin commented 1 year ago

As mentioned by @LLFourn in a set of messages, there are scenarios which we should handle:

Also related:

Contextual quotes

This is why I am concerned about just allowing arbitrary graph insertions. We have to come up with an algorithm to always make txs in chain consistent with graph on every insertion. -- @LLFourn

LLFourn commented 1 year ago

To give further context. Inserting a tx into a graph without a position can make two transactions that are currently non-conflicting conflict if that new tx is the ancestor of one tx and conflicts with the ancestor of another. So if we want to allow positionless graph insertions we must not allow it directly into the graph. There is also an error case when both conflicting transactions are confirmed already.

So anytime we insert a tx at chain position we need to evict conflicts and all their children in the chain. However we need to walk all the child nodes in the DAG in the TxGraph to find the transactions to evict (note we don't care if the all children are in the chain or not -- perhaps a child is not in the chain but a grandchild is, we still need to evict the grandchild).

If we allow positionless insertion into the graph we still might need to do eviction. If the tx you are inserting into the graph does conflict with a tx that is in the chain then you need to evict all child transactions of that new graph transaction from the chain before inserting it into the graph.

Furthermore, any time you insert a new tx into the chain which spends from an output that is not in the chain but is in the graph you need to check whether the graph allows its parent transactions to be in the chain or not. If the parent couldln't be in the chain then that new tx can't be in their either. I think this check needs to be done regardless of whether we allow permissionless insertion.

Possible I'm missing something but that might be it.

LLFourn commented 1 year ago

Another problem: https://github.com/LLFourn/bdk_core_staging/issues/135

evanlinjin commented 1 year ago

Completed by #138, the last missing piece is CPFP feerate calculation logic. Will make a separate ticket for this.

LLFourn commented 1 year ago

I don't think we can say this is really dealt with. Do we have a test case for:

Furthermore, any time you insert a new tx into the chain which spends from an output that is not in the chain but is in the graph you need to check whether the graph allows its parent transactions to be in the chain or not. If the parent couldn't be in the chain then that new tx can't be in there either. I think this check needs to be done regardless of whether we allow positionless insertion.