Bitcoin Forum
November 23, 2017, 11:02:50 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: Current SegWit code does not fix O(n^2)  (Read 1114 times)
jbreher
Legendary
*
Offline Offline

Activity: 1848


lose: unfind ... loose: untight


View Profile
June 29, 2016, 03:51:41 AM
 #1

Like the title says. The current iteration of The SegWit Omnibus Changeset does not fix the O(n^2) hashing problem. At least according to Peter Todd:

Quote
We haven’t actually fixed the O(n²) signature hashing problem yet, although we’re fairly confident that we can, and there’s a open pull-req implementing the cache that we need.

- https://petertodd.org/2016/segwit-consensus-critical-code-review

Not necessarily an insurmountable problem. And I suppose PT might be... err... uninformed. However, it certainly puts some specious claims (e.g., April; e.g. safe scaling) into perspective. One wonders what other major claimed features of The Omnibus SegWit Changeset remain technical pauperism.

Might be worth a discussion, donchathink?

Anyone with a campaign ad in their signature -- for an organization with which they are not otherwise affiliated -- is automatically deducted credibility points.

I've been convicted of heresy. Convicted by a known extortionist. Read my Trust for details. https://www.youtube.com/watch?v=sglyFwTjfDU
1511478170
Hero Member
*
Offline Offline

Posts: 1511478170

View Profile Personal Message (Offline)

Ignore
1511478170
Reply with quote  #2

1511478170
Report to moderator
1511478170
Hero Member
*
Offline Offline

Posts: 1511478170

View Profile Personal Message (Offline)

Ignore
1511478170
Reply with quote  #2

1511478170
Report to moderator
1511478170
Hero Member
*
Offline Offline

Posts: 1511478170

View Profile Personal Message (Offline)

Ignore
1511478170
Reply with quote  #2

1511478170
Report to moderator
Join ICO Now A blockchain platform for effective freelancing
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511478170
Hero Member
*
Offline Offline

Posts: 1511478170

View Profile Personal Message (Offline)

Ignore
1511478170
Reply with quote  #2

1511478170
Report to moderator
1511478170
Hero Member
*
Offline Offline

Posts: 1511478170

View Profile Personal Message (Offline)

Ignore
1511478170
Reply with quote  #2

1511478170
Report to moderator
crazywack
Legendary
*
Offline Offline

Activity: 1148


View Profile
June 29, 2016, 04:05:46 AM
 #2

Wow all the hype and it's not going to help clean up the mem pool right away, I'm I getting that right?

RealBitcoin
Hero Member
*****
Offline Offline

Activity: 854


JAYCE DESIGNS - http://bit.ly/1tmgIwK


View Profile
June 29, 2016, 04:11:36 AM
 #3

1 THING:  DONT RUSH THEM.

Whatever happens, dont rush the devs. They are working hard and they dont need pressure on their heads.

If you rush them, they might fuck it up, and we dont want that to happen. The network can easily work well 5-6 more months, so no need to rush things.

They should take their time, think ,research, develop, and test many times the proposals. Then we can implement it.

crazywack
Legendary
*
Offline Offline

Activity: 1148


View Profile
June 29, 2016, 04:15:16 AM
 #4

1 THING:  DONT RUSH THEM.

Whatever happens, dont rush the devs. They are working hard and they dont need pressure on their heads.

If you rush them, they might fuck it up, and we dont want that to happen.

Or do we?! Wink cheap coins.

I'm kidding. I just thought that with all the press in the BTC space of its implementation going live, we would actualy see it working and cleaning up he pool. That's all, just disappointing it's not ganna work out that way right now.

Lauda
Legendary
*
Offline Offline

Activity: 1680


GUNBOT Licenses -15% with ref. code 'GrumpyKitty'


View Profile WWW
June 29, 2016, 04:27:33 AM
 #5

Wow all the hype and it's not going to help clean up the mem pool right away, I'm I getting that right?
No, you're not getting this right. This has nothing to do with "help clean up the mempool".

Like the title says. The current iteration of The SegWit Omnibus Changeset does not fix the O(n^2) hashing problem. At least according to Peter Todd:

Quote
We haven’t actually fixed the O(n²) signature hashing problem yet, although we’re fairly confident that we can, and there’s a open pull-req implementing the cache that we need.
While I must admit that I was unaware of it at first, I don't see this as something problematic especially if you consider the last part. I've read some parts of that review last night and it seems very well done.

Might be worth a discussion, donchathink?
Maybe. However, don't be surprise if you see a lot of 'unusual' accounts joining in to bash Segwit.

I'm kidding. I just thought that with all the press in the BTC space of its implementation going live, we would actualy see it working and cleaning up he pool. That's all, just disappointing it's not ganna work out that way right now.
Again, you have no idea what you're talking about. There's no reason for it "not to work out that way right now".


▄██████████████████
███████████████████
███████████████████
█████████████████
███████████████
████████████████
████████████████
█████████████████
███████████████████
████████████████████
█████████████████████
▀████████████████████
Bazista®
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██

██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
|||
Foxpup
Legendary
*
Offline Offline

Activity: 2016



View Profile
June 29, 2016, 06:53:08 AM
 #6

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.

Will pretend to do unverifiable things (while actually eating an enchilada-style burrito) for bitcoins: 1K6d1EviQKX3SVKjPYmJGyWBb1avbmCFM4
jbreher
Legendary
*
Offline Offline

