Finding base point in elliptical curve = Bitcoin done

[o_e_l_e_o]

I was referring to the human factor in communicating to your cosigners your master public keys.

But you have to do this to set up the multisig wallet in the first place. And once it is set up, you can trivially generate billions of addresses with the same multisig requirements.

Electrum definitely cannot handle thousands of address at once.

Certainly not at the moment, but that is generally because it will start at index 0 and work up, generating and checking for balance thousands of addresses in the process. There is no requirement to do this, though. A small change in the code could mean that you could start generating addresses at index 10,000,000 (or any index you choose) and ignore the first 10 million address entirely. If people were serious about only using addresses once, then you could periodically update your wallet to start generating addresses at a higher index and stop paying attention to address you have already used.

Here is an example in Decimal: https://bitcointalk.org/index.php?topic=5245379.msg55190957#msg55190957

That is an example of turning the private key in to different base representations. It is not an example of elliptic curve multiplication.



Here is another simple resource regarding elliptic curve multiplication: https://learnmeabitcoin.com/beginners/public_keys

[1714834212]

1714834212

[1714834212]

1714834212

[1714834212]

1714834212

[release]

I think a few posts down they explain the point doubling a little. This is still a little confusing. The math used their is what I am trying to get more understanding of.

[release]

 How do you apply this G base point in math to get the public key. I know that G multiplied by private key gets the public key. Could you please give a real example of this in action.

[NotATether]

I was referring to the human factor in communicating to your cosigners your master public keys.

Forgive me because I didn't really do a thorough reading on TapRoot or Schnorr for that matter. With key aggregation, is it still possible to derive the individual public keys used for the transaction using the single public key revealed in such a transaction? My understanding that the individual public keys are not known but only the aggregated key will be within the script.

But again, it does make sense if the aggregated public key can be used to obtain something that can still be used to sign transactions to produce a valid signature. Please CMIIW.

To be honest I have no idea if one of the public keys can be retrieved from an aggregate public key, according to the MuSig whitepaper you need to find the reverse of the formula on page 12.

I don't think that the aggregated public key by itself will be helpful to an adversary though, or an aggregate with too few private keys of the co-signers.

So the question is now, how practical it is for an adversary to compute the list of all bitcoin addresses with a balance [and actually they don't even have to do that, as LoyceV already has such a list] and then given that there are millions of addresses, they still need thousands of compute minutes to crack them all, depending on the average number of transactions in a block.

do you mean trying to guess a private/public key pair and hoping to have gotten one with funds?... if so, why are you referring to number of transactions in a block?

Let's say the adversary wants to steal all the outputs from the transactions on a particular day. They need to know the average number of transactions in a block and that'll give them a rough idea of how many private keys need to be cracked (notwithstanding some transactions have outputs from multiple addresses/private keys), so they can calculate how much computing power they need to crack that many private keys in 10 minutes, the average block creation time.

I'm assuming an attacker is more interested in active addresses than dormant ones, though they will probably get the dormant addresses first because even if you have the private key to someone else's address, if they are moving some coins in an unconfirmed non-RBF transaction then you need to also gain control of a majority of the hashrate, a politically impossible task. Dormant addresses aren't moving anything anywhere.

I cannot understand your attack-scenario:
1) why an attacker should be more interested in active addresses than dormant ones? (I think to early times dormant P2PK with a lot of value)
2) why attacker needs to control hashrate? I suppose the attacked wouldn't have knowledge of being attacked until it sees the malicious transaction in mempool, and if  that transaction is a non-RBF one, it would be included in a block as a normal transaction without possibility to block it (unless the attacked can control the hashrate): so hashrate indipendence seems more a feature than a problem for an attacker who has discovered a someone else private key

To 1), I did admit that they would target dormant transactions first, I was just outlining how an attack against addresses with unconfirmed outputs would work.

