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 3E6B9FFC for ; Mon, 29 Jan 2018 21:53:09 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f46.google.com (mail-wm0-f46.google.com [74.125.82.46]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F19742F5 for ; Mon, 29 Jan 2018 21:53:07 +0000 (UTC) Received: by mail-wm0-f46.google.com with SMTP id f71so17201707wmf.0 for ; Mon, 29 Jan 2018 13:53:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=kZ6T7d2mnhmF8hXzasc8D9Oa7Bu661d33xvfbWUOZts=; b=MMQAfjn00Qv31sEuyWzjkEDeH26lnxnwkioE5LW97scdnPe7nwygeQgGGCuFyULf7z /BAa6vFIT6UnCCFTUO2JprGUtWWTVu/yt/rTCXVgFEzFign1PzoiPVZ/xcFKL6LpkIhq VD461UOLy5DDbykGWtW7VpVymXW4titjTZ8bFiC/xs5rPiWxOPNNOaJ+h7sXaAIA3vpF jR97CVKkdPK/EACLQ5jS1CT791glPdnSd/O76wcJhORcVPcmzIkVa/J2EkKpGHgUttce ioS3DU7pGlyXxN09YeLUaooCdnY6LvSkJbxejJukRCfdZWekF+TINFLU3TDSFtC7PXYP 5Pwg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=kZ6T7d2mnhmF8hXzasc8D9Oa7Bu661d33xvfbWUOZts=; b=rf4iRexl9r9m7Ewh2Qo/VLWYXrRV9UVNdCMIvpxrP0QryzaS/K1d4wBR82viOlQrFD DEOhNhtuDrz8i2TTfNlzPwBLh3i/13s9aAcf2VVjkyCgoiS7XnXhvIBrN9HjQvdcfzvP 4RqoEzCd58yZvX61pmTQGs0DHP7PgJqrn7BQSD7GbwdMIOFcl5aHVCtoIhWGDse1uP7x QcIpCHr7PQLW3cBcdLAJRI9SdTmSti53/gB55NpM+FRLHvNIi0pOYOLnSg2vu4FLiHUP NTmco+DF0YQTtwI1IzRjKCykuAOaFI9mpYe2M/WlWVjQ/3dra3ufH0MjdpUedaiUjgAn iZrQ== X-Gm-Message-State: AKwxytfRxcJg++/Z7FLsOfmlWGNBFmiAFswORA8Z1U2hA4O6rAuw15+J QWFsHf4z/+jaT95W3X5CjC4Yurmodz/jAC5OwPw= X-Google-Smtp-Source: AH8x225tNORKp8Ljmv7qBPdAmCRmKlvg6DwBJNn7+925h01Kr8PQO2l6+NiiciWS3qLP41OzZOEpJbHJFQ7LcpBgAqA= X-Received: by 10.80.170.61 with SMTP id o58mr37185120edc.142.1517262786548; Mon, 29 Jan 2018 13:53:06 -0800 (PST) MIME-Version: 1.0 Received: by 10.80.157.13 with HTTP; Mon, 29 Jan 2018 13:53:06 -0800 (PST) Received: by 10.80.157.13 with HTTP; Mon, 29 Jan 2018 13:53:06 -0800 (PST) In-Reply-To: References: From: George Balch Date: Mon, 29 Jan 2018 13:53:06 -0800 Message-ID: To: Neiman , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="94eb2c0dfcba6c57e90563f145b4" X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM, HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Mon, 29 Jan 2018 22:26:15 +0000 Subject: Re: [bitcoin-dev] How accurate are the Bitcoin 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, 29 Jan 2018 21:53:09 -0000 --94eb2c0dfcba6c57e90563f145b4 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable The terms "simple ordering of blocks" and timestamp are essentially the same thing. On Jan 29, 2018 1:16 PM, "Neiman via bitcoin-dev" < bitcoin-dev@lists.linuxfoundation.org> wrote: > First time posting here, please be gentle. > > I'm doing a research project about blockchain timestamping. There are man= y > such projects, including the fantastic OpenTimestamps. > > All of the projects essentially save some data in a block, and rely on th= e > block timestamp as a proof that this data existed at some specific time. > > But how accurate are Bitcoins timestamps? > > I didn't find any discussion or research regarding Bitcoin timestamp > accuracy (also not in the history of this mailing list). I share here a > simple analysis of timestamp accuracy, and a suggestion how to improve it= . > > Basic observations and questions: > ------------------------------------------- > *1.* It seems to me that the timestamp is not the time that the block was > created. Ideally, it's the time that the miner started to try to mine the > block. However, as timestamps may also be used as a source of variety for > hashes, the exact meaning of its value is unclear. > > If this is true, then there's a strange phenomena to observe in > blockchain.info and blockexplorer.com: the timestamps of blocks equals > the receiving times. > > Am I wrong in my understanding, or is there a mistake in those websites? > > *2.* Timestamps are not necessary to avoid double-spending. A simple > ordering of blocks is sufficient, so exchanging timestamps with enumerati= on > would work double-spending wise. Permissioned consensus protocols, such a= s > hyperledger, indeed have no timestamps (in version 1.0). > > As far as I could tell, timestamps are included in Bitcoin's protocol > *only* to adjust the difficulty of PoW. > > Direct control of timestamp accuracy: > ----------------------------------------------- > The only element in the protocol that I found to control timestamp > accuracy is based on the network time concept. > > The Bitcoin protocol defines =E2=80=9Cnetwork time=E2=80=9D for each node= . The network > time is the median time of the other clients, but only if > 1. there are at least 5 connected, and > 2. the difference between the median time and the nodes own system > time is less than 70 minutes. > > Then new blocks are accepted by the peers if their timestamps is > 1. less than the network time plus 2 hours, and > 2. greater than the median timestamp of previous 11 blocks. > > The first rule supplies a 2 hour upper bound for timestamp accuracy. > > However, the second rule doesn't give a tight lower bound. Actually, no > lower bound is given at all if no assumption is made about the median. If > we assume the median to be accurate enough at some timepoint, then we're > only assured that any future timestamp is no bigger than this specific > median, which is not much information. > > Further analysis can be made under different assumptions. For example, > what's the accuracy if holders of 51% of the computational power create > honest timestamps? But unfortunately, I don't see any good reason to work > under such an assumptions. > > The second rule cannot be strengthened to be similar to the first one > (i.e., nodes don't accept blocks less than network time minus 2 hours). T= he > reason is that nodes cannot differentiate if it's a new block with > dishonest timestamp, an old block with an old timestamps (with many other > blocks coming) or simply a new block that took a long time to mine. > > Indirect control of timestamps accuracy: > -------------------------------------------------- > If we assume that miners have no motive to increase difficulty > artificially, then the PoW adjusting algorithm yields a second mechanism = of > accuracy control. > > The adjustment rules are given in pow.cpp (bitcoin-core source, version > 0.15.1), in the function 'CalculateNextWorkRequired', by the formula (wit= h > some additional adjustments which I omit): > > (old_target* (time_of_last_block_in_2016_blocks_interval - > time_of_first_block_in_2016_blocks_interval) )/time_of_two_weeks > > It uses a simple average of block time in the last 2016 blocks. But such > averages ignore any values besides the first and last one in the interval= . > Hence, if the difficulty is constant, the following sequence is valid fro= m > both the protocol and the miners incentives point of views: > > 1, 2, 3,=E2=80=A6., 2015, 1209600 (time of two weeks), 2017, 2018, 20= 19,=E2=80=A6., > 4031, 1209600*2, 4033, 4044, =E2=80=A6 > > If we want to be pedantic, the best lower bound for a block timestamp is > the timestamp of the block that closes the adjustment interval in which i= t > resides. > > Possible improvement: > ----------------------------- > We may consider exchanging average with standard deviation in the > difficulty adjustment formula. It both better mirrors changes in the hash > power along the interval, and disables the option to manipulate timestamp= s > without affecting the difficulty. > > I'm aware that this change requires a hardfork, and won't happen any time > soon. But does it make sense to add it to a potential future hard fork? > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --94eb2c0dfcba6c57e90563f145b4 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
The terms "simple ordering of blocks" and times= tamp are essentially the same thing.

On Jan 29, 2018 1:16 PM, "Neiman via bitcoin-= dev" <bitc= oin-dev@lists.linuxfoundation.org> wrote:
First time posting here, plea= se be gentle.

I'm doing a research project about blockchain= timestamping. There are many such projects, including the fantastic OpenTi= mestamps.

All of the projects essentially save some data in a block= , and rely on the block timestamp as a proof that this data existed at some= specific time.

But how accurate are Bitcoins timestamps?

I d= idn't find any discussion or research regarding Bitcoin timestamp accur= acy (also not in the history of this mailing list). I share here a simple a= nalysis of timestamp accuracy, and a suggestion how to improve it.

B= asic observations and questions:
----------------------------= ---------------
1. It seems to me that the timestamp is not = the time that the block was created. Ideally, it's the time that the mi= ner started to try to mine the block. However, as timestamps may also be us= ed as a source of variety for hashes, the exact meaning of its value is unc= lear.

If this is true, then there's a strange phenomena to obser= ve in blockchain.info<= /a> and blockexplore= r.com: the timestamps of blocks equals the receiving times.

Am = I wrong in my understanding, or is there a mistake in those websites?
2. Timestamps are not necessary to avoid double-spending. A simple= ordering of blocks is sufficient, so exchanging timestamps with enumeratio= n would work double-spending wise. Permissioned consensus protocols, such a= s hyperledger, indeed have no timestamps (in version 1.0).

As far as= I could tell, timestamps are included in Bitcoin's protocol *only* to = adjust the difficulty of PoW.

Direct control of timestamp accuracy:<= br>-----------------------------------------------
The only element= in the protocol that I found to control timestamp accuracy is based on the= network time concept.

The Bitcoin protocol defines =E2=80=9Cnetwork= time=E2=80=9D for each node. The network time is the median time of the ot= her clients, but only if
=C2=A0=C2=A0=C2=A0 1. there are at least 5 conn= ected, and
=C2=A0=C2=A0=C2=A0 2. the difference between the median time = and the nodes own system time is less than 70 minutes.

Then new bloc= ks are accepted by the peers if their timestamps is
=C2=A0=C2=A0=C2=A0 1= . less than the network time plus 2 hours, and
=C2=A0=C2=A0=C2=A0 2. gre= ater than the median timestamp of previous 11 blocks.

The first rule= supplies a 2 hour upper bound for timestamp accuracy.

However, the= second rule doesn't give a tight lower bound. Actually, no lower bound= is given at all if no assumption is made about the median. If we assume th= e median to be accurate enough at some timepoint, then we're only assur= ed that any future timestamp is no bigger than this specific median, which = is not much information.

Further analysis can be made under differen= t assumptions. For example, what's the accuracy if holders of 51% of th= e computational power create honest timestamps? But unfortunately, I don= 9;t see any good reason to work under such an assumptions.

The secon= d rule cannot be strengthened to be similar to the first one (i.e., nodes d= on't accept blocks less than network time minus 2 hours). The reason is= that nodes cannot differentiate if it's a new block with dishonest tim= estamp, an old block with an old timestamps (with many other blocks coming)= or simply a new block that took a long time to mine.

Indirect cont= rol of timestamps accuracy:
---------------------------------------= -----------
If we assume that miners have no motive to increase difficul= ty artificially, then the PoW adjusting algorithm yields a second mechanism= of accuracy control.

The adjustment rules are given in pow.cpp (bit= coin-core source, version 0.15.1), in the function 'CalculateNextWorkRe= quired', by the formula (with some additional adjustments which I omit)= :

=C2=A0=C2=A0=C2=A0 (old_target* (time_of_last_block_in_2016_b= locks_interval - time_of_first_block_in_2016_blocks_interval) )/time_o= f_two_weeks

It uses a simple average of block time in the last 2016 = blocks. But such averages ignore any values besides the first and last one = in the interval. Hence, if the difficulty is constant, the following sequen= ce is valid from both the protocol and the miners incentives point of views= :

=C2=A0=C2=A0=C2=A0 1, 2, 3,=E2=80=A6., 2015, 1209600 (time of two = weeks), 2017, 2018, 2019,=E2=80=A6., 4031, 1209600*2, 4033, 4044, =E2=80=A6=

If we want to be pedantic, the best lower bound for a block timesta= mp is the timestamp of the block that closes the adjustment interval in whi= ch it resides.

Possible improvement:
---------------------------= --
We may consider exchanging average with standard deviation in the dif= ficulty adjustment formula. It both better mirrors changes in the hash powe= r along the interval, and disables the option to manipulate timestamps with= out affecting the difficulty.

I'm aware that this change require= s a hardfork, and won't happen any time soon. But does it make sense to= add it to a potential future hard fork?

_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev

--94eb2c0dfcba6c57e90563f145b4--