# Calculating difficulty and verifying a hash as a solution

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.

• 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. May 11, 2016 at 16:53

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.