Gold collapsing. Bitcoin UP.

Peter R

Well-Known Member
Aug 28, 2015
1,398
5,595
@rocks, @molecular

"The EC algorithm from a code perspective is pretty straight forward"

The high-level algorithm is pretty straightforward [see here]. However, once you get into the nuts & bolts, some of the operations are quite tricky and there are lots of ways to skin the cat. I believe there are at least three steps where it is possible to achieve algorithmic coding gain:

1. Calculating the curve point: (x, y) = k * G, where k is a secret number and G is the base point.

2. Doing arithmetic modulo a large prime number (at several points in the calculation)

3. Calculating the inverse of the secret number k.

For example, there are several different algorithms that can be used to carry out the multiplication in #1. The simplest is probably the "double and add" method. However, the amount of time it takes this algorithm to execute depends on the specific value of k (G is always constant for bitcoin). On the other hand, the "Montgomery Ladder" approach computes the point multiplication in a fixed amount of time (regardless of the specific value of k). This is beyond my expertise level, but I suspect there are several ways to tune this operation for the particular curve in question (secp256k1) to achieve both "constant time" and "as fast as possible."

Regarding the modulo arithmetic and inverse operations, there are speeds-ups possible here too and AFAIK the curve parameters for secp256k1 were actually chosen to facilitate acceleration of these operations.

I spent many days researching this when I was working on getting my sigsafe devices to be able to sign Bitcoin TXs using only the energy available from an NFC field. I forget a lot of it now, but I remember that it appeared to me at the time that lots of improvements should be possible if the math was tuned specifically for Bitcoin's elliptic curve.

That being said, I really wish the Blockstream folks would actually publish there work in a nice paper, so that we could all learn and understand what exactly the optimizations were. I dislike this "it's documented in the code" or "we discussed it on IRC" attitude.
 

Zangelbert Bingledack

Well-Known Member
Aug 29, 2015
1,485
5,585
https://bitcoin.org/en/bitcoin-core/capacity-increases


Looks like I already have to add another couple of sliders to my Consens-o-Tron:
  • NUMBER OF CONTRIBUTING DEVS REQ'D, REGARDLESS OF HOW MUCH THEY EACH CONTRIBUTED
  • HOW RECENT THEIR CONTRIBUTIONS MUST BE
[doublepost=1450740506,1450739710][/doublepost]It would be pretty disgraceful if their plan is to use the long tail of minor devs, many of whom would of course be likely - in any such high-profile software project - to be wannabes or sycophants eager to tow the party line, to rig the consensus away from a consensus of the committers because of Jeff's (and Luke's) sudden appearance as flies in Blockstream's ointment. "Look at all these people who agree, and how few of them work for Blockstream!"
 

cypherdoc

Well-Known Member
Aug 26, 2015
5,257
12,995
@rocks, @molecular

"The EC algorithm from a code perspective is pretty straight forward"

The high-level algorithm is pretty straightforward [see here]. However, once you get into the nuts & bolts, some of the operations are quite tricky and there are lots of ways to skin the cat. I believe there are at least three steps where it is possible to achieve algorithmic coding gain:

1. Calculating the curve point: (x, y) = k * G, where k is a secret number and G is the base point.

2. Doing arithmetic modulo a large prime number (at several points in the calculation)

3. Calculating the inverse of the secret number k.

For example, there are several different algorithms that can be used to carry out the multiplication in #1. The simplest is probably the "double and add" method. However, the amount of time it takes this algorithm to execute depends on the specific value of k (G is always constant for bitcoin). On the other hand, the "Montgomery Ladder" approach computes the point multiplication in a fixed amount of time (regardless of the specific value of k). This is beyond my expertise level, but I suspect there are several ways to tune this operation for the particular curve in question (secp256k1) to achieve both "constant time" and "as fast as possible."

Regarding the modulo arithmetic and inverse operations, there are speeds-ups possible here too and AFAIK the curve parameters for secp256k1 were actually chosen to facilitate acceleration of these operations.

I spent many days researching this when I was working on getting my sigsafe devices to be able to sign Bitcoin TXs using only the energy available from an NFC field. I forget a lot of it now, but I remember that it appeared to me at the time that lots of improvements should be possible if the math was tuned specifically for Bitcoin's elliptic curve.

That being said, I really wish the Blockstream folks would actually publish there work in a nice paper, so that we could all learn and understand what exactly the optimizations were. I dislike this "it's documented in the code" or "we discussed it on IRC" attitude.
i see this as a big problem.

as @rocks said, much of this this work on advanced crypto, esp new home brewed algos, need to be published in a rigorous manner to allow peer review by academia and industry. all coding and crypto expertise does not simply lie within core dev. and from what i've read, it takes years of testing and analysis with ppl all over the world poking and prodding the math and assumptions to make sure there are not holes.
 

Peter R

Well-Known Member
Aug 28, 2015
1,398
5,595
@cypherdoc

This isn't a new cryptographic operation that they've invented--instead it's a faster ways to calculate the answer using already-existing equations. So personally I'm not that concerned. Nonetheless, I still totally agree that they should write a paper about it to give more people the opportunity to understand what it's all about.
 

cypherdoc

Well-Known Member
Aug 26, 2015
5,257
12,995
well, there you have it:

"Bitcoin Core is a private software project, not Bitcoin itself."

[doublepost=1450741097][/doublepost]
@cypherdoc

This isn't a new cryptographic operation that they've invented--instead it's a faster ways to calculate the answer using already-existing equations. So personally I'm not that concerned. Nonetheless, I still totally agree that they should write a paper about it to give more people the opportunity to understand what it's all about.
so this isn't a concern?:

"Libsecp256k1 has many custom algorithms, it would not have this performance otherwise."
[doublepost=1450741347][/doublepost]hypocrisy at work:

 

Peter R

Well-Known Member
Aug 28, 2015
1,398
5,595
@cypherdoc:

so this isn't a concern?: "Libsecp256k1 has many custom algorithms, it would not have this performance otherwise."

I think the confusion is that people are using the words "algorithms" to mean two different things. Libsecp256k1 uses the standard ECDSA digital signature algorithm on the standard secp256k1 curve. The "custom algorithms" involve the mathematical operations needed to carry out the lower-level computations inside the ECDSA algorithm. See what I mean? So yeah, it's still a concern, but it's not like they've invented a new cryptosystem. Instead they've sped up some number crunching within an already-established algorithm.

Still, I'd feel a lot better if I could read up what exactly those efficiency improvements were.
 

Peter R

Well-Known Member
Aug 28, 2015
1,398
5,595
@theZerg

Exactly. Now what happens if Blockstream Core loses control after segwit is activated and miners revert back to the pre-sigwit rules?: I believe in that case they could steal all the segwit coins. I wouldn't be too surprised to see the market actually cheer for this as some sort of perverse punishment to teach us a lesson about soft vs. hard forks.
[doublepost=1450743822][/doublepost]Just curious: us big-block proponents face a headwind because the GitHub repo, bitcoin.org, /r/bitcoin and bitcointalk are all control by small-block proponents. This allows them to win the "lazy and indifferent" simply be default.

To level the playing field, would @Gavin Andresen have the ability to at least freeze everyone out of the GitHub repo? I think the best thing now would be to just shut it down completely. This would put us on a more level playing field, as both sides would need to win back users.
 
Last edited:

JVWVU

Active Member
Oct 10, 2015
142
177
I am not necessarily a big block proponent yet, I prefer going to a 4 or 8 MB at halving in 2016 and taking a few more years to get a large scaling option.

But after reading Theymos posts in reddit I want to hit him in the head with a baseball bat.

Anyone here want to sign me up for Github and make a contirbution to Core so each of us have a voice.
 

cypherdoc

Well-Known Member
Aug 26, 2015
5,257
12,995
@theZerg

Exactly. Now what happens if Blockstream Core loses control after segwit is activated and miners revert back to the pre-sigwit rules?: I believe in that case they could steal all the segwit coins. I wouldn't be too surprised to see the market actually cheer for this as some sort of perverse punishment to teach us a lesson about soft vs. hard forks.
[doublepost=1450743822][/doublepost]Just curious: us big-block proponents face a headwind because the GitHub repo, bitcoin.org, /r/bitcoin and bitcointalk are all control by small-block proponents. This allows them to win the "lazy and indifferent" simply be default.

To level the playing field, would @Gavin Andresen have the ability to at least freeze everyone out of the GitHub repo? I think the best thing now would be to just shut it down completely. This would put us on a more level playing field, as both sides would need to win back users.
Yes, @Gavin Andresen, at least let us know to expect something or nothing.
 

theZerg

Moderator
Staff member
Aug 28, 2015
1,012
2,327
IDK but I've been advocating that for a while. But its gavin's choice ofc. As much as we razz on them for the big issue they do good work...
 

Zangelbert Bingledack

