7

I have a scheme right now where individuals are committing to a contract a solution to a problem similar to Bitcoin's proof-of-work protocol. Here's the basic flow...the contract calculates a seed hash and individuals are trying to hash it (off-chain just using their own equipment) while incrementing a nonce until they find a solution within a certain subset of the 256 bit range (0 to 2^256 - 1). I am trying to figure out (1) what difficulty there should be if I want someone with a hash power of 1 MH/s to have a 95% chance of solving within a week and (2) the proper way to check if the submitted solution satisfies the requirement of being within the pre-specified range.

For (1) here is how I am calculating the difficulty D:

1 - ((D - 1) / D) ^ H = 0.95

So D can be thought of as representing the number of sides on a dice. The first "1" represents 100% of the possibilities, the "((D - 1) / D)" represents the subset of outcomes which are incorrect, and H represents the number of times the dice is rolled. So for example if I want to calculate the odds that I will roll a 1 within 4 rolls I have 6/6 - (5/6)^4 = 671/1296 = ~51.7%.

I'm trying to extrapolate this to hashing. In that case D represents how many pieces of pie the 2^256 range is sliced into and H represents the number of hashes performed. 1 week @ 1MH/s = 604.8 gigahashes. Solving for D gets me ~201,887,199,781 pieces of pie. My first question is do these calculations make sense? Will it take someone with 1 MH/s about a week to find a solution within one slice of pie?

For (2) I am writing an ETH contract which needs to calculate whether a submitted solution falls within the specified range given that difficulty. Here is how I am calculating that:

if (uint(sha3(finalSeed, _nonce)) <  2 ** 256 / difficulty )

So I am taking the entire 2^256 range and dividing it by the number of pie slices to arrive at how many numbers fit inside a single slice. The range the solution has to be in then is zero to the size of a slice of pie minus 1. Does this make sense? Is it necessary to convert to uint to perform this? Am I wasting a ton of resources with the "2 ** 256 / difficulty" calculation? Is there an easier way to accomplish all of this?

Any help would be greatly appreciated.

  • 1
    Instead of trying to compute a fixed value, consider using an adaptive system, where you measure the time taken to actually find a solution, and adjust the difficulty accordingly. You may find it easier to reason about maxvalue, the largest valid hash value, than difficulty, too. – Nick Johnson May 11 '16 at 16:53
2

Your calculation are correct.

Let says X=1 the event a hash is "valid", and X=0 if is not valid (X is called "Bernoulli random variable" Bernoulli Distribution). Now we have P(X=1) = D/2^256 where D is the number of valid solutions (and P(X=0) = 1 - D/2^256).

Let says you can make H hashes per week. Then we have X_1, X_2,... X_H that says if the k-ism hash was valid or not. If we say Y = X_1 + X_2 + ..+ X_H. You want to estimate D such that P(Y>=1) >= 0.95.

Here we can use the trick that P(Y>=1) = 1 - P(Y=0). To have at least one valid hash is the opposite of have no valid hashes. Now since the validity of each hash is independent of the others P(Y=0) = P(X_1=0)...P(X_H=0) = (1 - D/2^256)^H.

Putting all these together we have that P(Y>=1) = 1 - P(Y=0) = 1 - (1 - D/2^256)^H >= 0.95.

Then we have 0.05 >= (1 - D/2^256)^H ==> (0.05)^(1/H) >= 1-D/2^256 ==> D/2^256 = 1 - (0.05)^(1/H). Solving for H = 604800000000 I got D>=573548326756918809146437109998407756092224692540954418775767121920. Now your difficulty will be 2^256 / D <= 201,887,240,944.5476 which is pretty close to your calculations.

Thanks for your question! It was a really nice practice for my Probality Theory exams.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.