1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
Return-Path: <pete@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 88A5C98F
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 19 Sep 2016 17:56:24 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail148113.authsmtp.com (outmail148113.authsmtp.com
[62.13.148.113])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 96C85113
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 19 Sep 2016 17:56:23 +0000 (UTC)
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232])
by punt21.authsmtp.com (8.14.2/8.14.2/) with ESMTP id u8JHuMBC099725;
Mon, 19 Sep 2016 18:56:22 +0100 (BST)
Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com
[52.5.185.120]) (authenticated bits=0)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id u8JHuGnX030480
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Mon, 19 Sep 2016 18:56:17 +0100 (BST)
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 0701040120;
Mon, 19 Sep 2016 17:52:35 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id 8413320306; Mon, 19 Sep 2016 13:56:15 -0400 (EDT)
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)
X-Server-Quench: 5d560af6-7e92-11e6-829e-00151795d556
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aAdMdwsUC1AEAgsB AmAbWlxeVVt7WGQ7 bghPaBtcak9QXgdq
T0pMXVMcUQ0SeVl2 WHYeURl2fwUIf3d1 bQhnCnVdXBUsc1t6
F0dWCGwHMGF9YGIW BV1YdwJRcQRDe0tA b1YxNiYHcQ5VPz4z
GA41ejw8IwAXCSJJ TxsVN18OQEAEVjgA RhUPVTsoBwUZRyh7
NwE8MlkHEQ4WPCd6 G1o9UlUZNVobFhFT BF1ADGdFJlwMXDYi CBtBNQAA
X-Authentic-SMTP: 61633532353630.1037:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 52.5.185.120/25
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Interpreting nTime for the purpose of
Bitcoin-attested timestamps
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 19 Sep 2016 17:56:24 -0000
--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--
|