Well-Known Member
Aug 29, 2015
1,485
5,585
Wouldn't they just switch to a new repo? It'd be used as fodder for the mother of all claims of pettiness and lack of cooperation. Unless I'm misunderstanding something, this seems like it would damage trust severely among the community at large.
 
  • Like
Reactions: sickpig and AdrianX

Peter R

Well-Known Member
Aug 28, 2015
1,398
5,595
@Zangelbert Bingledack

Yes, they would just switch to a new repo. But it would be a different repo and I think people would notice the change and wonder what happened. Then they'd see Gavin (and Jeff?) on a new repo too and people might wonder "what is the real bitcoin now"?

Just brainstorming ways to get people to make an active choice, rather than blindly follow Core due to its historical ties to Satoshi's code.

Bad idea?
 

Peter R

Well-Known Member
Aug 28, 2015
1,398
5,595
Yes, I agree you'd want to give lots of time for both sides to organize, along with an explanation of why it's important to do.
 
  • Like
Reactions: AdrianX

rocks

Active Member
Sep 24, 2015
586
2,284
@rocks, @molecular

"The EC algorithm from a code perspective is pretty straight forward"

The high-level algorithm is pretty straightforward [see here]. However, once you get into the nuts & bolts, some of the operations are quite tricky and there are lots of ways to skin the cat. I believe there are at least three steps where it is possible to achieve algorithmic coding gain:

1. Calculating the curve point: (x, y) = k * G, where k is a secret number and G is the base point.

2. Doing arithmetic modulo a large prime number (at several points in the calculation)

3. Calculating the inverse of the secret number k.

For example, there are several different algorithms that can be used to carry out the multiplication in #1. The simplest is probably the "double and add" method. However, the amount of time it takes this algorithm to execute depends on the specific value of k (G is always constant for bitcoin). On the other hand, the "Montgomery Ladder" approach computes the point multiplication in a fixed amount of time (regardless of the specific value of k). This is beyond my expertise level, but I suspect there are several ways to tune this operation for the particular curve in question (secp256k1) to achieve both "constant time" and "as fast as possible."

Regarding the modulo arithmetic and inverse operations, there are speeds-ups possible here too and AFAIK the curve parameters for secp256k1 were actually chosen to facilitate acceleration of these operations.

I spent many days researching this when I was working on getting my sigsafe devices to be able to sign Bitcoin TXs using only the energy available from an NFC field. I forget a lot of it now, but I remember that it appeared to me at the time that lots of improvements should be possible if the math was tuned specifically for Bitcoin's elliptic curve.

That being said, I really wish the Blockstream folks would actually publish there work in a nice paper, so that we could all learn and understand what exactly the optimizations were. I dislike this "it's documented in the code" or "we discussed it on IRC" attitude.
All good points. Everyone still needs to know where the improvements came from and how though. There are pros and cons to everything and people need to agree to the trade-offs made IMHO.

For #1 Calculating the curve point, the double and add method already decomposes a multiply into a shift and add for speed-up, am curious to see where further improvements can come from. The "Montgomery Ladder" approach has constant time, but it is not faster. In fact this shows some of the trade-offs, faster is not better if it leaks information and there have been very interesting and successful timing based attacks over the years.

For #2 Changing the curve parameters is an algorithmic change. Other crypto algorithms have been shown to either be strong or almost fully broken based on the constant parameters used. This is the type of algorithmic change that should have +10 years of extensive testing.

BTW, DES (the predecessor to AES) has a very interesting history. This was the encryption standard for around 10 years until AES came out. When DES was going through its standardization process, the starting constants were changed by the NSA. The reason stated was to improve security. No one could find anything wrong with them.

10+ years later weaknesses were found in DES that the NSA changes actually helped protect against. Opposite what you would think, but it shows how the constants do matter, a lot. This is not something you change for performance reasons, you very well could have created an exploit.

For #3, isn't that operation only needed if you are generating a signature, not if you are verifying a signature? Speeding the signing of signatures is not needed since that's only done once per send. Speeding the verification of signatures is what needs to be done billions of times.

Overall my point is 1) the changes may seem small to some people and worth a performance, but in fact introduce one of many new attack vectors, and 2) need to be made public for testing and comments.

There has never, ever, been a cryptographic algorithm released with no documentation and statements to "look at the code". It makes me think something is being hidden, or you are dealing with people who under appreciate how dangerous small changes can be.

Edit: For those interested in the story of DES and the S-Box constants that were changed. The moral is changing constants that seem random can in fact change an algorithm's security model.
https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design
 
Last edited: