Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 73. (Read 60189 times)

member
Activity: 110
Merit: 61
February 26, 2021, 12:48:45 AM
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.
full member
Activity: 1232
Merit: 242
Shooters Shoot...
February 26, 2021, 12:13:52 AM
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:

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?  Tongue]

Cheers all.
I think it was mentioned in passing in regards to the puzzle...i.e. can't go above #125.
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.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
February 26, 2021, 12:09:47 AM
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?

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).
member
Activity: 110
Merit: 61
February 26, 2021, 12:06:03 AM
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?
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
February 25, 2021, 11:33:33 PM
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:

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?  Tongue]

Cheers all.
member
Activity: 406
Merit: 47
February 24, 2021, 11:49:32 PM

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.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
February 23, 2021, 11:28:18 PM

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.

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.
member
Activity: 406
Merit: 47
February 23, 2021, 09:56:54 PM


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.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
February 23, 2021, 04:43:38 AM

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.
member
Activity: 406
Merit: 47
February 23, 2021, 02:32:50 AM

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?
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
February 22, 2021, 11:28:29 PM

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.
member
Activity: 406
Merit: 47
February 22, 2021, 09:46:22 PM

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?

member
Activity: 73
Merit: 19
February 22, 2021, 05:01:09 PM
Hi, Everyone

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& 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);




}
full member
Activity: 1232
Merit: 242
Shooters Shoot...
February 22, 2021, 01:31:25 PM
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.
jr. member
Activity: 114
Merit: 5
February 22, 2021, 01:27:31 PM

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
member
Activity: 406
Merit: 47
February 22, 2021, 12:49:42 PM

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?
jr. member
Activity: 114
Merit: 5
full member
Activity: 1232
Merit: 242
Shooters Shoot...
February 22, 2021, 10:42:12 AM
Quote
Oh it says what the keyspace size is when you start the program but it must be wrong, I didn't actually calculate it myself

It does tell you the range width (keyspace search size) and the expected operations. The range width is spot on, the expected operations is a guesstimated "expected" amount of operations to perform to solve the key.
jr. member
Activity: 114
Merit: 5
February 22, 2021, 10:14:50 AM
I dunno man, so far I've gathered about 20,000 pubkeys to addresses that still have over 6 btc on them. I'm going to run them in the pollard kangaroo program in the keyspace 1 - 2^69 ( ͡° ͜ʖ ͡°) and possibly will find a private key in the low bit range! But the chances that anyone is legitimately using a private key in a keyspace less than 2^128 is pretty slim..

If you still want to go along with this then I suggest not letting it run for more than a day, because you're looking for private keys with 59 leading zero bits in them. Chances are if these addresses have a seed phrase associated with them, neither it's master private key or any of its child keys were derived in a way such that there are several zero bits at the beginning.

Maybe use a random prefix that has a mixture of 1s and 0s which is more likely to hit than all zeros.

Yeah I gave up on that after an hour lol

Here's an interesting random fact about puzzle address #120, in one whole day a Tesla V100 GPU can search 0.00000001% of the keyspace using the pollard kangaroo software. That is equal to approx. 2^93..
How did you come up with that math?  I came up with .0000000000000000000000021% for percentage. (but it's early and I may be off)

But here is match for V100; it checks (by jumping) 138,240,000,000,000 points(keys) for a distinguished bit, per day. 1600 Mkey/s * 60*60*24 .
2^93 = 9,903,520,314,283,042,199,192,993,792

Oh it says what the keyspace size is when you start the program but it must be wrong, I didn't actually calculate it myself
full member
Activity: 1232
Merit: 242
Shooters Shoot...
February 22, 2021, 09:10:04 AM

Yeah I gave up on that after an hour lol

Here's an interesting random fact about puzzle address #120, in one whole day a Tesla V100 GPU can search 0.00000001% of the keyspace using the pollard kangaroo software. That is equal to approx. 2^93..


How long need for puzzle #120 address?
I will try you method tonight with 8 hour for check result test

Expected time: ~2 months running 256 Tesla V100s, 24 hours/7 days a week.
Pages:
Jump to: