Privacy leaks with update-expiring?

[JeremyRand]

Hi,

I'm concerned that update-expiring might leak information about which names are owned by the same wallet, based on the fact that it might cause multiple name renewals to be mined in the same block with near-identical timestamps. Do you have thoughts on how this could be mitigated?

(Obviously graph analysis can still find some useful private data regardless. But we should be trying to eliminate sources of analysis where feasible, I think.)

Cheers!

[clehner]

I agree, it might not be desirable to associate names owned by different addresses in the same wallet. One way to address this would be to specify let the command take an argument for which names to renew, or which address's names to renew. Then a user could separately update the different sets of names, at different times.

Do you think specifying names or addresses would be more useful? Multiple names owned by the same address are already publicly associated, right? Wildcards/globbing could also be used.

Edit: Another idea would be to make renewing non-deterministic. i.e. instead of renewing all names with expiration within N blocks, randomly renew each name with a probability approaching 1 as N approaches 0. This would make it less likely that multiple names would get renewed at the same time.

[JeremyRand]

(So sorry for delayed reply -- been pretty busy with school.)

Multiple names owned by the same address are probably already associated, unless it's an ECDH address. (No Namecoin client supports ECDH addresses yet.) However, it's unlikely that two names will be owned by the same address, because the default behavior for Namecoin-Qt is to create a new address for each name_update operation. So I think treating each name as unique will be optimal.

Something non-deterministic would probably be sufficient. One method would be to pick 1 random name which expires in less than N blocks, and renew it. This would have a small risk of never renewing a name if there are a lot of names in the wallet. Another method would be to pick 1 random name from the set of names which are oldest by block height. This has a risk of revealing a little bit of information about which names might have a common owner, if a blockchain observer is watching the order that names are renewed in. Making the probability dependent on the block age might add some obfuscation, but I'm not sure how well it truly removes the information. Another possibility is combining the first two methods I listed -- pick a random name with less than N blocks to expire, unless there are one or more names with less than M blocks to expire, in which case pick one of the oldest ones. This might still leak information if a blockchain observer is looking for names which are renewed near a common age.

The statistical analysis here can get kind of complicated. Thoughts?

[clehner]

On Sat, 17 Oct 2015 17:33:52 -0700 JeremyRand notifications@github.com wrote:

(So sorry for delayed reply -- been pretty busy with school.)

Multiple names owned by the same address are probably already associated, unless it's an ECDH address. (No Namecoin client supports ECDH addresses yet.) However, it's unlikely that two names will be owned by the same address, because the default behavior for Namecoin-Qt is to create a new address for each name_update operation. So I think treating each name as unique will be optimal.

Ok, that's reasonable.

Aside: an optimization for mining fees would be to bundle updates together for names owned by the same address or that the user doesn't mind associating.

Something non-deterministic would probably be sufficient. One method would be to pick 1 random name which expires in less than N blocks, and renew it.

This is what I was thinking, except with giving greater weight to names closer to expiration, e.g. weight = 1/d for d days to expiry, to minimize chance of accidental expiration.

This would have a small risk of never renewing a name if there are a lot of names in the wallet.

Yes. The script could adjust the expiration threshold based on the number of names and the run time interval, but even then there could be names clustered together in time which would not all be able to be renewed unless multiple ones were renewed per run (possibly with random time delays between them).

It might be better to let the renewal script run continuously, and schedule its own renewals, than rely on it being called by cron at specific times - besides, if it is running daily from crontab, the names in the wallet could be correlated by their being renewed repeatedly at the same time of day. However, if the script runs continuously, then it has to either 1. leave the Namecoin wallet unlocked for long periods, 2. prompt the user periodically for the password to unlock it, or 3. store the password in memory after the first prompting - neither option being desirable. Although with a cron script 1 or 2 are already needed.

Another method would be to pick 1 random name from the set of names which are oldest by block height. This has a risk of revealing a little bit of information about which names might have a common owner, if a blockchain observer is watching the order that names are renewed in. Making the probability dependent on the block age might add some obfuscation, but I'm not sure how well it truly removes the information. Another possibility is combining the first two methods I listed -- pick a random name with less than N blocks to expire, unless there are one or more names with less than M blocks to expire, in which case pick one of the oldest ones. This might still leak information if a blockchain observer is looking for names which are renewed near a common age.

Weighted random would tend to pick the oldest names first, but with some "coarseness" depending on the run interval.

The statistical analysis here can get kind of complicated. Thoughts?

The desired behavior is to make it look like each name is being renewed by a different actor, in isolation, according to its own schedule. So the chance of one name being renewed during a given interval should not affect the chance of another name being renewed during that interval. Limiting renewals by the script to one per some time interval breaks that property, which becomes more obvious when the time interval is larger. So I think a better solution would be to have the script run continuously instead of at intervals, so it has more flexibility in scheduling renewals, and can schedule them "independently".

In summary:

Stop-gap solution: add a CLI option to nct to specify renewing just 1 name nearing expiration instead of all of them. Apprise the user of the risk of accidental expiration or correlation in cases of "too many" names expiring in a time interval.

Long-term solution: make another renewal daemon program, in a systems language, that renews names or at least notifies the user when to renew names, without correlating them in time more than necessary (IP address of transactions notwithstanding).