Jonathan Toomim (Toomim Bros) [ARCHIVE] / is on Nostr

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2015-09-23 to 2015-10-14
💬 Posted a total of 11 messages
📚 Participated in the following categories: bitcoin-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Last Notes

2023-06-07 17:43:16

- reply

📅 Original date posted:2015-10-13
📝 Original message:On Oct 13, 2015, at 3:49 PM, odinn <odinn.cyberguerrilla at riseup.net> wrote:
> Signed PGP part
> It would also help to know what operating system(s) you are
> using for both the oldie and the freshie.
Linux feather 3.16.0-4-amd64 #1 SMP Debian 3.16.7-ckt11-1+deb8u3 (2015-08-04) x86_64 GNU/Linux
Linux server 3.2.0-4-amd64 #1 SMP Debian 3.2.60-1+deb7u3 x86_64 GNU/Linux
Linux prime 3.2.0-4-amd64 #1 SMP Debian 3.2.63-2+deb7u2 x86_64 GNU/Linux
This excessive memory consumption was seen on 3 machines, all of which run Debian. All three machines run p2pool as well as bitcoind. Two run XT, one runs Core.
>
> You should compare this to having set up a node on a completely clean
> computer.
I can't afford to do that. All of the servers I have are being used for something. Also, I'm not sure what it is you're trying to test for with that suggestion. The numbers I'm reporting are for bitcoind's resident set, not for the whole server's memory usage. I don't see how other processes running on the same machine are relevant unless you are suggesting that RPC calls (e.g. getblocktemplate) might be somehow responsible.
>
> Also, dump your XT, is poo.
Not relevant. I addressed this message to both the Core and XT lists because the issue appears to affect both forks. Let's keep blocksize and governance debates to their own threads, please.
Repeating request: Has anyone else seen something similar? Can you report your mempool size and total bitcoind resident set size for your running full nodes?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151013/f11fac76/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151013/f11fac76/attachment-0001.sig>

2023-06-07 17:43:16

- reply

📅 Original date posted:2015-10-13
📝 Original message:> 16 million divided by 1085 transactions is almost 15Kb per transaction = unlikely, right?
The recent spam was about 15 kB per transaction, so that part sounds right.
The anomalous thing that I saw was that the total bitcoind process usage was about 50-100x higher than I would have expected if the mempool was the main determinant of memory usage scaling. Can you tell me how much memory Task Manager is reporting your bitcoin process as using both today and tomorrow?
On Oct 13, 2015, at 4:52 PM, Dave Scotese via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>
> {
> "size" : 1085,
> "bytes" : 16151768
> }
> It has been running about a day. I'll report tomorrow too. This is a Windows 8.1 box.
> 16 million divided by 1085 transactions is almost 15Kb per transaction = unlikely, right?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151013/b314b4b7/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151013/b314b4b7/attachment.sig>

2023-06-07 17:43:15

- reply

