....
Begging is not allowed on this forum, I remove all such messages. Because of work, I couldn't watch it in time
Well, may be next time  A question Did you run the script continously for 5 months or at certain point you stopped and choose another point and start from there or maybe a change in code ?
Why would I stop? Any stops and changes are dangerous, you can lose progress partially or completely when you change something. Same for splitting whole range into small pieces, it increases total complexity. So I started the process, made several scripts to automate everything (it's boring to manage many GPUs and systems remotely) and paid bills for five months, it was not cheap and I had no guaranties of success, somebody else on this planet could find the key faster, or I could make an error somewhere in code or calculations and fail, and I would get exactly zero. This game is expensive. People who think that they can crack 134bits of Secp256k1 with a couple of GPUs don't live in real world. I improved the algo itself and made crazy code using almost undocumented assembler, but anyway I had to rent hundreds of GPUs for months, with "normal" software like JLP's it would take years. Out of curiosity, what K were you at when it hit?
From "5 months on 200GPUs" I get roughly K=0.25-0.34, which would mean you found it at about a quarter of the expected work. Curious whether that's close.
You are correct, K was about 0.35, I used mixed 4090 and 5090 cards. So I was lucky. Also I remember somebody asked me if I want to share DB. I don't want, it's almost 400GB (I used DP=32 but anyway I had to use PC with 1TB RAM as a server), also I would need to provide all jump tables (they are calculated slightly different than RCKangaroo does for some reasons), just don't have time for this, also it won't help much for #140 that requires x5.5 more DPs. But I provided pk for #135 so if you were searching for #135 you can convert all your DPs to tames and continue searching for #140. Happy hunting! |
|
|
|
|
Mini-puzzle #7 closed.
#135 pk is: 0000000000000000000000000000006D9392A16883F90903D5F78DA57AF07EB2
|
|
|
|
Hmm, somebody quickly solved it and did not write here the solution. It's not polite  Ok, I will explain: to be able to calculate pk you just need to know the nonce from this signature, a hint is in the message: use bitcoin genesis block data (I used merkle root for nonce). So #135 pk is: 0000000000000000000000000000006D9392A16883F90903D5F78DA57AF07EB2 Done! |
|
|
|
Congratulations! You deserve it for your dedication and effort. I'm looking forward to that mini-puzzle; it would be great to be able to solve it, as I'm going through some tough times in my country (Venezuela)!
No problem, mini-puzzle #7 is here: https://bitcointalk.org/index.php?topic=5589799 |
|
|
|
Guys, let's have some fun one more time, a mini-puzzle for puzzle #135 16RGFo6hjq9ym6Pj7N5H7L1NR1rVPJyw2v Thank you Satoshi Nakamoto! ICVZGMwpPuca4krotcpwEzTyJXBUQF+w25M2TLnFHzIiAKYS+4c6taNLaMM7ZChJ2oMPQXiuzsYDCeF9xZFBMZg= There is about 280$ in BCH there, so hurry up! PS. No BS here please, I will remove it. PPS. For history, previous mini-puzzle is here: https://bitcointalk.org/index.php?topic=5577390 |
|
|
|
"fresh jump tables" every try or how?
It means I used own set of jumps for #135, not from previous puzzles. So did you even make a profit off #135? Your post's sentiment inclines a bit toward some frustration.
Sure I got profit, but I won't do it again, no fun anymore, it was too boring to pay bills for five months  Don't worry, your code will be dissected to blood and stand as the basis of future optimizations until the dawn of secp256k1.
Yeah, feel free to improve it by x10!  The range closest to the actual key is here. Is this correct
...
Please keep all magic predictions/circles/etc away from this thread, you have a whole separate 680-pages thread for this! |
|
|
|
RCKangaroo v4.0: https://github.com/RetiredC/RCKangarooI managed to exclude inverse calculation from main loop and applied Montgomery trick three times in total, so I call it "Triple Montgomery trick" That was fun! I have a question: which jump tables did you use for the main step and for escaping loops?
Did you use jump tables from the ranges of previous puzzles, taking advantage of the existing database, or did you start all over again?
I had reasons not to use old databases, so I used fresh jump tables. |
|
|
|
|
Thanks.
Yeah, finally I solved #135, it took about 5 months on 200GPUs.
It was... long. I quit, officially. Happy solving #140 without me.
To help you with this, today I will update RCKangaroo with complete sources for ASM turbo kernels.
I will also publish pk for #135 but later, not right now, when I have some time I will think up another mini-puzzle for that.
|
|
|
|
SOTA has K=1.15. For DP=0 with cheap point kangaroo can make two points for every jump that you add to DB, so you will get K=1.15/2 |
|
|
|
I named my app RCKangaroo because it's fun! I don't care that its algo is not original Pollard's kangaroo algo. Sorry, I removed your crazy discussion, please use that useless almost-1000-pages thread for such endless talks That’s interesting, but I’d like to get an expert opinion on whether it’s worth creating checkpoints and continuing the search in this format, as I haven't found a pool with a different approach.
I didn't check it so I have no idea. |
|
|
|
Regarding the jumps, it is clear that their direction depends on the Y-coordinate, and in most cases,
they tend to bounce around approximately within their own local area (halo).
However, please observe this closely. After just a month of running,
a large number of kangaroos will end up in a space that is 4 bits larger. This is a serious problem.
If you see this issue, probably the best solution is just to restart a kangaroo after it hits DP. Or you can reduce jumps and hope that it wont cause other issues. By the way, I added an implementation that restricts kangaroo landings to even X-coordinates 75% of the time.
SOTA+ does this trick with the cheap point. If you managed to do it without using cheap point - you found a security issue of secp256k1. |
|
|
|
1. About jump sizes and Out-Of-Bounds drifting
When working with large search ranges, the jumps from Table 2 accumulate over a long period, which causes the kangaroos to eventually drift far outside the boundaries of the search range.
Because of this, do you think it would be better to use smaller jumps in Table 2 to prevent them from drifting out of bounds?
Jumps for all tables can be right or left (depends on Y), so I don't expect any serious drifts. Also I don't like the idea of reducing these jumps, but you can try it.
2. Potential race condition in KernelB
Also, I noticed a potential issue in KernelB when writing to LoopTable. The code currently uses BLOCK_X at the end of the index:
Kparams.LoopTable[MD_LEN * BLOCK_SIZE * PNT_GROUP_CNT * BLOCK_X + 2 * MD_LEN * BLOCK_SIZE * gr_ind2 + ind * BLOCK_SIZE + BLOCK_X] = RegsA;
Doesn't this cause all threads in the block to overwrite the exact same memory address at the same time? I changed the last BLOCK_X to THREAD_X so that each thread writes to its own unique column, and it seems to work perfectly. Was BLOCK_X just a typo here, or is there a specific reason for it?
Oh, it's a bug, it must be THREAD_X of course! I have version 4.0 with a lot of changes to support asm kernels and some interesting ideas implemented, but I will upload it later (as I said above). |
|
|
|
Could you please tell me if you plan to release instructions or examples of assembly kernels specifically for the RCKangaroo program,
for different architectures, in the future?
Yes I will publish asm sources for my turbo kernels (both sm89 and sm120) for RCKangaroo as soon as #135 is solved (no matter who solves it). It will happen soon, so you won’t have to wait long. |
|
|
|
Finally I had some time to prepare RCAsm for people who are brave enough to make their CUDA kernels faster https://github.com/RetiredC/RCAsmWhy ASM? PTX is not powerful enough:- You still cannot control registers usage. - PTX does not provide all instructions, some of them can be really important if you are going to create really fast code. - There is no way to declare fast functions: if you define "inline" function, it's just including its code so main code grows every time when you call that function. If it's not inline, calls are very slow. - There is no way to use uniform registers and instructions directly. - There is no way to specify control codes. - There is no good management for carry flags, also some carry-related instruction are missed. - You have to check what SASS is generated every time, spend time to convince compiler to make it as you want, etc. As a result, often ASM is really faster if you know what you are doing. RCAsm features:- sm89 and sm120 support. - variables for R, UR, P. - asm functions (include/call). - supports constants and math expressions. - automatic kernels injection into .cuasm file. - simple but convenient editor for asm sources. - #IF #ELSEIF #ENDIF support. - open source, written in Python. I hope you will have a lot of fun with this tool and SASS Also check Kernel01 sample for SASS implementation of MulMod256. |
|
|
|
Rc, don't you think it would be better to change in RCGpuCore.cu: jmp_ind = x[0] % JMP_CNT; to jmp_ind = x[1] % JMP_CNT; So you think that the lowest bits of the X of secp256k1 points are not uniformly distributed, right? Why do you think so? I see same uniform distribution for any bits. Anyway, it's very easy to check and I don't see any difference in my tests. No, he is correct. And it's because when the DP uses the same bits as the jump index function, and you get to select a better X between two options, this adds bias for the even indices in the jump table, increasing their probability, hence losing the overall selection uniformity for the pseudo-random walk. This is easily proven (and very visible) by plotting the frequencies of the used jump indices - it's not uniform at all.
Even worse when selecting a DP based on more than one bit (powers of two indices get biased the more bits you get to compare between two X candidates).
Just don't use same bits for DP, jumps and for point selection to avoid such issues |
|
|
|
Let me guess: you compute Q = P + J and Q' = P - J, and you choose the point with minimum x.
Almost, it's all described here (also there are some comments in sources): https://github.com/RetiredC/Kang-1 |
|
|
|
BTW, I still don't understand why you bother about all these boring cycles, you have much better algo for a long time!
It ran too slow. btw you can get to 0.95 with SOTA+. Not sure why you don't like it for GPU, my assumption is that you trade some higher speed (1.5x points instead of 2x each step) with the higher k of SOTA? 1. Slow?? Well, ok 2. Oh, it's easy: SOTA+ requires additional MUL+SQR, so it's just not profitable if you have really cheap inversion. |
|
|
|
OMG, I see interesting comments here finally! ...a walk may hit one end of the 2-cycle, another walk the other end, but they must both exit from the same point...
Or you can don't care about it and lose just 0.1% of K. BTW, I still don't understand why you bother about all these boring cycles, you have much better algo for a long time! 47 bits, DP 10 [2] Ops: avg 11267030 = 0.950 * sqrt(b) min 7221075 max 15312985 dp_ovh: 1536.0 mul: 10.50
Stored footprints: avg 25820 min 16542 max 35099
No cycles. I wouldn't believe it either, so that's fine. Everything is already checked, counted, and verified to be correct.
I verified it also for higher bit ranges, that jump on GPU.
Those figures are the total op count including DP overhead (complexity excludes DP overhead).
And I'm using more than 3 kangaroos. Pure math and skills, you should understand that.
|
|
|
|
the speds varies depending on the language and the libraries , on python using ecdsa its very slow i think 80k/s but if we used coincurve it goes up (114,956 EC additions/sec) , but on c++ the speed is better never tested it but i can predict it coincurve uses libsecp so if we used the 4threads we can achive 500-700k/s , just tested it it can reach Speed: 548779 EC additions/sec using 4 threads in c++
BTW, you talk about knowledge and intelligence, but use slow python and its libs instead of writing own optimized lib in c. So optimizing is not a part of intelligence in you opinion? Performance always matters here, if I had only CPU I would create heavy-optimized lib for it to be able to perform more tests and researches. |
|
|
|
|
Show Posts
