Re: [bitcoin-dev] Weak block thoughts...

["Jonathan Toomim (Toomim Bros)" <j@toom.im>]

[-- Attachment #1.1: Type: text/plain, Size: 2646 bytes --]


On Sep 28, 2015, at 1:30 AM, Kalle Rosenbaum via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> Suppose that you've solved a block Z (weak or not) and you want to propagate it using a previous weak block Y. With "efficient differential transmission", I assume that you refer to the transmission of the differences between Y and Z to a peer? What encodings are discussed? I guess IBLTs are a hot candidate, but are there other schemes in the making? I suppose that sending something like "weak block Y plus transactions A, B, C minus transaction ids h(D), h(E)" is not considered an efficient differential transmission. Then that's part of the answer to my question.
> 

IBLTs are effective for synchronizing mempools, to ensure that all nodes in a network can successfully map a transaction hash to a full transaction. However, IBLTs do not help with the ordering of the transactions.

Encoding the new blocks as a diff (delete bytes x through y, insert string s after byte z) based on a weak block would probably be pretty effective, but it would probably require a lot of memory for keeping a weak block (or chain of diffs) for each miner that publishes weak blocks. It might be a little complicated to manage and remove duplicate information between weak blocks published by different sources. You'd probably have to build a weak block tree or DAG with diffs as edges, and walk the tree each time you wanted to fetch a (weak) block.

Another strategy is to use the Merkle tree nodes. Each node is a hash of its concatenated child nodes, Each node thus specifies the order of 2^n transaction hashes. Changing one transaction hash requires modifying log_2(n) Merkle node hashes, which is okay but maybe not as good as the diff approach. However, the main benefit comes from compressing and storing data from many different weak blocks generated by different miners. You can build a cache of Merkle nodes, and each time you get a new weak block, you can add any new Merkle nodes to that cache. There's some more info on this here: http://bitcoin-development.narkive.com/dGIxjVI5/torrent-style-new-block-propagation-on-merkle-trees

Merkle tree encodings handle replacements of transactions well, but they have trouble with insertions or deletions near the beginning of a block. Efforts could be made to avoid insertions and deletions in the actual transaction ordering to improve transmissibility, or a hybrid system could be implemented in which byte-level diffs or transaction-level diffs are used for transmitting the weak blocks as a diff against previously cached Merkle nodes.

Or maybe there's a better way.

[-- Attachment #1.2: Type: text/html, Size: 3590 bytes --]

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 496 bytes --]