Is it possible to avoid Monero address re-use without having to create a new wallet for each transaction?

Question

I understand that currently, if an user wants to avoid re-using Monero addresses to avoid off-chain linkability (ie same address used for withdrawal from 2 exchanges and the exchanges releasing their logs to some entity), he has to create a new wallet for each transaction. This is cumbersome considering that for each wallet, entire blockchain needs to be scanned for outputs belonging to it,

Recently, a proposal which hopes to address this issue was presented on Reddit by user kenshi84. The idea describes a way to avoid Monero address re-use while maintaining normal performace when scanning the blockchian.

As previously discussed in StackExchange, exchanges can link withdrawal transactions if one uses the same receiving Monero address repeatedly, and it is recommended to create a one-time Monero address for each withdrawal to make sure no exchanges can ever link any withdrawals. Since such one-time Monero address generation can be tedious and error-prone, I came up with an idea of slightly modifying the protocol as follows:

Instead of telling the exchange the actual Monero address (A,B), a user (receiver) tells the exchange an integer k>0 and a one-time Monero address (C,D) where C=a^k A and D=a^k B. Note that it is impossible to link (A,B) to (C,D) using k without knowing the viewkey a. The exchange then generates the one-time stealth address using (C,D) as in the current protocol, but it also adds k to the transaction data along with R. The receiver can test if a given transaction output belongs to him or not by computing one-time Monero private view+spend keys (c,d) as c=a^{k+1} and d=a^k b. Address reuse can be avoided by making sure to use a new value for k associated with a that hasn't appeared in the blockchain.

Can this idea be useful?

Latter on in the comments he adds that this could be an improvement over HD wallets:

(...)I guess there's one advantage of this proposal over HD wallet though: when checking if a given tx output belongs to him or not, with HD wallet one needs to check against all the previously created Monero addresses (ie. linearly growing cost), whereas in this proposal one only needs to check against one address computed from k (ie. constant cost).

And also that this could be implemented just using the already available payment IDs:

(...)I think the additional task of generating unique k is quite similar to generating unique payment id. In fact, this proposal can be thought of as a replacement to the current payment id scheme, and k can be passed to the sender in the form of integrated address.

kenshi84's idea sounded extremely promising to me, so I would like to hear more about its viability.

I'm curious about the following aspects of the proposal:

1. What would be the benefit over a HD wallet scheme?
2. Would it affect the blockchain size if implemented?
3. Would there be any loss in privacy if such a scheme was to be used?
4. Would there be any risk to user funds?
5. Is a protocol change required for this to work or could it be done entirely wallet-side?
6. Are there any other points to consider?

Answer 1

Update May-2017: there has been some novel research into this, and it will be possible to tweak the sending wallet to allow sending to a special address acting as an "alias". The funds would go to the same wallet regardless of the number of these "alias" addresses used. The scheme makes it so that given an "alias" address, you can't work out the regular address or other aliases. Again, the actual records on the blockchain would never store any public address (be it regular, integrated, or alias), but the sender would generate a seemingly-random one-time destination address, as usual.

Read up on Github: https://github.com/monero-project/monero/pull/1753

---

I will attempt to answer the question while considering what had been discussed through other channels: Reddit, IRC/Slack Pt.1 & Pt.2

First of all, let's get the terminology straight to avoid confusing the similar terms.

• Address / stealth-address: any Monero address is also a stealth address. This is because it never appears on the blockchain and is used only to calculate the one-time public key which is the destination of an output. Will be referred to as (A,B) where A is the public view key and B is the public spend key. Small-caps are the corresponding private keys.
• One-time public key, referred to as P is the one time destination of an output. Generated from the stealth addres public keys and sender's random data.
• Sub-address: I propose this term for the addresses created using the proposed scheme. It's another normal Monero address but generated in a special way so it can be derived from (a,b,k). It will be referred to as (C,D). It's worth highliting that any of them could be used as a stand-alone monero wallet if the keys (c,d) were to be imported.

What would be the benefit over a HD wallet scheme?

