gab's da nicht mal jemanden, der gemeint hätte er hätte das soweit optimiert, dass er nur noch ein bruchteil an kombinationen ausprobieren müsste? War irgendwo in dem Vanity Thread. Wenn ich mich recht erinnere, rückte er aber nicht raus, was er gemacht hätte. Insofern kann's auch ein Trollversuch gewesen sein :|
Topic: Optimierung (Profiling) des vanitygen Tools (Read 1158 times)
okay, der Autor hat vor 3 Stunden Version 0.10 ins GIT Repository gestellt.
das macht dann meine Beobachtungen erstmal hinfällig.
Neue Profilingrunde.
Jetzt sieht es so aus, als wäre man vor allem durch das weiterdrehen des public keys auf der elliptischen Kurve limitiert. Und da denke ich das OpenSSL schon ziemlich optimal arbeitet.
Bringt man jetzt die Funktionen EC_POINT_add und EC_POINTs_make_affine auf die GPU, dann kann man vielleicht noch eine Grössenordnung an Tempo herausholen.
Quote
Use EC_POINTs_make_affine() to improve performance. ~6X speedup!
Bump version to 0.10
Bump version to 0.10
das macht dann meine Beobachtungen erstmal hinfällig.
Neue Profilingrunde.
Code:
[3] 99.9 0.01 24.92 1 vg_thread_loop(_vg_context_s*) [3]
0.00 12.55 249406/250471 EC_POINT_add [7]
0.00 7.91 932/941 EC_POINTs_make_affine [9]
0.00 1.82 219546/219548 EC_POINT_point2oct [16]
0.00 1.53 272770/272775 SHA256 [19]
0.01 0.71 226973/226974 RIPEMD160 [26]
0.01 0.20 234588/234588 vg_prefix_test(_vg_context_s*, _vg_thread_context_s*) [45]
0.00 12.55 249406/250471 EC_POINT_add [7]
0.00 7.91 932/941 EC_POINTs_make_affine [9]
0.00 1.82 219546/219548 EC_POINT_point2oct [16]
0.00 1.53 272770/272775 SHA256 [19]
0.01 0.71 226973/226974 RIPEMD160 [26]
0.01 0.20 234588/234588 vg_prefix_test(_vg_context_s*, _vg_thread_context_s*) [45]
Jetzt sieht es so aus, als wäre man vor allem durch das weiterdrehen des public keys auf der elliptischen Kurve limitiert. Und da denke ich das OpenSSL schon ziemlich optimal arbeitet.
Bringt man jetzt die Funktionen EC_POINT_add und EC_POINTs_make_affine auf die GPU, dann kann man vielleicht noch eine Grössenordnung an Tempo herausholen.
Okay, ich denke ich kapiere so langsam wozu die Invertierung nötig ist.
Ein Punkt auf der elliptischen Kurve wird in der openssl Kryptobibliothek in Jacobi Koordinaten (projektive Koordinaten) beschrieben, weil das für die häufig benötigte Modulus Multiplikation wesentliche Vorteile bringt. Um den Punkt als Schlüssel auszugeben, muss dieser allerdings in affinen Koordinaten vorliegen. Hierzu braucht man eine Division zurch z, welche auch als Multiplikation mit der Inversen von z anzusehen ist:
Ich würde mal sagen dass das Vanitygen Tool 95 % seiner Zeit mit dieser Modulus Invertierung verbrät. Also müsste man sich bei einer GPU Implementierung genau darauf konzentrieren - und schon könnte man bis zu 20 mal schneller solche Addressen erzeugen.
Hier noch schnell das Profiling Ergebnis mit den Namen der Funktionen. In meinem Testlauf, der etwa 22 Sekunden dauerte, gingen etwa 19 Sekunden nur für die Invertierung drauf.
0.01 21.36 73314/73314 EC_POINT_point2oct [5]
[4] 80.5 0.01 21.36 73314 ec_GFp_simple_point2oct [4]
0.00 21.24 53466/53466 EC_POINT_get_affine_coordinates_GFp [6]
0.01 21.23 43805/43805 EC_POINT_get_affine_coordinates_GFp [6]
[7] 80.1 0.01 21.23 43805 ec_GFp_simple_point_get_affine_coordinates [7]
0.69 18.84 73452/73461 BN_mod_inverse [8]
0.00 0.60 129806/706165 ec_GFp_mont_field_mul [15]
0.00 0.50 71787/71787 BN_mod_sqr [27]
0.01 0.42 76319/76319 BN_mod_mul [29]
0.00 0.15 56763/56765 ec_GFp_mont_field_decode [43]
Die andere Sache, die man sich mal anschauen könnte, wäre, was mit z passiert wenn im Code der öffentliche Schlüssel auf der Kurve verschoben wird. Das ist in dem Vanitygen tool der Regelfall:
Vielleicht lässt sich der neue Wert von z^-1 aus dem vorhergehenden Wert von z^-1 ableiten, ohne dass dabei eine erneute Invertierung notwendig wird.
Christian
Ein Punkt auf der elliptischen Kurve wird in der openssl Kryptobibliothek in Jacobi Koordinaten (projektive Koordinaten) beschrieben, weil das für die häufig benötigte Modulus Multiplikation wesentliche Vorteile bringt. Um den Punkt als Schlüssel auszugeben, muss dieser allerdings in affinen Koordinaten vorliegen. Hierzu braucht man eine Division zurch z, welche auch als Multiplikation mit der Inversen von z anzusehen ist:
Quote
Affine points(x,y) correspond to standard projective points(xz,yz,z).Converting from standard projective to affine coordinates requires one modular inversion z^-1 and two modular multiplications:x(z^-1) and y(z^-1)
Ich würde mal sagen dass das Vanitygen Tool 95 % seiner Zeit mit dieser Modulus Invertierung verbrät. Also müsste man sich bei einer GPU Implementierung genau darauf konzentrieren - und schon könnte man bis zu 20 mal schneller solche Addressen erzeugen.
Hier noch schnell das Profiling Ergebnis mit den Namen der Funktionen. In meinem Testlauf, der etwa 22 Sekunden dauerte, gingen etwa 19 Sekunden nur für die Invertierung drauf.
Code:
0.01 21.36 73314/73314 EC_POINT_point2oct [5]
[4] 80.5 0.01 21.36 73314 ec_GFp_simple_point2oct [4]
0.00 21.24 53466/53466 EC_POINT_get_affine_coordinates_GFp [6]
0.01 21.23 43805/43805 EC_POINT_get_affine_coordinates_GFp [6]
[7] 80.1 0.01 21.23 43805 ec_GFp_simple_point_get_affine_coordinates [7]
0.69 18.84 73452/73461 BN_mod_inverse [8]
0.00 0.60 129806/706165 ec_GFp_mont_field_mul [15]
0.00 0.50 71787/71787 BN_mod_sqr [27]
0.01 0.42 76319/76319 BN_mod_mul [29]
0.00 0.15 56763/56765 ec_GFp_mont_field_decode [43]
Die andere Sache, die man sich mal anschauen könnte, wäre, was mit z passiert wenn im Code der öffentliche Schlüssel auf der Kurve verschoben wird. Das ist in dem Vanitygen tool der Regelfall:
Code:
/* Common case: next point */
EC_POINT_add(pgroup, ppnt, ppnt, pgen, bnctx);
EC_POINT_add(pgroup, ppnt, ppnt, pgen, bnctx);
Vielleicht lässt sich der neue Wert von z^-1 aus dem vorhergehenden Wert von z^-1 ableiten, ohne dass dabei eine erneute Invertierung notwendig wird.
Christian
Hi, ich habe mir heute mal den vanitygen 0.9 im Quelltext heruntergeladen und compiliert. Er generiert Bitcoin Wallet Addressen mit vorgebenenen Wortfetzen oder Anfangsbuchstaben und zeigt das zugehörige Schlüsselpaar an.
Sourcecode hier: http://pastebin.com/cQZKGzJe
Ein Profiling mit gprof unter Linux zeigte mir, dass die meiste Zeit damit verbraten wird, eine Modulus Inversfunktion auf grossen Zahlen (Bignums) auszuführen. Das passiert innerhalb der Routine EC_POINT_point2oct, in der offenbar ein Punkt auf der Kurve (der öffentliche Schlüssel) auf eine Binärzahl gemappt wird.
Kennt sich jemand ein bischen mit elliptischen Kurven aus, und weiss wozu bei der Generierung eines public/private Schluesselpaares diese Inversfunktion benoetigt wird? Diese Invertierung selbst ist wiederum nicht trivial und eine Vielzahl von weiteren Bignum Funktionen wie Bitshift, Addition usw. auf. Das macht es etwas schwierig, das ganze mit einer GPU zu beschleunigen.
Christian
Sourcecode hier: http://pastebin.com/cQZKGzJe
Ein Profiling mit gprof unter Linux zeigte mir, dass die meiste Zeit damit verbraten wird, eine Modulus Inversfunktion auf grossen Zahlen (Bignums) auszuführen. Das passiert innerhalb der Routine EC_POINT_point2oct, in der offenbar ein Punkt auf der Kurve (der öffentliche Schlüssel) auf eine Binärzahl gemappt wird.
Kennt sich jemand ein bischen mit elliptischen Kurven aus, und weiss wozu bei der Generierung eines public/private Schluesselpaares diese Inversfunktion benoetigt wird? Diese Invertierung selbst ist wiederum nicht trivial und eine Vielzahl von weiteren Bignum Funktionen wie Bitshift, Addition usw. auf. Das macht es etwas schwierig, das ganze mit einer GPU zu beschleunigen.
Christian
Jump to: