Baike.dev
All toolsOnline toolsAI codingTrendingOpen sourceNewsSubmit
Log in
< Back to tools
K

Kangaroo

> 编程语言
Open source

Pollard's kangaroo for SECPK1

371 stars0 likes1 views
WebsiteGitHub

About

Pollard's kangaroo for SECPK1

Pollard's kangaroo for SECPK1

A Pollard's kangaroo interval ECDLP solver for SECP256K1 (based on VanitySearch engine).
This program is limited to a 125bit interval search.

Feature

Fixed size arithmetic

Fast Modular Inversion (Delayed Right Shift 62 bits)

SecpK1 Fast modular multiplication (2 steps folding 512bits to 256bits reduction using 64 bits digits)

Multi-GPU support

CUDA optimisation via inline PTX assembly

Discussion Thread

Discusion thread: https://bitcointalk.org/index.php?topic=5244940.0

Usage

…

Structure of the input file:

  • All values are in hex format
  • Public keys can be given either in compressed or uncompressed format
Start range
End range
Key #1
Key #2
...

ex

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
0335BB25364370D4DD14A9FC2B406D398C4B53C85BE58FCC7297BD34004602EBEC

Note on Time/Memory tradeoff of the DP method

The distinguished point (DP) method is an efficient method for storing random walks and detect collision between them. Instead of storing all points of all kangagroo's random walks, we store only points that have an x value starting with dpBit zero bits. When 2 kangaroos collide, they will then follow the same path because their jumps are a function of their x values. The collision will be then detected when the 2 kangaroos reach a distinguished point.
This has a drawback when you have a lot of kangaroos and looking for collision in a small range as the overhead is in the order of nbKangaroo.2dpBit until a collision is detected. If dpBit is too small a large number of point will enter in the central table, will decrease performance and quickly fill the RAM. Powerfull GPUs with large number of cores won't be very efficient on small range, you can try to decrease the grid size in order to have less kangaroos but the GPU performance may not be optimal. Yau can change manualy the DP mask size using the -d option, take in consideration that it will require more operations to complete. See table below:

nbKangaroo.2dpBit/sqrt(N) DP Overhead Avg
4.000 cubicroot(1+4.000) = ~71.0% 3.55 sqrt(N)
2.000 cubicroot(1+2.000) = ~44.2% 2.99 sqrt(N)
1.000 cubicroot(1+1.000) = ~26.0% 2.62 sqrt(N)
0.500 cubicroot(1+0.500) = ~14.5% 2.38 sqrt(N)
0.250 cubicroot(1+0.250) = ~7.7% 2.24 sqrt(N)
0.125 cubicroot(1+0.125) = ~4.0% 2.16 sqrt(N)

DP overhead according to the range size (N), DP mask size (dpBit) and number of kangaroos running in paralell (nbKangaroo).

Note that restarting a client without having a kangaroo backup is like adding more kangaroos, when you merge workfiles coming from different kangaroos, it is also like having more kangaroos.

How to deal with work files

You can save periodicaly work files using -w -wi -ws options. When you save a work file, if it does not contain the kangaroos (-ws) you will lost a bit of work due to the DP overhead, so if you want to continue a file on a same configuration it is recommended to use -ws. To restart a work, use the -i option, the input ascii file is not needed.
When you continue a work file on a different hardware, or using a different number of bits for the distinguished points, or a different number of kangaroos, you will also get an overhead.
However, work files are compatible (same key and range) and can be merged, if 2 work files have a different number of distinguished bits, the lowest will be recorded in the destination file.
If you have several hosts with different configurations, it is preferable to use -ws on each host and then merge all files from time to time in order to check if the key can be solved. When a merge solve a key, no output file is written. A merged file does not contain kangaroos.

Start a work from scratch and save work file every 30 seconds:

Kangaroo.exe -ws -w save.work -wi 30 in.txt

Continue the work from save.work and save work file every 30 seconds:

Kangaroo.exe -ws -w save.work -wi 30 -i save.work

Getting info from a work file:

Kangaroo.exe -winfo save.work
Kangaroo v1.5
Loading: save.work
Version   : 0
DP bits   : 16
Start     : 3447F65ABC9F46F736A95F87B044829C8A0129D56782D635CD00000000000000
Stop      : 3447F65ABC9F46F736A95F87B044829C8A0129D56782D635CDFFFFFFFFFFFFFF
Key       : 031D91282433E664132046D25189A5FE0F64645A73494A37AB17BD6FB283AE5BA2
Count     : 808510464 2^29.591
Time      : 01:35
DP Size   : 2.4/5.8MB
DP Count  : 12199 2^13.574
HT Max    : 3 [@ 008A9F]
HT Min    : 0 [@ 000000]
HT Avg    : 0.05
HT SDev   : 0.22
Kangaroos : 4096 2^12.000

Merge 2 work files (here the key has been solved during the merge):

Kangaroo.exe -wm save1.work save2.work save3.work
Kangaroo v1.5
Loading: save1.work
MergeWork: [HashTable1 2.3/5.3MB] [00s]
Loading: save2.work
MergeWork: [HashTable2 2.3/5.3MB] [00s]
Merging...
Range width: 2^56

Key# 0 [1S]Pub:  0x031D91282433E664132046D25189A5FE0F64645A73494A37AB17BD6FB283AE5BA2
       Priv: 0x3447F65ABC9F46F736A95F87B044829C8A0129D56782D635CD612C0F05F3DA03
Dead kangaroo: 0
Total f1+f2: count 2^30.04 [02:17]

Note on the wsplit option:

In order to avoid to handle a big hashtable in RAM, it is possible to save it and reset it at each backup. It will save a work file with a prefix at each backup and reset the hashtable in RAM. Then a merge can be done offline and key solved by merge. Even with a small hashtable, the program may also solve the key as paths continue and collision may occur in the small hashtable so don't forget to use -o option when using server(s).

Exemple with a 64bit key:

Kangaroo.exe -d 10 -s -w save.work -wsplit -wi 10 ..\VC_CUDA8\in64.txt
…

CUDA = /usr/local/cuda-8.0 CXXCUDA = /usr/bin/g++-4.8

bash

You can enter a list of architecture (refer to nvcc documentation) if you have several GPU with different architecture. Compute capability 2.0 (Fermi) is deprecated for recent CUDA SDK.
Kangaroo need to be compiled and linked with a recent gcc (>=7). The current release has been compiled with gcc 7.3.0.\
Go to the Kangaroo directory. ccap is the desired compute capability.

$ g++ -v gcc version 7.3.0 (Ubuntu 7.3.0-27ubuntu1~18.04) $ make all (for build without CUDA support) or $ make gpu=1 ccap=20 all

Runnig Kangaroo (Intel(R) Xeon(R) CPU, 8 cores,  @ 2.93GHz, Quadro 600 (x2))

$pons@linpons:/Kangaroo$cat in.txt 0 FFFFFFFFFFFFFF 02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305FEF82A pons@linpons:/Kangaroo$export LD_LIBRARY_PATH=/usr/local/cuda-8.0/lib64 pons@linpons:~/Kangaroo$./kangaroo -t 4 -gpu -gpuId 0,1 in.txt Kangaroo v1.2 Start:0 Stop :FFFFFFFFFFFFFF Keys :1 Number of CPU thread: 4 Range width: 2^56 Number of random walk: 2^16.64 (Max DP=9) DP size: 9 [0xff80000000000000] SolveKeyCPU Thread 0: 1024 kangaroos SolveKeyCPU Thread 2: 1024 kangaroos SolveKeyCPU Thread 1: 1024 kangaroos SolveKeyCPU Thread 3: 1024 kangaroos GPU: GPU #0 Quadro 600 (2x48 cores) Grid(4x96) (13.5 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... GPU: GPU #1 Quadro 600 (2x48 cores) Grid(4x96) (13.5 MB used) SolveKeyGPU Thread GPU#1: creating kangaroos... SolveKeyGPU Thread GPU#0: 2^15.58 kangaroos in 334.8ms SolveKeyGPU Thread GPU#1: 2^15.58 kangaroos in 364.7ms [22.67 MKey/s][GPU 13.04 MKey/s][Count 2^29.06][Dead 0][28s][89.1MB]
Key# 0 Pub: 0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305FEF82A Priv: 0x378ABDEC51BC5D

Done: Total time 29s


# Example of usage

Puzzle [32BTC](https://www.blockchain.com/btc/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15), every 5 addresses, the public key is exposed and can be attacked with Kangaroo ECDLP solver.

Puzzle #85: 84bits private key [284,285-1], [1Kh22PvXERd2xpTQk3ur6pPEqFeckCJfAr](https://www.blockchain.com/btc/address/1Kh22PvXERd2xpTQk3ur6pPEqFeckCJfAr)

1000000000000000000000 1FFFFFFFFFFFFFFFFFFFFF 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a


On an Xeon E5-2690 V4 with 4xTesla V100 (GPU only):

Kangaroo v2.1 Start:1000000000000000000000 Stop :1FFFFFFFFFFFFFFFFFFFFF Keys :1 Number of CPU thread: 0 Range width: 2^84 Jump Avg distance: 2^42.03 Number of kangaroos: 2^23.32 Suggested DP: 16 Expected operations: 2^43.12 Expected RAM: 6347.6MB DP size: 16 [0xFFFF000000000000] GPU: GPU #1 Tesla V100-PCIE-16GB (80x64 cores) Grid(160x128) (207.0 MB used) SolveKeyGPU Thread GPU#1: creating kangaroos... GPU: GPU #2 Tesla V100-PCIE-16GB (80x64 cores) Grid(160x128) (207.0 MB used) SolveKeyGPU Thread GPU#2: creating kangaroos... GPU: GPU #0 Tesla V100-PCIE-16GB (80x64 cores) Grid(160x128) (207.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... GPU: GPU #3 Tesla V100-PCIE-16GB (80x64 cores) Grid(160x128) (207.0 MB used) SolveKeyGPU Thread GPU#3: creating kangaroos... SolveKeyGPU Thread GPU#1: 2^21.32 kangaroos [12.3s] SolveKeyGPU Thread GPU#2: 2^21.32 kangaroos [12.3s] SolveKeyGPU Thread GPU#3: 2^21.32 kangaroos [12.3s] SolveKeyGPU Thread GPU#0: 2^21.32 kangaroos [12.4s] [7828.45 MK/s][GPU 7828.45 MK/s][Count 2^43.22][Dead 2][24:56 (Avg 20:24)][4.8/6.9GB] Key# 0 [1S]Pub: 0x0329C4574A4FD8C810B7E42A4B398882B381BCD85E40C6883712912D167C83E73A Priv: 0x11720C4F018D51B8CEBBA8


Next puzzles to solve:

#110, 109bits private key [2109,2110-1], [12JzYkkN76xkwvcPT6AWKZtGX6w2LAgsJg](https://www.blockchain.com/btc/address/12JzYkkN76xkwvcPT6AWKZtGX6w2LAgsJg) **1.10BTC** **Solved by this program**

2000000000000000000000000000 3FFFFFFFFFFFFFFFFFFFFFFFFFFF 0309976BA5570966BF889196B7FDF5A0F9A1E9AB340556EC29F8BB60599616167D


#115, 114bits private key [2114,2115-1], [1NLbHuJebVwUZ1XqDjsAyfTRUPwDQbemfv](https://www.blockchain.com/btc/address/1NLbHuJebVwUZ1XqDjsAyfTRUPwDQbemfv) **1.15BTC** **Solved by this program**

40000000000000000000000000000 7FFFFFFFFFFFFFFFFFFFFFFFFFFFF 0248D313B0398D4923CDCA73B8CFA6532B91B96703902FC8B32FD438A3B7CD7F55

bash

#130, 129bits private key [2129,2130-1], [1Fo65aKq8s8iquMt6weF1rku1moWVEd5Ua](https://www.blockchain.com/explorer/addresses/btc/1Fo65aKq8s8iquMt6weF1rku1moWVEd5Ua) **13.0BTC**

Expected time: several years on 256 Tesla V100 (**Not possible with this program without modification**)

[Up to #160](https://raw.githubusercontent.com/JeanLucPons/Kangaroo/master/puzzle32.txt)

# Articles

 - [1] Using Equivalence Classes to Accelerate Solvingthe Discrete Logarithm Problem in a Short Interval\
       https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf
 - [2] Kangaroo Methods for Solving theInterval Discrete Logarithm Problem\
       https://arxiv.org/pdf/1501.07019.pdf
 - [3] Factoring and Discrete Logarithms using Pseudorandom Walks\
       https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch14.pdf
 - [4] Kangaroos, Monopoly and Discrete Logarithms\
       https://web.northeastern.edu/seigen/11Magic/KruskalsCount/PollardKangarooMonopoly.pdf

Issues· 0 open

View all issuesOpen on GitHub

No open issues yet, or sync has not completed.

> Tags

C++elliptic-curve-discrete-logarithmpollard-kangaroosecp256k1

No comments yet. Be the first to share.

> Details

PublishedAug 1, 2026
UpdatedSep 17, 2026
Category编程语言
PricingOpen source

> Related tools

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言