Optimierung (Profiling) des vanitygen Tools

[cbuchner1]

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

[cbuchner1]

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:

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

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

[cbuchner1]

okay, der Autor hat vor 3 Stunden Version 0.10 ins GIT Repository gestellt.

Use EC_POINTs_make_affine() to improve performance.  ~6X speedup!
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]

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.

[redhatzero]

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 :|