I assume you're referring to the C implementation of secp256k1 arithmetic, perhaps specfically this pull request? If not, comment and I'll revise my answer.
Why do they write an int128 type in secp256k1, when there's already arbitrary length rational numbers?
Computers generally cannot operate on arbitrary length numbers, let alone rational numbers. Hardware can generally only perform integer arithmetic up to numbers of 32 or 64 bits in size, or approximate arithmetic (with rounding) using floating-point numbers of 32 bits, 64 bits, or 80 bits in size. For cryptographic purposes we need exact arithmetic, so anything with rounding is off limits.
Anything else has to eventually be implemented in software. Many languages provide convenience functions that hide this complexity; for example Python has general-purpose arbitrary length integers and fractions as part of its standard library, but that simply means that the Python interpreter is translating operations on those apparent data types to many small individual instructions that each operate on just 64-bit integers, typically. If you wonder how that works, just imagine how you once learned to do math using numbers longer than 1 digit. Here the "digits" are 64-bit integers on their own, and so a 256-bit integer can be seen as a number consisting of 4 such digits. Many operations (addition, multiplication, ...) on those are very similar to what you'd do for decimal numbers on paper.
libsecp256k1 is not written in Python, but in C, and C doesn't have support for integer types larger than what CPUs support internally, in general. So, it doesn't have the luxury of being able to just use off-the-shelf code for its big integer arithmetic, it has to be implemented by hand. Of course, that is the point: libsecp256k1 is intended to be fast, and by having custom integer code that's designed specifically for this application it can be many times faster than what a Python implementation could ever hope to achieve.
Furthermore, it's necessary. Arbitrary-length integer types, even if they were available, are generally not appropriate for implementing cryptography. We aim to design code that runs in constant time, so that an attacker cannot learn anything about our private key by observing how long operations on it take. Variable-length types can obviously not be constant-time, as operating on them depends on how long the number is.
Is that fancy? Boredom?
The point of this pull request is testing, platform support, and verifiability.
Let me explain. libsecp256k1, in order to implement elliptic curve operations, needs to reason about fairly large integers (256 bits most of the time, occasionally up to 512 bits), often modulo some large (256-bit) prime.
To implement arithmetic with 256 bits long numbers, the operations are generally broken up into smaller bits as I explained above. But how small depends on what hardware you have. Modern x86_64 CPUs like those by Intel and AMD can natively do 64-bit arithmetic, including multiplication of two 64-bit numbers to obtain a 128-bit number (which is then stored in two 64-bit registers). This is very useful, but not possible everywhere. Most Raspberry Pi systems run in 32-bit mode, where no 64-bit integer type is available in hardware.
To deal with that, libsecp256k1 has multiple versions of its specialized 256-bit arithmetic code. Slightly simplified, it has one version for 32-bit systems and one for 64-bit systems. The first one uses 8 to 10 "digits" of 32 bits to represent 256-bit numbers, while the second one uses 4 to 5 pieces of 64 bits instead.
All of these of course have tests, but as this is a key cryptographic codebase, and bugs in it could very directly affect the security of many pieces of Bitcoin software that use it, including Bitcoin Core, more testing/verification/analysis is always welcome. Russell O'Connor has been contributing to this effort, with among other things, formal verification proofs for correctness. However, the system he is using does not support the 64x64->128 bit multiplication. We could of course only test the 32-bit implementation of the 256-bit integer logic, but we like to go a step further.
This is where the 128 bit integer type comes in. It's just a type implemented in libsecp256k1 itself. On 64-bit systems it would immediately defer to the actual 64x64->128 logic available in C. On other systems, it would emulate it by splitting things into operations on 32-bit integers. This means that the 256-bit implementation can then use our new 128-bit type (rather than use the C types directly), and this will work on both 32-bit and 64-bit systems. And more importantly, it will work in the formal verification tools that do not support the 128-bit type natively.
There is another advantage, though that's not yet implemented in this PR. That is the fact that MSVC (Microsoft Visual C) does support 128-bit operations, but doesn't do that through a 128-bit type. Instead it has special functions that do these using just 64 bit integers. So by introducing this intermediary 128-bit type, and then adding an instantiation for it for MSVC, we could automatically make our 256-bit logic work for MSVC without incurring the performance penalty of using 32-bit code only. If we wanted to achieve something similar without introducing a 128-bit wrapper type, we'd need to create a new implementation of the whole 256-bit integer logic just for MSVC, rather than just an implementation for the 128-bit wrapper. This may sound trivial, but it's several hundred lines of very tricky code, and code like this has actually had bugs in other libraries (including OpenSSL).
Isn't secp256k1 just for key pairs, and key pair arithmetic is seldom used
Not just key pairs; libsecp256k1 provides implementations for all kinds of operations that involve private keys, public keys, or both. That includes key generation (computing public key given private key), key derivation (e.g. BIP32), as well as signing and verifying digital signatures (ECDSA, since recently also BIP340 Schnorr).
In particular, signature validation is a very significant portion of time nodes spend on synchronizing and processing blocks and transactions. libsecp256k1 is primarily aimed at being efficient (in addition to being safe and well-tested) specifically because signature operations are such a bottleneck in Bitcoin.
You can get bonuses upto $100 FREE BONUS when you:
💰 Install these recommended apps:
💲 SocialGood - 100% Crypto Back on Everyday Shopping
💲 xPortal - The DeFi For The Next Billion
💲 CryptoTab Browser - Lightweight, fast, and ready to mine!
💰 Register on these recommended exchanges:
🟡 Binance🟡 Bitfinex🟡 Bitmart🟡 Bittrex🟡 Bitget
🟡 CoinEx🟡 Crypto.com🟡 Gate.io🟡 Huobi🟡 Kucoin.
Comments