Compressed block headers & merkle proofs over low bandwidth communications

[willcl-ark]

I have written up an Electrum Protocol proposal which seeks to improve both:

1. Reduce RPC bandwidth requirements (compressed block headers + protobuf/CBOR (de)serialisation)
2. Reduce requirements of Clients making calls (removing block_height requirement)

The proposal can be found here: https://github.com/willcl-ark/electrum-low-bandwidth/blob/master/spec.adoc

I will cross-reference kyuupichan/aiorpcX#12, because it covers much of the same ground.

I am currently looking for feedback and would appreciate any comments on the proposal you may have.

@JeremyRand I notice in kyuupichan/aiorpcX#12 there is some conversation on performance; do you have any data on how many requests some of the more active Electrum Servers are handling? I want to understand if serialisation performance can really be significant or not

[willcl-ark]

I should also cross-reference #712 from this repo

[JeremyRand]

Okay, so regarding compressed block headers, I have some comments about how this might interact with AuxPoW chains:

1. It would probably make sense to compress the parent block header.
2. SIdechains frequently have more than 1 parent chain, e.g. Bitcoin and BCH are both regularly used as parent chains of Namecoin.
3. The parent header's version field may be more diverse because of the use of multiple parent chains, i.e. there may be some benefit to supporting more than 7 previous values.
4. The parent header's previous block hash field might be a repeat of the previous block's, because the sidechain and the parent chain have different difficulties.
5. The parent header's previous block hash field might be the hash of a block from more than 1 block ago, due to the usage of multiple parent chains.
6. The parent header's nbits field is likely to change every time the parent chain changes, so being able to remember more than 1 previous nbits value might be helpful. (Also, my understanding is that BCH's nbits changes every block, so compression of nbits is only useful for a subset of parent chains.)
7. Implementing all of the above suggestions would probably cause the compression bitfield header to be more than 1 byte, so it would be beneficial to get some data on exactly how the tradeoff works in practice.
8. It would be useful to evaluate how much compression each of these proposals achieves both with and without DEFLATE. E.g. long repeated strings are likely to be heavily compressed by DEFLATE even if we don't explicitly compress them in the protocol.

Also tagging Namecoin Core maintainer @domob1812 in case he has opinions on how this serialization might interact with the Namecoin P2P wire protocol.

[JeremyRand]

@JeremyRand I notice in kyuupichan/aiorpcX#12 there is some conversation on performance; do you have any data on how many requests some of the more active Electrum Servers are handling?

I don't personally run any public ElectrumX servers. I have contact info for some of the operators of the public Namecoin ElectrumX servers, but I'm guessing that the Bitcoin ElectrumX servers are under considerably heavier load than Namecoin, so the Bitcoin ElectrumX operators are probably the people whose data matters.

[domob1812]

I don't have any specific things to add to what @JeremyRand already posted.

[SomberNight]

I have written up an Electrum Protocol proposal which seeks to improve both:
(1) Reduce RPC bandwidth requirements (compressed block headers + protobuf/CBOR (de)serialisation)
(2) Reduce requirements of Clients making calls (removing block_height requirement)

I think these are independent proposals.

Re (2),

Make height an optional parameter, now safe since BIP30 [8] and BIP34 [9]

note that the current implementation of blockchain.transaction.get_merkle in this present codebase uses the block_height to answer the request:

electrumx/electrumx/server/session.py

Lines 665 to 667 in bc175a6

	async def merkle_branch_for_tx_hash(self, height, tx_hash):
	'''Return a triple (branch, tx_pos, cost).'''
	tx_hashes, tx_hashes_cost = await self.tx_hashes_at_blockheight(height)

(although this could be changed; e.g. by calling the bitcoind getrawtransaction RPC (though minimising the bitcoind RPC invocations helps performance))

Add an additional transaction_index field to the return values in addition to the block_height so that a short_channel_id can be created for the transaction’s outputs.

I don't understand this. as per https://github.com/kyuupichan/electrumx/blob/bc175a6ed42cd6b968a556e27ba0f4408ae3b800/docs/protocol-methods.rst#blockchaintransactionget_merkle
the result already includes a block_height and a pos. Assuming you have the raw tx and can figure out the output index yourself, what else do you need to calculate a short_channel_id?

[remyers]

On Thu, May 21, 2020 at 6:50 PM ghost43 ***@***.***> wrote: I have written up an Electrum Protocol proposal which seeks to improve both: (1) Reduce RPC bandwidth requirements (compressed block headers + protobuf/CBOR (de)serialisation) (2) Reduce requirements of Clients making calls (removing block_height requirement) I think these are independent proposals.

