Gold collapsing. Bitcoin UP.

[sickpig]

> (If we were using UDP with FEC instead of TCP, these awful network throughput issues would largely go away. Do you know if anyone is working on that?)

Doesn't Corallo's FIBRE use UDP and FEC? Not knowing of anyone developing this for BCH thou.

Maybe @shadders could explain further the fast link idea he was referring to on reddit. Wonder if they are using udp/fec?

 

[jtoomim]

Yes, FIBRE uses UDP and FEC. That's one of the biggest reasons why it's so good. I've also seen a private UDP implementation of raw block transmission at Bitmain a few years back which allowed them to get around 90 Mbps on a 100 Mbps link across the border. UDP FEC FTW.

Given that shadders mentioned the November timeline for the "fast link idea," I think it's quite likely he's talking about Graphene. So we should ask the people who are implementing that into Bitcoin Cash daemons if they're using UDP.

Hey, are we using UDP for Graphene?

@Peter R

Thanks for doing that math. Plugging some numbers into your equations and running with it:

Assume attacker (A)=20% defender (B)=10%

rb / ra = (1 - B) / B = 0.9 / 0.1 = 9

Orphan rate ratio is 9. This means that 9 out of 10 blocks orphaned will be the defender's.

For each orphaned block, the attacker gains 0.2 of a block reward due to later difficulty decreases, the defender gains 0.1, and the others gain 0.7. The owner of that particular block also loses 1.

Attacker's net results: (10 * 0.2) + (1 * -1) = 1 block
Defender's net results: (10 * 0.1) + (9 * -1) = -8 blocks
Others' net results: (10 * 0.7) + (0 * -1) = 7 blocks

So the attacker expects to gain 0.1 blocks for each orphan race in this case where he has 0.1 more hashrate than his opponent.

More generally:

An entity's benefit from someone else's block being orphaned equals 1 block times their hashrate share.

An entity's benefit from an orphan race equals the above plus -1 blocks times their probability of losing the race (i.e. their opponent's share).

A's opponent is B. B's opponent is A+C. C has no opponents.

A's net results per race: (1 * A) + (B * -1)
B's net results per race: (1 * B) + ((A+C) * -1)
C's net results per race: (1 * C) + (0 * -1)

If we assume that A can make blocks that have an arbitrarily large delay without A's acceleration, orphan races will happen whenever A miners a block immediately followed by B. That is, they happen with frequency AB.

A's expected benefit: AB * (A-B) = 0.2%
B's expected benefit: AB * (B - (A+C)) = -1.6%
C's expected benefit: AB * (C) = 1.4%

If we plug in A=.4, B=.2, C=.4, we get:

A's expected benefit: AB * (A-B) = 1.6%
B's expected benefit: AB * (B - (A+C)) = -4.8%
C's expected benefit: AB * (C) = 3.2%

If the unaccelerated propagation time is t, then you multiply all those numbers by 1-e^(-t/600). For the 83 second delay I calculated a couple posts ago for an adversarial graphene 1 GB block, that would be a factor of 12.92%.

A pool with hashrate=0.4 and 83 second delay can gain 0.2067%% with this attack. Typical pool fees are on the order of 0.9% to 3%, so an extra 0.2067% would increase their total profit by 6.89% to 23.0%.

A pool with hashrate=0.2 and 83 second delay can increase their total profit by 0.86% to 2.9%.

In BCH terms, if A=0.4 and the block reward is 12.5 BCH, then the pool can gain 350.2 BCH per month in stolen profit. At A=0.2, the pool can gain 21.888 BCH/mo in stolen profit.

That seems like a scenario where it could be worthwhile for someone to actually perform this attack. A single pool with 40% of the hashrate is not too farfetched. We've seen that before several times. Even the 20% pool has a lot to gain.

One might think that miners would just switch pools from A to C if A did a selfish attack, since C actually benefits more than A. In truth, though, A would just cycle through all the other pools, so each one would have an equal amount of time being the victim. If this attack were being performed, it would just look like A had a lower orphan rate than everybody else. When calculating how much they owe their customers, they could use the network-average orphan rate and pocket the difference.

