Bitcoin Forum
April 27, 2024, 05:42:40 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: [validation performance] ECDSA GLV endomorphism patent expires Sep 25th 2020  (Read 218 times)
Carlton Banks (OP)
Legendary
*
Offline Offline

Activity: 3430
Merit: 3071



View Profile
September 18, 2020, 04:12:04 PM
Last edit: September 18, 2020, 10:53:14 PM by gmaxwell
Merited by Welsh (5), JuleAdka (2), vapourminer (1), JayJuanGee (1), pooya87 (1), HeRetiK (1), ABCbits (1), jackg (1), NotATether (1)
 #1

from http://gnusha.org/bitcoin-core-dev/2020-09-17.log

Quote

2:06 < sipa> hi!
12:06 < sipa> this is mostly a short announcement so it doesn't cause any surprise
12:07 < sipa> libsecp256k1 started out as an experiment to see how much secp256k1 EC operations could be made by using the GLV endomorphism optimization, which it was specifically designed to support, but not actually implemented anywhere
12:07 < luke-jr> vasild: that's kinda the point; it reduces to one config format
12:07 < fjahr> hi
12:07 < sipa> as it turned out that there is some risk it is encumbered by a patent, the GLV optimization was made optional, and defaults to off (and has been off in every bitcoin core release)
12:08 < sipa> it looks like that patent is expiring on september 25th, and blockstream had a patent attorney verify that (i'm happy to share their findings, if anyone cares)
12:08 < wumpus> yay!
12:08 < cfields> wooo!
12:08 < luke-jr> sipa: how sure can we be that it can't break consensus?
12:08 < sipa> so the plan is to switch it to default on after that date, or even rip out the non-GLV code
12:08 < sipa> luke-jr: good question
12:09 < luke-jr> is it provable? :x
12:09 < sipa> libsecp256k1' CI has always tested with both endomorphism enabled and disabled
12:09 < sipa> including our exhaustive tests, which are probably as close to a mathemetical proof we can get for real software - at least for some aspects
12:10 < sipa> fwiw, that's a test where the library is compiled with a slightly different curve equation that makes it trivially insecure, and only leaves 12 valid private/public keys
12:10 < sipa> and in that mode, we can test literally every combination of signature/pubkey/private key
12:11 < wumpus> nice
12:11 < sipa> so i think that given that, it shouldn't be any more invasive than regular code changes to libsecp256k1
12:11 < luke-jr> has it been proven on a mathematical level? (not saying it's a problem if not, just asking)
12:12 < sipa> luke-jr: for some parts of the code we have actual proofs (some hand-written, some automatic); though admittedly not the part touched by the endomorphism
12:12 < wumpus> I think he means in mathetmatical theory, not so much the specific code
12:12 < luke-jr> right
12:13 < sipa> wumpus: for the group arithmetic, there is a transliteration of the C code to python, which is then symbolically executed and can be automatically proven correct
12:13 -!- guest534543 [~mix@193.9.112.252] has joined #bitcoin-core-dev
12:13 < provoostenator> Very cool, somewhat scary, but how much of a speedup is this?
12:13 < sipa> the conversion from C to Python (or its semantics) of course aren't, but the algorithms at a slightly higher level are proven
12:13 < wumpus> sipa: that's a very interesting approach
12:13 < sipa> provoostenator: 27% for ecdsa verification
12:13 < provoostenator> Ok, that's worth some code review time alright.
12:13 < wumpus> very hard to say no to that Smiley
12:14 < sipa> well
12:14 < sipa> arguably, libsecp256k1 originally _only_ had the GLV mode
12:14 -!- davec [~davec@cpe-24-243-240-159.hot.res.rr.com] has quit [Ping timeout: 272 seconds]
12:14 < sipa> the mode where GLV was disabled (which is now default) was added later
12:14 < wumpus> yes it was added out of patent concerns
12:15 < sipa> yes
12:15 < sipa> but all changes since 2013 have always kept both GLV and non-GLV working, and tested
12:15 < meshcollider> Interesting, I didn't know that
12:15 < luke-jr> was the GLV mode ever released in Core?
12:15 < wumpus> no
12:15 < sipa> luke-jr: it's a compile time option, and it was never enabled in (default) builds of core
12:16 < sipa> you could always enable it yourself with --enable-endomorphism
12:16 -!- davec [~davec@cpe-24-243-240-159.hot.res.rr.com] has joined #bitcoin-core-dev
12:16 < luke-jr> right, not sure how many people actually did that tho :p
12:16 < wumpus> some people did it for benchmarking at times
12:16 -!- Kiminuo [~mix@141.98.103.116] has quit [Ping timeout: 260 seconds]
12:16 < wumpus> apart from that, dunno
12:16 < sipa> luke-jr: i assume nobody
12:16 < vasild> If there are concernts, what about doing all calculus in both and comparing they produce the same result?
12:17 < luke-jr> we do have a USE flag for it in Gentoo, but no metrics on usage

the above sounds rather promising: IBD (and validation in general) could see significant performance gains if this (already well tested for several years) feature is enabled in the distirbuted Bitcoin binaries/packages.

And interestingly, it appears we can compile all previous releases of Bitcoin using libsecp256k1 (back to 2013, I think) with this --enable-endomorphism option (possibly it needs enabling in the configure script for libsecp256k1 only, didn't check that yet). The Gentoo package for Bitcoin has (possibly always?) allowed it as an option, so maybe some people have been testing this without being aware they are breaking the patent restrictions.

my initial reaction was the same as someone later jokes in the chat:

1. cryptography patent
2. patent expires, and so people actually start using formerly patented code
3. (no) profit


Vires in numeris
1714239760
Hero Member
*
Offline Offline

Posts: 1714239760

View Profile Personal Message (Offline)

Ignore
1714239760
Reply with quote  #2

1714239760
Report to moderator
1714239760
Hero Member
*
Offline Offline

Posts: 1714239760

View Profile Personal Message (Offline)

Ignore
1714239760
Reply with quote  #2

1714239760
Report to moderator
1714239760
Hero Member
*
Offline Offline

Posts: 1714239760

View Profile Personal Message (Offline)

Ignore
1714239760
Reply with quote  #2

1714239760
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1714239760
Hero Member
*
Offline Offline

Posts: 1714239760

View Profile Personal Message (Offline)

Ignore
1714239760
Reply with quote  #2

1714239760
Report to moderator
1714239760
Hero Member
*
Offline Offline

Posts: 1714239760

View Profile Personal Message (Offline)

Ignore
1714239760
Reply with quote  #2

1714239760
Report to moderator
jackg
Copper Member
Legendary
*
Offline Offline

Activity: 2856
Merit: 3071


https://bit.ly/387FXHi lightning theory


View Profile
September 18, 2020, 10:06:14 PM
 #2

Isn't it still the core devs that broke the patent by allowing that option? I don't think someone enabling that in a private setting is breaking IP law imo.

I guess this is the reason a lot of code is copied from similar places which hopefully doesn't need to happen now if people can start developing their own versions of the protocol (legally). And is the few % (almost 25) gain of efficiency linked to this too or was that a separate topic?. Not that I'd support migrating to python but if the library is in C it might be an interesting take.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8382



View Profile WWW
September 18, 2020, 10:59:49 PM
Merited by Welsh (3), JayJuanGee (1)
 #3

Isn't it still the core devs that broke the patent by allowing that option?
It wasn't an option in Bitcoin, other than you could go modify the software to enable it-- which you could always do even if we'd never heard of the optimization. There is no case law that supports a conclusion that implementing something to test it in a non-commercial non-production scholarly manner is a patent violation: considering that the unequivocal case law in the US on the distribution of source code being a first amendment protected right, any attempt to block the scholarly evaluation of patented algorithms in this manner would be on pretty shaky constitutional grounds at best.  Plus how could you even decide if you wanted to implement something without actually trying it?

Quote
I guess this is the reason a lot of code is copied from similar places which hopefully doesn't need to happen now if people can start developing their own versions of the protocol
I can't make any sense of this statement.

Quote
And is the few % (almost 25) gain of efficiency linked to this too or was that a separate topic?. Not that I'd support migrating to python but if the library is in C it might be an interesting take.
This doesn't have anything to do with python. It's a 27% speedup.
jackg
Copper Member
Legendary
*
Offline Offline

Activity: 2856
Merit: 3071


https://bit.ly/387FXHi lightning theory


View Profile
September 18, 2020, 11:10:22 PM
 #4

It wasn't an option in Bitcoin, other than you could go modify the software to enable it-- which you could always do even if we'd never heard of the optimization. There is no case law that supports a conclusion that implementing something to test it in a non-commercial non-production scholarly manner is a patent violation: considering that the unequivocal case law in the US on the distribution of source code being a first amendment protected right, any attempt to block the scholarly evaluation of patented algorithms in this manner would be on pretty shaky constitutional grounds at best.  Plus how could you even decide if you wanted to implement something without actually trying it?


Ahh yeah the python thing was for testing whether the algorithm could be broken readingnbacknthroughbitnthere we're two conversations at once..

I thought that was the endomorphism command that disabled the flag and increased efficiently.


Quote

Quote
I guess this is the reason a lot of code is copied from similar places which hopefully doesn't need to happen now if people can start developing their own versions of the protocol
I can't make any sense of this statement.

I seem to remember a dev on here saying some of the original core algorithms for the ECC were from an open source library (I can't remember the name as I've used too many encryption libraries now)... So I assumed functioning code was just moved as per the mantra of not reinventing the wheel.
pooya87
Legendary
*
Offline Offline

Activity: 3430
Merit: 10505



View Profile
September 19, 2020, 03:52:15 AM
Merited by vapourminer (1)
 #5

I seem to remember a dev on here saying some of the original core algorithms for the ECC were from an open source library (I can't remember the name as I've used too many encryption libraries now)... So I assumed functioning code was just moved as per the mantra of not reinventing the wheel.

i believe you are referring to usage of OpenSSL library in early versions of bitcoin core by Satoshi. i wouldn't call replacing that with a self written code "reinventing the wheel". in fact using OpenSSL is the source of some of the mess we have in bitcoin's code for example involving signatures and their encoding, the implementation both prevents bugs coming from that library and improves speed.

.
.BLACKJACK ♠ FUN.
█████████
██████████████
████████████
█████████████████
████████████████▄▄
░█████████████▀░▀▀
██████████████████
░██████████████
████████████████
░██████████████
████████████
███████████████░██
██████████
CRYPTO CASINO &
SPORTS BETTING
▄▄███████▄▄
▄███████████████▄
███████████████████
█████████████████████
███████████████████████
█████████████████████████
█████████████████████████
█████████████████████████
███████████████████████
█████████████████████
███████████████████
▀███████████████▀
█████████
.
Carlton Banks (OP)
Legendary
*
Offline Offline

Activity: 3430
Merit: 3071



View Profile
September 19, 2020, 06:47:57 AM
Merited by vapourminer (1)
 #6

i believe you are referring to usage of OpenSSL library in early versions of bitcoin core by Satoshi. i wouldn't call replacing that with a self written code "reinventing the wheel". in fact using OpenSSL is the source of some of the mess we have in bitcoin's code for example involving signatures and their encoding, the implementation both prevents bugs coming from that library and improves speed.

right. From what I have read, using the OpenSSL library is a risky proposition for software that actually requires a high standard of cryptographic security, as the code is incredibly difficult to review. I am a little surprised that less was made of the multiple serious vulnerabilities found in OpenSSL throughout the mid 2010's (I've replaced it with LibreSSL where I can easily do so)

I'm fairly well convinced these days that where cryptography is well specified/defined, and the new code has good reviewers, that re-implementing some algorithms to replace known-bad implementations is better than using those known-bad implementations.

Vires in numeris
pooya87
Legendary
*
Offline Offline

Activity: 3430
Merit: 10505



View Profile
September 19, 2020, 08:24:47 AM
 #7

right. From what I have read, using the OpenSSL library is a risky proposition for software that actually requires a high standard of cryptographic security, as the code is incredibly difficult to review. I am a little surprised that less was made of the multiple serious vulnerabilities found in OpenSSL throughout the mid 2010's (I've replaced it with LibreSSL where I can easily do so)

I'm fairly well convinced these days that where cryptography is well specified/defined, and the new code has good reviewers, that re-implementing some algorithms to replace known-bad implementations is better than using those known-bad implementations.

i wouldn't call it "bad implementation" because there is nothing wrong or bad about OpenSSL. it is similarly open source and highly reviewed and tested.

the only problem is that it is not suitable for a distributed consensus based system like bitcoin. for example take the DER encoding issue that i pointed out above in cases when this library is used like with your browser reading signature provided by a website the browser doesn't care if that website is encoding it in a weird way (lose encoding instead of strict) it doesn't even matter if that website encoded each signature differently.
but in bitcoin, a lose definition of DER encoding causes malleability and potentially could cause a lot of issues for users receiving funds or even break clients down.

.
.BLACKJACK ♠ FUN.
█████████
██████████████
████████████
█████████████████
████████████████▄▄
░█████████████▀░▀▀
██████████████████
░██████████████
████████████████
░██████████████
████████████
███████████████░██
██████████
CRYPTO CASINO &
SPORTS BETTING
▄▄███████▄▄
▄███████████████▄
███████████████████
█████████████████████
███████████████████████
█████████████████████████
█████████████████████████
█████████████████████████
███████████████████████
█████████████████████
███████████████████
▀███████████████▀
█████████
.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8382



View Profile WWW
September 19, 2020, 12:31:06 PM
Merited by Welsh (2), vapourminer (1)
 #8

i wouldn't call it "bad implementation" because there is nothing wrong or bad about OpenSSL.
Even putting aside suitability-to-application, OpenSSL's implementation of secp256k1 has significant secret dependant timing-- so it's not secure if an attacker can measure the time it takes you to construct signatures (potentially even over the internet).  I think that is pretty unfortunate!

This isn't the case for all the curves OpenSSL implements-- e.g. Their P224 and P256 at least attempts (I haven't personally reviewed them) to be constant time.  So you have yet another problem with big grab-bag systems like OpenSSL: the provided security properties are extremely uneven,  and you might think it is secure on the basis of someone's comments with respect to some configuration but find out the hard way that your own configuration is not sufficiently secure.

