An idea on how to implement stealth addresses on Bitcoin layer 1

[tyook]

Hello there,

I'd like to share a scheme to improve the privacy of on-chain Bitcoin
transactions, without requiring changes in source code (can be done using
scripts)

The scheme I will present is based on RSA cryptography, but I bet someone can
suggest a better variation of it using better encryption protocols.

SCHEME

1. Alice generates a RSA key pair (s, p, n), where s is the secrete key, (p, n)
is the public key, and a^(sp) = a mod n for any a<n.

2. Alice then picks a random large number 1<S<n and computes B=S^2 mod n. Alice
wants to receive Bitcoin, so she shares (p, n, B) to Bob.

3. Bob chooses a nonce k and compute k' = k^p mod n, k'' = B^k mod n.

4. Bob then sends bitcoin to Alice using the following Bitcoin script for
authorizing Alice to spend her coins.

k` OP_DROP k'' OP_EQUAL

5. Alice finds out Bob's tx on the timechain,
then uses k' and her secrete key s to calculate k = k'^s.

6. Alice computes S^k mod n using k obtained in previous step.

7. Alice spends her bitcoin using the following bitcoin script:

S^k OP_DUP OP_MUL n OP_MOD

Let's see why this works. When Alice wants to spend her Bitcoin, her and Bob`s
script will be concatenated:

S^k OP_DUP OP_MUL n k` OP_DROP OP_MOD k'' OP_EQUAL

Then, this will happen:

Stack             Script
                  S^k OP_DUP OP_MUL n OP_MOD k` OP_DROP k'' OP_EQUAL
S^k               OP_DUP OP_MUL n OP_MOD k` OP_DROP k'' OP_EQUAL
S^k, S^k          OP_MUL n OP_MOD k` OP_DROP k'' OP_EQUAL
S^2k              n OP_MOD k` OP_DROP k'' OP_EQUAL
S^2k, n           OP_MOD k` OP_DROP k'' OP_EQUAL
S^2k mod n        k` OP_DROP k'' OP_EQUAL
S^2k mod n, k'    OP_DROP k'' OP_EQUAL
S^2k mod n        k'' OP_EQUAL
S^2k mod n, k''   OP_EQUAL
TRUE

Note that S^2k = (S^2)^k = B^k = k'' mod n. That`s why the script work.

I did say it could be implemented without requiring change to the source code,
but that was before I realize the script will not work because of the following:

1. The operations OP_MOD, OP_MUL are disabled (they can no longer be used)
2. The arithmetic operations work only for 32-bit values

So, actually this scheme won`t work but let us discuss this later on because I
want to highlight some points here.

PRIVACY PROVIDED BY THE SCHEME

Currently, most people advertise an address derived from their public key, and
the bitcoins is send to the address. If, for example, Alice is a content
creator and wants to provide her audience with a public address for donations,
then all donations will go that address and will be easy to know and track the
bitcoin received by Alice.

Using the suggested scheme, each person that gets Alice's public key will not
send bitcoin to an address. Instead, the script used to unlock the Bitcoin
contains data that does not reveals those bitcoins are being sent to Alice.
Why? Because this script contains only k' and k'' and cannot be link to Alice
as long as the nonce k is kept secret (only the sender and the receiver know
the value of k used to get k' and k'').

Moreover, when Alice goes spend her bitcoins, it does not reveal that she is
spending it because she only reveals S^k, which cannot be linked to her public
key (p, n, B).

So, an outsider cannot associate a public key pair to the bitcoin that was sent
to this public key pair, neither can him associate the bitcoin to the public
key pair when the new owner decides to spend it.

DRAWBACKS

The major drawback of the scheme (which we will see a solution soon) is that in
order for Alice to know she got Bitcoin is to scan all transactions using this
scheme and check if her keys can unlock the funds. For that, she needs to use
her private key.

Nowadays, people using Legacy or SegWit address can monitor how much Bitcoin
they own just using their master public key, without needing to reveal their
private key. They can export the master public key to a not-so-trusted mobile
or desktop wallet to monitor their funds, while being sure that their private
key lies secure in a hardware wallet, for example.

This cannot be done with the scheme described above, but a small change to the
scheme makes it possible to track the funds using only the public key!

SCHEME IMPROVED

In order for Alice to monitor her funds without exposing her private key, we
propose the following scheme (very similar to the previous one).

1. Alice generates a RSA key pair (s1, p1, n), where s is the secrete key,
(p, n) is the public key, and a^(s1 p1) = a mod n for any a<n.

2. Alice then picks a random large number 1<S<n and computes B=S^2 mod n.

3. Alice picks another RSA key pair (s2, p2, n) but uses the same n as in step
1. In other words, a^(s2p2) = a mod n for any a<n. If Alice wants to receive
Bitcoin, she shares (p1, p1, n, B) to Bob.

4. Bob chooses a nonce k1 and compute k' = k1^p mod n, k'' = B^k1 mod n.

5, Bob chooses another nonce k2 and computes H=hash(k2) and I = k2^p2 mod n.

6. Bob then sends bitcoin to Alice using the following Bitcoin script for
authorizing Alice to spend her coins.

I H k` OP_DROP3 k'' OP_EQUAL

