On Mon, Sep 19, 2016 at 09:13:40AM -0700, Tom Harding via bitcoin-dev wrote:
> 
> On 9/17/2016 9:20 PM, Peter Todd via bitcoin-dev wrote:
> > The probability that all N blocks are found by dishonest miners is q^N,
> 
> That's the probability that dishonest miners find N blocks in a row
> immediately.  What you want is the probability that they can build a
> chain N blocks long, taking the random-walk into account.
> 
> So use Satoshi's formula from bitcoin.pdf, section 11.  The results are
> remarkably different.  In particular, q=.5 is totally insecure, since
> for any N, both factions are guaranteed to eventually possess a chain of
> length N anchored at x at some point during the wild reorg melee.

Ah! That's a good point; my analysis only applies to the case where you're
assuming the dishonest miners aren't willing to lose revenue from the attack by
mining a less-work chain with blocks that won't end up in the main chain. I
should state that assumption more clearly.

If the dishonest miners are willing to spend money to create an invalid
timestamp the analysis is quite different. In OpenTimestamps a timestamp
doesn't contain the actual block headers - just a block height - so verifiers
are expected to have a working Bitcoin node. If that Bitcoin node is in sync
with the most-work work chain there's no risk: the blocks created by the
dishonest miners won't be part of the most-work chain, and validation of the
timestamp will fail.

In the case where the verifier is not in sync with the most-work chain, an
attacker can sybil attack the verifier's node and cause them to think that the
blocks committing the invalid timestamp are in fact the most-work chain. This
case is no different than a payee being sybil attacked, so we can use the same
analysis we would in that circumstance.

This also means that timestamps definitely shouldn't contain the block headers
of the blocks allegedly confirming them - that's an extremely weak proof given
the relative ease of creating a block, particularly when you take into account
that the same block could be used to create an unlimited number of fake
timestamps. OpenTimestamps doesn't do this, but it wouldn't hurt to make this
point 100% clear.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org