Good point; perhaps there are even three logically separable proposals from an implementation stand point: (1a) compressed block headers (1b) protobuf/CBOR (de)serialization 2) Reduce requirements of Clients making calls (removing block_height requirement)

Re (2), Make height an optional parameter, now safe since BIP30 [8] and BIP34 [9] note that the current implementation of blockchain.transaction.get_merkle in this present codebase uses the block_height to answer the request: https://github.com/kyuupichan/electrumx/blob/bc175a6ed42cd6b968a556e27ba0f4408ae3b800/electrumx/server/session.py#L665-L667 (although this could be changed; e.g. by calling the bitcoind getrawtransaction RPC (though minimising the bitcoind RPC invocations helps performance))

Perhaps a db index that maps txids to block heights would be more performant, but I'm not sure what the other trade-offs would be. Currently, if a light client submits a new transaction using blockchain.transaction.broadcast how should they later query for a proof it was confirmed in a block? They only know the txid, but how are they supposed to know the height? Ultimately a light client will need the server to make a bitcoind getrawtransaction call somehow right?

Add an additional transaction_index field to the return values in addition to the block_height so that a short_channel_id can be created for the transaction’s outputs. I don't understand this. as per https://github.com/kyuupichan/electrumx/blob/bc175a6ed42cd6b968a556e27ba0f4408ae3b800/docs/protocol-methods.rst#blockchaintransactionget_merkle the result already includes a block_height and a pos. Assuming you have the raw tx and can figure out the output index yourself, what else do you need to calculate a short_channel_id? Oh good! I suggested to Will he add that to support Lightning

short_channel_id, but I must have been looking at a different version of the return json that didn't have the `pos` field. Thanks for pointing that out. All the best,

…

-- Richard

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1007 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACBMAPAUO6QWSVTVJWK5S5TRSVLWJANCNFSM4NF5LRWQ> .

[remyers]

On Thu, May 21, 2020 at 7:06 AM JeremyRand ***@***.***> wrote: Okay, so regarding compressed block headers, I have some comments about how this might interact with AuxPoW chains: 1. It would probably make sense to compress the parent block header. If nodes for a merge-mined chains exchange parent chain block headers then

exchanging compressed block headers does make sense. Since this scheme is for over-the-wire transport the AuxPoW header should still continue to reference a full parent block header hash of course.

1. The parent header's version field may be more diverse because of the use of multiple parent chains, i.e. there may be some benefit to supporting more than 7 previous values. If the merge mined chain uses compressed headers then the compression

would presumably be less if it has more diverse version fields. I wouldn't want to burden less diverse chains with an addition `bitfield` byte though. Perhaps someone can check a few of these chains to see how much this diversity hurts the overall compression.

1. The parent header's previous block hash field might be a repeat of the previous block's, because the sidechain and the parent chain have different difficulties. This proposal is only looking at block headers, but maybe there's a

similar scheme that could be used to save space in the AuxPoW field. I think that's out of scope here though.

1. The parent header's previous block hash field might be the hash of a block from more than 1 block ago, due to the usage of multiple parent chains. Same as above, this sounds like something that that a separate proposal

about compressing an AuxPoW header should consider.

1. The parent header's nbits field is likely to change every time the parent chain changes, so being able to remember more than 1 previous nbits value might be helpful. (Also, my understanding is that BCH's nbits changes every block, so compression of nbits is only useful for a subset of parent chains.) Some modeling would be helpful here, but adding another `bitfield` byte

for this would unnecessarily burden the main chain(s). This kind of consideration would be better handled in a separate proposal for AuxPoW header compression.

1. Implementing all of the above suggestions would probably cause the compression bitfield header to be more than 1 byte, so it would be beneficial to get some data on exactly how the tradeoff works in practice. Agreed. 1. It would be useful to evaluate how much compression each of these proposals achieves both with and without DEFLATE. E.g. long repeated strings are likely to be heavily compressed by DEFLATE even if we don't explicitly compress them in the protocol. Agree it would be useful to evaluate DEFLATE vs. compressed headers with 1

byte `bitfield` for over-the-wire transport. You also might consider an alternative encoding for the AuxPoW Header to handle optimizations specific to nodes that exchange merge mined blocks.

…

Also tagging Namecoin Core maintainer @domob1812 <https://github.com/domob1812> in case he has opinions on how this serialization might interact with the Namecoin P2P wire protocol. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1007 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACBMAPA2J63M2NPDXEJK5KTRSSZGTANCNFSM4NF5LRWQ> .

[kyuupichan]

I'll be taking the protocol in a different direction going forwards

[willcl-ark]

@kyuupichan what direction are you looking to take it?