Just another idea which came to my head. I was thinking what if we changed Kangaroo to dump the list of points that it has already jumped through for the same interval and pubkey into a file. That way it can be loaded into some other system that runs it later to avoid doing all that heavy math for that point since it knows that there cannot be a collision there.
1MB would fit 32000 points stored in binary or 4000 points stored in hex. The hex in particular can be heavily compressed with LZMA algorithm to save more space than if we just compressed them to byte form.
The points can all be sorted so that binary search becomes possible. How effective do you think this idea is?
Topic: Pollard's kangaroo ECDLP solver - page 73. (Read 60698 times)
I try to understand how to kangaroo.exe it work, how to Calculate?
I don't know c++
I try to read from python script kangaroo
Can anyone tell short, over view?
I think kangaroo get X and Y and generate pubkey and compare match with pubkey right?
Other idea Can possible find relationship from pubkey (or convert pubkey to decimal and use it)
Sorry I am not programmer, just power user. but I will try to learn.
You have all explanations in the opening post of this thread:
https://github.com/JeanLucPons/Kangaroo#how-it-works
I try to understand how to kangaroo.exe it work, how to Calculate?
I don't know c++
I try to read from python script kangaroo
Can anyone tell short, over view?
I think kangaroo get X and Y and generate pubkey and compare match with pubkey right?
Other idea Can possible find relationship from pubkey (or convert pubkey to decimal and use it)
Sorry I am not programmer, just power user. but I will try to learn.
Sooooo what other files do you need merged? All files created from the program contain DPs. What is the final file?? If you mean you want to save the progress of the Kangaroos path, you would have to have prompted that before running the program.
I have several files contains kangaroos from multiple machines, that were running work on the CPU.
I want to continue work with that kangaroos on one single machine with GPU, which able to control all that kangaroos. With original solver I can load only one file, the missing kangaroos are created and starts a new paths.
So, I want to merge kangaroo's walks in one file, to continue their existing paths.
There's merging functionally built in to Kangaroo, use -wm file1 file2 destfile for multiple files or -wmdir dir destfile to merge an entire directory full of work files (that it can recognize).
This option merges only DPs and final file gets cleaned from kangaroos.
There's merging functionally built in to Kangaroo, use -wm file1 file2 destfile for multiple files or -wmdir dir destfile to merge an entire directory full of work files (that it can recognize).
This option merges only DPs and final file gets cleaned from kangaroos.
Hey guys, so apparently there's a discrepancy between the search length in the README and the actual search length.
The README says that there's a 125-but search limit, but this is apparently wrong and there's a 126-bit search limit according to the code for hashtable entries in Hashtable.h:
While the class Int is 256 bits wide but the top half are going unused. Actually, the hash entry IF is shoved into the third int64 of kangaroo position (x)!
Anyhow, I'm working on extending the search interval to 256 bits (full disclosure: I'm being paid to do this) and I'll upload the code when it's done so you guys can check it out too. There's really no point in extending it longer than that because all other arithmetic is in 256 bits.
There is also apparently a constant in the code that changes the Int size from 256 to 512 bits (this does not change the interval size which is still locked to 126 bits), but who's going to use 512 bit public keys unless you're using some non bitcoin curve like secp512k1 [I forgot, is that really a curve?
]
Cheers all.
I think it was mentioned in passing in regards to the puzzle...i.e. can't go above #125.The README says that there's a 125-but search limit, but this is apparently wrong and there's a 126-bit search limit according to the code for hashtable entries in Hashtable.h:
Quote from: https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/HashTable.h#L49-L56
Code:
// We store only 128 (+18) bit a the x value which give a probabilty a wrong collision after 2^73 entries
typedef struct {
int128_t x; // Poisition of kangaroo (128bit LSB)
int128_t d; // Travelled distance (b127=sign b126=kangaroo type, b125..b0 distance
} ENTRY;
While the class Int is 256 bits wide but the top half are going unused. Actually, the hash entry IF is shoved into the third int64 of kangaroo position (x)!
Anyhow, I'm working on extending the search interval to 256 bits (full disclosure: I'm being paid to do this) and I'll upload the code when it's done so you guys can check it out too. There's really no point in extending it longer than that because all other arithmetic is in 256 bits.
There is also apparently a constant in the code that changes the Int size from 256 to 512 bits (this does not change the interval size which is still locked to 126 bits), but who's going to use 512 bit public keys unless you're using some non bitcoin curve like secp512k1 [I forgot, is that really a curve?
]Cheers all.
It is one of the main reasons I decided not to use this version. Even though it is the fastest/best one to use. Jean Luc said it would be a slight overhaul to change it to 256 but no one seemed interested when I offered to work with him on it.
Is there any tool to merge kangaroos from two files?
I have some files with a small number of kangaroos which has been ran long time on CPU, and want to continue working on them all together on another machine with GPU, is that possible?
I have some files with a small number of kangaroos which has been ran long time on CPU, and want to continue working on them all together on another machine with GPU, is that possible?
There's merging functionally built in to Kangaroo, use -wm file1 file2 destfile for multiple files or -wmdir dir destfile to merge an entire directory full of work files (that it can recognize).
Is there any tool to merge kangaroos from two files?
I have some files with a small number of kangaroos which has been ran long time on CPU, and want to continue working on them all together on another machine with GPU, is that possible?
I have some files with a small number of kangaroos which has been ran long time on CPU, and want to continue working on them all together on another machine with GPU, is that possible?
Hey guys, so apparently there's a discrepancy between the search length in the README and the actual search length.
The README says that there's a 125-but search limit, but this is apparently wrong and there's a 126-bit search limit according to the code for hashtable entries in Hashtable.h:
While the class Int is 256 bits wide but the top half are going unused. Actually, the hash entry IF is shoved into the third int64 of kangaroo position (x)!
Anyhow, I'm working on extending the search interval to 256 bits (full disclosure: I'm being paid to do this) and I'll upload the code when it's done so you guys can check it out too. There's really no point in extending it longer than that because all other arithmetic is in 256 bits.
There is also apparently a constant in the code that changes the Int size from 256 to 512 bits (this does not change the interval size which is still locked to 126 bits), but who's going to use 512 bit public keys unless you're using some non bitcoin curve like secp512k1 [I forgot, is that really a curve?]
Cheers all.
The README says that there's a 125-but search limit, but this is apparently wrong and there's a 126-bit search limit according to the code for hashtable entries in Hashtable.h:
Quote from: https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/HashTable.h#L49-L56
Code:
// We store only 128 (+18) bit a the x value which give a probabilty a wrong collision after 2^73 entries
typedef struct {
int128_t x; // Poisition of kangaroo (128bit LSB)
int128_t d; // Travelled distance (b127=sign b126=kangaroo type, b125..b0 distance
} ENTRY;
While the class Int is 256 bits wide but the top half are going unused. Actually, the hash entry IF is shoved into the third int64 of kangaroo position (x)!
Anyhow, I'm working on extending the search interval to 256 bits (full disclosure: I'm being paid to do this) and I'll upload the code when it's done so you guys can check it out too. There's really no point in extending it longer than that because all other arithmetic is in 256 bits.
There is also apparently a constant in the code that changes the Int size from 256 to 512 bits (this does not change the interval size which is still locked to 126 bits), but who's going to use 512 bit public keys unless you're using some non bitcoin curve like secp512k1 [I forgot, is that really a curve?
]Cheers all.
It looks like it can only handle one public key at a time: [usage] %s [bits] [pubkey].
For email sending you can use the built-in smtplib module.
Thanks NotATether
I try already, it can use only one public key
and other public key may be not help to any calculate.
reference script python
both
http://bitchain.pl/100btc/pollard_kangaroo.txt
and
https://github.com/Telariust/pollard-kangaroo
pollard-kangaroo-multi.py
both
http://bitchain.pl/100btc/pollard_kangaroo.txt
and
https://github.com/Telariust/pollard-kangaroo
pollard-kangaroo-multi.py
I have to admit, that was a good attempt of them to port Kangaroo to Python. Though it uses xrange so it will not work on newer Python 3.
my question for setup python script pollard-kangaroo-multi.py
Done pubkey list on python they are useful or use on calculate or not?
Can I setup pubkey list on python script just one pubkey?
if pubkey list effect with calculate I will try to put all pubkey found already.
I try to use pollard-kangaroo-multi.py
if use python script work well, I would like to modify to sent email to me and message to know when found privatekey.
Done pubkey list on python they are useful or use on calculate or not?
Can I setup pubkey list on python script just one pubkey?
if pubkey list effect with calculate I will try to put all pubkey found already.
I try to use pollard-kangaroo-multi.py
if use python script work well, I would like to modify to sent email to me and message to know when found privatekey.
It looks like it can only handle one public key at a time: [usage] %s [bits] [pubkey].
For email sending you can use the built-in smtplib module.
I try to use Kangaroo.exe -gpu (use GPU) and pollard-kangaroo-multi.py (use CPU) on pc same time.
It has a GPU switch? I checked it and all the kangaroos were spawned as different CPU processes using message queues to communicate with each other. Not as fast as a native implementation that uses threads and shared memory though.
reference script python
both
http://bitchain.pl/100btc/pollard_kangaroo.txt
and
https://github.com/Telariust/pollard-kangaroo
pollard-kangaroo-multi.py
they are work same kangaroo 2.2 right?
https[Suspicious link removed] on windows easy setup with file in.txt
(Kangaroo.exe work very well and better with GPU option)
my question for setup python script pollard-kangaroo-multi.py
Done pubkey list on python they are useful or use on calculate or not?
Can I setup pubkey list on python script just one pubkey?
if pubkey list effect with calculate I will try to put all pubkey found already.
I try to use pollard-kangaroo-multi.py
if use python script work well, I would like to modify to sent email to me and message to know when found privatekey.
I try to use Kangaroo.exe -gpu (use GPU) and pollard-kangaroo-multi.py (use CPU) on pc same time.
AWS have v100 same GCP
https://docs.aws.amazon.com/dlami/latest/devguide/gpu.html
https://aws.amazon.com/blogs/aws/new-amazon-ec2-instances-with-up-to-8-nvidia-tesla-v100-gpus-p3/
Can free trial credit cover to using testing?
https://docs.aws.amazon.com/dlami/latest/devguide/gpu.html
https://aws.amazon.com/blogs/aws/new-amazon-ec2-instances-with-up-to-8-nvidia-tesla-v100-gpus-p3/
Can free trial credit cover to using testing?
Unlike Google Cloud, AWS doesn't give you free credit - their trial makes some products free and others not free. The GPUs fall into the not-free category unfortunately.
I'm an AWS groupie but you can get your bills from your billing statement in GCP's console, no?
The table linked on this page shows costs per hour and month, but you can get away with ridiculously low costs if you only run the GPUs for a few hours. For instance I am trying to get an NVIDIA T4 running Linux at $0.75 an hour.
Thanks,
AWS have v100 same GCP
https://docs.aws.amazon.com/dlami/latest/devguide/gpu.html
https://aws.amazon.com/blogs/aws/new-amazon-ec2-instances-with-up-to-8-nvidia-tesla-v100-gpus-p3/
Can free trial credit cover to using testing?
Google cloud gave me €200 free credit and 1 GPU to try, I'm only in 1st year of computer science though so not a researcher or anything
Thank you very much for great information
https://cloud.google.com/compute/gpus-pricing
How much you google cloud show cost, expensive?
I'm an AWS groupie but you can get your bills from your billing statement in GCP's console, no?
The table linked on this page shows costs per hour and month, but you can get away with ridiculously low costs if you only run the GPUs for a few hours. For instance I am trying to get an NVIDIA T4 running Linux at $0.75 an hour.
Google cloud gave me €200 free credit and 1 GPU to try, I'm only in 1st year of computer science though so not a researcher or anything
Thank you very much for great information
https://cloud.google.com/compute/gpus-pricing
How much you google cloud show cost, expensive?
Hi, Everyone
Test function in this main.cpp file
The file is running with CPU.
How can I run it with the GPU?
/*
* This file is part of the BSGS distribution (https://github.com/JeanLucPons/Kangaroo).
* Copyright (c) 2020 Jean Luc PONS.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 3.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see
*/
#include
#include "Kangaroo.h"
#include "Timer.h"
#include "SECPK1/SECP256k1.h"
#include "GPU/GPUEngine.h"
#include
#include
#include
#include
#include
#include
using namespace std;
#define CHECKARG(opt,n) if(a>=argc-1) {::printf(opt " missing argument #%d\n",n);exit(0);} else {a++;}
int getInt(string name, char* v) {
int r;
try {
r = std::stoi(string(v));
}
catch (std::invalid_argument&) {
printf("Invalid %s argument, number expected\n", name.c_str());
exit(-1);
}
return r;
}
double getDouble(string name, char* v) {
double r;
try {
r = std::stod(string(v));
}
catch (std::invalid_argument&) {
printf("Invalid %s argument, number expected\n", name.c_str());
exit(-1);
}
return r;
}
// ------------------------------------------------------------------------------------------
void getInts(string name, vector& tokens, const string& text, char sep) {
size_t start = 0, end = 0;
tokens.clear();
int item;
try {
while ((end = text.find(sep, start)) != string::npos) {
item = std::stoi(text.substr(start, end - start));
tokens.push_back(item);
start = end + 1;
}
item = std::stoi(text.substr(start));
tokens.push_back(item);
}
catch (std::invalid_argument&) {
printf("Invalid %s argument, number expected\n", name.c_str());
exit(-1);
}
}
// ------------------------------------------------------------------------------------------
// Default params
static int dp = -1;
static int nbCPUThread;
static string configFile = "";
static bool checkFlag = false;
static bool gpuEnable = false;
static vector gpuId = { 0 };
static vector gridSize;
static string workFile = "";
static string checkWorkFile = "";
static string iWorkFile = "";
static uint32_t savePeriod = 60;
static bool saveKangaroo = false;
static bool saveKangarooByServer = false;
static string merge1 = "";
static string merge2 = "";
static string mergeDest = "";
static string mergeDir = "";
static string infoFile = "";
static double maxStep = 0.0;
static int wtimeout = 3000;
static int ntimeout = 3000;
static int port = 17403;
static bool serverMode = false;
static string serverIP = "";
static string outputFile = "";
static bool splitWorkFile = false;
//Mamu
Secp256K1 secp256k1;
int nbGPUThread;
uint64_t totalRW;
uint64_t counters[256];
int CPU_GRP_SIZE = 1024;
void TestFunc(string ScalarInput)
{
Int i;
char* c = const_cast(ScalarInput.c_str()); //*****************************************************************************************************
i.SetBase10(c);
while (true)
{
i.AddOne();
Point aa = secp256k1.ComputePublicKey(&i);
string PointaX = aa.x.GetBase10();
string PointaY = aa.y.GetBase10();
Int s(secp256k1.order);
s.Sub(&i);
Point bb = secp256k1.ComputePublicKey(&s);
string PointbX = bb.x.GetBase10();
string PointbY = bb.y.GetBase10();
string num1 = i.GetBase10();
string num2 = s.GetBase10();
string Result1 = num1 + " = " + PointaX + " : " + PointaY + "\n";
string Result2 = num2 + " = " + PointbX + " : " + PointbY + "\n";
cout << Result1 << "\n";
cout << Result2 << "\n";
}
}
void main()
{
secp256k1.Init();
cout << "Working..." << "\n";
string ScalarInput;
printf("\n\tStart Number : ");
cin >> ScalarInput;
TestFunc(ScalarInput);
}
Test function in this main.cpp file
The file is running with CPU.
How can I run it with the GPU?
Code:
/*
* This file is part of the BSGS distribution (https://github.com/JeanLucPons/Kangaroo).
* Copyright (c) 2020 Jean Luc PONS.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 3.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see
*/
#include
#include "Kangaroo.h"
#include "Timer.h"
#include "SECPK1/SECP256k1.h"
#include "GPU/GPUEngine.h"
#include
#include
#include
#include
#include
#include
using namespace std;
#define CHECKARG(opt,n) if(a>=argc-1) {::printf(opt " missing argument #%d\n",n);exit(0);} else {a++;}
int getInt(string name, char* v) {
int r;
try {
r = std::stoi(string(v));
}
catch (std::invalid_argument&) {
printf("Invalid %s argument, number expected\n", name.c_str());
exit(-1);
}
return r;
}
double getDouble(string name, char* v) {
double r;
try {
r = std::stod(string(v));
}
catch (std::invalid_argument&) {
printf("Invalid %s argument, number expected\n", name.c_str());
exit(-1);
}
return r;
}
// ------------------------------------------------------------------------------------------
void getInts(string name, vector
size_t start = 0, end = 0;
tokens.clear();
int item;
try {
while ((end = text.find(sep, start)) != string::npos) {
item = std::stoi(text.substr(start, end - start));
tokens.push_back(item);
start = end + 1;
}
item = std::stoi(text.substr(start));
tokens.push_back(item);
}
catch (std::invalid_argument&) {
printf("Invalid %s argument, number expected\n", name.c_str());
exit(-1);
}
}
// ------------------------------------------------------------------------------------------
// Default params
static int dp = -1;
static int nbCPUThread;
static string configFile = "";
static bool checkFlag = false;
static bool gpuEnable = false;
static vector
static vector
static string workFile = "";
static string checkWorkFile = "";
static string iWorkFile = "";
static uint32_t savePeriod = 60;
static bool saveKangaroo = false;
static bool saveKangarooByServer = false;
static string merge1 = "";
static string merge2 = "";
static string mergeDest = "";
static string mergeDir = "";
static string infoFile = "";
static double maxStep = 0.0;
static int wtimeout = 3000;
static int ntimeout = 3000;
static int port = 17403;
static bool serverMode = false;
static string serverIP = "";
static string outputFile = "";
static bool splitWorkFile = false;
//Mamu
Secp256K1 secp256k1;
int nbGPUThread;
uint64_t totalRW;
uint64_t counters[256];
int CPU_GRP_SIZE = 1024;
void TestFunc(string ScalarInput)
{
Int i;
char* c = const_cast
i.SetBase10(c);
while (true)
{
i.AddOne();
Point aa = secp256k1.ComputePublicKey(&i);
string PointaX = aa.x.GetBase10();
string PointaY = aa.y.GetBase10();
Int s(secp256k1.order);
s.Sub(&i);
Point bb = secp256k1.ComputePublicKey(&s);
string PointbX = bb.x.GetBase10();
string PointbY = bb.y.GetBase10();
string num1 = i.GetBase10();
string num2 = s.GetBase10();
string Result1 = num1 + " = " + PointaX + " : " + PointaY + "\n";
string Result2 = num2 + " = " + PointbX + " : " + PointbY + "\n";
cout << Result1 << "\n";
cout << Result2 << "\n";
}
}
void main()
{
secp256k1.Init();
cout << "Working..." << "\n";
string ScalarInput;
printf("\n\tStart Number : ");
cin >> ScalarInput;
TestFunc(ScalarInput);
}
What am I looking at? That is the correct range.
A 120 range, or really, the search range is 2^119 would be 800000000000000000000000000000:FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
The range you have entered in your input file is a 2^93 range. The first 6 characters are the same in your start and stop range; C3F250. They basically zero each other out. And your next characters are a 2 in the start and a 3 in the stop. All that together equals a 2^93 search range.
Edit: Also, by searching a subrange of 2^93, you may get lucky, but to search entire 2^119 via 2^93 range searches, you will have to search 2^26 (67,108,864) ranges to have searched the entire 2^119 range.
A 120 range, or really, the search range is 2^119 would be 800000000000000000000000000000:FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
The range you have entered in your input file is a 2^93 range. The first 6 characters are the same in your start and stop range; C3F250. They basically zero each other out. And your next characters are a 2 in the start and a 3 in the stop. All that together equals a 2^93 search range.
Edit: Also, by searching a subrange of 2^93, you may get lucky, but to search entire 2^119 via 2^93 range searches, you will have to search 2^26 (67,108,864) ranges to have searched the entire 2^119 range.
https://i.imgur.com/vEUcFv8l.jpg
How expensive for buy one?
Are you AI. research or AI. Developer?
most people use high-end CUDA card work on AI. Training
buy one for use personal?
Google cloud gave me €200 free credit and 1 GPU to try, I'm only in 1st year of computer science though so not a researcher or anything
Jump to: