From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 88A5C98F for ; 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 ; 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 To: Tom Harding , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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--