public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Peter Todd <pete@petertodd.org>
To: Tom Harding <tomh@thinlink.com>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Interpreting nTime for the purpose of Bitcoin-attested timestamps
Date: Mon, 19 Sep 2016 13:56:15 -0400	[thread overview]
Message-ID: <20160919175615.GA6360@fedora-21-dvm> (raw)
In-Reply-To: <7ff1a87d-2916-2024-ea05-d6413bd17767@thinlink.com>

[-- Attachment #1: Type: text/plain, Size: 2311 bytes --]

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

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

  reply	other threads:[~2016-09-19 17:56 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-09-18  4:20 [bitcoin-dev] Interpreting nTime for the purpose of Bitcoin-attested timestamps Peter Todd
     [not found] ` <CABeL=0jSQsdyRFAUheQ9XSi1krM=PLFAARLXE8Du55FFkX8vZg@mail.gmail.com>
2016-09-18 16:05   ` Peter Todd
2016-09-19 16:13 ` Tom Harding
2016-09-19 17:56   ` Peter Todd [this message]
2016-09-19 19:53     ` Tom Harding

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20160919175615.GA6360@fedora-21-dvm \
    --to=pete@petertodd.org \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=tomh@thinlink.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox