aliashraf
Legendary
Offline
Activity: 1456
Merit: 1174
Always remember the cause!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 02:21:09 AM |
|
What's the point of this thread after all? Bragging with number theory algorithms ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) Fifty pages, one thousand posts, so many merits, ... what does it have to do with bitcoin? Seriously, I don't get it. I understand bitcoin has roots in cryptography it is called cryptocurrency after all and cryptography is mostly, if not all, about number theory, but is it really a bitcoin "development and technical discussion"? I don't think so. Some posts are off topic but the "number theories" over the last few pages are trying to determine if you can reuse previous kangaroo work. Therefore, it is for the development of this Pollard's kangaroo ECDLP solver. And what is relevant to bitcoin development here? Nothing! The whole thread belongs to the off-topic subforum, IMO.
|
|
|
|
Jean_Luc (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 09:05:16 AM |
|
50 pages and 2.25BTC unlocked in less than 2 months ! Rather a good score, no ?
|
|
|
|
keychainX
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 378
Merit: 53
Telegram @keychainX
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 09:07:38 AM |
|
What's the point of this thread after all? Bragging with number theory algorithms ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) Fifty pages, one thousand posts, so many merits, ... what does it have to do with bitcoin? Seriously, I don't get it. I understand bitcoin has roots in cryptography it is called cryptocurrency after all and cryptography is mostly, if not all, about number theory, but is it really a bitcoin "development and technical discussion"? I don't think so. Some posts are off topic but the "number theories" over the last few pages are trying to determine if you can reuse previous kangaroo work. Therefore, it is for the development of this Pollard's kangaroo ECDLP solver. And what is relevant to bitcoin development here? Nothing! The whole thread belongs to the off-topic subforum, IMO. The whole point is to find a backdoor to break bitcoin private keys. The Pollard algo can be used in many ways to decrease the search space so in my opinion it has a lot to do with Bitcoin. /KX
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 895
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 09:26:59 AM |
|
50 pages and 2.25BTC unlocked in less than 2 months ! Rather a good score, no ?
yes this is good score. Not listen all not health critics.
|
[
|
|
|
RXUser
Newbie
Offline
Activity: 7
Merit: 5
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 10:01:48 AM |
|
Yes just ignore the off-topic spams. thanks for this thread, it is very relevant and not only to Bitcoin development.
|
|
|
|
aliashraf
Legendary
Offline
Activity: 1456
Merit: 1174
Always remember the cause!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 10:53:30 AM |
|
50 pages and 2.25BTC unlocked in less than 2 months ! Rather a good score, no ?
No!
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 895
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 10:55:49 AM |
|
50 pages and 2.25BTC unlocked in less than 2 months ! Rather a good score, no ?
No! Go away from there, ok ?
|
[
|
|
|
Etar
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 03:59:46 PM |
|
@arulbero test with 1000 pub keys fulfilled. Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit. Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' ) -xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53) 1000 keys was generated in range 40000000000000:7fffffffffffff Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4 Expected operations 2^28.06 Total op was 261530636052 = 2^37.93 In average 2^27.98
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 895
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 04:11:15 PM |
|
@arulbero test with 1000 pub keys fulfilled. Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit. Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' ) -xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53) 1000 keys was generated in range 40000000000000:7fffffffffffff Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4 Expected operations 2^28.06 Total op was 261530636052 = 2^37.93 In average 2^27.98
Hello "Total op was 261530636052 = 2^37.93" this for 1000 pubkey or only one ?
|
[
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 04:16:08 PM Last edit: June 18, 2020, 05:06:54 PM by arulbero |
|
@arulbero test with 1000 pub keys fulfilled. Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit. Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' ) -xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47, 71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53) 1000 keys was generated in range 40000000000000:7fffffffffffff Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4 Expected operations 2^28.06 Total op was 261530636052 = 2^37.93 In average 2^27.98
Many thanks. The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit? If you have generated 2^25.08 points, then: (2^x + 2^25.08) tame * (2^x) wild = 2^54 couples 2^(2x) + 2^(25.08)*2^x - 2^54 = 0 --> x = 2^26.81 Then you should have computed on average 2^26.81 tame-steps + 2^26.81 wild-steps = 2^27.81 steps
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 895
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 04:17:19 PM |
|
@arulbero test with 1000 pub keys fulfilled. Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit. Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' ) -xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53) 1000 keys was generated in range 40000000000000:7fffffffffffff Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4 Expected operations 2^28.06 Total op was 261530636052 = 2^37.93 In average 2^27.98
Many thanks. The gain (- 5,7%) is little, how many DPs did you have generate for the key in 49 bit? Etar, this is a CPU or GPU version ?
|
[
|
|
|
Etar
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 05:10:07 PM Last edit: June 18, 2020, 05:20:22 PM by Etar |
|
-snip- The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit? -snip-
DP Count : 240568 2^17.876 in 49bit workfile. i have source file and converted file. I can share if you want to verify DPs. But each DP after multiplication was verifed with G' and x-coordinate correct. DP bits : 8 Start : 40000000000000 Stop : 7FFFFFFFFFFFFF Key : 025C396BA4347253BBAAFFAC6D4F9BA092847B27F2599EB2EB225DDA54F9964190 Count : 0 2^-inf Time : 00s DP Size : 9.3/30.6MB DP Count : 240568 2^17.876 HT Max : 8 [@ 01D30E] HT Min : 0 [@ 000001] HT Avg : 0.92 HT SDev : 0.95
-snip- "Total op was 261530636052 = 2^37.93" this for 1000 pubkey or only one ?
For 1000 pubkeys -snip-
Etar, this is a CPU or GPU version ?
Test done on CPU
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 895
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 05:22:22 PM |
|
"For 1000 pubkeys"
Think I not understand something but, for 1000 pubkeys 2^37.93 is very fast.
|
[
|
|
|
Etar
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 05:27:07 PM |
|
"For 1000 pubkeys"
Think I not understand something but, for 1000 pubkeys 2^37.93 is very fast.
expected op for 1 pub = 2^28.06 1000 pubkeys ~2^ 9.965 2^28.06*2^9.965=(28.06+9.965)=2^38.025 So 2^37.93 is little-little bit faster then expected
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 05:31:12 PM |
|
-snip- The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit? -snip-
DP Count : 240568 2^17.876 in 49bit workfile Then you have computed 2^17.876 * 2^8 = 2^25.876 points, (2^x + 2^25.876) tame * (2^x) wild = 2^54 couples --> x = 26.67 In theory it would be enough 2^27.67 steps instead of 2^27.98. To get 2^27.98, it is like 2^25.876 was worth about 2^21.8, the effect of reuse of old DPs is reduced by a factor of 16.
|
|
|
|
Etar
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 05:41:23 PM |
|
-snip-
To get 2^27.98, it is like 2^25.876 was worth about 2^21.8, the effect of reuse of old DPs is reduced by a factor of 16.
I think that for birthday paradox is a big difference between have 16Tame DP and 2 wild DP or 9tame and 9wild. Maybe if Kangaroo app first launch wild (as you say somewhere above) gain the same amount as tame DPs maybe in this case we will have faster result.
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 06:06:54 PM Last edit: June 18, 2020, 06:19:49 PM by arulbero |
|
-snip-
To get 2^27.98, it is like 2^25.876 was worth about 2^21.8, the effect of reuse of old DPs is reduced by a factor of 16.
I think that for birthday paradox is a big difference between have 16Tame DP and 2 wild DP or 9tame and 9wild. Maybe if Kangaroo app first launch wild (as you say somewhere above) gain the same amount as tame DPs maybe in this case we will have faster result. Yes, but in that case there is no big difference: (2^x + 2^25.876) tame * (2^x + 2^25.876) wild = 2^54 couples 2^x + 2^25.876 = 2^27 x = log2(2^27-2^25.876) = 26.1 --> only 2^26.1 tame + 2^26.1 wild + 2^25.876 wild steps are needed -> 2^27.61
|
|
|
|
Jean_Luc (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 06:07:55 PM |
|
The best time complexity with the birthday paradox and kangaroo having a starting position uniformly distributed in [0..N] is obtained when drawing alternatively one tame and one wild. When using DP0, you get ~2.sqrt(N). When using DPx, it is like drawing alternatively 2^x TAME and then 2^x WILD, you have then a DP overhead. I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel. For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta). So it is important to choose a DP such as k.theta << sqrt(N).
|
|
|
|
Etar
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 06:22:40 PM |
|
The best time complexity with the birthday paradox and kangaroo having a starting position uniformly distributed in [0..N] is obtained when drawing alternatively one tame and one wild. When using DP0, you get ~2.sqrt(N). When using DPx, it is like drawing alternatively 2^x TAME and then 2^x WILD, you have then a DP overhead. I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel. For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta). So it is important to choose a DP such as k.theta << sqrt(N).
In that case best choice for solving keys is using CPU ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) i7 7 thread 20Mop/s and 7168 kangaroos 2080ti 1.4Gop/s and 4464292 kangaroos 1.4Gop/s / 20Mop/s = 70 CPU the same speed but also only 501760 Kangaroos, 8.9 times less DP overhead. ![Wink](https://bitcointalk.org/Smileys/default/wink.gif)
|
|
|
|
brainless
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 318
Merit: 34
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 18, 2020, 06:30:51 PM |
|
-snip- The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit? -snip-
DP Count : 240568 2^17.876 in 49bit workfile. i have source file and converted file. I can share if you want to verify DPs. But each DP after multiplication was verifed with G' and x-coordinate correct. DP bits : 8 Start : 40000000000000 Stop : 7FFFFFFFFFFFFF Key : 025C396BA4347253BBAAFFAC6D4F9BA092847B27F2599EB2EB225DDA54F9964190 Count : 0 2^-inf Time : 00s DP Size : 9.3/30.6MB DP Count : 240568 2^17.876 HT Max : 8 [@ 01D30E] HT Min : 0 [@ 000001] HT Avg : 0.92 HT SDev : 0.95
-snip- "Total op was 261530636052 = 2^37.93" this for 1000 pubkey or only one ?
For 1000 pubkeys -snip-
Etar, this is a CPU or GPU version ?
Test done on CPU Etar if i am not wrong you have 49 bit 1000 pubkeys you shift dp file to 54 bit and you have this info " Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 " if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange 76 bit = 75557863725914323419135 54 bit = 18014398509481983 distance = 4194303 for 1000 pub key and for 1 pubkey = 419.4303 and for 32*g = 134217.72 in short you used tooo much time as compare to equal 76 bit work hope u understand
|
13sXkWqtivcMtNGQpskD78iqsgVy9hcHLF
|
|
|
|