Searching for an acceptable hash¶
5 October 2026. Michael asked whether obtaining the anticipated result needs to be difficult. For proof of work, the goal is expensive search and inexpensive verification. An acceptable result can be any digest within a target range; it need not be one exact preselected digest.
Executed hash_target_trials.py on Hello World, varying an eight-byte unsigned counter from zero. Each candidate is original message byte length encoded as u64 big-endian, followed by message bytes, followed by the counter as u64 big-endian. All candidate bits receive the proposed zero-bit interleaving. The existing SHAKE256 reference prefix and eight-byte output are retained. This changes the hashed input from the earlier bare-message example. The length and counter are inputs; there is no external recovery manifest. The counter is a public nonce, not a random salt.
Required leading zero bits |
Ideal expected attempts |
Actual first successful attempt |
Digest |
|---|---|---|---|
8 |
256 |
528 |
|
12 |
4096 |
6345 |
|
16 |
65536 |
68448 |
|
The successful nonce for the 16-bit target was 68447. Verification recomputed the hash from the complete serialized candidate and checked the target. All three verifications passed. A single shared ascending search determined the first success for each target; these are not three independent random trials. Complete results are in hash-target-results.json.
Under an ideal uniform independent-output approximation for distinct candidate inputs, each trial passes a k-leading-zero-bit target with probability 2^-k and the expected search takes 2^k attempts. Actual counts vary. This run demonstrates the interface and search, not the independence assumption or cryptographic security. Repeating the same deterministic search will return the same first successful nonce.
The experiment uses established SHAKE mixing, not a custom RedTail primitive or a physical random source. Every extra required zero bit doubles the ideal expected work. A fixed 64-bit output still has only about 32 bits of generic collision strength; target search, exact-digest preimage search, and finding any colliding pair are different tasks. The next custom-formula question is whether an attacker can solve for qualifying inputs substantially faster than the expected search.