Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 6A7B3BAC for ; Mon, 9 Oct 2017 21:28:12 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from sonic312-22.consmr.mail.gq1.yahoo.com (sonic312-22.consmr.mail.gq1.yahoo.com [98.137.69.203]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id 3AE6B367 for ; Mon, 9 Oct 2017 21:28:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1507584490; bh=INK6TyBbNQXHOjk9GWmbBLaWFNm6Aw87PfIRbnBY6pw=; h=Date:From:To:Subject:References:From:Subject; b=WSojLEoyFgECF4Rkl4rEejW9NYqgfnRAz4iS7n1z2G0X35w4GKbsT1l16MOjbjyPfb22uKsfQf9TTwfvK71bbVi4wCzUeiEhKF1PmKTChBcAkLlQlAFjfdJ9RAV1U8bdtxy9ZHaaMb1DZ0P3fbegIx+z6zhkdLbtrKG6P+vVlv80EIjKLXnMp3Rqm3ScJFpNdzJ7QyaYOCoYoVXDXpIG681rbd0f4cMjm8/Dj8mzr0cF4w/X8dwl2AqM2jHULlP8XK7Z+YGtSB5W6NTQLsdBWatNi2rws8QnKFk9bfXO8dQdat4V+0RppeJMbvLT/yjHjWF3v8OE7jcpI3cP/gghsQ== X-YMail-OSG: zxEitLgVM1lHjCdNNOkQRVn_aKFPhZB_ZeHuZO19ERTREQGACSX7KPupEg7TEcu VDZ.eQNWfJ7c1Mur_z9R27fVHwJrMxtBMu.vRf620.ROgwrVbsfZkBw.ucIpq45tKw5igtqylug. 3XC5bYRPNu90mOh4dvOy9ZJSAU_ieIkyK2nHCY1oICOdWF8NxXMP2rEqD3IQgbH2.bjHNUzmqXtE l3SrlMy78MRzQuMnfn7BfoagLfSO3pB.xy8JII17vGKyF1IPe.Qu1s1XqmV95evalYikWneR.WU7 .j0QdgOcwkMJqEJYWR1nQxIvsIBI_2fVgLG1nraiFDnXk5EXtKMukAm4UWcfTXLMaZJjcyIpYpAw nM_t3O5hWeP03gn0caf2KfbbYg_RXwHwfjTvleRt.JWKWZxeArXIlq2.mf8aZhkB_69DAa2MG2_i TvKu6wXEMBV1YNOU.hMTOfUsWTbo5H2IY_i0MuqKNSEpVkF5SU04cFcn6ApCbABaoic0tFW1JSC_ 46waoRdUMDT7WfHXcYZJ4oJkV1zba2kTVSLCmJdfL0dGana7_lVMTdY.1Kw-- Received: from sonic.gate.mail.ne1.yahoo.com by sonic312.consmr.mail.gq1.yahoo.com with HTTP; Mon, 9 Oct 2017 21:28:10 +0000 Date: Mon, 9 Oct 2017 21:26:50 +0000 (UTC) From: Scott Roberts To: bitcoin-dev@lists.linuxfoundation.org Message-ID: <1091872802.4256448.1507584410826@mail.yahoo.com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_4256447_1338361221.1507584410824" References: <1091872802.4256448.1507584410826.ref@mail.yahoo.com> X-Mailer: WebService/1.1.10668 YMailNorrin Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/61.0.3163.100 Safari/537.36 X-Spam-Status: No, score=1.5 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FORGED_MUA_MOZILLA,FREEMAIL_FROM,HTML_MESSAGE, RCVD_IN_DNSWL_NONE,RP_MATCHES_RCVD autolearn=disabled version=3.3.1 X-Spam-Level: * X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Mon, 09 Oct 2017 21:46:41 +0000 Subject: [bitcoin-dev] New difficulty algorithm needed for SegWit2x fork? 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, 09 Oct 2017 21:28:12 -0000 ------=_Part_4256447_1338361221.1507584410824 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Background: The bitcoin difficulty algorithm does not seem to be a good one.=C2=A0 If t= here is a fork due to miners seeking maximum profit without due regard to s= ecurity, users, and nodes, the "better" coin could end up being the minorit= y chain. If 90% of hashrate is really going to at least initially go toward= s using SegWit2x, BTC would face 10x delays in confirmations until the next= difficulty adjustment, negatively affecting its price relative to BTC1, ca= using further delays from even more miner abandonment (until the next adjus= tment). The 10% miners remaining on BTC do not inevitably lose by staying t= o endure 10x delays because they have 10x less competition, and the same si= tuation applies to BTC1 miners. If the prices are the same and stable, all = seems well for everyone, other things aside.=C2=A0 But if the BTC price doe= s not fall to reflect the decreased hashrate, the situation seems to be a b= ig problem for both coins: BTC1 miners will jump back to BTC when the diffi= culty adjustment occurs, initiating a potentially never-ending oscillation = between the two coins, potentially worse than what BCH is experiencing.=C2= =A0 They will not issue coins too fast like BCH because that is a side effe= ct of the asymmetry in BCH's rise and fall algorithm. Solution: Hard fork to implement a new difficulty algorithm that uses a simple rollin= g average with a much smaller window.=C2=A0 Many small coins have done this= as a way to stop big miners from coming on and then suddenly leaving, leav= ing constant miners stuck with a high difficulty for the rest of a (long) a= veraging window.=C2=A0 Even better, adjust the reward based on recent solve= times to motivate more mining (or less) if the solvetimes are too slow (or = too fast).=C2=A0 This will keep keep the coin issuance rate perfectly on sc= hedule with real time.=C2=A0 I recommend the following for Bitcoin, as fast, simple, and better than any= other difficulty algorithm I'm aware of.=C2=A0 This is the result of a lot= of work the past year. =3D=3D=3D Begin difficulty algorithm =3D=3D=3D# Zawy v6 difficulty algorith= m (modified for bitcoin)# Unmodified Zawy v6 for alt coins:=C2=A0# http://z= awy1.blogspot.com/2017/07/best-difficulty-algorithm-zawy-v1b.html# My faile= d attempts at something better:# https://github.com/seredat/karbowanec/comm= it/231db5270acb2e673a641a1800be910ce345668a## Keep negative solvetimes to c= orrect bad timestamps.# Do not be tempted to use:# next_D =3D sum(last N Ds= ) * T / [max(last N TSs) - min(last N TSs];# D=3Ddifficulty, ST=3D Solvetim= e, TS =3D timestamp, T=3DTargetSolveTime # set constants until next hard fork: T=3D600;=C2=A0N=3D30; # Averaging window. Smoother than N=3D15, faster resp= onse than N=3D60.X=3D5; # size of sudden hashrate changes expected as multi= ple of base hashrate.limit =3D X^(2/N); # limit rise and fall to protect ag= ainst timestamp errors & manipulationadjust =3D 1/(1+0.67/N);=C2=A0 # keeps= avg solvetime on track for small N. # begin difficulty algorithm=C2=A0 avg_ST=3D0; # avg SolveTimeavg_D=3D0;for ( i=3Dheight;=C2=A0 i > height-N;= =C2=A0 i--) {=C2=A0 # go through N most recent blocks=C2=A0 =C2=A0avg_ST += =3D (TS[i] - TS[i-1]) / N; # TS=3Dtimestamps=C2=A0 =C2=A0avg_D +=3D D[i]/N;= }avg_ST =3D T*limit if avg_ST > T*limit;=C2=A0avg_ST =3D T/limit if avg_ST = < T/limit;=C2=A0 next_D =3D avg_D * T / avg_ST * adjust;=C2=A0 # Tim Olsen suggested changing coin reward to protect against hash attacks.= # Karbowanek coin suggested something similar.# After testing many ideas, I= could not find anything better than the simplest idea below.# It was a sur= prise that coin issuance rate came out perfect.# BaseReward =3D coins per b= lock next_reward =3D BaseReward * avg_ST / T; =3D=3D=3D=3D=3D=3D=3D end algo =3D=3D=3D=3D Due to the limit and keeping negative solvetimes in a true average, timesta= mp errors resulting in negative solvetimes are corrected in the next block.= Otherwise, one would need to do like Zcash and cause a 5-block delay in th= e response by resorting to the median of past 11 blocks (MTP) as the most r= ecent timestamp, offsetting the timestamps from their corresponding difficu= lties by 5 blocks. (it does not cause an averaging problem, but it does cau= se a 5-block delay in the response.) Small N windows like keep the correct median, but cause avg solvetime to be= above the target. The "adjust" constant (empirically determined) fixes thi= s, but it causes the median to be that same percentage too low, below the i= deal Poisson median which is 0.693 of the mean. I was not able to find a fi= x to this that did not slow down the response to hashrate changes. ------=_Part_4256447_1338361221.1507584410824 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Background:

The bitcoin difficulty algorithm does not seem to be a go= od one.  If there is a fork due to miners seeking maximum profit witho= ut due regard to security, users, and nodes, the "better" coin could end up= being the minority chain. If 90% of hashrate is really going to at least i= nitially go towards using SegWit2x, BTC would face 10x delays in confirmati= ons until the next difficulty adjustment, negatively affecting its price re= lative to BTC1, causing further delays from even more miner abandonment (un= til the next adjustment). The 10% miners remaining on BTC do not inevitably= lose by staying to endure 10x delays because they have 10x less competitio= n, and the same situation applies to BTC1 miners. If the prices are the sam= e and stable, all seems well for everyone, other things aside.  But if= the BTC price does not fall to reflect the decreased hashrate, the situati= on seems to be a big problem for both coins: BTC1 miners will jump back to = BTC when the difficulty adjustment occurs, initiating a potentially never-e= nding oscillation between the two coins, potentially worse than what BCH is= experiencing.  They will not issue coins too fast like BCH because th= at is a side effect of the asymmetry in BCH's rise and fall algorithm.

Solution:

Hard fork to implem= ent a new difficulty algorithm that uses a simple rolling average with a mu= ch smaller window.  Many small coins have done this as a way to stop b= ig miners from coming on and then suddenly leaving, leaving constant miners= stuck with a high difficulty for the rest of a (long) averaging window.&nb= sp; Even better, adjust the reward based on recent solvetimes to motivate m= ore mining (or less) if the solvetimes are too slow (or too fast).  Th= is will keep keep the coin issuance rate perfectly on schedule with real ti= me. 

I recommend the following for Bitcoin, a= s fast, simple, and better than any other difficulty algorithm I'm aware of= .  This is the result of a lot of work the past year.

=3D=3D=3D Begin difficulty algorithm =3D=3D=3D
# Zawy v6= difficulty algorithm (modified for bitcoin)
# Unmodified Zawy v6= for alt coins: 
# http://zawy1.blogspot.com/2017/07/best-di= fficulty-algorithm-zawy-v1b.html
# My failed attempts at somethin= g better:
# https://github.com/seredat/karbowanec/commit/231db527= 0acb2e673a641a1800be910ce345668a
#
# Keep negative solv= etimes to correct bad timestamps.
# Do not be tempted to use:
# next_D =3D sum(last N Ds) * T / [max(last N TSs) - min(last N TSs]= ;
# D=3Ddifficulty, ST=3D Solvetime, TS =3D timestamp, T=3DTarget= SolveTime

# set constants until next hard fork:

T=3D600; 
N=3D30; # Averaging window.= Smoother than N=3D15, faster response than N=3D60.
X=3D5; # size= of sudden hashrate changes expected as multiple of base hashrate.
limit =3D X^(2/N); # limit rise and fall to protect against timestamp err= ors & manipulation
adjust =3D 1/(1+0.67/N);  # keeps avg= solvetime on track for small N.

# begin difficult= y algorithm 

avg_ST=3D0; # avg SolveTime
avg_D=3D0;
for ( i=3Dheight;  i > height-N;  i= --) {  # go through N most recent blocks
   avg_ST= +=3D (TS[i] - TS[i-1]) / N; # TS=3Dtimestamps
   avg_D= +=3D D[i]/N;
}
avg_ST =3D T*limit if avg_ST > T*lim= it; 
avg_ST =3D T/limit if avg_ST < T/limit; 
<= div>
next_D =3D avg_D * T / avg_ST * adjust; 
=
# Tim Olsen suggested changing coin reward to protect agains= t hash attacks.
# Karbowanek coin suggested something similar.
# After testing many ideas, I could not find anything better than t= he simplest idea below.
# It was a surprise that coin issuance ra= te came out perfect.
# BaseReward =3D coins per block
<= br>
next_reward =3D BaseReward * avg_ST / T;

=
=3D=3D=3D=3D=3D=3D=3D end algo =3D=3D=3D=3D

D= ue to the limit and keeping negative solvetimes in a true average, timestam= p errors resulting in negative solvetimes are corrected in the next block. = Otherwise, one would need to do like Zcash and cause a 5-block delay in the= response by resorting to the median of past 11 blocks (MTP) as the most re= cent timestamp, offsetting the timestamps from their corresponding difficul= ties by 5 blocks. (it does not cause an averaging problem, but it does caus= e a 5-block delay in the response.)

Small N window= s like keep the correct median, but cause avg solvetime to be above the tar= get. The "adjust" constant (empirically determined) fixes this, but it caus= es the median to be that same percentage too low, below the ideal Poisson m= edian which is 0.693 of the mean. I was not able to find a fix to this that= did not slow down the response to hashrate changes.
------=_Part_4256447_1338361221.1507584410824--