Topic: Pollard's kangaroo ECDLP solver - page 68. (Read 58537 times)

Your particular address has one transaction https://www.blockchain.com/btc/tx/6abc9aca979647341389ca9ef69314fc1c01985d9c49574a2dfb83e867292798 where it is listed as an output. Blockchain.com shows the script used for each output and that script has the public key.

In this case:


In this case your public key is aceb7b66651b4ba5d371223582efdc39968402c5.

Thank you

I try to split large keyspace to small size and scan and random keyspace 

may be key space too small 100,000,000,000

now I use 2**56 = 72057594037927936

What recommend minimum for 2**120 =1329227995784915872903807060280344576 ?

2**32 = 4294967296
2**36 = 68719476736
2**40 = 1099511627776
2**50 = 1125899906842624
2**56 = 72057594037927936
2**64 = 18446744073709551616
2**72 = 4722366482869645213696
2**80 = 1208925819614629174706176
2**120 =1329227995784915872903807060280344576

2**120 and 2**160 is too high

Without seeing your start command I would guess you were searching a very small small range with a very low dp where a key did not exist.
The signals are the very low GOU speed, the low count, and the high dead kangaroos.  The dead kangaroos mean that either tames were colliding with tames, wilds colliding with wilds, or probably both.

for testing right
40 bit far from private key very fast to found easy


40bit
23D4A09295BE678B21A5F1DCEAE1F634A69C1B41775F680EBF8164266471401B
23D4A09295BE678B21A5F1DCEAE1F634A69C1B41775F680EBF8166266471401B
03CA5606A1E820E7A2F6BB3AB090E8ADE7B04A7E0B5909A68DDA2744AE3B8ECBFA

40bit
B09C765FA3DC6AD138A8D0DA17CD94306FBC32ACB3D67BC093936761CCC48769
B09C765FA3DC6AD138A8D0DA17CD94306FBC32ACB3D67BC093936961CCC48769
0294FF933DA0498859959225ED6A50D709A4D9C678705D72E9202A4852C8084D85

40bit
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77D4C2A2ED0C99C1232
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77D4C2A30D0C99C1232
03E87E83F871DF1439B7873B4AE449D15306CAFC53E03A06FFFB534B3BF25B58D8


64bit
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77E4C2A2FD0C99C1232
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77C4C2A2FD0C99C1232
03E87E83F871DF1439B7873B4AE449D15306CAFC53E03A06FFFB534B3BF25B58D8

my scan yesterday

SaveWork: save.work..............................done [300.4 MB] [05s] Wed Mar 17 09:03:32 2021
[0.14 MK/s][GPU 0.13 MK/s][Count 2^29.30][Dead 8862934][26:01 (Avg 00s)][270.7/346.2MB]

What mean Dead 8862934 ?

what do you want to do?

if you want to testing this software with you own bitcoin no transaction
yes, you can do it if you know private key , you own bitcoin you have private key and check you pub key like this website

https://learnmeabitcoin.com/technical/public-key
put you privatekey will show public key


how to show public key
A. have  private key

A.1
bitcoin core use command
listaddressgroupings or  validateaddress

A.2
Electrum
click right show DETAIL  (show public key)

A.3 online tools more
https://learnmeabitcoin.com/technical/public-key
https://brainwalletx.github.io/
https://iancoleman.io/bitcoin-key-compression/
(search google)

A.4
other wallet client have option show public key on you own

B. no privatekey
check in transaction search
https://www.blockchain.com/explorer?utm_campaign=expnav_explorer


example case

1. bitcoin address you generate and have privatekey  blank bitcoin address
just use private key check publickey
can use this software test scan
try
https://www.bitaddress.org/

2. you own bitcoin have money , you have private key
can use this software test scan

3. you own bitcoin have transaction send money someone and still have balance  (public key explode)
other people can scan you bitcoin
can use this software test scan

4. Some bitcoin on found address have balance have money on bitcoin but not have transaction public key not yet show
you can not use this software because no pubkey to search no pubkey to reference this case you need to use bitcrack to scan it
can not use
check bitcrack

5. many bitcoin on internet have both balance  and transaction still have money  (public key explode)
can use this software test scan

6. used bitcoin on internet have transaction and zero balance (public key explode)
yes, you can use it
can use this software test scan

I have a coin in my address. No coins were sent to anyone from this address. My public key was not published by the blockchain because it was not sent.

My public address was not published by the blockchain because no coins were sent to another address.

For example ; https://www.blockchain.com/btc/address/1GmKKaFEP4omAA9uKh1zoRCAb7caJB863k

I am sorry for my English.

Quick someone give me sample start and end range with public keys, I think my 256-bit extension mod is done but I need to test it.

Ok thanks i' don't know that, (amazon EC2 F1 on AWS)

I made some search about FPGA performance on secp256k1 operations.

https://github.com/ZcashFoundation/zcash-fpga/blob/master/zcash_fpga_design_doc_v1.4.2.pdf

this paper (from Zcash fondation) presents some benchmarks of a well optimised group operation on secp256k1 implementating on an AWS FPGA (Zcash has the same curve than bitcoin).

Point addition is "only" about (1.9M op/s).
maybe it is possible to optimise it for the kangaroo algorithm but we are far away from the Giga op / s with the latest GPU.

 

If any transaction has been made to the address then it's public key will be exposed on the blockchain and you can inspect it's value inside the public script using a block explorer.

If not, which is the case here, then it means that you're trying to solve an address with no bitcoins inside (a purely academic problem) and you need to use BitCrack instead, which does work with RIPEMD160.

---

AWS has some rentable FPGAs, but it'll be incredibly hard finding an FPGA developer.

---

Fortunately the jump distance can be reduced to, well, as low as you want.

Part of the costly addition is deriving Y from X, which slows down the number of keys that can be solved. Given that nobody fills up their DP table it makes sense to cache Y as well in the DP table (which btw can be reduced to a vector if we stop using the entire lower qword of X as the dp  and also test its NOT in collision tests )

Sorry but i'm not sure to fully understand what you said about bits (1 vs 256).
I understand about the kangaroo algorithm that it forces you to perform a group addition at every jumps of every kangaroo of the herd (wild or tame)
in affine coordinate you have to calculate the next jump with this function (whatever the range size)

X(i+1)=X(i)+deterministic_random_walk[G,2G,4G...]

m = (y1 - y2) * inverse_mod(x - xG,P)
xQ = pow(m,2,P) - x1 - xG
yQ = y1 + m * (xQ - x1)
Q = (xQ %P -yQ %P)

knowing that P is about 2^256, you cannot reduce the size of the integers used in this function
below 256bits because the result coordinate of point Q will be (about randomly) between
(x,y) = ([1 -- 2^256],[1 -- 2^256])
and u need all this information to compute the next point (whatever DP bits used)

it is this costly addition function that i want to implement in my hypothetical ASICs of FPGA's chips (parrellised).

Storing the X coordinates (masked with DP) of every jump  (calculate with the dedicated devices) in a hash table could be achieved with a centralized computer with a lot of ram.

Seems like some good news pertaining with kangaroo.

This is impossible, all known ECDLP algorithms works with public key. Without knowing the public key, the only possible option to find out the private key is bruteforce.

I know the specific range, but I don't know my public key, as no money was sent from my wallet address. Therefore, I cannot use the kangaroo software. If possible, my request from you; I want you to add the RIPEMD-160 focused option. You may be short on time or you may wish not to. I would like to know if this is possible. So can I run the software focused on RIPEMD-160?

Maybe you can look at it from a different angle then trying to use the same concept that is used for mining and the use of ASIC/FPGA for these tasks.
It does not have to be 256 bit integers, it only has to be 256 bit integers if you are trying to travel to your public point that belongs to your known 256 bit private key.
You will visit a lot of intermediate points, which all correspond to valid bitcoin addresses on your way to bit 256.
It's possible that you visited some point/address at for example bit 122 that had 100 BTC in it, but you will never know it if you don't look for it and just skip it and discard the data.
But make sure that you understand that the nearest public point, if you are not trying to solve a known 256 bit key, is not 256 bits away but just one bit away since it is K+1 or Q+1G.
So that is 1 bit and not 256 bits.
Make sure you understand this so that you can use it to optimize your ideas, when it comes to collisions it can also be modified from SECP256K1 to SECP1K1 so realize that its not always 256 or an average of 128 point calculations there is a difference between talking about a specific point, and talking about any point.
A specific point will need to go through the entire loop of 256 bits, but any point is just any point on which you can throw any number of *G's.
For example if the (first) last bit of your private key is a 1 then this will rule out the entire key space below that number and it's only one step to get into that range, not 256 or 128.

Ok thanks for the correction so the average cost will be

549/7 *1000 about 78000 $ (not profitable ;( )


Yes I know that but i want to know if it feasible to develop such of "specific circuit" by a man or in team in is garage ( )for a relative low cost  ?

this study gives diagrams for implementing SECP256K1 addition/multiplication/modular inversion on 256bits integers on a FPGA.

https://cse.iitkgp.ac.in/~debdeep/osscrypto/psec/downloads/PSEC-KEM_prime.pdf

But i dont know what sort of performance it can have on FPGA (op/s) ?
If it is fast for relative low cost parrellised FPGA chips can may be an alternative to GPU??
Maybe is it possible to "convert" this diagram to develop an ASIC.?

To solve #120 you need about 2^60.5 group operations.
If GPU speed is 4 billion op/s (~2^32), then it will takes 2^28.5 seconds to solve.
2^28.5 seconds is ~4393 days
4393 days / 8 GPUs = ~549 days to solve.

There calculations on Kangaroo Github, that #120 will require ~2 months with 256x V100 (~2 billion op/s each)

ASIC == Application Specific Integrated Circuit.

It's baked specifically for one task (SHA256) and can not be easily made to do something else.


You can do zero padding like this: 000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFF

But realize that it's a large number: 1267650600228229401496703205375

Hello everybody,

I am newly interested in the resolution of puzzle # 120 (119 bits private key)
pubkey : 02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630 (hash 160: 17s2b9ksz5y7abUm92PCTzK8jEl5y7abUm92PCTzK8jEl5y7abUm92cHZK8jElc).
a short calculation shows the difficulty of it with the excellent (probably the most optimised) GPU  solver from Jean-Luc Pons.


n=2*sqrt(0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFF-0x40000000000000000000000000000)

best_GPU_card_speed=4*10**9 #(I read that RTX3090 can achieve around 4Giga Keys /s with Kangaroo ECDLP SOLVER)
excepted_days=n/best_GPU_card_power/86400

so ... around 833 excepted days! 

if u consider a rent of gpu cloud at the minimal price (around 1000$ per week for 8x3090) u can expected to resolve it in 100 days (about 15 weeks)
15*1000=15000$ (very rentable in comparison of 60000$/BTC market price) (1.2*60000 72000$ on wallet) 

But u forget that
-that someone else can be faster than u,
-u can be unlucky because the Kangaroo Lambda algorithm is a probabilistic algorithm.
-Bitcoin price can dip while u are in!

Are my calculation are correct?

Have u heard of an implementation of SEC256K1 addition on FPGA or ASIC (ASIC miner have only optimised implementation for sha256)?

Regards

Fanch

Right
and I try already  bitcoin original  from alpha version  bitcoin-nov08.tgz bitcoin-0.1.0.rar bitcoin-0.1.3.rar

all are 256 bits from 2009  (2008 develop) everything 256 bits

very good for over thinking bitcoin address

if develop fit use, may be bitcoin are hack done already

all real money bitcoin use 256 bit

have only Brainwallet have problem for human crack