re-use of addresses

[chriswilmer]

A bitcoin private key, d is (almost) any 256-bit integer (78 digit number).  To find the associated public key, Q, you need to multiply your private key by a special "number" G called the elliptic curve base point:

     Q = d x G

If you know d (private key) and G, it is fairly straight forward to calculate Q (public key).  Now, if G and Q were normal numbers, we could re-arrange this equation to solve for the private key by division:

     d = Q / G

But G and Q are not normal numbers; they are actually the {x, y} coordinates of points on a special type of curve called an elliptic curve.  Points on elliptic curves can be multiplied by normal numbers (like a private key), but it turns out that it is extremely difficult to "divide" two points on an elliptic curve to get a normal number (to solve for the private key, d).  I use quotes around "divide" because we actually call this problem the "elliptic curve discrete logarithm problem" (ECDLP) and not the division problem.

Now the reason the security is 128 bits when the private key is 256 bits is because you don't need to brute force every possible key.  You just need to find the value of d that when multiplied by G gives you Q.  There is a bit of a pattern that you can exploit, so to speak.  The fastest known algorithms that allow one to solve the ECDLP (baby-step giant-step, Pollard's rho, etc.), need O(√n) steps.  Since n = 2^256, √2^256 = 2^128.  So using the most efficient algorithm to solve for d if Q and G are known, it should "only" take around 2^128 steps, as opposed to the 2^256 steps it would take to try every possible key by brute force.

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Key_sizes

Isn't hash function SHA-256 plugged in there somewhere?  where does that fit into this?  And even if you knew "G", wouldn't you still have the hash to contend with?  

In the post you quoted, I was trying to explain elliptic curve multiplication and the discrete logarithm problem in a very simple way.  Elliptic curve multiplication is an example of a trapdoor function that is easy to compute in one direction (multiplying the private key (integer) by the elliptic curve base point to get the public key) but infeasible to compute in reverse (finding the private key given the public key and base point).  

When you produce an ECDSA signature for a bitcoin transaction, you sign a 256-bit hash, e, of the message (transaction), m, and get a pair of numbers {r, s}.  But in order for anyone to verify that the signature is correct, you must also tell them your public key Q in addition to r and s (and they must know the message, m, that you signed).

Everyone already knows G because it's a property of the secp256k1 curve.  The act of signing and broadcasting a transaction makes your public key Q known because you need to provide this in order for the network to verify your signature.  Someone could "steal" your funds remaining in the associated bitcoin address if they can solve the problem:

        Q = d x G

for an unknown d.  But like I explained earlier, it is not presently feasible to find d as the fastest known algorithm still takes 2^128 steps.  If the public key is not known, on the other hand, then someone could "steal" your funds if they try on average 2^160 random 256-bit integers until they find a ripeMD160 collision with your bitcoin address.   I say "steal" because 2^128 and 2^160 are really really big numbers and it's not actually feasible to perform a computation with such a huge number of steps.  


I've seen you express interest in elliptic curves in a few threads now.  How I learned about them was reading the wikipedia articles (many, many times), reviewing the comments by DeathAndTaxes, DannyHamilton, GMaxwell and a few others regarding these curves.  But what really made it sink in for me was writing code from scratch to sign and verify ECDSA.  I did this in Mathematica so that I didn't have to worry about integer size or modulus operations.  After I did this, l had new respect for the weird properties of elliptic curves and prime numbers too--it's really interesting stuff.  

Hah, you too! I have nothing to contribute other than to say that I also wrote my own ECDSA program in Mathematica. Doing this also gave me respect for the serious speed efficiencies that "real" implementations must incorporate (I was using a prime field of only 67 elements).

[1714624889]

1714624889

[1714624889]

1714624889

[1714624889]

1714624889

[1714624889]

1714624889

[1714624889]

1714624889

[DannyHamilton]

you must also tell them your public key Q in addition to r and s (and they must know the message, m, that you signed).

Everyone already knows G because it's a property of the secp256k1 curve.  The act of signing and broadcasting a transaction makes your public key Q known because you need to provide this in order for the network to verify your signature.

Actually, the Bitcoin protocol requires you to supply your public key Q, because that's the way Satoshi wrote the program. We all now have to live with it.

If Satoshi hadn't written it that way, it wouldn't be necessary to supply your public key Q to verify the signature.  Given the signature and the message, it's possible to compute the public key. Then by hashing that computed public key, it is possible to verify that the computed public key matches the bitcoin address from the output being spent.

[Stephen Gornick]

But this view is not universal, apparently:

Reusing addresses is therefore the preferred method of maintaining the privacy of your sources.

- http://bitcoinpete.com/2014/05/05/on-reusing-bitcoin-addresses

I still don't get how a dozen people sending to a single address of mine is protecting their privacy better than if I provide one address per transaction.  And I'm more interested in MY privacy than theirs, anyway.  If they want privacy, that's their job to mix or obfuscate -- not mine.

And then further that post reads ...

And perhaps the ultimate best practise tip, a heuristic for the intelligent use of Bitcoin:

Take whatever the Core Devs say and do the exact opposite.

I don't even.

[Valle]

But this view is not universal, apparently:

Reusing addresses is therefore the preferred method of maintaining the privacy of your sources.

- http://bitcoinpete.com/2014/05/05/on-reusing-bitcoin-addresses

I still don't get how a dozen people sending to a single address of mine is protecting their privacy better than if I provide one address per transaction.  And I'm more interested in MY privacy than theirs, anyway.  If they want privacy, that's their job to mix or obfuscate -- not mine.

That's quite simple. Creating a very secure paper wallet requires some efforts. Dealing with multiple paper wallets requires even more efforts. When you deal with multiple paper wallets there is always a risk that you loose a paper wallet and that means that a single paper wallet might be more safe than many wallets.

[jonald_fyookball]

I still don't get how a dozen people sending to a single address of mine is protecting their privacy better than if I provide one address per transaction.  

It's not, IMO.

If a large number of people are all sending to a single address, that address
becomes conspicuous.  So you are losing a layer of obfuscation there.
In other words, if you were looking at someone's wallet or transactions,
you would more easily be able to spot a well known address, as
well as determine what that address is for.

[Peter R]

you must also tell them your public key Q in addition to r and s (and they must know the message, m, that you signed).

Everyone already knows G because it's a property of the secp256k1 curve.  The act of signing and broadcasting a transaction makes your public key Q known because you need to provide this in order for the network to verify your signature.

Actually, the Bitcoin protocol requires you to supply your public key Q, because that's the way Satoshi wrote the program. We all now have to live with it.

If Satoshi hadn't written it that way, it wouldn't be necessary to supply your public key Q to verify the signature.  Given the signature and the message, it's possible to compute the public key. Then by hashing that computed public key, it is possible to verify that the computed public key matches the bitcoin address from the output being spent.

Thanks Danny, your comment has me quite interested.  The algorithm I coded in Mathematica (for learning purposes) to verify ECDSA is the one from the Wikipedia article here.  This algorithm assumes knowledge of the public key Q (in addition to the signature pair {r, s}) in Step 6:

6.  Calculate the curve point {x, y} = u1 x G + u2 x Q

In fact, the first thing the wiki says about ECDSA verification is "for Bob to authenticate Alice's signature, he must have a copy of her public-key curve point Q."

Can you point me to an algorithm that uses only the signature pair {r, s} and the message, m, to calculate Q?  I can see that if you could calculate Q from {r, s} and m, that you could then hash Q to a bitcoin address and verify this way.  That would have been pretty slick 

[DeathAndTaxes]

Peter,

Which language?  It is in the bitcoin-core (QT) sourecode.  Probably in the bitcoin libs for just about any language now.  In general the concept is called "ECDSA Public Key Recovery".  A very cool property of ECC that doesn't existing in all public key cryptography.  In Bitcoin it is only used in message (not transaction) signing.

Here is the standard.  Key Recovery starts on page 47.

http://www.secg.org/download/aid-780/sec1-v2.pdf

There is one thing i am unsure about.  The PubKey (in the absence of additional information) has to be found by trial and error (generate possible PubKey from sign, verify sig w/ possible key.  if valid then you have found key, if not try next possible key, if no possible key validates sig then sig is invalid). 

When locating the proper key one iterates from i=0 to i=h (domain parameter).  For secp256k1 h = 1 so the only possible i values should be 0 or 1.  Most code I have seen iterates from 0 to 3 I wonder if that is just an oversight.  If I am right then there will never be a recovery using an i of 2 or 3.

For Bitcoin messages the i value is encoded in the message header so only one recovery and verification needs to be done.  It is encoded as a byte as follows.
0x1B = Uncompressed PubKey, First Even Key (i = 0)
0x1C = Uncompressed PubKey, First Odd Key (i = 1)
0x1D = Uncompressed PubKey, Second Even Key (i = 2)  <- impossible for secp256k1?
0x1E = Uncompressed PubKey, Second Odd Key (i = 3) <- impossible for secp256k1?
0x1F = Compressed PubKey, First Even Key (i = 0)
0x20 = Compressed PubKey, First Odd Key (i = 1)
0x21 = Compressed PubKey, Second Even Key (i = 2) <- impossible for secp256k1?
0x22 = Compressed PubKey, Second Odd Key (i = 3) <- impossible for secp256k1?

[Peter R]

Peter,

Which language?  It is in the bitcoin-core (QT) sourecode.  Probably in the bitcoin libs for just about any language now.  In general the concept is called "ECDSA Public Key Recovery".  A very cool property of ECC that doesn't existing in all public key cryptography.  In Bitcoin it is only used in message (not transaction) signing.

Thanks DeathAndTaxes.  I was interested in only the math itself and just needed the key words "ECDSA Public Key Recovery" to find it.  For interested readers, the algorithm is on page 47 of this PDF: "Given an ECDSA signature (r, s) and EC domain parameters, it is generally possible to determine the public key Q, at least to within a small number of choices."

Very cool indeed.  Perhaps Satoshi didn't know this was possible, or perhaps he was worried about the possibility of more than one choice for Q given the signature (r, s) and the additional logic needed to deal with it.  


EDIT: I see Gavin supported Satoshi's decision to include the public key: https://bitcointalk.org/index.php?topic=6430.msg94290#msg94290

[Brangdon]

I still don't get how a dozen people sending to a single address of mine is protecting their privacy better than if I provide one address per transaction.

Well, suppose you are collecting donations from co-workers for your boss's birthday present. If you give them all the same address, you see the incoming transactions and the total balance, but you won't know who paid what, so they have some anonymity. If you give a different address to each co-worker, and remember who got which address, then you can tie the amount of each donation to the person who sent it. Then you can inform your boss about who didn't pay for her present. Clearly, your co-workers' anonymity has been compromised in a way that affects (some of) them adversely.

The above makes sense to me, but I can't relate it to Peter Dushenski's article, so he may have been saying something different. Quite a lot of that article makes no sense to me.

And I'm more interested in MY privacy than theirs, anyway.

That's your choice. In the above scenario, their loss of privacy is to your benefit. If you were running something like Wikileaks, you might get more donations if you did respect your benefactor's privacy.

If they want privacy, that's their job to mix or obfuscate -- not mine.

There's not a lot they can do in the above scenario.

[DannyHamilton]

I still don't get how a dozen people sending to a single address of mine is protecting their privacy better than if I provide one address per transaction.

Well, suppose you are collecting donations from co-workers for your boss's birthday present. If you give them all the same address, you see the incoming transactions and the total balance, but you won't know who paid what, so they have some anonymity. If you give a different address to each co-worker, and remember who got which address, then you can tie the amount of each donation to the person who sent it. Then you can inform your boss about who didn't pay for her present. Clearly, your co-workers' anonymity has been compromised in a way that affects (some of) them adversely.

By providing a single address, everyone can see the average amount donated per person, and know how many people didn't donate.  Using additional information, it might become possible to make educated guesses about who gave how much.  Now, not only you and the boss, but EVERYONE has information about the donations.

Better would be to print out enough donation addresses so there is one for each employee.  Then cut up the paper so that there is only one address per piece.  Turn then face down so nobody knows what address anybody else gets, and let everyone choose randomly.

Now nobody other than the recipient knows exactly how much each person donated.

Of course, privacy comes at a cost of security.  It is now possible for the person making the collection to lie about the amount that they received, skimming a bit off for themselves.  The group can decide if they want the list of donation addresses to be public or not.

[DeathAndTaxes]

I had updated my post but forgot to click submit.  I see you found the SEC spec.

Very cool indeed.  Perhaps Satoshi didn't know this was possible, or perhaps he was worried about the possibility of more than one choice for Q given the signature (r, s) and the additional logic needed to deal with it.  

I think the bolded part is more likely.  Satoshi also seemed unaware of the advantages of compressed keys as well.  A lot about the early code would suggest that Satoshi was a genius "big picture thinker" but cryptography may not have been his strongest suit.  None of this should be taken as criticism, it is amazing that Bitcoin worked effectively and securely from day 0, it is just an observation.

As I indicated above I believe (unless I am misreading the spec) that there are only two possible j values (0,1) for secp256k1 and thus two possible pubkey Q. The "j" can be encoded in the transaction making it unnecessary to try all permutations of j.  Bitcoin does this for signed messages by putting a flag byte in the header.  Even if the pubkey is recovered since Bitcoin supports both

Explicit PubKey = 34 (or 64) bytes per output.
Recovered PubKey (w/ hint) = 1 byte (and one recovery required) per output.
Recovered PubKey (no hint) = 0 bytes (and 1.5 recoveries on average) per output.

I see Gavin supported Satoshi's decision to include the public key.

He did at the time but I still wonder about that (and my guess is it wasn't a decision).  At the current rate the network is creating about 20 million transactions annually.  The average number of inputs per transaction is 2.4.  Even assuming 100% of them are compressed pubkeys that is still 34 bytes per PubKey or ~ 1.6 GB per year.  At the 1MB block limit the blockchain would increase by about 52 GB per year.  PubKeys would make up about a quarter of that if average number of inputs and outputs per transaction remain the same.  Computing power is the resource least likely to be a bottleneck (we are talking about tens of thousands of ECDSA validations per core per second).  It is far more likely as transaction volume grows and full nodes support more SPV nodes that bandwidth will be the first real world bottleneck. 

If necessary Bitcoin could be extended to support a new version of addresses that requires compressed keys, drops redundant DER encoding, and uses PubKey recovery to reduce the size of the average tx by 25%. It shouldn't be any more difficult than adding support for P2SH was unless I am missing something major.

[Brangdon]

By providing a single address, everyone can see the average amount donated per person, and know how many people didn't donate.

Yes. That's information about the community.

Using additional information, it might become possible to make educated guesses about who gave how much.

Well, yes. You could go around and ask them, or you could guess that those who knew the boss longest would give more. That's not much Bitcoin can do about additional information.

Better would be to print out enough donation addresses so there is one for each employee.  Then cut up the paper so that there is only one address per piece.  Turn then face down so nobody knows what address anybody else gets, and let everyone choose randomly.

Sure, there are ways to use multiple addresses. You could just choose to not remember who got which address. If all this is happening through email, then it becomes harder for the co-workers to directly verify.

In general, when someone gives you a custom address online, you have to figure they can tie it to you (or whatever conversation you are involved in). Usually that's a good thing. When ordering a pizza, you want the payment to be tied to the delivery address.

[MaxwellsDemon]

I still don't get how a dozen people sending to a single address of mine is protecting their privacy better than if I provide one address per transaction.

Well, suppose you are collecting donations from co-workers for your boss's birthday present. If you give them all the same address, you see the incoming transactions and the total balance, but you won't know who paid what, so they have some anonymity. If you give a different address to each co-worker, and remember who got which address, then you can tie the amount of each donation to the person who sent it. Then you can inform your boss about who didn't pay for her present. Clearly, your co-workers' anonymity has been compromised in a way that affects (some of) them adversely.

By providing a single address, everyone can see the average amount donated per person, and know how many people didn't donate.  Using additional information, it might become possible to make educated guesses about who gave how much.  Now, not only you and the boss, but EVERYONE has information about the donations.

Better would be to print out enough donation addresses so there is one for each employee.  Then cut up the paper so that there is only one address per piece.  Turn then face down so nobody knows what address anybody else gets, and let everyone choose randomly.

Now nobody other than the recipient knows exactly how much each person donated.

I already said this on this thread but I'll say it again: Stealth addresses. A lot simpler than cutting up pieces of paper, and achieves the same result  

Of course, privacy comes at a cost of security.  It is now possible for the person making the collection to lie about the amount that they received, skimming a bit off for themselves.  The group can decide if they want the list of donation addresses to be public or not.

There may be a way around this problem, using Gregory Maxwell's Merkle tree-based auditing technique:

1. After receiving the donations to various addresses, the donation collector creates a Merkle tree: every leaf contains hash(address to which coins were donated, sum donated); every node contains hash(child 1, child 2) and the total sum of the donations contained in the children.
2. The donation collector creates a separate file for every donator, which includes the branch of the tree relevant to that donator (the path from the donation address to the root).
3. Since even the collector doesn't know who donated to which address (and therefore who should get each file), she encrypts each of these files with the public key of the address from which the donation came, and publishes all the encrypted files.  
4. Each donator decrypts the relevant file and verifies her inclusion in the root.
5. The donation collector publishes a receipt, proving that she bought the boss a gift which cost at least as much as the sum of the root.

This way, nobody knows who donated what, everybody knows the total sum donated, only the donation collector knows how many people donated and the distribution of the donation sums, and everybody knows that the collector didn't steal.

It's a bit complicated for such an obscure use case, but I just love how smart cryptography can solve everything  



EDIT: Now that I think about it, maybe it's not such an obscure use case. We already discussed on this thread the advantages of stealth addresses for charities. Think about a charity that wants to initiate a limited-time fundraiser for a specific cause. It publishes a stealth address for donations. Every donation ends up in a different address, thus distancing donators from each other as well as from the charity. This increases privacy for the charity and for its donators, but lowers transparency.
To regain transparency, the charity uses the above auditing technique as soon as the fundraiser is over. It then produces evidence that it spent a sum of money at least as large as the root sum towards advancing the cause.
This could also be useful for things like crowdfunding campaigns on the bitcoin-only version of Kickstarter (does that exist yet?).

[jonald_fyookball]

A bitcoin private key, d is (almost) any 256-bit integer (78 digit number).  To find the associated public key, Q, you need to multiply your private key by a special "number" G called the elliptic curve base point:

     Q = d x G

If you know d (private key) and G, it is fairly straight forward to calculate Q (public key).  Now, if G and Q were normal numbers, we could re-arrange this equation to solve for the private key by division:

     d = Q / G

But G and Q are not normal numbers; they are actually the {x, y} coordinates of points on a special type of curve called an elliptic curve.  Points on elliptic curves can be multiplied by normal numbers (like a private key), but it turns out that it is extremely difficult to "divide" two points on an elliptic curve to get a normal number (to solve for the private key, d).  I use quotes around "divide" because we actually call this problem the "elliptic curve discrete logarithm problem" (ECDLP) and not the division problem.

Now the reason the security is 128 bits when the private key is 256 bits is because you don't need to brute force every possible key.  You just need to find the value of d that when multiplied by G gives you Q.  There is a bit of a pattern that you can exploit, so to speak.  The fastest known algorithms that allow one to solve the ECDLP (baby-step giant-step, Pollard's rho, etc.), need O(√n) steps.  Since n = 2^256, √2^256 = 2^128.  So using the most efficient algorithm to solve for d if Q and G are known, it should "only" take around 2^128 steps, as opposed to the 2^256 steps it would take to try every possible key by brute force.

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Key_sizes

Isn't hash function SHA-256 plugged in there somewhere?  where does that fit into this?  And even if you knew "G", wouldn't you still have the hash to contend with?  

In the post you quoted, I was trying to explain elliptic curve multiplication and the discrete logarithm problem in a very simple way.  Elliptic curve multiplication is an example of a trapdoor function that is easy to compute in one direction (multiplying the private key (integer) by the elliptic curve base point to get the public key) but infeasible to compute in reverse (finding the private key given the public key and base point).  

When you produce an ECDSA signature for a bitcoin transaction, you sign a 256-bit hash, e, of the message (transaction), m, and get a pair of numbers {r, s}.  But in order for anyone to verify that the signature is correct, you must also tell them your public key Q in addition to r and s (and they must know the message, m, that you signed).

Everyone already knows G because it's a property of the secp256k1 curve.  The act of signing and broadcasting a transaction makes your public key Q known because you need to provide this in order for the network to verify your signature.  Someone could "steal" your funds remaining in the associated bitcoin address if they can solve the problem:

        Q = d x G

for an unknown d.  But like I explained earlier, it is not presently feasible to find d as the fastest known algorithm still takes 2^128 steps.  If the public key is not known, on the other hand, then someone could "steal" your funds if they try on average 2^160 random 256-bit integers until they find a ripeMD160 collision with your bitcoin address.   I say "steal" because 2^128 and 2^160 are really really big numbers and it's not actually feasible to perform a computation with such a huge number of steps.  


