Date: Mon, 19 Sep 2016 13:56:15 -0400
From: Peter Todd <pete@petertodd.org>
To: Tom Harding <tomh@thinlink.com>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20160919175615.GA6360@fedora-21-dvm>
References: <20160918042001.GA9076@fedora-21-dvm>
	<7ff1a87d-2916-2024-ea05-d6413bd17767@thinlink.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="azLHFNyN32YCQGCU"
Content-Disposition: inline
In-Reply-To: <7ff1a87d-2916-2024-ea05-d6413bd17767@thinlink.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Subject: Re: [bitcoin-dev] Interpreting nTime for the purpose of
 Bitcoin-attested timestamps
Precedence: list


--azLHFNyN32YCQGCU
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Mon, Sep 19, 2016 at 09:13:40AM -0700, Tom Harding via bitcoin-dev wrote:
>=20
> 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,
>=20
> 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.
>=20
> So use Satoshi's formula from bitcoin.pdf, section 11.  The results are
> remarkably different.  In particular, q=3D.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 attac=
k 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 verifie=
rs
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. Th=
is
case is no different than a payee being sybil attacked, so we can use the s=
ame
analysis we would in that circumstance.

This also means that timestamps definitely shouldn't contain the block head=
ers
of the blocks allegedly confirming them - that's an extremely weak proof gi=
ven
the relative ease of creating a block, particularly when you take into acco=
unt
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 th=
is
point 100% clear.

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

--azLHFNyN32YCQGCU
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQEcBAEBCAAGBQJX4Ca8AAoJEGOZARBE6K+ynfAH/0MrTNV+QhmOribvTCnPct1s
KN/xOtd+zxpGOwGWEMDATnlnxGR38VBpIjuMwQtG8bu5Kshs+r11IdYAPQJDM7rJ
BKW2iJ/ybKvH93XQVeYA4wKpxHkJWMtaLY46pMtmvLk336leuPqEVdZAAVktzGgq
NY41chVECuNGseGpgwhikl2dCfd9aE93ClnwaQhdnspcdBWCK3BaqZn01UuVk312
js9xQiZolpDWEXObvkQ9lKKkp2MZv6DY8/h7gRKrTnKHxo0EErmkbfS4yBKoY536
F0s3HEcpAMGNRjJqdGQjyi1lwlSHw5uKXQWt5YIsGDgcaYI+xDvFpk57oklegDM=
=1iAE
-----END PGP SIGNATURE-----

--azLHFNyN32YCQGCU--