Rearchitect `bdk_electrum` syncing/scanning.

[evanlinjin]

How does syncing/scanning work now?

Currently, updating bdk_chain structures with bdk_electrum looks like this:

• The first round of fetching from the Electrum API:

  1. Grab latest blocks atomically from Electrum.
  2. Fetch history of txs from Electrum. Each tx is in form txid + conf_height.
  3. Create anchors for the fetched txs (by anchoring confirmed txids to the lowest-possible block fetched in step 1.).
  4. The update is returned as an ElectrumUpdate which is returned to the bdk_chain structures for processing.

• The update only contains txids. We determine the missing full transactions from TxGraph.

• The second round of fetching from the Electrum API: fetch missing full transactions. We then apply this to TxGraph.

Problems with the current implementation

1. The first round of fetching requires an unwieldy loop. This is required because of the following combination of factors:

   • We fetch histories of different spks in separate calls and we cannot guarantee the consistency between the calls.
   • Each txid is returned with txid + height. We don't have the confirmation blockhash, so we cannot know whether two txs confirmed at the same height can co-exist (they can be in conflicting blocks!).

   We mitigate this problem by fetching the chain tip height+hash before fetching txs, and ensuring the tip still exists in the best chain after. If it is not, we need to fetch tx histories again (hence, the purpose of the loop).

   However, there is a chance (although small) of this logic returning an inconsistent history. If a double-reorg occurs, where a stale-block appears in the best chain again.

2. TODO: I need to finish this ticket!

[LLFourn]

IMO the problem (1) mentioned above by @evanlinjin is minor. It's little concern to users but it would be nice to remove this convoluted logic. I presume he was just starting with the least important one first and didn't get to finish.

The important problem with the current system is it requires us to lock the wallet three times:

1. To start the sync process
2. To figure out which transactions we need to download
3. To apply the update

This makes it very difficult to package this process into a kind of opaque SynxRequest that is passed between components like @notmandatory is trying to do in #1194. If the approach in #1194 worked for electrum too then it would be a fantastic improvement in API.

How can we communicate to electrum what transactions are missing without locking the wallet

In brief here are a few ways:

1. Clone a HashSet<Txid> out of TxGraph to indicate what's missing. (problem: copy unbounded number of txids)
2. Clone a Arc<RwLock<HashSet<Txid>>> out of TxGraph (problem: sync primitives not available in no_std)
3. Some kind of cheaply clonable compressed set like bloom filter (problem: false positives)
4. Use heuristics to guess whether the transaction is needed to be downloaded (problem: user has to manage these implicit rules and do things in a certain way to get the right)
5. Just cache transactions in the electrum client

My proposal

Ok so I don't see a problem with 5. Fleshing it out more:

1. Any time the client downloads a tx it would keep it in memory by txid
2. You can have a method on the client like add_to_tx_cache(tx) for which you can add all the transactions in the graph when you load it from disk. If the developer forgets to do this then the worst case is you just download them all once.
3. Electrum always returns a full update TxGraph in one go because it has all the transactions cached locally.

This at least only copies around the number of transactions discovered during the sync for every sync so a sync of only one spk that discovers one transaction would only copy one transaction.

Using Arc<Transaction> in TxGraph

We can remove the copying too by using an Arc<Transaction> in TxGraph and in the electrum client transaction cache. So insert_tx becomes:

pub fn insert_tx<T: Into<Arc<Transaction>>>(&mut self, tx: T) -> ChangeSet<A> {
        let mut update = Self::default();
        update
            .txs
            .insert(tx.txid(), (TxNodeInternal::Whole(tx.into()), BTreeSet::new(), 0));
        self.apply_update(update)
    }

We could also put Arc<Transaction> in tx_graph::ChangeSet but we'd need to enable the rc feature of serde. I think we should do this as it doesn't cost anything and saves even more copying.

In general putting an Arc on a Transaction seems like the right thing to do here because it's the main potentially large variable size data structure we deal with so I think we'd be justified to put an Arc around it to reduce copying. It doesn't really introduce much friction if any at all.

[evanlinjin]

Using Arc<Transaction> does not solve all the copying problems, and I think that it will be more expensive than just copying over all the Txids from the wallet's TxGraph.

To make the cache useful, we need a map of Txid -> Transaction. We either need to copy all the Txid from TxGraph, or re-hash the transaction (which will be more expensive).

I think the best, and simplest, approach would to just maintain a HashSet of Txids in the Electrum chain source. In terms of memory use, we still need copies of txid, so it will be better with just a HashSet<Txid>.

[evanlinjin]

I started describing the ticket talking about the convoluted loop because there is a bug in bdk_electrum (and I suspect the bug is something to do with the loop).

[LLFourn]

Using Arc<Transaction> does not solve all the copying problems

What copying problems does it not solve?

To make the cache useful, we need a map of Txid -> Transaction. We either need to copy all the Txid from TxGraph, or re-hash the transaction (which will be more expensive).

So we're coping the HashMap<Txid, Arc<Transaction>> from TxGraph once at application startup into the electrum client. And if we don't the worst thing that happens is that all the transactions are re-loaded from electrum. I don't see a concern here.

I think the best, and simplest, approach would to just maintain a HashSet of Txids in the Electrum chain source. In terms of memory use, we still need copies of txid, so it will be better with just a HashSet<Txid>.

This is not simple because you are coupling the state of a TxGraph with the state of the HashSet<Txid> inside the electrum client. What if you want to update a different TxGraph? This TxGraphcould need a transaction in theHashSet<Txid>`. It will be invisibly omitted from the update without the caller having any warning or indication that this is happening. Coupling is complexity. An internal cache transaction cache doesn't couple the client with the state of any other mechanism and also removes all runtime tx copying.

[notmandatory]

fixed by #1403