Bitcoin Forum
October 12, 2024, 04:20:43 AM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1]
1  Bitcoin / Bitcoin Discussion / Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it on: October 11, 2024, 01:12:50 PM
There isn't a single paper that says to use random starting points when we have multiple kangaroos per herd; on the contrary, they start from well-defined positions. To use random start points is an arbitrary decision: first of all, on average, it degrades the expected runtime; second, it's used for spin-off strategies, like in Bernstein's pre-computation paper "Computing discrete logs faster".

Well, papers are about theory mostly.
Again, in practical implementation you have to use random start points because you don't know exact number of GPUs you will use during solving (because it's a long process and some GPUs can be turned on and off, or added/removed), also sometimes some GPUs will start new kangs.
2  Bitcoin / Bitcoin Discussion / Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it on: October 11, 2024, 12:16:59 PM
Quote
JLP did a great job by making his work open-source.
Though when I see K=2.08, or 3-4GH on 4090, or his code, or that annoying bug with displayed speed higher than real speed, problems with handling large db, etc... Yeah, it definitely looks like free open source  Grin
Anyway, it's a great start point.
3  Bitcoin / Bitcoin Discussion / Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it on: October 11, 2024, 11:21:13 AM
Here's another kicker: Kangaroo doesn't rely on the birthday paradox. That would be Gaudry-Schost.

Correct.
But in practice, nobody implements original kangaroo with only few kangs. Practical implementation always contains a lot of kangs with random start points and they don't go far, so it's exact or similar to Gaudry-Schost and it does use birthday paradox.
4  Bitcoin / Development & Technical Discussion / Re: 5-7 kangaroo method on: October 10, 2024, 09:58:42 PM
Stop promoting garbage. If you precompute certain values, you might lose the effect of the birthday paradox in the sense that you are reducing randomness and possible combinations. Precomputation can make the problem more deterministic and less dependent on the random coincidences that make the birthday paradox so surprising. You are leading people into a void.

Excellent!  Grin
I think now it's time for some magic circles, don't hesitate!
5  Bitcoin / Development & Technical Discussion / Re: 5-7 kangaroo method on: October 10, 2024, 06:18:29 PM
If we keep silence, maybe he will go away  Cheesy
6  Bitcoin / Development & Technical Discussion / Re: 5-7 kangaroo method on: October 10, 2024, 03:18:39 PM
You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G

And next step is to calculate required memory for 0.5*sqrt(2^134) points.
After this calculation you will lose all your interest in BSGS  Grin
Or may be you are going to break a lot of <64bit points? Even so, kang is faster because you can have precomputed db of DPs and reduce time in 10 times or even more.


If the goal is to retrieve a private key in a 2^134 interval, there is no doubt: BSGS is not the algorithm to use.

But in a 2^64 interval, BSGS can be faster.  

For one 64bit point without precomputing - yes. For many points - kang with precomputed DPs is faster.
Of course you can do the same for BSGS, precompute more points to speedup it, but it won't be so effective as for kang, to speedup BSGS in 10 times you will have to precompute (and store) much more points than for kang (because BSGS does not use birthday paradox sqrt).
7  Bitcoin / Development & Technical Discussion / Re: 5-7 kangaroo method on: October 10, 2024, 02:47:51 PM
You only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G

And next step is to calculate required memory for 0.5*sqrt(2^134) points.
After this calculation you will lose all your interest in BSGS  Grin
Or may be you are going to break a lot of <64bit points? Even so, kang is faster because you can have precomputed db of DPs and reduce time in 10 times or even more.
8  Bitcoin / Development & Technical Discussion / Re: 5-7 kangaroo method on: October 08, 2024, 07:49:38 PM
OK, I don't insist, see no reasons to do that if you are happy with 1.7 Grin
9  Bitcoin / Development & Technical Discussion / Re: 5-7 kangaroo method on: October 08, 2024, 04:26:12 PM
Such papers is just a way to get a degree, zero new ideas.
And all this is not important actually.
The main problem that you won't get better than K=1.7 this way even if you use 1000 instead of 3-4-5-7 kangs.
K=1.7 is boring, really. It's like solving puzzles #6x  Grin
Why don't you try this? https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf
Going this way (a long way btw) you can "invent" something interesting and get real K (not in theory but real) around 1.2 if you are smart enough Cheesy I call this approach "mirrored" kangs.
But, of course, this way is not so easy as "normal" kangs that always jump in one direction.
Just a tip for you because it seems you read some papers instead of creating magic circles/code as most people here Cheesy
Though I doubt that you will break #135, it's always fun to invent and discover so you can spend a lot of time having fun...
10  Bitcoin / Bitcoin Discussion / Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it on: October 06, 2024, 12:55:36 PM
Meanwhile, 3Emi...YESs probably already spinning up his ASICs for 135.

Everybody can see that the same person has solved three puzzles in a row, but still there are people who think that they can solve #135 faster.
Well, good luck  Grin
Pages: [1]
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!