14

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?
  • I've flagged this for closing, but it is an interesting topic. However, SE is not really the place for this kind of discussion. Reddit, IRC or maybe SE chat is better suited. For SE, the question should be specific so it can be possible to give a definite answer. – JollyMort Oct 25 '16 at 1:24
  • @JollyMort: I understand the desire to have more or less simple Q&A in SE, but I IMHO we shouldn't be too strict with that when it comes to a new technology that, gladly, is still under great development. Asking about the viability of a certain approach creates the opportunity for people to learn more about the current underpinnings, goals and restrictions of Monero protocol, client etc. – user141 Oct 25 '16 at 13:28
  • It's not just my desire. I don't mind having a quality discussion anywhere, but it's the SE rules which give this guidance. Already this post is a mess because it's inadequate format for a discussion. Imagine being a newcomer and trying to make sense of this page... anyway, now that some discussion and clarification occured, we could think about how to present the idea in a clear Q&A format ie. "Would it be possible to do x to achieve y", and the answed would cover all the benefits, drawbacks or tech. limits which were talked about. – JollyMort Oct 25 '16 at 19:55
  • ok edited a bit to give an actual question, I think we can make it work :) I'll try and write-up a summary of what was discussed as an answer – JollyMort Oct 25 '16 at 20:20
8

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?
  • This is a great summary, thank you! I am glad that this generated so much interest. – user141 Oct 26 '16 at 1:28
3

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.

  • 1
    Sender chooses random r and sends R=rG along with the transaction just the same. From what I can see, (C,D) is just a stealth address like any other, except in that we derived it's private keys from those of (A,B), but I don't see how that would have any impact. So that the sender sends XMR to P = H(rC)G+D = H(r*a^{k+1}G)G+(a^k*b)G so that x = H(r*a^{k+1}G)+(a^k*b) is the one time private key to that address, and it depends on the random r, as usual. I don't see the reuse. Could you tell me what I am missing? – user141 Oct 23 '16 at 20:25
  • 2
    If the sender picks a random each time, then it doesn't have that problem. I don't know much about the crypto so I can't really comment on that specific set of steps. – user36303 Oct 23 '16 at 21:20
2

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.

  • I think there's a misconception of what stealth addresses are. They're something generated from wallet addres + some random data, and are thus never re-used. This proposal doesn't change this, as you'll be deriving a, let's call it, sub-address from wallet addres + k, and then the stealth address is generated from this sub-address + some random data. The sub-address could be made into a self-standing monero wallet, too, as it's no different than what we use now (except for the link to the main one, using k). – JollyMort Oct 24 '16 at 20:35
  • @JollyMort: I see your point that the naming could be switched. However, I couldn't find explicit mentions of the term stealth address in the Cryptonote or RingCT papers, and from Moneropedia on stealth addresses: "[Stealth addresses] allow and require the sender to create random one-time addresses for every transaction on behalf of the recipient", getmonero.org/knowledge-base/moneropedia/stealthaddress. So I think my use of the term is at least consistent with Moneropedia. Could you give a reference from where you take your definition? – user141 Oct 25 '16 at 12:53
  • Sorry, it was actually me misusing the term. Stealth address is any Monero address and is called stealth because funds are never sent to it but to the one-time destionation generated from it by the sender, as you write above. – JollyMort Oct 25 '16 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.