From: "Jonathan Toomim (Toomim Bros)" <j@toom•im>
To: Kalle Rosenbaum <kalle@rosenbaum•se>
Cc: Bitcoin Dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Weak block thoughts...
Date: Mon, 28 Sep 2015 06:30:22 -0700 [thread overview]
Message-ID: <8166B5CA-BE2A-444E-B826-BFA18F4C4757@toom.im> (raw)
In-Reply-To: <CAPswA9xei1UNMeNqi=XzSnZU=SeroaeKN_6xHJ0HfhgXBzY_mw@mail.gmail.com>
[-- 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 --]
next prev parent reply other threads:[~2015-09-28 13:30 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-09-23 15:43 Gavin Andresen
2015-09-23 16:07 ` Bryan Bishop
2015-09-23 19:24 ` Gregory Maxwell
2015-09-23 21:37 ` Gavin Andresen
2015-09-23 22:16 ` Jonathan Toomim (Toomim Bros)
2015-09-24 1:11 ` Rusty Russell
2015-09-27 1:39 ` Gregory Maxwell
2015-09-27 9:42 ` Tier Nolan
2015-09-27 15:10 ` Kalle Rosenbaum
2015-09-27 19:50 ` Gregory Maxwell
2015-09-28 8:30 ` Kalle Rosenbaum
2015-09-28 13:30 ` Jonathan Toomim (Toomim Bros) [this message]
2015-09-23 16:07 ` Btc Drak
2015-09-23 16:28 ` Peter R
2015-09-23 17:40 ` Gavin
2015-09-23 17:49 ` Peter R
2015-09-23 18:48 ` Tier Nolan
2015-09-24 1:32 ` Rusty Russell
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=8166B5CA-BE2A-444E-B826-BFA18F4C4757@toom.im \
--to=j@toom$(echo .)im \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=kalle@rosenbaum$(echo .)se \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox