Bitcoin Forum
September 19, 2019, 09:35:30 AM *
News: Latest Bitcoin Core release: 0.18.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 [14] 15 16 17 18 19 20 »  All
  Print  
Author Topic: Bitcoin challenge transaction: ~100 BTC total bounty to solvers!  (Read 9372 times)
MrFreeDragon
Jr. Member
*
Offline Offline

Activity: 34
Merit: 2


View Profile
August 29, 2019, 11:15:04 PM
 #261

I am at 1080ti maximum reached 380 Mkey / s. This is probably normal relative to 1070 and AMD. I wonder why 2080ti is more powerful in ~ 3 times than 1080ti, it should be about ~ 30% (500 Mkey / s). Due to what such a gap, have thoughts?

Can you please tell your configuration for 1080ti? (b, t, p and any other relevant info). What CUDA do you use? (9.2 or the newest 10.1).
I tried on the week to test 1080ti (Gigabyte Gaming OC 11Gb) and received thr result 150 Mkey/sec (as another guy posted earlier) with -b 56 -t 512 -p 2048.
1568885730
Hero Member
*
Offline Offline

Posts: 1568885730

View Profile Personal Message (Offline)

Ignore
1568885730
Reply with quote  #2

1568885730
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1568885730
Hero Member
*
Offline Offline

Posts: 1568885730

View Profile Personal Message (Offline)

Ignore
1568885730
Reply with quote  #2

1568885730
Report to moderator
vimp666
Newbie
*
Offline Offline

Activity: 22
Merit: 0


View Profile
August 30, 2019, 11:28:39 AM
Last edit: August 30, 2019, 01:21:12 PM by vimp666
 #262

I am at 1080ti maximum reached 380 Mkey / s. This is probably normal relative to 1070 and AMD. I wonder why 2080ti is more powerful in ~ 3 times than 1080ti, it should be about ~ 30% (500 Mkey / s). Due to what such a gap, have thoughts?

Can you please tell your configuration for 1080ti? (b, t, p and any other relevant info). What CUDA do you use? (9.2 or the newest 10.1).
I tried on the week to test 1080ti (Gigabyte Gaming OC 11Gb) and received thr result 150 Mkey/sec (as another guy posted earlier) with -b 56 -t 512 -p 2048.
experiments. I think you need to gradually increase the parameter -b. You can also raise the parameter -p (this uses the memory of your card).try for example like this  -b 80 -t 512 -p 4000 or  -b 88 -t 256 -p 4500 or  -b 60 -t 512 -p 6000  etc. change the parameters and...experiments....experiments....experiments....
MeBender
Newbie
*
Offline Offline

Activity: 24
Merit: 0


View Profile
August 30, 2019, 01:44:54 PM
 #263

I am at 1080ti maximum reached 380 Mkey / s. This is probably normal relative to 1070 and AMD. I wonder why 2080ti is more powerful in ~ 3 times than 1080ti, it should be about ~ 30% (500 Mkey / s). Due to what such a gap, have thoughts?

Can you please tell your configuration for 1080ti? (b, t, p and any other relevant info). What CUDA do you use? (9.2 or the newest 10.1).
I tried on the week to test 1080ti (Gigabyte Gaming OC 11Gb) and received thr result 150 Mkey/sec (as another guy posted earlier) with -b 56 -t 512 -p 2048.
experiments. I think you need to gradually increase the parameter -b. You can also raise the parameter -p (this uses the memory of your card).try for example like this  -b 80 -t 512 -p 4000 or  -b 88 -t 256 -p 4500 or  -b 60 -t 512 -p 6000  etc. change the parameters and...experiments....experiments....experiments....

Just want to add that you should increase -p in multiples of 512
PrivatePerson
Newbie
*
Offline Offline

Activity: 14
Merit: 0


View Profile
August 30, 2019, 03:49:30 PM
 #264

Let's discuss the Pollard's kangaroo script from 57fe since it is not possible to register on its forum. Has anyone managed to increase the speed above 150k? And who understands, explain what the lines mean 5-8:

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8


This is the easiest part  Grin All these integers are determined by bitcoin mathematics in ECDSA. Gx and Gy are x, y coordinates of the base point (G) which is used to produce private key. Modulo is the mod of the field (like border). Order is the order of the fiels, i.e the total number of points of ECDSA curve.


if I want to look for any other bitcoin key (I guess it takes a very long time), I do not need to change these lines? Only lines 168-176 and 178?
MrFreeDragon
Jr. Member
*
Offline Offline

Activity: 34
Merit: 2


View Profile
August 30, 2019, 08:15:34 PM
 #265

if I want to look for any other bitcoin key (I guess it takes a very long time), I do not need to change these lines? Only lines 168-176 and 178?

These are the constant numbers. They are always the same for bitcoin.
Raj Lassi
Newbie
*
Offline Offline

Activity: 15
Merit: 1


View Profile
August 31, 2019, 01:41:32 AM
 #266

Distributed Random Brute Force

I don't have the GPU power to make any progress with sequential brute force.
I also found, by experiment, that guessing random numbers can take much longer.

So, to maximize the fun, I am doing both. 
I distribute the scan over the 20-3F keyspace, pick 3 random bytes, and brute force the rest.

My ranges look like this: (where XXXXXX is 3 random bytes)

[20-3F][XXXXXX]00000000 - [20-3F][XXXXXX]FFFFFFFF

My old card can try fifteen 3-byte randoms per scan, every 13 hours, at 44Mkey/s.  Plus about 2 million really random randoms with the leftover starting points.

What does that get me?

15 random blocks of 4.3 billion keys in each of 32 sub-ranges [20-3F] per scan = 2 trillion.  4T/day.  Pffft.

so, every 26-hour day, scanning the following:
128 B keys in 20XXXXXX00000000-20XXXXXXFFFFFFFF
128 B keys in 21XXXXXX00000000-21XXXXXXFFFFFFFF
128 B keys in 22XXXXXX00000000-22XXXXXXFFFFFFFF
.
.
.
128 B keys in 3DXXXXXX00000000-3DXXXXXXFFFFFFFF
128 B keys in 3EXXXXXX00000000-3EXXXXXXFFFFFFFF
128 B keys in 3FXXXXXX00000000-3FXXXXXXFFFFFFFF


i just need to get lucky with 3 bytes.  how hard can that be?Huh
or, get lucky with 2 bytes, but wait a week to find out.  that shouldn't take much more than 65535 weeks.




So, speaking of case 61:

In my case, what I do is mix randomness with full range scan. I keep the range small enough to get reasonable waiting time (say 10 min) .
This is an example:

1) generate all possibles 5 bits number: 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 

2) pick a random 5 hex digit number (20bit) : for instance CADE9
we have now 16 possibles header for our key

10CADE9
11CADE9
12CADE9
13CADE9
14CADE9
15CADE9
16CADE9
17CADE9
18CADE9
19CADE9
1ACADE9
1BCADE9
1CCADE9
1DCADE9
1ECADE9
1FCADE9

3) call 16 instances of Bitcrack fully scanning following 16 ranges

10CADE9000000000:10CADE9FFFFFFFFF
11CADE9000000000:11CADE9FFFFFFFFF
12CADE9000000000:12CADE9FFFFFFFFF
13CADE9000000000:13CADE9FFFFFFFFF
14CADE9000000000:14CADE9FFFFFFFFF
15CADE9000000000:15CADE9FFFFFFFFF
16CADE9000000000:16CADE9FFFFFFFFF
17CADE9000000000:17CADE9FFFFFFFFF
18CADE9000000000:18CADE9FFFFFFFFF
19CADE9000000000:19CADE9FFFFFFFFF
1ACADE9000000000:1ACADE9FFFFFFFFF
1BCADE9000000000:1BCADE9FFFFFFFFF
1CCADE9000000000:1CCADE9FFFFFFFFF
1DCADE9000000000:1DCADE9FFFFFFFFF
1ECADE9000000000:1ECADE9FFFFFFFFF
1FCADE9000000000:1FCADE9FFFFFFFFF
 
goto step 2 and repeat.

each cycle will take 16*10min = 160 min if you have one GPU.

This trick will increase your likelihood in finding the key as times increases and not wait 180 years (1GPU) or 5 years (36GPUs). LOL
   
a random 5 hex digit is one of 1,048,575  if you get it right, you have the key in 160 min with only one GPU Wink

 


This looks like a suggestion I've made a while ago  Wink


hahaha cool.  i made some tweaks to BitCrack so i can set whatever starting points i want.  I have it count to FFFF and restart with a new batch of points.  it writes everything it has tried to a file.  It has not picked the same random 3 bytes yet, nor has any scan overlapped any ranges posted here.  i will be lazy and wait until it does before coding anything to prevent that. Tongue
Telariust
Jr. Member
*
Offline Offline

Activity: 35
Merit: 15


View Profile
August 31, 2019, 10:12:18 AM
Last edit: September 18, 2019, 04:35:54 PM by Telariust
 #267

origin link
https://fe57.org/forum/thread.php?board=4&thema=1#1

..Let's discuss the Pollard's kangaroo script from 57fe since it is not possible to register on its forum. Has anyone managed to increase the speed above 150k?..
Let's!

I will conduct a lot of tests and update this post.
Last update at Sep 18 2019, edit#32

#################
Notice, about power, it is the same

2123 == 2^(123) == 2**(123) == pow(2,123) == pow2(123) == 1<<123
sqrt(2) == 21/2 == 2**0.5

2123 - only this forum, outside of quote/code tags
2** - its python specific
pow() - popularity in many programm langs
2^ - classic old standart math text format, so i use it in 99%, not beautiful but it works

here x^y is math text format of power as xy and not bit operation xor as [x xor y], do not confuse!
#################
# gmpy2

When I ported the code to coincurve lib, I was surprised to find that gmpy2 is faster.
Until this moment, I have not seen an implementation faster than in coincurve, my respect!
1core i5-2540 python37x64 win7x64
Code:
coincurve: 30528.2 j/s
coincurve+cffi: 41165.6 j/s
gmpy2: 90194.8 j/s
(with python27x64 -10%)
(on linux +20% and more!)

how to install gmpy2 on windows
 1) download file .whl from https://www.lfd.uci.edu/~gohlke/pythonlibs/
 2) put to root dir of python
 3) install
Python27>python -m pip install gmpy2-2.0.8-cp27-cp27m-win_amd64.whl
Python37>python -m pip install gmpy2-2.0.8-cp37-cp37m-win_amd64.whl

#################
# speed cpu

Quote
..Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code..
..because this is the limit of computation on the cpu
take for example break_short
1core i5-2540 = 0,16 Mkeys/s (C secp256k1 x64 without calc Y) (A + J -> J; xJ -> xA)
add(points) using every loop in break_short
add(points) using every jump in kangaroo
therefore their speed is equivalent

#################
# about kangaroos algo by 57fe

Quote
..Now we give the improved algorithm of [11] (for a serial computer).
The two kangaroos now make alternate jumps, and T starts at the middle of the interval, i.e. x0 = rM , where M = [(L + U)/2].
Whenever xi falls in D, we store the pair (xi, di) together with the name of the kangaroo (T or W).
This information may be stored in a hash table, hashing on xi.
When some xi is stored for the second time, having been reached by both kangaroos, we can compute the solution.
Thus, if xi(forT)=x'j(forW), we have z = M + di - d'j .
In this version, unlike [5], we do not know which kangaroo is in the lead,..
this is based of [5]

Quote
Launch m/2 tame kangaroos with starting points g(b/2)+iv, for 0=i<m, where v is a small constant
(avoid a power of 2 for v so that the probability of tame kangaroos following the same path is not abnormally high).
At the same time, launch m/2 wild kangaroos with starting points ygb+iv, for 0<=i<m.
Whenever a kangaroo lands on a distinguished point, store it in a list common to all processors.
With each distinguished point, store a flag indicating the kangaroo type (tame or wild) and the distance
from g0 (for tame kangaroos) or from y (for wild kangaroos).
Suppose that a kangaroo reaches a distinguished point that is already in the list.
If the kangaroos are of the same type, then move the trailing kangaroo forward by some small random distance so that it will not repeat the other kangaroo’s path.
If the distinguished point was produced by kangaroos of different type, then subtract the distances to get the desired logarithm and we are done.
and this is parallelism of [11]

[5] J. M. Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., #32 (1978)
[11] P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, J. Cryptology, #12 (1999)

I studied the source:
 - used pre-calc Set jumps with size pow2 (by Pollard)
 - creates 8 Tame kangaroos + 8 Wild kangaroos (idea 1T+1W by Oorschot&Wiener of [11]);
..but why 8/8?? 1/1 be must norm.. if set 1/1 - speed drops - calculation of jumpsize and startrange not optimal..
..i think, author try fix low efficiency (see below "anomaly detected"), or its trick to avg runtime, but fact - its slower -30%
(answer: variable kangoo_power (number kangaroos in herd) affects the step size, so the illusion is created that T8+W8 is optimal, although in fact it should not differ from T1+W1)
 - gradually added new distinguished points in T+W sets that pass through DP_rarity (distinguished points for economy ram by Oorschot&Wiener);
hmm... has problem:
Quote
..where 0 <= uj,vj < r are chosen uniformly at random..
...
Launch m/2 tame kangaroos with starting points g(b/2)+iv, for 0 <= i < m, where v is a small constant
(avoid a power of 2 for v so that the probability of tame kangaroos following the same path is not abnormally high).
...
We analyse a variation of their method, which avoids thepossibility of “collisions” between members of the same herd.
The numbers of kangaroos in the herds will be coprime integers u and v, nearly equal, with u+v=P.
Thus if P=4p, we could take u=2p+1 and v=2p-1. Their jumps will all be multiples of uv..
coprime integers! or 2p(+/-)1 integers! not equal random.randint(1,(1<<(problem-1))) !
and uniqueness new point is not checked.
some kangaroos can falls into the trap of same sequences (without new distinguished points);
Quote
..If the kangaroos are of the same type, then move the trailing kangaroo forward by some small random distance so that it will not repeat the other kangaroo’s path..
this reduces speed, jumps indicating norm, but really there are many calculation useless same sequences.
Quote
..If there is a collision between two kangaroos of the same herd then it will eventually be detected when the second one lands on the same distinguished point as the first.
In [473] it is suggested that in this case the server should instruct the second kangaroo to take a jump of random length so that it no longer follows the path of the front kangaroo.
Note that Teske [606] has shown that the expected number of collisions within the same herd is 2, so this issue can probably be ignored in practice.
omg, but ok

#################
# Most famous optimizations of Pollard
# about complexity, runtime and RAM

Quote
1) not use distinguished points (early, of [5])
..runtime of approximately 3.28w1/2 group operations
minimal RAM

 2) use distinguished points
..The kangaroo method (of [11, p. 13]) can solve in about 2w1/2 expected operations..
It is expected to take 1.64 times faster than early, of [5].
need more RAM for saved points

why use distinguished points more efficiency
Quote
..by keeping previous data, the number of collisions found grows as the square of the time spent..
(because, the number of pairs of points grows as the square of the number of points produced)

 "three-kangaroo algorithm"
("Using Inversion", but I think it means symmetry of Y)
One can perform a version of the kangaroo method with three kangaroos:
One tame kangaroo starting from g^u for an appropriate value of u and two wild kangaroos starting from h and h^(-1) respectively.
runtime (average-case expected) of 1.897w1/2 group operations if m=0.316w1/2 (m is avg size 1 jump)
runtime (average-case expected) of 1.818w1/2 group operations if m=0.375w1/2

 "four-kangaroo algorithm"
runtime (average-case expected) of 1.714w1/2 group operations if m=0.375(2w1/2)


other algo avg runtime for compare

 "Gaudry-Schost algorithm"
The basic idea of the Gaudry-Schost algorithm is as follows. One has pseudorandom walks in two (or more) subsets of the group such that a collision between walks of different types leads to a solution to the discrete logarithm problem.
runtime (average-case expected) of 1.660w1/2 group operations

 "Baby-step Giant-step” method of Shanks
runtime (average-case expected) of (3/2)w1/2 group operations if first compute Baby and save in hashtable
runtime (average-case expected) of (4/3)w1/2 group operations if compute both sets at the same time (double RAM)
very more RAM, w1/2

pollard-rho
Theorem1 - 1.25w1/2
Quote
..Theorem1 makes the assumption of true randomness.
However, it has been shown empirically that this assumption does not hold exactly for Pollard’s iteration function.
The actual performance is worse than the expected value given in Teske..
In prime order subgroups.. is 1.55w1/2 and Teske is 1.27w1/2
..while in groups of points of elliptic curves over finite fields.. is 1.60w1/2 and 1.29w1/2
1) Floyd improvement, y value is updated at each step y=F(F(y))
gcd is calculated for N and (y-x)
Floyd’s method needs on average 2.47(lt + lh) group operations (2.47 is three times the expected value of the epact).
2) Brent improvement (Brent improves Floyd)
check only (xi, xj), where j=2^k; k=1,2,3..a; i=[2^k+1; 2^(k+1)]
Brent has given an improved cycle finding method that still only requires storage for two group elements but which requires fewer group operations.
Brent’s method is 30-40% faster than Floyd’s. minimal RAM.
3) Teske improvement, used 20 kangaroo instead of 3(rho), +20%.
..running time the assumption is made that a random walk in the underlying group is simulated.
..this assumption does not hold for the walk originally suggested by Pollard: its performance is worse than in the random case.
..introduce a class of walks that lead to the same performance as expected in the random case.

Quote
Thus the complexity of Pollard rho method is determined by the size of the base group G on which random walk is performed and the running time of the iterating function.
Reducing either one of these two factors will result in speedup of the Pollard rho
...
In fact, the result on generic algorithm complexity implies that, to achieve results better than normal Pollard rho, we should either exploit the group encoding or invent a method that mostly uses the fastest of the group operations.

#################
# Compare pollard-rho vs pollard-kangaroo(lambda method*)

*parallel version rho resembles an image of the shape of the greek letter lambda, do not confuse!
*endomorphism have the constant is called lambda, do not confuse!

pollard-rho method effective for full field size Fp;
pollard-kangaroo method effective for partly field size Fp;
we can use rho for partly Fp, but runtime will remain as for full;
we can use kangaroo for full Fp, but it is about 1.60 times slower than rho; it becomes faster when b < 0.39p;

#################
# batch inversion, affine/jacobian, endomorphism, symmetry Y

Batch inversion is impossible.
Because its  adding single points with pseudo random size step, instead total sequential compute.

Quote from: arulbero
"Are you using affine or jacobian coordinates for the points?"
its affine
Code:
# A + A -> A
# 1I, 2M, 1S
def add(P, Q, p=modulo):
R = Point()
dx = Q.x - P.x
dy = Q.y - P.y
if flag_gmpy2: # 1I, 1M
c = dy * gmpy2.invert(dx, p) % p
else:
c = dy * rev(dx, p) % p
R.x = (c*c - P.x - Q.x) % p # 1S
R.y = (c*(P.x - R.x) - P.y) % p # 1M
return R
But it's useless, we cannot economy multiples without batch inversion.

..how about using jacobian coordinates for adding points?
(to economy on inversions, 1I equal 20M, its very expensive)
Quote
One often uses projective coordinates to speed up elliptic curve arithmetic, so it is natural to use
projective coordinates when implementing these algorithms. But to define the pseudorandom walk one
needs a unique representation for points, so projective coordinates are not appropriate. See Remark 13.3.2.
test showed - X jacobian doesnt unique representation and distinguished points not found.
after convert J->A (only X) - all work, but -40% speed. conclusion - A+A->A is optimal. close.

Endomorphism is impossible.
Applying it to X coordinate is the same as changing discriminator(DP_rarity) - it will not give acceleration.
Speed depends only on number and size of jumps.

SymmetryY used in "three-kangaroo algorithm".
but 1.818w1/2 vs 2w1/2 very small speed-up efficiency. close.
SymmetryY used in "four-kangaroo algorithm"
1.714w1/2 ..its (1.7/2)*100 = +15%. close.


lol, in python x*x*x*... more faster than x**y

and byte_shift 1<<123 more fastest (x10) than 2**123

#################
# popular questions
# I carefully read your posts in the thread and reply to them here

Quote
Why does the work suddenly increase (by a factor of about 8 to 10, depending on time or jumps)
Quote
why do you need 10 Ntimeit(N_tests)?
Algo of Pollard is probablistic nature (Birthday Paradox, Kruskal's card trick, etc)
The solution time is not stable; several attempts are needed to obtain the avg runtime and jumps.
Quote
..(heuristic time rather than deterministic)..
######
Quote
why need
pow2kang/kangoo_power = 3
its pow2 of number of kangaroos in herd T/W, affects max size jump, affects discriminator (DP_rarity)
######
Quote
pubkeys = {
   , 33: ('02ed949eaca31df5e8be9bf46adc1dfae1734b8900dcc303606831372955c728da', False) #0x01abcd1234
   ,105: ('03bcf7ce887ffca5e62c9cabbdb7ffa71dc183c52c04ff4ee5ee82e0c55c39d77b', False)
..what does 3 column mean? And why do 33 and 105 matter False?..
it private key for double-check solution (demo/debug mode)
False if it unknow (recovery mode)
######
Quote
what i don't understand is , if 250 bit address can be found in 570 second.
then why, we can't find 2105 bits of puzzle address in 1140 second? or bit more? but why it takes so much time than it should simply do...
105/50=2,1 ? not, wrong logic!
250  = 1125899906842624
2105 = 40564819207303340847894502572032
2105/250 = 36028797018963968 times more?
..no, its square dependence - need sqrt: x1/2
((2105)1/2) / ((250)1/2) =
 ((40564819207303340847894502572032)1/2) / ((1125899906842624)1/2) =
6369051672525772 / 33554432 =
189812531 times more! its right result
and now if 250 found in 570sec, then 2105 is
189812531 * 570 = 108193142670 sec = 3478y  5m  5d 10:44:30s
######
Quote
..multi pubkeys at once check inside bit range..
..this script check only 1 pubkey in bit range..
..but would it work does someone a test if multiple pub keys work?..
yes, only 1
"multi" check at the cost of "multi" drop in performance!
(if u dont know, break_short has the same problem on Gigant-step calc)
sry, but no
######
Quote
The Pollard-Kangaroo ... seems to find keys even when the specified bit size doesn't match the key mask, but it does take longer. I guess the bits parameter is a hint at where to start searching, rather than a maximum search space limit.
Pollard answers
Quote
If z is outside the interval, the algorithm will still work but will take longer.

#################
# CPU build

Python, dev status, add/fix::
 - python2/3 compatibility (print/time/input/xrange/IntDiv)
 - auto adaptation under environment
 - raw python/coincurve+cffi/gmpy2
 - some checks, debug, more info, minor accelerate
 - (un)compress/custom/random pubkey
 - format time: 0y 0m 0d 00:00:00s 000ms
 - format prefix SI: Kilo/Mega/Giga/Tera/Peta/Exa
 - heuristic prognosis (avg)time and (avg)jump per bits
 - repair kangaroos, that falls into the trap of same sequences
 - location privkey in keyspace on the strip
 - percent status progress, lost/left time
 - support arbitrary range (keyspace) start:end

now support only single core
ps: you can already use option 1) by running script in Ncores copies, manually spliting the search range


Multicore, dev status, add/fix:
1) naive parallelism, split equally the search range
 - warning! the lowest efficiency (w/Ncores)1/2
 - in process, wait..
2) parallelism by Oorschot&Wiener
 - norm efficiency w1/2/Ncores
 - odd numbers U=V=2p+/-1, U+V<=Ncores
 - has problem of collisions between members of the same herd
 - in process, wait..
3) parallelism by Pollard (best choice)
 - norm efficiency w1/2/Ncores
 - coprime number U+V<=Ncores
 - never problem of collisions between members of the same herd
 - in process, wait..

Acceleration on several devices (i.e. with shared RAM) for 2) and 3) (w1/2/Ncores) can only be achieved using the pool.
Filtered distinguished points should be sent to the pool in a single hashtable.


ver 0.9, python2/3, raw/coincurve+cffi/gmpy2
Quote
The message exceeds the maximum allowed length (64000 characters).
source moved to github
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo.py


my cpu benchmark libs
Algo: 1 Tame + 1 Wild with distinguished points,  expected of 2w^(1/2) group operations
1core i5-2540, win7x64
Code:
python2x64
[lib#raw] 7.1K j/s
[lib#coincurve] 24.5K j/s
[lib#coincurve+cffi] 35.4K j/s
[lib#gmpy2] 89.4K j/s

python3x64
[lib#raw] 8.9K j/s
[lib#coincurve] 31.2K j/s
[lib#coincurve+cffi] 43.2K j/s
[lib#gmpy2] 97.8K j/s

1core i7-6820
Code:
python3x64
[lib#gmpy2] 174.3K j/s;


my cpu heuristic prognose
Algo: 1 Tame + 1 Wild with distinguished points,  expected of 2w1/2 group operations
avg stat after 10tests
1core i5-2540, python37x64 + gmpy2, win7x64
Code:
[i] 97.8K j/s;..
...
[prognose] expected of 2w^(1/2) group operations
-------|--------/--------|---------------------------------/---------------------------------|
   W   |jump avg/2w^(1/2)| time                         avg/2w^(1/2)                         |
-------|--------/--------|---------------------------------/---------------------------------|
..
 2^020 |    1.8K/   2.0K |              0d 00:00:00s 018ms /              0d 00:00:00s 020ms |
..
 2^030 |   57.3K/  65.5K |              0d 00:00:00s 586ms /              0d 00:00:00s 670ms |
>2^031 |   81.1K/  92.7K |              0d 00:00:00s 829ms /              0d 00:00:00s 948ms |
 2^032 |  114.6K/ 131.1K |              0d 00:00:01s 173ms /              0d 00:00:01s 341ms |
..
 2^040 |    1.8M/   2.1M |              0d 00:00:18s 777ms /              0d 00:00:21s 471ms |
..
 2^050 |   58.7M/  67.1M |              0d 00:10:00s 886ms /              0d 00:11:27s 086ms |
..
 2^060 |    1.9G/   2.1G |              0d 05:20:28s 355ms /              0d 06:06:26s 759ms |
..
 2^070 |   60.1G/  68.7G |              7d 02:55:07s 378ms /              8d 03:26:16s 292ms |
..
 2^080 |    1.9T/   2.2T |          7m 17d 21:23:56s 096ms /          8m 20d 14:00:41s 355ms |
..
 2^090 |   61.5T/  70.4T |     20y  3m  2d 12:45:55s 095ms /     23y  1m 28d 16:22:03s 390ms |
..
 2^100 |    2.0P/   2.3P |    648y  2m 21d 00:29:23s 067ms /    741y  2m 17d 19:45:48s 481ms |
..
 2^105 |   11.1P/  12.7P |   3.7Ky 10m 29d 06:43:07s 581ms /   4.2Ky 11m 12d 16:12:57s 514ms |
..
 2^110 |   63.0P/  72.1P |  20.7Ky  2m 12d 15:40:18s 166ms /  23.7Ky 11m  0d 08:25:51s 416ms |
..
 2^120 |    2.0E/   2.3E | 663.8Ky  5m 14d 21:29:41s 312ms / 759.0Ky  4m 11d 05:47:25s 328ms |
----------------------------------------------------------------------------------------------


C99, dev status, add/fix:
 - prototype ready!
 - https://bitcointalk.org/index.php?topic=5173445.msg52473992#msg52473992
 - bitcoin-core/secp256k1 library
 - singlecore
 - A+A->A; xA is ready; 0.219Mk/s Mk/s (1core i5-2540)

#################
# GPU build (cuda/opencl)

Quote from: TRINITY
Tank, I need a pilot program for a V-212 helicopter cuda/opencl.. Let’s go.

https://bitcointalk.org/index.php?topic=1306983.msg51796187#msg51796187
https://imgur.com/a/f3zTmTa
thank you, it helped a lot

i imagine how j2002ba2 read topic and thinks
Quote
omg, he used python.. what a primitive primate..
Smiley

article cuda + pollard-rho
https://github.com/beranm14/pollard_rho/blob/master/report/main.pdf

roadmap:
 - rewrite VanitySearch to pollard-kangaroo

in process, wait..

#################
# parallelism problems

Quote
Maybe you can split equally the search range among threads ...

Pollard answers
Quote
6. The Kangaroo Method on a Parallel Computer
..A bad method is to divide the interval [L, U] into P equal parts, and use each of P processors(cores) to search one part, using the serial method. This will take time O((w/P)1/2)..
van Oorschot and Wiener [11] employ two herds of kangaroos in a method which runs in time O((w1/2)/P)..
i.e. if have P cpu and split equally the search range, than speed-up only P1/2

Quote
..The lambda method suffers the same parallelization problem as the rho method..
Note that here each parallel processor is producing its own sequence of points independently of the others and each particular processor
does not increase the probability of success of any other processor.
..m cores have m1/2 accelerate..

Quote
..Suppose that there are P identical artists.
If we use P different sequences (that is, different polynomials F(x)), then the probability that the first k numbers in these sequences will be different modulo p will be approximately equal to exp ((-k^2P)/2p). Thus, the maximum acceleration can be estimated as P1/2..

Quote
One important property of the lambda method is the fact that it is easily distributed on several computers. Each participant in distributed computing selects a random number r and begins to take pseudo-random steps from the number b^r, where b is the element of the group for which a discrete logarithm is sought. Each participant uses the same easily computable pseudorandom function f(G)->S, where S is a relatively small set of numbers with an average value comparable to the size of a group G of order n. The powers a^s for S are calculated in advance..
...
A small difficulty is that a match can occur within the same sequence. However, if the number of participants in the calculations is large enough, then the probability of a match between sequences is greater than the probability of a match within one sequence.
...
The central computer must track all sequences from all participants to identify matches. According to the birthday paradox, a match is expected when the number of elements in all sequences is of the order of O(N1/2). Obviously, in the described form, this method requires a large expenditure of memory of the central computer. The following idea, described by van Orschot, greatly reduces memory requirements and thus makes this method applicable to solving complex problems. The idea is to consider the so-called selected points. It is assumed that the elements of the group are represented by integers (or, possibly, sets of integers). A distinguished binary field of length k in this number will consist of zeros of about (1/2)k of the entire time. A random walk will go through such marked points on average every 2k steps. If two random sequences intersect somewhere, then they will intersect further and together will get to the next selected point. So, the idea is to send only these dedicated points to the central computer, which will reduce the required memory size by 2k times.

Quote
There are two versions of the distributed algorithm, one by van Oorschot and Wiener [473] and another by Pollard [488].
The difference is how they handle the possibility of collisions between kangaroos of the same herd.
The former has a mechanism to deal with this, which we will explain later. The latter paper elegantly ensures that there will not be collisions between individuals of the same herd.

 Van Oorschot and Wiener Version
..kangaroos are spaced a (small) distance s apart..
..If there is a collision between two kangaroos of the same herd then it will eventually be detected when the second one lands on the same distinguished point as the first.
In [473] it is suggested that in this case the server should instruct the second kangaroo to take a jump of random length so that it no longer follows the path of the front kangaroo.
Note that Teske [606] has shown that the expected number of collisions within the same herd is 2, so this issue can probably be ignored in practice.

 Pollard Version
Let N be the number of processors and suppose we can write N=U+V where gcd(U,V)=1 (i.e. U,V is prime numbers) and U,V = N/2.
The number of tame kangaroos is U and the number of wild kangaroos is V.
The (super) kangaroos perform the usual pseudorandom walk with steps {U*V*u0,...,U*V*u(n-1)} having mean m=N(w1/2)/4
(this is UV times the mean step size for solving the DLP in an interval of length w/UV =~ 4w/(N2).
As usual we choose either uj=2j or else random values between 0 and 2m/UV.
The U tame kangaroos start at g(w/2)+i*V for 0 <= i < U.
The V wild kangaroos start at hgj*U      for 0 <= j < V.

Lemma 14.6.5. Suppose the walks do not cover the whole group, i.e., 0 <= an < r (r is order).
Then there is no collision between two tame kangaroos or two wild kangaroos.
There is a unique pair of tame and wild kangaroos who can collide.


#################
How Bitcoin works, a simple explanation.

Private Key is the number N (very large, 2256, so that it is impossible to guess or count).
The Public Key is the point (x, y) on the ec curve type "secp256k1".
privkey is primary, and pubkey is computed from it. They exist in pairs.

Knowing the pubkey is almost impossible to restore its privkey. This is where safety is based.

There is a basic-point (i.e. basic-pubkey but don’t say that), everyone knows it, and the privkey for this point is 1.
To calculate pubkeyX from privkey = X, multiply basic-point by X.

#################
# How pollard-kangaroo works, the Tame and Wild kangaroos, is a simple explanation.

Suppose there is pubkeyX, unknow privkeyX, but privkeyX is in range w=[L..U]
The keys have a property - if we increase pubkey by S, then its privkey will also increase by S.
We start step-by-step to increase pubkeyX by S(i), keeping sumX(S(i)). This is a Wild kangaroo.
We select a random privkeyT from range [L..U], compute pubkeyT.
We start step-by-step to increment pubkeyT by S(i) while maintaining sumT(S(i)). This is a Tame kangaroo.
The size of the jump S(i) is determined by the x coordinate of the current point, so if a Wild or Tame kangaroo lands on one point, their paths will merge.
(we are concerned with pseudo random walks whose next step is determined by the current position)
Thanks to the Birthday Paradox (Kruskal's card trick), their paths will one day meet.
Knowing each traveled path, privkeyX is calculated.
The number of jumps is approximately 2*(w^1/2) group operations, which is much less than a full search w.

#################
# articles
(links from other users, all in one place)

base
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
hand translate to ru/ua (recommend instead translate.google)
https://habr.com/ru/post/335906/

0) best of the best, all in 1, epic,  2012
Chapter 14. Factoring and Discrete Logarithms using Pseudorandom Walks
https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch14.pdf

1) with reference to old
J. M. Pollard, “Kangaroos, monopoly and discrete logarithms,” Journal of Cryptology, #13 (2000).
https://web.northeastern.edu/seigen/11Magic/KruskalsCount/PollardKangarooMonopoly.pdf
(good dir web.northeastern.edu/seigen/11Magic/KruskalsCount/)

2) about parallelism problems
P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, J. Cryptology, #12 (1999)
https://people.scs.carleton.ca/~paulv/papers/JoC97.pdf

advice acceleration tips by fernand77
https://github.com/JeanLucPons/VanitySearch/issues/25#issuecomment-509293732

#################
# polard implementations
(links from other users, all in one place)

kangaroo (now no info), by BurtW, (openssl,secp256k1?)
https://bitcointalk.org/index.php?topic=5173445.0

kangaroo (classic, not use distinguished points), by natmchugh, python
https://bitcointalk.org/index.php?topic=5166284.msg52233957#msg52233957

python, rho
rho, by Andrea Corbellini
github.com/andreacorbellini/ecc/blob/master/logs/pollardsrho.py
rho, by qubd
raw.githubusercontent.com/qubd/mini_ecdsa/master/mini_ecdsa.py
rho, by David Cox 2016
gist.github.com/davidcox143/c68a477b8390f35cb9a19084edd2a1e5
rho, by ralphleon
github.com/ralphleon/Python-Algorithms/blob/master/Cryptology/pollard.py
rho, by thomdixon
gist.github.com/thomdixon/dd1e280681f16535fbf1

other lang
github.com/nikitaneo/rho_pollard
github.com/twjvdhorst/Parallel-Pollard-Rho/
github.com/beranm14/pollard_rho/
github.com/grouville/factrace/

#################
# motivation

..they don`t want to share the tools like Pollard kangaroo script..

Quote from: BENDER
..Well, I’m gonna go build my own theme park, with blackjack and hookers!..

#################

why not use endomorphism for pollard-rho?
point after multiplying by beta is enough pseudo random?
if I'm right, this will be a new superfast method to calculate pollard-rho at the cost of 1M per 1 point
didn’t it occur to anyone before me, I need to test

#################

to be continued..
MrFreeDragon
Jr. Member
*
Offline Offline

Activity: 34
Merit: 2


View Profile
August 31, 2019, 12:56:56 PM
 #268

multicore in process, wait..

to be continue..

Thak you! Nice job :-) By the way, can you explain why do you need 10 Ntimeit? It actually finds the key from the 1st time, and the 2nd, 3d, etc finds the same key (for #32 as i tested). So, what is the reason for doing the same 10 times?

And also, can you confirm that in this Kangaroo method the luck also is important (for high order pubkeys)?
racminer
Member
**
Offline Offline

Activity: 181
Merit: 16


View Profile
August 31, 2019, 11:33:33 PM
 #269


.......................
multicore in process, wait..

to be continue..

Maybe you can split equally the search range among threads ...
bulleteyedk
Jr. Member
*
Offline Offline

Activity: 49
Merit: 1


View Profile
September 01, 2019, 03:04:56 PM
 #270

I read again most of the results posted here, and collected them to one table. Of corse results could differ from card to card depending on the settings. I also add the price of the CUDA. I tried to collect some benchmark. If you have some other device - pls, do not hesitate to add  Roll Eyes

Code:
1. RTX 2080ti    1,200-1,300M key/sec  (price $1,200-1,500)
2. GTX 1070      250 Mkey/sec          (price $450-550)
3. GTX 1080ti    150 Mkey/sec          (price $700-1,000)
4. GTX 680       109 Mkey/sec          (price $150)
5. RX 480        107 Mkey/sec          (price $130-150)
6. RX 470        105 Mkey/sec          (price $150-300)
7. RX 580        89 Mkey/sec           (price $200-250)
8. RX 560        50 Mkey/sec           (price $100-150)
9. R9 280/290x   20 Mkey/sec           (price $50)


Thanks for making this table, i've just tested one of my kids' GTX 770 2GB card and its capable of doing 120MKey/sec
MrFreeDragon
Jr. Member
*
Offline Offline

Activity: 34
Merit: 2


View Profile
September 01, 2019, 06:09:39 PM
Merited by vapourminer (1)
 #271

Table update with bitcrack key/rate per sec:

Code:
1. RTX 2080ti     1,200-1,300 Mkey/sec  (price $1,200-1,500)
2. GTX 2070ti     805 MMkey/sec
2. GTX 1080ti     345 Mkey/sec          (price $700-1,000)
3. GTX 1080       130 Mkey/sec          (price $500)
3. GTX 1070ti     100 Mkey/sec
3. GTX 1070       80-90 Mkey/sec        (price $450-550)
3. GTX 1060       69 Mkey/sec
4. GTX 1050ti     64 Mkey/sec           (price $150-200)
4. GTX 980        70-80 Mkey/sec
4. GTX 770(2Gb)   120 MKey/sec
4. GTX 680        109 Mkey/sec          (price $150)
4. GT 640         9 Mkey/sec     
5. RX 480         107 Mkey/sec          (price $130-150)
6. RX 470         105 Mkey/sec          (price $150-300)
7. RX 580         89 Mkey/sec           (price $200-250)
8. RX 560         50 Mkey/sec           (price $100-150)
9. R9 280/290x    20 Mkey/sec           (price $50)
MrFreeDragon
Jr. Member
*
Offline Offline

Activity: 34
Merit: 2


View Profile
September 01, 2019, 06:19:36 PM
 #272

Thanks for making this table, i've just tested one of my kids' GTX 770 2GB card and its capable of doing 120MKey/sec

How could you manage this? Are you really sure in 120 Mkey/sec with GTX 770? This card GTX 770 cost not so much, and in comparison with GTX 1080ti you can need 3 cards GTX 770 and for the the same (or more) Key/sec rate. But the cost will be 2 times less.
zielar
Member
**
Offline Offline

Activity: 113
Merit: 26


View Profile
September 01, 2019, 06:31:29 PM
 #273

Thanks for making this table, i've just tested one of my kids' GTX 770 2GB card and its capable of doing 120MKey/sec

How could you manage this? Are you really sure in 120 Mkey/sec with GTX 770? This card GTX 770 cost not so much, and in comparison with GTX 1080ti you can need 3 cards GTX 770 and for the the same (or more) Key/sec rate. But the cost will be 2 times less.

GTX 770 = price ~$80-90
GTX 980 = price ~$150-160
GTX 1060 = price ~$240-260
GTX 1070Ti = price ~$280-300
GT 640 = price ~$10-15

Tesla V100 16GB - 1570-1600 Mkey/s = price ~$10000
Telariust
Jr. Member
*
Offline Offline

Activity: 35
Merit: 15


View Profile
September 01, 2019, 06:38:49 PM
 #274

compare
Code:
>cuBitCrack -c -d 0  1AVJKwzs9AskraJLGHAZPiaZcrpDr1U6AB
[2019-09-01.21:24:56] [Info] Compression: compressed
...
[2019-09-01.21:24:56] [Info] Initializing GeForce GTX 1070
[2019-09-01.21:24:56] [Info] Generating 262,144 starting points (10.0MB)
...
GeForce GTX 1070 232/8192MB | 1 target 73.28 MKey/s (403,701,760 total) [00:00:10]
and
Code:
>cuBitCrack -c -d 0 -b 15 -t 512 -p 1024 1AVJKwzs9AskraJLGHAZPiaZcrpDr1U6AB
[2019-09-01.21:24:56] [Info] Compression: compressed
...
[2019-09-01.21:23:20] [Info] Initializing GeForce GTX 1070
[2019-09-01.21:23:21] [Info] Generating 7,864,320 starting points (300.0MB)
...
GeForce GTX 1070 928/8192MB | 1 target 241.32 MKey/s (1,753,743,360 total) [00:00:10]
see?

need new column - optimal argv
i know
# GTX1060  = -b 9 -t 512 -p 1024
# GTX1070  = -b 15 -t 512 -p 1024
# GTX1080Ti= -b 28 -t 512 -p 1024

and 2cols of hashrate - with default and with optimal argv

..and its good content for add to 1post
bulleteyedk
Jr. Member
*
Offline Offline

Activity: 49
Merit: 1


View Profile
September 01, 2019, 08:15:23 PM
Last edit: September 01, 2019, 08:59:32 PM by bulleteyedk
Merited by vapourminer (1)
 #275

Thanks for making this table, i've just tested one of my kids' GTX 770 2GB card and its capable of doing 120MKey/sec

How could you manage this? Are you really sure in 120 Mkey/sec with GTX 770? This card GTX 770 cost not so much, and in comparison with GTX 1080ti you can need 3 cards GTX 770 and for the the same (or more) Key/sec rate. But the cost will be 2 times less.

I was expecting that GTX 770 to be in that area, as i have a GTX 680 running in my own PC, that scores 109-110 MKey/sec.
The parameters i use for my own setup was slightly altered, but mainly they are the same as for my own setup.




Actually i think especially in regards to the cuda version of bitcrack, the number of cuda cores for the specific card is really important, and there is actually a bunch of older cards with some great numbers here, for ex. the GTX 680 have 1536 cuda cores, which also happends to be the number of cuda cores for the GTX 770.

For comparison other cards cuda cores:
RTX 2080 TI - 4352
GTX 1080 TI - 3583
RTX 2080 Super - 3072
RTX 2080 Gaming - 2944
GTX 780 TI - 2880
GTX 980 TI - 2816
GTX 2070 TI - 2560
GTX 1080 - 2560
RTX 2070 Gaming - 2304
GTX 780 - 2304
RTX 2060 Super - 2176
GTX 980 - 2048
RTX 2060 - 1920
GTX 1070 - 1920
GTX 1060 1708
GTX 1660 TI - 1536
GTX 770 - 1536
GTX 680 - 1536
GTX 1660 Dual OC - 1408
GTX 670 - 1344
GTX 1660 Armor - 1280
GTX 1060 - 1152
GTX 760 - 1152
GTX 1650 - 896
GTX 1050 TI - 768
GTX 1050 - 640
GTX 580 - 512

Due to this challenge i have actually been on the lookout for a cheap and used GTX 780 TI - but not succeeded in finding anyone in my price target yet, im exitied to see how much this card can deliver  Grin
MrFreeDragon
Jr. Member
*
Offline Offline

Activity: 34
Merit: 2


View Profile
September 02, 2019, 12:16:46 AM
 #276

Here is nice comparison of the most popular models:

Code:
Product Name        Cores   TMUs  ROPs
GeForce RTX 2080 Ti 4352 272 88
Radeon RX 5700 XT 2560 160 64
Radeon Vega 8         512  32 8
Radeon RX 580         2304 144 32
Radeon RX 570         2048 128 32
GeForce RTX 2060 1920 120 48
GeForce RTX 2070 SUPER 2560 160 64
GeForce RTX 2070 2304 144 64
GeForce GTX 1660 Ti 1536 96 48
GeForce GTX 1050 Ti 768 48 32
GeForce GTX 1080 Ti 3584 224 88
GeForce GTX 1650 896 56 32
GeForce RTX 2080 2944 184 64
GeForce GTX 750 Ti 640 40 16
GeForce GTX 1060 6 GB 1280 80 48
Radeon RX 5700         2304 144 64
GeForce GTX 1660 1408 88 48
GeForce GTX 1080 2560 160 64
GeForce RTX 2060 SUPER 2176 136 64
GeForce GTX 1070 1920 120 64
GeForce GTX 970         1664 104 56
Radeon RX Vega 11 704 44 8
GeForce RTX 2080 SUPER 3072 192 64
HD Graphics 4000 128 16 2
GeForce 210         16 8 4
Radeon R5 Graphics 128 8 4
GeForce GTX 960  1024 64 32
Radeon RX Vega 56 3584 224 64
Radeon VII         3840 240 64
GeForce GTX 1050 640 40 32
Radeon RX 590         2304 144 32
Radeon RX 480         2304 144 32
Radeon HD 5450         80 8 4
Radeon RX 470         2048 128 32
GeForce GTX 980 Ti 2816 176 96
Radeon RX Vega 64 4096 256 64
Radeon RX 560         1024 64 16
GeForce GT 1030         384 24 16
HD Graphics 4600 160 20 2
GeForce GTX 1070 Ti 2432 152 64
Quadro 4000         256 32 32
Radeon RX 550         512 32 16
Radeon R9 280X    2048 128 32
Xbox One X GPU         2560 160 32
Radeon R4 Graphics 128 8 4
Radeon HD 6450         160 8 4
Radeon HD 5770         800 40 16
GeForce GTX 980         2048 128 64
GeForce GTX 1650 Ti 1024 64 32
GeForce GTX 660         960 80 24

original full table is here: https://www.techpowerup.com/gpu-specs/
brainless
Newbie
*
Offline Offline

Activity: 25
Merit: 0


View Profile
September 02, 2019, 06:03:59 PM
 #277

Code:
#!/usr/bin/python

# by 57fe (fe57.org/forum/thread.php?board=4&thema=1#1)

#######################
# print() compatibility python 2/3
from __future__ import print_function
#######################
# settings

pow2pubkey = 32 # bits/order/pow2/exp key

pow2kangaroo = 3 # discriminator

Ntimeit = 10 # times for avg runtime

prngseed = 0 # 0,any
flag_debug = 0 # 0,1,2,3

#######################
# low order pubkeys

pubkeys = {
 16: ('029d8c5d35231d75eb87fd2c5f05f65281ed9573dc41853288c62ee94eb2590b7a', 0xc936)
, 24: ('036ea839d22847ee1dce3bfc5b11f6cf785b0682db58c35b63d1342eb221c3490c', 0xdc2a04)
, 32: ('0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69', 0xb862a62e)
, 33: ('02ed949eaca31df5e8be9bf46adc1dfae1734b8900dcc303606831372955c728da', False) #0x01abcd1234
, 40: ('03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4', 0xe9ae4933d6)
, 45: ('026ecabd2d22fdb737be21975ce9a694e108eb94f3649c586cc7461c8abf5da71a', 0x122fca143c05)
, 50: ('03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6', 0x022bd43c2e9354)
, 65: ('0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b', 0x01a838b13505b26867)
,105: ('03bcf7ce887ffca5e62c9cabbdb7ffa71dc183c52c04ff4ee5ee82e0c55c39d77b', False)
}

#######################
# import

import os
import sys
import time
import random

try:
# https://www.lfd.uci.edu/~gohlke/pythonlibs/
import gmpy2
except:
flag_gmpy2 = False
print("[warn] gmpy2 not found. raw python is slow!")
else:
flag_gmpy2 = True

try:
from coincurve import PrivateKey, PublicKey
from coincurve.utils import int_to_bytes, hex_to_bytes, bytes_to_int, bytes_to_hex, int_to_bytes_padded
except:
flag_coincurve = False
#print("[warn] coincurve not found. random pubkey not available!")
else:
flag_coincurve = True


if 0:
from multiprocessing import Pool
from multiprocessing import cpu_count
from multiprocessing import freeze_support

#######################
# python 2,3

#import sys
#import time
if sys.version_info[0] == 2:
from time import clock
else:
from time import perf_counter
from time import process_time
clock = time.perf_counter
xrange=range
raw_input=input

#######################
# secp256k1

#modulo = 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1
modulo = 115792089237316195423570985008687907853269984665640564039457584007908834671663
order = 115792089237316195423570985008687907852837564279074904382605163141518161494337
#modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
#order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
#Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
#Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
def __init__(self, x=0, y=0):
self.x = x
self.y = y


Gp = Point(Gx,Gy)
Zp = Point(0,0) # zero-point, infinite in real x,y - plane

#######################
# functions

# return (g, x, y) a*x + b*y = gcd(x, y)
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)


def rev(b, n=modulo):
while b < 0:
b += n
g, x, _ = egcd(b, n)
if g == 1:
return x % n


def mul2(P, p=modulo):
R = Point()
if flag_gmpy2:
c = 3 * P.x * P.x * gmpy2.invert(2*P.y, p) % p
else:
c = 3 * P.x * P.x * rev(2*P.y, p) % p
R.x = (c*c - 2*P.x) % p
R.y = (c*(P.x - R.x) - P.y) % p
return R


# 1I, 3M
def add(P, Q, p=modulo):
R = Point()
dx = Q.x - P.x
dy = Q.y - P.y
if flag_gmpy2: # 1I, 1M
c = dy * gmpy2.invert(dx, p) % p
else:
c = dy * rev(dx, p) % p
R.x = (c*c - P.x - Q.x) % p # 1M
R.y = (c*(P.x - R.x) - P.y) % p # 1M
return R


def mulk(k, P=Gp, p=modulo):
if k == 0: return Zp
elif k == 1: return P
elif (k % 2 == 0):
return mulk(k/2, mul2(P, p), p)
else:
return add(P, mulk( (k-1)/2, mul2(P, p), p), p)


def newX2Y(X, y_parity):
p = modulo

Y = 3
tmp = 1
while Y:
if Y & 1:
tmp = tmp*X % p
Y >>= 1
X = X*X % p

X = (tmp+7) % p

Y = (p+1)//4
tmp = 1
while Y:
if Y & 1:
tmp = tmp*X % p
Y >>= 1
X = X*X % p

Y = tmp

if Y%2 != y_parity:
Y = -Y % p

return Y


def KANGAROO():

DP_rarity = 1 << ((pow2pubkey -  2*pow2kangaroo)//2 - 2)
if flag_debug > 0:
print("[DP_rarity] 1<<((pow2pub - 2*pow2k) -2) = 1<<((%s-2*%s)//2 -2) = %s" % (pow2pubkey,pow2kangaroo,DP_rarity))

jump_modulo = ((pow2pubkey-1) // 2) + pow2kangaroo
if flag_debug > 0:
print("[jump_modulo] (pow2pub-1)//2 + pow2k = (%s-1)//2 + %s = %s" % (pow2pubkey,pow2kangaroo,jump_modulo))

T, t, dt = [], [], []
W, w, dw = [], [], []

if flag_debug > 0:
print( '[t] 3<<(pow2pub-2) + rng(1,(1<<(pow2pub-1))) = 3<<(%s-2) + rng(1,(1<<(%s-1))) = %s + %s' %
( pow2pubkey, pow2pubkey
,3<<(pow2pubkey-2), random.randint(1, (1<<(pow2pubkey-1)))
)
)

for k in range(Nt):
t.append((3 << (pow2pubkey - 2)) + random.randint(1, (1 << (pow2pubkey - 1))))#-(1 << (pow2pubkey - 2)) )
T.append(mulk(t[k]))
dt.append(0)
for k in range(Nw):
w.append(random.randint(1, (1 << (pow2pubkey - 1))))
W.append(add(W0,mulk(w[k])))
dw.append(0)

print('[+] T+W ready')

n_jump = last_jump = 0
prvkey = False;
A, Ak, B, Bk = [], [], [], []
t0 = t1 = t2 = time.time()

while (1):

if flag_debug > 2: print('[new_loop] %s jumps'%n_jump)

for k in range(Nt):
if flag_debug > 2: print('[k/Nt] %s/%s'%(k+1,Nt))
n_jump += 1
pw = T[k].x % jump_modulo
pw = int(pw)
dt[k] = 1 << pw

if T[k].x % (DP_rarity) == 0:
A.append(T[k].x)
Ak.append(t[k])
if flag_debug > 1:
print('[tame] A=%s, B=%s'%(len(A),len(B)))
if flag_debug > 0:
save2file('tame.txt', 'a', '%064x %s\n'%(T[k].x,t[k]) )
result = list(set(A) & set(B))
if len(result) > 0:
sol_kt = A.index(result[0])
sol_kw = B.index(result[0])
prvkey = Ak[sol_kt] - Bk[sol_kw]

if prvkey: break
t[k] += dt[k]
T[k] = add(P[pw], T[k])
if prvkey: break
for k in range(Nw):
if flag_debug > 2: print('[k/Nw] %s/%s'%(k+1,Nw))
n_jump += 1
pw = W[k].x % jump_modulo
pw = int(pw)
dw[k] = 1 << pw

if W[k].x % (DP_rarity) == 0:
B.append(W[k].x)
Bk.append(w[k])
if flag_debug > 1:
print('[wild] A=%s, B=%s'%(len(A),len(B)))
if flag_debug > 0:
save2file('wild.txt', 'a', '%064x %s\n'%(W[k].x,w[k]) )
result = list(set(A) & set(B))
if len(result) > 0:
sol_kt = A.index(result[0])
sol_kw = B.index(result[0])
prvkey = Ak[sol_kt] - Bk[sol_kw]

if prvkey: break
w[k] += dw[k]
W[k] = add(P[pw], W[k])
if prvkey: break
t2 = time.time()
if (t2-t1) > 1:
if sys.version_info[0] == 2:
print('\r[~] %.1f j/s'%((n_jump-last_jump)/(t2-t1)), end='')
sys.stdout.flush()
else:
print('\r[~] %.1f j/s'%((n_jump-last_jump)/(t2-t1)), end='', flush=True )
t1 = t2
last_jump = n_jump

return prvkey, n_jump, (time.time()-t0)



def save2file(path, mode, data):
fp = open(path, mode)
if type(data) in (list,tuple,dict):
fp.writelines(data)
else:
#elif type(data) in (str,int):
fp.write(data)
fp.close()


def usage():
print('[usage] %s [bits] [pubkey]'%(sys.argv[0]))
print('        %s 32'%(sys.argv[0]))
print('        %s 32 %s'%(sys.argv[0],pubkeys[32][0]))
exit(-1)

#######################
#main

if __name__ == '__main__':

#print('[os] %s' % os.name)
if os.name == 'nt':
#freeze_support()
pass

print("[################################################]")
print("[# ECDSA Pollard-kangaroo PrivKey Recovery Tool #]")
print("[#          based on code by 57fe 2019          #]")
print("[#                  singlecore                  #]");
#print("[#                  multicore                   #]");
print("[################################################]")

if len(sys.argv) > 1 and str(sys.argv[1]) in ('--help','-h','/?') :
usage()

print('[date] {}'.format(time.ctime()))
print("[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]")

if prngseed in (0,'0',False,'False','false',''):
prngseed = random.randint(1,2**32)
random.seed(prngseed)
print('[PRNGseed] %s' % prngseed)

if len(sys.argv) > 1 :
try:
pow2pubkey=int(sys.argv[1])
except:
usage()
if pow2pubkey < 1 or pow2pubkey > 256 :
print("[error] bits must be in range 1..256!")
usage()
print('[bits] 2^%s %s' % (pow2pubkey, '(warn: too big!)' if pow2pubkey>50 else ''))

if len(sys.argv) > 2 :
prvkey0 = False
pubkey0 = str(sys.argv[2])
print('[i] pubkey#%s loaded from argv2' % pow2pubkey)
elif flag_coincurve:
prvkey0 = random.randint(1,2**pow2pubkey)
pubkey0 = bytes_to_hex(PublicKey.from_secret(int_to_bytes_padded(prvkey0)).format(1))
#pubkey0 = bytes_to_hex(PublicKey.from_secret(int_to_bytes_padded(prvkey0)).format(0))
print('[i] pubkey#%s randomly generated' % pow2pubkey)
else:
pubkey0, prvkey0 = pubkeys[pow2pubkey]
print('[i] pubkey#%s loaded from default table' % pow2pubkey)
else:
print('[bits] 2^%s %s' % (pow2pubkey, '(warn: too big!)' if pow2pubkey>50 else ''))
pubkey0, prvkey0 = pubkeys[pow2pubkey]
print('[i] pubkey#%s loaded from default table' % pow2pubkey)

if prvkey0 not in (0,'0',False,'False','false',''):
print('[prvkey#%s] 0x%064x' % (pow2pubkey,prvkey0))
print('[pubkey#%s] %s' % (pow2pubkey,pubkey0))

#calc Y if pubkey is compress
if len(pubkey0)==130:
X = int(pubkey0[2:66], 16)
Y = int(pubkey0[66:],16)
print("[format] uncompressed")
elif len(pubkey0)==66:
X = int(pubkey0[2:66], 16)
Y = newX2Y(X,int(pubkey0[:2])-2)
print("[format] compressed")
else:
print("[error] pubkey len(66/130) invalid!")
usage()

print("[Xcoordinate] %064x" % X)
print("[Ycoordinate] %064x" % Y)

W0 = Point(X,Y)

print("[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]")
starttime = time.time()

P = [Gp]
for k in range(255): P.append(mul2(P[k]))
print('[+] P-table ready')

Nt = Nw = 2**pow2kangaroo
if flag_debug > 0:
print("[range(L..U)] 1..2^%s(0x%x)" % (pow2pubkey, 2**pow2pubkey))
print("[w=U-L] 0x%x ; w/2=0x%x" % (2**pow2pubkey, 2**(pow2pubkey-1)))
print("[pow2k] 2^%s: Nt=%s, Nw=%s" % (pow2kangaroo,Nt,Nw))

jumps_list = []
runtime_list = []

#timeit
for i in range(Ntimeit):
print("[~~~~~~~~~~~~~~~~~~~~~~~[%s]~~~~~~~~~~~~~~~~~~~~~~]"%(i+1))
if flag_debug > 0:
save2file('tame.txt', 'w', '')
save2file('wild.txt', 'w', '')
prvkey, n_jump, runtime = KANGAROO()
jumps_list.append(n_jump)
runtime_list.append(runtime)

print('')
print('[prvkeyX] %064x' % (prvkey) )
save2file('results.txt', 'a', ('%064x\n'%prvkey, '---------------\n'))

if prvkey0 not in (0,'0',False,'False','false',''):
print('[prvkey0] %064x' % (prvkey0))
if prvkey == prvkey0:
print('[double-check] success!')
else:
print('[double-check] failed!')

print('[jump] %s' % n_jump)
print('[time] %.1f sec' % runtime)


print("[################################################]")

if Ntimeit > 1:
M = sum(jumps_list)*1.0 / len(jumps_list)
print('[(avg)jump] %.0f' % (M) )
#D = sum((xi - M) ** 2 for xi in jumps_list)*1.0 / len(jumps_list)
#print('[(avg)jum2] %.1f +/- %.1f' % (M, (D/(len(jumps_list)-1))**0.5) )
print('[(avg)time] %.1f sec' % (sum(runtime for runtime in runtime_list)/Ntimeit) )
#print('[(avg)tim2] %.1f sec' % ((time.time()-starttime)/Ntimeit) )
else:
pass

print("[################################################]")
print('[date] {}'.format(time.ctime()))
#print('[exit] exit')
#print('');raw_input('Press ENTER to continue...');print('')
exit(0)


Addon needed

remove pubkeys = xxxxxx
add example
** with open("pubkeys.txt", "r") as m:
        add = m.read().split()
        for ad in add:  ***
multi pubkeys at once check inside bit range

this script check only 1 pubkey in bit range
byyuans
Newbie
*
Offline Offline

Activity: 32
Merit: 0


View Profile
September 03, 2019, 01:32:19 PM
 #278

Kangaroo System, test friends.
Can you share your scan time and speed?
and How many bits?

I'm

48 bit - 110k / s -  87 sec
51 bit - 110k / s -  200 sec
PrivatePerson
Newbie
*
Offline Offline

Activity: 14
Merit: 0


View Profile
September 03, 2019, 02:04:37 PM
Last edit: September 03, 2019, 02:14:43 PM by PrivatePerson
 #279

Kangaroo System, test friends.
Can you share your scan time and speed?
and How many bits?

I'm

48 bit - 110k / s -  87 sec
51 bit - 110k / s -  200 sec
Code:
[################################################]
[# ECDSA Pollard-kangaroo PrivKey Recovery Tool #]
[#          based on code by 57fe 2019          #]
[#                  singlecore                  #]
[################################################]
[date] Tue Sep  3 17:52:34 2019
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[PRNGseed] 439144377
[bits] 2^50
[i] pubkey#50 loaded from default table
[prvkey#50] 0x00000000000000000000000000000000000000000000000000022bd43c2e9354
[pubkey#50] 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
[format] compressed
[Xcoordinate] f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
[Ycoordinate] eb3dfcc04c320b55c529291478550be6072977c0c86603fb2e4f5283631064fb
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] P-table ready
[~~~~~~~~~~~~~~~~~~~~~~~[1]~~~~~~~~~~~~~~~~~~~~~~]
[+] T+W ready
[~] 144975.9 j/s
[prvkeyX] 00000000000000000000000000000000000000000000000000022bd43c2e9354
[prvkey0] 00000000000000000000000000000000000000000000000000022bd43c2e9354
[double-check] success!
[jump] 82359278
[time] 570.5 sec


what does 3 column mean? And why do 33 and 105 matter False?

Code:
pubkeys = {
  16: ('029d8c5d35231d75eb87fd2c5f05f65281ed9573dc41853288c62ee94eb2590b7a', 0xc936)
, 24: ('036ea839d22847ee1dce3bfc5b11f6cf785b0682db58c35b63d1342eb221c3490c', 0xdc2a04)
, 32: ('0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69', 0xb862a62e)
, 33: ('02ed949eaca31df5e8be9bf46adc1dfae1734b8900dcc303606831372955c728da', False) #0x01abcd1234
, 40: ('03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4', 0xe9ae4933d6)
, 45: ('026ecabd2d22fdb737be21975ce9a694e108eb94f3649c586cc7461c8abf5da71a', 0x122fca143c05)
, 50: ('03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6', 0x022bd43c2e9354)
, 65: ('0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b', 0x01a838b13505b26867)
,105: ('03bcf7ce887ffca5e62c9cabbdb7ffa71dc183c52c04ff4ee5ee82e0c55c39d77b', False)
Hurtson
Newbie
*
Offline Offline

Activity: 17
Merit: 1


View Profile
September 03, 2019, 02:18:20 PM
 #280

Kangaroo System, test friends.
Can you share your scan time and speed?
and How many bits?

I'm

48 bit - 110k / s -  87 sec
51 bit - 110k / s -  200 sec
Code:
[################################################]
[# ECDSA Pollard-kangaroo PrivKey Recovery Tool #]
[#          based on code by 57fe 2019          #]
[#                  singlecore                  #]
[################################################]
[date] Tue Sep  3 17:52:34 2019
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[PRNGseed] 439144377
[bits] 2^50
[i] pubkey#50 loaded from default table
[prvkey#50] 0x00000000000000000000000000000000000000000000000000022bd43c2e9354
[pubkey#50] 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
[format] compressed
[Xcoordinate] f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
[Ycoordinate] eb3dfcc04c320b55c529291478550be6072977c0c86603fb2e4f5283631064fb
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] P-table ready
[~~~~~~~~~~~~~~~~~~~~~~~[1]~~~~~~~~~~~~~~~~~~~~~~]
[+] T+W ready
[~] 144975.9 j/s
[prvkeyX] 00000000000000000000000000000000000000000000000000022bd43c2e9354
[prvkey0] 00000000000000000000000000000000000000000000000000022bd43c2e9354
[double-check] success!
[jump] 82359278
[time] 570.5 sec



what i don't understand is , if 2^50 bit address can be found in 570 second.
then why, we can't find 2^105 bits of puzzle address in 1140 second? or bit more? but why it takes so much time than it should simply do...
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 [14] 15 16 17 18 19 20 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!