Bitcoin Forum
December 08, 2016, 02:34:02 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Optimierung (Profiling) des vanitygen Tools  (Read 947 times)
cbuchner1
Hero Member
*****
Offline Offline

Activity: 742


View Profile
July 11, 2011, 07:44:54 PM
 #1

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
1481164442
Hero Member
*
Offline Offline

Posts: 1481164442

View Profile Personal Message (Offline)

Ignore
1481164442
Reply with quote  #2

1481164442
Report to moderator
1481164442
Hero Member
*
Offline Offline

Posts: 1481164442

View Profile Personal Message (Offline)

Ignore
1481164442
Reply with quote  #2

1481164442
Report to moderator
1481164442
Hero Member
*
Offline Offline

Posts: 1481164442

View Profile Personal Message (Offline)

Ignore
1481164442
Reply with quote  #2

1481164442
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481164442
Hero Member
*
Offline Offline

Posts: 1481164442

View Profile Personal Message (Offline)

Ignore
1481164442
Reply with quote  #2

1481164442
Report to moderator
cbuchner1
Hero Member
*****
Offline Offline

Activity: 742


View Profile
July 12, 2011, 09:51:37 AM
 #2

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:

                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
Hero Member
*****
Offline Offline

Activity: 742


View Profile
July 12, 2011, 12:57:00 PM
 #3

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. Wink

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
Full Member
***
Offline Offline

Activity: 126



View Profile
July 12, 2011, 03:38:53 PM
 #4

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

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!