Date: Mon, 9 Oct 2017 21:26:50 +0000 (UTC)
From: Scott Roberts <zawy@yahoo.com>
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>
Subject: [bitcoin-dev] New difficulty algorithm needed for SegWit2x fork?
Precedence: list

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

<html><head></head><body><div style=3D"font-family:Helvetica Neue, Helvetic=
a, Arial, sans-serif;font-size:16px;"><div style=3D"font-family:Helvetica N=
eue, Helvetica, Arial, sans-serif;font-size:16px;"><div>Background:</div><d=
iv><br></div><div>The bitcoin difficulty algorithm does not seem to be a go=
od one.&nbsp; 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.&nbsp; 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.&nbsp; 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.</div=
><div><br></div><div>Solution:</div><div><br></div><div>Hard fork to implem=
ent a new difficulty algorithm that uses a simple rolling average with a mu=
ch smaller window.&nbsp; 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).&nbsp; Th=
is will keep keep the coin issuance rate perfectly on schedule with real ti=
me.&nbsp;</div><div><br></div><div>I recommend the following for Bitcoin, a=
s fast, simple, and better than any other difficulty algorithm I'm aware of=
.&nbsp; This is the result of a lot of work the past year.</div><div><br></=
div><div>=3D=3D=3D Begin difficulty algorithm =3D=3D=3D</div><div># Zawy v6=
 difficulty algorithm (modified for bitcoin)</div><div># Unmodified Zawy v6=
 for alt coins:&nbsp;</div><div># http://zawy1.blogspot.com/2017/07/best-di=
fficulty-algorithm-zawy-v1b.html</div><div># My failed attempts at somethin=
g better:</div><div># https://github.com/seredat/karbowanec/commit/231db527=
0acb2e673a641a1800be910ce345668a</div><div>#</div><div># Keep negative solv=
etimes to correct bad timestamps.</div><div># Do not be tempted to use:</di=
v><div># next_D =3D sum(last N Ds) * T / [max(last N TSs) - min(last N TSs]=
;</div><div># D=3Ddifficulty, ST=3D Solvetime, TS =3D timestamp, T=3DTarget=
SolveTime</div><div><br></div><div># set constants until next hard fork:</d=
iv><div><br></div><div>T=3D600;&nbsp;</div><div>N=3D30; # Averaging window.=
 Smoother than N=3D15, faster response than N=3D60.</div><div>X=3D5; # size=
 of sudden hashrate changes expected as multiple of base hashrate.</div><di=
v>limit =3D X^(2/N); # limit rise and fall to protect against timestamp err=
ors &amp; manipulation</div><div>adjust =3D 1/(1+0.67/N);&nbsp; # keeps avg=
 solvetime on track for small N.</div><div><br></div><div># begin difficult=
y algorithm&nbsp;</div><div><br></div><div>avg_ST=3D0; # avg SolveTime</div=
><div>avg_D=3D0;</div><div>for ( i=3Dheight;&nbsp; i &gt; height-N;&nbsp; i=
--) {&nbsp; # go through N most recent blocks</div><div>&nbsp; &nbsp;avg_ST=
 +=3D (TS[i] - TS[i-1]) / N; # TS=3Dtimestamps</div><div>&nbsp; &nbsp;avg_D=
 +=3D D[i]/N;</div><div>}</div><div>avg_ST =3D T*limit if avg_ST &gt; T*lim=
it;&nbsp;</div><div>avg_ST =3D T/limit if avg_ST &lt; T/limit;&nbsp;</div><=
div><br></div><div>next_D =3D avg_D * T / avg_ST * adjust;&nbsp;</div><div>=
<br></div><div># Tim Olsen suggested changing coin reward to protect agains=
t hash attacks.</div><div># Karbowanek coin suggested something similar.</d=
iv><div># After testing many ideas, I could not find anything better than t=
he simplest idea below.</div><div># It was a surprise that coin issuance ra=
te came out perfect.</div><div># BaseReward =3D coins per block</div><div><=
br></div><div>next_reward =3D BaseReward * avg_ST / T;</div><div><br></div>=
<div>=3D=3D=3D=3D=3D=3D=3D end algo =3D=3D=3D=3D</div><div><br></div><div>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.)</div><div><br></div><div>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.</div></div></div></bod=
y></html>
------=_Part_4256447_1338361221.1507584410824--