Interestingly, this attack appears to be profitable for any sized miner or pool to perform. A pool with 1% of the network hashrate would have a positive (but tiny) expected benefit from using this attack against a 0.5% miner or pool. However, the infrastructure costs (for VPSs) increase if you want to be able to target miners that finely, so it's only practical for larger pools.

...

Can anyone think of a good name for this attack? "Propagation-mediated selfish mining" is awkward. Maybe "network-partitioning delay attack"? There has to be something better than that.

 

[awemany]

@jtoomim, really quick as there's an issue with OP_DATASIGVERIFY that makes it or breaks it IMO and that I am working on:

Graphene unfortunately uses just TCP at the moment. Fully concur on UDP with FEC and having Graphene on top of that. I have looked for cheap ways to improve the current Graphene wire protocol and I think there's another 25% or so that can be saved just by encoding some fields more efficiently and dropping others. AFAIR George Bissias tentatively agrees and has some further ideas to optimize this.

The 83s seems to be a huge value in the above. You'd have to isolate that particular pool for 83s from receiving a more efficiently transferred block, correct?

I think a good way forward to guard against your scenarios is parallel block validation - and as I said, I think of it as elegant as it guards against multiple scenarios. (For example also the broken attack block with O(n^2) scenarios of which I am not sure that we've plugged all the holes that could lead to such a situation).

That all said, good luck on your negotiations with your power provider.

 

[jtoomim]

Yeah, the 83 sec is pretty long. It's a worst-case scenario using an adversarially constructed 1 GB graphene block with 30 kB/s effective TCP bandwidth. I was a bit surprised by that number too when I calculated it. Note that 30 kB/s is what we seem to be getting right now out of TCP for lossy long-haul links with traffic bursts. TCP congestion control is not our friend.

If you drop that to 8.3 seconds, then you still get 35 BCH/month for the 40% pool. I think 8.3 sec is an underestimate of what would be possible, though.

Parallel block validation does not solve the problem. The analysis we just did assumes validation times are 0 seconds, and all of the delays come from block propagation.

The O(n^2) sighash bug was fixed in the BCH fork. Yes, parallel validation also addressed that problem.

 

[awemany]

@jtoomim: But the extra delay in graphene transmission could simply be achieved by trickling the block out instead?

I was thinking parallel validation is a defense because I figuring you were thinking about some kind of propagation of blocks that would be akin to 'cut-through switching'.

 

[jtoomim]

In order for the attack to work, you need to generate a block that can't be forwarded quickly without some secret.

For example, I can generate a block using a transaction order determined by some 256 bit cryptographic random seed. If I want to send that block to another one of my own nodes, I can do it as a Graphene block plus that 256 bit seed to dictate the order. I do this to a VPS on the same LAN as the pools I want to have supporting my block. If I have 40% of the network hashrate, I do that for all but 40%/2 = 20% of the hashrate. So all but 20% of the network gets the block within a second, and 60% of the network is trying to send the block to the remaining 20%. That ends up being slow for them because they don't have the 256 bit seed (and wouldn't know what it means anyway). So instead they have to encode the full block order at e.g. 4 bytes per transaction, and send that in their Graphene block. 4 bytes per TX for a 1 GB 2 million tx block is 8 MB.

Because TCP sucks, getting 8 MB to every corner of the globe can take a shockingly long time. Back in 2015 when I did tests, we saw an average of 90 seconds for 9 MB blocks to get to every node in China, but some blocks took even longer, up to 130 seconds. And that was with a network of about 15 nodes. Most of that delay was due to TCP congestion, speed-of-light latency, and China Unicom+China Telecom+China Mobile's policies of not provisioning enough fiber to avoid congestion on their interconnect peering links, and to charge through the wazoo for international links that aren't congested. And the Firewall compounds the issue.

Something else to keep in mind when thinking about these bandwidth requirements: You need to be uploading these block encodings to between 8 and 100 nodes at the same time. A block propagation velocity of 30 kB/s can represent a node that's actually sending out 1.5 MB/s of data to 50 peers, but each peer is only getting 30 kB/s of that.

Key things with this attack: You can do it with any arbitrary amount of hashrate. As long as you are isolating a subset with less hashrate than you have, you will win at least a little bit. You are able to use the hashpower of other pools to support your block without their collusion.

Something I'm concerned about, but don't know enough about to be sure, is that it may be possible to create adversarial Graphene encodings in other ways by e.g. manipulating the mempool, or by brute-force generating transactions with hashes that make IBLT decoding problematic. If you can make Graphene unencodable/undecodable without a secret, then you can force other nodes to fall back to xthin or getblock, and if that happens, 83 seconds will pass like a heartbeat.

 

[awemany]

But this all depends on the block not being available in normal fashion through another link?

 

[jtoomim]

It's all about delays. It will be available eventually, but the extent to which the block can be delayed for a small subset of the network is the extent to which the attacker can profit. A 1 GB block has 2 million transactions, but that might only be a 20 kB Graphene message if you have the right order. On the other hand, if you have to fall back to manual order encoding, you're looking at 8 MB. If you have to switch to xthin, you're looking at 15 MB. Those numbers are prohibitively slow. The block is available, just not fast enough.

 

[Tom Zander]

Maybe you can start to acknowledge that the majority of the transactions in a block can be freely reordered and only a very small percentage (typically less than one percent) is required to be in natural ordering.

Acknowledging that and thus acknowledging your graphene message will be 21KB without any hard fork need, that acknowledgement will make this discussion a lot more honest.

 

[theZerg]

@jtoomim This is not directly relevant to the rest of your arguments, but since I've read it a few times I'd like to discuss.

Calculating a number for gigablock propagation and calling it network propagation is not accurate. I did not allow the mempool to be updated with new transactions while processing blocks. Given the giga_perf optimizations, this was an easy feature to add, but we needed to stop dev and start collecting data to make the presentation date. But the effect of this is that the time transactions were being accepted was much less than the 10 minute block interval average. So dividing blocksize/10minutes and calling that network capacity is making a big mistake.

 

[awemany]

On a completely different note (well it might be touching the topic of lexicographic ordering indirectly), I made this reddit post:

https://www.reddit.com/r/btc/comments/97b7nf/telegram_and_other_privacy_drains/

@dgenr8 , @deadalnix

 

[Peter R]

@jtoomim:

I agree with all of your math. As for a name for this attack, two ideas for short/simple names are an "ostracism attack" and an "outcast attack." The first name refers to the victims being treated differently and in a negative way. The second name refers to a social group that would be the "last to know" any exciting news.

But I still don't see how this attack can be carried out in an impactful way without collusion between groups A (the attacker) and C (the other miners).

For example, I can generate a block using a transaction order determined by some 256 bit cryptographic random seed. If I want to send that block to another one of my own nodes, I can do it as a Graphene block plus that 256 bit seed to dictate the order. I do this to a VPS on the same LAN as the pools I want to have supporting my block. If I have 40% of the network hashrate, I do that for all but 40%/2 = 20% of the hashrate. So all but 20% of the network gets the block within a second, and 60% of the network is trying to send the block to the remaining 20%. That ends up being slow for them because they don't have the 256 bit seed (and wouldn't know what it means anyway). So instead they have to encode the full block order at e.g. 4 bytes per transaction, and send that in their Graphene block. 4 bytes per TX for a 1 GB 2 million tx block is 8 MB.

How do the 40% of the miners you don't control know how to interpret the 256 bit seed? The way I see it, if some miners can interpret the seed (without collusion) then all miners should be able to interpret the seed.

If it takes 2 seconds to send the block to the other 40%, then why can't the other 40% send the block in the same way to the remaining 20%? This means the lag is only t = 2 seconds.

 

[awemany]

EDIT: The below has since been all solved. I am sorry for calling names. It was due to a miscommunication.
----

Sorry for making this public @deadalnix, but I want to say I am moderately angry now.

On a comment by @MarkBLundeberg on reddit, I have been pointed to an updated spec on the CHECKDATASIG(VERIFY) opcode that included double-hashing the input. This is problematic, and yesterday evening, I pointed this out in the pull request for the spec:

https://github.com/bitcoincashorg/bitcoincash.org/pull/93#issuecomment-412637195

This pull request includes two reviewers and developers from your ABC team, schancel and jasonbcox.

I like to also point out that this very late spec change is due to a very late change of the code (the introduction of double-hashing, that is), which happened on Sunday (ABC commit bcaa59bb2fbeec1811696a99a1dddf9530126b1c). It came to my ears that you don't like late spec changes, and I have to say I agree, but the last folks you can attribute this to is me or @theZerg. So I hope something got lost in translation here, but it sounded a bit from @Mengerian like you put blame on us. I have a hard time reaching you, communication is difficult. See the above question on lexicographic ordering by @ShadowOfHarbringer as well.

I didn't get any response, except by @Mengerian, who supported my plight to make it just a single hash. He then talked (while I was asleep) to @theZerg, who was going to implement this.
When I woke up, I got notified of that new thread (a three person meeting between us on slack) and I gladly took over the job to implement this. I was warned by @Mengerian that it is unlikely this will get merged. He told us that ABC is informed that we're working on this. I then pushed ahead because I feel this change is very important.

I posted progress updates regularly, including code and pointed to my code as soon as 2pm today (CEST). So by that time, your team was WELL aware that I was working with high intensity on this.

I then further took the effort to all make it compatible with your phabricator process, set up the build environment for ABC (which is different from BU, just so much as to also cause some minor extra work) and when I was finished with my work, which included regular pushes to github and several messages (as can be seen in that github PR) opened a "differential":

https://reviews.bitcoinabc.org/D1652

That commit then idled there for several hours with your reviewers keeping dead quiet about it. Reviewers who knew about my work as I was posting updates on the spec PR and mentioned them - as it can be seen, as reviewers (as recommended by Mengerian) in the Differential.

Then, suddenly, three hours later, you post your code:
https://reviews.bitcoinabc.org/D1653

And suddenly the reviewers spring into action right away.

Now I am fine if you take the commit authorship of your variant what is essentially the same code, you wrote that one. Most important is that the opcode gets fixed. (Though as a minor note aside, it would be great if you could credit on finding the issues, especially the issue of the length prefix.)

That's not what I am angry about, however. I am angry that I wasted my time, even though you have been informed that we're working on this. You just merged your PR. Great.

I wasted a lot of time today with writing this. @Mengerian has facilitated communication with you because there was no other way to reach out, apparently. I thank him for that.

But one little note that you will take this over and do your own implementation would have been very easy. If something is a dick move, then it is this.

 

[jtoomim]

@Peter R, I like both of those names. Thanks. I have a slight preference for outcast attack. It's like if a bunch of friends has one person who usually does the instigating for get-togethers, and suddenly decides to stop inviting you. He invites everyone else at the same time on Facebook. They're all welcome to invite you too, but they don't notice you're not invited until they get to the party and see that you're not there yet. So they call you on your phone, but you still have to get dressed and find a gift to bring to the party. By the time you arrive at the party, everyone else has moved on to go clubbing. Nobody wants to drink the scotch you brought, so you drink it all yourself and spend the night alone. No cute girls for you tonight. If this keeps happening to you, then you never get to have any children, making you a childless block in the blockchain.

@jtoomim:
But I still don't see how this attack can be carried out in an impactful way without collusion between groups A (the attacker) and C (the other miners).
How do the 40% of the miners you don't control know how to interpret the 256 bit seed?

Pool C doesn't know how to encode/decode the seed at all. Rather, A does it for them. All that A needs to do is rent a server in the same datacenter as C's poolservers. You send the block with your own 256 bit encoding to your own rented server, then you use the general (and inefficient, in this case) Graphene or getblock protocol to send the block to them. Since you're on the same LAN (possibly even the same physical server!), you'll have 1 to 40 Gbit/s of bandwidth with <1 ms latency, so it won't matter that the encoding is inefficient. However, if they try to forward that inefficient encoding to other pools in different datacenters or different countries, the inefficient encoding will slow the flow to the speed of black molasses, or possibly even honey.

How do you know where to set up your VPSs? It's fairly well-known in the mining community where a lot of these poolservers are. Most are in Aliyun Hangzhou, Shanghai, or Beijing. Renting a VPS there costs under $30/month per site. Those three DCs used to encompass 60% of the network hashrate for BTC. In general, you can find the DCs their servers are in by doing GeoIP lookups.

