[Contest] - Win 2 BTC for the best retargeting algorithm. Python testbed inside!

[Evil-Knievel]

I meant like a python example using the code above.
Your entry will be tested automatically later on for the standard error compared to the ideal tx rate.

[loracle]

What do you mean by slow initialization ?
If I understand your code correctly, the huge spikes are due to the fact that in the beginning, the amount of miners is multiplied by 6, then by 2, then by 0.68, etc so you have this ripple effect, and you can't do much about the spikes, you have to wait for the re targeting to happen for them to be corrected.

[Evil-Knievel]

What do you mean by slow initialization ?
If I understand your code correctly, the huge spikes are due to the fact that in the beginning, the amount of miners is multiplied by 6, then by 2, then by 0.68, etc so you have this ripple effect, and you can't do much about the spikes, you have to wait for the re targeting to happen for them to be corrected.

In the latest code (the one i attached to your reply) we start with 199381 miners, and 70242 add every 10 blocks.
The problem is the crappy initial "difficulty" which is very very low. It takes a few iterations to "converge". Until we converge we always max out the 20 max possible transactions per block.

 The less initial miners we have the faster it converges.

But since "pool hopping" may cause these very effects (huge loads of miners come suddenly) I think there are more elegant ways to level such spikes out. Pure KGW does not do that sufficiently, yet it does it good!

It might be wise to exceed the minimum possible factor 0.5 (that I observed during this phase) for some side cases.

Code:

how_many_miners_come_or_go = 70242
initial_miners = 199381

[loracle]

Okay I see, but like I said, this is due to the fact that we can't be aware there is that much miners on the network. All we see is 20 transactions per block. Because of this 20 transactions limit, we can't know how much transaction would have been really mined, so we can't know the hashing power of the network.

[ttookk]

Ok, I probably look extremely stupid for even asking it (certainly feel like it), but here it is anyway:

Can't we use Elastic itself for this?

It seems we have all it needs to at least give it a try:

- we have an array of possible variables.
- we have at least some kind of algorithm.

Couldn't we "just" bruteforce this to find factors per set of special cases, that can be applied? As in, play through as many combinations as possible and find the optimal factor per combination, then either find a median or a range in which the same factor can be used?

I realize, that an algorithm is more elegant, but it seems like a library with conditional factors may work as well. I don't mean to have some kind of factor ready for every single case, more like a factor per range. My hope is, that if we play through enough combinations to apply these factors (like, in the graphs shown, there is this spike every few blocks. if you know when to expect such a spike and maybe apply at least a little bit of stochastic, you may be able to level them out, just by applying "I see condition X, the most likely scenario is condition Y, so that's what I'm going for").

Does that make any sense at all?

Now, to actually use Elastic to find these conditional factors, I'd suggest to make a test run on testnet with greatly simplified conditions. If this works, we could "contract" miners to work on a special testnet version, whose only purpose is to find these conditional factors. Since we would know the power and number of miners on this network, we wouldn't need an optimal algorithm, yet. The miners would be paid with btc.

[Evil-Knievel]

Okay I see, but like I said, this is due to the fact that we can't be aware there is that much miners on the network. All we see is 20 transactions per block. Because of this 20 transactions limit, we can't know how much transaction would have been really mined, so we can't know the hashing power of the network.

Well, this is the tricky question. See this submission here:

I have just added a "optimistic" down throttling clause into the while loop:

Code:

# adjust hard-core if limit was reached in last 3 blocks
        if counter == 1 and pastMass == 20:
        	adjustment_speed_up = 0.05

So we do some "hard core" throttling which will likely result in way too few transactions per block. KGW can then "fix things" in the next block.
This approach is shitty and not perfect, but shows how greedy approaches could work.

Maybe some "intelligent exponential backoff just as implemented in TCP Vegas"?

Before, your code:



After, changed code:

Code:

import datetime
import random
import numpy as np
import matplotlib.pyplot as plt

# sudo apt-get install python-tk
# pip2 install numpy matplotlib

def create_block(timestamp, num_pow):
	return {'time_stamp' : timestamp, 'num_pow' : num_pow, 'first_work_factor':0}

def create_work(idx, factor, target):
	return {'id': idx, 'base_executions_per_second' : factor, 'target' : target}

def addSecs(tm, secs):
    fulldate = tm + datetime.timedelta(seconds=secs)
    return fulldate

def randomDuration():
	if do_not_randomize_block_times_but_do_always_60_sec:
		return 60
	else:
		return int(random.uniform(25, 120))

current_time = datetime.datetime.now()

# experiment with the number of work packages
works_to_create = 3

generate_blocks = 100
current_height = 0
blockchain = []
work_packages = []
base_target = 0x000000ffffffffffffffffffffffffff
poisson_distribution = np.random.poisson(5, generate_blocks)
stretch_number_pows = True
do_not_randomize_block_times_but_do_always_60_sec = True
new_miner_every_xth_second = 10
how_many_miners_come_or_go = 500
significant_miner_drop_to_100_on_block = 60
initial_miners = 700000000

def currently_active_miners(current_height):
	if current_height>=significant_miner_drop_to_100_on_block:
		return 100
	# get the current active number of miners in relation of blockchain height,
	# but the number of miners increases by 1 every 10 blocks
	increases = int(current_height/new_miner_every_xth_second) * how_many_miners_come_or_go
	return initial_miners+increases

	# for now, leave poisson distributed variable miner count out and assume only one miner
	ret = poisson_distribution[current_height]
	if ret > 0:
		return ret
	else:
		return 1

def miner_pows_based_on_target(work, height, dur):
	current_target = work["target"]
	factor = (current_target / base_target) * 1.0*dur/60.0
	actual_pow_mined = work["base_executions_per_second"]
	# random jitter
	actual_pow_mined = abs((actual_pow_mined - 1) + random.uniform(1,2)) * currently_active_miners(height)
	actual_pow_mined = actual_pow_mined *factor
	# rate limit to 20 pows per block
	if actual_pow_mined>20:
		actual_pow_mined = 20
	if actual_pow_mined < 0:
		actual_pow_mined = 0
	if actual_pow_mined == 0:
		print "mined",actual_pow_mined,work["base_executions_per_second"]*factor,currently_active_miners(height)
	return actual_pow_mined
def kimoto(x):
    return  1 + (0.7084 * pow(((x)/(144)), -1.228));
def retarget_work(block, x):
    targetI = x["target"]
    pastMass = 0
    counter = 0
    current_block = block
    current_block_timestamp = blockchain[current_block]["time_stamp"]
    adjustment = 0
    adjustment_speed_up = 1
    while True:
        counter += 1
        pastMass += blockchain[current_block]["num_pow"][x["id"]]

        # adjust hard-core if limit was reached in last 3 blocks
        if counter == 1 and pastMass == 20:
        	adjustment_speed_up = 0.05

        seconds_passed = (current_block_timestamp - blockchain[current_block-1]["time_stamp"]).seconds
        current_block -= 1
        if seconds_passed < 1:
            seconds_passed = 1
        trs_per_second = float(pastMass) / float(seconds_passed)
        target_per_second = 10.0 / 60.0
        adjustment = target_per_second / trs_per_second
        kim = kimoto(pastMass * 30)
        #print("kim : " + str(kim) + " adjustment : " + str(adjustment))
        if adjustment > kim or adjustment < (1.0/kim):
            print("SPEEDUP: " + str(adjustment_speed_up) + ", count: " + str(counter) + " kim : " + str(kim) + " 1/kim : " + str(1.0/kim) + " adj : " + str(adjustment))
            break
        if current_block < 1:
            break
    targetI = targetI * adjustment * adjustment_speed_up
    if targetI>base_target:
            targetI = base_target
    if x["id"] == 0:
            blockchain[block]["first_work_factor"] = adjustment
    x["target"] = targetI


def retarget_works(block):
	for x in work_packages:
		retarget_work(block,x)

# Here we create up to three different work objects
if works_to_create>=1:
	work_packages.append(create_work(0, 20, base_target))
if works_to_create>=2:
	work_packages.append(create_work(1, 60, base_target))
if works_to_create>=3:
	work_packages.append(create_work(2, 35, base_target))

while current_height < generate_blocks:
	dur = randomDuration()
	current_time = addSecs(current_time,dur) # random block generation time
	block_pows = {}
	for x in work_packages:
		num_pow = miner_pows_based_on_target(x, current_height, dur) # mine some POW depending on the current difficulty
		block_pows[x["id"]] = num_pow
	blockchain.append(create_block(current_time, block_pows))
	retarget_works(current_height) # This retargeting method is the "critical part here"
	current_height = current_height + 1


values = []
target_factors = []
ideal = []
for idx in range(len(blockchain)):
	if idx == 0:
		continue
	x = blockchain[idx]
	x_minus_one = blockchain[idx-1]
	time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
	strech_normalizer = time_passed / 60.0
	if stretch_number_pows == False:
		ideal.append(works_to_create*10*strech_normalizer)
	else:
		ideal.append(works_to_create*10)
	sum_x = 0
	for y in x["num_pow"]:
		sum_x += x["num_pow"][y]
	if stretch_number_pows == False:
		values.append(sum_x)
	else:
		values.append(sum_x/strech_normalizer)
x = range(generate_blocks)[1:]
y = values

#fig = plt.figure()
ax0 = plt.subplot(211)
if stretch_number_pows:
	ax0.set_ylabel('POW rate per 60s', color='b')
else:
	ax0.set_ylabel('POWs per Block', color='b')
ax0.set_xlabel('Block height')
ax0.plot(x,y,'-o',x,ideal,'r--')
values = []
ideal = []
target_factors = []
for idx in range(len(blockchain)):
	if idx == 0:
		continue
	x = blockchain[idx]
	x_minus_one = blockchain[idx-1]
	time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
	strech_normalizer = time_passed / 60.0
	if stretch_number_pows == False:
		ideal.append(10*strech_normalizer)
	else:
		ideal.append(10)
	sum_x = 0
	sum_x += x["num_pow"][0]
	#print "sumx",sum_x
	if stretch_number_pows == False:
		values.append(sum_x)
	else:
		values.append(sum_x/strech_normalizer)
x = range(generate_blocks)[1:]
y = values
plt.title('All Works: Total POWs')

ax1 = plt.subplot(212)
ax1.plot(x,y,'-o',x,ideal,'r--')
ax1.set_xlabel('Block Height')
# Make the y-axis label and tick labels match the line color.
if stretch_number_pows:
	ax1.set_ylabel('POW rate per 60s', color='b')
else:
	ax1.set_ylabel('POWs per Block', color='b')

for tl in ax1.get_yticklabels():
    tl.set_color('b')



ax2 = ax1.twinx()
ax2.set_ylim(0.4, 1.6)
ax2.bar(x,[x["first_work_factor"] for x in blockchain][1:],0.45,color='#deb0b0', alpha=0.2)
ax2.set_ylabel('Retargeting Factor', color='r')
for tl in ax2.get_yticklabels():
    tl.set_color('r')
plt.title('First Work: POWs + Retargeting Factor')

plt.show()

[loracle]

Indeed that's a good idea, here is my version, I count the number of full blocks, and divide the adjustment by 2^FullBlockCount. Also, I don't do it if there is only one block full before as it induces too much oscillations.

Code:

import datetime
import random
import numpy as np
import matplotlib.pyplot as plt

# sudo apt-get install python-tk
# pip2 install numpy matplotlib

def create_block(timestamp, num_pow):
	return {'time_stamp' : timestamp, 'num_pow' : num_pow, 'first_work_factor':0}

def create_work(idx, factor, target):
	return {'id': idx, 'base_executions_per_second' : factor, 'target' : target}

def addSecs(tm, secs):
    fulldate = tm + datetime.timedelta(seconds=secs)
    return fulldate

def randomDuration():
	if do_not_randomize_block_times_but_do_always_60_sec:
		return 60
	else:
		return int(random.uniform(25, 120))

current_time = datetime.datetime.now()

# experiment with the number of work packages
works_to_create = 3

generate_blocks = 100
current_height = 0
blockchain = []
work_packages = []
base_target = 0x000000ffffffffffffffffffffffffff
poisson_distribution = np.random.poisson(5, generate_blocks)
stretch_number_pows = True
do_not_randomize_block_times_but_do_always_60_sec = False
new_miner_every_xth_second = 10
how_many_miners_come_or_go = 70242
initial_miners = 199381

def currently_active_miners(current_height):
	# get the current active number of miners in relation of blockchain height,
	# but the number of miners increases by 1 every 10 blocks
	increases = int(current_height/new_miner_every_xth_second) * how_many_miners_come_or_go
	return initial_miners+increases

	# for now, leave poisson distributed variable miner count out and assume only one miner
	ret = poisson_distribution[current_height]
	if ret > 0:
		return ret
	else:
		return 1

def miner_pows_based_on_target(work, height, dur):
	current_target = work["target"]
	factor = (current_target / base_target) * 1.0*dur/60.0
	actual_pow_mined = work["base_executions_per_second"]
	# random jitter
	actual_pow_mined = abs((actual_pow_mined - 1) + random.uniform(1,2)) * currently_active_miners(height)
	actual_pow_mined = actual_pow_mined *factor
	# rate limit to 20 pows per block
        if actual_pow_mined > 20:
            actual_pow_mined = 20
	if actual_pow_mined < 0:
		actual_pow_mined = 0
	if actual_pow_mined == 0:
		print "mined",actual_pow_mined,work["base_executions_per_second"]*factor,currently_active_miners(height)
	return actual_pow_mined
def kimoto(x):
    return  1 + (0.7084 * pow(((x)/(144)), -1.228));
def retarget_work(block, x):
    targetI = x["target"]
    pastMass = 0
    counter = 0
    current_block = block
    current_block_timestamp = blockchain[current_block]["time_stamp"]
    adjustment = 0
    isFull = True
    fullCnt = 0
    isEmpty = True
    emptyCnt = 0
    while isFull or isEmpty:
        if isFull and blockchain[current_block]["num_pow"][x["id"]] == 20:
            fullCnt += 1
        else:
            isFull = False
        if isEmpty and blockchain[current_block]["num_pow"][x["id"]] == 0:
            emptyCnt += 1
        else:
            isEmpty = False
        current_block -= 1
        if current_block < 1:
            break
    current_block = block
    while True:
        counter += 1
        pastMass += blockchain[current_block]["num_pow"][x["id"]]
        seconds_passed = (current_block_timestamp - blockchain[current_block-1]["time_stamp"]).seconds
        current_block -= 1
        if seconds_passed < 1:
            seconds_passed = 1
        trs_per_second = float(pastMass) / float(seconds_passed)
        target_per_second = 10.0 / 60.0
        adjustment = target_per_second / trs_per_second
        kim = kimoto(pastMass * 30)
        #print("kim : " + str(kim) + " adjustment : " + str(adjustment))
        if adjustment > kim or adjustment < (1.0/kim):
            break
        if current_block < 1:
            break
    if fullCnt > 1:
        adjustment = adjustment / (1 << (fullCnt))
    if emptuCnt > 1:
        adjustment = adjustment * (1 << (emptyCnt))
    targetI = targetI * adjustment
    if targetI>base_target:
            targetI = base_target
    if x["id"] == 0:
            blockchain[block]["first_work_factor"] = adjustment
    x["target"] = targetI


def retarget_works(block):
	for x in work_packages:
		retarget_work(block,x)

# Here we create up to three different work objects
if works_to_create>=1:
	work_packages.append(create_work(0, 20, base_target))
if works_to_create>=2:
	work_packages.append(create_work(1, 60, base_target))
if works_to_create>=3:
	work_packages.append(create_work(2, 35, base_target))

while current_height < generate_blocks:
	dur = randomDuration()
	current_time = addSecs(current_time,dur) # random block generation time
	block_pows = {}
	for x in work_packages:
		num_pow = miner_pows_based_on_target(x, current_height, dur) # mine some POW depending on the current difficulty
		block_pows[x["id"]] = num_pow
	blockchain.append(create_block(current_time, block_pows))
	retarget_works(current_height) # This retargeting method is the "critical part here"
	current_height = current_height + 1


values = []
target_factors = []
ideal = []
for idx in range(len(blockchain)):
	if idx == 0:
		continue
	x = blockchain[idx]
	x_minus_one = blockchain[idx-1]
	time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
	strech_normalizer = time_passed / 60.0
	if stretch_number_pows == False:
		ideal.append(works_to_create*10*strech_normalizer)
	else:
		ideal.append(works_to_create*10)
	sum_x = 0
	for y in x["num_pow"]:
		sum_x += x["num_pow"][y]
	if stretch_number_pows == False:
		values.append(sum_x)
	else:
		values.append(sum_x/strech_normalizer)
x = range(generate_blocks)[1:]
y = values

#fig = plt.figure()
ax0 = plt.subplot(211)
if stretch_number_pows:
	ax0.set_ylabel('POW rate per 60s', color='b')
else:
	ax0.set_ylabel('POWs per Block', color='b')
ax0.set_xlabel('Block height')
ax0.plot(x,y,'-o',x,ideal,'r--')
values = []
ideal = []
target_factors = []
for idx in range(len(blockchain)):
	if idx == 0:
		continue
	x = blockchain[idx]
	x_minus_one = blockchain[idx-1]
	time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
	strech_normalizer = time_passed / 60.0
	if stretch_number_pows == False:
		ideal.append(10*strech_normalizer)
	else:
		ideal.append(10)
	sum_x = 0
	sum_x += x["num_pow"][0]
	#print "sumx",sum_x
	if stretch_number_pows == False:
		values.append(sum_x)
	else:
		values.append(sum_x/strech_normalizer)
x = range(generate_blocks)[1:]
y = values
plt.title('All Works: Total POWs')

ax1 = plt.subplot(212)
ax1.plot(x,y,'-o',x,ideal,'r--')
ax1.set_xlabel('Block Height')
# Make the y-axis label and tick labels match the line color.
if stretch_number_pows:
	ax1.set_ylabel('POW rate per 60s', color='b')
else:
	ax1.set_ylabel('POWs per Block', color='b')

for tl in ax1.get_yticklabels():
    tl.set_color('b')



ax2 = ax1.twinx()
ax2.set_ylim(0.4, 1.6)
ax2.bar(x,[x["first_work_factor"] for x in blockchain][1:],0.45,color='#deb0b0', alpha=0.2)
ax2.set_ylabel('Retargeting Factor', color='r')
for tl in ax2.get_yticklabels():
    tl.set_color('r')
plt.title('First Work: POWs + Retargeting Factor')

plt.show()

With random block time:

https://i.imgur.com/dqPTtAG.png

With fixed block time:

https://i.imgur.com/f1Rml4j.png

[GilAlexander]

Well, let we have N>20 transactions in the last block and 0<B<=20 before that. Let we assume that maximal sudden spike in hashrate is always less than q times. Then 20<N<qB. You know neither N nor distribution of N. If you want to have the fastest retarget for any case you need to take uniform distribution of N. Then the mean is (qB+20)/2=M. If you cut the hashrate in (M/10) times now, the expected number of transactions in the next block will be 10. Then you need to adjust difficulty more precisely and fight with possible timewarp exploits. If N was really in 20..qB range, then the approach gives you the fastest retarget.

[Limx Dev]

* Kimoto's Gravity Well
   - Auroracoin implementation (from MegaCoin)
   - Dash implementation (above plus handling of negative uint256 and parameter change)
   - Vulnerable to Timewarp Attack (has been carried out on an altcoin).
       timewarp attacks attempt to decrease the difficulty to then mine many coins fast, or with a 51% attack mine a new chain from the genesis block.

* Nite's Gravity Well
  - Implements fix for KGW Timewarp Attack.
  - I can't find any particular reference to the other changes notsofast refers to, and the AuroraCoin source doesn't even appear to use it (they changed     to a different calculation for a multi-PoW-algorithm setup AFAICT).

* DigiShield
   - DigiByte implementation of v3 (there are four versions, see above and below that function).
   - Designed to overcome the issues of the Kimoto Gravity Well algorithm in recovering from large multipool engagements.
   - Asymmetric (allows difficulty to decrease faster than it can increase) .
   - Possibly makes it vulnerable to timewarp attacks, but no proof yet.

* Dark Gravity Wave
   - Dash implementation
 - Combines multiple exponential and simple moving averages to smooth difficulty readjustments and mitigate against exploits in the Kimoto Gravity Well.

I have create the Dual KGW 3 (DK3).



This works already in Europecoin V3/ Bitsend Block 239K and the termdeposit is excatly over months. The function Diffbreak protect the chain. (Reduce the diff after 6h) etc....
I am not sure whether it with elastic works.

[Evil-Knievel]

Limx, if you want to "enter" you need to provide a variant of this PoC code.

Here is loracle's last version with some "security patches" of mine which prevent "Time Warp" (and a few other) attacks:

Code:

import datetime
import random
import numpy as np
import matplotlib.pyplot as plt

# sudo apt-get install python-tk
# pip2 install numpy matplotlib

def create_block(timestamp, num_pow):
    return {'time_stamp' : timestamp, 'num_pow' : num_pow, 'first_work_factor':0}

def create_work(idx, factor, target):
    return {'id': idx, 'base_executions_per_second' : factor, 'target' : target}

def addSecs(tm, secs):
    fulldate = tm + datetime.timedelta(seconds=secs)
    return fulldate

def randomDuration():
    if do_not_randomize_block_times_but_do_always_60_sec:
        return 60
    else:
        return int(random.uniform(25, 120))

current_time = datetime.datetime.now()

# experiment with the number of work packages
works_to_create = 3

generate_blocks = 100
current_height = 0
blockchain = []
work_packages = []
base_target = 0x000000ffffffffffffffffffffffffff
poisson_distribution = np.random.poisson(5, generate_blocks)
stretch_number_pows = True
do_not_randomize_block_times_but_do_always_60_sec = True
new_miner_every_xth_second = 10
how_many_miners_come_or_go = 70242
initial_miners = 50
miners_kick_in_at_block=50

def currently_active_miners(current_height):
    if current_height<miners_kick_in_at_block:
        return 0
    # get the current active number of miners in relation of blockchain height,
    # but the number of miners increases by 1 every 10 blocks
    increases = int(current_height/new_miner_every_xth_second) * how_many_miners_come_or_go
    return initial_miners+increases

def miner_pows_based_on_target(work, height, dur):
    current_target = work["target"]
    factor = (current_target / base_target) * 1.0*dur/60.0
    actual_pow_mined = work["base_executions_per_second"]
    # random jitter
    actual_pow_mined = abs((actual_pow_mined - 1) + random.uniform(1,2)) * currently_active_miners(height)
    actual_pow_mined = actual_pow_mined *factor
    # rate limit to 20 pows per block
    if actual_pow_mined > 20:
        actual_pow_mined = 20
    if actual_pow_mined < 0:
        actual_pow_mined = 0
    return actual_pow_mined
def kimoto(x):
    return  1 + (0.7084 * pow(((x)/(144)), -1.228));
def retarget_work(block, x):
    targetI = x["target"]
    pastMass = 0
    counter = 0
    current_block = block
    current_block_timestamp = blockchain[current_block]["time_stamp"]
    adjustment = 0
    isFull = True
    fullCnt = 0
    isEmpty = True
    max_block_reading = 144
    emptyCnt = 0
    while isFull or isEmpty:
        if isFull and blockchain[current_block]["num_pow"][x["id"]] == 20:
            fullCnt += 1
        else:
            isFull = False
        if isEmpty and blockchain[current_block]["num_pow"][x["id"]] == 0:
            emptyCnt += 1
        else:
            isEmpty = False
        current_block -= 1
        if current_block < 1:
            break
    current_block = block
    while True:
        counter += 1
        pastMass += blockchain[current_block]["num_pow"][x["id"]]
        if current_block_timestamp < blockchain[current_block-1]["time_stamp"]:
            current_block_timestamp = blockchain[current_block-1]["time_stamp"]
        seconds_passed = (current_block_timestamp - blockchain[current_block-1]["time_stamp"]).seconds
        current_block -= 1
        if seconds_passed < 1:
            seconds_passed = 1
        trs_per_second = float(pastMass) / float(seconds_passed)
        target_per_second = 10.0 / 60.0
        if trs_per_second > 0:
            adjustment = target_per_second / trs_per_second
            kim = kimoto(pastMass * 30)
            if adjustment > kim or adjustment < (1.0/kim):
                break
        else:
            adjustment = 1
        if current_block < 1 or counter == max_block_reading:
            break

    if fullCnt > 1:
        adjustment = adjustment / (1 << fullCnt)
    if emptyCnt > 1:
        adjustment = adjustment * (1 << emptyCnt)
    targetI = targetI * adjustment
    if targetI>base_target:
            targetI = base_target
    if x["id"] == 0:
            blockchain[block]["first_work_factor"] = adjustment
    x["target"] = targetI
    print "Retarget using",counter,"blocks","fullcnt",fullCnt,"emptyCnt",emptyCnt


def retarget_works(block):
    for x in work_packages:
        retarget_work(block,x)

# Here we create up to three different work objects
if works_to_create>=1:
    work_packages.append(create_work(0, 20, base_target))
if works_to_create>=2:
    work_packages.append(create_work(1, 60, base_target))
if works_to_create>=3:
    work_packages.append(create_work(2, 35, base_target))

while current_height < generate_blocks:
    dur = randomDuration()
    current_time = addSecs(current_time,dur) # random block generation time
    block_pows = {}
    for x in work_packages:
        num_pow = miner_pows_based_on_target(x, current_height, dur) # mine some POW depending on the current difficulty
        block_pows[x["id"]] = num_pow
    blockchain.append(create_block(current_time, block_pows))
    retarget_works(current_height) # This retargeting method is the "critical part here"
    current_height = current_height + 1


values = []
target_factors = []
ideal = []
for idx in range(len(blockchain)):
    if idx == 0:
        continue
    x = blockchain[idx]
    x_minus_one = blockchain[idx-1]
    time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
    strech_normalizer = time_passed / 60.0
    if stretch_number_pows == False:
        ideal.append(works_to_create*10*strech_normalizer)
    else:
        ideal.append(works_to_create*10)
    sum_x = 0
    for y in x["num_pow"]:
        sum_x += x["num_pow"][y]
    if stretch_number_pows == False:
        values.append(sum_x)
    else:
        values.append(sum_x/strech_normalizer)
x = range(generate_blocks)[1:]
y = values

#fig = plt.figure()
ax0 = plt.subplot(211)
if stretch_number_pows:
    ax0.set_ylabel('POW rate per 60s', color='b')
else:
    ax0.set_ylabel('POWs per Block', color='b')
ax0.set_xlabel('Block height')
ax0.plot(x,y,'-o',x,ideal,'r--')
values = []
ideal = []
target_factors = []
for idx in range(len(blockchain)):
    if idx == 0:
        continue
    x = blockchain[idx]
    x_minus_one = blockchain[idx-1]
    time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
    strech_normalizer = time_passed / 60.0
    if stretch_number_pows == False:
        ideal.append(10*strech_normalizer)
    else:
        ideal.append(10)
    sum_x = 0
    sum_x += x["num_pow"][0]
    #print "sumx",sum_x
    if stretch_number_pows == False:
        values.append(sum_x)
    else:
        values.append(sum_x/strech_normalizer)
x = range(generate_blocks)[1:]
y = values
plt.title('All Works: Total POWs')

ax1 = plt.subplot(212)
ax1.plot(x,y,'-o',x,ideal,'r--')
ax1.set_xlabel('Block Height')
# Make the y-axis label and tick labels match the line color.
if stretch_number_pows:
    ax1.set_ylabel('POW rate per 60s', color='b')
