Return to Answer

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.

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).

3. Something else that perhaps should be made more explicit is that this construction preserves the ability of an auditor, or a light client toview-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.

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.

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. Maybe the wallet that owns (A,B) could keep track of the k's that have been used for that address only to make sure that that k is not 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 is big enough, assuming that that ends up being used as k).

3. Something else that perhaps should be made more explicit is that this construction preserves the ability of an auditor, or a light client 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 d = b^{k+1}, for example, would still work to create one-time stealth addresses but would break that.)

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.

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).

3. Something else that perhaps should be made more explicit is that this construction preserves the ability of an auditor, or a light client toview-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.