Activity: 1848


lose: unfind ... loose: untight


View Profile
June 29, 2016, 07:10:04 AM
 #7

So what? SegWit only makes linear verification time possible, it doesn't necessarily implement it.

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.

Quote
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?

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!'

Quote
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.

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?

Anyone with a campaign ad in their signature -- for an organization with which they are not otherwise affiliated -- is automatically deducted credibility points.

I've been convicted of heresy. Convicted by a known extortionist. Read my Trust for details. https://www.youtube.com/watch?v=sglyFwTjfDU
Foxpup
Legendary
*
Offline Offline

Activity: 2016



View Profile
June 29, 2016, 07:47:49 AM
 #8

You _are_ aware that The SegWit Omnibus Changeset is being sold as a solution to the block congestion problem, right?
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.

Will pretend to do unverifiable things (while actually eating an enchilada-style burrito) for bitcoins: 1K6d1EviQKX3SVKjPYmJGyWBb1avbmCFM4
Carlton Banks
Legendary
*
Offline Offline

Activity: 1834



View Profile
June 29, 2016, 09:01:31 AM
 #9

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"?


Vires in numeris
Lauda
Legendary
*
Offline Offline

Activity: 1680


GUNBOT Licenses -15% with ref. code 'GrumpyKitty'


View Profile WWW
June 29, 2016, 10:23:14 AM
 #10

None of the coup-attempt Developers noticed this, even though they were most incentivised to do so. lol
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).

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"?
Doesn't working count as being productive? Roll Eyes


▄██████████████████
███████████████████
███████████████████
█████████████████
███████████████
████████████████
████████████████
█████████████████
███████████████████
████████████████████
█████████████████████
▀████████████████████
Bazista®
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██

██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
██ █  ██ ██
██   ██  ██
██  ██   ██
██ ██  █ ██
|||
Carlton Banks
Legendary
*
Offline Offline

Activity: 1834



View Profile
June 29, 2016, 10:54:10 AM
 #11

Doesn't working count as being productive? Roll Eyes

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".

Vires in numeris
mayax
Legendary
*
Offline Offline

Activity: 1050


View Profile
June 29, 2016, 10:56:47 AM
 #12

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

Activity: 1848


lose: unfind ... loose: untight


View Profile
June 29, 2016, 07:09:02 PM
 #13

You _are_ aware that The SegWit Omnibus Changeset is being sold as a solution to the block congestion problem, right?
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.

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

Anyone with a campaign ad in their signature -- for an organization with which they are not otherwise affiliated -- is automatically deducted credibility points.

I've been convicted of heresy. Convicted by a known extortionist. Read my Trust for details. https://www.youtube.com/watch?v=sglyFwTjfDU
jbreher
Legendary
*
Offline Offline

Activity: 1848


lose: unfind ... loose: untight


View Profile
June 29, 2016, 07:14:10 PM
 #14

jbreher is hell-bent on destroying a productive (not to mention innovative) system

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.

Anyone with a campaign ad in their signature -- for an organization with which they are not otherwise affiliated -- is automatically deducted credibility points.

I've been convicted of heresy. Convicted by a known extortionist. Read my Trust for details. https://www.youtube.com/watch?v=sglyFwTjfDU
jbreher
Legendary
*
Offline Offline

Activity: 1848


lose: unfind ... loose: untight


View Profile
June 29, 2016, 07:17:34 PM
 #15

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

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.

Anyone with a campaign ad in their signature -- for an organization with which they are not otherwise affiliated -- is automatically deducted credibility points.

I've been convicted of heresy. Convicted by a known extortionist. Read my Trust for details. https://www.youtube.com/watch?v=sglyFwTjfDU
gmaxwell
Staff
Legendary
*
Offline Offline

Activity: 2338



View Profile
June 29, 2016, 07:36:49 PM
 #16

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. Smiley

Bitcoin will not be compromised
franky1
Legendary
*
Offline Offline

Activity: 1862



View Profile
June 29, 2016, 08:16:31 PM
 #17

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. Smiley

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

I DO NOT TRADE OR ACT AS ESCROW ON THIS FORUM EVER.
Don't take any information given on this forum on face value. Please do your own due diligence & respect what is written here as both opinion & information gleaned from experience. If you wish to seek legal FACTUAL advice, then seek the guidance of a LEGAL specialist.
Carlton Banks
Legendary
*
Offline Offline

Activity: 1834



View Profile
June 29, 2016, 08:31:37 PM
 #18

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.

Vires in numeris
gmaxwell
Staff
Legendary
*
Offline Offline

Activity: 2338



View Profile
June 29, 2016, 09:35:34 PM
 #19

lets get to the short and curlies of it.

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.

Quote
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.
I expect it to be included in any release with segwit activated.

Bitcoin will not be compromised
jbreher
Legendary
*
Offline Offline

Activity: 1848


lose: unfind ... loose: untight


View Profile
June 30, 2016, 12:06:44 AM
 #20

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

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?

Anyone with a campaign ad in their signature -- for an organization with which they are not otherwise affiliated -- is automatically deducted credibility points.

I've been convicted of heresy. Convicted by a known extortionist. Read my Trust for details. https://www.youtube.com/watch?v=sglyFwTjfDU
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!