The proposal boils down to having the recipient give to sender his (C,D,k) and the sender is expected to include the k in the transaction data when paying to (C,D). This way, the receiving wallet has to scan every one-time publick key on the blockchain only twice:

• first time with the assumption that the payment was done to (A,B), using a
• second time with the assumption that the tx data contains k, so it attempts to check if it belongs to a matching (C,D) by using c derived from (a,k)

Now, let's compare this against a HD wallet. It would have to check each output against every address belonging to it, so the refresh time would grow linearly with the number of addresses used. From this point of view, there is a clear benefit of the proposed sub-address sheme.

Would it affect the blockchain size if implemented?

Yes, as it is required to store the k on the blockchain. It could be in the range between 1-32 bytes, depending on the details of implementation.

Would there be any loss in privacy if such a scheme was to be used?

It depends. Let's consider some options:

1. Have k randomly generated and limit the size of it in a way that collisions are expected often. This would mean that there would be many transactions with the same k, but not neccessarrily belonging to the same user. Also, if it's generated randomly, distribution should be uniform. This allows for accidential or intentional re-use of the (C,D,k), which is not neccessarily a bad thing.

   • Consider we limit size of k to 1-byte. This would give each wallet 256 sub-addresses to work with. Once exausted, the user could start to re-use some old ones or archive the wallet and start using a new one. This way we have linear growth again, but slowed down 256 times, which may be just enough to preserve reasonable refresh time. Remember, the only reason HD wallets are inconvenient is the long refresh time it would take them.
   • Privacy would be preserved, but some loss of it would occur as we could assert that some transaction belongs to the group of users who decided to use the proposed scheme. In fact, we have the same kind of situation with payment ID now as some transactions have it and some don't.
   • If the protocol would enforce the k to be non-empty, then some random data could always be written in place of k when it would not be used, and it would completely preserve privacy while increasing the size of blockchain for a fixed amount / each tx. This way, every transaction would have a number 0-255 associated with it which would hint to the recipient which (c,d) to use.

2. Have the k randomly generated and of size big enough to avoid collisons. Also, re-use should be prohibited by the protocol.

   • In this case, collisions should be avoided entirely because if size of k is big enough. This is because it would be unlikely that 2 different users would happen to "roll" the same k, so one could assert that its more likely that any 2 transactions found on the blockchain belong to the same user because the (C,D,k) could have been re-used, accidentially or intentionally.
   • If we would enforce k to be unique, then any accidental collision would make the 2nd transaction fail to send if another one with the same k would get in a block first. The chance of this happening would be reduced with increasing the size of k.
   • Again, we have the potential loss of privacy if they're not enforced. Here, we'd increase the blockchain size more just because k has to be bigger for this option to work.

Also note that it may be better to opt for some deterministic scheme to generate k on the receiver end, like k=H(a,0..n). This way, the k would appear as random to the world, but the user would have a way to restore the list of (C,D)s issued in case he would lose the wallet file.

Would there be any risk to user funds?

It would depend on the implementation adapted. Imagine that the sender, for whatever reason, just sends to (C,D) and omits the k in the transaction data or puts a wrong one. If size of k is small enough, the receiver could attempt a fall-back method to try every k for each one-time public key. This way, his refresh time would be 128 times longer than usual, but he'd have a chance at recovering the funds. If allowed size of k was too big, the funds would probably be irrecoverable in some cases. In case deterministic ks were to be used, I guess it would mitigate this risk as well.

Is a protocol change required for this to work or could it be done entirely wallet-side?

Not required but it could be desired for some cases. If it was to be implemented using TX_EXTRA, then all it would need is to be supported by the sending and receiving wallets. Some new address scheme could be used to pass all the data (C,D,k) in one string to avoid accidents with omitting the k. Compatible wallets would be able to read this address, while others would just report an error.

Are there any other points to consider?

