Topic: Current SegWit code does not fix O(n^2) (Read 1346 times)

Don't be so hard on him on this (every other reason is good to go).  SegWit Omnibus changeset sounds like something _I_ would say-- I'd use it to refer to the pull request that implemented the segwit consensus rules, the segwit wallet support, and the huge amount of testing infrastructure.

I actually haven't since he's on my ignore list (and I'm only replying to satisfy my masochistic tendencies), but I did Google the phrase and fail to find anything useful. I'm just going to assume it means "SegWit plus all other Core updates I don't understand or like".

Fundamental misunderstanding, conflating the protocol with non-normative implementation particulars.  The Bitcoin protocol has a design flaw where transaction validation can take time quadratic in the size of the transaction. No implementation can avoid this wasteful computation because it is a consensus rule normative to the protocol.

With an increase in blocksize this wasteful computation could easily be turned into a system halting denial of service.

Rather that fixing it, Bitcoin Classic implemented yet another useless hard limit of transaction sizes-- to keep the bleeding at a moderate level. (Still allowing blocks to trigger 1.2 _gigabytes_ of hashing)

Segwit's design addressed the issue in two ways: One is that the extra capacity in segwit is for witness data, which is not hashed by the signature hasher. Because of this even with no fix, the worst case possible is much less significant than a plain 2MB block.  The other is that segwit changes the data structure which is hashed to not require the quadratic computation, by making the part of the hashing that all signatures would share identical that computation can be shared-- the resulting structure can be hashed with O(N) work instead of O(N^2).  These are both done, integrated, and tested since 2015.  Both are fundamental to segwit.

The point Peter Todd was making was that the segwit implementation in Bitcoin Core doesn't make use of that changed structure in the second improvement to actually save the computation possible from that second improvement.  There is an open pull request for it it just isn't integrated yet.  Btcd's does however.    This is an implementation specific difference, on my computer it does, on yours it doesn't and we're totally compatible.  Similarly, even ignoring segwit Bitcoin Core is normally many times faster than btcd, but both are compatible.

Our focus is on correctness, compatibility, and ensuring flexibility, not in getting in every last possible optimization into the system on day one. Not changing the signature-hashing algorithm, just changing the data structure, made review for correctness easier, and also allowed compatibility testing (between the naive code, the unmerged optimization, and the btcd implementation).

The important thing is that the design flaw has been eliminated for segwit txn; allowing the implementations to implement the optimization at their leisure.  It makes not a difference at all if anyone actually makes use of the new structure until segwit is activated on the network.

Fair point. At least he doesn't have a 24/7 shift on his account.

If you've seen his posts anywhere else before, you'd know that he calls it the "The SegWit Omnibus Changeset". I can only assume that the changes are too complex for himself and thus they must be complex for everyone.

That's what altcoin supporters mostly call them, yes. That part about "several Core supporters deriding.." is also false. We have Hearn (who is definitely not a Core supporter), Garzik and Gavin. All of these people have barely contributed anything to the development in the recent times.

Apparently only their (wrong) way is the right way in their eyes.

So then what does that mean? The SegWit code has been released ages ago. Do you mean the version of Bitcoin Core that merges the code? It's sure to have a whole bunch of new features completely unrelated to SegWit (mostly bugfixes) and anyway nobody can be sure exactly what features it will have until it is actually released.

"Alternative node implementations"? Is that what we're calling altcoins now?

That's to be expected. SegWit bashers are weird people.

Hello Gregory. I was not trying to insinuate anything was wrong, per se. We layfolk are not party to the detailed development plans, and that is OK. However, with several Core supporters deriding alternative node implementations for limiting the effects of the O(n^2) issue, rather than solving it head on -- specifically with the claim that The SegWit Omnibus Changeset addresses this in a better manner -- it is somewhat of a surprise to learn that this feature is not yet integrated. At what point is this feature scheduled for integration? How long has it been in test, and in what environment?

Can you explain to me what the change does and what significance it has?

I think that would do more to get the details, like making it clear that your "concern" is motivated by harassment rather than actual concern.

I expect it to be included in any release with segwit activated.

Frankys, do something. Something real, in the real world. Anything, to prove that you're not just some computer science back-seat driver. You just have no clue about this stuff, and seriously expect to waste everyone's time with your rambling moronic over-wrought tl;dr posts.

lets get to the short and curlies of it.
lets not talk about the segnet(altcoin/sandbox) implementation. or the testnet(altcoin/sandbox) implementation.. i truly hate people back-dating availability by including the time its played around with in sandboxes of non bitcoin data

but in regards to a publicly downloading implementation that handles real bitcoin data on the real live bitcoin network.
will the optimization be included in the next release. (just needs to be pulled) or are you saying it wont be because it "complicates review and increases risk"

im asking respectfully. will the next version of bitcoin-core including segwit be "optimized" or will it be another release at a later date that the "optimization" is added.

all i ask is a simple reply without waffle. even something like "next release" or "at a later date after initial bitcoin core segwit release" would suffice

Weird thread.

Fixing the O(n^2) issue required a change in how signature hashes are computed so that the work of hashing the transaction can be reused between multiple signatures.  Then it requires making use of that change van an optimization to actually reuse the computation.  (This optimization has earned the cheeky name, hashcache).

The segwit consensus rules do the former.  The segwit PR to Bitcoin core didn't include the latter optimization, because it isn't wasn't for the system to work (assuming we don't care that it can be slow), and packing everything in at once complicates review and increases risk. The correctness of the optimization is easier to verify as a change by itself, and the correctness of segwit was easier to verify without the optimization in the way.

But the code to actually make use of the format change is the queue as well https://github.com/bitcoin/bitcoin/pull/8259  (which was open 5 days ago, but the code for it was written January 19th).  This optimization is also part of the btcd implementation and has been since they originally wrote it.

Considering this, the presentation of this as some kind of flaw or surprising find make it look to me that people are desperate to find something wrong.  I suppose that is good: more eyes may reduce the risk of unbound actual issues. Hopefully the next time it won't be over a missing optimization which we've had an implementation of for six months.

I disagree. The amount of traffic dedicated to the subject shows that transaction volume is a topic of near-universal interest. In light of the fact that the O(n^2) hashing issue bears directly upon the ability of certain transactions to impair transaction volume, it would be a topic perfectly suitable for general discussion.

Well, no. Destroying a productive system (assuming you are referring to Bitcoin) would be directly against my financial interests. Accordingly, I am working towards its success.

All the features bundled together as part of the impending SegWit release.

this discussion belongs to Development & Technical Discussion. it's useless for 99% from those who are using BTC.

Depends on whether your work involves building or destroying. jbreher is hell-bent on destroying a productive (not to mention innovative) system, so he's no better than those sociopathic bullies that bat food out of a stranger's hand and then walk off down the street laughing at their hilarious "joke".

I'd like to hear their failed attempts at gather excuses as to why they didn't notice it. Either they have failed to recognize this, or they haven't looked at it at all (which tells us more than we need to know).

Doesn't working count as being productive?

OP makes out like he's the one reporting the issue. He's not.

None of the coup-attempt Developers noticed this, even though they were most incentivised to do so. lol

It's pretty sad really, jbreher, all you can do is dance around like a child sticking your tongue out. Why not do something productive with your "life"?

How can I be aware? I've actually never heard the phrase "The SegWit Omnibus Changeset" before your post, and a Google search for that phrase doesn't turn up much either. You say it's "more stuff" than SegWit, but what exactly is it? Who's selling it? Is anyone buying it? You need to define your terms.

I realize that SegWit -- in and of itself -- does not do anything about the quadratic verification time. That is but one reason I refer to it as The SegWit Omnibus Changeset - there is considerably more *stuff* in it than SegWit. Indeed, my impression is that SegWit itself has absolutely nothing whatsoever to do with the alleviation of quadratic verification time.


Well, you might be saying that, but the message that is coming through loud and clear is 'we don't need a simple increase in maxblocksize because SegWit!'

Well, that and 'The SegWit Omnibus Changeset is superior to other solutions from a scaling perspective because other solutions merely limit quadratic hashing time, rather than fixing it!'


Maybe if the company line wasn't always changing, we'd latch onto it.

But whatevs...

You _are_ aware that The SegWit Omnibus Changeset is being sold as a solution to the block congestion problem, right?

So what? SegWit only makes linear verification time possible, it doesn't necessarily implement it. And the reason there's no rush to implement it is because scaling is not the purpose of SegWit! How many times do we have to explain that before people get it? It seems like people have the expectation that when SegWit is "implemented" (a word which seemingly nobody can agree on a definition) blocks will stop "being full" and transaction fees will drop to almost nothing so they can buy their coffee on the blockchain. These people then get inexplicably angry every time someone tries to tell them that this is not actually the case.