We know that:
private key k : --> public key: (X,Y) = k*G
private key n-k : --> public key: (X,-Y) = (X,p-Y) (no need for multiplication/inverse anymore)
...
So you can calculate:
(1*G,(n-1)*G), (2*G,(n-2)*G), (3*G,(n-3)*G), ....., (k*G,(n-k)*G), .... , (2^159*G, (n-2^159)*G)
k from 1 to 2^159 and n-1 downto n-2^159
Same amount of keys, half time, double speed.
Very intriguing as for the effective reduction in computational effort per pk, also well manageable from the aspect of interval arithmetics to keep track of "computed areas", because both are continuous. I'll certainly have a more detailed look at this. Rico |
|
|
|
a) The odds are about the same, only 1 / 2^(256-160) = 1/2^96 it is a original key. 200 leading zeroes or 2^(2^87) have exactly the same chance of happening.
If you look at the statistical distribution of the hamming weight of the private keys, how can you say that 200 leading zeroes are no exceptional (=rare) event? It is true, that given one (unknown) original private key, the chance of finding a supposedly alternate key that is the original is 1/2^96 in both search spaces. But the hypothesis of this actually being an alternate key is much more probable in the "leading zeroes" case. 2^256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936
ncr(256;128) = 5768658823449206338089748357862286887740211701975162032608436567264518750790
ncr(256;56) = 1529810590453037906058619994778570990615168461145717234720
2^56 = 72057594037927936
Rico |
|
|
|
I was thinking:
why we calculate: G, G+G, G+G+G, G+G+G+G, ...., 2^160*G (private keys: 1,2,3,4,...., 2^160)
instead of: G, 2*G, 4*G, 8*G, 16*G, ......... 2^(2^160)*G ?
(private keys: 1,2,4,8,16, .... 2^(2^160) mod p)
...
I understand that point doubling is much cheaper than point addition (the case 2J is the optimal one, secp256k1 library uses J+A)
I know that our points form a finite cyclic group that is isomorphic to the additive group of Z/nZ. So if we use the second succession instead of the first one, we probably cannot obtain the entire group. But you need only 2^160 points, not all 2^256.
Am I wrong?
There are two problems. a) the resulting private keys from doubling become statistically indistinguishable from "real non-pathological(*)" private keys and b) the whole interval arithmetic for parallelization of the distribution is moot. At the moment, the client precomputes a table with 4096 (uncompressed public keys) with basically this code: int
hrdec_pubkey_batch_incr(uchar (*pub)[65],
uchar start[32]) {
unsigned int i;
hrdec_mult_gen2(&batchpj[0], start);
for (i = 1; i < 4096; ++i) {
hrdec_gej_add_ge(&batchpj[i], &batchpj[i-1], &incr_a); // increment public key
}
hrdec_ge_set_all_gej_new(batchpa, batchpj); // convert all jacobian coordinates to affine
for (i = 0; i < 4096; ++i) { // compute uncompressed public keys
pub[i][0] = 0x04;
secp256k1_fe_normalize_var(&batchpa[i].x);
hrdec_fe_get_b32(pub[i] + 1, &batchpa[i].x);
secp256k1_fe_normalize_var(&batchpa[i].y);
hrdec_fe_get_b32(pub[i] + 33, &batchpa[i].y);
}
return 0;
}
static void hrdec_ge_set_all_gej_new(secp256k1_ge *r, const secp256k1_gej *a) {
secp256k1_fe *az;
secp256k1_fe u;
unsigned int i;
az = (secp256k1_fe *)malloc(sizeof(secp256k1_fe) * 4096);
az[0] = a[0].z;
for (i = 1; i < 4096; i++) {
secp256k1_fe_mul(&az[i], &az[i - 1], &a[i].z);
}
secp256k1_fe_inv_var(&u, &az[--i]); // sets i to 4095 here
while (--i) {
secp256k1_fe_mul(&az[i + 1], &az[i], &u);
secp256k1_fe_mul(&u, &u, &a[i + 1].z);
}
az[0] = u;
for (i = 0; i < 4096; i++) {
r[i].infinity = a[i].infinity;
secp256k1_ge_set_gej_zinv(&r[i], &a[i], &az[i]);
}
free(az);
}
Although I have already optimized the sh*t out of this code, I still feel it's way too clumsy as is and potentially could be improved a lot. If anyone has any suggestions, I'm all ears. (*) If the pool finds - as it currently does by design - a private key that has e.g. 200 leading zeroes, you can assume that this private key is either "the original key" of an address generated by some bad software/as test or by a very marginal chance it got generated correctly but by accident ended up like that. If - on the other hand - your private key contains around 128 bits set/clear, you can assume it is a correctly generated original key. Rico |
|
|
|
root@server-02:~# ./LBC -h
JSON not found - installing it.
Can't locate JSON.pm in @INC (you may need to install the JSON module) (@INC contains: /etc/perl /usr/local/lib/perl/5.18.2 /usr/local/share/perl/5.18.2 /usr/lib/perl5 /usr/share/perl5 /usr/lib/perl/5.18 /usr/share/perl/5.18 /usr/local/lib/site_perl .) at ./LBC line 88.
BEGIN failed--compilation aborted at ./LBC line 88.
tried to google it and installed all kind of shit ... nothing helped ... same problem every time. The system is an Ubuntu 14.04 LTS.
I take it, you've read https://lbc.cryptoguru.org/man/admin#on-linux and gcc is installed. If so, try to install JSON manually by doing and if it fails, paste the results. Rico |
|
|
|
Guten morgen oder guten tag,
nu mal so am rande. ich hasse die nachtschicht.
so ich habe jetzt mal die cpu ausgelesen. er läuft immer
nur noch auf einem pott
Sow wie ich das sehe, hast Du 3 CPUs (VMware default auf einem 4 CPU system - also ok) und 8 GB RAM (mehr als genug, würden 3GB auch reichen). Bist Du sicher, dass Du eingibst? Wenn ja, was sagt er dann? Rico |
|
|
|
R9 290X GPU, 4 GB GDDR5, 2,816 processors and 5,600 GFLOPS,
the OpenCL 32-bit implementation uses the 32-bit scalar type of OpenCL 1.2
On a R9 290X, the OpenCL 32-bit implementation performs 1,778,000 scalar multiplications per second, i.e.
one scalar multiplication in 563 nanoseconds
Almost 2 MKeys/s (without sha256/ripmed160) and on another curve (Curve25519). Is it possible to do better on secp256k1? It certainly must be, as the lower bound for an OpenCL implementation of key generation on my Notebook GPU (Quadro M2000M - 640 cores) is 15 Mkeys/s. (As I said, vanitygen does that - inefficiently - computing the compressed public key once you have computed the uncompressed is quite easy). My estimate is, that we should be able to squeeze 20 Mkeys/s out of the Quadro M2000M. My R9-280X does some 29 Mkeys/s (again vanitygen), an optimal implementation should squeeze 38-40 Mkeys/s from that. Rico PS: I ditched the field_5x52_asm_impl.h in secp256k1 altogether, optimizing field_5x52_int128_impl.h (a lot). Now it's faster.  |
|
|
|
Current generation speed: 23.71 Mkeys/s (*)
very very slow ... w8ing for GPU update ... thats when the real speed will appear . I could do 5-6 times the current speed alone with GPU ... If you have something, by all means code and advice is welcome. I have an unpublishable GPU prototype based on vanitygen. It's basically half the speed of vanitygen (which has 15 MKeys/s on my notebook), as it uses 2 passes, one for compressed and one for uncompressed public keys. Also, it requires around 4GB RAM on startup until the AVL data structures are fiddled up. So on my notebook, the GPU prototype needs around 4GB memory on startup and 3.4 GB in GPU RAM and gives around 7MKeys/s. Compared to this, SHA256 and RIPEMD160 code from hashcat 3.2 indicates around 150 Mega-hash160(x) per second and I am working on bringing the private key -> x (a.k.a. EC arithmetics) to the GPU also. For that, I need to strip down everything not relevant to generation, wrap my head around OpenCL distribution of the RMD160(SHA256(EC(private key))) x 2 Then I have a GPU implementation I got some time ago from a user - allegedly working, but (according to his own claims) with a bad performance. This solution seems Windows and AMD GPU only, and quite honestly I have not even been able to compile it. All in all I agree that what we currently see as total pool speed, in a few weeks may come from one mid-range GPU. Rico |
|
|
|
Time since inception: 6 months Number of keys generated: 250 trillion Number of unspents found: 2 (genuine, no bounties etc.) Total collisions confirmed: 0 Current generation speed: 23.71 Mkeys/s (*) Updated BLF on server. Upon restart, your clients should auto-update. (*) The equivalent of about 185000 pages on directory.io where each address (compressed and uncompressed) checked against ~ 9000000 addresses with unspent outputs - per second. Rico |
|
|
|
I really wish this forum would sometimes happen to be about an actual technical discussion and not always about who has a bigger dick.
How can that be if it's moderated by a bearded dwarf (with the according dick size) acting out his moderator power fantasies. I mean look what happened: I contributed to secp256k1, but then I made the fatal mistake to criticize it and the even more fatal mistake to criticize his holiness Maxwell the 1st. Immediately I am - according to treebeard extraordinaire - "A wallet thief", "incompetent" and what not. Plus of course the usual negative trust rating he gives in these cases. Yay - my 1st negative trust rating here ever. How can you have a technical discussion, if the gnome here is swinging his sceptre. Not benevolently I might add if you happen to not wank his ego. Then technical discussion happens via PM (thanks AlexGR et al.) or elsewhere and result in non-public solutions. Yep guys - there you have it: Your glorious core developer deity barring people from bringing their ideas/work in. Sorry, not exact. *Taking their contribution and fuck them over afterwards.* Yep more like it. Rico |
|
|
|
Instead, when we meet at the next Bitcoin event we'll both be attending, I'll approach you and we'll handle our arguments like real men. Promise. "Violence is the last refuge of the incompetent." Interesting. So real men are incompetent in your eyes. I thought real men (including intelligence) have a beer. My bad. Assuming intelligence. Won't happen again. Sorry. Rico |
|
|
|
also ich kann immer nur noch einen cpu benutzen. leider muss ich jetzt zur arbeit.
aber sobald ich morgen mittag wach bin mache ich mal bilder von dem
auslesen meiner daten über dieses programm.
wünsche eine angenehme nacht.
Nachtwächter? :-) Auf jeden Fall folgendes testen: 1) Hardware Wieviele Kerne hat die Maschine (real, logisch) oder halt einfach welche CPU, dann sehe ich nach Wieviel Speicher hat die Maschine in GB 2) VM Wieviele Kerne sind der VM zugewiesen (steht in den Vmplayer Parametern) Wieviel Speicher ist der VM zugewiesen In der VM unter linux entsprechend > cat /proc/cpuinfo > free eingeben, Ergebnis mitteilen (beantwortet die Frage was sieht das OS in der VM real). Naja und dann halt den Screenshot wie du LBC startest (kommandozeilenparameter) und was der so von sich gibt. Das wird schon. Rico |
|
|
|
this project is trying to find private keys to random public addresses with btc in it, is it not?
Well, the public addresses appear random, but the private keys "behind them" are not. E.g. would you know, that 1MaGmdHoZpGzZk8m92rWSJ5LxUGic8RLjv and 1Gs7mi3eerJwzUrs39fMBa3Uh4skw3ew96 are neighbors? They are at least in one case where their private keys differ by just 1. Of course you cannot see this until you have computed them. ( http://directory.io/1938276999168) The pool is generating hash160s from simply incrementing the underlying private keys. And it checks all generated keys against all known hash160 with unspent inputs on them. Yes. Well - for a very special definition of "simply incrementing": i thought that was, for all intents and purposes, impossible due to the truly astronomical odds.
so how is this finding them?
https://lbc.cryptoguru.org/man/theory#what-we-doOne reason why the pool keeps finding is the speed increase. Long term average, the pool is getting faster and faster. Machines are faster, the generator gets faster, people come and go, but in the end the more people let the LBC client run, the bigger the impact. Another reason is, that we may hit private keys that were generated by some badly designed software, are tests or whatever. And - of course - another reason may be that this task is not at all so impossible as it is always presented. btw love the name.
Thanks - me too. Rico |
|
|
|
A legit collision?  To prove there is a collision you've to prove two different inputs result in same output. This is correct. Right now, all the pool has is one key. Again, a very strange key with many many leading zeroes. The address found is younger, but still from a time ~3 months before even the theoretical inception of the LBC project. If we could leave the usual "how do you prove it's not you who deposited..." aside, we could analyze what the pool has found and where to look for that other private key. On a side note, I would like to mention, that given the speed of the pool at time of inception and the linear search since then, the projected find time of this key would be around ... 19055 days ~52 years in the future. If we look at the originating address https://blockchain.info/de/address/1C22ZukCKVszze8KXVLfAMRaeqhRzWEZGiit seems there were a lot of 0.0001 transactions done - mostly to addresses that have significant funds on them. Don't know exactly what this is (begging or whatever), but the address found is different from all the other targets of 1C22ZukCKVszze8KXVLfAMRaeqhRzWEZGi I'm looking right now which P2SH 378e8af588e6433032d0f5fb548431408c4bcb3c resolves to (hm.. none - so it's standalone). Rico |
|
|
|
ja sehr cool. Kannst du meine Treffer (wenn ich mal einen haben sollte) auch sehen?
Thread studieren hilft (hatten wir vor ~4 Tagen, Antwort ist nein) Genau genommen weiß ich ja nicht einmal wer "Du" bist, so lange Du mir nicht sagst von welcher IP Deine Clients zugreifen, bzw. welche Id Du hast. Aber da jeder Finder stolz wie Oskar ist, kann/soll er mir natürlich von seinem Fund mitteilen, damit ich das auf der Trophies page verewigen kann. Gerne auch mit Id des Finders wenn er das will. So weit ich das verstanden habe, hat "der Pool" auch schon wesentlich mehr "gefunden", als so offiziell angezeigt wird, weil die Leute mit der manuellen Eingabe von Blöcken irgendwelche Suchräume abgrasen, bei denen sie vermutlich selbst wissen was drauf ist und das entsprechend verifizieren. Ja, theoretisch könnte ich mir die Logs ansehen und diese Blöcke auch durchforsten, aber praktisch habe ich keine Chance da hinterherzukommen. 1:many Relation... Meistens sind das eh irgendwelche kleinen Testbeträge, die jemand drauf hat um zu testen ob der LBC überhaupt funktioniert.  edit: So habe ich z.B. den letzten Bug gefunden, indem ich von einem user darauf hingewiesen wurde, dass er https://blockchain.info/address/17AxE7odq6A8sp1jMZFtagD745M126yuehnicht finden konnte, obwohl er den korrekten Suchraum eingab. Nachdem ich den Bug korrigiert hatte, hat ers heute wohl wieder abgezogen. Es war wohl als Weihnachtsgeschenk gedacht, aber halt im falschen Suchraum deponiert. Rico |
|
|
|
Sehr gute Aktion. Manchmal muss man den Leute vor Augen führen, was für einen Humbug die gedenken einzuführen Kommt doch vom LG Humbug. Rico |
|
|
|
"I started making keys, starting with ones with fewest cuts and systematically working through all possibilities. To learn if these keys matched any that had been used in the past, I tried each one in every door in the neighborhood. After a bit I found a few valuables. What was I supposed to do, leave them there?"
Yeah. I had lot's of these discussions. Your comparison doesn't apply - even remotely. "I started taking walks in the park - systematically taking paths to cover the whole area. From time to time I find some coins. What am I supposed to do, leave them there?" The doors in the neighborhood have names on them. And yes, even "for finds in the park" rules apply. We adhere to them. You are lucky, this night the pool found something again. The funds are still on the address. What would be your take on this now? It's a rhetoric question, I do not really need your input. As promised I slept over our - for me yesterdays - "conversation". I guess I'll leave the lawyers in their box this time. Instead, when we meet at the next Bitcoin event we'll both be attending, I'll approach you and we'll handle our arguments like real men. Promise. Rico |
|
|
|
Gerade habe ich mit gmaxwell ein "freundschaftliches" Gespräch gehabt und festgestellt, dass z.B. für die Core-Entwickler eigentlich nur die Geschwindigkeit der pubkey Validierung (*) von Interesse ist.
(*) und die Absicherung gegen Side-Channel Angriffe Und die Absicherung gegen Side-Channel Angriffe. Ja, wichtiges Thema, ist mir auch erst im Verlauf so richtig bewusst geworden. Ändert aber nichts an der Tatsache, dass ich für die Generierung die Performance anderswo brauche und wenn das im Rahmen der Standard-secp256k1 Bibliothek nicht möglich ist, dann muss ich eben selbst ran. Und dass die libsecp256k1 nicht der Weisheit letzter Schluss ist, wird mir auch immer klarer. Es macht ja auch Spaß, schliesslich kommt man so zu Ergebnissen, die es anderswo nicht gibt.  Rico |
|
|
|
A normal move is constant time but not conditional, so "constant time move" wouldn't make much sense.
It was a hint to the mnemonics used. "cctmov ctcmov ..." But I understand the importance of constant time now better (especially why https://github.com/llamasoft/secp256k1_fast_unsafe proclaims itself as being unsafe). If so, only by a highly inefficient means. hash160 is a hash function, there is no EC involved at all. If you were merely attempting to find a hash160 collision you'd simply need to run hash160. You also wouldn't have any reason to check your results against assets in the bitcoin chain... You might also use an efficient collision finding algorithm instead of brute force.
I know the hash160 is only the RIPEMD160(SHA256(x)) part of the generation process. So maybe I'm just missing the nomenclature here for "full generation chain collision". Unfortunately such a thing is not mentioned here https://bitcointalk.org/index.php?topic=293382.0The reason why it's checking against the funds is explained in the text I referenced. Ah. And I did so in "full disclosure", haven't touched the funds on the custody address and if you point me to the rightful owner you are aware he gets not only his funds back, but also quite a bounty from RyanC and I believe a round-up from myself? I mean do you even think before you write some things? Right now I am - doing the LBC project as a hobby
- never took any money/donation for it (although offered) and don't intend to
- except the users testing, never wanted anyone to "slavishly" contribute any work
- on the contrary, I contributed off-spins from this to other projects (secp256k1, Linux Kernel - which will have a faster RIPEMD160 because of me)
Actually, it looks like I have the fastest RIPEMD160 CPU implementation at the moment. I can accept, that you call the LBC project "inefficient", "badly designed" or whatever as response to my criticism of the libsecp256k1, but pulling the "you're a thief" card is really low. If you consider transferring the 0.00778379 BTC funds to custody "stealing", you should really work on your judgement. What should I have had done instead? Leave them alone, just saying "Pool has found something, but we won't tell you what and where"  With the "pool search front" being quite visible even this announcement would lead to jeopardizing the funds. So what then? Not doing it at all? Maybe you need more poeple to tell you to stop working in the Crypto world and breed sheep instead. If you have suggestions for an escrow for the finds, come forth. And if you continue with your allegation(s), I really have no problem to step out of (pseudo)-anonymity and let my lawyers drill your sorry ass until they hit crude oil. And this is not even a rude statement.
Bring it on. I see. Let me sleep a night over it and then decide if educating you is worth the effort. Rico |
|
|
|
|
Show Posts