else:
    ax1.set_ylabel('POWs per Block', color='b')

for tl in ax1.get_yticklabels():
    tl.set_color('b')



ax2 = ax1.twinx()
ax2.set_ylim(0.4, 1.6)
ax2.bar(x,[x["first_work_factor"] for x in blockchain][1:],0.45,color='#deb0b0', alpha=0.2)
ax2.set_ylabel('Retargeting Factor', color='r')
for tl in ax2.get_yticklabels():
    tl.set_color('r')
plt.title('First Work: POWs + Retargeting Factor')

plt.show()

[sormin]

This may be Very Difficult,
satoshi Nakamoto would not be able 

[Limx Dev]

Limx, if you want to "enter" you need to provide a variant of this PoC code.

Here is loracle's last version with some "security patches" of mine which prevent "Time Warp" (and a few other) attacks:

Code:

import datetime
import random
import numpy as np
import matplotlib.pyplot as plt

# sudo apt-get install python-tk
# pip2 install numpy matplotlib

def create_block(timestamp, num_pow):
    return {'time_stamp' : timestamp, 'num_pow' : num_pow, 'first_work_factor':0}

def create_work(idx, factor, target):
    return {'id': idx, 'base_executions_per_second' : factor, 'target' : target}

def addSecs(tm, secs):
    fulldate = tm + datetime.timedelta(seconds=secs)
    return fulldate

def randomDuration():
    if do_not_randomize_block_times_but_do_always_60_sec:
        return 60
    else:
        return int(random.uniform(25, 120))

current_time = datetime.datetime.now()

# experiment with the number of work packages
works_to_create = 3

generate_blocks = 100
current_height = 0
blockchain = []
work_packages = []
base_target = 0x000000ffffffffffffffffffffffffff
poisson_distribution = np.random.poisson(5, generate_blocks)
stretch_number_pows = True
do_not_randomize_block_times_but_do_always_60_sec = True
new_miner_every_xth_second = 10
how_many_miners_come_or_go = 70242
initial_miners = 50
miners_kick_in_at_block=50

def currently_active_miners(current_height):
    if current_height<miners_kick_in_at_block:
        return 0
    # get the current active number of miners in relation of blockchain height,
    # but the number of miners increases by 1 every 10 blocks
    increases = int(current_height/new_miner_every_xth_second) * how_many_miners_come_or_go
    return initial_miners+increases

def miner_pows_based_on_target(work, height, dur):
    current_target = work["target"]
    factor = (current_target / base_target) * 1.0*dur/60.0
    actual_pow_mined = work["base_executions_per_second"]
    # random jitter
    actual_pow_mined = abs((actual_pow_mined - 1) + random.uniform(1,2)) * currently_active_miners(height)
    actual_pow_mined = actual_pow_mined *factor
    # rate limit to 20 pows per block
    if actual_pow_mined > 20:
        actual_pow_mined = 20
    if actual_pow_mined < 0:
        actual_pow_mined = 0
    return actual_pow_mined
def kimoto(x):
    return  1 + (0.7084 * pow(((x)/(144)), -1.228));
def retarget_work(block, x):
    targetI = x["target"]
    pastMass = 0
    counter = 0
    current_block = block
    current_block_timestamp = blockchain[current_block]["time_stamp"]
    adjustment = 0
    isFull = True
    fullCnt = 0
    isEmpty = True
    max_block_reading = 144
    emptyCnt = 0
    while isFull or isEmpty:
        if isFull and blockchain[current_block]["num_pow"][x["id"]] == 20:
            fullCnt += 1
        else:
            isFull = False
        if isEmpty and blockchain[current_block]["num_pow"][x["id"]] == 0:
            emptyCnt += 1
        else:
            isEmpty = False
        current_block -= 1
        if current_block < 1:
            break
    current_block = block
    while True:
        counter += 1
        pastMass += blockchain[current_block]["num_pow"][x["id"]]
        if current_block_timestamp < blockchain[current_block-1]["time_stamp"]:
            current_block_timestamp = blockchain[current_block-1]["time_stamp"]
        seconds_passed = (current_block_timestamp - blockchain[current_block-1]["time_stamp"]).seconds
        current_block -= 1
        if seconds_passed < 1:
            seconds_passed = 1
        trs_per_second = float(pastMass) / float(seconds_passed)
        target_per_second = 10.0 / 60.0
        if trs_per_second > 0:
            adjustment = target_per_second / trs_per_second
            kim = kimoto(pastMass * 30)
            if adjustment > kim or adjustment < (1.0/kim):
                break
        else:
            adjustment = 1
        if current_block < 1 or counter == max_block_reading:
            break

    if fullCnt > 1:
        adjustment = adjustment / (1 << fullCnt)
    if emptyCnt > 1:
        adjustment = adjustment * (1 << emptyCnt)
    targetI = targetI * adjustment
    if targetI>base_target:
            targetI = base_target
    if x["id"] == 0:
            blockchain[block]["first_work_factor"] = adjustment
    x["target"] = targetI
    print "Retarget using",counter,"blocks","fullcnt",fullCnt,"emptyCnt",emptyCnt


def retarget_works(block):
    for x in work_packages:
        retarget_work(block,x)

# Here we create up to three different work objects
if works_to_create>=1:
    work_packages.append(create_work(0, 20, base_target))
if works_to_create>=2:
    work_packages.append(create_work(1, 60, base_target))
if works_to_create>=3:
    work_packages.append(create_work(2, 35, base_target))

while current_height < generate_blocks:
    dur = randomDuration()
    current_time = addSecs(current_time,dur) # random block generation time
    block_pows = {}
    for x in work_packages:
        num_pow = miner_pows_based_on_target(x, current_height, dur) # mine some POW depending on the current difficulty
        block_pows[x["id"]] = num_pow
    blockchain.append(create_block(current_time, block_pows))
    retarget_works(current_height) # This retargeting method is the "critical part here"
    current_height = current_height + 1


values = []
target_factors = []
ideal = []
for idx in range(len(blockchain)):
    if idx == 0:
        continue
    x = blockchain[idx]
    x_minus_one = blockchain[idx-1]
    time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
    strech_normalizer = time_passed / 60.0
    if stretch_number_pows == False:
        ideal.append(works_to_create*10*strech_normalizer)
    else:
        ideal.append(works_to_create*10)
    sum_x = 0
    for y in x["num_pow"]:
        sum_x += x["num_pow"][y]
    if stretch_number_pows == False:
        values.append(sum_x)
    else:
        values.append(sum_x/strech_normalizer)
x = range(generate_blocks)[1:]
y = values

#fig = plt.figure()
ax0 = plt.subplot(211)
if stretch_number_pows:
    ax0.set_ylabel('POW rate per 60s', color='b')
else:
    ax0.set_ylabel('POWs per Block', color='b')
ax0.set_xlabel('Block height')
ax0.plot(x,y,'-o',x,ideal,'r--')
values = []
ideal = []
target_factors = []
for idx in range(len(blockchain)):
    if idx == 0:
        continue
    x = blockchain[idx]
    x_minus_one = blockchain[idx-1]
    time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
    strech_normalizer = time_passed / 60.0
    if stretch_number_pows == False:
        ideal.append(10*strech_normalizer)
    else:
        ideal.append(10)
    sum_x = 0
    sum_x += x["num_pow"][0]
    #print "sumx",sum_x
    if stretch_number_pows == False:
        values.append(sum_x)
    else:
        values.append(sum_x/strech_normalizer)
x = range(generate_blocks)[1:]
y = values
plt.title('All Works: Total POWs')

ax1 = plt.subplot(212)
ax1.plot(x,y,'-o',x,ideal,'r--')
ax1.set_xlabel('Block Height')
# Make the y-axis label and tick labels match the line color.
if stretch_number_pows:
    ax1.set_ylabel('POW rate per 60s', color='b')
else:
    ax1.set_ylabel('POWs per Block', color='b')

for tl in ax1.get_yticklabels():
    tl.set_color('b')



ax2 = ax1.twinx()
ax2.set_ylim(0.4, 1.6)
ax2.bar(x,[x["first_work_factor"] for x in blockchain][1:],0.45,color='#deb0b0', alpha=0.2)
ax2.set_ylabel('Retargeting Factor', color='r')
for tl in ax2.get_yticklabels():
    tl.set_color('r')
plt.title('First Work: POWs + Retargeting Factor')

plt.show()

Okay, I look it tonight.

[Evil-Knievel]

So essentially, with the dummy seed right now, loracle's algorithm reaches an error of 6 per block, which is somewhat bad i think! The error is counted in the global case. So on average (of the targetted 30 POW per block, were 6 off)

Code:

Executing run 0
  -> generated block 0
Run 0 - total error = 2.51886191335
Executing run 1
  -> generated block 0
Run 1 - total error = 2.62137314327
Executing run 2
  -> generated block 0
Run 2 - total error = 4.95028524559
Executing run 3
  -> generated block 0
Run 3 - total error = 2.73114641499
Executing run 4
  -> generated block 0
Run 4 - total error = 6.15524345231
Executing run 5
  -> generated block 0
Run 5 - total error = 2.40522822993
Executing run 6
  -> generated block 0
Run 6 - total error = 2.28732108474
Executing run 7
  -> generated block 0
Run 7 - total error = 2.38065310135
Executing run 8
  -> generated block 0
Run 8 - total error = 2.56361782843
Largest error: 6.15524345231
anonymous@bunghole ~/Development/ret

Note: If anyone of you disagrees with the testing method, please ask before the contest ends ;-) We can improve the tests of course. But that has to be done before the seeding hash is known!

[Evil-Knievel]

Hint ... for the late ones.

what about DGW?
https://github.com/dashpay/dash/blob/master/src/pow.cpp#L82

Or the ppcoin adjustment?

Code:

unsigned int GetNextWorkRequired(const CBlockIndex* pindexLast, const CBlockHeader *pblock, const Consensus::Params& params)
{
    const PowAlgo algo = pblock->GetAlgo();
    const arith_uint256 bnProofOfWorkLimit = UintToArith256(params.powLimit[algo]);
    const unsigned nProofOfWorkLimit = bnProofOfWorkLimit.GetCompact();

    if (!pindexLast)
        return nProofOfWorkLimit;
    if (params.fPowNoRetargeting)
        return pindexLast->nBits;

    const CBlockIndex* pindexPrev = GetLastBlockIndex(pindexLast, algo);
    if (!pindexPrev || !pindexPrev->pprev)
        return nProofOfWorkLimit; // first block
    const CBlockIndex* pindexPrevPrev = GetLastBlockIndex(pindexPrev->pprev, algo);
    if (!pindexPrevPrev || !pindexPrevPrev->pprev)
        return nProofOfWorkLimit; // second block

    const int64_t nActualSpacing = pindexPrev->GetBlockTime() - pindexPrevPrev->GetBlockTime();

    // ppcoin: target change every block
    // ppcoin: retarget with exponential moving toward target spacing
    arith_uint256 bnNew;
    bnNew.SetCompact(pindexPrev->nBits);

    /* The old computation here was:
      
          bnNew *= (nInterval - 1) * nTargetSpacing + 2 * nActualSpacing;
          bnNew /= (nInterval + 1) * nTargetSpacing;

       This, however, may exceed 256 bits for a low difficulty in the
       intermediate step.  We can rewrite it:

          A = (nInterval + 1) nTargetSpacing
          bnNew *= A + 2 (nActualSpacing - nTargetSpacing)
          bnNew /= A

       Or also:

          A = (nInterval + 1) nTargetSpacing
          B = (nActualSpacing - nTargetSpacing)
          bnNew = (bnNew A + bnNew 2 B) / A = bnNew + (2 bnNew B) / A

      To compute (2 bnNew B) / A without overflowing, let

          bnNew = P * A + R.

      Then

          (2 bnNew B) / A = 2 P B + (2 R B) / A.

      Assuming that A is not too large (which it definitely isn't in comparison
      to 256 bits), also (2 R B) does not overflow before the divide.

    */

    const int64_t nInterval = params.DifficultyAdjustmentInterval();

    const int64_t a = (nInterval + 1) * params.nPowTargetSpacing;
    const int64_t b = nActualSpacing - params.nPowTargetSpacing;
    const arith_uint256 p = bnNew / a;
    const arith_uint256 r = bnNew - p * a;

    /* Make sure to get the division right for negative b!  Division is
       not "preserved" under two's complement.  */
    if (b >= 0)
        bnNew += 2 * p * b + (2 * r * b) / a;
    else
        bnNew -= 2 * p * (-b) + (2 * r * (-b)) / a;

    if (bnNew > bnProofOfWorkLimit)
        bnNew = bnProofOfWorkLimit;

    return bnNew.GetCompact();
}

try out and maybe win 

[HunterMinerCrafter]

Okay I see, but like I said, this is due to the fact that we can't be aware there is that much miners on the network. All we see is 20 transactions per block. Because of this 20 transactions limit, we can't know how much transaction would have been really mined, so we can't know the hashing power of the network.

We might need to think about this a bit further in the broader context of XEL.  (It does seem like volatility could end up being introduced (to any targeting algorithm) from the work limiting.)

[HunterMinerCrafter]

Note: If anyone of you disagrees with the testing method, please ask before the contest ends ;-) We can improve the tests of course. But that has to be done before the seeding hash is known!

It would probably be ideal to be able to test more behaviors.  As it is, it seems like an algorithm that wins the contest easily could significantly under-perform in less uniform churn behavior scenarios.

[VeryNewMember]

A totally experimental creation of mine. At least it beats the error of the other submissions.

Code:

import datetime
import random
import numpy as np
import matplotlib.pyplot as plt

# sudo apt-get install python-tk
# pip2 install numpy matplotlib


class RetargetTest():
    # experiment with the number of work packages
    def __init__(self):
        self.current_time = datetime.datetime.now()
        self.works_to_create = 3
        self.generate_blocks = 100
        self.current_height = 0
        self.blockchain = []
        self.work_packages = []
        self.base_target = 0x000000ffffffffffffffffffffffffff
        self.stretch_number_pows = True
        self.do_not_randomize_block_times_but_do_always_60_sec = True
        self.new_miner_every_xth_second = 10
        self.how_many_miners_come_or_go = 70242
        self.initial_miners = 50
        self.miners_kick_in_at_block=50
        self.miners_drop_at = 0
        self.miners_drop_for=20
        self.jitter_size = 0

    def seeder(self, hasher):
        random.seed(hasher)

    def randomize_params(self):
        self.generate_blocks = random.randint(80,500)
        self.new_miner_every_xth_second = random.randint(5,50)
        self.how_many_miners_come_or_go = random.randint(0,1000000)
        self.initial_miners = random.randint(0,1000000) 
        self.miners_kick_in_at_block = random.randint(0,40) 
        self.jitter_size = random.randint(1,7) 
        self.miners_drop_at = random.randint(self.generate_blocks/2,self.generate_blocks)
        pass

    def create_block(self,timestamp, num_pow):
        return {'time_stamp' : timestamp, 'num_pow' : num_pow, 'first_work_factor':0}

    def create_work(self,idx, factor, target):
        return {'id': idx, 'base_executions_per_second' : factor, 'target' : target}

    def addSecs(self,tm, secs):
        fulldate = tm + datetime.timedelta(seconds=secs)
        return fulldate

    def randomDuration(self):
        if self.do_not_randomize_block_times_but_do_always_60_sec:
            return 60
        else:
            return int(random.uniform(25, 120))

    def currently_active_miners(self,current_height):
        if self.current_height<self.miners_kick_in_at_block:
            return 0

        if self.current_height>=self.miners_drop_at and self.current_height<=self.miners_drop_at+self.miners_drop_for:
            return 0
        # get the current active number of miners in relation of blockchain height,
        # but the number of miners increases by 1 every 10 blocks
        increases = int(self.current_height/self.new_miner_every_xth_second) * self.how_many_miners_come_or_go
        return self.initial_miners+increases

    def miner_pows_based_on_target(self,work, height, dur):
        current_target = work["target"]
        factor = (current_target / self.base_target) * 1.0*dur/60.0
        actual_pow_mined = work["base_executions_per_second"]
        # random jitter
        actual_pow_mined = abs((actual_pow_mined - self.jitter_size) + random.uniform(self.jitter_size,2*self.jitter_size)) * self.currently_active_miners(height)
        if actual_pow_mined < 0:
            actual_pow_mined = 0
        actual_pow_mined = actual_pow_mined *factor
        # rate limit to 20 pows per block
        if actual_pow_mined > 20:
            actual_pow_mined = 20
        if actual_pow_mined < 0:
            actual_pow_mined = 0
        return actual_pow_mined
    def kimoto(self,x):
        return  1 + (0.7084 * pow(((x)/(144)), -1.228))

    def retarget_work(self,block, x):
        targetI = x["target"]
        pastMass = 0
        counter = 0
        current_block = block
        current_block_timestamp = self.blockchain[current_block]["time_stamp"]
        adjustment = 0
        max_block_reading = 44
        min_block_reading = 2

        lowerbound = 0.2
        higherbound = 1.8

        minval = 0x000000ffffffffffffffffffffffffff
        maxval = 0

        ultra_aggressive = False
        modest_aggressive = False
        was_negative = False
        seconds_passed = 0
        while True:
            counter += 1
            currpows = self.blockchain[current_block]["num_pow"][x["id"]]
            pastMass += currpows
            if currpows<minval:
                minval=currpows
            if currpows>maxval:
                maxval=currpows
            old_seconds_passed = seconds_passed
            seconds_passed = (current_block_timestamp - self.blockchain[current_block-1]["time_stamp"]).seconds
            if current_block_timestamp < self.blockchain[current_block-1]["time_stamp"]:
                current_block_timestamp = self.blockchain[current_block-1]["time_stamp"]
            current_block -= 1
            if seconds_passed < 1:
                seconds_passed = 1

            seconds_target_passed = pastMass * 6 # 6 seconds per POW
            adj = seconds_target_passed / seconds_passed
            
            # break if  fluctuations are too heavy
            if counter*20 == pastMass and counter >= min_block_reading:
                ultra_aggressive = True
                break

            if counter==1:
                if adj<1:
                    was_negative = True
            else:
                if adj<1 and was_negative == False:
                    seconds_passed = old_seconds_passed
                    pastMass -= currpows
                    break
                if adj>=1 and was_negative == True:
                    seconds_passed = old_seconds_passed
                    pastMass -= currpows
                    break

            if minval > 0 and maxval/minval>1.5:
                modest_aggressive = True

            if minval > 0 and maxval/minval>1.5 and counter >= min_block_reading:
                break

            if current_block < 1 or counter == max_block_reading:
                break
        print "used",counter
        lowerbound = min(0.75,lowerbound+counter*0.25)
        higherbound = max(1.25,higherbound-counter*0.25)
        
        if pastMass>=1 and ultra_aggressive==False:
            seconds_target_passed = pastMass * 6 # 6 seconds per POW
            adj = seconds_target_passed / seconds_passed
            if adj<lowerbound:
                adj=lowerbound
            if adj>higherbound:
                adj=higherbound

            if modest_aggressive and adj>=1:
                adj *= 1.2
            if modest_aggressive and adj<1:
                adj /= 1.2

            targetI /= adj
        elif pastMass>=1 and ultra_aggressive==True:
            targetI = targetI/(3*counter)
        else:
            targetI *= 2


        if targetI>self.base_target:
            targetI = self.base_target
        if targetI<1000:
            targetI=1000
        if x["id"] == 0:
            self.blockchain[block]["first_work_factor"] = adjustment
        x["target"] = targetI
        #print "Retarget using",counter,"blocks","fullcnt",fullCnt,"emptyCnt",emptyCnt


    def retarget_works(self,block):
        for x in self.work_packages:
            self.retarget_work(block,x)


    def reset_chain(self):
        self.blockchain = []
        self.work_packages = []
        self.current_height = 0
        self.current_time = datetime.datetime.now()

        # Here we create up to three different work objects
        if self.works_to_create>=1:
            self.work_packages.append(self.create_work(0, 20, self.base_target))
        if self.works_to_create>=2:
            self.work_packages.append(self.create_work(1, 60, self.base_target))
        if self.works_to_create>=3:
            self.work_packages.append(self.create_work(2, 35, self.base_target))

    def generate_chain(self):
        while self.current_height < self.generate_blocks:
            if self.current_height%1000==0:
                print "  -> generated block",self.current_height
            dur = self.randomDuration()
            self.current_time = self.addSecs(self.current_time,dur) # random block generation time
            block_pows = {}
            for x in self.work_packages:
                num_pow = self.miner_pows_based_on_target(x, self.current_height, dur) # mine some POW depending on the current difficulty
                block_pows[x["id"]] = num_pow
            self.blockchain.append(self.create_block(self.current_time, block_pows))
            self.retarget_works(self.current_height) # This retargeting method is the "critical part here"
            self.current_height = self.current_height + 1

    def get_total_error(self):
        values = []
        ideal = []
        for idx in range(len(self.blockchain)):
            if idx == 0:
                continue
            x = self.blockchain[idx]
            x_minus_one = self.blockchain[idx-1]
            time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
            strech_normalizer = time_passed / 60.0
           
            sum_x = 0
            for y in x["num_pow"]:
                sum_x += x["num_pow"][y]

            if sum_x == 0:
                ideal.append(0)
            else:
                if self.stretch_number_pows == False:
                    ideal.append(self.works_to_create*10*strech_normalizer)
                else:
                    ideal.append(self.works_to_create*10)


            if self.stretch_number_pows == False:
                values.append(sum_x)
            else:
                values.append(sum_x/strech_normalizer)
        #print values
        #print ideal
        total_error = 0
        for x in range(len(values)):
            soll = ideal[x]
            ist = values[x]
            total_error += abs(soll-ist)
        return total_error/len(values)

    def plot(self,run):
        values = []
        target_factors = []
        ideal = []
        for idx in range(len(self.blockchain)):
            if idx == 0:
                continue
            x = self.blockchain[idx]
            x_minus_one = self.blockchain[idx-1]
            time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
            strech_normalizer = time_passed / 60.0
            
            sum_x = 0
            for y in x["num_pow"]:
                sum_x += x["num_pow"][y]

            if sum_x == 0:
                ideal.append(0)
            else:
                if self.stretch_number_pows == False:
                    ideal.append(self.works_to_create*10*strech_normalizer)
                else:
                    ideal.append(self.works_to_create*10)

            if self.stretch_number_pows == False:
                values.append(sum_x)
            else:
                values.append(sum_x/strech_normalizer)
        x = range(self.generate_blocks)[1:]
        y = values

        #print "LEN: x",len(x),"y",len(y),"ideal",len(ideal)

        #fig = plt.figure()
        ax0 = plt.subplot(211)
        if self.stretch_number_pows:
            ax0.set_ylabel('POW rate per 60s', color='b')
        else:
            ax0.set_ylabel('POWs per Block', color='b')
        ax0.set_xlabel('Block height')
        ax0.plot(x,y,'-o',x,ideal,'r--')
        values = []
        ideal = []
        target_factors = []
        for idx in range(len(self.blockchain)):
            if idx == 0:
                continue
            x = self.blockchain[idx]
            x_minus_one = self.blockchain[idx-1]
            time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
            strech_normalizer = time_passed / 60.0
            
            sum_x = 0
            sum_x += x["num_pow"][0]

            if sum_x == 0:
                ideal.append(0)
            else:
                if self.stretch_number_pows == False:
                    ideal.append(10*strech_normalizer)
                else:
                    ideal.append(10)

            #print "sumx",sum_x
            if self.stretch_number_pows == False:
                values.append(sum_x)
            else:
                values.append(sum_x/strech_normalizer)
        x = range(self.generate_blocks)[1:]
        y = values
        plt.title('All Works: Total POWs')
        #print "LEN: x",len(x),"y",len(y),"ideal",len(ideal)

        ax1 = plt.subplot(212)
        ax1.plot(x,y,'-o',x,ideal,'r--')
        ax1.set_xlabel('Block Height')
        # Make the y-axis label and tick labels match the line color.
        if self.stretch_number_pows:
            ax1.set_ylabel('POW rate per 60s', color='b')
        else:
            ax1.set_ylabel('POWs per Block', color='b')

        for tl in ax1.get_yticklabels():
            tl.set_color('b')



        ax2 = ax1.twinx()
        ax2.set_ylim(0.4, 1.6)
        ax2.bar(x,[x["first_work_factor"] for x in self.blockchain][1:],0.45,color='#deb0b0', alpha=0.2)
        ax2.set_ylabel('Retargeting Factor', color='r')
        for tl in ax2.get_yticklabels():
            tl.set_color('r')
        plt.title('First Work: POWs + Retargeting Factor')

        plt.savefig('render-' + str(run) + '.png')
        plt.close()

[HunterMinerCrafter]

Note: If anyone of you disagrees with the testing method, please ask before the contest ends ;-) We can improve the tests of course. But that has to be done before the seeding hash is known!

Here is my first entry, in pseudocode:

Code:

alwas set all targets to constant value 0xFF;

This has a perfect 0.0 error rate in your test harness, so it can't be beaten with any better score.  Both ideal and simulated work counts come out to 0 per block, every block, every time, regardless of randomizer seed.

I WIN!(?!?!)

 

[Evil-Knievel]

Note: If anyone of you disagrees with the testing method, please ask before the contest ends ;-) We can improve the tests of course. But that has to be done before the seeding hash is known!

It would probably be ideal to be able to test more behaviors.  As it is, it seems like an algorithm that wins the contest easily could significantly under-perform in less uniform churn behavior scenarios.

Open to any suggestions ;-)
In the current test setup I tried to account for:

- In the beginning, nobody does anything
- At some early block, a large (or not so large) amount of miners enter the game
- At fixed intervals, new miners join the network
- Mining power is not uniform but jittered, also with a random intensity
- During some interval in the second half of the test run, all miners leave and rejoin later (tried to simulate some multipool behaviour)
- The block time itself is jittered as well, to simulate the variations in the actual block generation time

[Evil-Knievel]

I'll fix the test setup to estimate the "desired POW rate" more correctly  

EDIT:

Like this maybe:

Code:

def currently_active_miners(self,current_height):
        if current_height<self.miners_kick_in_at_block:
            return 0

        if current_height>=self.miners_drop_at and current_height<=self.miners_drop_at+self.miners_drop_for:
            return 0
        # get the current active number of miners in relation of blockchain height,
        # but the number of miners increases by 1 every 10 blocks
        increases = int(current_height/self.new_miner_every_xth_second) * self.how_many_miners_come_or_go
        return self.initial_miners+increases

def get_total_error(self):
        values = []
        ideal = []
        for idx in range(len(self.blockchain)):
            if idx == 0:
                continue
            x = self.blockchain[idx]
            x_minus_one = self.blockchain[idx-1]
            time_passed = (x["time_stamp"] - x_minus_one["time_stamp"]).seconds
            strech_normalizer = time_passed / 60.0
           
            sum_x = 0
            for y in x["num_pow"]:
                sum_x += x["num_pow"][y]

            if self.currently_active_miners(idx) == 0:
                ideal.append(0)
            else:
                if self.stretch_number_pows == False:
                    ideal.append(self.works_to_create*10*strech_normalizer)
                else:
                    ideal.append(self.works_to_create*10)


            if self.stretch_number_pows == False:
                values.append(sum_x)
            else:
                values.append(sum_x/strech_normalizer)
        #print values
        #print ideal
        total_error = 0
        for x in range(len(values)):
            soll = ideal[x]
            ist = values[x]
            total_error += abs(soll-ist)
        return total_error/len(values)