I've seen you express interest in elliptic curves in a few threads now.  How I learned about them was reading the wikipedia articles (many, many times), reviewing the comments by DeathAndTaxes, DannyHamilton, GMaxwell and a few others regarding these curves.  But what really made it sink in for me was writing code from scratch to sign and verify ECDSA.  I did this in Mathematica so that I didn't have to worry about integer size or modulus operations.  After I did this, l had new respect for the weird properties of elliptic curves and prime numbers too--it's really interesting stuff.  

Thanks Peter,
I read the wiki article on ECDSA.  I get idea better now. 

Still miles behind the conversion but at least I see what
is this "k" you guys keep talking about and why we shouldn't
re use addresses for that reason.

wrong RNG or simple collision in the integer space used for K
Is orders of magnitude more feasible than brute forcing a key,
I assume. 

Btw, how big is the space  for k?

[Peter R]

Btw, how big is the space  for k?

Big!

k must be on the interval [1, n-1] where n is the integer order of G (and G is the base point for secp256k1).  n is the big prime number:

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

or in hex:

n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

If you pick a 256-bit unsigned integer at random, it will be a permissible value for k 99.99999999999999999999999999999999999962655% of the time.

This also shows that it is not feasible to "randomly" generate the same k value twice (well, unless your random number generator is broken à la the Android bug but then it wasn't really random).  

[jonald_fyookball]

So then I was completely wrong, as this is on the order of 2^256.

Are the common implementations using numbers that big?

[DeathAndTaxes]

So then I was completely wrong, as this is on the order of 2^256.

Are the common implementations using numbers that big?

Well it has to be a 256 bit number.  0x0000000000000000000000000000000000000000000000000000000000000001 is a 256 bit number.

Are you asking, do the k values generated really have 256 bits of entropy?  That is a very hard thing to prove, which is why I am an advocate of RFC6979.  It bypasses that concern entirely by making the k value deterministic.  With RFC6979 and HD wallets you could process a lifetime of bitcoin transactions with just 128 random bits (a small enough amount to generate by rolling dice or flipping coins).

[Peter R]

So then I was completely wrong, as this is on the order of 2^256.

Correct.  You're more likely to brute force a private key that unlocks a funded bitcoin address (1 in 2^160) than you are to generate the same k value twice with a working RNG (1 in 2^256).

Are the common implementations using numbers that big?

Yes, which means that repeat-k-value problems are entirely due to bugs.  Bitcoin is forcing us to recognize how poor our computer security really is (and RNGs are not the only culprit by a long shot).  

[jonald_fyookball]

So then I was completely wrong, as this is on the order of 2^256.

Are the common implementations using numbers that big?

Well it has to be a 256 bit number.  0x0000000000000000000000000000000000000000000000000000000000000001 is a 256 bit number.

Are you asking, do the k values generated really have 256 bits of entropy?  That is a very hard thing to prove, which is why I am an advocate of RFC6979 it bypasses that concern entirely by making the k value deterministic.

No, I wasn't asking that to be honest.

It would have been a much smarter question.

I guess I was somehow thinking it might be too big of
a number to calculate the curve point or something.

But I now I see that is the whole point here...

 

[phillipsjk]

With a self signed cert say you got a cert claiming to be your bank.  How do you know it was your bank which created it?

Easy, your bank mails out their Certificate hash; and posts a copy of the cert (with hash) in local branches in the case of key rotation.

With the CA sytem, you are blindly accepting the "self-signed" CA cert anyway if your browser does not recognize the CA authority your bank is using. I tried calling one of my parents's banks after such a warning. I was told to just trust the HTTP re-direct because the bank actually uses many different certs (and they did not know which signature to read over the phone).

IMO, giving dire warnings for self-signed certs, but not HTTP sites is a design flaw.