Calculating difficulty and verifying a hash as a solution

Question

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.

Answer 1

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.