Comparing Prefix Search with Random and Sequential Methods (Solved)

I wrote this script to compare two different methods for locating a single element identified by its RIPEMD-160 hash in a list of numbers. The goal is to determine which of these two approaches is faster and more effective at finding that specific element. To keep things equal, I run several simulations under the same conditions: - The list is broken down into "blocks". - These blocks are examined in a random sequence. - I randomly choose the number we’re trying to find from that list. - The whole thing is repeated multiple times to collect data: we track how many checks each method performs and how often each method "wins" by finding the target with fewer checks. Two approaches: 1. Sequential Search: This one is pretty straightforward. It simply checks each block from start to finish, one at a time, to see if the hash matches the target. It’s like flipping through every page of a book without skipping. While it’s simple and serves as a good baseline, if the element is at the end of the list, this method will end up making a ton of checks. 2. Prefix-Based Search: This method is a bit smarter. While it also goes through the blocks in a random order, before checking the entire block, it first looks to see if any element's hash starts with the same first three characters as the hash we’re searching for. In hexadecimal terms, each character has 16 possibilities, which means three characters give us 16³, or 4,096 combinations. If a block contains 4,096 elements, you’d expect each combination to show up about once on average. So, if it finds an element that matches that prefix, it greatly reduces the number of checks needed.

Yeah, finally I see something interesting here instead of endless blah-blah from people who think that they know everything, have >100 years of expertise etc. To scan entire range (to get 100% probability of success), your method requires same number of ops as bruteforce (so it does not break any math laws), but it has better changes to find the key faster than bruteforce because it has non-linear probability of success (higher at the beginning and lower at the end comparing to bruteforce). Nice! I think results can be improved a bit by using more complex logic, but your script demonstrates the main idea very well. Thanks for the fun! I donated some btc to your address.

Thank you, Rc, it is a very noble gesture on your part, especially during this time in my life. I truly appreciate it infinitely.

So if I have N different colored balls in an urn, and it takes a hash(ball color) op to label every ball after every extraction, in order to compare the label with the target (or even to check the prefix), you are saying that the prefix method will extract the winning ball sooner, because you're stashing separately groups of balls. If the prefix check would be a free or cheap operation, I would agree. However, the balls have no markings or clues on them in regard to their eventual label, and the average costs of both methods are the same, so the fact that the prefix method loses more badly (more operations) in the cases when sequential wins, is not accounted at all. Otherwise, the averages would not be identical. There's also no "loser" here since both methods account for the actual total number of ops to solve each hidden value. For each his own though.

Hey, don't spoil magic with your balls! I adore sources that demonstrate something incredible, like fighting with bruteforce, it brings so much fun, I'm going to support it! Because reality is so boring...

Thank you for starting a new thread for this, and providing a full write-up of the method, etc 👍

great! imo, in the context of prefix filtering for Bitcoin private key recovery, Hamming distance tolerance can be used to widen the match range without heavily sacrificing efficiency. Maybe combining not only prefix address or hash160, but both.

While I see a few things about this technique that are ignored and not included in the "findings", and I believe significantly better search algorithms already exist, I'm most curious why you chose THREE, specifically, as the number of "characters" to check?  Is there something about THREE that makes it better than TWO or FOUR (or any other number)?  Have you tried your simulations with other prefix sizes to find the optimal prefix size? Also, it seems very inefficient to take a hash (which is a large binary number), and first convert it to a string representation of its value as represented in hexadecimal, and then use string manipulation to compare "characters"?  Wouldn't it be much faster and simpler to perform a bitwise XOR between some predetermined prefix of bits of the hash computed from the list element and the same prefix of bits on the target hash. And, if you ARE going to use XOR, is there a benefit to taking the extra steps to generate a bitwise prefix since XOR is so incredibly fast as a comparison method? In the time you spend separating the prefix from the initial hash, the XOR between the full hash values would likely already have completed, wouldn't it?

The probabilistic formula for the distribution of prefixes states that a prefix of length N has a probability of 1/16**N. Therefore, if you divide the range to be explored into blocks of size 16**N (or close), once you find a prefix, the probability of finding another within the same block will be very low/rare. Consequently, you can stop scanning and save the remaining range. (If you use it for puzzle searches, you can explore it in a second pass if necessary). Example: If you use a prefix "aabbccde" you should use blocks close to 16**8 or 4,294,967,296. If you find the prefix at 2,000,000,000, it is very unlikely (though not impossible) to find another in the rest of the block. Statistically, leaving that segment for a second pass if necessary, is the most convenient approach, saving computational power that would be used for searching the remaining block, where it would be very rare to find the prefix again. Yes, but since my intention was to compare both methods, the important thing is that the conditions remain the same. However, it is good to take your advice if one intends to implement it in a real scenario. Out of curiosity, which algorithms are you referring to?

I'm from my phone now, I'm not able to scroll the code but as far I understood you are scanning for "aabbcc" in a block, once found you move to next one. Right? If yes, it's like the "?" checksum in minikey, basically you get one valid ripemd starting with "00" once every 256~ hashes. And it's interesting. it's like kangaroo 🦘 for hashes if I got it right.

Kangaroos work completely differently from what is explained there. There is a dedicated thread from RetiredCoder with details about the method.

We sought to reach the truth, and we did. If you have a better variation, publish it. The donation has done its part, thanks to RC, I now have half the components for my new desktop.