Understanding Stealth Addresses/Payments

[bitfreak!]

I only recently learnt about "stealth payments", probably because I assumed it was the same as some other anon transaction mechanism with a similar name. All the anonymization mechanisms I've looked at in the past have some sort of disadvantage which turns me off using them in practice. However after doing some basic research on stealth payments it seems to me this is an absolutely ingenious mechanism without any major pitfalls.

It does force the receiver to scan for transactions to their stealth address but I think that's a fair price to pay for being able to receive anonymous transactions by sharing only a single stealth address. It doesn't bloat the blockchain with a huge amount of metadata and the method its self is extremely elegant, unlike other bulky mechanisms which are highly complicated and hard to understand. CoinDesk quoted Mike Hearn as saying "Stealth addresses let us have our cake and eat it."

To begin my research I simply googled "Stealth Addresses" and the top result was a StackExchange question with a nice answer:

What is a stealth address?

With a stealth address, you ask payers to generate a unique address in such a way that you (using some additional data which is attached to the transaction) can deduce the corresponding private key. So although you publish a single "stealth address" on your website, the block chain sees all your incoming payments as going to separate addresses and has no way to correlate them. (Of course, any individual payer knows their payment went to you, and can trace how you spend it, but they don't learn anything about other people's payments to you.)

My first impression was that this sounded like some sort of black magic and I had no idea how it could possibly work. I couldn't understand how the payer could generate a new address but only the payee could know the private key to that address, even though they played no role in the generation of the address. The CoinDesk article went a bit deeper into the mathematics involved but it's written very poorly and is full of mistakes.

However after reading a few more articles on the subject of stealth payments I now understand how it works in theory, for the most part anyway. The purpose of this thread was not only to explain how it works, but to clear up some of my confusion on the things I still don't fully understand. First of all, it seems to me that the stealth address is really just the full public key encoded into some higher base (58 I assume) to make it shorter.