Maybe you can start to acknowledge that the majority of the transactions in a block can be freely reordered and only a very small percentage (typically less than one percent) is required to be in natural ordering.

Acknowledging that and thus acknowledging your graphene message will be 21KB without any hard fork need, that acknowledgement will make this discussion a lot more honest.

Correct, most of the transactions can be freely reordered, unless there's a (soft?) fork to remove that ability. That is exactly the problem.

It seems you think that no rational self-interested miner would ever intentionally create an order that obstructs block propagation. That is a very intuitive position to have, but it turns out to be false, according to Peter R's and my model of the outcast attack.

If you can pick and choose whom you quickly propagate the block to, then you can gain extra rewards (after diff adjustments) by orphaning their blocks more often than not. You can accomplish this in Graphene by setting your own servers next to the pools you want to receive your blocks quickly, using weak blocks or a secret encoding scheme to get your blocks to your relay servers, and then intentionally randomizing your transaction ordering so that everyone else suffers a delay.

If there is an incentive for people to intentionally obfuscate their blocks, we cannot assume that people will always volunteer to keep their orders sane. Such an incentive exists. While it's not terribly strong for common scenarios, it could be significant in the GB block era. Because we can't assume miners will always order transactions sanely of their own selfish free will, we should consider enforcing a sane ordering as a consensus rule.

The ostracizing behavior I'm describing is an adversarial condition. This is not an accidental selfish mining instance (though those exist too); it's an intentional one.

If you're proposing a soft fork to address this scenario, then I agree, that would work. I think a full lexicographic sorting would be more elegant and probably more performant, but those are both empirical questions if a lex sorting implementation is ever written.

@jtoomim This is not directly relevant to the rest of your arguments, but since I've read it a few times I'd like to discuss.

Calculating a number for gigablock propagation and calling it network propagation is not accurate. I did not allow the mempool to be updated with new transactions while processing blocks. ... dividing blocksize/10minutes and calling that network capacity is making a big mistake.

I was not calculating 1 GB / 600 sec = 1.666 MB/s. Instead, I was basing it off of the slope z in Peter R's least squares fit. That best fit line appears to explain propagation speed at lower blocksizes equally well. As I understand it, at lower blocksizes, there should be enough time in between block validation steps that neither mempool fill rate nor block validation will lock up the CPU. Consequently, there should be plenty of free cycles around the time the block is being propagated, and mempool shouldn't stop that. Is that correct? Yes, things get wonky at around 300 MB, but I (and the least squares fit) was looking mostly at the 1 MB to 100 MB range, all of which seems to be fit decently by 1.6 MB/s. Is there something I'm missing?

 

[AdrianX]

Coindesk - the gloves are off. https://www.coindesk.com/a-new-way-to-compare-bitcoin-cash-to-bitcoin/

 

[jtoomim]

I propose DDoSing their employees with kittens. If we mail them enough warm furry cuteness, their workers will be too happy and won't be able to write anything negative again.

 

[jtoomim]

By the way, on a different topic, has anyone thought about bringing back the free transaction relay mechanism we had in Bitcoin Core 0.11 and before as a way of dealing with the low-fee (below mintxrelayfee) double-spend attack? Eliminating minrelaytxfee entirely opens DoS risk, but if you cap the flow rate for free transactions, you can detect double spends most of the time, and for the rest you can notice when your flow rate is capped and DoSed and possibly restrict 0-conf.

Is this worth making a Github feature request issue?

 

[jtoomim]

@jtoomim, really quick as there's an issue with OP_DATASIGVERIFY that makes it or breaks it IMO and that I am working on

Just so you know, I have no opinion or special knowledge on OP_DATASIGVERIFY. I am not a member of the Bitcoin ABC team. (I am on nobody's side, because nobody's on my side.)

 

[79b79aa8]

well hopefully your power utility is on your side! $0.025 kW/h or bust.

 

[jtoomim]

Bust it is then. I went to the meeting to propose a $0.0345/kWh rate, actually. With $105k/MW collected up front and an 8.5 month deposit. Link if you're curious.