Limit auxPOW timestamp differences (core/protocol/SPV) ?

Namecoin, NMControl
Post Reply
phelix
Posts: 1631
Joined: Thu Aug 18, 2011 6:59 am

Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by phelix » Tue Nov 24, 2015 3:57 pm

Currently the timestamps of a Bitcoin parent block and a merge mined Namecoin block are independent. Limiting the maximum allowed difference would increase SPV security. This would also increase the significance of a chain snippet of a couple of block headers.

At the moment a malicious Bitcoin miner can work on a fake Namecoin blockchain with arbitrary timestamps. If we would limit the allowed timestamp difference miners would be forced to use Namecoin timestamps close to the parent block Bitcoin timestamps.

Honest miners should not really be affected. More than 99.5% of timestamp differences are within -300 and +2000 seconds difference.

Timestamp differences distribution over last 50k blocks (two large negative data points removed):

Histogram edges: [ -289. 443.4 1175.8 1908.2 2640.6 3373. 4105.4 4837.8 5570.2 6302.6 7035. ]
Number of entries in bin: [41502 7388 914 147 35 7 3 1 0 1]
" %: [ 8.30073203e+01 1.47765911e+01 1.82807312e+00 2.94011760e-01 7.00028001e-02 1.40005600e-02 6.00024001e-03 2.00008000e-03 0.00000000e+00 2.00008000e-03]

n: 49998
max: 7035 at 219563
min: -289 at 216902


This is not an urgent issue but something to ponder.


Messy code to play with is attached (depends on namerpc, e.g. from nameGUI).
Attachments
auxpow_timing2.txt
(2.36 KiB) Downloaded 107 times
nx.bit - some namecoin stats
nf.bit - shortcut to this forum

domob
Posts: 1119
Joined: Mon Jun 24, 2013 11:27 am
Contact:

Re: Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by domob » Wed Nov 25, 2015 6:38 am

Sounds like an interesting idea - but I have not thought about the details. It is probably not too hard to implement, and would amount to a softfork. We should, however, thoroughly analyse the various ways for miners to attack SPV with and without this change to see if it really does what it should and cannot easily be avoided.
BTC: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS
Use your Namecoin identity as OpenID: https://nameid.org/

biolizard89
Posts: 1977
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by biolizard89 » Thu Nov 26, 2015 9:52 am

I'm not sure I follow how specifically this is a security issue. @phelix, what attacks on SPV are you thinking of?
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

johnc
Posts: 89
Joined: Sun Dec 28, 2014 10:03 am

Re: Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by johnc » Fri Dec 18, 2015 5:59 am

biolizard89 wrote:I'm not sure I follow how specifically this is a security issue. @phelix, what attacks on SPV are you thinking of?
phelix wrote: If we would limit the allowed timestamp difference miners would be forced to use Namecoin timestamps close to the parent block Bitcoin timestamps.
If it's possible seems like a improvement in security against fake chains.

biolizard89
Posts: 1977
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by biolizard89 » Fri Dec 18, 2015 7:23 am

johnc wrote:
biolizard89 wrote:I'm not sure I follow how specifically this is a security issue. @phelix, what attacks on SPV are you thinking of?
phelix wrote: If we would limit the allowed timestamp difference miners would be forced to use Namecoin timestamps close to the parent block Bitcoin timestamps.
If it's possible seems like a improvement in security against fake chains.
Do you have a specific example?
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

johnc
Posts: 89
Joined: Sun Dec 28, 2014 10:03 am

Re: Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by johnc » Fri Dec 18, 2015 11:40 am

biolizard89 wrote: Do you have a specific example?
Let's say a big mining pool starts mining namecoin from the beginning, they use fake timestamps and low difficulty, then they create a longer namecoin chain with misleading info for the SPV clients that only check headers. Then they promote their service for SPV clients while executing a MITM attack.

I think it was called timetravel attack and it was fixed but it seems SPV clients are vulnerable. This pach will make this attack uneconomical because they will have to fake bitcoin headers too.

phelix
Posts: 1631
Joined: Thu Aug 18, 2011 6:59 am

Re: Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by phelix » Sat Dec 19, 2015 5:04 pm

johnc wrote:
biolizard89 wrote: Do you have a specific example?
Let's say a big mining pool starts mining namecoin from the beginning, they use fake timestamps and low difficulty, then they create a longer namecoin chain with misleading info for the SPV clients that only check headers. Then they promote their service for SPV clients while executing a MITM attack.

I think it was called timetravel attack and it was fixed but it seems SPV clients are vulnerable. This pach will make this attack uneconomical because they will have to fake bitcoin headers too.
Something in this direction. SPV clients IIRC do compare the total amount of work, though, not chain length.

Another viewpoint on this: are we sure the current behavior is safe? It is difficult to say because it is a complex issue with lots of edge cases. Linking timestamps would add a rule but it seems to me it would simplify the system and make it potentially more robust.
nx.bit - some namecoin stats
nf.bit - shortcut to this forum

biolizard89
Posts: 1977
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by biolizard89 » Mon Dec 21, 2015 9:41 pm

phelix wrote:
johnc wrote:
biolizard89 wrote: Do you have a specific example?
Let's say a big mining pool starts mining namecoin from the beginning, they use fake timestamps and low difficulty, then they create a longer namecoin chain with misleading info for the SPV clients that only check headers. Then they promote their service for SPV clients while executing a MITM attack.

I think it was called timetravel attack and it was fixed but it seems SPV clients are vulnerable. This pach will make this attack uneconomical because they will have to fake bitcoin headers too.
Something in this direction. SPV clients IIRC do compare the total amount of work, though, not chain length.
I don't see an attack here, for exactly the reason Phelix says: the longest blockchain is the one with the most work, not the one with the most blocks. If that weren't the case, then Bitcoin would be broken too. Does anyone have a link to info on the Time Travel attack?
phelix wrote:Another viewpoint on this: are we sure the current behavior is safe? It is difficult to say because it is a complex issue with lots of edge cases. Linking timestamps would add a rule but it seems to me it would simplify the system and make it potentially more robust.
Adding the rule doesn't appear on first glance to be harmful. And if does add a bit more consistency. I just don't see an attack either way. (Obviously I could be missing something.)
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

biolizard89
Posts: 1977
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Limit auxPOW timestamp differences (core/protocol/SPV) ?

Post by biolizard89 » Sun Sep 25, 2016 7:28 am

Okay, I'm thinking out loud here, so don't take this as an endorsement of any ideas.

I think I see an attack that is made much more difficult by this proposed softfork. Here's how it works.

Glenn registers a Namecoin name, and waits a little while before setting up a website for it. Keith discovers Glenn's Namecoin name after the website is set up. By this time, the timestamp requirements for new Namecoin blocks (based on proximity to new Bitcoin blocks' timestamps) are noticibly different from what they were when Glenn registered his name.

Keith hates Glenn's website and wants to steal Glenn's name.

If this softfork is not in effect, Keith can bribe Bitcoin miners who control a majority of Namecoin hashpower to mine a hostile fork of the Namecoin chain, with the fork point being right before Glenn's registration. The forked chain will then eventually overtake the legit Namecoin chain, at which point Keith will control Glenn's name. Note that this isn't necessarily an expensive attack -- bribing miners to attack Namecoin is a lot easier than bribing them to attack Bitcoin, since the Namecoin block reward's real-world value is much lower.

It is relatively accepted that in the event of a very long chainfork (let's say 2 weeks to a month deep), an emergency softfork would be deployed that nukes the chain that was created later. A Bitcoin or Namecoin client very well could be configured to intentionally shut down and demand manual user intervention when it detects such a chainfork.

However, here's where the timestamp softfork helps. If the Ed (an end user) is forced to take a manual action to decide which side of the chainfork is valid, then if the timestamp softfork is active, Ed will be choosing between a chain that has normal-looking headers, and a chain that has a giant gap in its timestamps that corresponds to the period between Glenn's registration and when Keith started mining a hostile chainfork.

This information is not reliable enough to automatically choose the correct chain; there are perfectly legit reasons why there might be gaps in a chain (e.g. the Aggregator incident). However, it makes it *much* easier for humans to analyze the two sides of the fork and convince everyone involved which chain is valid.

Of course, Keith could circumvent this by mining Bitcoin blocks that don't build on the latest Bitcoin block. But that increases Keith's costs by a lot, because bribing miners to attack Bitcoin now means that the miners are risking the Bitcoin block reward in addition to the Namecoin block reward. In effect, we can take the Bitcoin blockchain hostage, because we know that most miners won't dare to attack it.

You might be pointing out now that since the Bitcoin timestamps are in both sides of the fork, we can do this analysis anyway. You are correct, as long as Bitcoin is the AuxPoW parent chain. If Bitcoin and Namecoin both end up as AuxPoW chains with a common parent (as Luke-Jr has proposed as a Bitcoin hardfork), then we would be depending on block headers of an AuxPoW parent chain whose timestamps have little to no economic value -- unless both Namecoin and Bitcoin implement this proposed softfork, so that Namecoin and Bitcoin timestamps are tied together by this softfork using the parent chain as a proxy.

So obviously this softfork doesn't really matter for the above attack as long as Bitcoin keeps their current DMMS. But I think it's worth considering for the future.

Is my 2 AM logic accurate?

(Thanks go to midnightmagic for a discussion earlier that loosely inspired this 2 AM brain dump. Midnightmagic isn't responsible for any stupidity I might have written here.)

EDIT: it occurs to me that we could also require the Bitcoin coinbase block height to be monotonically increasing as Namecoin block height increases. Or a weaker variant where e.g. the median of the last N Bitcoin coinbase block heights in the Namecoin chain must be monotonically increasing. It's unclear to me exactly how this compares to the security of using timestamps.

EDIT 2: using the Bitcoin coinbase block height assumes that the parent chain of Namecoin never changes. Right now this seems pretty reliable (Bitcoin isn't dying anytime soon), but it's a pretty strong assumption that I don't feel comfortable betting on at the moment.
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

Post Reply