To 2), it is only necessary to control hashrate if the attacker also wants to steal the unconfirmed outputs in the address as well. This is so they can block the transaction that's taking the outputs away and create their own transaction (normally this isn't possible with a 51% majority but in this case they also have the private keys) to send the unconfirmed bitcoins to their own address.

Because of this, if all addresses were constantly on the move and that all addresses were made to send their entire balance to some empty addresses, then the threat of widespread cracking of private keys is mitigated.

[LoyceV]

I don't think single-use addresses everywhere is practical because the majority of wallets work with a fixed amount of addresses unless you generate more of them.

All of the wallets I use can generate an unlimited number of addresses. Which wallet doesn't do this yet?
I can think of other reasons why it isn't practical, for instance for recurring payments.

And in certain setups like multisig you cannot conveniently transfer everything to a second multisig address and those are where the majority of riches are stored.

I recently tried this in Electrum, and to my surprise it created a "normal" wallet with many addresses (although starting with a 3 now). So even with multisig it's very easy to generate many different addresses.

So the question is now, how practical it is for an adversary to compute the list of all bitcoin addresses with a balance [and actually they don't even have to do that, as LoyceV already has such a list] and then given that there are millions of addresses, they still need thousands of compute minutes to crack them all, depending on the average number of transactions in a block.

I'm pretty sure some people use this list trying to find a funded private key. Let them! All they'll do is prove to themselves how secure Bitcoin is. As long as it's properly generated, they'll never find a loaded private key this way.

[o_e_l_e_o]

Let's say the adversary wants to steal all the outputs from the transactions on a particular day.

That seems like a incredibly unlikely scenario, when there are over 1 million bitcoin sitting in P2PK addresses which a known public key which the attacker could target with almost no time limit, as opposed to trying to brute force a public key in <10 minutes. Not to mention several million bitcoin sitting in reused addresses with known public keys. And long before all 1 million bitcoin in P2PK addresses are stolen by quantum computing we will have moved to a quantum resistant algorithm that means attacks on unconfirmed transactions are impossible.

To 2), it is only necessary to control hashrate if the attacker also wants to steal the unconfirmed outputs in the address as well.

If it ever did come to this, then presumably the attacker would just target RBF enabled transactions first, since they could do so without 51% of the hashrate.

[pooya87]

your answer seems very well suited for the OP level, but dealing a bit more with details, would it be correct to say that the number of points the generator can create is the cyclic subgroup order, different from curve order by a cofactor?

According to Standards for Efficient Cryptography the relationship between order of the generator point and co-factor and number of points on curve is as follows:
h=#E(F_q)/n
where h is the co-factor, #E(F_q) is the number of points on the curve E over F_q where q is an odd prime and n is the order of the base point G (the order of the sub-group generated by this point).
h for secp256k1 curve is equal to 1.

[release]

The last explanation completely lost me lol can someone explain simply how to use scalar multiplication now that we know the base point.

[pooya87]

The last explanation completely lost me lol can someone explain simply how to use scalar multiplication now that we know the base point.

Basically you add G by itself k times where k is the private key. But since that is not reasonable there are faster algorithms to perform this depending on the curve. A simple one would be "double and add" method where you convert k to its binary form and for each 1 you perform a point addition (add 2 points) then point double and for each 0 you perform a point doubling (adding to self).
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Double-and-add
The point addition and point doubling is also explained in the above wikipedia link.

[release]

Ok thank you. I think I a trying to understand it. So you add g (base point) by itself as many time as the value of the private key. As this isn't feasible their are algorithms to spead up the process?

[pooya87]

Ok thank you. I think I a trying to understand it. So you add g (base point) by itself as many time as the value of the private key. As this isn't feasible their are algorithms to spead up the process?

Correct. k is always usually big so you can't really add G by itself k times, that would take forever. But with these algorithms (like the one above) the number of operations is significantly reduced. For example you have 256 bits and if all were 1 you end up performing 256 point addition and 256 point double which isn't going to take that much compared to adding G to itself ~2²⁵⁶ times.

[release]

Thanks for your help I have a much  better understanding. Still don't understand 2 things:

1) how to multiply 2 hexadecimal strings. I would assume the point G would need to be converted into 1 decimal string? If not please clarify.

2) The amount of times G is added to itself  to get the public key is the amount of private key. In which format is the private key in for this to be possible.

[pooya87]

Thanks for your help I have a much  better understanding. Still don't understand 2 things:

1) how to multiply 2 hexadecimal strings. I would assume the point G would need to be converted into 1 decimal string? If not please clarify.

2) The amount of times G is added to itself  to get the public key is the amount of private key. In which format is the private key in for this to be possible.

1. You can't multiply strings, you perform arithmetic on numbers. So you have to first convert the string representation of the number to an integer then start the "math". In this case you should convert the hexadecimal string to a 256 bit integer using the big endian notation.

2. Same as #1, the private key is also a number with at most 256 bits. Again you convert the string representation (in this case usually base58 instead of base16 since that's the common encoding for WIFs) then use that in the multiplication code.

[o_e_l_e_o]

k is always big so you can't really add G by itself k times, that would take forever.

k isn't necessarily big. k could be 1.

2) The amount of times G is added to itself  to get the public key is the amount of private key. In which format is the private key in for this to be possible.

To expand on pooya87's answer here - it doesn't really matter what format the private key is in. The private key is simply a number between 1 and (just smaller than) 2²⁵⁶. It doesn't matter if you represent that in base10, base16, base58, binary, or whatever. It is the same number.

As this isn't feasible their are algorithms to spead up the process?

Lets say your private key was 50. Rather than calculate G + G + G + ... + G, which would require 49 operations, you can instead do the following:

Code:

G + G = 2G
2G + 2G = 4G
4G + 4G = 8G
8G + 8G = 16G
16G + 16G = 32G
32G + 16G + 2G = 50G

This only requires 7 operations instead of 49.

[release]

Thank you for that. What is the best method/easiest  method of doing this math. To me it seems easier to make both G and k a number. Decimal or binary? This is easier to do for k than it is for G. Probably my final question as I have a much greater understanding now. I still can't visually comprehend and equation where G is know but now a number.

[BASE16]

I gave you a working example in decimal and handling all of the 256 Bit's in the private key.

[release]

I gave you a working example in decimal and handling all of the 256 Bit's in the private key.

Thank you yes as I see that. I will study it a bit more.

[release]

I gave you a working example in decimal and handling all of the 256 Bit's in the private key.

That post was very helpful in showing how to get the correct number to add G to itself I appreciate that thank you.

The big missing link is still G. As G is an X and Y value in hex. How do you get it to 1 number to add it to itself. This is the only bit I am struggling with. I have every piece of the puzzle but one very large piece which is G lol

If G was one hex string I could easily enough convert it to binary and do the same thing as you did in the other post with the private key. As it is 2 coordinates I am struggling.

Please clear this up for me.

Thanks

[release]

GX : 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 -> 55066263022277343669578718895168534326250603453777594175500187360389116729240
GY : 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 ->32670510020758816978083085130507043184471273380659243275938904335757337482424

55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424

G as 2 decimal strings x and y.

[baro77]

The big missing link is still G. As G is an X and Y value in hex. How do you get it to 1 number to add it to itself.

you have the wrong target.. you haven't to convert G to a scalar ("1 number" as you say) to add it to itself. G is a point in a 2D discrete space (the domain of EC) and there is a algorithm (and a nice visual representation of it in the special case in which the space is continuous and not discrete) for the sum of that kind of points.

For sure the links about ECs many of us have provided contain that kind of info.


LATE EDIT

I'm thinking that somewhere you could find about "compression" to represent an EC point as a single value, not two: but don't get confused, it's just a way to use less space to store it but you don't get a proper number/scalar... meaning with "proper" something you can do COMMON algebra with