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 AE0BC317B for ; Mon, 29 Jan 2018 13:34:22 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f65.google.com (mail-it0-f65.google.com [209.85.214.65]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A59BD3C4 for ; Mon, 29 Jan 2018 13:34:21 +0000 (UTC) Received: by mail-it0-f65.google.com with SMTP id w14so9310954itc.3 for ; Mon, 29 Jan 2018 05:34:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=ASEZdUnkzxh8aZk3rTB+BRr9UDVz7WLvwEDU4gA3aNQ=; b=l5bKpKxqOWk5VXpA1NrjIEQkIa4VaRljwDpp8IOi9eYaN0Fx/KUCNvchthBjZwwnfI tzHDeeAtPH/JDqKsW/GSOUua88oj1mhbYueJb6zh4KRWc+p5nO1WC2dxUp7ehOos0wwk bPC3Ap4LJb/sEho9EEBsjCq/Lbhtnzm2bWUVVF+Rn8cAdA5CBx46Y5DYdsQvMJaoX3T7 4sl3Jx/wJTuIZwPLJFtEG1R0thNG5evmjHEWlO3fgqg/4q2B514g6GNS/Tw2Dewm0qNt neTm29lmprCpO3XPdbMdfFyAhlwFJGQ6bdmxmQmWfSDmZ853OoYxlVv/ZTbVrOSeNkm4 QbGw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=ASEZdUnkzxh8aZk3rTB+BRr9UDVz7WLvwEDU4gA3aNQ=; b=FTSgdJ6Wf3D7UmhFlXJElb/ddy9s2ECCAXHjP90L+35bv9jBJsO0F4kjHSODmgQu11 IfkxYcuZdtZGwAh/++f52DvJPLLDotlrRFzOS+ycVFyma4t64RuyQlE7U3e80OwmcciX dVy8MEhulkmigSXhe1rECjMEkoc/hVhy0WMV2GFrIcCm3d4sF6TZ1XiDsNwYfjM/A9qY GWubgjrIJB6jcK/yn8OlFOKXgc1jCdgkNOzrgvQeodJz10yV5JHu2TJl13vcutzWKx03 e5BV5Ck++DHgMDnFx88qRqJtyA6c7sxohjLmQH8HXEbE0nq+6PSv0ymGefcUQRDIIYq0 l8Eg== X-Gm-Message-State: AKwxytc5ELMTKo+wlKY4nRTvs+XQZMfg5iwK3eq9FwleMT13Gvn45jqa rN67SL7g3XO+LyoLy1CMsnoBkWK8zrnZw4/MLNZL3Q== X-Google-Smtp-Source: AH8x2259a7rr/W/6TdXapaX1cR9XPZn5FjbjbPMw+TtBTCQXKzecpM/d2qe7oupLRikkNd3zU7uAg53LSVm3AvEVnmk= X-Received: by 10.36.17.208 with SMTP id 199mr26508964itf.103.1517232860690; Mon, 29 Jan 2018 05:34:20 -0800 (PST) MIME-Version: 1.0 Received: by 10.2.77.141 with HTTP; Mon, 29 Jan 2018 05:34:20 -0800 (PST) From: Neiman Date: Mon, 29 Jan 2018 14:34:20 +0100 Message-ID: To: bitcoin-dev@lists.linuxfoundation.org Content-Type: multipart/alternative; boundary="001a1143eef4b3fd1e0563ea4d23" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham 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 20:30:49 +0000 Subject: [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 20:03:56 -0000 --001a1143eef4b3fd1e0563ea4d23 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable First time posting here, please be gentle. I'm doing a research project about blockchain timestamping. There are many such projects, including the fantastic OpenTimestamps. 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 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 enumeration would work double-spending wise. Permissioned consensus protocols, such as 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). The 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 (with 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 from both the protocol and the miners incentives point of views: 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 timestamp is the timestamp of the block that closes the adjustment interval in which it 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 timestamps 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? --001a1143eef4b3fd1e0563ea4d23 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
First time posting here, please be gentle.

I&#= 39;m doing a research project about blockchain timestamping. There are many= such projects, including the fantastic OpenTimestamps.

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

But ho= w 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 questio= ns:
-------------------------------------------
1. = It seems to me that the timestamp is not the time that the block was create= d. Ideally, it's the time that the miner started to try to mine the blo= ck. However, as timestamps may also be used as a source of variety for hash= es, the exact meaning of its value is unclear.

If this is true, then= there's a strange phenomena to observe in blockchain.info and blockex= plorer.com: the timestamps of blocks equals the receiving times.
Am I wrong in my understanding, or is there a mistake in those websites?<= br>
2. Timestamps are not necessary to avoid double-spending. A s= imple ordering of blocks is sufficient, so exchanging timestamps with enume= ration would work double-spending wise. Permissioned consensus protocols, s= uch as hyperledger, indeed have no timestamps (in version 1.0).

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

Direct control of timestamp accur= acy:
-----------------------------------------------
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 difficulty ar= tificially, then the PoW adjusting algorithm yields a second mechanism of a= ccuracy control.

The adjustment rules are given in pow.cpp (bitcoin-= core source, version 0.15.1), in the function 'CalculateNextWorkRequire= d', by the formula (with some additional adjustments which I omit):
=
=C2=A0=C2=A0=C2=A0 (old_target* (time_of_last_block_in_2016_blocks_inte= rval - 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 suc= h 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:

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

If we w= ant to be pedantic, the best lower bound for a block timestamp is the times= tamp of the block that closes the adjustment interval in which it resides. =

Possible improvement:
-----------------------------
We may co= nsider exchanging average with standard deviation in the difficulty adjustm= ent formula. It both better mirrors changes in the hash power along the int= erval, and disables the option to manipulate timestamps without affecting t= he difficulty.

I'm aware that this change requires a hardfork, a= nd won't happen any time soon. But does it make sense to add it to a po= tential future hard fork?
--001a1143eef4b3fd1e0563ea4d23--