rfc: should Bitcoin Core add a -wtxindex?

[Sjors]

I'm working on a revival of adding witness support to gettxproof / verifytxproof in bitcoin/bitcoin#32844. I have prototype here in Sjors/bitcoin#116.

An open question is whether this needs a witness equivalent for -txindex, such as Sjors/bitcoin#117.

[SomberNight]

Hey Sjors, dumping my jumbled thoughts here.

First of all, re comments bitcoin/bitcoin#32844 (comment) and bitcoin/bitcoin#32844 (comment).

The request I would like an electrum server, assuming txindex=1, to be able to serve is:

bc.tx.get_merkle_witness(txid), (so given just a txid,)

return a dict containing:

• wtxid
• block_height
• block_hash
• pos (index of tx in block)
• merkle or wmerkle
  • exactly one of the two
  • merkle is the Satoshi-SPV proof, in case there is no witness commitment in the block
  • wmerkle is the witness-SPV proof otherwise
• cb_tx, the generation/coinbase tx
• cb_proof, the Satoshi-SPV proof for the generation tx

I assume you can also make the request by wtxid? If not, why not?

Two design questions:

• should the input param be txid or wtxid
• should the input params contain a block_height (or perhaps a block_hash)
  • (note: ElectrumX can map block_height<->block_hash)

---

Re input params containing a block_height:

The current blockchain.transaction.get_merkle protocol method for Satoshi SPV (non-witness) takes (txid, height).

It came up once or twice over the years that it would be possible to drop requiring the height and that might make life of certain clients a tiny bit easier. (e.g. #43)

I had a design in mind where ElectrumX would have its own txid->txnum map (txnum is a 5 byte int representing the canonical index of a mined tx in the best chain), essentially it own txindex.
There is already an array containing the cumulative number of txs at the end of height N, allowing txnum->block_height lookups.
The two together would allow txid->txnum->block_height lookups.

Even without ElectrumX having that txid->txnum map, if bitcoind has -txindex, ElectrumX can still do a txid->block_height lookup by asking bitcoind: we can use the "getrawtransaction" bitcoind RPC with verbose=1, read the "blockhash" from the response (and map that to a block_height in ElectrumX).

Anyway, I keep re-realising that requiring the client to supply the block_height makes life easier for the server. It would be easier to just keep requiring it...

I previously had another use-case for an internal txindex-duplicate (my original server impl for serving outpoint subscriptions), but that usecase kind of evaporated for now: as bitcoind added -txospenderindex, ElectrumX is instead using that for serving outpoint subs. Hence it would be even more wasteful to duplicate txindex now.

---

Re bc.tx.get_merkle_witness taking txid vs wtxid:

Alternatively, the electrum protocol method could be bc.tx.get_merkle_witness(wtxid, height).

Now the protocol return value could be similar to before, just omitting the wtxid.
Returning a dict with:

• block_height (the input height is just a hint to the server that the server could disregard)
• block_hash
• pos (index of tx in block)
• merkle or wmerkle
  • exactly one of the two
  • merkle is the Satoshi-SPV proof, in case there is no witness commitment in the block
  • wmerkle is the witness-SPV proof otherwise
• cb_tx, the generation/coinbase tx
• cb_proof, the Satoshi-SPV proof for the generation tx

The electrum protocol blockchain.scriptpubkey.get_history (or blockchain.scripthash.get_history prior to v1.7) returns a list of (txid, height) pairs.
The status of an address(/scriptpubkey/scripthash) is also defined based on the same: it is the hash of the list of (txid, height) pairs.

Consider that a client connects to serverA, requests the history of a scriptpubkey (spk1) and gets a list of (txid, height) pairs. The client then separately requests the full raw txs using blockchain.transaction.get for the txids, and also downloads wmerkle proofs, from serverA. Let's say for txid1, it received rawtx1 and persisted that. Then a bit later the wmerkle proof is received but it fails validation. Hence the client disconnects from this server and connects to a different one, serverB.

The client then requests the history of spk1 from serverB, and sees it's the same it already had saved. Should it re-request the full raw txs for the txids? It already has matching full raw txs for each txid but maybe this server has txs with different witnesses!

(1) Imagine bc.tx.get_merkle_witness takes a txid as input. In that case the client can just request wmerkle proofs for the txids, and if the corresponding responses contain a wtxid, the client can compare that to the full raw txs it already has saved. If they mismatch, the client would delete the full raw txs it has and re-send blockchain.transaction.get for those txids now.

(2) Alternatively, imagine bc.tx.get_merkle_witness takes a wtxid as input. In that case the client should pre-emptively delete the full raw txs it already has saved that have not yet been successfully witness-SPV-ed. Re-send blockchain.transaction.get for those txids to get full txs from serverB. Then request wmerkle proofs for the wtxids.

One complication is that often the client would have already downloaded the raw tx while it was still in the mempool, but of course SPV will only happen after the server tells the client the tx got mined.

Note that flow (1) is a bit nicer for the client, but both seems to work.
In general all this is somewhat complicated and hard to fully understand until implementing it :/
but overall, I think we can make-do without a wtxid index.

---

Note that if bitcoind had a wtxindex, the electrum server could certainly utilise it.
(Assuming bitcoind then also supported getrawtransaction(wtxid) -> rawtx calls.)

I think we could change the electrum protocol to use wtxids instead of txids in several methods.

• the status of a scriptpubkey could be based on wtxids
• get_history could return a list of (wtxid, height) pairs

but I think we would still need a txindex either in bitcoind or re-implemented in the electrum server anyway...

For example, blockchain.outpoint.subscribe takes an outpoint (i.e. txid), and needs to return (among other things) the block_height the outpoint got funded in. That needs a (non-witness) txindex.

[Sjors]

Assuming bitcoind then also supported getrawtransaction(wtxid) -> rawtx calls.

We do for IPC now: getTransactionsByTxID() and getTransactionsByWitnessID(), which can also take an array so they're more efficient for bulk lookups.

https://github.com/bitcoin/bitcoin/blob/master/src/ipc/capnp/mining.capnp

[cculianu]

Anyway, I keep re-realising that requiring the client to supply the block_height makes life easier for the server. It would be easier to just keep requiring it...

Note that if you don't have a txindex -- the server must deserialize the entire block in question, and then perform a linear search for the txn. This eats CPU and doesn't scale terribly well. Imagine like 20 or 50 or 200 clients all asking for txns at the same time, potentially in disparate blocks.. the bitcoind daemon must repeatedly deserialize each block for each txn, each time! It's nuts. There's no cachine of this on the daemon-side. If you ask for the same exact txn 100 times, it will deserialize the entire block that txn lives-in 100 times! The txn may only be ~200 bytes but it must churn through >1MB of data each time! Nuts! (This scenario is only the case if txindex=0).

The bitcoind rpc basically was not really optimized for the usecase of retrieving a single txn without txindex enabled.

Txindex allows the daemon to know precisely where in the block file a txn lives -- and only read that info. It's orders of magnitude faster... so yeah. -txindex does eat space but buys you performance.

[SomberNight]

Note that if you don't have a txindex -- the server must deserialize the entire block in question, and then perform a linear search for the txn.

Good point. Thanks.

The question arises how you plan witness merkle proof lookups without a wtxid index then, @Sjors? Do you plan to scan the full block for each proof?

If having a wtxindex would significantly improve performance, then public electrum servers would probably want to make the tradeoff and offer up the extra disk space.

---

For Satoshi SPV proofs (blockchain.transaction.get_merkle), ElectrumX reads all the txids (not full raw txs) that are in the block at the provided height (from its on-disk txnum->txid map), and then linearly scans them to find the position in the block and to efficiently look up the rest of the txids needed based on the binary representation of the pos. The list of txids in the block is then cached.

electrumx/src/electrumx/server/db.py

Lines 147 to 148 in 280cb33

	# on-disk: 32 byte txids in chain order, allows (tx_num -> txid_rev) map
	self.hashes_file = util.LogicalFile('meta/hashes', 4, 16000000)

electrumx/src/electrumx/server/session.py

Line 948 in 280cb33

txids_rev, txids_cost = await self.txids_rev_at_blockheight(height)

electrumx/src/electrumx/server/session.py

Line 979 in 280cb33

txids_rev = self._txids_cache.get(height)

So this is also linear time, but at least the disk reads are cached, and it's only the txids, not the full block, that is operated on.
I also wonder how the performance of this, the ElectrumX impl, compares to bitcoin core's gettxoutproof with txindex. (because if bitcoind is faster, we could switch to that :P)

[Sjors]

The question arises how you plan witness merkle proof lookups without a wtxid index then, @Sjors? Do you plan to scan the full block for each proof?

I guess so, I haven't looked at the implementation in detail: Sjors/bitcoin#116

If having a wtxindex would significantly improve performance, then public electrum servers would probably want to make the tradeoff and offer up the extra disk space.

I would be useful to have a benchmark for ElectrumX that compares Sjors/bitcoin#116 to Sjors/bitcoin#118.