Then again, *other* than libsecp256k1 ... other implementations of secp256k1 out there, even ones claiming to be "high security" are not particularly free of secret leaking timing side-channels either.  Nor do they usually have tests beyond a couple static test vectors, etc.   From my perspective almost everything else is a joke, but no one cares because the limiting factor in user security is usually something else.  Attackers need not worry about triggering targets to sign a bunch of things on command and then performing complex mathematics to recover the private keys-- they can just spoof an email as the target company's CEO and tell someone to send over their wallet.dat and all too often they will.
Carlton Banks (OP)
Legendary
*
Offline Offline

Activity: 3430
Merit: 3071



View Profile
September 22, 2020, 11:01:36 AM
Merited by vapourminer (1)
 #9

I am a little surprised that less was made of the multiple serious vulnerabilities found in OpenSSL throughout the mid 2010's (I've replaced it with LibreSSL where I can easily do so)

I'm fairly well convinced these days that where cryptography is well specified/defined, and the new code has good reviewers, that re-implementing some algorithms to replace known-bad implementations is better than using those known-bad implementations.

i wouldn't call it "bad implementation" because there is nothing wrong or bad about OpenSSL. it is similarly open source and highly reviewed and tested.

review of the OpenSSL codebase hasn't always been easy (apparently, I have not tried to read the code myself). OpenSSL is used by various industries who require that it can be compiled for use on their old hardware architectures (possibly using old operating systems in some cases). OpenSSL cater to those clients, and doing this makes the code harder to reason about. Supposedly. OpenSSL has had a newer version number (1.1.x) introduced since the critical bugs that were disclosed in the mid-2010's, perhaps the codebase has been restructured to improve readability since then.

I don't see much point in open source code that is unreadable by anyone except those who wrote it, it's very similar to the proposition of proprietary binaries to me

Meanwhile, there are several SSL implementations available, some more widely used and tested than others (and each targeting various different uses). It's not the easiest change to make to a system, it's really best done to a minimal OS installation before any other software is installed (as so much software depends on SSL).

Vires in numeris
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8382



View Profile WWW
September 23, 2020, 05:06:42 AM
Merited by Welsh (10), aliashraf (2), vapourminer (1), ABCbits (1)
 #10

review of the OpenSSL codebase hasn't always been easy (apparently, I have not tried to read the code myself).
Depends on the part, the ASN1 parser stuff is and was extremely difficult to review. The basic cryptographic code OTOH is mostly fine, readability wise-- though there are a lot of different platform specific optimizations and different cryptosystems in there, so a lot of work to review.

A lot of the "readability" fixes that they did do were just running the entirely codebase through an autoformatter. I think this was a complete and utter disaster for reviewability-- it caused them to issue a 400k line diff (which they also mixed in with security changes).  Presumably they were also hiding undisclosed fixes in that massive change, but-- perhaps they also hid new vulnerabilities.  It's completely impractical to review that, so only history will tell.

If your "readability" problem was one that could be solved by mechanically adjusting formatting, you could have done that locally without any fear that something naughty was slipped in.

