MIME-Version: 1.0
In-Reply-To: <CACRYg-4ho-XGK3xUdQW-ny2BFs2O91BuendrxuVYBni4wHrRqw@mail.gmail.com>
References: <CACRYg-4ho-XGK3xUdQW-ny2BFs2O91BuendrxuVYBni4wHrRqw@mail.gmail.com>
From: George Balch <gbalch714@gmail.com>
Date: Mon, 29 Jan 2018 13:53:06 -0800
Message-ID: <CAC94VgDR7pXLtk5ZbQS9cO=NVLh-p7kMtAU8x+uT0ndCbjZrOA@mail.gmail.com>
To: Neiman <neiman.mail@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="94eb2c0dfcba6c57e90563f145b4"
Subject: Re: [bitcoin-dev] How accurate are the Bitcoin timestamps?
Precedence: list

--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

<div dir=3D"auto">The terms &quot;simple ordering of blocks&quot; and times=
tamp are essentially the same thing.</div><div class=3D"gmail_extra"><br><d=
iv class=3D"gmail_quote">On Jan 29, 2018 1:16 PM, &quot;Neiman via bitcoin-=
dev&quot; &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitc=
oin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br type=3D"attribution"><b=
lockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px =
#ccc solid;padding-left:1ex"><div dir=3D"ltr">First time posting here, plea=
se be gentle.<br><div><br>I&#39;m doing a research project about blockchain=
 timestamping. There are many such projects, including the fantastic OpenTi=
mestamps. <br><br>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.<br><br>But how accurate are Bitcoins timestamps?<br><br>I d=
idn&#39;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.<br><br>B=
asic observations and questions:<br></div><div>----------------------------=
--<wbr>-------------<br><b>1.</b> It seems to me that the timestamp is not =
the time that the block was created. Ideally, it&#39;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.<br><br>If this is true, then there&#39;s a strange phenomena to obser=
ve in <a href=3D"http://blockchain.info" target=3D"_blank">blockchain.info<=
/a> and <a href=3D"http://blockexplorer.com" target=3D"_blank">blockexplore=
r.com</a>: the timestamps of blocks equals the receiving times. <br><br>Am =
I wrong in my understanding, or is there a mistake in those websites?<br><b=
r><b>2.</b> 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).<br><br>As far as=
 I could tell, timestamps are included in Bitcoin&#39;s protocol *only* to =
adjust the difficulty of PoW.<br><br>Direct control of timestamp accuracy:<=
br>------------------------------<wbr>-----------------<br>The only element=
 in the protocol that I found to control timestamp accuracy is based on the=
 network time concept.<br><br>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<br>=C2=A0=C2=A0=C2=A0 1. there are at least 5 conn=
ected, and<br>=C2=A0=C2=A0=C2=A0 2. the difference between the median time =
and the nodes own system time is less than 70 minutes.<br><br>Then new bloc=
ks are accepted by the peers if their timestamps is<br>=C2=A0=C2=A0=C2=A0 1=
. less than the network time plus 2 hours, and<br>=C2=A0=C2=A0=C2=A0 2. gre=
ater than the median timestamp of previous 11 blocks.<br><br>The first rule=
 supplies a 2 hour upper bound for timestamp accuracy. <br><br>However, the=
 second rule doesn&#39;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&#39;re only assur=
ed that any future timestamp is no bigger than this specific median, which =
is not much information.<br><br>Further analysis can be made under differen=
t assumptions. For example, what&#39;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.<br><br>The secon=
d rule cannot be strengthened to be similar to the first one (i.e., nodes d=
on&#39;t accept blocks less than network time minus 2 hours). The reason is=
 that nodes cannot differentiate if it&#39;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. <br><br>Indirect cont=
rol of timestamps accuracy:<br>------------------------------<wbr>---------=
-----------<br>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.<br><br>The adjustment rules are given in pow.cpp (bit=
coin-core source, version 0.15.1), in the function &#39;CalculateNextWorkRe=
quired&#39;, by the formula (with some additional adjustments which I omit)=
:<br><br>=C2=A0=C2=A0=C2=A0 (old_target* (time_of_last_block_in_2016_<wbr>b=
locks_interval - time_of_first_block_in_2016_<wbr>blocks_interval) )/time_o=
f_two_weeks<br><br>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=
:<br><br>=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=
<br><br>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. <br><br>Possible improvement:<br>---------------------------=
--<br>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.<br><br>I&#39;m aware that this change require=
s a hardfork, and won&#39;t happen any time soon. But does it make sense to=
 add it to a potential future hard fork?<br></div></div>
<br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div></div>

--94eb2c0dfcba6c57e90563f145b4--