Bitcoin Forum

Hi all.

I have got a question: Bitcoin uses Elliptic Curves maths for several reasons. But my question is: How does it work in reality?

Of course in every book you find the "normal" addition and point doubling formulas in every book, such as:

http://patentimages.storage.googleapis.com/EP1653428A1/imgf0001.png


This is nice to see, but is is "standard theory", these computations are very expensive; there are much more efficient algorithms. Especially, Renes, Costello and Batina showed "complete addition formulas" (see https://eprint.iacr.org/2015/1060.pdf), where one calculates in the projective plane.

So, does anyone know how ECC is used in Bitcoin? Is there a possibility where I can find the code in the Bitcoin protocol?


I also read that Bitcoin chose Secp256k1 because of efficiency reasons, so I cannot believe that they use "standard" formulas for calculating.

I would give anything to have the ability to run my fingers through secp256k1 (personally) and verify how free it is of any air bubbles

https://en.m.wikipedia.org/wiki/Dual_EC_DRBG

Bitcoin uses ECC in making the public key from your private key.

Private key is just a big number that is kept secret.
Your private key is multiplied with the base point B using ECC math to get the public key.
Privkey*B=Pubkey

This operation is "one way" meaning that it is easy to do, but almost impossible to reverse.

For some curves like secp256k1 there are some more efficient ways to do the addition and multiplication operations. But basically they do the exact same thing as the "standard formulas" only  ~20-30% faster. For example the field size is  2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 which makes it faster to take the mod operation.

The other thing where bitcoin uses ECC is ECDSA https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm (https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm)
It is a public key signing algorithm, which enables you to verify that you own your address without showing anyone your secret private key. You just use your private key to sign the transfer.

It is really just normal elliptic curve crypto. Nothing that special in it or the curve secp256k1.

What prevents you? It is all public knowledge.

There is even a challenge, where you can win hundreds of thousands of dollars if you can break their crypto  :)
https://www.certicom.com/content/dam/certicom/images/pdfs/challenge-2009.pdf (https://www.certicom.com/content/dam/certicom/images/pdfs/challenge-2009.pdf)

Good luck!

just a few more hours brute forcing this https://blockchain.info/address/1oBgkXsgCDMvoWcnrnm1XvYmRAqiuovFd and drinks are on me

what is the bitcoin address ? or is it different type of challenge., i did nt read the pdf yet.

Well at least you are not greedy  ;D

Why not try this address, that has over 1000 000 000$ worth of bitcoins in it:
https://blockchain.info/address/3D2oetdNuZUqQHPJmcMDDHYoqkyNVsFk9r (https://blockchain.info/address/3D2oetdNuZUqQHPJmcMDDHYoqkyNVsFk9r)

isnt that multisig address ?, and its diffucult to calculate multiple private keys rather than just one for simple address public key which starts with 1 ?

No.  It's a P2SH address.

P2SH addresses can have multisig as the script that was used to generate the hash, however there is no requirement that the spender use a multisig script when spending it.


You wouldn't need to calculate multiple private keys.

You would only need to calculate a SINGLE key pair.  Any private/publick key pair at all would work.  You don't even need to find the original key (or keys) that were used when creating the address.

Then, you would build a script that uses the public key that you generated and a nonce value.  After that, all you have to do is brute force the nonce until the hash of the script (public key + nonce) is equal to the hash used for that address.  On average, it should take you approximately 2¹⁵⁹ attempts.

Thanks for your answer. Of course, I know the "sense" about kryptography. These is not new for me. My question is why we got these 20-30% faster computations. You wrote:



So my question is: Why is it ~20-30% faster? What are the more efficient ways to do the addition and multiplication operations?

Of course the result is the same as if I would calculate it with the "standard formulas". The specific curve was chosen because you can do more efficient operations on it. But why is this the case?

from 1 sha256 private key i can create WIF private key and public kay pair which is
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf  1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

how would i get p2sh address for something like that ?

or am i missing again something .,

does the p2sh address's private key also falls in

int range
1 - 115792089237316195423570985008687907852837564279074904382605163141518161494336

if so then how can i generate a pair ?

lets say , so far i have these

input                        : 1
network                      : Bitcoin mainnet
netcode                      : BTC
secret exponent              : 1
 hex                         : 1
wif                          : KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73sVHnoWn
 uncompressed                : 5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf
public pair x                : 55066263022277343669578718895168534326250603453777594175500187360389116729240
public pair y                : 32670510020758816978083085130507043184471273380659243275938904335757337482424
 x as hex                    : 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
 y as hex                    : 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
y parity                     : even
key pair as sec              : 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
 uncompressed                : 0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798\
                                 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
hash160                      : 751e76e8199196d454941c45d1b3a323f1433bd6
 uncompressed                : 91b24bf9f5288532960ac687abb035127b1d28a5
Bitcoin address              : 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH
Bitcoin address uncompressed : 1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm
Bitcoin segwit address       : p2y59b9U5YTUAYEDBr5zwSHFoM8pn3ozAhRD

That is NOT a public key.

That is a bitcoin address.  Specifically, that is an uncompressed key P2PKH bitcoin address.

From that SAME WIF private key, you could also generate a compressed key P2PKH bitcoin address:
1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH

Furthermore, you could create 2¹⁶⁰ different P2SH bitcoin addresses.  Here are a few of them:
38fEX6RbBBMmpu3nbbuULku1xyrrzqqqnE
3Q2iKGxFppUJEZUTUMmahjwUoLNRqDY9o3
3CZj1DTSHD4vhr3zALL3pgs6acyw1deYDt


Build a bitcoin output script.  Hash it.  Concatenate a byte value of 0x05 in front of the hash value. Encode the result with base64check encoding.


Probably.


P2SH means "pay to script hash".  It doesn't necessarily need a key, but is it is safer to build a script that requires a signature (in which case a signature would be required).

Bitcoin Core's ECC code is libsecp256k1, which uses several optimizations to achieve ~5x speedup vs OpenSSL. The code has a lot of comments, eg. this one describing the algorithm exploiting secp256k1's endomorphism: https://github.com/bitcoin-core/secp256k1/blob/0b7024185045a49a1a6a4c5615bf31c94f63d9c4/src/scalar_impl.h#L259

Wow, thank you very much!