Search content
Sort by
Showing 20 of 641 results by Etar
-snip-
Imagine a big bag full of green beans and only one red bean (the private key we're looking for). If I pick a random bean blindly from the bag and throw it back if it is not the red one, every bean I pick will have the same incredibly low probability of being the red one. And for each pick, the chance of getting the red one will be the same as taking the one I threw back before... So I might end up scanning a lot more keys than the size of the range before I find the private key.
So even if I count the number of beans I test, I have no guarantee that after testing as many beans as there are in the bag, there will be no red bean. Maybe I was just unlucky and didn't pick it.
Any constructive thoughts/opinions on this?
I don't think anyone searches for a key this way. Usually, if you want to search randomly, the entire range is divided into small subranges. These subranges are entered into the database. And each time after a random selection of a subrange from all the remaining ones, it is removed from the queue and does not participate in the future. Thus, green beans do not return to the bag.Imagine a big bag full of green beans and only one red bean (the private key we're looking for). If I pick a random bean blindly from the bag and throw it back if it is not the red one, every bean I pick will have the same incredibly low probability of being the red one. And for each pick, the chance of getting the red one will be the same as taking the one I threw back before... So I might end up scanning a lot more keys than the size of the range before I find the private key.
So even if I count the number of beans I test, I have no guarantee that after testing as many beans as there are in the bag, there will be no red bean. Maybe I was just unlucky and didn't pick it.
Any constructive thoughts/opinions on this?
Hi,
Lately I was wondering if it is possible to modify JLPKangaroo_OW_OT to write DP's on SSD M.2 NVMe instead of RAM? Do You have some experience or theoretical knowledge about such an issue?
I know that RAM is something different than SSD, but concerning that main task in Kangaroo is to caclucate points, find DP's and search for colision, is there a chance to store DP's on NVMe SSD without losing performance?
Best Regards
Damian
For JLP you can try using client/server. The DPs will be saved and sent to the server, where they will be merged into 1 file.Lately I was wondering if it is possible to modify JLPKangaroo_OW_OT to write DP's on SSD M.2 NVMe instead of RAM? Do You have some experience or theoretical knowledge about such an issue?
I know that RAM is something different than SSD, but concerning that main task in Kangaroo is to caclucate points, find DP's and search for colision, is there a chance to store DP's on NVMe SSD without losing performance?
Best Regards
Damian
Or if you don't care what software to use, you can try Etarkangaroo where can save DPs after any period of time without losing much in performance. When saving, they merge.
Please report speed for other cards, for old cards speedup is up to 40%.
Thanks!1660Super 948Mkey/s
@RetiredCoder I want to admit that unfortunately I did not win mini game #130, I just followed your explanations and found the key #130 0x33e7665705359f04f28b88cf897c603c9
r1_1 = 02de97092bfb7c02148a827b4f8b62db1e189a739c77815799df5e6fb35ae88a1f
r2_1 = 02838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc
delta = 031e283a9ebc4c50b0a93f27d411e69d0a97aad2a6d4ae26f5725f8b55fb5176f5
delta _k = 0xfffffffffffffffffffffffffffffffebaaedce6af487e246f4eac90b714b3bd
r2_1 = 02838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc
delta = 031e283a9ebc4c50b0a93f27d411e69d0a97aad2a6d4ae26f5725f8b55fb5176f5
delta _k = 0xfffffffffffffffffffffffffffffffebaaedce6af487e246f4eac90b714b3bd
Yes, you should have some understanding of ECDSA signature vulnerabilities.
2 most common vulnerabilities are repetitions of K for the same private key and weak KWe have only 2 signed messages and their signature r does not match, only the weak K remains.
I checked 02/03838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc in the 80-bit range it is not there.
sha256 from the message also does not reveal r, as well as double hashing.
The rabbit hole is too deep. I'm tired))
The main vulnerability of signatures is the use of the same value of K, which gives the same value of r.
for the first message the values of r and s were:
r 0xde97092bfb7c02148a827b4f8b62db1e189a739c77815799df5e6fb35ae88a1f
s 0x3f4fa38bcbb17615446fabc6fbebceefbb7d052eca9ce136b3a4a67b7f0d4f42
for the second message the values of r and s were:
r 0x838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc
s 0x288da41a03e78a23e2ac277921e2d19d17717a27a10f1c6cca7fd5ba351a5fca
I don't see the same r values here, maybe I'm being stupid.
for the first message the values of r and s were:
r 0xde97092bfb7c02148a827b4f8b62db1e189a739c77815799df5e6fb35ae88a1f
s 0x3f4fa38bcbb17615446fabc6fbebceefbb7d052eca9ce136b3a4a67b7f0d4f42
for the second message the values of r and s were:
r 0x838db77b981db321faf527a830461cfda01aed50d85c345a7b0a8f4e5e4fd3fc
s 0x288da41a03e78a23e2ac277921e2d19d17717a27a10f1c6cca7fd5ba351a5fca
I don't see the same r values here, maybe I'm being stupid.
You say:
I can currently squeeze out 6.2 Gk/s on a RTX 4090, but some users here claim they can obtain 8 Gk/s or more
RetiredCoder say:Note that I have not included all possible optimizations because it's public code and I want to keep it as simple/readable as possible.
Git RCKangaroo say:Code:
about 8GKeys/s on RTX 4090.
You say:NB regarding RCKangaroo - it runs 1.5x slower than my kernel.
How can this be understood?Did you make a mistake?
I use visual studio.Code:
if (deviceProp.major < 6)
{
printf("GPU %d - not supported, skip\r\n", i);
continue;
}
I also made other changes, which is probably why the line numbers don't match. But you can easily find the lines you need, because I didn't add anything new, I just changed it.{
printf("GPU %d - not supported, skip\r\n", i);
continue;
}
@Etar how did you do everything to make your GTX 1660 work? Can you tell me all the changes and show me them? Many thanks
file: RCGpuCore.culine 285: u64* table = LDS + 8 * JMP_CNT + 16 * THREAD_X;
Line 99: if (deviceProp.major < 6)
file: defs.h
#define LDS_SIZE_A (64 * 1024)
#define LDS_SIZE_B (64 * 1024)
#define LDS_SIZE_C (64 * 1024)
#define JMP_CNT 512
file: RCKangaroo.vcxproj
line 118: <CodeGeneration>compute_75,sm_75;compute_75,sm_75</CodeGeneration>
line 141: <CodeGeneration>compute_75,sm_75;compute_75,sm_75</CodeGeneration>
Code:
CUDA devices: 1, CUDA driver/runtime: 12.6/12.1
GPU 0: NVIDIA GeForce GTX 1660 SUPER, 6.00 GB, 22 CUs, cap 7.5, PCI 1, L2 size: 1536 KB
Total GPUs for work: 1
MAIN MODE
Solving public key
X: 29C4574A4FD8C810B7E42A4B398882B381BCD85E40C6883712912D167C83E73A
Y: 0E02C3AFD79913AB0961C95F12498F36A72FFA35C93AF27CEE30010FA6B51C53
Offset: 0000000000000000000000000000000000000000001000000000000000000000
Solving point: Range 84 bits, DP 16, start...
SOTA method, estimated ops: 2^42.202, RAM for DPs: 3.062 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 570.958.
GPU 0: allocated 772 MB, 135168 kangaroos.
GPUs started...
MAIN: Speed: 599 MKeys/s, Err: 0, DPs: 88K/77175K, Time: 0d:00h:00m:10s, Est: 0d:02h:20m:43s
GPU 0: NVIDIA GeForce GTX 1660 SUPER, 6.00 GB, 22 CUs, cap 7.5, PCI 1, L2 size: 1536 KB
Total GPUs for work: 1
MAIN MODE
Solving public key
X: 29C4574A4FD8C810B7E42A4B398882B381BCD85E40C6883712912D167C83E73A
Y: 0E02C3AFD79913AB0961C95F12498F36A72FFA35C93AF27CEE30010FA6B51C53
Offset: 0000000000000000000000000000000000000000001000000000000000000000
Solving point: Range 84 bits, DP 16, start...
SOTA method, estimated ops: 2^42.202, RAM for DPs: 3.062 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 570.958.
GPU 0: allocated 772 MB, 135168 kangaroos.
GPUs started...
MAIN: Speed: 599 MKeys/s, Err: 0, DPs: 88K/77175K, Time: 0d:00h:00m:10s, Est: 0d:02h:20m:43s
That's why I don't want to support old cards: if I support them officially but not optimize you will blame me that they have bad speed.
But feel free to modify/optimize sources for your hardware
I'll be honest, your kangaroo finds the key faster than mine or jlp. Yes, the speed shows less, but in the end it finds it much faster. But feel free to modify/optimize sources for your hardware
Works even on 1660 super (~600Mkeys/s).
Thanks for sharing.
Honestly, I'm just a lazy developer. My program, Keyhunt, isn't even optimized for GPUs yet! After more than three years, it's still riddled with bugs and quirks. But hey, despite all that, it's currently the fastest Baby-Step Giant-Step (BSGS) implementation available for CPUs. Not bad for a hobby project, right?
I am also lazy and I made the fastest (for now) implementation of bsgs for gpu. The difference between us and him is that we let people use our developments and sources, but he does not. If everyone sits in their own world and does not share knowledge, then there will be no progress. And this applies not only to him, but to others as well.And what is the meaning of calculating K? As soon as you increase the number of kangaroos, your K will fly into space.
With 65536 kangaroos in the classic version K will be 3.07
And when using the GPU, K increases even more due to dp overhead, in this case you will easily reach k=10
With 65536 kangaroos in the classic version K will be 3.07
And when using the GPU, K increases even more due to dp overhead, in this case you will easily reach k=10
1BY8GQbnueY How did you know it was 56 bit?
If you look at the RMD hash (739437bb3dd6d1 9 83e66629c5f08c70e52769371), you will see that for your combination 1BY8GQbnueY 14 hex numbers are used, plus one more digit from 4 to a. In total, this gives 2^56 bits.And how did you come to the conclusion that in the 66-bit range there are only 4 combinations?
⭐ Merited by kTimesG (1)
So I guess everyone learned the answer to the question I wrote before,
How many 1BY8GQbnueY starts are there in our 67 bit range? The correct answer is 4.
I disagree with you. Firstly, puzzle #67 has a range width of 66 bits.How many 1BY8GQbnueY starts are there in our 67 bit range? The correct answer is 4.
The second is that 1BY8GQbnueY has a length of 56 bits and accordingly in the entire range of 66 bits there are approximately 1024 such combinations.
I can't understand why this code doesn't want to work correctly. The DPs accumulate but there is no collision...
Code:
__device__ void ComputeKangaroos(uint64_t* kangaroos, uint32_t maxFound, uint32_t* out, uint64_t dpMask) {
//GPU_GRP_SIZE =4
//NUM_OF_JUMPS = 64
uint64_t px[GPU_GRP_SIZE][4];
uint64_t py[GPU_GRP_SIZE][4];
uint64_t dist[GPU_GRP_SIZE][4];
uint64_t lastJump[GPU_GRP_SIZE];
uint64_t newpx[NUM_OF_JUMPS][4];
uint64_t newpy[NUM_OF_JUMPS][4];
uint64_t newpz[NUM_OF_JUMPS][4];
uint64_t jmp;
int stride = threadIdx.x & 31;
Load256(SjPx[stride], jPx[stride]);
Load256(SjPy[stride], jPy[stride]);
Load256(SjD[stride], jD[stride]);
__syncthreads();
LoadKangaroos(kangaroos, px, py, dist, lastJump);
for (int run = 0; run < NB_RUN; run++) {
for (int grp = 0; grp < GPU_GRP_SIZE; grp++){
newpz[0][3] = 0;
newpz[0][2] = 0;
newpz[0][1] = 0;
newpz[0][0] = 1;
jmp = (unsigned int)px[grp][0] & (NB_JUMP - 1);
ADDz1(newpx[0], newpy[0], newpz[0], px[grp], py[grp], newpz[0], SjPx[jmp], SjPy[jmp]);
for (int g = 1; g < NUM_OF_JUMPS; g++) {
jmp = (unsigned int)newpx[g - 1][0] & (NB_JUMP - 1);
ADDz1(newpx[g], newpy[g], newpz[g], newpx[g - 1], newpy[g - 1], newpz[g - 1], SjPx[jmp], SjPy[jmp]);
}
__syncthreads();
_InvGrouped(newpz);
jmp = (unsigned int)px[grp][0] & (NB_JUMP - 1);
_ModMult(px[grp], newpx[0], newpz[0]);
_ModMult(py[grp], newpy[0], newpz[0]);
Add128(dist[grp], SjD[jmp]);
if ((px[grp][3] & dpMask) == 0) {
// Distinguished point
uint32_t pos = atomicAdd(out, 1);
if (pos < maxFound) {
uint64_t kIdx = (uint64_t)IDX + (uint64_t)grp * (uint64_t)blockDim.x + (uint64_t)blockIdx.x * ((uint64_t)blockDim.x * GPU_GRP_SIZE);
OutputDP(px[grp], dist[grp], &kIdx);
}
}
for (int g = 1; g < NUM_OF_JUMPS; g++) {
jmp = (unsigned int)newpx[g - 1][0] & (NB_JUMP - 1);
_ModMult(px[grp], newpx[g], newpz[g]);
_ModMult(py[grp], newpy[g], newpz[g]);
Add128(dist[grp], SjD[jmp]);
if ((px[grp][3] & dpMask) == 0) {
// Distinguished point
uint32_t pos = atomicAdd(out, 1);
if (pos < maxFound) {
uint64_t kIdx = (uint64_t)IDX + (uint64_t)grp * (uint64_t)blockDim.x + (uint64_t)blockIdx.x * ((uint64_t)blockDim.x * GPU_GRP_SIZE);
OutputDP(px[grp], dist[grp], &kIdx);
}
}
}
}
}
__syncthreads();
StoreKangaroos(kangaroos, px, py, dist, lastJump);
}
//GPU_GRP_SIZE =4
//NUM_OF_JUMPS = 64
uint64_t px[GPU_GRP_SIZE][4];
uint64_t py[GPU_GRP_SIZE][4];
uint64_t dist[GPU_GRP_SIZE][4];
uint64_t lastJump[GPU_GRP_SIZE];
uint64_t newpx[NUM_OF_JUMPS][4];
uint64_t newpy[NUM_OF_JUMPS][4];
uint64_t newpz[NUM_OF_JUMPS][4];
uint64_t jmp;
int stride = threadIdx.x & 31;
Load256(SjPx[stride], jPx[stride]);
Load256(SjPy[stride], jPy[stride]);
Load256(SjD[stride], jD[stride]);
__syncthreads();
LoadKangaroos(kangaroos, px, py, dist, lastJump);
for (int run = 0; run < NB_RUN; run++) {
for (int grp = 0; grp < GPU_GRP_SIZE; grp++){
newpz[0][3] = 0;
newpz[0][2] = 0;
newpz[0][1] = 0;
newpz[0][0] = 1;
jmp = (unsigned int)px[grp][0] & (NB_JUMP - 1);
ADDz1(newpx[0], newpy[0], newpz[0], px[grp], py[grp], newpz[0], SjPx[jmp], SjPy[jmp]);
for (int g = 1; g < NUM_OF_JUMPS; g++) {
jmp = (unsigned int)newpx[g - 1][0] & (NB_JUMP - 1);
ADDz1(newpx[g], newpy[g], newpz[g], newpx[g - 1], newpy[g - 1], newpz[g - 1], SjPx[jmp], SjPy[jmp]);
}
__syncthreads();
_InvGrouped(newpz);
jmp = (unsigned int)px[grp][0] & (NB_JUMP - 1);
_ModMult(px[grp], newpx[0], newpz[0]);
_ModMult(py[grp], newpy[0], newpz[0]);
Add128(dist[grp], SjD[jmp]);
if ((px[grp][3] & dpMask) == 0) {
// Distinguished point
uint32_t pos = atomicAdd(out, 1);
if (pos < maxFound) {
uint64_t kIdx = (uint64_t)IDX + (uint64_t)grp * (uint64_t)blockDim.x + (uint64_t)blockIdx.x * ((uint64_t)blockDim.x * GPU_GRP_SIZE);
OutputDP(px[grp], dist[grp], &kIdx);
}
}
for (int g = 1; g < NUM_OF_JUMPS; g++) {
jmp = (unsigned int)newpx[g - 1][0] & (NB_JUMP - 1);
_ModMult(px[grp], newpx[g], newpz[g]);
_ModMult(py[grp], newpy[g], newpz[g]);
Add128(dist[grp], SjD[jmp]);
if ((px[grp][3] & dpMask) == 0) {
// Distinguished point
uint32_t pos = atomicAdd(out, 1);
if (pos < maxFound) {
uint64_t kIdx = (uint64_t)IDX + (uint64_t)grp * (uint64_t)blockDim.x + (uint64_t)blockIdx.x * ((uint64_t)blockDim.x * GPU_GRP_SIZE);
OutputDP(px[grp], dist[grp], &kIdx);
}
}
}
}
}
__syncthreads();
StoreKangaroos(kangaroos, px, py, dist, lastJump);
}
⭐ Merited by vapourminer (1)
What grid size are you using with the "original JLP Kangaroo version 1.7" in order to see it at 700 Mk/s on a GTX 1660S? Are you sure about that speed being real?
Cause with no code changes and using the 1.7 release tag, I can't go beyond 300 Mk/s (or rather, ~250 in reality, since stats display is kinda broken) on a card that is both newer and superior to that model. And looking at the nvcc compile stats, I have some doubts that it would even be capable to go at a triple speed, on an inferior card with 25% less CUDA cores.
You probably configured the grid incorrectly. The Nsight shows that 4 blocks are working simultaneously. That's why I have a grid of 88*128. And yes, the speed is +/- correct since it matches the amount of DP accumulated over a certain period of time.Cause with no code changes and using the 1.7 release tag, I can't go beyond 300 Mk/s (or rather, ~250 in reality, since stats display is kinda broken) on a card that is both newer and superior to that model. And looking at the nvcc compile stats, I have some doubts that it would even be capable to go at a triple speed, on an inferior card with 25% less CUDA cores.
P.S. If you like it, I can add a version with a bit more speed (gtx 1160 Super - 1.1 Gk/s)
I wonder what exactly you mean by 1.1Gk/s. Only one type of kangaroos included in that? Using my 1080 Ti, I get about 580Mk/s with my version.
[/quote]
The original JLP Kangaroo version 1.7 gives a speed of about 700 Mk/s for GTX 1660 Super, a few changes in the code and the speed will be 1.1 Gk/s and around 2.2Gk/s for 2080ti.
1080 Ti is old card, I don't know what speed you can get.
If you can share changewf.py though, that'd be great.
https://bitcointalk.org/index.php?topic=1306983.msg64701973#msg64701973⭐ Merited by vapourminer (1)
I didn't touch the workfile or changed it using a script. I did try using a CPU. I'll try now using a GPU.
Edit - doesn't work with a GPU either. what did you change from JLP's version?
I downloaded the KangarooOT and KangarooOW version from GitHub to make sure we were using the same tools.Edit - doesn't work with a GPU either. what did you change from JLP's version?
For the experiment we will look for the public key 02d2779258710a6fcd4e978335698e5c1b20795f8c3aae524714e0e40ebacdb213
whose private key is 0x7989031fda5ba3bf5 in the 67-bit range from 0 to 7ffffffffffffffff
Step 0: create a 67bitWrong.txt file with the following content:
Code:
0
7ffffffffffffffff
03633CBE3EC02B9401C5EFFA144C5B4D22F87940259634858FC7E59B1C09937852
Step 1: аor the accumulation of tame DPs create a step1.bat file with the following content and launch:7ffffffffffffffff
03633CBE3EC02B9401C5EFFA144C5B4D22F87940259634858FC7E59B1C09937852
Code:
kangarooOT -t 0 -gpu -gpuId 0 -g 88,128 -m 2.5 -d 13 -wi 120 -w testwork 67bitWrong.txt
for /l %%i in (1,1,6) do (
echo Iteration %%i
kangarooOT -t 0 -gpu -gpuId 0 -g 88,128 -m 2.5 -d 13 -wi 120 -w testwork -i testwork
)
pause
Step 2: To change the public key in the working file, make a step2.bat file and launch:for /l %%i in (1,1,6) do (
echo Iteration %%i
kangarooOT -t 0 -gpu -gpuId 0 -g 88,128 -m 2.5 -d 13 -wi 120 -w testwork -i testwork
)
pause
Code:
py changewf.py -f testwork -pub 02d2779258710a6fcd4e978335698e5c1b20795f8c3aae524714e0e40ebacdb213 -rb 0 -re 7ffffffffffffffff
pause
Step 3: To find the public key make a step3.bat file and launch:pause
Code:
kangarooOW -t 0 -gpu -gpuId 0 -g 88,128 -i testwork
pause
pause
When I try this trick, it just doesn't find the collision. even when it should take just a second, it never finds it. can you confirm these are the steps you did?
Choose a range (say, 48 bit)
Choose any key that is not in that range
run kangaroo on it for some time, (with -m 3 to be exact to your example), and make it save the work into a workfile.
Then load the work file into a new session with an actual key inside the range.
This is what I did, didn't work.
Before finding the public key in the range, did you change it in the working file using a script?Choose a range (say, 48 bit)
Choose any key that is not in that range
run kangaroo on it for some time, (with -m 3 to be exact to your example), and make it save the work into a workfile.
Then load the work file into a new session with an actual key inside the range.
This is what I did, didn't work.