"we ?ust nee? to sim?ly c?eck if the ?rivate ke? is o?d or eve?, the? re?uce the ran?e to ? ?its"
Of course. Anyone can do that, on any public key.
Q=02145D2611C823A396EF6712CE0F712F09B9B4F3135E3E0AA3230FB9B6D08D1E16 (135-bit key)
rangeStart=0x4000000000000000000000000000000000
rangeStop =0x7fffffffffffffffffffffffffffffffff
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
n-1=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140
n/2=0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1
Q/2=026740DAF760406CEAE6D79B0AC803B8D2A7DF71DDC4DB08264325A10BCC3DD66A
(Q-1)/2=02163134C25215569344912A14EA07CCD8ADA8573458A1672BBF845D0D83F9F6EB
And then, if that key really has only 135 bits (it lacks DLEQ proofs, so we can assume it is the case, but we cannot be 100% sure), then 026740DAF760406CEAE6D79B0AC803B8D2A7DF71DDC4DB08264325A10BCC3DD66A or 02163134C25215569344912A14EA07CCD8ADA8573458A1672BBF845D0D83F9F6EB has 134 bits. And so on, and so forth: the range can be always reduced. It is possible to generate 32 public keys, where one of them will have 130 bits. But: nobody will know, which one, and it won't make the challenge any easier.
"do?s a??one kn?w if prefi?es are use?ul? we ?an ski? 9?% of ran?e pat?erns"
Well, there are some known weaknesses in hash functions. And by observing some patterns, it is possible to skip some keys. However, newbies from this topic know nothing about internal connections of temporary values inside SHA-256 or RIPEMD-160, to use it properly, and really skip some keys. Which means, that prefixes are useless, because by observing the first N bits of RIPEMD-160, you observe random different internal bit positions inside RIPEMD-160. Because the first bit of RIPEMD-160 does not depend on just the first bit of the hashed message. These dependencies are much, much more complex than just that. A single bit of the final hash depends on hundreds, sometimes thousands of bits of the hashed message, and avalanche effect turns all of that into a complete mess.
However, someone, who has some crypto skills, can make some useful optimizations. Because it is not needed to compute every hash function till the end. Here is some SHA-256 example, why it is the case, and how to use it properly. Let's say that we have the hash of the Genesis Block:
+-------------------------------------------------------------------------+----------------+
| 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19 | initial hash |
+-------------------------------------------------------------------------+----------------+
| 01000000 00000000 00000000 00000000 | first message |
| 00000000 00000000 00000000 00000000 | |
| 00000000 3ba3edfd 7a7b12b2 7ac72c3e | |
| 67768f61 7fc81bc3 888a5132 3a9fb8aa | |
+-------------------------------------------------------------------------+----------------+
| bc909a33 6358bff0 90ccac7d 1e59caa8 c3c8d8e9 4f0103c8 96b18736 4719f91b | exit hash |
+-------------------------------------------------------------------------+----------------+
| 4b1e5e4a 29ab5f49 ffff001d 1dac2b7c | second message |
| 80000000 00000000 00000000 00000000 | |
| 00000000 00000000 00000000 00000000 | |
| 00000000 00000000 00000000 00000280 | |
+-------------------------------------------------------------------------+----------------+
| af42031e 805ff493 a07341e2 f74ff581 49d22ab9 ba19f613 43e2c86c 71c5d66d | final hash |
+-------------------------------------------------------------------------+----------------+
+-------------------------------------------------------------------------+----------------+
| 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19 | initial hash |
+-------------------------------------------------------------------------+----------------+
| af42031e 805ff493 a07341e2 f74ff581 | third message |
| 49d22ab9 ba19f613 43e2c86c 71c5d66d | |
| 80000000 00000000 00000000 00000000 | |
| 00000000 00000000 00000000 00000100 | |
+-------------------------------------------------------------------------+----------------+
| 6fe28c0a b6f1b372 c1a6a246 ae63f74f 931e8365 e15a089c 68d61900 00000000 | block hash |
+-------------------------------------------------------------------------+----------------+
And then, when miners grind their nonces, then what is really changed in practice? Only nonce value, set to 0x1dac2b7c is incremented, decremented, or otherwise altered. Which means, that for the first 2^32 computations, after getting a given block template, a lot of computations are identical. A lot of internal SHA-256 states are identical, when first, second, and third message is hashed. Which means, that things doesn't have to be computed every time.
One of the obvious optimizations is saving "exit hash", and then using only two SHA-256 calls, to mine things. However, there are also some less obvious optimizations. For example: if a single 32-bit value is the only thing, which is changed, then the final block hash depends only on these 32 bits. Everything else is constant. All other w-values are the same. Which means, that a lot of things can be computed once, and reused, without triggering the full SHA-256 computation over and over again.
And this fact is obviously used in some ASICs, because they are wired specifically to mine 80-byte block headers, and many things are computed once, and then stored for all future computations. When it comes to RIPEMD-160, executed on top of SHA-256 of some public key, similar optimizations can be done. But it is far from mapping the single bit of the hash, to the single bit of the hashed public key. By analyzing SHA-256 and RIPEMD-160 more deeply, it is possible to create a chain of equations, which would allow skipping some keys, but I doubt prefix searches are smart enough, to even prepare such equations, and switch from their "vanity grinding" into something better, and actually checking the proper bits in RIPEMD-160 output, instead of checking just the beginning.
now there is so much newbies that are posting rubbish that I cannot stand it
Just ignore them. Reading this thread after filtering some users is much easier.
Edit: Here is how hash function analysis can be started. We have two hashed blocks: the Genesis Block, and the block after that. We can explore it round-by-round, four rounds at a time (because the same internal values are passed from one round to another). Then, we can see something like that:
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
| | Genesis Block | Block number one |
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
| | 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19 | 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19 |
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
| 0 | 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19 | 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19 |
| 4 | c83f4d56 a2a7a1b0 fb9d8a8c fd08884d 7b116b56 465b3847 1df5d216 99c7e2a2 | 0f0ab261 2499aad3 6b801696 fd08884d 12780b06 46efd306 8dd85e20 99c7e2a2 |
| 8 | cde67f7d 543f3eff a2d7a833 e5f73d23 d31ffd8a 1e678142 f1279627 d2b3724d | 06411511 f43f42fd 45155cd2 7f85235a 084afe03 a72f84f4 ef4bf414 5301a7e3 |
| 12 | b6765083 bd08b5ff 70eaa7fe c92cbfc6 28cbdc34 3e025d97 48119282 d8c2b68f | c973f92d 46b0d3da 1c695ead 2cb581d8 f6d1d1fc 178700ae 695e543e 7ad91d0c |
| 16 | 75cb74d0 381faffc dda5108a b3ff0d63 6328db87 95b3d2fc 1b39d036 17feeddf | 036ae1ad e9d019c5 05760271 9309d539 57526a13 2430ad2d 74538499 fe777873 |
| 20 | d167be3b e00ec585 5a17eaac c1cbbd65 17e89ecf aa14dd21 1047c73f 62196338 | 3179b978 67a5b391 08e2e2c5 6d4a35f8 7355d2fd 686effe4 08c8acaf 18adf21b |
| 24 | e793709d 06e5c375 1b574460 e66077ff e579537b 9ac886b0 cd4f65e8 3ca4bac1 | 3b94e376 d0c42e62 13226d52 a6ba00e0 02ce6992 9d426e78 2da366b5 d0a87db1 |
| 28 | 65ebca1d 4612c6bf 34714950 aad46208 77ca7c81 236e790d 3d7abf09 d8940270 | 44514e4b d3ff613e 58c48564 a717124b 6b817358 3a28961c 9080fd9e 73736725 |
| 32 | 141109fe d4c607a4 a5e36006 738e87b7 742d17eb 901f1ebf 97830240 13357754 | 60450bfa 7a186dfa ea0f69de 21234741 a9a8ca16 24408e49 0203cba9 90edb815 |
| 36 | 6909e0b3 56bdd333 a952d853 687645dc 592b0ce6 9f88ded2 0cf68ef9 b86eb146 | 2d864ce4 402d8b7f 55e93f71 ee8cff9d 0b40faae 4b6b93be 2139fd1b d1b5338d |
| 40 | 80158847 7c78b105 2354749c 6523592d 4dbd1d78 744e9c72 4a3630f7 6c23d10f | 610e44ea 1bbe34aa ea9cd7ed 374a1857 7788842a 75c58c8d f46dae4f 6ab698c2 |
| 44 | 01812bd6 96041c8e c456f44e 73aa8ab5 5a088a34 09b3a097 d406f6ae c460b720 | 9e93e5d8 1bec88ab 0636d087 28f599fd c32c40f2 787c52d7 7361be1a 6e9e2c9e |
| 48 | 67be715f 510a1a84 b37dba9a 8039d657 effbe2ea d6f3dcb6 41e865b7 95610544 | bfdb2104 7c38e0b4 26d46791 f84787d6 e8eb172e b4ab15b3 f38a3a16 bb8ef1b5 |
| 52 | 85c177fa d78fde5a cf2ebde8 e84f669f a623c9c9 d2f10dcc 2e272166 4a79261e | 6c74f956 215077b7 cfdb7e0d 96290e76 70c2d038 0f4d9400 c66f9cdd 04411051 |
| 56 | 63cc77d5 65e6fb99 2424ca47 c3e910d3 654c20b6 af7c77f9 59631ce2 c92cdd96 | 09327200 5f3fe7fa 9ad82319 4e71bc48 bfaada81 1328eded c713662a f4ff4764 |
| 60 | 3c723956 f40e251d b13e2ecf b3b5b928 81882538 43afa463 3e31ac54 3a32780d | 65b88e30 d2aad572 f09f81bb 56130674 e7e58f7e 51d92fec c2049e07 2dc58a6d |
| 64 | 5286b3cc a7f1116b 545db90b 7909d56e 72ba866a b3fb9b3c 772dad8b eb392c02 | 3fec2cbc c4537bab c9fdaf62 d811832f 7baebc61 8d7012e9 406e8ac4 b2943493 |
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
| | bc909a33 6358bff0 90ccac7d 1e59caa8 c3c8d8e9 4f0103c8 96b18736 4719f91b | a9f61323 7fbb2a30 066ca2d4 7d617869 ccbd0ee0 28757b75 5ff2646f 0e7501ac |
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
| 0 | bc909a33 6358bff0 90ccac7d 1e59caa8 c3c8d8e9 4f0103c8 96b18736 4719f91b | a9f61323 7fbb2a30 066ca2d4 7d617869 ccbd0ee0 28757b75 5ff2646f 0e7501ac |
| 4 | 98610c20 de845910 1f8aee5c b7f888df c7253cdb 238956e3 af5e1cba a8a8881c | f76ada1d d9d5e474 9b6d409f a07055cc c5a9438f 58f6c7f5 b0b9abe3 42a76626 |
| 8 | 77ced14b 6928073f 93b7a01d 5600cb82 7961a521 fb09d45b 0a85b9bb ac4d05f0 | 5347a1d5 a645862f 164d97d2 e8ca2653 d5700861 7c74348f d7bb71b6 a76f41f6 |
| 12 | b4109b69 568f8b4d 147883a5 718e3059 a56c8572 8fb0e9c7 5038acc6 e6f352c1 | 35a64c33 c3a7f0e4 590fcef8 651f6bcb 1fd19118 ba22b096 0d61e35e f2a7e342 |
| 16 | 8d628d5f b85b77bb 346fa1f2 09a2accd caf190f9 9ebad54f 85b1c84a 72f4312b | c1f36a85 f797bee4 e8565acf b2a4235d 70c9bb11 959779c9 a6f5de16 905acf50 |
| 20 | 2cb82542 6ebaeafa 097e66b9 b3eb89c3 6649a0d3 0f9e9e62 77c206ed fd90da1f | a82d973a f3af8ca0 7530249e f93694f5 910b7f71 80e74d7d 681d051b e00a7b50 |
| 24 | ea6b17f8 0c581004 4edd9829 c29f3a60 e4cfae2a 47d80cc1 4a597b15 0825f906 | 7f4c585c df40e640 8b530a96 1373b495 85d68818 8d321a3a 1ead778f 75f9f6ce |
| 28 | adfd69c0 b643bce2 638fb548 593ff620 e0e1f55c caf644dd 115c823e a483ab49 | 31f0a3ad e727f36d 12aba469 04857889 2d299928 e6678957 ae2ed89c 4c674542 |
| 32 | 647e6aea 60bb3b5c 3ca721e0 107d66b6 b39bf62a 3d51e8ab a784683f 311067ea | 8b886e6c 38d3735e c5099a99 a12b9713 c3651c4f faeba934 3805e9b9 de725886 |
| 36 | bce0bd6f e8951c41 1ae6a1d5 446ca183 0c1f827e 324b8aaf 838891d7 b843cb79 | e2fe2295 818ebdbb 1452e787 f78df154 a1ae4e4d 702742ae 9d517ae0 9ef01815 |
| 40 | 8ff5ea0b 2efd669a f9eeacb3 07f01c55 d1e633f1 385b1aa6 04bfc5b9 0cc789e6 | 3da7a559 754d694e 82fc3a41 4faebb13 f633c2be f183cd7e 2202c7a6 31c33bf1 |
| 44 | 81925455 be68b761 ccd5d8cd 9fdccde9 fc610813 7b582d84 bb3a2b12 93c5d091 | 18eabf27 2a277a91 ae14b0db 2bc37e88 28a01eb0 3051fcdb fffddcbe 4a4fafb5 |
| 48 | 63e9b560 0d183c7b 1547bb26 c71464c2 9ff84168 03dca2f5 94ccf523 4e868ee5 | 637d89d7 19b7466d d6ff04e2 02210911 c1949c56 c238b640 eecc6368 6dbed807 |
| 52 | 986207b6 e4c03870 440cafd0 1a0bb7a3 bdec1198 5290728a f90603b6 c6a96b69 | f5a532e1 9b08ac29 e7bf489f c309d3a3 70da9eea 914f98bc 30eda5f0 10e8b3b9 |
| 56 | 29c7669f e242d533 79dbf2fa 0b75edcf fc7a0f87 47204a1f ba7657e3 4d8edce6 | 57733186 34c38720 1eed3eff b16fc5d0 ddfb1570 9526b7ab 97b5a9ee fe1f0a83 |
| 60 | 2f89c72b d04c9164 6eaf599e 95eb24e1 f6f1e66a 9a612751 57e207af 548a30ba | 02750a01 7fdef707 f1e0c9a3 b04f1e3a 4c08fd9b 90fe31dc 7acc4249 75b33dbf |
| 64 | f2b168eb 1d0734a3 0fa69565 d8f62ad9 860951d0 6b18f24b ad314136 2aabdd52 | fd77c414 1123cd85 710a4f5b 24b05933 277412c7 e12e0339 7a24be9f 9c4d5749 |
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
| | af42031e 805ff493 a07341e2 f74ff581 49d22ab9 ba19f613 43e2c86c 71c5d66d | a76dd737 90def7b5 7776f22f a211d19c f43121a7 09a37eae da17230e aac258f5 |
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
| 0 | 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19 | 6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19 |
| 4 | e6ec0284 dd7bfa27 e8f12634 ab4a8b6b 9df1b4a1 df96249e de72151c 4809e5c0 | 4cc92bf3 09f85c30 fa8130a1 a3765f84 08541cd1 dbf17445 7e0196b0 4035b9d9 |
| 8 | cde00ab8 5c147bb3 2c47cb8e 1ff26718 3d046e63 425b89e2 3e9e8994 40adac05 | 2062c851 7f1d61a4 a97243c2 d0ee80e7 0c4b80e0 42e4e82a 1204b362 8393c634 |
| 12 | fb9b744c b053d4d9 e599023c 90cd3b90 93185b03 fa15a603 68c3074c 7de6c855 | 1774f570 d0923a3a 71a0c0cc 52f432a6 ba0ca9b6 45c64e27 d759a1a7 78bf7c4a |
| 16 | a406a042 f3547aab ae5aed1e b0773648 74eb6ac0 4075280f a11f0e28 5e58eb56 | f134cf94 182602cb 68570429 ea77c171 57d856b9 56f25181 59696f3a 6e32bcf9 |
| 20 | 0a4df97b 400a3e7c 82ceadca 022fe184 e12c6d23 bcff8059 dbf4c150 5abaad0d | 0e06eff9 84a8e4a3 45baa551 086e35ad 92ec876f ca1e8042 3e4627b2 e6db070e |
| 24 | af5a1ef0 c8888de7 c897ff80 b0d2618e 31e932c6 eddd1a5c 61550f99 7204c580 | 8832df7b 5f238175 1ab6513f bfa9247e a42f01b8 2f144302 a939c2ed 9b764449 |
| 28 | 14cdb379 adc275fd d11379d2 df7db108 198a5ab6 5fbaac69 80f526a0 138d32e5 | be4fc17a a1ab3288 f3eeca1f 88d6c68f 93adfae9 60ab93a0 f91e8aa9 5ba00126 |
| 32 | 15c8de99 ab58f29d e82f242b dbec618c a13920b8 186a1f9e 905a3791 3d7071bb | ee62a90a 0608ad00 1b86e12b fb6de272 466f6e45 182635fb 394060b2 3510fe0e |
| 36 | 765dd4f9 b7a4c0cf aad9f494 c71cd314 6bf22f33 f1636397 3182e6e3 66ff4050 | 8c24ccef ced86627 d1027bec 084d7bfb 0f2e0999 29d4f191 b61bc359 7c4cc275 |
| 40 | 7dff285d c14863d3 c19ed040 4be4f1ba 634cadd2 6bef97ca 67a66973 cf14cde8 | c71eb7fe 429e11e1 7811815e 164a3443 593f5e28 22831a7e 6b7065cb 3b505522 |
| 44 | 5ba5091f c85903da 16adc632 7bd4f62d b5f70223 068074b8 a229dd52 24a6377d | 1ca6081b 71ff41e1 dedc6548 2d2f0357 b751a493 791a5f9a a1cfdd96 8c6c3786 |
| 48 | cb2eb43a d890f410 bd3420f7 5bc06388 77d0a1e8 0cd296e3 6ce3fc01 72b0749a | 2db9451c fa733d0a 04936efe 7ab032d2 356cd72b 94514cdb a1c54294 2b0fe99c |
| 52 | 4963773d 25889731 0c8f1e74 a11706c1 1c4b47e8 a81000fa fe58bbcf 79d596c0 | 156033bc 6c064e31 6baed901 ddf9c568 a1b875a9 cf3ad79b 771bc514 655b3ee1 |
| 56 | c6396799 1494042b 1b6aec9a 5644097e 44ebc8a4 95022602 1473aaab 83619519 | dae5e94b 64e12363 821299ef 9da3604b 24f4195a d62636be 67e9f538 f60072c7 |
| 60 | 36ec7c9d d95159d4 e0540517 a4006b06 5f3fcb86 89169a84 87156a54 3b2e00b4 | 1dc22635 695dab44 547616af 287bbfbc 594f1e3b bd8973ae 54a5a8a0 d7faf486 |
| 64 | 05d8a5a3 fb8a04ed 8537aed4 09140215 421030e6 4654a010 49523f55 a41f32e7 | de5704b1 03b3679b a70fa11e 573a4d3b c3331d58 b65442fa 490ac0d8 a41f32e7 |
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
| | 6fe28c0a b6f1b372 c1a6a246 ae63f74f 931e8365 e15a089c 68d61900 00000000 | 4860eb18 bf1b1620 e37e9490 fc8a4275 14416fd7 5159ab86 688e9a83 00000000 |
+----+-------------------------------------------------------------------------+-------------------------------------------------------------------------+
And now, someone can look closely, and notice: Hey! 0xa41f32e7 is repeated in both cases, and both block hashes end with zeroes! By looking closer at it, we can notice, that initialization vector is added with the 64th round of SHA-256, and that's what can form a final hash. Which can lead us to some interesting observations. For example: when we mine blocks, then we don't need the last addition of 0xa41f32e7 and 0x5be0cd19, which would give us 0x100000000, and would be trimmed into 32-bit value of 0x00000000. And there is more: if 64th h-value is always equal to 0xa41f32e7, then it depends on some other values before that. And they also should be equal to something, to give us exactly this result, which puts some constraints on top of what we have.
Also, someone can notice: Hey! 0xfd08884d and 0x99c7e2a2 is also repeated! And it should be, because the first 32-byte value, which is consumed, is just the version of the block header, which is identical in both cases. Which also means, that as long as it is set to 0x01000000, then it can be computed once, and then reused.
Similar dependencies are present, when SHA-256 is combined with RIPEMD-160. When different public keys are tried, then some bits of the hashed message are the same, and some are different. And because of some known weaknesses of SHA-256 and RIPEMD-160, that fact can be used, to properly calculate, which bits will change, and how they will change. And after trying a few examples, it should be obvious, that just comparing vanity prefixes is stupid, because of how the structure of used hash functions looks like.
However, there are some dependencies, waiting to be discovered by people, who really understand, how hash functions are internally computed, and which computations can be simplified. Computing four rounds at a time, starting from some hash in the middle, and skipping some single operations like addition, and re-using the same values from previous computations, are just some trivial optimizations, that can be done at the start. But there is more, much more to discover (and obviously, it is much more complex, than comparing just some prefixes, and hoping that vanity generator is all that is needed).