• There was talk about using payment ID as k and also consideration of using integratted addresses. Later it was realized that integrated addresses can't really work with this scheme as there is a chicken-egg problem involved in those :)
• There are surely different ways to go about generating (c,d) from (a,b,k) so this could use some further examination.
• There was a suggestion to look into bi-linear groups, but I can only mention it as I know nothing about this.
• Further consideration would be needed to see how this would fit together with payment IDs. Also, k should be protected from pruning, if it's ever implemented.
• Some other clumsy scenario with handling these kind of addresses?
• Some neat crypto-magic which could help in solving this in the most elegant way?
• What happens if we make a transaction sending to multiple addresses in the same tx?

Answer 2

It's something that we toyed about a while back, but it has one large disadvantage: such an address must not be reused (I assume the math behind that version is similar to the ones we were looking at). Reusing the address would mean only one of the outputs to that address would be spendable, so would be like burning monero.

Now, consensus rules could be changed at a later fork to prevent reuse. This would fix that issue, but would mean keeping a list of known one time pubkeys for quick lookup.

So yes, it is possible, and may be done at some point.

Answer 3

Just a few things I'd like to add:

1) This proposal should solve the problem of stealth address reuse. So address reuse here shouldn't be interpreted as reusing the public key of an output, which would be really bad and doesn't happen under the suggested construction. (Just to be clear about the difference: if a stealth address (A,B) is used to produce an output address P = H(rA)G + B, reusing (A,B) in two different situations would allow anyone that sees that to conclude that they were dealing with the same entity, so this is an off-chain concern. Reusing P, on the other hand, would mean that although there would be two outputs on the blockchain crediting P, only one of them could ever be spent, effectively burning whatever value was assigned to the other output; this is an on-chain concern.)

2) "Address reuse can be avoided by making sure to use a new value for k associated with a that hasn't appeared in the blockchain." It is not necessary to keep track of all the values of k that ever appeared in the blockchain. The same k combined with different stealth addresses (A,B) and (A',B') will produce new different stealth addresses. This is something to be taken care of in the level of the wallet that owns (A,B): it may, perhaps, keep track of only the k's that have been used for that address to make sure that they don't get reused with (A,B). (I believe that that is what the referred quote meant, by the way. I am just clarifying.) Also, maybe just making sure the value of k is being chosen in a random way could be enough (e.g. using the same sampler that generates the r values; and I believe the number of possible payment ID's available is big enough, assuming that that ends up being used as k). (Edit: I may have missed the point slightly here, by emphasizing that k can be chosen randomly. Although that is true, there is nothing wrong in using, for instance k = 1, 2, 3,..... as long as the same k is not repeated. The only information this might leak is that the transaction might involve and HD wallet address using this scheme, but nothing else I can think of.)

3) Something else that perhaps should be made more explicit is that this construction preserves the ability of an auditor, or a light client to view-only the transactions using just the view key (a,B) (and the public value of k) since that is the only information needed to check that P = H(a^{k+1}R)+a^k*B belongs to (A,B). (Something like defining d = b^{k+1}, for example, would still work to create one-time stealth addresses, but would break that nice property.)

These are just some of the nice points I see about this. I would really like to know if there is some objection to the security of this method, the feasibility of its implementation, its consistency with the development goals etc, because as far as I can see, this seems like a very good feature to implement, and the natural way of doing the function of HD wallets in Monero.

---

EDIT: Here is the bad aspect of this approach. Maybe it is fixable, but I don't see how yet. From IRC chat discussions:

The whole point of stealth addresses is to make transactions to the same sender unlinkable; that is, these transactions won't contain any information of hints that they were sent to the same address. However, in the this proposed scheme, k is being sent in the clear. So if the sender decides to send multiple transactions to the receiver, he will reuse k multiple times. If that happens, an external observer would be able to, if not outright link the transactions, then at least to attribute higher likelihood that they are linked!

Such a problem could be solved assuming k could be published in encrypted form, but that might increase the cost involved and defeat the point of doing it more efficiently than the naive HD approach of just keeping track of a bunch of keys (cost linear on the number of keys...).

What is needed is some kind of master cryptographic private key that could open various public keys for a low computational cost, if such a thing exists. Someone suggested looking into bilinear groups (I believe it was theking01). Anyways, last I saw, no one knew how to fix this yet, but please let me know if there has been any progress.