![]() ![]() The first Proof Of Work algorithms such as Bitcoin’s SHA256 hash function was “compute-bound”, so mining dialogue focussed on the clock speed. It’s important to note that hash rate is not equal to your computer’s processor speed. Basically, how many times your computer can calculate the output of a hash function. Hash rate is measured in hashes per second. To help put the numbers in perspective, I’ve included a few real-world probabilities scraped from the web, like the odds of winning the lottery.What are the calculated units of measure for hash rates? If you know the number of hash values, simply find the nearest matching row. That’s why the most interesting probabilities are the small ones.Īssuming your hash values are 32-bit, 64-bit or 160-bit, the following table contains a range of small probabilities. In certain applications - such as when using hash values as IDs - it can be very important to avoid collisions. So the absolute simplest approximation is just: Small Collision Probabilities Floating point numbers are not very good at representing values extremely close to 1.įurthermore, if you’re talking about more than a handful of \(k \), there isn’t a very big difference between \(k(k-1) \) and \(k^2 \). This is actually a handy representation, because it avoids some numerical precision problems in the original expression. So for small collision probabilities, we can use the simplified expression: In other words, the exponent makes a pretty good approximation all by itself! In fact, the smaller the \(X \), the more accurate it gets. Therefore, the probability of randomly generating two integers that are unique from each other is \(\frac \) or less: After that, there are \(N-1 \) remaining values (out of a possible \(N \)) that are unique from the first. Given a space of \(N \) possible hash values, suppose you’ve already picked a single value. It turns out it’s actually a bit simpler to start with the reverse question: What is the probability that they are all unique? Whatever the answer to the reverse question, we can just subtract it from one, and we’ll have the answer to our original question. Given \(k \) randomly generated values, where each value is a non-negative integer less than \(N \), what is the probability that at least two of them are equal? Our question, then, translates into the following: In this case, generating hash values for a collection of inputs is a lot like generating a collection of random numbers. For our purposes, let’s assume the hash function is pretty good - it distributes hash values evenly across the available range. If you’re interested in the real-world performance of a few known hash functions, Charles Bloom and offer some comparisons. Some distribute hash values evenly across the available range others don’t. Some hash functions are fast others are slow. There are many choices of hash function, and the creation of a good hash function is still an active area of research. Calculating the Probability of a Hash Collision Let’s derive the math and try to get a better feel for those probabilities. The answer is not always intuitive, so it’s difficult to guess correctly. What is the probability of a hash collision? This question is just a general form of the birthday problem from mathematics. If you feed this function the two strings “plumless” and “buckeroo”, it generates the same value. Take the well-known hash function CRC32, for example. ![]() Therefore, there’s always a chance that two different inputs will generate the same hash value. It just performs some arithmetic and/or bit-magic operations on the input item passed to it. ![]() The same input always generates the same hash value, and a good hash function tends to generate different hash values when given different inputs.Ī hash function has no awareness of “other” items in the set of inputs. The input items can be anything: strings, compiled shader programs, files, even directories. A hash function takes an item of a given type and generates an integer hash value within a given range. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |