|
Title: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 07, 2019, 05:00:27 PM Please note that since this thread will be used as reference material in a science fair project we delete most posts in this thread just to keep it clean. My middle school daughter and I are working together on a science fair project related to using the Pollard Kangaroo algorithm (https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm) to find low entropy private keys when the public key is known.In other words, once we quote a post and answer it then we delete the original post. Your post and the answers we gave or questions from us will all still be in the thread. The thread stays shorter and cleaner this way. I hope this is not an issue for anyone. It is just to keep the thread as short and clean as possible. It is not because we do not appreciate your posts. We do! Thanks! So far we have written the basic code and it works. We are using the results from the "Private Key Entropy Test Transactions" (best thread here) (https://bitcointalk.org/index.php?topic=5166284.0) (other thread here) (https://bitcointalk.org/index.php?topic=1306983.0) as our known answer unit test for the program. Found a lot of good information here (https://bitcointalk.org/index.php?topic=5166284.msg52318676#msg52318676) The current "record" for the largest private keys found by the program is shown below. Note how slow the program is compared to the state of the art GPU based programs: Code: ver = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available Code: ver = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available Code: ver = the subversion VERsion of the code People who have volunteered to help with testing (listed in alphabetical order): Quote agatazit AirShark AndreuSmetanin Angelo1710 arulbero asher1101 ayiphelmy bulleteyedk byyuans Darmont33 dextronomous Firebox iparktur JDScreesh johan11 miningforprofit PietCoin97 sanhwy stivensons supika Telariust ultramen vimp666 ZafotheNinja zielar Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 07, 2019, 06:50:03 PM just make a volcano like everyone else she will get a good grade on the project. It looks cool to and she will have fun. ;D She actually did that for here kindergarten science fair project.Combine the vinegar, water, dish soap and 2 drops of food coloring into the empty soda bottle. Use a spoon to mix the baking soda slurry until it is all a liquid. Eruption time! … Pour the baking soda slurry into the soda bottle quickly and step back! Here is a list of the 2018 Colorado Science & Engineering Fair entries. Take a look at the titles of the projects. This will give you some idea of the quality of the projects she is competing against: http://www.csef.colostate.edu/2018CSEF/2018_Finalists.html You will see that there is not a single vinegar and baking soda volcano in the entire list ;) Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 08, 2019, 01:25:00 AM bits = number of BITS of entropy in the private key a = lower bound for the private key search b = upper bound for the private key search I think your number of bits of entropy value is off by one, unless bounds are inclusive and you are rounding up. Here is an example from the output: Code: test = 5 The first private key that has 6 bits is 0x20, the last one that has 6 bits would be 0x3F. So, yes, I need to subtract one from the value of b being displayed. Is that what you are referring to? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 08, 2019, 02:45:33 AM Yes and no. One of the bits in your private keys is always 1, so it can't count toward entropy. If your range goes from 0x20 to 0x3f, then there are 32 possible values, so 5 bits of entropy. If it goes to 0x40, then there are 33 possible values and slightly more than 5 bits. OK, we will fix the terminology issue. bits = the number of bits in the private key, not the entropy (which is one less).Also, what I know about the algorithm is what I got from skimming the wikipedia article. A couple questions: 1. Is there a reason for not setting a to 0? 2. What is your mapping function? There are two conditions that can happen when you run the wild kangaroo portion of the algorithm: there is a collision with the tame kangaroo and the private key is found, or, the two fail to collide. The termination condition for a failure to collide is test (b - a + c) so if a is zero then it will cause the algorithm to run longer than necessary in the failure to collide case. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 08, 2019, 11:26:12 AM BurtW We have not decided yet on that. If you would trust me I can give you the executable much sooner. If you would not trust an executable from me then you would have to wait for us to decide to give out the source code.You give source code or binary file? We are still making great strides in making it faster so we are not ready to publish it as an executable or as source yet. We are also waiting to see if drotika actually publishes their code and what it looks like when it is published. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 08, 2019, 11:58:48 AM This shows that luck is a major factor in the total run time. In general it should take about twice as much time to find the next key but the run times are all over the map because of the luck factor:
Code: Bits in the Number of tame Time to find We are still optimizing the code so the absolute values of these run time will go down over time as the program is improved. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Firebox on August 08, 2019, 12:47:44 PM BurtW We have not decided yet on that. If you would trust me I can give you the executable much sooner. If you would not trust an executable from me then you would have to wait for us to decide to give out the source code.You give source code or binary file? We are still making great strides in making it faster so we are not ready to publish it as an executable or as source yet. We are also waiting to see if drotika actually publishes their code and what it looks like when it is published. You are, guys, doing a very comprehensive and very very important work. Such a tallented kids like your daughter deserves not only the awarded medal in the school but a huge popularity within the scientific comunity, as such kids are the ones who will definetely influence our future. Personnaly me, I have no any reason to NOT trust your binaries. So if you will publish it I will definetely test it on my PC. Even if it will f**k up my machine I will have NO any complaints to you. I wish you great success in all what you are doing! Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Telariust on August 09, 2019, 06:29:16 AM Top useful links:
base https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ hand translate to ru/ua (recommend instead translate.google) https://habr.com/ru/post/335906/ 0) best of the best, all in 1, epic, 2012 Chapter 14. Factoring and Discrete Logarithms using Pseudorandom Walks https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch14.pdf 1) with reference to old J. M. Pollard, “Kangaroos, monopoly and discrete logarithms,” Journal of Cryptology, №13 (2000). https://web.northeastern.edu/seigen/11Magic/KruskalsCount/PollardKangarooMonopoly.pdf (good dir web.northeastern.edu/seigen/11Magic/KruskalsCount/) 2) about parallelism problems P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, J. Cryptology, №12 (1999) https://people.scs.carleton.ca/~paulv/papers/JoC97.pdf advice acceleration tips by fernand77 https://github.com/JeanLucPons/VanitySearch/issues/25#issuecomment-509293732 ====== Sorry, I can not resist ;D a little friendly trolling Quote Dad, for the new year, I asked Santa to give me Barbie and DVD with the new Winx Club season. Why did he decide that the “Pollard Kangaroo Algorithm in raw asm” would be better? ====== I would like to test your Pollard Kangaroo program. (need more examples sources for undestand concept how it work. bin no interest. lang any.) Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 09, 2019, 06:43:24 PM I would like to test your program. ;D I would like to test your Pollard Kangaroo program. (need more examples sources for undestand concept how it work. bin no interest. lang any.) I would like to become a tester, but I have a very weak AMD laptop. I would like to test your program. ::) All added to the list in the OP.Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 19, 2019, 01:44:11 PM I would like to test your program. :) I would like to test your program :-* If you need more testers i would like to participate and help out I have been following the 100BTC challenge thread and just recently tried working with bitcrack I would like to test your program, BurtW. All added to the list in the OPTitle: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 19, 2019, 02:50:19 PM See chart: https://imgur.com/M8j5rdl
We are still fine tuning the algorithm. Using just one thread on a PC and an algorithm which uses almost no luck we predict it would take 101 million years to find #105. This is using a small number of very careful and "thorough" tame kangaroos. Next we will try to get better results using a larger number of more luck based tame kangaroos. Data collected by the latest algorithm: Code: bits Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: supika on August 20, 2019, 11:45:58 AM Who need some code, I have it for Python 2.7! This is my own code and I apologize for absolutely no-PEP. And for my English, I apologize too. The code is not so fast, but my estimation is more optimistic - only 10000 years on average for the problem 105. Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code. The code is on my WebSite: http://fe57.org/forum/thread.php?board=4&thema=1#1 This is my main interest. You are now informed that my site exists in the Universe! To be more interesting: test problem 75 from pickachunakapika to drotika solution: 26970178626862821196031 (decimal) I guess that the solution can be posted now because all deadlines are finished. Or I miss something and drotika was already posted the answer. Great contribution @57fe The script is working only with compressed addresses? Would be possible to work also with uncompressed addresses? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: vimp666 on August 20, 2019, 12:46:56 PM Quote Would be possible to work also with uncompressed addresses? Yes, it's even simpler than for compressed address. All you need is to set X and Y coordinates from an uncompressed record explicitly just before line 188 in the code. No need to calculate Y from X. If I think correctly, uncompressed coordinates in blockchain definitely means uncompressed address. Perhaps, it is actual only for very old blocks.Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: vimp666 on August 20, 2019, 01:03:24 PM X = X % (2**256) it turns out after this line you need to insert Y = Y % (2**256)? No. First, you need coordinates of EC-point in uncompressed form. See, for example, the transaction: https://www.blockchain.com/ru/btc/tx/69211d75f7aa8b2bd8f495a672de5cb87d5ce3789cfb0a91407a4b9120405384?show_adv=true (https://www.blockchain.com/ru/btc/tx/69211d75f7aa8b2bd8f495a672de5cb87d5ce3789cfb0a91407a4b9120405384?show_adv=true) There is uncompressed coordinates in every record starting from words PUSHDATA(65). Let's take the one of them: Code: PUSHDATA(65)[0485c26293005c33a5afafada4fd3177767af371927db1c8519402d04072cf9852b3f555474c9cbac1f786141da4bad9fabb4e450dd812a7f1e69ca662caef1796] You can split this hex number manually, or with Python: Code: s = '85c26293005c33a5afafada4fd3177767af371927db1c8519402d04072cf9852b3f555474c9cbac1f786141da4bad9fabb4e450dd812a7f1e69ca662caef1796' Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: vimp666 on August 20, 2019, 03:20:37 PM Who need some code, I have it for Python 2.7! This is my own code and I apologize for absolutely no-PEP. And for my English, I apologize too. The code is not so fast, but my estimation is more optimistic - only 10000 years on average for the problem 105. Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code. The code is on my WebSite: http://fe57.org/forum/thread.php?board=4&thema=1#1 This is my main interest. You are now informed that my site exists in the Universe! To be more interesting: test problem 75 from pickachunakapika to drotika solution: 26970178626862821196031 (decimal) I guess that the solution can be posted now because all deadlines are finished. Or I miss something and drotika was already posted the answer. Very nice :) For those who use python3, you may have to change a few things for the code to work: 1) for all print statements you need (), for example line 60 change this > print 'prime must be 3 modulo 4' to this > print ('prime must be 3 modulo 4') 2) make sure you distinguish between integer division // and float division / for example, line 63 change this > pw = (p + 1) / 4 to this > pw = (p + 1) // 4 For case 32 I get P-table prepared tame and wild herds are prepared 6091.198 h/s 6119.991 h/s 6047.619 h/s 6028.418 h/s 6020.816 h/s 5995.830 h/s 6041.220 h/s 6026.008 h/s 6077.185 h/s total time: 45.38 sec SOLVED: 3093472814 Hops: 273742 tame and wild herds are prepared 5995.223 h/s 6044.420 h/s 5966.429 h/s 6050.819 h/s total time: 68.41 sec SOLVED: 3093472814 Hops: 137749 tame and wild herds are prepared 6038.017 h/s 5968.435 h/s total time: 82.83 sec SOLVED: 3093472814 Hops: 85546 165679.0 +/- 56093.66357263537 Average time to solve: 27.61 sec Average time to solve: 0.86 sec Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: 57fe on August 20, 2019, 05:11:03 PM Quote If you wish to speed up calculations by a factor 15 approximately, install gmpy2 module.. that's great butQuote random.randint this is a very slow function, try to speed up through its analog numpy.randomFunctions from random module used only in preliminary stage for placement tame and wild herds. So, there is almost no influence on speed of the algorithm. Only if we try to select a huge number of kangaroos. Also, when the problem is very simple (16 bit, for example) the time of the placement may be significant in comparison with the time of solution. But total time still very small for human. For pseudorandom hops the coordinate X itself is used. Main goal of the code presented is a template with minimal dependencies. Numpy is external module which requires installation. But I can't eliminate gmpy2 at all, it is very efficient. Anyway, the table with time-to-solve estimations posted by j2002ba2 means GPUs are 3..4-order more efficient than the code presented. j2002ba2, if you are here, how many hops/sec you have reached on single Tesla V100? Is my estimation of 2 GHops/s correct? At least 1 GHops/s required if authomorphisms taken into account, but I can't beat even half of this value. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: 57fe on August 21, 2019, 04:52:56 AM Anyway, the table with time-to-solve estimations posted by j2002ba2 means GPUs are 3..4-order more efficient than the code presented. For me 4x Tesla V100 on AWS were running at 6515 Mj/s, this gives 1629 Mj/s for a single V100.j2002ba2, if you are here, how many hops/sec you have reached on single Tesla V100? Is my estimation of 2 GHops/s correct? At least 1 GHops/s required if authomorphisms taken into account, but I can't beat even half of this value. This is really cool! j2002ba2, thank you very much for posting this reference point. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: itod on August 22, 2019, 12:24:11 PM Have anyone experience to change the script for multi thread or cuda GPU? Also for uncompressed public keys? It's not trivial to implement it in CUDA. Read here about the problems expected: https://github.com/beranm14/pollard_rho/blob/master/report/main.pdf (https://github.com/beranm14/pollard_rho/blob/master/report/main.pdf) Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Darmont33 on August 22, 2019, 03:30:58 PM Who need some code, I have it for Python 2.7! This is my own code and I apologize for absolutely no-PEP. And for my English, I apologize too. The code is not so fast, but my estimation is more optimistic - only 10000 years on average for the problem 105. Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code. The code is on my WebSite: http://fe57.org/forum/thread.php?board=4&thema=1#1 This is my main interest. You are now informed that my site exists in the Universe! To be more interesting: test problem 75 from pickachunakapika to drotika solution: 26970178626862821196031 (decimal) I guess that the solution can be posted now because all deadlines are finished. Or I miss something and drotika was already posted the answer. Very nice :) For those who use python3, you may have to change a few things for the code to work: 1) for all print statements you need (), for example line 60 change this > print 'prime must be 3 modulo 4' to this > print ('prime must be 3 modulo 4') 2) make sure you distinguish between integer division // and float division / for example, line 63 change this > pw = (p + 1) / 4 to this > pw = (p + 1) // 4 For case 32 I get P-table prepared tame and wild herds are prepared 6091.198 h/s 6119.991 h/s 6047.619 h/s 6028.418 h/s 6020.816 h/s 5995.830 h/s 6041.220 h/s 6026.008 h/s 6077.185 h/s total time: 45.38 sec SOLVED: 3093472814 Hops: 273742 tame and wild herds are prepared 5995.223 h/s 6044.420 h/s 5966.429 h/s 6050.819 h/s total time: 68.41 sec SOLVED: 3093472814 Hops: 137749 tame and wild herds are prepared 6038.017 h/s 5968.435 h/s total time: 82.83 sec SOLVED: 3093472814 Hops: 85546 165679.0 +/- 56093.66357263537 Average time to solve: 27.61 sec Hi, how did you change line 160 for python 3? if you mean this line: print '%.3f h/s'%((Hops-Hops_old)/(t1-t0)) just add parenthesis print ('%.3f h/s'%((Hops-Hops_old)/(t1-t0))) do the same for all print statements. Now everything works! I didn’t put it there () thank ;) Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 24, 2019, 03:24:55 PM We are about to release the first executable of our project for feedback. There will be a Windows 64 bit cygwin version and a 64 bit Linux version. The program is written in C using the standard OpenSSL library BIGNUM and EC_POINT objects. The main thing we are interested in for this release of the program is the number of hops per second on various machines. It seems to us the OpenSSL library is pretty slow. Here is what three runs of the program, for a 35 bit key, looks like on my Windows laptop:
Code: C:\ROO\Debug>roo Code: burt@burt-MS-7640:~/ROO1/Debug$ ./ROO.exe Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Telariust on August 24, 2019, 06:30:14 PM ..OpenSSL library is pretty slow. OpenSSL's advantage in versatility, but not in speed, no.https://ai2-s2-public.s3.amazonaws.com/figures/2017-08-08/116ed892cf5daf05adfa03d2f421b84f340b2efb/4-Table2-1.png I bet python+coincurve will be faster! ideally you need C bitcoin/secp256k1 I am porting your code to bitcoin/secp256k1 as soon as the source code is published. (there is the usual addition and multiplication of points, nothing complicated) (..but I feel you want to do it yourself, your own and not someone else's head?) Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 25, 2019, 06:10:18 AM One weird thing is that the runs on the Linux machine took longer than the ones on Windows (usually is the other way around). And the other weird thing is that the program is called 'roo' in Windows and 'ROO.exe' in Linux :) It is actually ROO.exe in Windows but Windows adds the .exe for you and is not case sensitive...OpenSSL library is pretty slow. ...ideally you need C bitcoin/secp256k1 ... Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 26, 2019, 10:23:54 PM We now have a compile time switch between OpenSSL, secp256k1(SCALAR_8X32, FIELD_10X26), secp256k1(SCALAR_4X64, FIELD_5X52), and secp256k1(SCALAR_4X64, FIELD_5X52, ENDOMORMPHSIM). Here is the run time and hops per second comparison for the 32 unit tests:
Code: pkey Standard OpenSSL library secp256k1 (S 8X32, F 10X26) secp256k1(S 4X64, F 5X52) secp256k1(S4X64, F5X52, EM) secp256k1 (S 8X32, F 10X26) averaged 5258 hops per second secp256k1(S 4X64, F 5X52) averaged 5352 hops per second secp256k1(S 4X64, F 5X52, , ENDOMORMPHSIM) averaged 5350 hops per second We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on August 27, 2019, 10:38:46 AM I draw your attention, secp256k1_scalar_set_int() has x32-x64 problem We also found this issue and also quickly created our own functions to get it to work. We also called our new functions secp256k1_scalar_set/get_uint64 so I guess great minds think alike! ;)my fix Code: void secp256k1_scalar_set_uint64(secp256k1_scalar *r, uint64_t v){maybe your problems grow from here. We were just trying to quickly get everything to work so we have not optimized anything yet. Our function was: Code: static uint64_t secp256k1_scalar_get_uint64(secp256k1_scalar * a) ENDOMORMPHSIM Endomorphism is implemented here only to accelerate the signing of the transaction, so do not expect this to accelerate the usual multiplication.We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance? table #1eprint.iacr.org/2016/103.pdf The size of a pre-computed table in memory is created just for this. Speeds up multiplication in exchange for RAM. Ryan also used the increased size -w 18/20/22/24.. in the brainflayer. ECMULT_WINDOW_SIZE? maybe ECMULT_TABLE_SIZE with WINDOW_G? ecmult_impl.h Code: #else We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance? questions like these can only be answered with a well designed benchmark. in this case you have to measure how long it takes to do the precomputation with different values ∈ [2, 24] and how that compares with the rest of computation. if the rest is significantly longer then it can justify that long initial precomputation and allocation of memory. We also found this in the code: Code: /** Larger values for ECMULT_WINDOW_SIZE result in possibly better Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Firebox on August 29, 2019, 02:15:17 PM Who need some code, I have it for Python 2.7! This is my own code and I apologize for absolutely no-PEP. And for my English, I apologize too. The code is not so fast, but my estimation is more optimistic - only 10000 years on average for the problem 105. Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code. The code is on my WebSite: http://fe57.org/forum/thread.php?board=4&thema=1#1 This is my main interest. You are now informed that my site exists in the Universe! To be more interesting: test problem 75 from pickachunakapika to drotika solution: 26970178626862821196031 (decimal) I guess that the solution can be posted now because all deadlines are finished. Or I miss something and drotika was already posted the answer. Very nice :) For those who use python3, you may have to change a few things for the code to work: 1) for all print statements you need (), for example line 60 change this > print 'prime must be 3 modulo 4' to this > print ('prime must be 3 modulo 4') 2) make sure you distinguish between integer division // and float division / for example, line 63 change this > pw = (p + 1) / 4 to this > pw = (p + 1) // 4 For case 32 I get P-table prepared tame and wild herds are prepared 6091.198 h/s 6119.991 h/s 6047.619 h/s 6028.418 h/s 6020.816 h/s 5995.830 h/s 6041.220 h/s 6026.008 h/s 6077.185 h/s total time: 45.38 sec SOLVED: 3093472814 Hops: 273742 tame and wild herds are prepared 5995.223 h/s 6044.420 h/s 5966.429 h/s 6050.819 h/s total time: 68.41 sec SOLVED: 3093472814 Hops: 137749 tame and wild herds are prepared 6038.017 h/s 5968.435 h/s total time: 82.83 sec SOLVED: 3093472814 Hops: 85546 165679.0 +/- 56093.66357263537 Average time to solve: 27.61 sec Hi, how did you change line 160 for python 3? if you mean this line: print '%.3f h/s'%((Hops-Hops_old)/(t1-t0)) just add parenthesis print ('%.3f h/s'%((Hops-Hops_old)/(t1-t0))) do the same for all print statements. Now everything works! I didn’t put it there () thank ;) I have installed gmpy2 module v.2.0.8 and got a good results, speed increased from ~6k h/s till ~150k h/s and for e.g. #45 solved in ~100sec. But when I run the same script for e.g. #105 files wild.txt & tame.txt are empty ((. When you, guys, run this script for the #105 addr, do your files wild.txt & tame.txt being filled-up with any data? If yes share pls your version of script. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Mangal99 on August 29, 2019, 03:28:12 PM To Firefox: Does that mean that kargaroo jumps appears very late? At startup files wild.txt & tame.txt were also empty, but after 2 days of work has appeared a few lines. I think yes. Puzzle # 105 has a lot of difficulty. Obviously, you need a version of the program on the GPU. There are already several programs for computing using the Pollard algorithm on the GPU, but they are not in the public domain. Also on freelance sites there are several orders for the development of such programs on CUDA and OpenCL. Budget from 300 to 1000 dollars. Maybe someone will share or sell a similar program. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Firebox on August 29, 2019, 05:54:21 PM To Firefox: Does that mean that kargaroo jumps appears very late? At startup files wild.txt & tame.txt were also empty, but after 2 days of work has appeared a few lines. I think yes. Puzzle # 105 has a lot of difficulty. Obviously, you need a version of the program on the GPU. There are already several programs for computing using the Pollard algorithm on the GPU, but they are not in the public domain. Also on freelance sites there are several orders for the development of such programs on CUDA and OpenCL. Budget from 300 to 1000 dollars. Maybe someone will share or sell a similar program. If any of it realy exist... I have a huge doubt! Otherwise why to sell it if you have it )). Take a fu****g loan in the bank, rent any huge cloud GPU VPS and open all addresses with available PUBKEY. That it! But as far as we can see, since this scripts were anounced none of the 100+ addresses was openned, so looks like or it doesn't work or it's fake.))) Anyhow, hopefully a good part of community soon will release an open source version on such script. Fingers crossed! Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: asher1101 on August 31, 2019, 07:03:43 PM Hello, I am glad to participate in this project.
Regarding the Elliptic Curve, I think there is a weakness in the current Algorithm. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on August 31, 2019, 10:59:18 PM Finally I got gmpy2 installed on windows ::) Thanks to this site : "https://www.lfd.uci.edu/~gohlke/pythonlibs/" which provides unofficial Windows binaries for Python Extension Packages.
Code:
My modest config: Intel(R) Core(TM) i7-2670QM CPU @2.20GHz 16Gb (Dell Inspiron N5110) Without gmpy2, I was getting some 8000 h/s ... for example, if you are running windows 10 64 bit and you have python 3.7 installed, download this file : gmpy2-2.0.8-cp37-cp37m-win_amd64.whl from the site above and do: pip install gmpy2-2.0.8-cp37-cp37m-win_amd64.whl Next 0) uncomment ligne 3 (import gmpy2) 1) uncomment ligne 45 (c = dy * gmpy2.invert(dx, p) % p) 2) comment ligne 45 (#c = dy * rev(dx, p) % p ) good luck ! Ooops !!! , I saw this afteward ... https://bitcointalk.org/index.php?topic=5166284.260 from Telariust Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on September 01, 2019, 12:04:13 PM Terminology for the science fair project ------------------------- ------------------------- 0x034AF4B81F8C450C2C870CE1DF184AFF1297E5FCD54944D98D81E1A545FFB22596 54 bit 222872.369 h/s 223958.708 h/s --------------- 230794.045 h/s 230895.206 h/s 230857.369 h/s intel i3-6100, 8gb ddr4 ram, ubuntu 18.x It runs at 3.7GHz ... that explains your rate ... Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: brainless on September 04, 2019, 07:29:45 PM I have tried the python code on linux and windows with or without gmpy2. I was able to retrieve all known private keys (up to case 100) with linux python. However when using windows things go wrong beyond case 59. For exemple case 60 ... the private key should be 0xFC07A1825367BDA but I get 0xFC07A1825367BXX with XX a random number case 61 ... the private key should be 0x13C96A3742F64906 but I get 0x13C96A3742F64XXX with XXX a random number case 63 ... the private key should be 0x7CCE5EFDACCF6808 but I get 0x7CCE5EFDACCF6XXX with XXX a random number etc ... This bug persists even without gmpy2 !!! I am working on it ;D What hardware do you use and how long it took to crack 100? To check all known private keys, I changed the code to search within a given range [a, b], not necessarily the whole range. For instance, private key for case 100 is 0xaf55fc59c335c8ec67ed24826, so if I run my modified python script for range [ 0xaf55fc59c335c8e0000000000, 0xaf55fc59c335c8f0000000000 ], I get the answer in less than half a minute. like to share modifed script for search range ? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 05, 2019, 01:22:22 AM Does anyone know why this post has been erased? it is still here because "brainless" quoted it? Yes, your entire conversation is still in the thread, again: Please note that since this thread will be used as reference material in a science fair project we delete most posts in this thread just to keep it clean. In other words, once a post is quoted then we delete the original post. Your posts will all still be in the thread. The thread stays shorter and cleaner this way. I hope this is not an issue for anyone. It is just to keep the thread as short and clean as possible. It is not because we do not appreciate your posts. We do! Thanks! Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 05, 2019, 01:26:07 AM I am up for testing also? It is live on GitHub yet? Hello, I am glad to participate in this project. Regarding the Elliptic Curve, I think there is a weakness in the current Algorithm. Also, I'm interested in testing... the fpga port. You have been added to the list of possible testers. See the OP of this thread.I realise that is a far way off, and I'm willing to help with the development if you and your daughter are open to the idea. Whatup whatup, all doing their own test, nice to have something to test on a pkey or address, You are already on the list. We are still working on our first release of code.how should i know how it works, i don't know, any news fpga or gpu or cpu dont matter, i'm in, systems ready, got two days off, so love peace out, Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 05, 2019, 01:46:19 AM Terminology for the science fair project We have created the following terminology, inspired by the ITU radio bands (https://en.wikipedia.org/wiki/ITU_radio_bands), that we will be using to describe the relative entropy of the various private keys. For example private keys that have between 61 and 70 bits are called "low entropy" or LE private keys. Keys that use between 91 and 100 bits are called "high entropy" or HE private keys. The entire scale is as follows: Code: max bits entropy range designation Code: ver = 138 with 128 bit integers, sizeof(int) = 4 Using this terminology we can say that our program can pretty easily find all RLE and TLE keys in simple brute force mode [set the PRF to always return 1]. Here are the execution times and number of hops in brute force mode from our program for the RLE, TLE and ELE private keys: Code: bits brute force time hops (of 1*G) 0x034AF4B81F8C450C2C870CE1DF184AFF1297E5FCD54944D98D81E1A545FFB22596 54 bit 222872.369 h/s 223958.708 h/s 223408.635 h/s ... 221374.437 h/s 222090.945 h/s 220270.176 h/s total time: 1089.12 sec SOLVED: 9974455244496707 Hops: 246139766 Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on September 06, 2019, 11:27:20 AM I have tried the python code on linux and windows with or without gmpy2. I was able to retrieve all known private keys (up to case 100) with linux python. However when using windows things go wrong beyond case 59. For exemple case 60 ... the private key should be 0xFC07A1825367BDA but I get 0xFC07A1825367BXX with XX a random number case 61 ... the private key should be 0x13C96A3742F64906 but I get 0x13C96A3742F64XXX with XXX a random number case 63 ... the private key should be 0x7CCE5EFDACCF6808 but I get 0x7CCE5EFDACCF6XXX with XXX a random number etc ... This bug persists even without gmpy2 !!! I am working on it ;D What hardware do you use and how long it took to crack 100? To check all known private keys, I changed the code to search within a given range [a, b], not necessarily the whole range. For instance, private key for case 100 is 0xaf55fc59c335c8ec67ed24826, so if I run my modified python script for range [ 0xaf55fc59c335c8e0000000000, 0xaf55fc59c335c8f0000000000 ], I get the answer in less than half a minute. like to share modifed script for search range ? See here: https://bitcointalk.org/index.php?topic=5166284.msg52375040#msg52375040 Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 09, 2019, 03:56:42 PM We have updated the OP with our latest results. Here is a summary of the results of runs for tests 0 through 49:
Code: test time hps hops compares mem(bytes) total time time hopping not hopping Code: test test number Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Firebox on September 10, 2019, 09:01:32 AM We have updated the OP with our latest results. Here is a summary of the results of runs for tests 0 through 49:... That is already good result! When will be the first release? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Telariust on September 10, 2019, 04:55:56 PM thx, no need all norm after add Code: # get JmaxofSp ################# about speed We have updated the OP with our latest results. Here is a summary of the results of runs for tests 0 through 49:... That is already good result! August 26, 2019 Code: pkey Standard OpenSSL library secp256k1 (S 8X32, F 10X26) secp256k1 (S 8X32, F 10X26) averaged 5258 hops per second September 09, 2019 (secp256k1) Code: test time hps hops it very slow for 1core C/C++ openssl/secp256k1, it should be more! (even if u built early classic 1 Wild algo with 3.28w^(1/2), this does not explain x10 speed drop) Quote We were just trying to quickly get everything to work so we have not optimized anything yet. ok, we expect and hopesee for compare Algo: 1 Tame + 1 Wild with distinguished points, expected of 2w^(1/2) group operations avg stat after 10tests 1core i5-2540, python37x64, win7x64 Code: [i] 8.6K j/s; ... 1core i5-2540, python37x64 + gmpy2, win7x64 Code: [i] 73.6K j/s; ... ################# about secp256k1 library Legendary main question from legendary master :) root of all ecc problems) Are you using affine or jacobian coordinates for the points? secp256k1 have functions J+J->J , J+A->J , and no have functions A+A->A (Is this a precisely optimized library for bitcoin? :)) (all simple, because in real often need multiply rand point instead adding, and jacobian is better for multiply) J+J->J (12M, 4S) - bad choice J+A->J (8M, 3S) - already better (look eprint.iacr.org/2016/103.pdf) you can take the code from break_short by Jochen Hoenicke, it fits perfectly. this code uses J+A->J and convert only X to Affine xJ ->xA (its max what we have in secp256k1 as it is) where A is S-table with pre-computed G,2G,4G,8G,16G.. ..u used pre-computed, y? not say me what u calc every Si permanently used multiplication, nonono,plz,no! X%mask instead pow2(X%k)? (..by the way, that would explain your terrible speed..) ..and use old alternatively functions without protection against side channel attacks, +10-20% speed secp256k1_gej_add_ge_var() instead secp256k1_gej_add_ge() (warn, _var() need normalize before use in some functions.. my early mistake, "leading zeros" github.com/bitcoin-core/secp256k1/issues/601) in ideal - need write new functions: A+A->A (1I, 2M, 1S) - best choice, because in the end we need X in affine for unique representation each point to adding in storage hashtable ..u used hashtable, y?) after which do not need to spend 8M,3S, only nearly 20M to each 1I, it +35% speed-up like that ######## I seem to know what the problem is. This is a very obvious fact for me, I should have started with it. (I should have guessed at a time when about ECMULT_WINDOW_SIZE) No multiplies the points inside the loop! I warn, multiplication points is very expensive, more expensive than the slowest addition points. Shouldn't use it at all in multi-million integration cycles. You must calculate all possible displacement points before the start of the cycle. Then just add them, being inside cycle. I think you are using a mask https://bitcointalk.org/index.php?topic=5166284.msg52068840#msg52068840 ..so you can’t store several million pre-calculated points in memory. it explains your choice. Quote x = PRF(X) not mask, i see,.. then simple, u tried built classic pattern of a*b+c= 1 << (X % m) ... ec_point_mul_and_add(r,a,n) Quote ..rewritten the following functions.. I tell you - take loop from break_short as it is (with standart functions), rewrite to kangaroos, and benchmark it.if after you still want to rewrite what, then ok (but i think what not) I think the "secret sauce" will not create, it will turn out an exotic slow implementation through multiplication. I would like to be mistaken, but my experience says that you lose time. ..How do I know about multiplication?.. I checked it myself,.. and from the topic about why brainflayer is slow and why it cannot be done faster,.. and it was on one of the topics pages LBC. This is not the most famous fact, it is not surprising that you did not know about it, no fault. Its not random, not brainflayer, its pseudo random walk, so we can pre-compute our jumps size (offset points) for using addition points instead multiplication points. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 10, 2019, 09:20:51 PM Thanks for all your input. We are reading it over carefully to see what we can use in our project and will get back to you.
We have already rewritten the following functions to make them as fast as possible: static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn) SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigned int overflow) static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) We are working on rewriting: static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) Our internal function Code: #define ec_point_mul_and_add(r,a,n) We heavily rely on and use the following observation to inform our parameter choices: Code: If the PRF is defined as follows: Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Telariust on September 14, 2019, 08:34:32 PM static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn) .. why the name of this function is not familiar to me? (although I used multiplication) .. and why I myself didn’t feel the need to write a*b+c ?..... #define ec_point_mul_and_add(r,a,n) { i looked at my source code - always use // R = na*A + ng*G // secp256k1_ecmult(*ctx, gej *r, const gej *a, const scalar *na, const scalar *ng); Quote 1899. Mr. Deull's most famous attributed utterance is that "everything that can be invented has been invented." I bet your experiments with ECMULT_WINDOW_SIZE didn’t give anything, because secp256k1_ecmult_gen() doesn’t use it :DI used exactly secp256k1_ecmult() because it is accelerated in ECMULT_WINDOW_SIZE. moreover, secp256k1_ecmult() uses endomorphism to accelerate multiplication (but only if you use both na*A+ng*G, not one of them) also why _ecmult() more faster than _gen() https://github.com/bitcoin-core/secp256k1/pull/41 https://github.com/bitcoin-core/secp256k1/pull/210#issuecomment-96145070 https://github.com/bitcoin-core/secp256k1/pull/210#issuecomment-96166989 simple init for secp256k1_ecmult() Code: //secp256k1_context *ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE); ################# I was interested to compare these functions. 1core i7-6820 secp256k1 (now, without endomorphism) Code: make clean default ECMULT_WINDOW_SIZE = 15 ######## Test#1, multiplication, increment sequential points, calculation 1million pubkeys in loop: Code: for(uint64_t i = 1; i<1000000 ; ++i){results of benchmark Code: //// Multiply: R = q*A (in constant-time) constant-time? hoho) Code: //// Multiply: R = a*G (with the generator) .. against timing attacks? y, its need rewrite, its right. Code: //// R = na*A + ng*G same function, another Code: //// R = na*A + ng*G now u can see, how efficiency working ECMULT_WINDOW_SIZE (because we calculation sequential points) secp256k1_ecmult() (option "0*P0 + K*G") - best choice (x7.5 faster than secp256k1_ecmult_gen() for multiply sequential points) ######## Test#2, multiplication, pseudo random points, calculation 1million pubkeys in loop: Code: for(uint64_t i = 1; i<1000000 ; ++i){results of benchmark Code: secp256k1_ecmult_const(&TestGej, &secp256k1_ge_const_g, &scalarK, 256); same Code: secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &TestGej, &scalarK); same Code: secp256k1_ecmult(&ctx->ecmult_ctx, &TestGej, &secp256k1_gej_const_g, &scalarK, &scalar0); // k*G + 0*G diff! slower same function, another Code: secp256k1_ecmult(&ctx->ecmult_ctx, &TestGej, &point_0gej, &scalar0, &scalarK); // 0*P0 + k*G diff! slower efficiency lower, ECMULT_WINDOW_SIZE working is not so good (because we calculation pseudo random points) secp256k1_ecmult() with "0*P0 + K*G" - best choice (x2.8 faster than secp256k1_ecmult_gen() for multiply pseudo random points) ######## Quote from: Telariust ..multiplication points is very expensive, more expensive than the slowest addition points. Test#3, addition points, calculation 1million pubkeys in loop: Code: for(uint64_t i = 1; i<1000000 ; ++i){results of benchmark Code: secp256k1_gej_add_ge(&TestGej, &TestGej, &secp256k1_ge_const_g); Code: secp256k1_gej_add_ge_var(&TestGej, &TestGej, &secp256k1_ge_const_g, NULL); 3,5Mk/s, Karl! Code: secp256k1_gej_double_var(&TestGej, &TestGej, NULL); (its double, rarely used) secp256k1_gej_add_ge_var() - best choice (x33.3 faster than secp256k1_ecmult(), x92.9 faster than secp256k1_ecmult_gen()) https://github.com/Telariust/pollard-kangaroo-c99/blob/master/compare-test.c Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Telariust on September 16, 2019, 06:58:06 PM Quote from: Telariust it very slow for 1core C/C++ openssl/secp256k1, it should be more! talk less, work more... my C99 prototype ready!everything is exactly as I described above 1core i7-6820, win7x64 // MODE: J + A -> J, xJ->xA ; 0.23Mk/s; secp256k1_gej_add_ge_var(), convert only X jacobian to affine Code: C:\cygwin64\home\User\pollard-kangaroo>pollard-kangaroo.exe // MODE: 1*J+k*G->J, xJ->xA ; 0.09Mk/s; secp256k1_ecmult(), convert only X jacobian to affine Code: --> [0y 0m 0d 00:00:16s] [0.09Mk/s] [0y 0m 0d 00:00:27s] // MODE: k*G->J, J+J->J, xJ->xA; 0.03Mk/s; secp256k1_ecmult_gen() + secp256k1_gej_add_var() , convert only X jacobian to affine Code: --> [0y 0m 0d 00:00:48s] [0.03Mk/s] [0y 0m 0d 00:01:19s] ################# Quote from: BurtW Quote from: Telariust so as not to create possible problems for you, I will publish the source code only after you. We are doing this to learn. It would be no problem for us if you publish your source code. We already have the published python source code and have looked at it in order to improve our program. You do not need to wait for us to publish. The science fair is not until next year so we have a lot of time to get everything just right and then move the code on to a GPU.github.com/Telariust/pollard-kangaroo-c99/releases/ Enjoy! ;D ################# Quote from: Telariust At this time, I will try to write addition in affine coordinates, which is the fastest way, +30% expected speed-up. Quote from: Telariust in ideal - need write new functions: A+A->A (1I, 2M, 1S) - best choice, because in the end we need X in affine for unique representation each point to adding in storage hashtable.. after which do not need to spend 8M,3S, only nearly 20M to each 1I, it +35% speed-up Affinity A + A-> A ready. Real growth was about 6-8% (probably 20M per 1I from the article is overpriced) runing test, task is 50 1core i7-6820, win7x64 Code: [pow2bits] 2^50 [algo#1] J + A -> J, xJ->xA ; secp256k1_gej_add_ge_var() Code: --> [0y 0m 0d 00:09:16s] [0.27Mk/s] [0y 0m 0d 00:00:00s] [algo#0] A + A -> A, xA ready ; the fastest! Code: --> [0y 0m 0d 00:08:42s] [0.29Mk/s] [0y 0m 0d 00:00:00s] runtime: 556/522 = x0.065 (+6,5%) hashrate: 0.29/0.27 = x0.074 (+7,4%) miserable improvement, less statistical error... certainly better than nothing; but checked the hypothesis A+A->A; Short compare algoritms: 1core i7-6820, win7x64 Code: // 0: A + A -> A, xA ready ; 0.291Mk/s; the fastest ready-made, if someone needs it. Affine points addition, custom functions, C99, bitcoin-core/secp256k1 2A -> A (1I, 2M, 2S) A + A -> A (1I, 2M, 1S) Code: // 2A -> A (1I, 2M, 2S) From https://www.nayuki.io/page/elliptic-curve-point-addition-in-projective-coordinates ################# Quote from: Telariust Quote from: 57fe ..Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code.. ..because this is the limit of computation on the cpuver0.1 C99, win7x64, algo A+A->A 1core i7-6820 0.291Mk/s 1core i5-2540 0.219Mk/s ver0.9 python37x64+gmpy2, win7x64, algo A+A->A 1core i7-6820 174.3K j/s; 1core i5-2540 99.7K j/s; Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 16, 2019, 10:47:22 PM Thanks for all of your help! We have been very carefully implementing all the best suggestions. The latest test results using my laptop computer are as follows.
Average h/s over all runs from test 0 through test 49: 80,028 Max h/s reached was: 194,547 We have updated the run results in the OP. Code: test hps Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: brainless on September 17, 2019, 06:05:16 AM Telariust, Could you do us a favor and run our version of the secp256k1_ecmult_gen function through your same benchmarks and let us know what you get? This way we can compare apples to apples on hop rates. Code: static inline void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn) Test#2, multiplication, pseudo random points, calculation 1million pubkeys in loop: Code: for(uint64_t i = 1; i<1000000 ; ++i){origin secp256k1_ecmult_gen() 1M at 26sec 699msec; 0.037 Mk/s custom BurtW secp256k1_ecmult_gen() 1M at 22sec 498msec; 0.044 Mk/s my processor 13-6100 ddr4 8gb tel-kangro-0.83 speed [~] 384.0K j/s; 14.1Mj 0.0%; dp/kgr=0.0; [ 0d 00:00:36s lost_TIME_left 750y 6m 8d 07:20:44s ] Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 17, 2019, 12:37:39 PM We have a new record for our little program: 57 bit private key in 1.73 hours averaging 153,791 hops per second using only 310,784 bytes of dynamically allocated memory. We still have not yet implemented all of the great ideas in this thread that will improve the hop rate and implementation/algorithm.
Code: ver = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available so as not to create possible problems for you, I will publish the source code only after you. We are doing this to learn. It would be no problem for us if you publish your source code. We already have the published python source code and have looked at it in order to improve our program. You do not need to wait for us to publish. The science fair is not until next year so we have a lot of time to get everything just right and then move the code on to a GPU.At this time, I will try to write addition in affine coordinates, which is the fastest way, +30% expected speed-up. Statistics from our most recent run: Code: test time hps hops compares mem(bytes) total time Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on September 17, 2019, 06:43:41 PM I mentioned that there is no need to compare T and W lists at every hop because comparing lists is time consuming. You may insert an if ( hops % cycle ==0) { compare ...} where cycle can be 100 000 or even 1 000 000 especially for higher cases. for example, case 56 , you have 957 628 504 hops and 885 620 875 compares, take cycle=1 000 000, I am pretty sure that timing will be down to 15 min. In other words, you don't need to check for collisions at every hop ::) Three points: 1) Our code is very different from the published python code with many modification for speed and to get it ready to move to a GPU. We do not do list comparisons like the python code does. 2) The number we are displaying is the actual total number of point to point comparisons and is not the same as the number of list comparisons in the python code. 3) To get an equivalent number from the python code that uses the list compare function you would have to count up the actual number of point to point comparisons that are hidden down in the list comparison function. OK 1) Our code is very different from the published python code with many modification for speed and to get it ready to move to a GPU. We do not do list comparisons like the python code does. >>> Pollard-kangaroo is Pollard-kangaroo as far as I know 2) The number we are displaying is the actual total number of point to point comparisons and is not the same as the number of list comparisons in the python code. >>> up to case 63, the lists are quite small in size (rarely more than 200), so brute force point to point is around 200x200 = 40000 still small. 3) To get an equivalent number from the python code that uses the list compare function you would have to count up the actual number of point to point comparisons that are hidden down in the list comparison function. >>> I did count, the number of hops is around 20 times bigger that point to point comparison in case 63. But why is yours so slow as compared to the simple python code ? Code: Case # time (sec) whatever your code is (which we have not seen as yet :)), basically at some point you are comparing, all what I'm suggesting to you is to try defer comparing as much as possible. Thanks. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: dextronomous on September 19, 2019, 12:02:26 AM Hey guys, especially Telariust, Racminer, BurtW,
really impressed by you'r calculation skills, math skills. Who's going to release the exe file first, reading he want's to wait you'r release first, then again, could you guys ellaborate a bit on when this might or will happen thanks in advance, will be waiting for the software. What to do in the meantime, can't do nothing then. Learn some python then. ??? just almost forgetting another question, when is the tested gpu version there for us readers to review. cheers Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on September 23, 2019, 11:07:58 AM #105 found !
Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: ZafotheNinja on September 25, 2019, 03:12:34 AM This seems like a noobish question but, with the scp256k1 curve, what is the formula for calculating the Galois field?
The bitcoin wiki gives the paramaters for the curve, but I haven't been able to find a formula for how the parameters interact. Any extra reading materials would also be helpful. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 25, 2019, 12:47:43 PM This seems like a noobish question but, with the secp256k1 curve, what is the formula for calculating the Galois field? Not sure exactly what you are asking here. First of all the points on the elliptical curve for a group, not a field.The bitcoin wiki gives the parameters for the curve, but I haven't been able to find a formula for how the parameters interact. Any extra reading materials would also be helpful. Here is a pretty good primer on the defined addition operation for the group. https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3 Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: pooya87 on September 27, 2019, 07:02:14 AM What I'm trying to figure out is, how to express this point addition/multiplication in algebraic terms. did you look at the pictures in that article with the curves and the lines? if you haven't first do that and then come back and read on. mainly this: https://hackernoon.com/hn-images/1*dErGh_rL2ExM6AX-Rtyb7w.png the point addition is basically defined as drawing a line between the two points, finding the third point (there is always a third point "intersection" when the other 2 points are on the curve) on the curve and negating that. we call the point without a name S on this picture, and first have to find S then find R from that. first a line between the two points and find the "formula" for that line. since the line is straight the formula is y = mx + a where m is the slope also known as λ. λ = (yq-yp)/(xq-xp) and y = yp + λ(x-xp) is that formula using point P (we can use any of the other 3 points too). if we put it in the elliptic curve formula (y2 = x3 + ax + b) we get: x3 − λ2x2 + a+2λ2xp −2λypx + (b−(λxp−yp)2) = 0 we know thanks to Vieta that in a quadratic equation (https://en.wikipedia.org/wiki/Quadratic_equation#Vieta's_formulas) ax3 + bx2 + cx + d =0 that the sum of roots r1, r2 and r3 is equal to -b/a so in our case sum of three values for x which are the coordinates of the 3 points on the straight line is equal to -(-λ2/1)= λ2 hence we can calculate the x coordinate of point S: xp+xq+xs=λ2 => xs=λ2−xp−xq. and since xs=xr we have found the x coordinate of our point R which is here: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition to find its y coordinate of S we simply use the line's formula and since yr=-ys we just have to flip the sign hence the yr formula in wikipedia link 2 additional things to note: 1. point doubling aka adding a point to itself is the same math with only one difference: x and y coordinate of P and Q are the same. 2. all the math here is modular (mod curve's prime) Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on September 27, 2019, 11:21:56 AM Ah, thanks for the link, it definitely helped clear a few things up. I understand the formula y^2 = x^3+7 generates the secp256k1 curve, and that bitcoin specifies a point on that curve as a generator/base point. As far as I've found, this base point is added with itself x times, where x is your private key, to get the public key. What I'm trying to figure out is, how to express this point addition/multiplication in algebraic terms. Thanks pooya87 for your very detailed answer. Also, if you like to look at code instead of mathematical equations we just wrote the code for point addition using the secp256k1 library and posted it. Here is that post repeated here. You can read through the code and see that this code implements exactly the mathematical equations that pooya87 detailed in their post. We have our first pass of our A+A->A implementation which we did from scratch using only the wikipedia page for the formula. It runs and is faster but we have not finish optimizing it - we just got through the bugs and got it to run. Since Telariust shared his implementation we will share ours. I am very surprised this function is not already a standard function in the secp256k1 library. We are still running tests and optimizing our entire system. I will post the results in the OP when the runs finish and we will see how much faster it is in our implementation. Code: static void secp256k1_add_ge_var(secp256k1_ge * const r, const secp256k1_ge * const P, const secp256k1_ge * const Q) NOTE: fixed a couple of minor bugs in the above code. It should be good to go now. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: usama12 on September 29, 2019, 07:05:50 AM Hi BurtW I have gone through whole thread and its very interesting and informative. I am interested to get listed on your list of testers.
Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: MrFreeDragon on October 01, 2019, 11:01:05 AM In the case of the puzzle transactions a publickey should be in the space 2^(bit-1) to (2^bit)-1, we can just calculate 2^(bit-1) + 2^(bit-2) as a point and subtract it from our known publickey. Our new generated public key will be within the space(ORDER - 2^(bit-2)) to 2 ^(bit-2). Now we only have to check the x values from space 0 to 2^(bit-2). When we find the solution to the calculated publickey, the solution to our orginal publickey will be either solution or (ORDER - solution) + subtraction factor. Can you please clarify there is the benefit in your method? You are saying that "Now we only have to check the x values from space 0 to 2^(bit-2)", so we need to check 2^(bit-2) combinations. It is just 2 times less that the brutforce of the full range. Not effective. However in Pollard method we should make only sqr (2^(bit-1)) operations, which is much much less than in your method. Example: for 110 bit key, you suggest to check 2^108 combinations, but in Pollard method we need only 2^54.5 operations. So why is your method valuable? What is the main idea and advantage? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 01, 2019, 01:52:38 PM Can you please clarify there is the benefit in your method? You are saying that "Now we only have to check the x values from space 0 to 2^(bit-2)", so we need to check 2^(bit-2) combinations. It is just 2 times less that the brutforce of the full range. Not effective. However in Pollard method we should make only sqr (2^(bit-1)) operations, which is much much less than in your method. Example: for 110 bit key, you suggest to check 2^108 combinations, but in Pollard method we need only 2^54.5 operations. So why is your method valuable? What is the main idea and advantage? The idea is of course to only make sqr(2^(bit-2)) operations. for #50: python pollard-kangaroo-multi.py 50 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6 should be equivalent to python pollard-kangaroo-multi.py 8:FFFFFFFFFFFF 02bc9d041a4839d3bef61e319cd02d3b177292ccb79ed27c1bf6043ab0ec635bfd (8 is by default minimum bit using pollard-kangaroo-multi.py) edit: sorry was the wrong pubkey for #50 in first place Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 01, 2019, 02:48:36 PM need detail explain for this area example to test: from #50 = 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6 to 0-48 02bc9d041a4839d3bef61e319cd02d3b177292ccb79ed27c1bf6043ab0ec635bfd steps guide 1. Create ECPoint "p" from 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6 2. Calculate subtraction space "sub"= (2^(bit-1)) + (2^(bit-2)); 3. Create ECPoint from sub "subP" = G.Multiply(sub); 4. Create ECPoint new "newP" = p.Subtract(subP); 5. Create compressed publicKey string "newPK" = newP.GetEncoded(True).ToString(); 6. Calculate your "newkeySpaceU" value = (2^(bit-2))-1 7. Convert newkeySpaceU from decimal to hexadecimal string= newKeySpace.ToString("X"); 8. Use pollard-kangaroo-multi.py 8:newkeySpaceU newPubkey (Correctly keySpace L should be always 0, by default 8 is minimum) 9. Convert your result prvkey output from hexadecimal to BigInteger "res" 10.Calculate "offset1" = res + sub and calculate "offset2" = ((Order -res) + sub)%Order 11. Generate new ECPOINT "offset1P" and "offset2P" = G.Multiply(offset1) and G.Multiply(offset2) 12. Compare "offset1P" to "p" = if(p.Equals(offset1P)) offset1 is my prvkey; else offset2 is my privkey Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 01, 2019, 07:59:47 PM sending you PM, your need allow my id for send PM to you Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 01, 2019, 09:52:11 PM Here is another example of #40
#40 sqr(2^(bit-1)) python pollard-kangaroo-multi.py 40 //privkey = 1003651412950 #40 sqr(2^(bit-2)) python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399 //privkey = 179017692118 Addfactor: 824633720832 //result1 = 1003651412950 true Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on October 01, 2019, 10:35:57 PM ----------------------------------------------------------------- Very nice work. I've tried your C code and it hops two times faster than 57fe python code. I can't figure out where exactly do you store the tame and wild kangaroos as it is done in the "tame.txt" and "wild.txt" files for the python code. thanks for your help Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: MrFreeDragon on October 02, 2019, 12:12:22 AM Here is another example of #40 #40 sqr(2^(bit-1)) python pollard-kangaroo-multi.py 40 //privkey = 1003651412950 #40 sqr(2^(bit-2)) python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399 //privkey = 179017692118 Addfactor: 824633720832 //result1 = 1003651412950 true This method is not universal. It depends on the 2nd bit actually 8) So, for #40 it works. But for #35 for example it will not work. For #50 it will not work as well. First bit is always 1 in these transaction chalange keys. But the 2nd bit could be 1 or 0 (as any other bit). You decrease the bit power considering that the 2nd bit is 1, but it is not obligitary. It also could be 0. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on October 02, 2019, 12:34:20 AM Here is another example of #40 #40 sqr(2^(bit-1)) python pollard-kangaroo-multi.py 40 //privkey = 1003651412950 #40 sqr(2^(bit-2)) python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399 //privkey = 179017692118 Addfactor: 824633720832 //result1 = 1003651412950 true 824633720832 is just 0xC000000000 179017692118 is 0x29AE4933D6 1003651412950 is 0xE9AE4933D6 So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point. You are not doing less work, you've just changed the origin. Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: MrFreeDragon on October 02, 2019, 12:47:19 AM Here is another example of #40 #40 sqr(2^(bit-1)) python pollard-kangaroo-multi.py 40 //privkey = 1003651412950 #40 sqr(2^(bit-2)) python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399 //privkey = 179017692118 Addfactor: 824633720832 //result1 = 1003651412950 true 824633720832 is just 0xC000000000 179017692118 is 0x29AE4933D6 1003651412950 is 0xE9AE4933D6 So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point. You are not doing less work, you've just changed the origin. Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo. Absolutely! In general terms, it could be explaind like this: for bit key the range is from 2^(bit-1) up to 2^(bit)-1, where the total number of combinations (range length) is 2^(bit-1). 2^(bit-2) is a half of 2^(bit-1), so 2^(bit-1) + 2^(bit-2) is 1.5 * 2^(bit-1) --> the absolute middle of the total range for the (bit) key. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 02, 2019, 01:08:23 AM Here is another example of #40 #40 sqr(2^(bit-1)) python pollard-kangaroo-multi.py 40 //privkey = 1003651412950 #40 sqr(2^(bit-2)) python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399 //privkey = 179017692118 Addfactor: 824633720832 //result1 = 1003651412950 true 824633720832 is just 0xC000000000 179017692118 is 0x29AE4933D6 1003651412950 is 0xE9AE4933D6 So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point. You are not doing less work, you've just changed the origin. Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo. Exactly that was the plan > wraping the space W with the middle of the space to point infinity. So that actually all x values get halfed. I thought possibly that when a wild kangaroo jumps, a jump from the tame kangaroo in the negative space in the different direction could also lead to the same result in less time(cause it would be the same distance). The key is definitely to find in the space(bit-2), however if you say regarding the kangaroo method, that there is no speed gain, the method is useless. i have to test #35. i would not understand if the key is not findable. like #50 if the key is on the negative side it will find the privatekey and publickey on the positiv side,there will be just no publickey match> Watch it in the console im not sure if gets to the result.txt Thanks for testing! Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 03, 2019, 12:06:15 AM I deleted my posts to avoid any confusions.
Now i better understand how kangaroo jumping works, i didn't even know that it is possible to find a publickey which is not in the space we are searching for. That's why it finds the publickey when you just change Y. I thought that when a tame kangaroo jumps out of space, a new tame and wild kangaroo would be set within the space to start jumping again. As my suggestion, it would be the same if you just set the searchspace for from 2^(bit-1) > (2^(bit)-1) to (2^(bit-1) + 2^(bit-2)) > (2(bit)-1). You would have a 50% chance to find the key in sqr(2^(bit-2)). In my tests it must have been luck to find the keys not in that 50%chance in less time than average. The only benefit i see by pushing the space with the middle to Infinity point, would be if a X value match could be detected when a wildkangaroo starts in negative mirrored space. That would possible be a rarely case by the time it catches up to the positive space where all tame kangaroos would start. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: brainless on October 03, 2019, 06:25:26 AM I deleted my posts to avoid any confusions. Now i better understand how kangaroo jumping works, i didn't even know that it is possible to find a publickey which is not in the space we are searching for. That's why it finds the publickey when you just change Y. I thought that when a tame kangaroo jumps out of space, a new tame and wild kangaroo would be set within the space to start jumping again. As my suggestion, it would be the same if you just set the searchspace for from 2^(bit-1) > (2(bit)-1) to (2^(bit-1) + 2^(bit-2)) > (2(bit)-1). You would have a 50% chance to find the key in sqr(2^(bit-2)). In my tests it must have been luck to find the keys not in that 50%chance in less time than average. The only benefit i see by pushing the space with the middle to Infinity point, would be if a X value match could be detected when a wildkangaroo starts in negative mirrored space. That would possible be a rarely case by the time it catches up to the positive space where all tame kangaroos would start. i sent you PM, 2 time in last 2 days, have some time for reply Looking Farword Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 03, 2019, 07:01:45 AM i sent you PM, 2 time in last 2 days, have some time for reply seems like you need to change your settings too Looking Farword Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: brainless on October 07, 2019, 06:39:56 PM hi
in script, there is bug, or maybe he unable to catch point, as if you have 37 bit pubkey and you command is ./script 40 02xxxxxxpublickey 40 bit mean search in bit range but script will find key in 37 bit if you have 42 bit key, and same command for search in 40 bit by apply 40 or 8:fffff.... bit range, script will find 42 key its not restrict only for define bit range mean always find start from 8 to onword, so its take time consume, Smiley test it Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 07, 2019, 10:05:46 PM hi in script, there is bug, or maybe he unable to catch point, as if you have 37 bit pubkey and you command is ./script 40 02xxxxxxpublickey 40 bit mean search in bit range but script will find key in 37 bit if you have 42 bit key, and same command for search in 40 bit by apply 40 or 8:fffff.... bit range, script will find 42 key its not restrict only for define bit range mean always find start from 8 to onword, so its take time consume, Smiley test it Yes, this was my point. I first thought that there is a parallel behaviour, cause the script was finding the publickey when changing y value only, and we could use it to only make sqr(2^(bit-2)) operations, unitil i found a completely different pubkey from another space. You don't have to set from 8:... bitspace it also works with orginal keyspace It's not a bug i guess...i am cleary not an expert in this matter :P, but that's what i think: It seems logical, it will just take longer on average to find the key. The average jumpsize should be calculated from the searchspace. When you search for exampe puplic key from 37 bit within 40 bit the average jumpsize should be bigger and the opposite when searching 43bit pubkey within 40 bit. It's strange, that when you change only the y value of the key, you will find the orginal publickey with privatekey, but not the one you changed. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Telariust on October 09, 2019, 04:05:30 AM Quote from: racminer ..where exactly do you store the tame and wild kangaroos as it is done in the "tame.txt" and "wild.txt" files for the python code.. in hashtableok, i will add output to file distinguished points in next release. there is only one practical use for saving points to disk - distributed enumeration on different devices without a pool. I myself plan to do so, since writing a pool is much more difficult than collecting a save once a day. Quote from: st0ffl The idea is of course to only make sqr(2^(bit-2)) operations. x2 speed-up, nice idea, i will add as option of boost in next releaseQuote from: racminer The Hash table is only 1024 entries, is it enough for cases like #110 ? the formula calculates a number of points about 10 pieces per kangaroo for 100% of the lead time, taking into account the size of the range.Now the overflow of the table will occur with a probability of 50% if launched on 96 cores or more. It needs to be fixed. I understand that -t is the number of threads. 1) Algo of Pollard is probablistic nature (Birthday Paradox, Kruskal's card trick, etc)The question is why the speed increases, but time does not decrease, more often it even increases. The solution time is not stable; several attempts (timeit loop in python script) are needed to obtain the avg runtime and jumps. heuristic time rather than deterministic 2) threads should run at equal speed. If input -t N over than really N cores, so threads will compete, some will be faster and some will be left behind. 3) maybe my code have bug, need more tests ################# post dedicated cuda/opencl implementations we have some ways for just ready GPU implement good candidates to rewrite: 1) cuda, c++, VanitySearch, by Jean_Luc https://github.com/JeanLucPons/VanitySearch 2) cuda/opencl, c++, BitCrack, by brichard19 https://github.com/brichard19/BitCrack 2) cuda, python, pollard-rho, by brichard19 https://github.com/brichard19/ecdl 3) cuda, ?, pollard-rho github.com/beranm14/pollard_rho/ 4) opencl, C#, pollard-rho github.com/twjvdhorst/Parallel-Pollard-Rho/ I intend to evaluate their performance, as well as rewrite one or more to kangaroo. ################# multicore, CPU only, c++, based on engine VanitySearch1.15 https://github.com/Telariust/vs-kangaroo/releases bignum lib by Jean_Luc is good, only %15 slower than bitcoin-core/secp256k1 lib (with raw asm mult) Code: C:\Users\User\source\repos\VanitySearch-1.15_kangaroo\x64\Rel_SM52>vs-kangaroo -v 1 -t 4 -bits 42 ################# BitCrack runs at about 715 MKeys/s on Tesla V100 - look here (https://bitcointalk.org/index.php?topic=4453897.msg49793258#msg49793258). notIf we remove hash160, the rate would be 1430 Mj/s. Mj here stands for million kangaroo jumps. BitCrack use batch packet inversion (x8 speed-up). We cant(OR CAN?..) use its in kangaroo method, so 1430/8 = 175M j/s but on screen https://imgur.com/a/f3zTmTa see 4xV100=6515M j/s, each 1600M j/snow unclear.. ################# https://bitcointalk.org/index.php?topic=1306983.msg48224432#msg48224432 November 25, 2018 this man speaks as if he already has a finished implementation. https://imgur.com/a/f3zTmTa O great master, j2002ba2, I urge you! :) Plz, come and explain to the miserable mortals, which means s2,s1,m3,m4 in your program! ################# https://docs.nvidia.com/cuda/volta-tuning-guide/index.html he high-priority recommendations from those guides are as follows: - Find ways to parallelize sequential code; - Minimize data transfers between the host and the device; - Adjust kernel launch configuration to maximize device utilization; - Ensure global memory accesses are coalesced; - Minimize redundant accesses to global memory whenever possible; - Avoid long sequences of diverged execution by threads within the same warp; about last, " - Avoid long sequences of diverged execution by threads within the same warp;" parallelism algo by Pollard (U+V) escape problem of collisions between kangaroos of the same herd; this allows you to completely abandon the correction block because adding IF () inevitably breaks the parallelism of the GPU; ################# to be continued.. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: croxNN on October 09, 2019, 04:16:22 AM Telariust, there is nothing in Source Code, only README.md
Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: PrivatePerson on October 09, 2019, 09:48:02 AM -t 4 -bits 55 1.0M j/s [runtime] 00:04:01
-t 16 -bits 55 3.2M j/s [runtime] 00:04:33 ??? Code: PS D:\btc\vs-kangaroo-0.01> ./vs-kangaroo_0.01.exe -v 1 -t 4 -bits 55 Code: PS D:\btc\vs-kangaroo-0.01> ./vs-kangaroo_0.01.exe -v 1 -t 16 -bits 55 Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on October 09, 2019, 10:42:22 PM Quote from: racminer ..where exactly do you store the tame and wild kangaroos as it is done in the "tame.txt" and "wild.txt" files for the python code.. in hashtableok, i will add output to file distinguished points in next release Thanks for your answer and all your answers. The Hash table is only 1024 entries, is it enough for cases like #110 ? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on October 10, 2019, 12:51:41 AM -t 4 -bits 55 1.0M j/s [runtime] 00:04:01 -t 16 -bits 55 3.2M j/s [runtime] 00:04:33 ??? why are you ??? ? scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor :) ) and # of threads per core (which is one or two) -t is generally equal to core number ... on some cpu's you might get better performance for -t equal to 2 x core number. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: PrivatePerson on October 10, 2019, 04:26:40 AM why are you ??? ? scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor :) ) and # of threads per core (which is one or two) -t is generally equal to core number ... on some cpu's you might get better performance for -t equal to 2 x core number. This is Ryzen 7 2700 (8 cores 16 threads) I understand that -t is the number of threads. The question is why the speed increases, but time does not decrease, more often it even increases. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on October 10, 2019, 11:07:35 AM why are you ??? ? scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor :) ) and # of threads per core (which is one or two) -t is generally equal to core number ... on some cpu's you might get better performance for -t equal to 2 x core number. This is Ryzen 7 2700 (8 cores 16 threads) I understand that -t is the number of threads. The question is why the speed increases, but time does not decrease, more often it even increases. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on October 10, 2019, 11:12:58 AM ################# BurtW, maybe I'm too active here, if you don’t like it, then you can ask me to leave and create a separate topic. ################# No problem. We enjoy your informative posts and have used several of your ideas in our program. Right now I am very busy with work and my daughter is very busy in school so we have not had time to work on the program. We will get back to our version when things slow down a bit. BTW we keep all our points in memory in a hash table also. Disk access is a no no, especially when we are targeting a GPU (eventually). Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: MrFreeDragon on October 10, 2019, 11:56:53 AM BTW we keep all our points in memory in a hash table also. Disk access is a no no, especially when we are targeting a GPU (eventually). Can you explain why don't you keep the points on disk, and keep them only in memory? And also please tell which point you keep - every point, or just some multipliers of predefined number (let's say 10^10)? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: st0ffl on October 10, 2019, 12:44:36 PM Quote from: st0ffl The idea is of course to only make sqr(2^(bit-2)) operations. nice idea, i will add as option of boost in next releaseThank's Telariust! It will take time but i could try to implement the kangaroo method myself in c#, to learn if it would be possible to detect a parallelism for the average usage of sqr(2^(bit-2)) operations, when halfing x values of the searchspace, unless you can confirm from your experience that there is no such behaviour detectable? Currently it's just like you would guess in a keyspace of 1024 that the privatekey is greater than 512... BUT... If it is possible to find a privatekey less than 512 in less than 150% of sqr(2^(bit-1)) it should be an average overall speedgain. My current idea to achieve that would be with the cost of an extra wild, when pushing the searchspace to point Infinity. This wild point could just be the negation point of the orginal point without or with offset. Cause i don't see ECPoint subtraction implemented in your script, you can use addition: therefore the ECPoint offset calculation to wrap the space arround Infinity should be G.Multiply(ORDER-SpaceL-(SpaceL/2)). x2 speed-up, nice idea, i will add as option of boost in next release Thank'sTitle: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: PrivatePerson on October 11, 2019, 04:18:43 AM Even with higher speeds, runtime may fluctuate a lot. In order to compare performances, you need several trials. Naturally I did a few measurements. Python scripts behaved the same way. The single-core and multi-core scripts showed approximately the same search time, although the multi-core speed was much higher. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: racminer on October 11, 2019, 01:14:58 PM Even with higher speeds, runtime may fluctuate a lot. In order to compare performances, you need several trials. Naturally I did a few measurements. Python scripts behaved the same way. The single-core and multi-core scripts showed approximately the same search time, although the multi-core speed was much higher. In this case, remains the question whether the program stops running immediately or not when one of the threads finds the solution. We need to ask the developper ??? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: brainless on October 20, 2019, 01:09:13 PM Seems no more new update in kangroo subject, all waiting GPu ver, but developer have it, and he maybe waiting to find 110 puzzle, but till no news in updates and upgrades in kaangroo
anyway any modification for multiple pubkey find in range space at once, by input file (multiple pubkey) ??? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: MrFreeDragon on October 21, 2019, 01:30:18 AM Did anybody make the analysis for the right DP_rarity? (in phyton code the "points" reconciliation is made only for X-coordinate multiple of DP_rariry: if P.x % DP_rarity == 0)
If we select very small DP_rarity, so many points will be saved, and wee need more memory/disk space. If we select very high DP_rarirty, so most of jump points will be missed, and the meeting point of wild and tame kagaroos could be missed as well. What is the most effctive value of DP_rarity? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: brainless on October 23, 2019, 08:26:33 PM Dear dev's
can you post script (python or c ) where multiple publickeys checking in kangroo bit range, (by reading pubkeys file i.e pubkeys.txt) same as implemented in brainflayer, like bloomfilter check bitcrack, vanitysearch, etc yes its reduce speed but 10%, but if publickeys are in 100 or 200, it will not effect love to see multiple pubkeys like bloom filter or else check in table, in bit range. hope you could manage it too Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: dextronomous on October 26, 2019, 11:56:43 PM this thread not posting nada, niet, nothing,
23-10-2019 08:26:33 PMPosted by: brainless but the posters are the best. serious hard work and nice work. but no BurtW software as of yet released, just test result i guessed. so guys let some of you be heard we wan't it to. greetings. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: supika on October 28, 2019, 09:02:24 AM this thread not posting nada, niet, nothing, 23-10-2019 08:26:33 PMPosted by: brainless but the posters are the best. serious hard work and nice work. but no BurtW software as of yet released, just test result i guessed. so guys let some of you be heard we wan't it to. greetings. Something new will appear in one month aprox, after they will find 110 puzzle. After that they will need something new because kangaroo will not find 115 in a reasonable time. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: brainless on November 06, 2019, 09:19:06 PM Hi all dev
seems you all only gone busy for your interest, its good, board in empty, no new updates, no new developmentsm, no new news, no sharing, etc comunity wish you join back, and update, post your new work , idea's, etc Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: bounty0z on November 26, 2019, 05:03:51 PM Hello,
any one here please can explain to me what mean by Wild and Tame ? , I know that they are hops of kangaroo, but how can I use them. for example I want to know if i run pollard for #105 and get a Wild hop, but I shutdown the pollar code .. I don't want to start from the beginning so how can I import the Wild that I find in first ? ,and the same for Tame. the second question is, what is tame and wild ? they are collision ? if yes and we can import them ,so we can just everyone poste the wild and tame that he find and we will find it quicly !! Thanks Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: MrFreeDragon on November 26, 2019, 09:51:36 PM Hello, any one here please can explain to me what mean by Wild and Tame ? , I know that they are hops of kangaroo, but how can I use them. for example I want to know if i run pollard for #105 and get a Wild hop, but I shutdown the pollar code .. I don't want to start from the beginning so how can I import the Wild that I find in first ? ,and the same for Tame. the second question is, what is tame and wild ? they are collision ? if yes and we can import them, so we can just everyone poste the wild and tame that he find and we will find it quicly !! Thanks In general, tame kangaroos are jumping "in the area" of private keys, and wild kangaroos are jumping "in the area" of public keys. If k is the private key, so public key for it will be Q = k*G, where G is basis point. Now, tame kangaroos are jumping in the area of private key (number), but wild kangaroos are jumping from the point Q (public key). There is a rule in ECDSA group addition: if we add some number to private key, the result will be the sum of the public keys, i.e. public key of the number (k + j) is (k+j) * G = k*G + j*G. So you can calculate the public of the jump step, add to public key of the private key to be found and receive the resulting point. The collision is the exact one point where tame and wild kangaroos are met. In order to import all your jumps to continue, you should save the tables of their jumps (and later use them again). Small example: Imagine you want to find the private key for the public key Q 02ed3bace23c5e17652e174c835fb72bf53ee306b3406a26890221b4cef7500f88 [1] This is the public key from the private number 100 (in hex 64), but you do not know this. If tame kanagroo jumped to number tame_jump = 150 (in hex 96), we receive the public key from this number equal to 031f6014569d1203ae0c128ac00a41097609b16386bde7f857b908ea95e5eebbef [2] And if wild kangaroo jumped by step wild_jump = 50, we should calculate the resulting point for wild as the addition of the known public key [1] and the public key of step 50 (in hex 32) which is 0229757774cc6f3be1d5f1774aefa8f02e50bc64404230e7a67e8fde79bd559a9a [3] So, adding point [1] (Q) and point [3] (scalar addition in bitcoin ECDSA), we receive the resulting point 031f6014569d1203ae0c128ac00a41097609b16386bde7f857b908ea95e5eebbef [4] No we see the collision: point [4] is exatcly the point [1]. Finally, while [4] equals to [2], the private key k is tame_jump - wild_jump = 150 - 50 = 100. So, as wild and tame kangaroo jumped to the same point, we could find the private key as the difference between jumps. Visually you also can imagine that all tame kangaroos are jumping with the cord - so you know the private key of every tame's location. But wild kangaroos are wild and you know only the jump step for them but do not know the private key for their location. Wild kangaroos are located just at another public point with uknown private key. As soon as wild and tame are met at the same point, you can calculate the unknown private key with the help of your "cord" connected with the tame kangaroo ;) Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: bounty0z on November 27, 2019, 10:15:18 AM Visually you also can imagine that all tame kangaroos are jumping with the cord - so you know the private key of every tame's location. But wild kangaroos are wild and you know only the jump step for them but do not know the private key for their location. Wild kangaroos are located just at another public point with uknown private key. As soon as wild and tame are met at the same point, you can calculate the unknown private key with the help of your "cord" connected with the tame kangaroo ;) + How can I upload the tame and wild into my code, because when code start he create new empty file tame and wild ? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: MrFreeDragon on December 05, 2019, 12:06:25 AM + How can I upload the tame and wild into my code, because when code start he create new empty file tame and wild ? If you can specify what kind of code do you use, it will be easier to answer your question. However as I remember there were 2 main pollard python codes in discussion - one used text files to store tame and wild, and another used memory to store them (without files). So I can guess that you use the 1st one (with files). In code you can find that in the beginning it creates (re-writes) tame and wild files. You need just comment or remove these rows from the code, like these: #open("tame.txt",'w').close() #open("wild.txt",'w').close() 'w' for only writing (an existing file with the same name will be erased) Every time you run the code, it will use the same tame and wild tables, and will continue to search (however the start locations of kangaroos will be changed, but it is not so important - anyway kangaroos are jumping in random way) Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Sadlife on December 05, 2019, 02:21:33 AM That is quite an interesting project im assuming this is still under development phase that's why, you're trying to find out the length and entropy of each BTC address are you trying to generate address as well so you check for duplicates ?
You could try this site https://www.blockcypher.com/dev/bitcoin/#documentation-structure this api has a lot of different functions including checking unconfirmed payments. You could try this out if you want more features to your project. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: dextronomous on January 07, 2020, 02:59:44 AM Happy New Year 2020 to all,
anything new under the sun regarding the project, maybe some gpu pollard. or. Burt's Surprise Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: MrFreeDragon on February 28, 2020, 12:07:25 PM ============================================================================================= Sample Private key: 1000 Information you give me If you give your private key 1000 public 1000-1 = 999 public key 1000 +1 = 1001 public key 1000 + 500 = 1500 public key 1000-500 = 500 public key If I know the public key of 999,1001,1500,500 My information Will it help me find my Bitcoin private key? https://t.me/kyscolx Of course. If you know this exact step between the known public key and target public key you will find the private for the target one. I mean if you know 1 and 500 in your example. But is these steps are just x and y - so no. And also you should know the PRIVATE key from 1000+500, 1000-500, etc, not public one. Knowing just public is not enough because public key is just an ECDSA addition of 2 points. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: Btchunter3333 on February 28, 2020, 09:18:24 PM If i have 10 PC with different cpu cores numbers, how i can setup the program to search for same private key but on different range and to run program on all PC?
PC 1 to search for 10% of private keys PC 2 for next 10% and so on and the last for last 10%? Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: brainless on April 24, 2020, 08:52:13 PM If i have 10 PC with different cpu cores numbers, how i can setup the program to search for same private key but on different range and to run program on all PC? PC 1 to search for 10% of private keys PC 2 for next 10% and so on and the last for last 10%? try now gpu version for Kangaroo https://github.com/JeanLucPons/Kangaroo Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: BurtW on July 14, 2020, 06:12:19 PM As you can probably guess my daughter lost interest in this project and she moved on to other things: competitive rock climbing, learning to fly an airplane, collecting vinyl records (!), learning to play the bass guitar in her own rock and roll band, etc. Oh to be 13 again...
Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: dextronomous on July 14, 2020, 06:13:50 PM ok great to have had you around. bye
Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: alevlaslo on October 25, 2020, 05:08:32 PM talk less, work more... my C99 prototype ready! everything is exactly as I described above 1core i7-6820, win7x64 // MODE: J + A -> J, xJ->xA ; 0.23Mk/s; secp256k1_gej_add_ge_var(), convert only X jacobian to affine Code: C:\cygwin64\home\User\pollard-kangaroo>pollard-kangaroo.exe Puzzle 32 how many time? :) https://bitcointalk.org/index.php?topic=1306983.msg55448862#msg55448862 Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: btc-room101 on April 23, 2021, 01:09:13 AM Hello, any one here please can explain to me what mean by Wild and Tame ? , I know that they are hops of kangaroo, but how can I use them. for example I want to know if i run pollard for #105 and get a Wild hop, but I shutdown the pollar code .. I don't want to start from the beginning so how can I import the Wild that I find in first ? ,and the same for Tame. the second question is, what is tame and wild ? they are collision ? if yes and we can import them ,so we can just everyone poste the wild and tame that he find and we will find it quicly !! Thanks Even the inventor John Pollard regrets this name, this tech is some 40+ years old. Originally is was called Pollards's Rho/Lamba method, where Lamda is an upside down Y The notion was that two different searches converge on a common point, leading to the end goal Then historically Pollard was reading 'national geographic' on a story about kangaroo breeding in Austrailia, and decided to call lambda-method the Kangaroo method, it is complete bullshit, there is no abstraction or moral equivalence, or equivalent thinking here Long ago, they used to call this crap baby-step/giant-step which is better, it all come out of the same people The principal IDEA of Kangaroo is they HOP, they HOP BIG ( giant step ), they hop small ( baby step ), you jump around the finite-field ( your prime space, a big number ) Originally they kept all the hop history in memory, but of course that restricted the search, think 2^256 is 10^77, which is all the electrons in the universe, impossible to find this memory So they came up with a method that didn't require lots of memory, which is this method the 'kangaroo' or 'lambda' method. Jump around the field space, and if you find a Disctinct-Point you record it in memory, and you have 100's if not 1,000's of processes doing the same, if later another process hits that special-point, then all the kangaroos follow that point. So a DP is the 'Y' where the two top lines converge to make one. Now the problem with DP is its not the real Lambda Point its just a special point, defined as you wish, sort of like mining bitcoin, where difficulty is set by the number of leading zeros on a hash, here the DP is the special point defined much the same way, its just a unique point that all processes can agree on; it doesn't mean that this is the true point of convergence, just means that its a "Point of Interest", randomly defined by humans. Under their rules. So kangaroos hop around looking for a DP in giant-hops, and if a DP is found, then they incrementally search that point forward; The problem with the Lambda method is its restricted to a tiny subspace of the field, if your doing btc which is 2^256, the jean-luc kangaroo algo only lets you choose a 2^20 field of view, so unless its a 'made up puzzle' problem in that 2^40 space, the likelyhood of solving the problem is zilch Most success in ECDLP has been in Pollard-Rho, like a '6' character you following the tail until find the point of entry into a circle, but this method requires memory storage, but this method only works on TOY problems because there is not enough memory on earth to store the history. Title: Re: Science Fair Project to trap Bitcoin private keys using Kangaroos! Post by: j2002ba2 on April 23, 2021, 09:31:14 AM Most success in ECDLP has been in Pollard-Rho, like a '6' character you following the tail until find the point of entry into a circle, but this method requires memory storage, but this method only works on TOY problems because there is not enough memory on earth to store the history. You are mistaken. Pollard Rho & Kangaroo both use the same amount of memory (the same order of magnitude). In the original rho the whole memory is only two points and two numbers mod curve order. Parallelizing multiplies the needed memory, but it still remains insignificant compared to the number of point additions. The amount of memory needed is linearly dependent on the number of parallel computations. |
