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.