Tuesday, November 21, 2017

Best difficulty algorithm

I'm changing this as I find improvements. Last change: 12/1/2017.

This first one appears to be the best all around:
# Jacob Eliosoff's EMA (exponential moving average)
# https://en.wikipedia.org/wiki/Moving_average#Application_to_measuring_computer_performance
# ST = solvetime, T=target solvetime
# height = most recently solved block
# N=70
# MTP should not be used

for (i=height - 10 to height) {  # check timestamps starting 10 blocks into past)
   previous_max = max
   max=timestamp[i] if timestamp[i] > max
}
ST = max - previous_max
ST = max(T/100,min(T*10, ST))
next_D = previous_D * ( T/ST + e^(-ST/T/N) * (1-T/ST) )
A word of caution with the above EMA: when converting to and from bits field (aka target) to difficulty, it is important to not make a consistently wrong "rounding" error. For example, if previous difficulty was 100,000, it is important that nothing in the code make it consistently +50 more or consistently -50 less (0.05% error). That would cause the EMA at N=70 to have 3.5% error in solvetime. At 0.5% error per block, there is 35% error in the solvetimes (difficulty is 30% too high or low). The error that develops seems to be based on about 1.005^70 = 41%. If half the time it is +1,000 too high and the other half -1,000 too low, then it's OK. just don't be consistently wrong in the same direction. Error in the value for e=2.7183 does not hurt it.

In an simple average (SMA), a multiplicative error like this only causes a proportional error in solvetime, not a compounded error.

There is a T/solvetime ratio in two places. It must be the same in both places. I don't know how it would be coded to give something different, but it's something to be aware of.

==========
The following attempts to make it smoother while having some ability to respond to faster to big hashrate changes.
# Dynamic EMA difficulty algo (Jacob Eliosoff's EMA and Zawy's adjustable window). 
# Bitcoin cash dev(?) came up with the median of three to reduce timestamp errors.
# For EMA origins see 
# https://en.wikipedia.org/wiki/Moving_average#Application_to_measuring_computer_performance
# "Dynamic" means it triggers to a faster-responding value for N if a substantial change in hashrate
# is detected. It increases from that event back to Nmax

Nmax=100 # max EMA window
Nmin=25 # min EMA window
A=10, B=2, C=0.37  # A,B,C = 10,2,37 or 20, 1.65 0.45, 

# TS=timestamp, T=target solvetime, i.e. 600 seconds
# Find the most recent unusual 20-block event
for (i=height-Nmax to height) {  # height=current block index
    if ( (median(TS[i],TS[i-1],TS[i-2]) - median(TS[i-20],TS[i-21],TS[i-22]))/T/A  > B 
           or  
         (median(TS[i],TS[i-1],TS[i-2]) - median(TS[i-20],TS[i-21],TS[i-22]))/T/A  < C  ) 
      {   unusual_event=height - i + Nmin   } 
}
N = min(Nmax, unusual_event))

# now do the EMA shown above with this N 

Here's another algorithm that seems to be about as good as the EMA
#  Weighted-Weighted Harmonic Mean (WWHM) difficulty algorithm
# Original idea from Tom Harding (Deger8) called "WT-144"  
# No limits, filtering, or tempering should be attempted.
# MTP should not be used.

# set constants
# N=60 # See Masari coin for live data with N=60
# T=600 # coin's Target solvetime. If this changes, nothing else needs to be changed.
# adjust=0.99 # 0.98 for N=30, 0.99 for N=60
#  k = (N+1)/2 *adjust * T # there is not a missing N. 
# height = most recently solved block

# algorithm
d=0, t=0, j=0
previous_max=timestamp[height - N] 
for ( i = height-N+1; i < height+1; i++) {  # (N most recent blocks)
    max_timestamp=max(timestamp[i], previous_max)
    solvetime = max_timestamp - previous_max
    solvetime=1 if solvetime < 1
   # for N=60, 10*T solvetimes drives difficulty too far down, so:
    solvetime = 10*T if solvetime > 10*T 
    previous_max=max_timestamp
    j++
    t +=  solvetime * j 
    d += D[i] # sum the difficulties this is how WWHM is different from Tom's WT.
}
t=T*N if t < T*N  # in case of startup weirdness, keep t reasonable
next_D = d * k / t 

# limits on next_D do not need to be used because of the above solvetime restrictions
# but if you still want limits on D's change per block & expect max 5x hash rate
# changes or want to replace the solvetime restrictions, use
# limit = 5^(3/N)
# next_D = previous_D*limit if next_D > previous_D*limit
# next_D = previous_D/limit if next_D > previous_D/limit


Monday, November 13, 2017

Maximizing options as the basis of memory-less intelligence

There seems to be some big news in A.I. and cosmology. To give an example of how far-reaching this idea is, view walking upright and the ability to use our hands as something that maximizes our options rather than something that gives us more power in any other sense. This simple algorithm can successfully play games without any training at all, other than defining "maximize future options" for a given set of rules.

I am far from certain his general view is correct (or even expressed clearly enough to criticize. I still can't view it as anymore than a method of problem solving when his claims are much greater than that, but I can't exactly understand his claims. It sounds like he is saying things appear intelligent because nature somehow keeps options open.


Ted Talk
https://www.ted.com/talks/alex_wissner_gross_a_new_equation_for_intelligence

General idea:
https://physics.aps.org/articles/v6/46

How it's good at playing atari without training:
http://entropicai.blogspot.com/2017/06/solved-atari-games.html#more

On freedom in society making us more powerful:
https://www.edge.org/response-detail/26181

Basic physics of causal entropy and intelligence
http://www.alexwg.org/publications/PhysRevLett_110-168702.pdf

How it can predict the cosmological constant by following the anthropic principle:
http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-pub-12353.pdf


Wednesday, November 1, 2017

Why Degner8's WT difficulty algorithm is the best

I previously said difficulty is not open to debate or opinion. By this
I mean a scientific measurement should be followed by a mathematical
calculation. We should measure current hashrate and then
mathematically set difficulty based on that to get the desired average
solvetime. The only discussion (debate and opinion) needed is to
determine how to make the measurement and how to do the math. This
coincidentally provides the perfect protection to hash attacks and
delays (unless you change the Poisson by shifting consensus from POW
to better time restrictions set by the nodes, i.e. Andrew Stone's
idea.)

The difficulty math should be: difficulty = 600 * hashrate. Hashrate
= current difficulty / current solvetime. This part is not open for
debate. The problem is determining current hashrate because the only
way to measure it is to see the network response to current
difficulty, and it's current difficulty that we're looking for. (I
should mention schancel has an idea on how to get a true "current
hashrate", but as with long tail and block reward adjustment I
consider it "for the future"). So the best we can do is to base the
math on the hashrate on the previous difficulty. The problem is
random variation. What observations and math should we use to
estimate current hash rate? This is open for debate, but it's not
debatable in a sense because there should be some provable optimum.

With this background I want to "prove" Degnr8's WT with low N is the
optimal formula. Bitcoin measures avg hashrate of past 2 weeks of
blocks by using the perfectly correct next_D = sum (D) / sum(solvetimes)
times a proportionality constant. So it is measuring hashrate as it
was 1 week in the past, and only adjusts once every two weeks.
(Hashrate = difficulty times a proportionality constant)
Obviously this is not the best measure of current hashrate. So,
everyone started using the same equation, but applying it every block
and using a smaller N. There have been many attempts to improve this
math, but every attempt I am aware of made it worse. The amount of
time wasted trying to improvement it is incredible. They go by a lot
of fancy names. They often apply a "filter" to try to reduce the
"noise", but they don't understand that the random variation is not
real noise that has a forcing function that needs to be filtered out
with something analogous to a capacitor and/or inductor on an
electrical signal. It can be noisy from miners jumping on and off or
from network effects, but we have no way to estimate the nature of
that noise in order to justify a specific filter design. The random
variation is, as far as we can measure, precise data that needs to be
included. Devs will also hurt the incontrovertible math by making
asymmetrical changes such as preventing negative timestamps. They have
their reasoning processes, but their reasoning is not as good as the
required math.

The simple average with low N is the state of the art. But it
has a problem: it is measuring the hashrate as it was N/2 blocks into
the past. Lower N helps, but there starts to be accidental variation
that causes longer delays. Fear of this is greatly exaggerated.
Filters do not help because the end result is not as good as just
going to a longer N. Degnr8's algo does not address the tradeoff
between faster response and accidental changes in difficulty that
occurs with low N. But by letting the weighting factor for the blocks
linearly reduce as they get further in the past, he's made possibly
the best possible measurement of the hashrate as it stood in the
PREVIOUS block rather than looking at N/2. There might be a slightly
more complex equation to make it a little more accurate, but if it
overestimates what the previous, current, or future block hashrates
are, it will send it into oscillations by overshooting, leaving it
open to exploit that amplifies the oscillations. Industrial process
controllers (PID controllers) do something better, but they depend on
the process being stable in its characteristic, not something like
miners seeking profit and thereby able to change how they react to the
controller. In other words diff algos can't try to predict the future
hashrate. The best they can do is estimate what the hashrate was in
the previous block. In watching Degnr8's WT respond to step
functions, it is a very linear increase. This is the hallmark of a
controller that is NOT trying to predict the future. It responds
faster than the simple equation, but does not overshoot or undershoot
in any sense.

This is the basis for me claiming there is no alternative to using
Degnr8's TW. The only thing to quibble over is the setting of N. I'm
down for 30. I'm working on getting an exposition of what it looks
like when small alts use N=16, 30, and 63.

Saturday, October 21, 2017

bits field relation to hashing and difficulty

In the block explorer you can see a "bits" field determines the difficulty that can be compared between all coins. It is a compact form of the maximum value the hash of the block header must have before nodes will accept the miner's hash. A miner's job is to hash until he can find a hash that is less than the hash value stated in the bits field. The difficulty algorithm sets the bits field value. In HUSH's block 190703 the bits field is 1d 08 ec fa. The 1d in decimal is 29, which means the max hash value is 29 bytes long. The 08 ec fa gives the value of the first 3 of those 29 bytes. The rest of them are 00. If you convert those 1st three to decimal and multiple that by 256^(29-3) it is 2.4E68. The hash of a block header is 32 bytes long, which can take on 2^32 = 1.15E77 different values. The miner's job is to keeping hashing, changing the nonce field between each hash (with a starting point given to him by the pool) to get a different hash each time, until he finds a 32 byte hash that is below that 2.4E68 number. 2.4E68 is 481 million tmies less than 1.16E77. So the miner has to hash that many times in 150 seconds to have a 50% chance of winning. 481 / 150 = 3.21 million hashes per second, which was the network hashrate during that block. The difficulty in hush-cli as you said was 239 M. 2^1 * 239 / 150 = 3.19 M Hashes/s network rate. For some reason, in Zcash replace the 2^1 with 2^13.

Friday, October 20, 2017

Blockchain timestamps, difficulty, and the stars.

posted to Zcash github:
https://github.com/zcash/zcash/issues/1889


Any upper limit you apply to timestamps should be reflected in a lower limit. For example, you could follow the rule that the next timestamp is limited to +/- 750 seconds from the previous timestamp +150 seconds (+900 / -600). If you don't allow the "negative" timestamp (-600 from previous timestamp) AND if miners can assign timestamps without a real-time limit from nodes, then a miner with > 20% of the network hashrate can drive the difficulty as low as he wants, letting everyone get blocks as fast as he wants, in less than a day.

A symmetrical limit on timestamps allows honest miner timestamps to completely erase the effect of bad timestamps. ( You do not need to wait 6 blocks for MTP like Zcash does in delaying the use of timestamps for difficulty, see footnote. ) If you allow the symmetrical "negative" timestamps, you do not need nodes to have the correct time with NTP or GPS unless miners collude with > 51% agreement on setting the timestamps further and further ahead of time to drive difficulty down. It's a real possibility if miners decide they do not like a certain fork due to not providing them with enough fees.

But if your nodes have an accurate time, you do not need mining at all. The only fundamental reason for mining is to act as a timestamp server to prevent double spending.

BTC and ETH depend on nodes to limit the future time assigned to blocks. This seems like a bad joke. Zooko was the only one here who seemed to know there is something fishy about strong reliance on nodes having the correct time. The extent to which BTC and ETH need those forward-time limits to be enforced by real time is the extent to which they do not need mining.

Since gmaxwell (and apparently Satoshi) reject the idea of relying on state-sponsored and crash-able GPS, NTP, or cellphone systems to eliminate the need for miners, the ideal solution is to have nodes that use a camera with a good zoom, known location, and accelerometer (if their camera is a cell phone not correctly mounted) to determine star position and to periodically calibrate their time based on that. @fluffypony was the only one I could get to "like" this idea on twitter. Every honest desktop node could reject transactions with bad timestamps, within some small window like 1 minute (with good optics). Science like this does not need to ask for consensus. Every node on his own could give the middle finger to every node that disagrees with him. Nodes with correct time would naturally comprise the biggest network, all saying F-you to the miners. Blocks could be 2 minutes apart and need only 1 confirmation. Science began with looking at the stars and time is the only thing I can think of that computers can determine in isolation and then agree on without a trusted 3rd party. Colluding miners bullying us with > 51% hashrate into more total fees at the expense of security is a trusted 3rd party.

Footnote:
MTP does not stop a 25% attacker who can set timestamps > 4 blocks ahead if other miners are not allowed to assign a "negative" timestamp to eliminate the error in the next block. But if you allow the "negatives" then MTP is not needed. Putting your tempering aside, this assumes you use

next_D = avg(D's) * T / avg(solvetimes, allowing negative solvetime)
instead of

next_D=sum(D's) * T / [max(Timestamps) - min(Timestamps) ]
because the N's of the denominator and number of the first equation do not cancel like you would think and hope (in order to use the second equation) when there are bad timestamps at the beginning and end of the window. With the MTP, your difficulty is delayed 5 blocks in responding to big ETH miners who jump on about twice a day. That's like a gift to them at the expense of your constant miners.

Also, your tempered N=17 gives almost the same results as a straight average N=63. I would use N=40 instead, without the tempering. It should reduce the cheap blocks the big ETH miners are getting.

Your 16% / 32% limits are rarely reached due to the N=63 slowness. This is good because it is a symmetry problem, although it would not be as bad as BCH. Use "limit" and "1/limit" where limit = X^(2/N) where N=63 for your current tempering and X = the size of the larger ETH attackers as a fraction of your total hashrate, which is about 3. This allows the the fastest response up or down at N for a given X with 80% probability. Change the 2 to 3 to get a higher probability of an adequately-fast response. The benefit is that it is a really loose timestamp limit on individual values, as long as the aggregate is not too far from the expected range.

Wednesday, October 18, 2017

Hold coins w/ nLocktime (or burn) as a source of price appreciation (via velocity theory of money)

post to HUSH chat:

Now I see we can't even charge HUSH fees for sending email because if the value increases a lot it will be too expensive. to email. Is it possible for the protocol to measure the swap rate between dollars and HUSH? If yes, then that seems to be a way you could charge say $0.0025 per tx output plus $0.000001 per tx byte . I'm allergic to blockchain bloat. You could burn 1/3 for price appreciation, send 1/3 to devs, and 1/3 to miners. If you don't burn HUSH (or enforcing holding times), what is the market incentive to increase its value if Zcash and other alts are going to attract most of the people seeking an anonymous store of value? There's a similar problem when spending HUSH for XHCP. How is XHCP automatically lowering in HUSH price so that you don't have to fork when HUSH increases 10x? Is burning some of that HUSH the only sure way to get market appreciation? Instead of burning in both cases you could require an nLocktime holding time to enforce the velocity theory of money. Previously I mentioned putting a locktime on the HUSH (for XHCP) before it can be spent, so devs can't spend it right away, giving a contuned work motivation just like stocks. But now I see it has a price appreciation effect. Dollars have value because they are being HELD in many places. It's not merely for savings, but as a requirement of doing business. But in a blockchain that is not being used to make purchases for goods or services in order to get other goods and services that have shipping and production times, there is no hold time. True, XHCP is a service, but if this "gas" should have a constant value, then the exchange rate between it and HUSHJ should fluctuate and in doing so, it removes the incentive to hold HUSH. As a speculator, I would have to trust the devs to hold their HUSH. That trust seems to be the primary source of objective (aka real aka justified) price appreciation.
Are there coins requiring a hold time on transactions as a source of price appreciation? I previously described making receivers also hold HUSH in order to receive but that seems to make it complicated without benefit. In this simpler holding time scheme, the sender would be required to send an amount of HUSH (determined by dollar or commodity basket exchange rate) with a locktime on it to himself.

Sunday, October 15, 2017

Smoothing coin release rate for bitcoin


If a coin wants to implement a continuous reward adjustment to give the same number of coins released as the same rate as bitcoin use:

C/block = 69.3*(0.5)^(-height/210,000)

But to implement it in an an existing coin, it takes a little more work to find a solution:

The halving events in BTC seem absurb in being such a powerful step function. Due to rounding error and trying to keep the same quantity of satoshis emitted every 4 years, it takes some effort to find a formula that exactly ends in 1/2 as many coins per block after 4 years (210,000 blocks) and gives the exact same number of Satoshis in those 4 years. Here's what I came up with.

Once every 4 hours, starting half-way into a halving event, set coins awarded to

BTC=C*int(1E8*A*B^(N/8750))/1E8

where

C = number of coins supposed to be emitted in this halving event.
A = 1.072026880076
B = 0.46636556
N = blocks after the 1/2-way point, up to 8750 when N goes back to 1 and C is cut in half.

8750 is 4 years' worth of 4-hour periods. I didn't like 5, 7, or 10 hours because it is not a multiple of a day. 2 hours would have been harder to check in excel, having 2*8750 adjustment per halving. Other options were not an integer number of blocks. I guess 8 hours is an option.

I guess it could be improved to not have to reset C and N every 4 years.

I believe there is a starting point that is better in the sense that it results in a simpler equation that is good for all time, like ln(2) = 0.693 into a halving event or maybe 1/e into it or 1/e before the end.