📅 Original date posted:2015-10-13
📝 Original message:I just noticed that several of my running bitcoind processes were using around 3+ GB of RAM, even though the mempool itself seemed to be under control.
XXXX at prime:~/bin$ ./bitcoin-cli getmempoolinfo
{
"size" : 1896,
"bytes" : 37341328
}
[total memory usage not shown -- I restarted bitcoind as soon as I noticed, and didn't copy it down from top]
37 MB mempool, >3 GB RAM usage. Normally, when there aren't a lot of unconfirmed txns floating around the network, memory usage is around 600 MB, so this is quite unusual.
After restarting the process and letting it run for a few minutes, I get:
PID USER PRI NI VIRT RES SHR S CPU% MEM% TIME+ Command
[###] [XXXX] 20 0 1402M 317M 49836 S 1.0 8.2 0:41.71 ./bitcoind -daemon
XXXX at prime:~/bin$ ./bitcoin-cli getmempoolinfo
{
"size" : 1072,
"bytes" : 670000
}
0.67 MB mempool, 317 MB RAM usage. Much more reasonable.
Here's another node I'm running that has been online longer, before restarting:
PID USER PRI NI VIRT RES SHR S CPU% MEM% TIME+ Command
[###] [XXXX] 20 0 4961M 3540M 11080 S 2.8 45.3 8h20:11 bin/bitcoind -daemon
XXXX at feather:~$ bin/bitcoin-cli getmempoolinfo
{
"size" : 3045,
"bytes" : 39656126
}
39 MB mempool, 3540 MB total memory usage. After restarting bitcoind, I see:
[XXXX]@feather:~$ bin/bitcoin-cli stop
Bitcoin server stopping
[XXXX]@feather:~$ bin/bitcoind -daemon
Bitcoin server starting
[XXXX]@feather:~$ sleep 10; bin/bitcoin-cli getmempoolinfo
{
"size" : 39,
"bytes" : 47037
}
PID USER PRI NI VIRT RES SHR S CPU% MEM% TIME+ Command
[###] [XXXX] 20 0 1640M 247M 67960 S 0.0 3.2 0:05.17 bin/bitcoind -daemon
Does anybody have any guesses where we might be leaking memory, or what is using the additional 2.4 GB? I've been using minrelaytxfee=0.00003 or similar on my nodes. Maybe there's a leak in the minrelaytxfee code path? Has anyone else seen something similar?
This issue appears to happen both with Bitcoin Core 0.10.1 and with Bitcoin XT 0.11B.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151013/dc82ee16/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151013/dc82ee16/attachment.sig>

2023-06-07 17:42:05

- reply

📅 Original date posted:2015-10-07
📝 Original message:On Oct 7, 2015, at 9:02 AM, Eric Lombrozo <elombrozo at gmail.com> wrote:
> But a real hashpower supermajority would make such attacks hard to pull off in practice.
If you had a 99% hashpower supermajority on the new version, an attacker would still be able to perform this attack once per day. Since the attacker is creating a transaction which is invalid according to new clients, it will just sit around in old clients' mempool until one of them mines a block.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151007/114cbf39/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151007/114cbf39/attachment-0001.sig>

2023-06-07 17:42:03

- reply

📅 Original date posted:2015-10-07
📝 Original message:On Oct 7, 2015, at 8:00 AM, Anthony Towns via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> *But* a soft fork that only forbids transactions that would previously
> not have been mined anyway should be the best of both worlds, as it
> automatically reduces the liklihood of old miners building newly invalid
> blocks to a vanishingly small probability; which means that upgraded
> bitcoin nodes, non-upgraded bitcoin nodes, /and/ SPV clients *all*
> continuing to work fine during the upgrade.
I agree with pretty much everything you wrote except the above paragraph.
An attacker can create a transaction that would be valid if it were an OP_NOP, but not valid if it were any more restrictive transaction. For example, an attacker might send 1 BTC to an address with . An old node would consider that OP_CLTV to be OP_NOP, so no signature is necessary for old nodes. Then the attacker buys something from a merchant running old node code or an SPV client, and spends the 1 BTC in that address in a way that is invalid according to OP_CLTV but valid according to OP_NOP, and includes a hefty fee. A miner on the old version includes this transaction into a block, thereby making the block invalid according to the new rules, and rejected by new-client miners. The merchant sees the 1-conf, and maybe even 2-conf, rejoices, and ships. The attacker then has until the OP_CLTV matures to double-spend the coin with new nodes using a valid signature.
Basically, it's trivial to create transactions that exploit the difference in validation rules as long as miners are still on the old version to mine them. Transactions can be created that are guaranteed to be orphaned and trivially double-spendable. Attackers never have to risk actual losses. This can be done as long as miners continue to mine old-version blocks, regardless of their frequency.
Those of you who know Script better than me: would this be an example of a transaction that would be spendable with a valid sig XOR with (far future date OR old code)?
OP_DUP OP_HASH160 <pubkeyhash> OP_EQUALVERIFY OP_CHECKSIGVERIFY OP_PUSHDATA <locktime far in the future> OP_CLTV
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151007/c701783e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151007/c701783e/attachment.sig>

2023-06-07 17:41:46

- reply

📅 Original date posted:2015-09-29
📝 Original message:At the 95% threshold, I don't think it would happen unless there was a very strong motivating factor, like a small group believing that CLTV was a conspiracy run by the NSA agent John Titor to contaminate our precious bodily fluids with time-traveling traveler's cheques.
At the 75% threshold, I think it could happen with mostly rational users, but even then it's not very likely with most forks. With the blocksize issue, there are some people who get very religious about things like decentralization or fee markets and think that even 1 MB is too large; I could see them making financial sacrifices in order to try to make a small-block parallel fork a reality, one that is true to their vision of what's needed to make Bitcoin true and pure, or whatever.
On Sep 29, 2015, at 7:04 AM, Gavin Andresen <gavinandresen at gmail.com> wrote:
> I keep seeing statements like this:
>
> On Tue, Sep 29, 2015 at 9:30 AM, Jonathan Toomim (Toomim Bros) via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> As a further benefit to hard forks, anybody who is ideologically opposed to the change can continue to use the old version successfully, as long as there are enough miners to keep the fork alive.
>
> ... but I can't see how that would work.
>
> Lets say there is a hard fork, and 5% of miners stubbornly refuse to go along with the 95% majority (for this thought experiment, it doesn't matter if the old rules or new rules 'win').
>
> Lets further imagine that some exchange decides to support that 5% and lets people trade coins from that fork (one of the small altcoin exchanges would definitely do this if they think they can make a profit).
>
> Now, lets say I've got a lot of pre-fork bitcoin; they're valid on both sides of the fork. I support the 95% chain (because I'm not insane), but I'm happy to take people's money if they're stupid enough to give it to me.
>
> So, I do the following:
>
> 1) Create a send-to-self transaction on the 95% fork that is ONLY valid on the 95% fork (maybe I CoinJoin with a post-fork coinbase transaction, or just move my coins into then out of an exchange's very active hot wallet so I get coins with a long transaction history on the 95% side of the fork).
>
> 2) Transfer those same coins to the 5% exchange and sell them for whatever price I can get (I don't care how low, it is free money to me-- I will still own the coins on the 95% fork).
>
> I have to do step (1) to prevent the exchange from taking the transfer-to-exchange transaction and replaying it on the 95% chain.
>
> I don't see any way of preventing EVERYBODY who has coins on the 95% side of the fork from doing that. The result would be a huge free-fall in price as I, and everybody else, rushes to get some free money from anybody willing to pay us to remain idealogically pure.
>
> Does anybody think something else would happen, and do you think that ANYBODY would stick to the 5% fork in the face of enormously long transaction confirmation times (~3 hours), a huge transaction backlog as lots of the 95%'ers try to sell their coins before the price drops, and a massive price drop for coins on the 5% fork.
>
> --
> --
> Gavin Andresen
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150929/4dde6117/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150929/4dde6117/attachment.sig>

2023-06-07 17:41:36

- reply

📅 Original date posted:2015-09-29
📝 Original message:On Sep 28, 2015, at 7:43 AM, Peter Todd via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Ok, so again, if that's your security criteria, what's the issue with
> soft-forks? With soft-forks, the result of a SPV wallet following the
> highest work chain is the same: eventually invalid blocks are reorged
> out.
>
> However, because soft-forks make it less likely that a long invalid
> chain will be generated, an attacker sybil attacking your SPV wallet has
> a much harder time tricking it into accepting a transaction. (they might
> get one or two confirmations, rather than dozens)
>
> What's the scenario where soft-forks are worse than hard-forks from a
> SPV wallet's perspective?
I don't think this was addressed clearly, so here's my attempt.
With a soft fork, miners who have not upgraded append their blocks to the longest block chain. To SPV clients and to old fully-validating clients, it appears to be a valid block that inevitably gets orphaned. SPV clients will be tricked to follow these blocks every time they appear, since every time they appear they will have a PoW advantage for a few minutes. SPV clients will appear to behave normally, and will continue to show new transactions and get confirmations in a timely fashion. However, they will be systematically susceptible to attack from double-spends that attempt to spend funds in a way that the upgraded nodes will reject. These transactions will appear to get 1 confirmation, then regress to zero conf, every single time. These attacks can be performed for as long as someone mines with the old version. If an attacker thinks he could get more than 25 BTC of double-spends per block, he might even choose to mine with the obsolete version in order to get predictable orphans and to trick SPV clients and fully verifying wallets on the old version.
With a hard fork, miners who have not upgraded will append their blocks on the shorter fork. SPV clients will ignore this fork unless Sybil attacked. If an SPV node only connects to one full node server, that's equivalent to a Sybil attack. In that case, transactions on the long chain will often not be present on the short chain due to its shortness. Confirmations will be slow, and will be shown to be very different from what's shown on block explorers. Displayed transaction dates and times will be off, when they show up at all. Any transactions that have been contaminated by recent mining revenue will not show up at all. SPV client users will probably notice something is wrong. If the SPV client connects to several full nodes, then this should rarely happen. For example, if 5% of full nodes are still on the old version, and an SPV wallet connects to 2 nodes at a time, there is a 0.05**2 = 0.25% chance. If the SPV client has headers cached on disk from a previous connection to the longer chain, then that chance effectively drops to zero. As a further benefit to hard forks, anybody who is ideologically opposed to the change can continue to use the old version successfully, as long as there are enough miners to keep the fork alive.
In short: soft forks mean frequent predictable and manipulable orphan blocks that SPV clients will always follow, with transactions that get confirmed once and then perma-orphaned. Hard forks mean that SPV clients will almost always work flawlessly, and will occasionally give very strange and noticeably wrong results. For fully-verifying nodes, soft forks make old versions insecure, but hard forks allow new and old versions to operate in parallel.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150929/22615768/attachment.sig>

2023-06-07 17:41:23

- reply

📅 Original date posted:2015-09-29
📝 Original message:Making statements about a developer's personal character is also off-topic for this list.
On Sep 29, 2015, at 3:58 PM, Milly Bitcoin via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> On 9/29/2015 5:07 PM, Jeff Garzik via bitcoin-dev wrote:
>> This is off-topic for this list.
>
> You like to go around pretending you are in charge and telling people what to do. You have no such authority and your time is probably better spent reviewing your company's Bitcoin handling and security procedures instead of trying to bully people all the time.
>
> Russ
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150929/48b57d13/attachment.sig>

2023-06-07 17:41:13

- reply

📅 Original date posted:2015-09-23
📝 Original message:As I understand it, the current block propagation algorithm is this:
1. A node mines a block.
2. It notifies its peers that it has a new block with an inv. Typical nodes have 8 peers.
3. The peers respond that they have not seen it, and request the block with getdata [hash].
4. The node sends out the block in parallel to all 8 peers simultaneously. If the node's upstream bandwidth is limiting, then all peers will receive most of the block before any peer receives all of the block. The block is sent out as the small header followed by a list of transactions.
5. Once a peer completes the download, it verifies the block, then enters step 2.
(If I'm missing anything, please let me know.)
The main problem with this algorithm is that it requires a peer to have the full block before it does any uploading to other peers in the p2p mesh. This slows down block propagation to O( p • log_p(n) ), where n is the number of peers in the mesh, and p is the number of peers transmitted to simultaneously.
It's like the Napster era of file-sharing. We can do much better than this. Bittorrent can be an example for us. Bittorrent splits the file to be shared into a bunch of chunks, and hashes each chunk. Downloaders (leeches) grab the list of hashes, then start requesting their peers for the chunks out-of-order. As each leech completes a chunk and verifies it against the hash, it begins to share those chunks with other leeches. Total propagation time for large files can be approximately equal to the transmission time for an FTP upload. Sometimes it's significantly slower, but often it's actually faster due to less bottlenecking on a single connection and better resistance to packet/connection loss. (This could be relevant for crossing the Chinese border, since the Great Firewall tends to produce random packet loss, especially on encrypted connections.)
Bitcoin uses a data structure for transactions with hashes built-in. We can use that in lieu of Bittorrent's file chunks.
A Bittorrent-inspired algorithm might be something like this:
0. (Optional steps to build a Merkle cache; described later)
1. A seed node mines a block.
2. It notifies its peers that it has a new block with an extended version of inv.
3. The leech peers request the block header.
4. The seed sends the block header. The leech code path splits into two.
5(a). The leeches verify the block header, including the PoW. If the header is valid,
6(a). They notify their peers that they have a header for an unverified new block with an extended version of inv, looping back to 2. above. If it is invalid, they abort thread (b).
5(b). The leeches request the Nth row (from the root) of the transaction Merkle tree, where N might typically be between 2 and 10. That corresponds to about 1/4th to 1/1024th of the transactions. The leeches also request a bitfield indicating which of the Merkle nodes the seed has leaves for. The seed supplies this (0xFFFF...).
6(b). The leeches calculate all parent node hashes in the Merkle tree, and verify that the root hash is as described in the header.
7. The leeches search their Merkle hash cache to see if they have the leaves (transaction hashes and/or transactions) for that node already.
8. The leeches send a bitfield request to the node indicating which Merkle nodes they want the leaves for.
9. The seed responds by sending leaves (either txn hashes or full transactions, depending on benchmark results) to the leeches in whatever order it decides is optimal for the network.
10. The leeches verify that the leaves hash into the ancestor node hashes that they already have.
11. The leeches begin sharing leaves with each other.
12. If the leaves are txn hashes, they check their cache for the actual transactions. If they are missing it, they request the txns with a getdata, or all of the txns they're missing (as a list) with a few batch getdatas.
The main feature of this algorithm is that a leech will begin to upload chunks of data as soon as it gets them and confirms both PoW and hash/data integrity instead of waiting for a fully copy with full verification.
This algorithm is more complicated than the existing algorithm, and won't always be better in performance. Because more round trip messages are required for negotiating the Merkle tree transfers, it will perform worse in situations where the bandwidth to ping latency ratio is high relative to the blocksize. Specifically, the minimum per-hop latency will likely be higher. This might be mitigated by reducing the number of round-trip messages needed to set up the blocktorrent by using larger and more complex inv-like and getdata-like messages that preemptively send some data (e.g. block headers). This would trade off latency for bandwidth overhead from larger duplicated inv messages. Depending on implementation quality, the latency for the smallest block size might be the same between algorithms, or it might be 300% higher for the torrent algorithm. For small blocks (perhaps < 100 kB), the blocktorrent algorithm will likely be slightly slower. For large blocks (e.g. 8 MB over 20 Mbps), I expect the blocktorrent algo will likely be around an order of magnitude faster in the worst case (adversarial) scenarios, in which none of the block's transactions are in the caches.
One of the big benefits of the blocktorrent algorithm is that it provides several obvious and straightforward points for bandwidth saving and optimization by caching transactions and reconstructing the transaction order. A cooperating miner can pre-announce Merkle subtrees with some of the transactions they are planning on including in the final block. Other miners who see those subtrees can compare the transactions in those subtrees to the transaction sets they are mining with, and can rearrange their block prototypes to use the same subtrees as much as possible. In the case of public pools supporting the getblocktemplate protocol, it might be possible to build Merkle subtree caches without the pool's help by having one or more nodes just scraping their getblocktemplate results. Even if some transactions are inserted or deleted, it may be possible to guess a lot of the tree based on the previous ordering.
Once a block header and the first few rows of the Merkle tree have been published, they will propagate through the whole network, at which time full nodes might even be able to guess parts of the tree by searching through their txn and Merkle node/subtree caches. That might be fun to think about, but probably not effective due to O(n^2) or worse scaling with transaction count. Might be able to make it work if the whole network cooperates on it, but there are probably more important things to do.
There are also a few other features of Bittorrent that would be useful here, like prioritizing uploads to different peers based on their upload capacity, and banning peers that submit data that doesn't hash to the right value. (It might be good if we could get Bram Cohen to help with the implementation.)
Another option is just to treat the block as a file and literally Bittorrent it, but I think that there should be enough benefits to integrating it with the existing bitcoin p2p connections and also with using bitcoind's transaction caches and Merkle tree caches to make a native implementation worthwhile. Also, Bittorrent itself was designed to optimize more for bandwidth than for latency, so we will have slightly different goals and tradeoffs during implementation.
One of the concerns that I initially had about this idea was that it would involve nodes forwarding unverified block data to other nodes. At first, I thought this might be useful for a rogue miner or node who wanted to quickly waste the whole network's bandwidth. However, in order to perform this attack, the rogue needs to construct a valid header with a valid PoW, but use a set of transactions that renders the block as a whole invalid in a manner that is difficult to detect without full verification. However, it will be difficult to design such an attack so that the damage in bandwidth used has a greater value than the 240 exahashes (and 25.1 BTC opportunity cost) associated with creating a valid header.
As I understand it, the O(1) IBLT approach requires that blocks follow strict rules (yet to be fully defined) about the transaction ordering. If these are not followed, then it turns into sending a list of txn hashes, and separately ensuring that all of the txns in the new block are already in the recipient's mempool. When mempools are very dissimilar, the IBLT approach performance degrades heavily and performance becomes worse than simply sending the raw block. This could occur if a node just joined the network, during chain reorgs, or due to malicious selfish miners. Also, if the mempool has a lot more transactions than are included in the block, the false positive rate for detecting whether a transaction already exists in another node's mempool might get high for otherwise reasonable bucket counts/sizes.
With the blocktorrent approach, the focus is on transmitting the list of hashes in a manner that propagates as quickly as possible while still allowing methods for reducing the total bandwidth needed. The blocktorrent algorithm does not really address how the actual transaction data will be obtained because, once the leech has the list of txn hashes, the standard Bitcoin p2p protocol can supply them in a parallelized and decentralized manner.
Thoughts?
-jtoomim
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150923/8e6e7243/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150923/8e6e7243/attachment-0001.sig>

2023-06-07 17:41:08

- reply

📅 Original date posted:2015-09-28
📝 Original message:On Sep 28, 2015, at 1:30 AM, Kalle Rosenbaum via bitcoin-dev <bitcoin-dev at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150928/4decf9a0/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150928/4decf9a0/attachment.sig>

2023-06-07 17:41:06

- reply

📅 Original date posted:2015-09-23
📝 Original message:On Sep 23, 2015, at 2:37 PM, Gavin Andresen via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> Take care, here-- if a scheme is used where e.g. the full solution had
> to be exactly identical to a prior weak block then the result would be
> making mining not progress free because bigger miners would have
> disproportionately more access to the weak/strong one/two punch. I
> think what you're thinking here is okay, but it wasn't clear to me if
> you'd caught that particular potential issue.
>
> I'm assuming the optimized protocol would be forward-error-coded (e.g. using IBLTs) and NOT require the full solution (or follow-on weak blocks) to be exactly the same.
>
One possible improvement on this is to cache Merkle nodes/subtrees. When a weak block is created, nodes could cache the hashes for the Merkle nodes along with each node's children. A miner could then describe their block in terms of Merkle nodes (describing groups of 2^n transactions), which would give them the ability to copy e.g. 87.5% or 96.875% or whatever of their new block from someone else's weak block but with a few modifications (e.g. new transactions) in the remaining non-prespecified portion. This gives small miners the ability to trade off versatility (do I specify all of the transactions with my own Merkle structure?) versus propagation speed (do I copy all of my Merkle tree from another miner's weak block?) with all steps in between.
I've got a proposal for a block propagation protocol inspired by bittorrent applied to the Merkle tree instead of chunks of a file. Weak blocks would fit in with this blocktorrent protocol quite nicely by caching and pre-transmitting Merkle nodes. I don't want to hijack this thread, so I'll post it under a separate subject in an hour or so.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150923/3edaab92/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20150923/3edaab92/attachment.sig>