Title: Optimierung (Profiling) des vanitygen Tools Post by: cbuchner1 on July 11, 2011, 07:44:54 PM 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 Title: Re: Optimierung (Profiling) des vanitygen Tools Post by: cbuchner1 on July 12, 2011, 09:51:37 AM 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: 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:
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 */ 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 Title: Re: Optimierung (Profiling) des vanitygen Tools Post by: cbuchner1 on July 12, 2011, 12:57:00 PM okay, der Autor hat vor 3 Stunden Version 0.10 ins GIT Repository gestellt.
Quote 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] 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. Title: Re: Optimierung (Profiling) des vanitygen Tools Post by: redhatzero on July 12, 2011, 03:38:53 PM 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 :|
|