Quote
OpenSSL is used by various industries who require that it can be compiled for use on their old hardware architectures (possibly using old operating systems in some cases).

Libsecp256k1 should be roughly equally portable (in fact, in some respects it is more portable just because it's smaller and does less-- so any adjustments needed for a weird platform would be smaller).  I test libsecp256k1 back to GCC 2.95 (from 2001, which is extremely old by modern standards-- though OpenSSL originally worked with older toolchains I have no idea if they continue to test with anything that old).  Libsecp256k1's tests also pass when compiled to a 16-bit DOS executable (though a couple of changes are needed to the tests to keep them from exhausting the stacks).

Quote
I don't see much point in open source code that is unreadable by anyone except those who wrote it, it's very similar to the proposition of proprietary binaries to me
Well there are orders of magnitude, even the worst parts of the OpenSSL code are much more reviewable than a binary.

Quote
Meanwhile, there are several SSL implementations available, some more widely used and tested than others (and each targeting various different uses). It's not the easiest change to make to a system, it's really best done to a minimal OS installation before any other software is installed (as so much software depends on SSL).

It's always good to be a bit wary when someone is pitching that their reimplementation solves all the problems unsolved by the Standard Solution-- often it means that the reimplementation didn't understand the entire problem domain (or they did and are intentionally ignoring a big chunk).

Some of OpenSSL's awfulness is self-inflicted legacy baggage, but a good chunk is simply because of what it's being asked to do. Some of OpenSSL's flaws also appear to stem from interface decisions that cause callers to introduce flaws, -- and the drop in OpenSSL alternatives preserve those interfaces for compatibility.

To the extent that some of these alternatives have dropped support for older standards or weird platforms they might also have improved on the "being asked to do" front, ... if your usage is okay with those limitations.  As far as legacy baggage goes-- we remain in a state where virtually none of the folklore advice about code-smell has been backed by rigorous scientific study.  Programmers are often _extremely_ opinionated about "bad code" yet there are relatively few examples of widely code style differences which are uncontroversially and unambiguous causes of defect-- often complaints about "bad code" really just means "not my preferred style".  In so far as an alternative is only an improvement with respect to some person(s) subjective impression of "bad code" I am extremely wary,  the hardening that software gets from widespread use is commonly and easily undervalued-- if I had to pick between a widely deployed solutions with well understood weaknesses vs something new which is supposed to be subjectively better, I'd pick the former every time.  It seems the market agrees: OpenSSL is extremely widely used compared to some of the new alternatives.

For Libsecp256k1 in Bitcoin we switched not because subjective "code smell" sorts of reasons but because of more objective criteria like:

* Designed for consensus consistency: OpenSSL was provably not consensus consistent and was continuing to actively make changes which damaged consistency with little to no consideration of this class of concern or even adequate disclosure of the changes.

* Free of timing sidechannel secret leaks for secp256k1: OpenSSL's code for this curve wasn't even trying to be constant time. Ours was.

* Formal validation: Libsecp256k1 is partially formally validated, none of the parts of OpenSSL we were using are, to the best of my knowledge.

* Speed: libsecp256k1 was 5-7x faster than OpenSSL.

* Extensive testing: libsecp256k1 had many kinds of tests openssl didn't have at all, and has more now-- tests in libsecp256k1 found serious bugs in openssl, etc.

And sure I think the libsecp256k1 is a lot more readable and maintainable than the relevant code in openssl, and I hope those differences also help lower defect rates... but its all the items above that made it the right thing for Bitcoin to use vs something with a much longer track record, and not some formatting stuff which is inherently pretty subjective and may not actually make the software better.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!