Hi,
Does anyone know why my speed is so small, the card is GTX Titan Z.
I am using the compiled version of Jean_Luc.
Your card is the equivalent of two underclocked GTX 780 Tis and it is performing as expected. It is based on the Kepler architecture which is very old by today's standards. |
|
|
|
I think we can reduce the search range by 1 bit by shifting the initial range, and then shifting half the range. For example, the 79bit puzzle is shifted to the 78bit range: Start:0
Stop :3FFFFFFFFFFFFFFFFFFF
Range width: 2^78
[1405.94 MK/s][GPU 1405.94 MK/s][Count 2^38.90][Dead 0][06:55 (Avg 15:15)][481.5/608.4MB]
Key# 0 [1S]Pub: 0x02F65E6E18EAB67F86287D565702468C2F30A303F22EBDCEBE556C23D016350222
Priv: 0x2A1A5C66DCC11B5AD181 + 0x3fffffffffffffffffff + 0x80000000000000000000 = 0xea1a5c66dcc11b5ad180
without shifting: Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Range width: 2^79
[1380.42 MK/s][GPU 1380.42 MK/s][Count 2^40.59][Dead 0][22:35 (Avg 21:15)][1541.1/1932.8MB]
Key# 0 [1S]Pub: 0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
Priv: 0xEA1A5C66DCC11B5AD180
As you can see time and count less with shifting. If pubkey appear "under zero" after shifting it is not a matter you any way will found key. Here is example were pubkey is "below zero" random key 0xbc690499fb50bfde866b Start:0
Stop :3FFFFFFFFFFFFFFFFFFF
Range width: 2^78
[1390.34 MK/s][GPU 1390.34 MK/s][Count 2^40.00][Dead 0][14:53 (Avg 15:26)][1027.3/1290.6MB]
Key# 0 [1S]Pub: 0x02996740F4755163FB167F7D06875B3F415CD7AB9E2F198DE66E1E7D082086E64F
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF489CA4C46C59DD9014C7AD + 0x3fffffffffffffffffff + 0x80000000000000000000 = 0xbc690499fb50bfde866b
without shifting: Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Range width: 2^79
[1385.36 MK/s][GPU 1385.36 MK/s][Count 2^39.90][Dead 1][13:54 (Avg 21:10)][957.7/1203.7MB]
Key# 0 [1S]Pub: 0x02D48BBCB4370DA5F3CD5FBC25D1052C8BAC97953C65FB4F837A423320FAE88CB4
Priv: 0xBC690499FB50BFDE866B
In last example without shifting little bit faster because pubkey was around the center of range. Any way need few test.. It’s an 80-bit private key challenge and because we know that the private key can only be expressed with 80 bits, we can immediately eliminate half of the search interval. Half of 2^80 is 2^79, so that’s why I call it 80-bit private key challenge with a 79-bit search interval. Same is true for the other private key challenges with exposed public keys in this series. You cannot reduce the search space any further without brute force. |
|
|
|
I used Linux version, compiling github last version. 65.txt
------
10000000000000000
1FFFFFFFFFFFFFFFF
0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b
# Kangaroo github version Date: Sun Jun 7 06:43:00 2020 +0200
./kangaroo -wi 1 -w 65.save 65.txt
# My fork with 'wexport'
./FriedKangaroo -wexport 65.save
head tame.txt wild.txt
==> tame.txt <==
00007860796862b77663def37eaec012748f8 0000000000000000d1a2b6873ad16061
000082e81e4c4a33d0c1b8b49c3e00a4be836 000000000000000026cad0b165912746
000437e07afd45cef7944ae5b161f1df0ba4e 0000000000000000601ac5f0134d69bd
000464166e33cbd94e3ccf5272b4df1b11469 000000000000000051e7b44b64751df0
0004c94946d338d9f706cbae1860e0a4a362c 000000000000000056f0b43bc155a22c
0005d51d5b66f09c891a5af6efbb9a0f51aae 000000000000000042d2568962f26df1
00061a3590ca99c26549e8c8ee1275516bcab 0000000000000000d80aad8f08314744
000630f0c3542f10acc88362e11df849bc98b 00000000000000008c93cfb5218c6182
000813b89d1350e9740af0bed4224911401f3 0000000000000000ec870953b96ff89b
0008bd33af12d0587acb72a758667760f0780 0000000000000000a8e43affff9d308e
==> wild.txt <==
00011ee12c4fe000037449166c9680be93bf3 0000000000000000732a93a7c0625d29
000158515f890c49b608f23ec7717ed42e650 000000000000000020dee9654893f1d9
00025559376457b3d94c0c6493fb1fd893a15 00000000000000001730d21498fcc363
0003f80f12b0f73ad8483e3d63bb37bd1043a -00000000000000005af81793c032e216
00042e9863823886282176066c4bcc3020c60 -00000000000000004da91f00d7ef1261
00055b5545e9b32f5d9f4b26500d6126f0962 -000000000000000068762260d7829363
0006895b5122bf0a599cc2f4e7d3de2d0180d 00000000000000004ad469542989e05b
00070258142e4c4fddf93edec87781bc43be8 00000000000000006c9d275e1a58bc14
00072dfc9270c8b69f77119b9830b4243e089 00000000000000004a61321922a283ef
00092eb91a1ebe9c45a746bb43928db973eca -0000000000000000342d7af2532ab7c0
# Without 'wexport' using hexdump or xxd.
# Skip 156 bytes of savefile header and show hexdump
dd if=65.save bs=1 count=256 skip=156 | xxd -c 32 -g 16 -e
...
00000040: 860796862b77663def37eaec012748f8 0000000000000000d1a2b6873ad16061
... Interesting. So Linux vs Windows, you get two different looking files. I think that on Windows it has to be %0I64x or %016llx for the format specifier. I don’t have Windows to test, so make the changes and see if it makes a difference. In the function “void Kangaroo::WorkExport(std::string &fileName)” change “%016lx” to “%0I64x or %016llx” https://github.com/PatatasFritas/FriedKangaroo/blob/master/Backup.cpp#L525 |
|
|
|
@WanderingPhilospher
Let G = secp256k1_generator_point
Edit:
Let LSB = 128 lower bits of the x-coordinate
(0x0000000024a2b6bb0000000026dd90e3)*G = 0x1bfbfb9e55b617f03ad44aabe7545c1aad8ac86776cf2b3ba9bc5d0eb1002f99
Doesn’t match the LSB of the x-coordinate from your tame line data, maybe try a few more random points from the file. I was able to validate 10,000 points from my file without any errors.
Yes, you should be able to solve the key when there is a match from the files. But you will also need the beginning range that was used to solve for the original key. We only need to find out if there’s a match of the LSB of the x-coordinates from both types of kangaroos, then we can use the distances and the beginning range to calculate the private key.
So, if you have matching LSBs, then you may have a solution? In your estimate, how many times can LSBs match up but do not solve the key, guesstimate. If you have 128-bit matching LSB, then with very high probability that you will find a solution. The probability for not finding a solution with 128-bit matching LSB is very small: [number of entries in your hash table] divided by [2^128] |
|
|
|
|
@WanderingPhilospher
Let G = secp256k1_generator_point
Edit:
Let LSB = 128 lower bits of the x-coordinate
(0x0000000024a2b6bb0000000026dd90e3)*G = 0x1bfbfb9e55b617f03ad44aabe7545c1aad8ac86776cf2b3ba9bc5d0eb1002f99
Doesn’t match the LSB of the x-coordinate from your tame line data, maybe try a few more random points from the file. I was able to validate 10,000 points from my file without any errors.
Yes, you should be able to solve the key when there is a match from the files. But you will also need the beginning range that was used to solve for the original key. We only need to find out if there’s a match of the LSB of the x-coordinates from both types of kangaroos, then we can use the distances and the beginning range to calculate the private key.
|
|
|
|
Those are from Tame and Wild files. What exactly does the program look for in those 2 lines above to result in solved key? Can anyone break it down by line and what the line/characters represent? Thanks.
Without knowing how the data is encoded/decoded, the lines by themselves are not very useful. A link to the source code would be very useful in this case. was the export done by patatasfritas where he stated: The X-coord is 128+18 bits and distance 126bits. The X-coordinate could be re-generated from the distance if necessary. source code: // Read DP
for(uint32_t h = 0; h < HASH_SIZE; h++) {
fread(&items,sizeof(uint32_t),1,f1);
fread(&maxItems,sizeof(uint32_t),1,f1);
for(uint32_t i = 0; i < items; i++) {
fread(&x,16,1,f1);
fread(&d,16,1,f1);
sign = (d.i64[1] & 0x8000000000000000);
htype = (d.i64[1] & 0x4000000000000000);
if(htype==0) {
::fprintf(ft,"%05x%016lx%016lx ", h & 0x3ffff, (uint64_t) (x.i64[1]), (uint64_t) (x.i64[0]));
::fprintf(ft,"%016lx%016lx\n", (uint64_t) (d.i64[1] & 0x3fffffffffffffff), (uint64_t) (d.i64[0]));
numTame++;
} else {
::fprintf(fw,"%05x%016lx%016lx ", h & 0x3ffff, (uint64_t) (x.i64[1]), (uint64_t) (x.i64[0]));
if(sign)
::fprintf(fw,"-");
::fprintf(fw,"%016lx%016lx\n", (uint64_t) (d.i64[1] & 0x3fffffffffffffff), (uint64_t) (d.i64[0]));
numWild++; ft = tame; fw= wild. I found and compiled the above source code and my exported data validates while yours do not. The first column is the least significant bits (LSB) of the x-coordinate, and the second column is the traveled_distance to multiply secp256k1_generator_point with. Tame: [distinguished_point] = (tame_traveled_distance)*(secp256k1_generator_point) Wild: [working_public_key] = [(original_public_key) - (beginning_range)*(secp256k1_generator_point)]. [distinguished_point] = [(+-wild_traveled_distance)*(secp256k1_generator_point)] + [working_public key] [private_key] = (beginning_range) + (tame_traveled_distance) +- (wild_traveled_distance) |
|
|
|
Those are from Tame and Wild files. What exactly does the program look for in those 2 lines above to result in solved key? Can anyone break it down by line and what the line/characters represent? Thanks.
Without knowing how the data is encoded/decoded, the lines by themselves are not very useful. A link to the source code would be very useful in this case. |
|
|
|
How many Chrome tabs can you open with 4TB or RAM  Not on a single server, a distributed hash table on 8 servers with 512GB per server. |
|
|
|
This is a race, we keep few settings secret. We will probably end to fight after #120. However now news from Zielar, he is probably sleeping  Good luck and you guys have way more computing power that you are willing to commit.  I am going straight for the knowledge, world record, and bragging rights for secp256k1 130-bit private key (129-bit interval). But I only have 4TB of RAM and still working on how to minimize storage below 16bytes/point with data compression techniques.  |
|
|
|
@arulbero Well said, the information above should be very useful for those new to the area. Also as it relates to FPGAs, those are more suited for binary curves; and GPUs such as RTX 2080Tis, RX Vega 64, and the likes are well suited for prime curves $ for $. If you would like to play around with FPGAs and ECDSA (secp256k1), everything you need to start is right here: https://github.com/ZcashFoundation/zcash-fpga |
|
|
|
-snip- ------- if some tool change pubkey inside save.work, and this save work recalculate within all his record, how much time its take to find changed pubkey for same 64 bit  if you change only pubkey it will be not working, due to wildDP produced from old pubkey. You need tame wild DP with known private key and than you can use this file agan but there will be only tame DP. I think today about using experience and concluded that it might help, but not too much. The whole point of a kangaroo is the effect of a birthday paradox. And if we have no pairs in the working file, but only one view, then the help is not too big, I think. Yes, precomputation works best when the Tame Kangaroos are randomly distributed in a given search interval. Not necessarily so when only using a single output from the previous run. |
|
|
|
Is this the correct x and y coords for pub 110?
Public Key : 0309976BA5570966BF889196B7FDF5A0F9A1E9AB340556EC29F8BB60599616167D
Xcoordinate: 09976BA5570966BF889196B7FDF5A0F9A1E9AB340556EC29F8BB60599616167D
Ycoordinate: 02EF58F7EEF3EBBC285602744AD51753BAD939C214FF6A465C384377ABDEA7B9
Yes |
|
|
|
Congrates to winner giving you new thinking level for 115, from my previous research, some friends here tested but hard for them to believe earlier, just for information check my 2048 pubkeys list https://anonfiles.com/a750taA8n6/100bit_txt dated November 09, 2019, 06:35:23 PM refrence https://bitcointalk.org/index.php?topic=1306983.msg53030914#msg53030914privatekey 110 hex: 35c0d7234df7deb0f20cf7062444 hex: 00000000000000000000000000000000000035c0d7234df7deb0f20cf7062444 dec: 1090246098153987172547740458951748 / 1024 dec: 1064693455228503098191152791945.06640625 hex: D7035C8D37DF7AC3C833DC189 pubkey: 03bb788bea10bedfc4f32aee0f542fc9a0749b5db72a8b094cbbad9fde366f6fa4 hex: D7035C8D37DF7AC3C833DC188 pubkey: 02f2c172df4c4553891bd3c5e8a668a8fd5f5a46d0bc6b109649507180011301ac check my created 100 bit 02f2...301ac and 03bb788... 6fa4 listed in 2048 corresponding keys to 110 puzzle @brainless The solution set to your list is [(110_bit_private_key - 2i)/(1024)] modulo (secp256k1_group_order). This adds no new information to help solve the problem. |
|
|
|
Congratulations to @Zielar |
|
|
|
what i do not understand why zielar is not solve key yet..
with him power he can already done 4*sqrt(n) simply.
I left the race because I feel like something is wrong here.
It’s not a compute only problem. It’s a compute, storage, and network bandwidth problem when you place solving time constraints on large intervals. Hopefully after he solves it, he will disclose the resources used and any challenging issues that he had to overcome. |
|
|
|
Any body know if it is possible to know point is positive or negative? Or it is imposssible to know?
Only after solving the DL for that point, otherwise it would be trivial to solve the DLP on that curve. In a way, there are no negative or positive points because of the modular group. |
|
|
|
Hardware, how long are you running your precomp for? You have a set # of DPs or a percentage? 2/3 ops?
@WanderingPhilospher The goal is ~512GiB worth of precomputed points (@ 16bytes/point). How much bytes do you have for x-coordinate and for distance? For the whole distance in 109bit range we need 109/8 ~ 14 bytes. If you allocate lower space, you need to brute the remaining bytes/bits if the collision is found. If you have 16 bytes space per point, so you should split somehow it between x-coordinate and distance. @MrFreeDragon Please see my previous comment. Only 8bytes of the x-coordinate is needed plus ~4bytes for lookup information. |
|
|
|
How did you manage to get it down to 16 bytes per point?
@BitCrack I am storing only 8bytes of the x-coordinate and lookup information (8bytes with HT overhead included) on how to retrieve the rest of the information in the event of a collision. This is accomplish by using a custom version of Google’s Sparse_Hash_Map in a distributed setup. The cost is network bandwidth but all clients are on a 1 GigE network. https://github.com/sparsehash/sparsehash |
|
|
|
As relating to the Wild Kangaroos, [working_public_key] = [(original_public_key) - (beginning_range)*(secp256k1_generator_point)].
[distinguished_point] = [(+-traveled_distance)*(secp256k1_generator_point)] + [working_public key]
You will need to add back the (beginning_range) when there’s a collision to solve for the (original_public_key).
Ok. it is addidng point not addiding key + distance (0xe6dabff2705a80acc23ae121956873c4ff9fd31cb0faca522c33624e23657e04,0x125c04d29ea83874332ea8aef3b3467f22665a4970df415be756bcdf5675e569) + (fb12e2e7eba822db7582b91da81c0f1d991a6fec79d170733a1eceb039b3e1f9,ee2e79d5326d178c91ed36ca52f9be4f04c42e3cf7cabb3299e070bc1231bb05) =(dcbae520622e89bd4c0062bb82400003c628f41e76f5bce8566c3dfa2c3fff0,b6fdc18b5be9048e837759b86efa422511b717ed9e7bc2d7b1936c06a0620cfe) and x coordinate is correct,, but any way tame will never get this point becouse it is out of range 0..fffffffffffff So not all wild can be tame. We can tame all wild with sign + but each wild with sign - should be verifid with range. In that case we can add tamed wild to experience. @Etar I am not sure if that’s the case with Jean_Luc’s software, but with mine all Wild_Kangaroos can be converted to Tame_Kangaroos after the DL has been solved. I ran a small test and it was true for all cases: iterations = 65536 (2^16)
bmul size = 22
batch size = 128
total keys = 8388608
main context = 0.01402114
bmul context = 10.28601294
Baseline verification passed
Serial verification passed
Starting...
fffffffffffffffffffffffffffffffebaaebd0cde863851b153c3b3e54b842a
2855b4681021cbc04373860592de141d7e8686574f6edb7de522baf3a8eb0309
000001e66aa3c3ccbbe8735d6af80000078097436d9053b4552d8bb2c6491b15
fffffffffffffffffffffffffffffffebaaebcf57871bba71cababca3cfc6ba5
3c9bf5c08830cbd65ac8c4d551ddd8b77e93b56ba917fe70a6f9a7093f11907c
00000145e24ee029218b666ef7bc00000977a6faaf969829b43524b39c1594ae
fffffffffffffffffffffffffffffffebaaebcfdf0ee232d9145f3fe9d38ff41
85aa570afa81ba04d4a5cb000a90468caf95078cfedd7ca8379c32a9e5f2d615
000000688f0aa57f0950015258ac00000b30373c83ed1236f3fb177730a2117e
fffffffffffffffffffffffffffffffebaaebd0598056b9fc923ecc885a3bc20
c4c7a3af557b96e726a9377f7a37ca9bae18d06e16f11f859a95cb4409780f47
000001820963965f9c34ad90266400000d412f5abe971869764e15e03f8f8ad8
fffffffffffffffffffffffffffffffebaaebd0ada254af6931585f77bafcf4d
dd3d0d37ea59b4bbae97dcef111398a86bfd249dbf0ab536457c23f634d92aaa
0000017bdcfa4edd88fdf04dfd0c00000f16e754bc105657863055dd948487a1
fffffffffffffffffffffffffffffffebaaebcf25b5a4b020e63b0ce136fa282
f4cb6a2aa4fdace911883c0aa733af8447e06b5c56526f43569168b91936cb19
000000a4bf27ad623515dc0de7f8000016c74bbaa3098d7aa92ed4f331f12c95
fffffffffffffffffffffffffffffffebaaebcf176baa77561285fff4e219ad5
1af3f603f6edd7b10349afcfa13bbd63c1bdb99801e491b682184924dfc5c3c4
00000022f465e6f8b16d0f1c1ea000001706ad24024dd9fa0ce11c0adce08018
fffffffffffffffffffffffffffffffebaaebd015682cd2ae25d864d4169574c
d64b5bcb9724ed9a02dae2dac8ec17686f4b6f765c0534bff11888b928d08ec2
000001c2d572bdebd0f8831fd3e800001831690f67a08f7da03346684b117560
fffffffffffffffffffffffffffffffebaaebcf3d017caaa8c6822877b7f8688
13c9f7a86c88bc696fc6da053acf6568110acb4677620fef3bc7d5fd3800c2bb
000000866db879683704712e878400001ba7908f67561bdc006981cbbdcb15b1
fffffffffffffffffffffffffffffffebaaebcf5eb02df76cdf1112b2f85aa76
32be189e1d49409560a3e0273d973965b5742407caba96942af32f0b239a4bdb
000001be084cae57d8293270a5b400001c8467b521322e3635adf277d28d460b
.
.
.
|
|
|
|
Hardware, how long are you running your precomp for? You have a set # of DPs or a percentage? 2/3 ops?
@WanderingPhilospher The goal is ~512GiB worth of precomputed points (@ 16bytes/point). |
|
|
|
|
Show Posts
