From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1UaG78-00070z-TD for bitcoin-development@lists.sourceforge.net; Thu, 09 May 2013 01:57:46 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.84 as permitted sender) client-ip=62.13.149.84; envelope-from=pete@petertodd.org; helo=outmail149084.authsmtp.net; Received: from outmail149084.authsmtp.net ([62.13.149.84]) by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1UaG77-00051A-BT for bitcoin-development@lists.sourceforge.net; Thu, 09 May 2013 01:57:46 +0000 Received: from mail-c233.authsmtp.com (mail-c233.authsmtp.com [62.13.128.233]) by punt8.authsmtp.com (8.14.2/8.14.2/Kp) with ESMTP id r491vZp4066313; Thu, 9 May 2013 02:57:35 +0100 (BST) Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id r491vWLY059297 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Thu, 9 May 2013 02:57:34 +0100 (BST) Date: Wed, 8 May 2013 21:57:31 -0400 From: Peter Todd To: John Dillon Message-ID: <20130509015731.GA26423@savin> References: <20130508234422.GA30870@savin> <20130509011338.GA8708@vps7135.xlshosting.net> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="UlVJffcvxoiEqYs2" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: d180dd4a-b84b-11e2-a49c-0025907707a1 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aQdMdgsUFVQNAgsB AmUbW1ZeVVp7WmY7 bAxPbAVDY01GQQRq WVdMSlVNFUsqBRUA QHliOxl3fgdPfzBy YkZjWD4PXUx6IRJ5 E1MGHWlUeGZhPWIC AURRJB5UcAFPdx9C bVB4BXJDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA5QRHYi XFhcQXAlHFFNWyQ2 Igc6I1sEVEgQP0E+ KjMA X-Authentic-SMTP: 61633532353630.1021:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 SPF_PASS SPF: sender matches SPF record X-Headers-End: 1UaG77-00051A-BT Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] 32 vs 64-bit timestamp fields X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 09 May 2013 01:57:47 -0000 --UlVJffcvxoiEqYs2 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Thu, May 09, 2013 at 01:27:33AM +0000, John Dillon wrote: > > There's also no need: 32 bits is plenty of precision. Hell, even 16 bit= s would > > do (assuming there's never more than a 65535s (about 18 hours) gap betw= een two > > blocks). Just assume the "full" 64-bit time is the smallest one that ma= kes > > sense, given its lower 32 bits. >=20 > I feel somewhat uncomfortable about the "after-the-fact" auditing possibl= e in > this scenario. Besides the timestamping provided by the block headers app= ears > to be useful in some payment protocols, not to mention in general. Remember that interpreting the timestamp on a block for the purposes of timestamping is a lot more subtle than it appears at first. Any node will accept a block with a timestamp no more than two hours ahead of what it thinks the current time is. That time is adjusted by the median of the timestamps reported by your peers. For instance the RPC call getinfo returns, among other things: { "timeoffset" : -1, } That is saying my node's wall clock time is 1 second behind the median reported by it's peers - pretty good! Naively you might think this means block timestamps are accurate to within 2 hours right? Well, it's not so simple. Nodes will accept any block with any timestamp *after* the median of the last 11 blocks. From CBlock::AcceptBlock(): // Check timestamp against prev if (GetBlockTime() <=3D pindexPrev->GetMedianTimePast()) return state.Invalid(error("AcceptBlock() : block's timestamp is to= o early")); So in theory a miner could prevent that block from moving forward, although if they do they drive up the difficulty, so all miners have an incentive to set the timestamp accurately. There are two types of timestamps possible: proofs that data existed before a time, and proofs that data existed after. With the former type the *later* the proof says the data existed, the more conservative the assumptions behind the proof. So simply adding two hours to the block's timestamp is relatively reasonable. (this assumes the attack managed to mine a single block, and all nodes have accurate clocks) The latter type, where you prove data existed after a given time, is a much more tricky thing to apply. The genesis block is a great example with that famous newspaper headline: The Times 03/Jan/2009 Chancellor on brink of second bailout for banks As I mentioned in my other (private) email to you a few minutes ago, the sig of my emails has the latest block hash in each one. The basic idea is called a random beacon; NIST has a good description and a project to create one: http://www.nist.gov/itl/csd/ct/nist_beacon.cfm Now technically speaking a random beacon is actually a more sophisticated concept than just timestamping, the random beacon's value is public and distributed widely, but for timestamping the idea is basically to have an unpredictable number known to have been produced at a certain time. So you know this email was written after block #235235, timestamp 2013-05-09 01:21:52 right? Not so fast. All you actually know is the PGP *signature* was created after that time, because the actual text of the email is independent of the beacon nonce. (dunno if I have the correct terminology here FWIW) For a blockchain it's easy enough, the blocks naturally depend on a genesis block, but applying the concept more generally is tricky and application dependent; consider for example proving you created a keypair after some data, which might be a useful thing to prove if the secret key was created in some tamperproof hardware that you know has left the factory and is in your possesion. It's easy to see how to do this with ECC: just use the same techniques as in HD wallets to derive keys. To use the blockchain as a secure random beacon you need to make two assumptions, 50% of the hashing power is controlled by honest miners, and those honest miners have accurate clocks. With those assumptions you can work out what is the minimum possible time the block could have been accepted by the GetMedianTimePast() function and you are good to go. What do people do in practice? Well look at http://vog.github.io/bitcoinproof/, they just give the timestamp and nothing else. Same for OpenTimestamps. (although I'm adding this email to my notes, half the reason it's so detailed...) Back to the block header time... Frankly, the easiest thing to do is just have a flag day where blocks after a certain height are considered to have a different epoch from the standard 1970 one when computing their time. Boring, but it works fine and only needs to be updated every few decades. You're midstate idea is very clever though and could come in handy in the future for different purposes. Eventually we should discuss this with the ASIC manufacturers - if it can be implemented as a firmware or FPGA upgrade in the field all the better. --=20 'peter'[:-1]@petertodd.org 000000000000010a10e05e172442e0675a818d17b62c1ed041a4572002ca051e --UlVJffcvxoiEqYs2 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQEcBAEBCAAGBQJRiwKLAAoJECSBQD2l8JH7VzQH/2cOS+W4LQ0SbMj9u2uxUpTC OZJV5IMM3/lLkKXPbJeq12Usvdzp7odGLTGHtjG+Ywo+2TZdoqnkVRGMgFOcAlpJ XmGmq8m4Ie+Rg/S6bLkJ4wMBQmuFA+IAj+lmW/B5XwhTDG4w0nWudtrHtj0RUEku bRSGU/OK477lqrCfXHMI+Zg1L3QIIOypkplxGDOG3yRwIIp1hGJefJZYeOlt7mEL OtDMQVxdNSGTmJ510cwlMvMXWPO5APdIm4I8ZEIzjARInoiFFrey81oOXf8QPmmG FgGr+Bi/ADAEZPB2cds1xghcBsEjVWy6MSDYXbNVmpmqdKOFDimv22kA77wHGJM= =h/Gr -----END PGP SIGNATURE----- --UlVJffcvxoiEqYs2--