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 2930C92 for ; Sun, 18 Sep 2016 04:20:09 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from outmail148110.authsmtp.com (outmail148110.authsmtp.com [62.13.148.110]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id CE7421A2 for ; Sun, 18 Sep 2016 04:20:07 +0000 (UTC) Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232]) by punt20.authsmtp.com (8.14.2/8.14.2/) with ESMTP id u8I4K6P4087827 for ; Sun, 18 Sep 2016 05:20:06 +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 u8I4K34C021964 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sun, 18 Sep 2016 05:20:03 +0100 (BST) Received: from [127.0.0.1] (localhost [127.0.0.1]) by petertodd.org (Postfix) with ESMTPSA id 02B04400DB for ; Sun, 18 Sep 2016 04:16:23 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id 93B7520850; Sun, 18 Sep 2016 00:20:01 -0400 (EDT) Date: Sun, 18 Sep 2016 00:20:01 -0400 From: Peter Todd To: bitcoin-dev@lists.linuxfoundation.org Message-ID: <20160918042001.GA9076@fedora-21-dvm> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="pf9I7BMVVzbSWLtt" Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) X-Server-Quench: 2c6d2a75-7d57-11e6-829e-00151795d556 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd P1hyKltILEZaQVBf Ri5dBBEKBAw1ADwr dVUTOktcalUtCkV1 UkhIREJSEQ9qARYB AlAbUAd3aQROfWBx Z0Z9XHVEXQo/fT95 OU1QZm0EZG5mbC4W WEJYOQEHdldILxhA d1crUXQQYGRSYGdo RV4+emhpZGgGd3UI TlxQc0QzR1oGBCYm SgwDGzpnG3EEQih7 IRs8YkIcEQ4JL18q NkAsEVUWezUTFgZZ HkcICTNFKkIdSiZj EQJfUFUCGThFWk8C 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: [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: Sun, 18 Sep 2016 04:20:09 -0000 --pf9I7BMVVzbSWLtt Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable As part of my recent work(1) on OpenTimestamps I've been putting some thoug= ht towards how to interpret the nTime fields in block headers, for the purpose= of timestamping. I'd like to get some peer review on the following scheme I've come up with. # Motivation We want to use the Bitcoin blockchain to provide evidence (the "attestation= ") that a message M existed prior to some point in time T. Exactly how we do t= his is beyond the scope of this post, but suffice to say we show that some block header b cryptographically commits to the message, e.g. via a commitment operation path proof, as implemented by OpenTimestamps. A valid timestamp is simply one where T is a point in time where the message did in fact exist. Of course, if a timestamp for time T is valid, all subsequent T+d are also valid; such timestamps are simply more conservative versions of the same statement. A naively approach - as is implemented by most (all?) existing Bitcoin timestamping schemes - is to assume that the block header's nTime field was perfectly accurate, and thus M exists prior to the block's nTime. But that doesn't take into account malicious miners, who may backdate their blocks. # Threat Model We assume miners are divided into two categories: 1) Dishonest Miners --- These miners are actively conspiring to create inva= lid timestamps for time's prior to when the message existed. A dishonest miner = will set the nTime field in blocks they create to the minimum possible value. 2) Honest Miners --- These miners set nTime in blocks they create to approximately the current true time. An honest miner may use techniques suc= h as nTime-rolling. Additionally, all honest miners may be simultaneously affect= ed by systematic misconfigurations. ## nTime Rolling Prior to BIP113, reducing a block's nTime from the work given by a pool by = even a second could easily render it invalid, as the pool may have included nLockTime'd transactions in the block. Thus hashing software was designed to only roll nTime in the forward direction, not reverse, even though rolling could be done in the reverse direction, up to the limit of the median-time-= past + 1. The Stratum mining protocol doesn't even have a way to tell clients what the minimum allowed time is, just a single field, nTime, which is defined as "t= he current time". Thus Stratum hashers will only ever increase nTime, which can never result in an invalid timestamp if the original, unrolled, nTime would have been a valid timestamp. The getblocktemplate protocol does support telling hashers the minimum time= via the mintime field, which Bitcoin Core sets to the median-time-past. Regardl= ess, it appears that the pools supporting GBT (Eligius) return a much tighter li= mit on mintime than the median-time-past, just 180 seconds, and as of writing, don't actually declare that the ntime field is mutable anyway. =46rom an implementation point of view, relying on being able to roll nTime backwards is unwise anyway, as the amount you can roll it back may be minim= al (e.g. if multiple blocks were recently found). Since all miners have an incentive for time to move forward to keep difficu= lty down it's reasonable to assume that the above observed behavior will contin= ue, and nTime rolling in the reverse direction will be a minimal effect; we'll assume no miner rolls nTime backwards more than 1 hour. ## Systematic Errors 1) Botched daylight savings time changes --- While internal clocks should be unaffected by timezone changes, it's plausible that some kind of mistake related to daylight savings could result in the time being set incorrectly = +- 1 hour. For example, multiple large miners might manually set their clocks, b= ased on an incorrect understanding of what time it was. 2) Broken NTP servers --- It's reasonable to assume that many miners are us= ing NTP to set their clocks, and it's plausible that they're using the same NTP servers. Of course, a broken NTP server could return any time at all! The Bitcoin protocol considers blocks to be valid if nTime is set up to 2 hours= in the future (from the perspective of the local node) so we'll say instead th= at we expect systematic NTP errors to be corrected with high probability if they're more than 2 hours in magnitude - more than that and the Bitcoin net= work is broken in a very visible way anyway. Thus, we'll assume honest miners always create blocks with nTime greater th= an the true time minus two hours, which accounts for both likely daylight savi= ngs time misconfigurations, and likely NTP server misconfigurations. Additional= ly, two hours is greater than any expected effects from nTime rolling. # Proposed Algorithm For a timestamp anchored at a block of height x we'll define the time T it represents as: T =3D max(block[i].nTime for i in {x, ..., x + N-1}) + max_offset In short, T is the maximum nTime out of the N blocks that confirmed the timestamp, including first block that actually committed the timestamp; max_offset is the maximum nTime offset we expect from a block created by an honest miner, discussed above. The dishonest miners can successfully create an invalid timestamp iff all N blocks are found by them; if any block is found by an honest miner, the nTi= me field will be set correctly. Of course T may not be the minimum possible va= lue, but the timestamp will be at least valid. So how big should N be? Let q be the ratio of dishonest miners to total has= hing power. The probability that all N blocks are found by dishonest miners is q= ^N, and thus the probability P that at least one block is found by an honest mi= ner is: P =3D 1 - q^N =3D> N =3D log(1 - P)/log(q) If the dishonest miners have q>0.5, the situation is hopeless, as they can reject blocks from honest miners entirely; the only limit on them setting n= Time is the median-time-past rule, which only requires blocks timestamps to increment by one second per block (steady state). Thus we'll assume q=3D0.5= , the worst possible case where a Bitcoin timestamp can still be meaningful evide= nce: P =3D 97% =3D> N =3D 5 P =3D 99% =3D> N =3D 7 P =3D 99.9% =3D> N =3D 10 P =3D 99.99% =3D> N =3D 14 P =3D 99.999% =3D> N =3D 17 P =3D 99.9999% =3D> N =3D 20 The reliability for the higher N is higher than the actual reliability of Bitcoin itself. On the other hand, there's no known instance where miners h= ave ever created blocks with nTime's significantly less than true time on a wide scale; even in the well-known cases where the Bitcoin network has temporari= ly failed due to forks, timestamps produced during those times would be valid,= if delayed by a few hours. Similarly, if we assume a lower q, say a single "rogue" 20% mining pool, we get: q =3D 0.20, P =3D 99.99% =3D> N =3D 6 Another way to think about the choice of N is to compare its contribution to how conservative the timestamp is - T as compared to the true time - to the effect of the max-honest-miner-offset we choose earlier. For example, 98% of the time at least 6 blocks will be found within 2 hours, which means that i= f we pick N=3D7, 98% of the time the conservatism added by N will be less than t= he contribution of the max offset. # UI Considerations One problem with the above algorithm is that it will frequently return timestamps in the future, from the perspective of the user. A user who sees= a message like the following at 2:00 pm, immediately after their timestamp confirms, is understandably going to be confused: Bitcoin: 99% chance that existed prior to 4:00 pm, Jan 1st 2016 A reasonable approach to this problem might just to refrain from displaying timestamps at all until the local time is after the timestamp; the UI could describe the timestamp as "Not yet confirmed" It may also be reasonable to round the timestamp up to the nearest day when displaying it. However what timezone to use is a tricky issue; people rarely expect to see timezones specified alongside dates. Of course, in some cases a less conservative approach to interpreting the timestamp is reasonable; those users however should be reading and understanding the calculations in this post! # References 1) https://petertodd.org/2016/opentimestamps-announcement --=20 https://petertodd.org 'peter'[:-1]@petertodd.org --pf9I7BMVVzbSWLtt Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQEcBAEBCAAGBQJX3hXuAAoJEGOZARBE6K+ykVAH/2r+89oHoXNCfOcXY82Uwze5 xvoruiB9JLJvIhwse/hoiwXyJHAyIcVDXmn+soWqgTVo9SZ8KNfQvma/fRrcNQ1B oqvENeq4aB01FS/+AtSOV7FVyT7JylcTaUhbpkF2O0a95n9ljd+FJ96Km964TLHQ tmNguIFky87K6mk3fwRbU9WIhg3aw1kUHMUO/5WJiyZpXF0a0yPAlLpXI6ww19ex H4u+5t9YzJo2XrRip2PVMlFyJeqAk1tuzyf72HSGjwkOgzwyEZzlLyfNsTg2WCqr s6+m78hQuWfOzKM8YXYHqDE5+qJ69ODD0G3vc4FAi7AsiwJIHCxkjX9X4Ir3hkc= =5xWD -----END PGP SIGNATURE----- --pf9I7BMVVzbSWLtt--