When someone wants to make a payment to that stealth address they will decode the stealth address back into the full public key and then use it to generate the actual address they will be sending the payment to (I'll call this "address X" from now on). But in order to generate address X the payer also needs to generate their own key pair, although I see no reason they couldn't use a key pair they previously generated and used for something else.

The payer can generate a shared secret (S) by using their own private key (e) and the public key (Q) derived from the original stealth address. The exact equation is S=eQ. This is the first thing about stealth payments which seems rather amazing to me because it implies that if I take any two key pairs, and then swap the public keys, then multiply the public key by the private key in each pair, the result should be the same for both key pairs.

Obviously I'm not an expert on ECC math but I didn't know that was possible. Technically the shared secret seems to be a sha256 hash of eQ but we don't really need to worry about that detail to understand it. Then finally, the payer will add Q to the shared secret (aka Q+S) in order to generate the public key for address X. So the payer has no idea what the private key for address X is, but the payee can calculate it by using the equation d+S where d is the private key for Q.

This is the second bit of math which seems rather amazing to me. If the public key for address X is equal to Q+S and the private key is equal to d+S, that implies I can take any key pair, then increase both the public and private keys by the same amount, and I will still have a perfectly valid key pair. Really the shared secret is just the incremental value which both parties can agree upon without anyone else knowing the value of the secret.

To put it in the simplest possible terms, the payer will increment the public key derived from the stealth address to produce address X. The payee will be scanning the blockchain looking for transactions sent to their stealth address (see this diagram to understand how that works). Then after receiving the transaction the payee will increment their private key using the same shared secret the payer used.

This allows the payee to produce a private key which is valid for address X. The original key pair used for the stealth address is essentially acting as a seed for all the real addresses which the coins get sent to. One of things about this whole process which still isn't clear to me is exactly what is the metadata? I assume it must just be the public key the payer used to generate the shared secret, but it seems like I might be wrong about that.

The reason I'm asking is because I think this could be the perfect anonymization mechanism for Cryptonite and other mini-blockchain coins because the metadata could be stored in the tx message field if it's not too large. Since there can only be one message field in each transaction it would obviously restrict the number of stealth payments to one per transaction but that seems like a very reasonable compromise to me.

EDIT: fixed some mistakes.

[bitfreak!]

Also it's unclear to me whether the payer is using the public key associated with the address they are sending coins from or if they generate a new key pair on the fly for every stealth payment. It seems to me if they used the public key connected to the input address then the payee could derive the public key from the signature and it wouldn't have to be saved as extra metadata.

[tacotime]

Please refer to CryptoNote CNS006 for an explanation

https://cryptonote.org/cns/cns006.txt

Please note that stealth addresses do not afford anonymity but rather forward privacy (they obfuscate where funds are being sent to). Recipients also must scan the blockchain to decipher if any outputs belong to them (and so thin clients become a bit more difficult, because they can no longer simply poll a server for an address balance).

[YarkoL]

Also it's unclear to me whether the payer is using the public key associated with the address they are sending coins from or if they generate a new key pair on the fly for every stealth payment. It seems to me if they used the public key connected to the input address then the payee could derive the public key from the signature and it wouldn't have to be saved as extra metadata.

In my understanding, a new keypair is generated by the
payer per stealth transaction. For this reason they are referred
as ephem(eral) keys.

Using the terminology in your diagram, Alice, the payer generates a stealth public key Q'
from Bob's (the payees) public spending key Q and from her ephem private key e.

She includes the ephem public key P as metadata in the transaction that pays to Q'.

Bob can then extract P and combine it with his private spending key d
to get the stealth private key with which he can spend the amount Alice paid to Q'.

[bitfreak!]

Thanks for the resource, but I found it a little hard to follow because the math is slightly different from what I've seen so far. However I just found a brilliant reddit comment which essentially answers all my questions and explains the process much more eloquently than I could. It does work exactly how I thought.

Elliptic Curve Diffie Hellman

Alice wants to send some Bitcoins to Bob. For that, she needs an address. Bob does not want to explicitly give Alice an address - he wants to publish a public key that anyone can use to generate an address from, but he doesn't want everybody to generate the same address. How is this possible?

Alice needs a shared secret with Bob. To create one, she multiplies her private key by Bob's public key:

S = aB

This doesn't look immediately useful until we consider how Bob would calculate the shared secret. He multiplies his private key by Alice's public key.

S = bA

Are these really the same? Remember that public keys are private keys multiplied by a generator point:

S = aB = a(bG)

S = bA = b(aG)

S = abG = baG

Any two individuals who know each other's public key can, with simple multiplication, can calculate a shared secret that nobody else can either duplicate or link to either party's public keys. That's ECDH.

Alice and Bob can turn their shared secret (which is a curve point) into a number using a hash function. We'll call the number representation of the shared secret (s).

In what way is the shared secret useful for Alice's problem?

She needs to calculate a new public key for which Bob can calculate the private key, but which nobody else can connect either to Alice's or to Bob's public keys.

Alice creates a new public key for Bob by adding the shared secret to Bob's public key:

C = B + sG

How do we know that Bob has the private key (c) for this new public key?

C = B + sG = bG + sG

C = (b+s)G

c = b + s

Perfect. To spend bitcoins sent to the address for C, all Bob needs to know is Alice's public key. Then he can calculate the shared secret, and add that shared secret to his private key.

Alice can't calculate c, because she doesn't know Bob's private key.

No outside observers can connect C to either Alice or Bob, because they can't calculate the shared secret.

[bitfreak!]

Using the terminology in your diagram, Alice, the payer generates a stealth public key Q'
from Bob's (the payees) public spending key Q and from her ephem private key e.

She includes the ephem public key P as metadata in the transaction that pays to Q'.

But what exactly is the point of that? If the only concern is generating a unique Q' each time, then it seems to me some random data used in the process of generating Q' could do the trick. Instead of embedding P as metadata you embed the random data, and the public key is derived from the signature.

[bitfreak!]

Now that I think about it, it seems to me there is another way to achieve the same thing. Since the payee needs to share his full public key (Q), it would be possible for the payer to encrypt data using Q and only the payee would be able to decrypt it. The payer can generate a random number (r), then use that in the same way as the shared secret to generate Q'. Then they encrypt r using Q and embed it as metadata. The payee can scan for transactions by checking if his private key can decrypt the metadata.

EDIT: or better yet, the shared secret is generated the normal way by multiplying the private and public keys together, but we use it as the key for a strong symmetric encryption algorithm to encrypt r instead of using Q to encrypt r, which should be a more secure approach.

[YarkoL]

The payee can scan for transactions by checking if his private key can decrypt the metadata.

How does the payee get at the stealth private key that can
spend Q' in this scenario?

[bitfreak!]

The payee can scan for transactions by checking if his private key can decrypt the metadata.

How does the payee get at the stealth private key that can
spend Q' in this scenario?

The decrypted metadata will contain the shared secret necessary to calculate it obviously. Even though it's a random number generated by the payer, it still works as a shared secret because both parties know what it is but no one else does.

And in the scenario mentioned by my edit, the payee would first need to calculate the decryption key by multiplying his private key with the public key of the payer, as usual. Then he can decrypt the metadata and figure out the shared secret, or second shared secret if you will.

[tacotime]

Now that I think about it, it seems to me there is another way to achieve the same thing. Since the payee needs to share his full public key (Q), it would be possible for the payer to encrypt data using Q and only the payee would be able to decrypt it. The payer can generate a random number (r), then use that in the same way as the shared secret to generate Q'. Then they encrypt r using Q and embed it as metadata. The payee can scan for transactions by checking if his private key can decrypt the metadata.

EDIT: or better yet, the shared secret is generated the normal way by multiplying the private and public keys together, but we use it as the key for a strong symmetric encryption algorithm to encrypt r instead of using Q to encrypt r, which should be a more secure approach.

There is no orthologous method for ECDSA that you'd use to directly encrypt data to a recipient key as you would with RSA. ECDSA is purely for signing.

What you're describing (using the shared secret for a symmetric cipher) is known widely as Elliptic curve Diffie–Hellman (ECDH). It overcomes the above limitation. It is used to transmit messages in transactions in some CryptoNote coins, and is widely used in protocols such as SSH and TLS.

http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman

[bitfreak!]

There is no orthologous method for ECDSA that you'd use to directly encrypt data to a recipient key as you would with RSA. ECDSA is purely for signing.

Well I have no idea what orthologous means in relation to cryptography and appears Google doesn't either, lol. I know EC cryptography can be used for asymmetric encryption, but it probably wouldn't be a great idea, which is why I made that edit mentioning the shared secret can be used as an encryption key for a strong symmetric encryption algorithm.

What you're describing (using the shared secret for a symmetric cipher) is known widely as Elliptic curve Diffie–Hellman (ECDH).

I'm aware of that, the whole reddit post I just quoted describes how ECDH works. And actually ECDH is just a way to agree upon a shared secret, not an encryption technique. The main point I was making is that we don't need to use the shared secret as the value we use to increment Q, we can actually use it as the key for a symmetric cipher which we use to encrypt a second shared secret, which is the random value we use to increment Q.

[YarkoL]

The payee can scan for transactions by checking if his private key can decrypt the metadata.

How does the payee get at the stealth private key that can
spend Q' in this scenario?

The decrypted metadata will contain the shared secret necessary to calculate it obviously. Even though it's a random number generated by the payer, it still works as a shared secret because both parties know what it is but no one else does.

But can you generate a valid stealth keypair from
combining the random number with the payees original keypair,
i.e by what procedure do you replace the ephem keypair with
just one number?

And in the scenario mentioned by my edit, the payee would first need to calculate the decryption key by multiplying his private key with the private key of the payer, as usual. Then he can decrypt the metadata and figure out the shared secret, or second shared secret if you will.

I think you mean the payer multiplies his private key with the public key
of the payee? He can't have the private key of the other party.

[bitfreak!]

i.e by what procedure do you replace the ephem keypair with
just one number?

Well the ephem keypair is only required for traditional stealth payments because that's how both parties can calculate the shared secret. That's not necessary in my first scenario because only the public address of the payee is required to encrypt the randomly generated shared secret. It's probably easier to think about my second scenario, the one I gave in the edit. In that scenario the ephem keypair is still required to calculate the first shared secret like normal, but we use it as the key for a symmetric encryption algorithm so that we can encrypt the randomly generated shared secret. The second random shared secret is what we actually use to calculate Q'.

I think you mean the payer multiplies his private key with the public key
of the payee? He can't have the private key of the other party.

Yes that is what I meant, I have corrected it now.

[YarkoL]

Well the ephem keypair is only required for traditional stealth payments because that's how both parties can calculate the shared secret. That's not necessary in my first scenario because only the public address of the payee is required to encrypt the randomly generated shared secret. It's probably easier to think about my second scenario, the one I gave in the edit. In that scenario the ephem keypair is still required to calculate the first shared secret like normal, but we use it as the key for a symmetric encryption algorithm so that we can encrypt the randomly generated shared secret. The second random shared secret is what we actually use to calculate Q'.

Ok, I see it now. I think that (using Q X e as an encryption key) would work in principle,
but you'd have to test it in practice. Probably there's some hitch or two, otherwise
this would have superseded Diffie-Hellman already in computing stealth keys. Maybe
it comes down to the fact that this requires an additional layer of encryption, whereas the
original method works just as well and very elegantly too. 
.

[bitfreak!]

Ok, I see it now. I think that (using Q X e as an encryption key) would work in principle,
but you'd have to test it in practice. Probably there's some hitch or two, otherwise
this would have superseded Diffie-Hellman already in computing stealth keys. Maybe
it comes down to the fact that this requires an additional layer of encryption, whereas the
original method works just as well and very elegantly too.

ECDH is still used in my second scenario to calculate the shared secret. It's not really an improvement on stealth payments, it's just an alternate way to do it. I was trying to think of a way to do it without having to generate a new ephem keypair for each stealth payment. In my second scenario the ephem keypair is not generated on the fly, the payer will just use the keypair associated with the address they are withdrawing coins from. The resulting Q' is still unique each time because the second shared secret is a randomly generated value. Doing it that way means the payer doesn't need to include their public key as metadata because it can be derived from the signature, and the only metadata we need to store is the encrypted random shared secret. That may be a better approach for Cryptonite because the tx message field is limited in size.

[YarkoL]

ECDH is still used in my second scenario to calculate the shared secret. It's not really an improvement on stealth payments, it's just an alternate way to do it. I was trying to think of a way to do it without having to generate a new ephem keypair for each stealth payment. In my second scenario the ephem keypair is not generated on the fly, the payer will just use the keypair associated with the address they are withdrawing coins from. The resulting Q' is still unique each time because the second shared secret is a randomly generated value. Doing it that way means the payer doesn't need to include their public key as metadata because it can be derived from the signature, and the only metadata we need to store is the encrypted random shared secret. That may be a better approach for Cryptonite because the tx message field is limited in size.

I read some more on this, and it appears that a scenario where you do not generate ephem keys on the fly
belongs under the category of static (non-ephemeral) DH key exchange, which is not considered as secure,
since if the keypair of the payee gets compromised, the payer(s) get exposed as well.

http://security.stackexchange.com/questions/33233/ecdh-and-forward-secrecy

I think the original idea of transmitting a random number would therefore
work better. In fact, in the MillenniumCoin (script-based anonymity) you initiate
transactions by doing an off-chain exchange of a random nonce between the nodes,
so I was deprived of about one hour of much-needed sleep last night as my mind
started to mull over the possibilities  

[bitfreak!]

I think the original idea of transmitting a random number would therefore
work better.

Well both of my methods transmit a random number, the difference is the way the number is encrypted. In the first scenario we simply use the public key of the payee to encrypt it and then the payee will use his private key to decrypt it. But in the second scenario the first shared secret is computed using ECDH as usual, but instead of using it to produce Q', we use it to encrypt the random number with a symmetric cipher.

But the flaw you mentioned does still apply to my second scenario because if the payer were to have their private key compromised it would allow anyone to calculate the first shared secret and then decrypt the metadata, allowing them to see the second shared secret, thus allowing them to calculate Q' using a brute force tactic in which they use a list of all known stealth addresses to see if they can produce Q'.

Ephemeral keypairs have the same problem if they get leaked, it's just that they are only used that one time and then thrown away, so it's harder to accidentally leak an ephem keypair. I'll have to think about this problem some more. As mentioned earlier, the first scenario isn't really a good way to go either. I think I understand the point tacotime was making now. EC cryptography can't produce a truly asymmetric encryption scheme so it cannot be used the same way as RSA.

In fact, in the MillenniumCoin (script-based anonymity) you initiate
transactions by exchanging off-chain such a random nonce between the nodes,

That seems pretty stupid to me. Wouldn't it mean both parties have to be online at the same time in order to do this? ECDH seems like a much more elegant solution to me.

[YarkoL]

[EC cryptography can't produce a truly asymmetric encryption scheme so it cannot be used the same way as RSA.

I thought that you'd use RSA or another
scheme to encrypt anyway (hence "additional layer of encryption" that I mentioned)

In fact, in the MillenniumCoin (script-based anonymity) you initiate
transactions by exchanging off-chain such a random nonce between the nodes,

That seems pretty stupid to me. Wouldn't it mean both parties have to be online at the same time in order to do this? ECDH seems like a much more elegant solution to me.

It's a little different situation. The nonce is exchanged between
payer and a "delegate" (basically a middleman), and the latter is selected
from the nodes that are online at any given moment, and the delegate then
transfers the amount to the payee. I was thinking about ways to
use the nonce to stealth the payees address and/or making it possible for the payee
to identify payment in the case of multiple delegates handling the transfer of the amount broken
down to round numbers (to make it more untraceable)... Not very elegant, but interesting.

[bitfreak!]

I thought that you'd use RSA or another

No I was assuming that we could do asymmetric encryption directly with the EC keypairs just like with RSA but it turns out that might not be true. I suppose we could use RSA but then the stealth addresses would need to be even longer than they already are, and they're already much longer than a normal Bitcoin address, so making them even longer seems untenable. If we could use the EC keypairs for asymmetric encryption then we would avoid that problem because those long stealth addresses already contain the EC public key. We still need that in order to generate Q' so we can't just get rid of it.