Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 30, 2016, 07:51:39 PM Last edit: December 05, 2016, 10:14:14 AM by Evil-Knievel |
|
I am looking for the best and smoothest retargeting algorithmCode was just updated (09:24:20 PM forum time)!Terms:I will give 2 BTC form my personal savings to the best submission within the next 5 days from now! By best submission, I refer to the least cumulative error compared to the ideal outcome. You will understand that soon ;-) Your algorithm will be tested in 9 different settings. The highest cumulative error of all settings counts. More, below! If we have some obvious bug in our code or in this description, one that would make everything that we find out here useless, you agree that we can fix this bug even before the end of this contest. A bug is also if we meant something differently that we wrote it down! It's fine to submit possible solutions as soon as possible to discuss them openly. If multiple solutions are equally good (like its the case for copy cats), the first submission will win. Obvious copy cats will be disqualified at pure will. Copy cats from other coins with liberal open source licenses is very welcome ... as long as it works! Ah, and I can also make submissions! Short background information of the theoretical scenario (sounds very complicated, you can skip this if you feel lucky)- 1. We have a blockchain that grows at 1 Block per between 25 and 120 seconds. The growth speed is uniformely random
- 2. We have three tansaction types that may get included into each block, let's call them Work1, Work2 and Work3
- 3. Assume that Work1, Work2 and Work3 transactions cannot be generated arbitrarily fast.
- 4. Assume we have a base target of t=0x000000ffffffffffffffffffffffffff and the target can only lie in the interval [1, 0x000000ffffffffffffffffffffffffff]
- 5. Assume that when this target is active, we can generate 20 Work1 transactions, 60 Work2 transactions and 35 Work3 transactions per minute per user. It may happen that multiple number of users come or go, so it's not known how many users will be generating those transactions until a block is generated and we can count the actual number that was generated.
- 6. Each of the Transaction types has an own target value, which gets initially set to the base target
- 7. We can now rate limit the three transaction types by adjusting their target value.
- 8. When we multiply the target value by 0.5, we also multiply the rate at which the transactions come in by 0.5.
- 9. The desired goal is to have 10 transactions per minute per each transaction type, regardless of how fast they can be generated. So ultimately the three transaction types will end up with totally different target values
- 10. No matter how many transactions are generated, the hard limit is 20 per block per transaction type. So for 3 transaction types we can only have 60 transactions per block. Everything beyond that gets discarded.
What is this all about?The basic explanation: We have three transaction types that are generated by the users. The difficulty to generate such transaction type correlates with the target value of that transaction type. If too many users generate too much of one of the transaction types, we can throttle the generation rate by lowering the target value. What we don't know?We don't know the numbers of users that were generating these transactions. We don't know the number of transactions that will be generated in the future (when we retarget at block X, we can only use the information from blocks X-1 ... 0) Current Mechanism?Its in the retarget_retarget_work() method beginning in the python file at line 65. We basically walk back as many blocks as are needed to span a time frame of 120 seconds. Then we look at how many transactions of a specific transaction type have been found, also we count the total number of transactions (of all types altogether). Then we look at how many we have seen, and how many we should have seen. According to the different we scale the target by between -10% and +10% (2 other side cases are in the code). The scaling factor can be understood like thatValues < 1 throttle down the generation Values > 1 increase the generation speed Unprecise!!!Here, the critical parts are when a) we are at the beginning (there is no smooth start) and b) when the amount of "miners" changes. Remember, every 10 blocks one new miner kicks in in this example. This is unprecise, because this scheme tends to oscillate for some reason. Please see the following plots that on the x axis show the block height and on the y axis show the POW rate per 60s. This is a normalized value: So if a block took 2 minutes and it contains 10 transactions of Work1 type, then the POW rate / 60s would be 20. The red line depicts the ideal value. The plot contains two sub plots. Above for all transaction types altogether, and below only for the Work1 transaction type. In this case we also show the "factor" value which scales the target. Here you see the plot with our 120s window (as described above) ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2Fd8awq7b.png&t=665&c=cSKLnhhw3ByPOA) If we increase the window to 1000s, we have heavy oscillations: ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2F89J4kBx.png&t=665&c=Y9ibsy11GZ6hBw) And with only 60s, it's better but still not good. 60 seconds gets too messy when sudden changes arise in the miner's structure: ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2FfuP1ySd.png&t=665&c=PD-U7gS2eN4JiQ) You think this is smooth? Then let not only one new "miner" join every 10 blocks, but 15. Look at the distortion at the beginning ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2FUWC9yMe.png&t=665&c=ZQcsFtB7jC94bA) Another very very bad example. It just takes too long to "absorb" sudden changes!!!! ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2F9tIUj6R.png&t=665&c=kmPNJ-LkMMZ3Xw) You see, it all sucks! We want to be as close as possible to the red line! I think we need a totally different retargeting algorithm. PS: If you want to have the Y axis not normalized to 60 seconds but show the actual number of transactions per block, use stretch_number_pows = False in the python script. Then, the red ideal line will be stretched. Also, you can play with these variables 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 = 5 jitter_size = 1 To modify how many miners enter how often, and how much "noise" is in the generation (the jitter) The python scriptUse python2, and install the preliminaries: sudo apt-get install python-tk sudo pip install numpy matplotlib
And here it is: 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 = 5 jitter_size = 1 maximum_movement = 0.5 # 1=100%
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 return 1+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 - jitter_size) + random.uniform(0,2*jitter_size)) * 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 retarget_work(block, x): targetI = x["target"] pastMass = 0 account_for_block_max = 10 seconds_passed = 0 totalMass = 0 counter = 0 current_block = block current_block_timestamp = blockchain[current_block]["time_stamp"] while True: counter = counter + 1 pastMass += blockchain[current_block]["num_pow"][x["id"]] for y in blockchain[current_block]["num_pow"]: totalMass += blockchain[current_block]["num_pow"][y] seconds_passed = (current_block_timestamp - blockchain[current_block-1]["time_stamp"]).seconds current_block = current_block - 1 #print "iter",seconds_passed if current_block < 1 or seconds_passed >= 60: break
if seconds_passed < 1: seconds_passed = 1
pows_per_360_seconds = ((pastMass * 360.0) / seconds_passed) if pows_per_360_seconds>0 and pows_per_360_seconds<1: pows_per_360_seconds = 1
factor = 1 if pows_per_360_seconds > 0: factor = 10*6.0/pows_per_360_seconds if factor<1-maximum_movement: factor = 1-maximum_movement if factor>1+maximum_movement: factor=1+maximum_movement elif pows_per_360_seconds == 0 and totalMass == 0: factor = 1.05 else: factor = 1
#print "seconds",seconds_passed,"blocks",counter,"actual pows",pastMass,"per 360s:",pows_per_360_seconds,"wanted:",60,"factor",factor
targetI = targetI * factor if targetI>base_target: targetI = base_target if x["id"]==0: blockchain[block]["first_work_factor"] = factor 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(1-maximum_movement-0.05, 1+maximum_movement+0.05) 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() What will be tested?We will test your algorithm with 9 yet-to-define scenarios including different distributions of the number of miners per timestep, with different blockchain lengths, and different mining patterns. Right now all three transaction types are generated simultaneously, we can also think to test what happens if the generation only focuses on one of them and then shifts to another over time. The scenarios will be defined at some later point in time, arbitrarily, but will be same for all submissions. Testing can be carried out in an extended version of the code, one that simulates different kinds of settings. EDIT: This will be the testbed:Tester Code: tester.pyfrom retarget import RetargetTest
retarget = RetargetTest() max_error = 0 retarget.seeder("BLOCK_HASH_OF_FIRST_BLOCK_AFTER_CONTEST_GOES HERE") for i in range(9): print "Executing run",i retarget.reset_chain() retarget.randomize_params() retarget.generate_chain() err = retarget.get_total_error() retarget.plot(i) print "Run",i,"-","total error =",err if max_error<err: max_error=err print "Largest error:",max_error Here, as an example, my own retarget method embedded into the test class: retarget.pyimport 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 account_for_block_max = 10 seconds_passed = 0 totalMass = 0 counter = 0 current_block = block current_block_timestamp = self.blockchain[current_block]["time_stamp"]
massive_retarget = False deviation_too_high = False last_two_deviation = 0.0
while True: counter = counter + 1 curmass = self.blockchain[current_block]["num_pow"][x["id"]] pastMass += curmass
# if the maximum block-tx-limit of 20 was reached, do massive retargeting if counter == 1 and pastMass == 20: massive_retarget = True break
# Also if deviation of last two block was too high, do some "magic" if counter == 1 and curmass > 0: last_two_deviation = curmass / 10 if last_two_deviation > 1.25 or last_two_deviation < -0.75: #deviation of over 25% is bad print "last two deviation",last_two_deviation,"at block",block deviation_too_high = True break
for y in self.blockchain[current_block]["num_pow"]: totalMass += self.blockchain[current_block]["num_pow"][y] seconds_passed = (current_block_timestamp - self.blockchain[current_block-1]["time_stamp"]).seconds current_block = current_block - 1 if current_block < 1 or seconds_passed >= 60: # retarget every 120 seconds ~ 1 block on average break
factor = 1 if massive_retarget == True: factor = 0.4 # lower to just 40% elif deviation_too_high == True: factor = 1/last_two_deviation else: if seconds_passed < 1: seconds_passed = 1
pows_per_360_seconds = ((pastMass * 360.0) / seconds_passed) if pows_per_360_seconds>0 and pows_per_360_seconds<1: pows_per_360_seconds = 1
factor = 1 if pows_per_360_seconds > 0: factor = 10*6.0/pows_per_360_seconds if factor<0.9: factor = 0.9 if factor>1.1: factor=1.1 elif pows_per_360_seconds == 0 and totalMass == 0: factor = 1.05 else: factor = 1
#print "seconds",seconds_passed,"blocks",counter,"actual pows",pastMass,"per 360s:",pows_per_360_seconds,"wanted:",60,"factor",factor
targetI = targetI * factor if targetI>self.base_target: targetI = self.base_target if x["id"]==0: self.blockchain[block]["first_work_factor"] = factor x["target"] = targetI
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()
There will be 9 random test cases generated by a seeded random number generator, which will be seeded with the first block hash after the contest is over. The average error per block is returned after each test run, the highest error counts. The algorithm with the least error wins.
|
|
|
|
nelson4lov
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 30, 2016, 08:09:34 PM |
|
Coders only?
|
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 30, 2016, 08:49:28 PM |
|
Like 2 or 3 serious ideas I surely can implement and test. But i think it will become too much when I have to implement 10 or more submissions.
So coding is preferred, pseudo code is accepted if "i'm in the mood" ;-)
|
|
|
|
nelson4lov
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 30, 2016, 08:54:41 PM |
|
Like 2 or 3 serious ideas I surely can implement and test. But i think it will become too much when I have to implement 10 or more submissions.
So coding is preferred, pseudo code is accepted if "i'm in the mood" ;-)
Sadly, I only know a bit of code but I can help somehow with pseudo code
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 30, 2016, 09:15:35 PM |
|
Important note: copy cat from other coins is very welcome ... as long as it works!
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 30, 2016, 09:42:23 PM |
|
Updated initial posting!
|
|
|
|
Selsonblue
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 03:43:51 AM |
|
Working my way through the code. I dont see myself submitting any solutions but I know some people that like bitcoin.
|
|
|
|
szafa
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 06:51:30 AM |
|
What crypto will be used this algorytm?
|
|
|
|
klintay
Legendary
Offline
Activity: 1775
Merit: 1032
Value will be measured in sats
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 07:19:08 AM Last edit: December 01, 2016, 07:29:50 AM by klintay |
|
What crypto will be used this algorytm?
Elastic Coin! Solution 1: Kimoto Gravity Well (from bitcoin)KGW = 1 + (0.7084 * pow((double(PastBlocksMass)/double(144)), -1.228)); Kimoto Gravity Well (KGW) retargets after every block and adjusts very quickly, e.g. when multipools add and retract mining power to a smaller coin's network. http://bitcoin.stackexchange.com/questions/21730/how-does-the-kimoto-gravity-well-regulate-difficultyCan we use a variant of this algorithm? Solution 2: DigiShield Retargetting (from digicoin) // * If we are creating a transaction we allow transactions up to 1,000 bytes // to be considered safe and assume they can likely make it into this section. if (nBytes < (mode == GMF_SEND ? 1000 : (DEFAULT_BLOCK_PRIORITY_SIZE - 1000))) nMinFee = 0; } // This code can be removed after enough miners have upgraded to version 0.9. // Until then, be safe when sending and require a fee if any output // is less than CENT: if (nMinFee < nBaseFee && mode == GMF_SEND) { BOOST_FOREACH(const CTxOut& txout, tx.vout) if (txout.nValue < CENT) nMinFee = nBaseFee; } if (!MoneyRange(nMinFee)) nMinFee = MAX_MONEY; return nMinFee; } bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransaction &tx, bool fLimitFree, bool* pfMissingInputs, bool fRejectInsaneFee) { AssertLockHeld(cs_main); if (pfMissingInputs) *pfMissingInputs = false; if (!CheckTransaction(tx, state)) return error("AcceptToMemoryPool: : CheckTransaction failed"); // Coinbase is only valid in a block, not as a loose transaction if (tx.IsCoinBase()) return state.DoS(100, error("AcceptToMemoryPool: : coinbase as individual tx"), REJECT_INVALID, "coinbase"); // Rather not work on nonstandard transactions (unless -testnet/-regtest) string reason; if (Params().NetworkID() == CChainParams::MAIN && !IsStandardTx(tx, reason)) return state.DoS(0, error("AcceptToMemoryPool : nonstandard transaction: %s", reason), REJECT_NONSTANDARD, reason); // is it already in the memory pool? uint256 hash = tx.GetHash(); if (pool.exists(hash)) return false; // Check for conflicts with in-memory transactions { LOCK(pool.cs); // protect pool.mapNextTx for (unsigned int i = 0; i < tx.vin.size(); i++) { COutPoint outpoint = tx.vin .prevout; if (pool.mapNextTx.count(outpoint)) { // Disable replacement feature for now return false; } } }
{ CCoinsView dummy; CCoinsViewCache view(dummy);
{ LOCK(pool.cs); CCoinsViewMemPool viewMemPool(*pcoinsTip, pool); view.SetBackend(viewMemPool);
// do we already have it? if (view.HaveCoins(hash)) return false;
// do all inputs exist? // Note that this does not check for the presence of actual outputs (see the next check for that), // only helps filling in pfMissingInputs (to determine missing vs spent). BOOST_FOREACH(const CTxIn txin, tx.vin) { if (!view.HaveCoins(txin.prevout.hash)) { if (pfMissingInputs) *pfMissingInputs = true; return false; } }
// are the actual inputs available? if (!view.HaveInputs(tx)) return state.Invalid(error("AcceptToMemoryPool : inputs already spent"),REJECT_DUPLICATE, "bad-txns-inputs-spent");
// Bring the best block into scope view.GetBestBlock();
// we have all inputs cached now, so switch back to dummy, so we don't need to keep lock on mempool view.SetBackend(dummy); }
// Check for non-standard pay-to-script-hash in inputs if (Params().NetworkID() == CChainParams::MAIN && !AreInputsStandard(tx, view)) return error("AcceptToMemoryPool: : nonstandard transaction input");
// Note: if you modify this code to accept non-standard transactions, then // you should add code here to check that the transaction does a // reasonable number of ECDSA signature verifications.
int64_t nValueIn = view.GetValueIn(tx); int64_t nValueOut = tx.GetValueOut(); int64_t nFees = nValueIn-nValueOut; double dPriority = view.GetPriority(tx, chainActive.Height());
CTxMemPoolEntry entry(tx, nFees, GetTime(), dPriority, chainActive.Height()); unsigned int nSize = entry.GetTxSize();
// Don't accept it if it can't get into a block int64_t txMinFee = GetMinFee(tx, nSize, true, GMF_RELAY); if (fLimitFree && nFees < txMinFee) return state.DoS(0, error("AcceptToMemoryPool : not enough fees %s, %d < %d", hash.ToString(), nFees, txMinFee), REJECT_INSUFFICIENTFEE, "insufficient fee");
// Continuously rate-limit free transactions // This mitigates 'penny-flooding' -- sending thousands of free transactions just to // be annoying or make others' transactions take longer to confirm. if (fLimitFree && nFees < CTransaction::nMinRelayTxFee) { static CCriticalSection csFreeLimiter; static double dFreeCount; static int64_t nLastTime; int64_t nNow = GetTime();
LOCK(csFreeLimiter);
// Use an exponentially decaying ~10-minute window: dFreeCount *= pow(1.0 - 1.0/600.0, (double)(nNow - nLastTime)); nLastTime = nNow; // -limitfreerelay unit is thousand-bytes-per-minute // At default rate it would take over a month to fill 1GB if (dFreeCount >= GetArg("-limitfreerelay", 15)*10*1000) return state.DoS(0, error("AcceptToMemoryPool : free transaction rejected by rate limiter"), REJECT_INSUFFICIENTFEE, "insufficient priority"); LogPrint("mempool", "Rate limit dFreeCount: %g => %g\n", dFreeCount, dFreeCount+nSize); dFreeCount += nSize; }
if (fRejectInsaneFee && nFees > CTransaction::nMinRelayTxFee * 10000) return error("AcceptToMemoryPool: : insane fees %s, %d > %d", hash.ToString(), nFees, CTransaction::nMinRelayTxFee * 10000);
// Check against previous transactions // This is done last to help prevent CPU exhaustion denial-of-service attacks. if (!CheckInputs(tx, state, view, true, SCRIPT_VERIFY_P2SH | SCRIPT_VERIFY_STRICTENC)) { return error("AcceptToMemoryPool: : ConnectInputs failed %s", hash.ToString()); } // Store transaction in memory pool.addUnchecked(hash, entry); }
g_signals.SyncTransaction(hash, tx, NULL);
return true; }
int CMerkleTx::GetDepthInMainChainINTERNAL(CBlockIndex* &pindexRet) const { if (hashBlock == 0 || nIndex == -1) return 0; AssertLockHeld(cs_main);
// Find the block it claims to be in map<uint256, CBlockIndex*>::iterator mi = mapBlockIndex.find(hashBlock); if (mi == mapBlockIndex.end()) return 0; CBlockIndex* pindex = (*mi).second; if (!pindex || !chainActive.Contains(pindex)) return 0;
// Make sure the merkle branch connects to this block
https://github.com/digibyte/digibyte/blob/master/src/main.cpp https://www.reddit.com/r/Digibyte/comments/213t7b/what_is_digishield_how_it_works_to_retarget/
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 08:03:30 AM |
|
I will implement klintay's suggestions now and test! But I see that it takes way too much time, so I will not accept any more "non-proof-of-concept-code" submissions without plots. ![Wink](https://bitcointalk.org/Smileys/default/wink.gif)
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 09:07:19 AM |
|
@klintay: Both methods are not suitable.Digishield just rate limits with an upper bound! It does not "converge" to a desired unbounded value. We rate limit at 20 per 60seconds but want to converge to 10 per 60seconds. Doesn't work with the approach. Also, my KGW seems to not work at all. At least my coding! I had to edit it a bit (bug are possible) bit in KGW it is not possible to have a pastBlockMass of zero, because every block is at lest one block. In our scheme, there may be blocks with ZERO transactions. If I coded the KGW wrong, feel free to correct and submit a working proof-of-concept along with plots. 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 = 5
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 return 1+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 account_for_block_max = 10 seconds_passed = 0 totalMass = 0 counter = 0 current_block = block adjustmentRatio=0 current_block_timestamp = blockchain[current_block]["time_stamp"] while True: counter = counter + 1 pastMass += blockchain[current_block]["num_pow"][x["id"]] for y in blockchain[current_block]["num_pow"]: totalMass += blockchain[current_block]["num_pow"][y] seconds_passed = (current_block_timestamp - blockchain[current_block-1]["time_stamp"]).seconds current_block = current_block - 1 #print "iter",seconds_passed rateActualSeconds = seconds_passed*1.0/pastMass rateTargetSeconds = 6 # ten per minute, 6 seconds per pow
print "time passed",seconds_passed,"seen pows",pastMass,"actual seconds per pow",rateActualSeconds,"wanted seconds",rateTargetSeconds adjustmentRatio = 1 if rateActualSeconds <0: rateActualSeconds = 0 if rateActualSeconds!=0 and rateTargetSeconds != 0: adjustmentRatio = rateTargetSeconds / rateActualSeconds if pastMass>0: horizonDeviation = kimoto(pastMass*1.0) horizonDeviationSlow = 1/kimoto(pastMass*1.0) else: horizonDeviation = 1 horizonDeviationSlow = 1
if pastMass >= 50: if adjustmentRatio<=horizonDeviationSlow or adjustmentRatio>=horizonDeviation: break
if current_block < 1 or counter == account_for_block_max: break
if seconds_passed < 1: seconds_passed = 1
factor = adjustmentRatio
#print "seconds",seconds_passed,"blocks",counter,"actual pows",pastMass,"per 360s:",pows_per_360_seconds,"wanted:",60,"factor",factor
targetI = targetI * factor if targetI>base_target: targetI = base_target if x["id"]==0: blockchain[block]["first_work_factor"] = factor 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.85, 1.15) 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()
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 09:42:18 AM |
|
An own submission of myself:
Added two special cases. When the limit of 20 is reached, then a "massive retarget" takes place, also in the last block encountered a "too high" deviation to the desired value, we do a different retarget. BEFORE AND AFTER: Peeks are now eliminated in at most 2 blocks. Its better but still sucks when randomizing the block length (here, we use fixed 0 seconds) Before: ![](https://ip.bitcointalk.org/?u=http%3A%2F%2Fi.imgur.com%2F9tIUj6R.png&t=665&c=AQZnmPO5ep2hoA) After: ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2F9vMbTxf.png&t=665&c=EnvJG5NlJkEYWA) Also, when we start with MANY miners upfront, the retarget is too slow in the beginning: ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2FwQgwP42.png&t=665&c=aw1FyCq2-j9qLw) 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 = 7
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 return 1+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 retarget_work(block, x): targetI = x["target"] pastMass = 0 account_for_block_max = 10 seconds_passed = 0 totalMass = 0 counter = 0 current_block = block current_block_timestamp = blockchain[current_block]["time_stamp"]
massive_retarget = False deviation_too_high = False last_two_deviation = 0.0
while True: counter = counter + 1 curmass = blockchain[current_block]["num_pow"][x["id"]] pastMass += curmass
# if the maximum block-tx-limit of 20 was reached, do massive retargeting if counter == 1 and pastMass == 20: massive_retarget = True break
# Also if deviation of last two block was too high, do some "magic" if counter == 1 and curmass > 0: last_two_deviation = curmass / 10 if last_two_deviation > 1.25 or last_two_deviation < -0.75: #deviation of over 25% is bad print "last two deviation",last_two_deviation,"at block",block deviation_too_high = True break
for y in blockchain[current_block]["num_pow"]: totalMass += blockchain[current_block]["num_pow"][y] seconds_passed = (current_block_timestamp - blockchain[current_block-1]["time_stamp"]).seconds current_block = current_block - 1 if current_block < 1 or seconds_passed >= 60: # retarget every 120 seconds ~ 1 block on average break
factor = 1 if massive_retarget == True: factor = 0.4 # lower to just 40% elif deviation_too_high == True: factor = 1/last_two_deviation else: if seconds_passed < 1: seconds_passed = 1
pows_per_360_seconds = ((pastMass * 360.0) / seconds_passed) if pows_per_360_seconds>0 and pows_per_360_seconds<1: pows_per_360_seconds = 1
factor = 1 if pows_per_360_seconds > 0: factor = 10*6.0/pows_per_360_seconds if factor<0.9: factor = 0.9 if factor>1.1: factor=1.1 elif pows_per_360_seconds == 0 and totalMass == 0: factor = 1.05 else: factor = 1
#print "seconds",seconds_passed,"blocks",counter,"actual pows",pastMass,"per 360s:",pows_per_360_seconds,"wanted:",60,"factor",factor
targetI = targetI * factor if targetI>base_target: targetI = base_target if x["id"]==0: blockchain[block]["first_work_factor"] = factor 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
Newbie
Offline
Activity: 34
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 11:14:00 AM |
|
The kimoto function was designed to take into account the few last blocks if the hashrate is changing too much in a short amount of time. The block mass needs to be quite high for kimoto to start having reasonable values (kimoto(144) = 1.7084), so a lot of blocks will be taken into account, even if you have a big change in mining power, which will slow down the adjustment. So, I think you should increase the blockMass argument, few tests lead me to think that blockMass * 30 is a good choice, with this parameter, the amount of block to be taken into account (Assuming 10 transactions per block) will quickly decrease as the blockMass increases, and works OK in your case where there is a lot of sudden changes in the number of transaction per seconds, which I don't think would happen that much in production, well I don't really know because I haven't quite understood what you are trying to do. Also, because we are limited to 20 trs/minwe don't know if the actual rate is 21 or 300, so in case of big spike, it will take time to readjust the difficulty. Finally, do you want to adjust the difficulty at each blocks ? https://i.imgur.com/8kzKv0N.pngdef retarget_work_2(block, x): targetI = x["target"] pastMass = 0 counter = 0 current_block = block current_block_timestamp = blockchain[current_block]["time_stamp"] adjustment = 0 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): print("kim : " + str(kim) + " 1/kim : " + str(1.0/kim) + " adj : " + str(adjustment)) break if current_block < 1: break targetI = targetI * adjustment if targetI>base_target: targetI = base_target if x["id"] == 0: blockchain[block]["first_work_factor"] = adjustment x["target"] = targetI
|
|
|
|
loracle
Newbie
Offline
Activity: 34
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 11:21:35 AM Last edit: December 01, 2016, 12:13:47 PM by loracle |
|
Results when we randomize the block time: https://i.imgur.com/BdLPEFp.png
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 12:45:19 PM |
|
...
Thanks, but in the example below this approach underperforms in relation to the solution in the submission just above you. Yours: ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2FnWZ1nGX.png&t=665&c=PvXQlwXd7bywkw) Other Submission: ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.imgur.com%2FwQgwP42.png&t=665&c=aw1FyCq2-j9qLw) Code (Your code modified) 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 = 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 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): print("kim : " + str(kim) + " 1/kim : " + str(1.0/kim) + " adj : " + str(adjustment)) break if current_block < 1: break 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() Ill test in other settings soon ;-)
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 01:02:08 PM |
|
loracle, correction: yours works better for randomized block times. So I guess it's a valid submission for now! ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) But I think it will happen that people will in the next days try to level out the "slow initialization phase" at the beginning. Maybe it's worth taking a look at this!
|
|
|
|
hendryrodriguez1990
Newbie
Offline
Activity: 3
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 01:22:31 PM |
|
A better choose than kimoto function is the implementation of DigiShield , In summary DigiShield is a balanced asymmetrical approach to difficulty re-targeting. You don't want to let the difficulty go to high to fast, but you need to give it enough room to catch up quickly. The same thing goes with down swings, since it takes longer to discover new blocks you need to give it more room to go down, but not enough to send it to the floor. The DigiShield code can be found here between lines 833 & 1007: https://github.com/digibyte/DigiByteProject/blob/master/src/main.cppTake a look at the Dogecoin difficulty chart: http://www.coinwarz.com/difficulty-charts/dogecoin-difficulty-chart. You can see how multi-pools have really been mining most of the coins and leaving the dedicated Doge miners to pick up the slack and get the short end of the stick when it comes to new coins. You can also see when DigiShield took effect and that no longer occurs.
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 01:28:48 PM |
|
hendryrodriguez1990, thanks for the suggestion. If you want to take the run for the 2BTC you need to make a short proof-of-concept. ![Wink](https://bitcointalk.org/Smileys/default/wink.gif)
|
|
|
|
hendryrodriguez1990
Newbie
Offline
Activity: 3
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 01, 2016, 01:30:50 PM |
|
* 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.
|
|
|
|
|