7. In order for Alice to figure out which unspent outputs Bob sent to her, she
scans the timechain and computes I^s2 = k2^(p2s2) = k2 mod n. If hash(k2) == H,
then the Bitcoin was sent to Alice. Otherwise, the Bitcoin was sent to
someone else.

8. Alice then uses k' and her secrete key s to calculate k1 = k'^s.

9. Alice computes S^k1 mod n using k1 obtained in previous step.

7. Alice spends her bitcoin using the following bitcoin script:

S^k1 OP_DUP OP_MUL n OP_MOD

Notice that (p2, s2) is used only as a way for Alice to identify which Bitcoins
belong to her without her needing to expose her private key s1. The only way to
spend Alice's bitcoins is knowing s1. The only way to know which Bitcoin
belongs to Alice`s key pair (p1, s1, 2) is eitheir knowing s1 or knowing s2.
Knowing only s2 it is possible to monitor Alice's funds.

IMPLEMENTATION

Using the improved scheme, or some variation of it (using something other than
RSA), it is possible to achieve high level of privacy on Bitcoin layer 1. As
said before, now it is not possible to implement these schemes because:

- The operations OP_MUL and OP_MOD are disabled
- Arithmetic operations in Bitcoin scripts only support 32-bit integers

Thus, the only way to implement the suggested scheme is through some BIP which
could introduce a new operation.

For example, Bob would use the following script to send BTC to Alice:

I H k' OP_DROP3 k'' OP_CHECK_STEALTH_ADDR

Alice would use the following script to unlock it:

S^k1 n

The OP_CHECK_STEALTH_ADDR would square S^k1 modulus n, then compare it to k''
and return TRUE if only if they are equal. In other words, this OP would take
a,b,c as input and return true if a^2 mod b = c.

CONCLUSION

This text proposes a scheme to provide on-chain privacy on Bitcoin layer 1. This
is just a draft that needs to be elaborated further. I'm aware that it is crucial that
any improvement does not compromise the security and decentralization of
bitcoin, so I hope my suggestion is welcomed and not seen negatively.

[NotATether]

OP_MUL and OP_MOD are disabled opcodes - you can't use them in scripts because their evaluation by the interpreter will abort the script immediately and cause permanent fund loss.

You are talking about Stealth addresses generated by C = (G*a)+B and C = (G*b) + A formulas, right? You don't need fancy scripts to spend to them - they are regular public keys which can be hashed into a legacy, segwit, or taproot address, or any other future address, and their respecive scripts can be used.

[witcher_sense]

Since adding OP_MUL and OP_MOD  OP codes anyway requires conducting a hardfork, it would be better to implement more sophisticated privacy-enhancing tools like ring signatures, confidential transactions, or anything else that hides senders and receivers and the amount transferred. But if it could be possible to hardfork bitcoin every time there is a "useful" update or interesting method to improve on-chain privacy, bitcoin would be no better than Ethereum, which is already almost taken over by large corporations and governments. Luckily, we don't need to introduce unnecessary code to make bitcoin more private because, as NotATether already said, you can simply convert your fancy cryptography into conventional public keys and bitcoin addresses, from which the receiver can spend the usual way. The scheme you proposed reminded me of silent payments by Ruben Somsen, which was discussed in detail in this thread. The idea was that the receiver makes their silent address public, and anyone willing to make a payment can construct a bitcoin address from which only the receiver can spend. Check out that thread.

[pooya87]

Since adding OP_MUL and OP_MOD  OP codes anyway requires conducting a hardfork

It could be done with a soft fork specially through a new witness version. All it takes is to add a couple of lines of code in the interpreter when handling witness version X to handle new OP codes just like how the new OP_CHECKSIGADD was introduced recently with Taproot soft fork.
It can also be part of Taproot scripts using one of the OP_SUCCESS bytes in a backward compatible way.

[NotATether]

I see another problem with this scheme - the script size in bytes is too large. I'm counting two 64-byte pushes (n and k) along with some half-dozen opcodes - that's approximately 130 bytes of script size. This is multiple times larger than standard script types (P2[W]PKH is about 23 bytes, and P2[W]SH has an almost equal byte size). Inputs like these will fill up the block size limit very quickly, because you are basically reducing the number of transactions in a block by a factor of 6 if everyone goes on to use Stealth addresses which of course won't happen, so the reduction will be less but still significant - think a 2x or 3x reduction in transactions-per-block.

[aliashraf]

7. Alice spends her bitcoin using the following bitcoin script:

S^k OP_DUP OP_MUL n OP_MOD

OP,
Thanks for sharing. Maybe I'm missing something, but other than implementation challenges, I suspect this scheme is vulnerable to miner theft as once it goes to the mempool, miners can take it and replace the output with theirs. It is because the transaction is not signed, hence forgery is not prohibited.

[tyook]

> OP_MUL and OP_MOD are disabled opcodes - you can't use them in scripts because their evaluation by the interpreter will abort the script immediately and cause permanent fund loss.

Yes, I pointed that out in the post

> You are talking about Stealth addresses generated by C = (G*a)+B and C = (G*b) + A formulas, right? You don't need fancy scripts to spend to them - they are regular public keys which can be hashed into a Legacy, SegWit, or taproot address, or any other future address, and their respecive scripts can be used.

To be sincere, I didn't know about stealth addresses when I first came up with this scheme, only knew about them later. I don't know about those formulas you mentioned;
can you please suggest me some reading?

Also, as far as I know, the Legacy, SegWit and Taproot address formats do not provide the level of privacy suggested by the scheme. For example, if Alice publishes her Legacy/SegWit address on the internet to receive, i.e, donations, them everyone can see how much Alice has got by checking the public address on the timechain. On the other hand, in the scheme I suggested, the sender Bob does not use an address to send Bitcoin to, rather it generates a random nonce that nobody else knows, thus obfuscating the fact he sent the Bitcoin to Alice. Not only that, when Alice goes spend that Bitcoin, she does not reveal that it is she who is spending the Bitcoin. Please correct if I'm wrong, but from what I have studied it is not possible to achieve this level of privacy with legacy, segwit or taproot.

> Since adding OP_MUL and OP_MOD  OP codes anyway requires conducting a hardfork, it would be better to implement more sophisticated privacy-enhancing tools like ring signatures, confidential transactions, or anything else that hides senders and receivers and the amount transferred. But if it could be possible to hardfork bitcoin every time there is a "useful" update or interesting method to improve on-chain privacy, bitcoin would be no better than Ethereum, which is already almost taken over by large corporations and governments.

I agree with you. A hardfork is not an option. The immutability of the protocol is more desirable than rich features, even privacy features. However, if we can improve Bitcoin without causing hardforks, without introducing vulnerabilities, without compromising decentralization, then we should strive to do so.

> I see another problem with this scheme - the script size in bytes is too large. I'm counting two 64-byte pushes (n and k) along with some half-dozen opcodes - that's approximately 130 bytes of script size. This is multiple times larger than standard script types (P2[W]PKH is about 23 bytes, and P2[W]SH has an almost equal byte size). Inputs like these will fill up the block size limit very quickly, because you are basically reducing the number of transactions in a block by a factor of 6 if everyone goes on to use Stealth addresses which of course won't happen, so the reduction will be less but still significant - think a 2x or 3x reduction in transactions-per-block.

This is true, specially because in the draft I used RSA encryption, but there are nowadays encryption standards that allow shorter and more secure encryption and signatures schemes. My goals was to show a proof of concept; some real solution needs to be practical (i.e, fewer bytes, secure enough)

> Thanks for sharing. Maybe I'm missing something, but other than implementation challenges, I suspect this scheme is vulnerable to miner theft as once it goes to the mempool, miners can take it and replace the output with theirs. It is because the transaction is not signed, hence forgery is not prohibited.

That's true. Thanks for pointing that out. I didn't realize that... I thought the scheme was pretty useful because allowed one-time address to be generated by the sender on the fly, but now I see the scheme is useless since anybody monitoring the mempool can forge the script. I will see if I can come up with something to tackle that

[garlonicon]

Please correct if I'm wrong, but from what I have studied it is not possible to achieve this level of privacy with legacy, segwit or taproot.

It is possible. It is called "Silent Payments" and is work in progress: https://bitcointalk.org/index.php?topic=5400363

[tyook]

> It is possible. It is called "Silent Payments" and is work in progress: https://bitcointalk.org/index.php?topic=5400363

Thank you! That's very interesting!