📅 Original date posted:2016-05-10
📝 Original message:Replies inline.
On May 10, 2016 5:23:55 PM EDT, Rusty Russell via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>Gregory Maxwell <greg at xiph.org> writes:
>> On Tue, May 10, 2016 at 5:28 AM, Rusty Russell via bitcoin-dev
>> <bitcoin-dev at lists.linuxfoundation.org> wrote:
>>> I used variable-length bit encodings, and used the shortest encoding
>>> which is unique to you (including mempool). It's a little more
>work,
>>> but for an average node transmitting a block with 1300 txs and
>another
>>> ~3000 in the mempool, you expect about 12 bits per transaction.
>IOW,
>>> about 1/5 of your current size. Critically, we might be able to fit
>in
>>> two or three TCP packets.
>>
>> Hm. 12 bits sounds very small even giving those figures. Why failure
>> rate were you targeting?
>
>That's a good question; I was assuming a best-case in which we have
>mempool set reconciliation (handwave) thus know they are close. But
>there's also an alterior motive: any later more sophisticated approach
>will want variable-length IDs, and I'd like Matt to do the work :)
Yea, there's already an ongoing discussion of that, and the UDP stuff will definitely want something different than the current proposals.
>In particular, you can significantly narrow the possibilities for a
>block by sending the min-fee-per-kb and a list of "txs in my mempool
>which didn't get in" and "txs which did despite not making the
>fee-per-kb". Those turn out to be tiny, and often make set
>reconciliation trivial. That's best done with variable-length IDs.
>
>> (*Not interesting because it mostly reduces exposure to loss and the
>> gods of TCP, but since those are the long poles in the latency tent,
>> it's best to escape them entirely, see Matt's udp_wip branch.)
>
>I'm not convinced on UDP; it always looks impressive, but then ends up
>reimplementing TCP in practice. We should be well within a TCP window
>for these, so it's hard to see where we'd win.
Not at all. The goal with the UDP stuff I've been working on is not to provide reliable transport. Like the relay network, it is assumed some percent of blocks will fail to transit properly, and you will use some other transport to figure out how to get the block. Indeed, a big part of my desire for diversity in network protocols is to enable them to make tradeoffs in reliability/privacy/etc.
>>> I would also avoid the nonce to save recalculating for each node,
>and
>>> instead define an id as:
>>
>> Doing this would greatly increase the cost of a collision though, as
>> it would happen in many places in the network at once over the on the
>> network at once, rather than just happening on a single link, thus
>> hardly impacting overall propagation.
>
>"Greatly increase"? I don't see that.
>
>Let's assume an attacker grinds out 10,000 txs with 128 bits of the
>same
>TXID, and gets them all in a block. They then win the lottery and get
>a
>collision. Now we have to transmit ~48 bytes more than expected.
I assume what Greg was referring to the idea that if there is a conflict, a given block will require an extra round trip when being broadcast between roughly each peer, compounding the effect across each hop.
>> Using the same nonce means you also would not get a recovery gain
>from
>> jointly decoding using compact blocks sent from multiple peers (which
>> you'll have anyways in high bandwidth mode).
>
>Not quite true, since if their mempools differ they'll use different
>encoding lengths, but yes, you'll get less of this.
... Assuming different encoding lengths aren't just truncated, but ok :).
>> With a nonce a sender does have the option of reusing what they got--
>> but the actual encoding cost is negligible, for a 2500 transaction
>> block its 27 microseconds (once per block, shared across all peers)
>> using Pieter's suggestion of siphash 1-3 instead of the cheaper
>> construct in the current draft.
>>
>> Of course, if you're going to check your whole mempool to reroll the
>> nonce, thats another matter-- but that seems wasteful compared to
>just
>> using a table driven size with a known negligible failure rate.
>
>I'm not worried about the sender: The recipient needs to encode all the
>mempool.
>
>>> As Peter R points out, we could later enhance receiver to brute
>force
>>> collisions (you could speed that by sending a XOR of all the txids,
>but
>>> really if there are more than a few collisions, give up).
>>
>> The band between "no collisions" and "infeasible many" is fairly
>> narrow. You can add a small amount more space to the ids and
>> immediately be in the no collision zone.
>
>Indeed, I would be adding extra bits in the sender and not implementing
>brute force in the receiver. But I welcome someone else to do so.
>
>Cheers,
>Rusty.
>_______________________________________________
>bitcoin-dev mailing list
>bitcoin-dev at lists.linuxfoundation.org
>https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Matt Corallo [ARCHIVE] /
npub1e4…jxmcu
2023-06-07 17:50:22
in reply to nevent1q…ldxk
Author Public Key
npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcuPublished at
2023-06-07 17:50:22Event JSON
{
"id": "a1a0f1d9196010b5bdc2fa8d535f5643002169442d98756da1321b18e63beacd",
"pubkey": "cd753aa8fbc112e14ffe9fe09d3630f0eff76ca68e376e004b8e77b687adddba",
"created_at": 1686160222,
"kind": 1,
"tags": [
[
"e",
"37fe3d2b857e9599a14c87e34f77dee62e90bb6721200fbd7752c60823834c1e",
"",
"root"
],
[
"e",
"4dd68f863cb752aac20ce024d7a703eead5ddb9a52ed7b0c3c202b127d6b8135",
"",
"reply"
],
[
"p",
"13bd8c1c5e3b3508a07c92598647160b11ab0deef4c452098e223e443c1ca425"
]
],
"content": "📅 Original date posted:2016-05-10\n📝 Original message:Replies inline.\n\nOn May 10, 2016 5:23:55 PM EDT, Rusty Russell via bitcoin-dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003eGregory Maxwell \u003cgreg at xiph.org\u003e writes:\n\u003e\u003e On Tue, May 10, 2016 at 5:28 AM, Rusty Russell via bitcoin-dev\n\u003e\u003e \u003cbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\u003e\u003e I used variable-length bit encodings, and used the shortest encoding\n\u003e\u003e\u003e which is unique to you (including mempool). It's a little more\n\u003ework,\n\u003e\u003e\u003e but for an average node transmitting a block with 1300 txs and\n\u003eanother\n\u003e\u003e\u003e ~3000 in the mempool, you expect about 12 bits per transaction. \n\u003eIOW,\n\u003e\u003e\u003e about 1/5 of your current size. Critically, we might be able to fit\n\u003ein\n\u003e\u003e\u003e two or three TCP packets.\n\u003e\u003e\n\u003e\u003e Hm. 12 bits sounds very small even giving those figures. Why failure\n\u003e\u003e rate were you targeting?\n\u003e\n\u003eThat's a good question; I was assuming a best-case in which we have\n\u003emempool set reconciliation (handwave) thus know they are close. But\n\u003ethere's also an alterior motive: any later more sophisticated approach\n\u003ewill want variable-length IDs, and I'd like Matt to do the work :)\n\nYea, there's already an ongoing discussion of that, and the UDP stuff will definitely want something different than the current proposals.\n\n\u003eIn particular, you can significantly narrow the possibilities for a\n\u003eblock by sending the min-fee-per-kb and a list of \"txs in my mempool\n\u003ewhich didn't get in\" and \"txs which did despite not making the\n\u003efee-per-kb\". Those turn out to be tiny, and often make set\n\u003ereconciliation trivial. That's best done with variable-length IDs.\n\u003e\n\u003e\u003e (*Not interesting because it mostly reduces exposure to loss and the\n\u003e\u003e gods of TCP, but since those are the long poles in the latency tent,\n\u003e\u003e it's best to escape them entirely, see Matt's udp_wip branch.)\n\u003e\n\u003eI'm not convinced on UDP; it always looks impressive, but then ends up\n\u003ereimplementing TCP in practice. We should be well within a TCP window\n\u003efor these, so it's hard to see where we'd win.\n\nNot at all. The goal with the UDP stuff I've been working on is not to provide reliable transport. Like the relay network, it is assumed some percent of blocks will fail to transit properly, and you will use some other transport to figure out how to get the block. Indeed, a big part of my desire for diversity in network protocols is to enable them to make tradeoffs in reliability/privacy/etc.\n\n\u003e\u003e\u003e I would also avoid the nonce to save recalculating for each node,\n\u003eand\n\u003e\u003e\u003e instead define an id as:\n\u003e\u003e\n\u003e\u003e Doing this would greatly increase the cost of a collision though, as\n\u003e\u003e it would happen in many places in the network at once over the on the\n\u003e\u003e network at once, rather than just happening on a single link, thus\n\u003e\u003e hardly impacting overall propagation.\n\u003e\n\u003e\"Greatly increase\"? I don't see that.\n\u003e\n\u003eLet's assume an attacker grinds out 10,000 txs with 128 bits of the\n\u003esame\n\u003eTXID, and gets them all in a block. They then win the lottery and get\n\u003ea\n\u003ecollision. Now we have to transmit ~48 bytes more than expected.\n\nI assume what Greg was referring to the idea that if there is a conflict, a given block will require an extra round trip when being broadcast between roughly each peer, compounding the effect across each hop.\n\n\u003e\u003e Using the same nonce means you also would not get a recovery gain\n\u003efrom\n\u003e\u003e jointly decoding using compact blocks sent from multiple peers (which\n\u003e\u003e you'll have anyways in high bandwidth mode).\n\u003e\n\u003eNot quite true, since if their mempools differ they'll use different\n\u003eencoding lengths, but yes, you'll get less of this.\n\n... Assuming different encoding lengths aren't just truncated, but ok :).\n\n\u003e\u003e With a nonce a sender does have the option of reusing what they got--\n\u003e\u003e but the actual encoding cost is negligible, for a 2500 transaction\n\u003e\u003e block its 27 microseconds (once per block, shared across all peers)\n\u003e\u003e using Pieter's suggestion of siphash 1-3 instead of the cheaper\n\u003e\u003e construct in the current draft.\n\u003e\u003e\n\u003e\u003e Of course, if you're going to check your whole mempool to reroll the\n\u003e\u003e nonce, thats another matter-- but that seems wasteful compared to\n\u003ejust\n\u003e\u003e using a table driven size with a known negligible failure rate.\n\u003e\n\u003eI'm not worried about the sender: The recipient needs to encode all the\n\u003emempool.\n\u003e\n\u003e\u003e\u003e As Peter R points out, we could later enhance receiver to brute\n\u003eforce\n\u003e\u003e\u003e collisions (you could speed that by sending a XOR of all the txids,\n\u003ebut\n\u003e\u003e\u003e really if there are more than a few collisions, give up).\n\u003e\u003e\n\u003e\u003e The band between \"no collisions\" and \"infeasible many\" is fairly\n\u003e\u003e narrow. You can add a small amount more space to the ids and\n\u003e\u003e immediately be in the no collision zone.\n\u003e\n\u003eIndeed, I would be adding extra bits in the sender and not implementing\n\u003ebrute force in the receiver. But I welcome someone else to do so.\n\u003e\n\u003eCheers,\n\u003eRusty.\n\u003e_______________________________________________\n\u003ebitcoin-dev mailing list\n\u003ebitcoin-dev at lists.linuxfoundation.org\n\u003ehttps://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev",
"sig": "e3a0f9c83a8c8a4596274c87956d814d0b51ef77fab5bb83e8899a3f8b4d9f171dfaed2ed08e0c4aa989f3d7bd7636c4b6c5a11ff0ca4b93a7d2fd0f950a0dd1"
}