I tried it. On my notebook it takes real 0m26.493s
user 0m26.490s
sys 0m0.000s
for the ~4.1mio keys (1000 * 4096). And real 1m47.661s
user 1m47.657s
sys 0m0.003s
for 16M keys. So around ~160 000 keys/s However, the HRD core also does the hash160 of the uncompressed and also hash160 of the compressed public keys. The public key generation part takes around 6 seconds for the 16M keys. If I understand your code correctly, it also does only the ECC computation part. Then we are at around 6 seconds versus 107 seconds. Not sure how much slower Python vs. C is http://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=python3&lang2=gccsuggests it can be anything between a factor of 3 and 100  Factor 100 would be cool, then your code should be somewhere ~1s in C ... we'll see. It certainly seems more lightweight than what we have now. So in your case 107 / 6 means about 18x slower, I think it is not bad at all. I'm sure that your optimizations with field_5x52_int128_impl.h can make a huge difference. The field operations make the difference. We'll see. |
|
|
|
2. Outside the Box
2. Outside the Box
IMO, for any substantial optimizations, it is required to think outside the box. The box here being the libsecp256k1 library. This library provides us with an API - a set of functions - which is functionally complete, but may sometimes be obstructive for certain tasks. If you look at the use case from above, it would certainly be nice if we had a function that could efficiently sum up affine points into jacobian.
Thinking outside the box, why do we need a function A + A -> J ? We have to add only affine points, and we have never to add the result of an addition with other points. So we can get rid of the jacobian coordinates. In this way we achieve only 3,5M + 1S for each point, if we use the classical (simple and more efficient) A+A-> A formula! Here is my script: https://www.dropbox.com/s/kr10oil2idlhd80/ecc_for_collider02.zip?dl=0 it works with python3 too 1) kG 2) all the inverse of the batch (3M for couple, 1,5M for each point) 3) 2048 couples (2M + 1S with A+A->A for each point) total 3,5M + 1S for each point. Very very fast. EDIT: with this script https://www.dropbox.com/s/4q3i0mqvdfgd258/ecc_for_collider03.zip?dl=0I can generate about 4.1 millions of keys in 51 s, about 80000 keys/s antonio@ubuntu:~/src/python$ time python3 ./gen_batch_points03.py
real 0m52.423s
user 0m51.992s
sys 0m0.040s
With your code my old pc generates about 530000 keys/s (200000 keys/s --> 200000 * 22/6 = 530000), my script then is only 6,5x slower than your code! No assembly, no C! |
|
|
|
oggi mi sono trovato nella condizione di fare una double spending per sbloccare una tx ferma da ben 6 ore
ma tuttavia coinbin mi torna
258: txn-mempool-conflict
...
Guarda che si può fare una double spending (almeno tramite i nodi Core) solo se la transazione originale aveva un flag apposito, flag con il quale l'emittente certifica alla rete, sin dal momento della creazione della tx, che egli si riserva la possibilità di sostituire quella transazione in futuro con una nuova transazione con fee maggiorate. https://bitcoincore.org/en/faq/optin_rbf/Does the opt-in RBF implementation change the likelihood that a “non-RBF” transaction can be double-spent?
No. A transaction must be marked replaceable (sequence number below MAX-1) in order for the opt-in RBF implementation to treat it as replaceable.
Si parla in questo caso di "opt-in RBF transaction", che io tradurrei in : "transazione che eplicita pubblicamente il suo assenso a essere sostituita mediante fee maggiorate", mentre non penso esistano ancora nodi che implementino la possibilità di sostituire una qualsiasi transazione con un'altra mediante fee maggiorate. |
|
|
|
|
Good news, from 6M + 2S to 4,5M +2S for each point!
Considering that your current code performs 6M + 1S only for the transition from jacobian to affine coordinates for each point and that you are using J+J --> J to perform each addition (12M + 4S), your current cost should be 18M + 5S each point.
Let's say 1S = 0,8M, then my code should be about 3,5 faster than yours.
If you are now using instead J+A --> J to perform addition (8M + 3S), then my code should be 2,8 faster than yours.
If you implement:
1) (X,Y) , (X,-Y) --> 2x
2) endomorphism --> 3x (but non free, 1M for each point)
3) 4,5M + 2S generation --> 2,8x / 3,5x
you could speedup your points generation about x 15 (at least). Maybe less if your field multiplication is so optimized that it makes field additions/negations not negligible.
Enjoy your holiday!
|
|
|
|
New version of symmetric function, only 2M + 1S def symmetric(x1,y1,x2,y2,z3inv):
a=((y2+y1)*z3inv) % p #1M
b=a**2 % p #1S
x4 = (b - x1 - x2) % p
y4 = (a*(x4-x1) - y1) % p #1M
return x4,y4
then we pass from 7M + 1,5S for each point to 6M + 2S. |
|
|
|
This is my output: antonio@ubuntu:~/src/python$ ./gen_couple_points.py
kG
0xbfcdf2
0xa884186c5d47633c9b58ae542b8b6797230c8e67808ade960793d4bc0e546cd3L
0xd74beb0250afe97f2d1ab66a02e689447b87a2df62383f4717b9452607a9b4ffL
*******
mG
0x1d1
0x87be732373bd4b738627fb63bd4d50bfd6f2bb81f804b52829549fe93fe1ac2eL
0xf6a9186ff147b9b5ffc844b2ec0e255a1ae5537d75624288ce8421f87e94e1a4L
*******
kG+mG
0xbfcfc3
0xc6292537e08b2fcad6e378b1673c446f279bed612ba928ad63d05cf6bbb8165L
0x3a744f5375e3207a53345975fc610cea7fb47dd738307e26d86e5d6bb775197dL
*******
kG-mG
0xbfcc21
0x893c80077fa3d8fcdc1fd6db146a389fec56e312bba27c3f7b3380c636a85e60L
0x6e8da51c1c82ffdbc0073bfcc00463cc50ec9dbf237efbb275503cf64886b5afL
*******
Try v//u instead of v/u, we have different versions of python. |
|
|
|
....
2. Outside the Box
IMO, for any substantial optimizations, it is required to think outside the box. The box here being the libsecp256k1 library. This library provides us with an API - a set of functions - which is functionally complete, but may sometimes be obstructive for certain tasks. If you look at the use case from above, it would certainly be nice if we had a function that could efficiently sum up affine points into jacobian.
That's why I started to hack my own libsecp256k1, extending it with functionality for the LBC use case (public key generation).
I made a very simple python script, 2 files --> https://www.dropbox.com/s/xr2ypa5zplry/ecc_for_collider.zip?dl=0ecc_for_collider.py (a very small library) gen_couple_points.py (a test program, it computes kG+mG, kG-mG, given kG and mG) The script works  ********************************************************************* ecc_for_collider.pyfunction add_a_a_j(x1, y1, x2, y2) --> input kG=(x1,y1) , mG=(x2,y2) --> output kG + mG = (x3,y3,z3) (0<m<2049) --> 4M + 2S h=(x2-x1) % p
r=(y2-y1) % p
a=r**2 % p # 1S
b=h**2 % p # 1S
c=b*h % p # 1M c=h**3
d=x1*b % p # 1M d=x1*h**2
e=y1*c % p # 1M e=y1*h**3
x3 = (a-c-2*d) % p # 0M r**2 - h**3 - 2*x1*h**2
y3 = (r*(d-x3)-e) % p # 1M r*(x1*h**2 - x3) - y1*h**3
z3 = h # 0M x2-x1
This is the classic "mixed" jacobian-affine addition (with Z1 and Z2 = 1) ("A"+"A" --> J) I use only affine coordinates (for the operands), because I know already all coordinates of any points kG, G, 2G, mG, 2048G, this is the first advantage of this method. function symmetric(x1,y1,x2,y2,x3,z3inv,z3inv2) This function exploits the symmetry of kG+mG / kG-mG respect of kG --> input: kG, mG, kG+mG (all in affine coordinates!), (z3)^-1 and (z3)^-2 of kG+mG --> output: kG-mG (in affine coordinates) --> 4M (including jacobian to affine) def symmetric(x1,y1,x2,y2,x3,z3inv,z3inv2):
x4 = (x3+4*(y1*y2)*z3inv2) % p #2M
y4 = (z3inv*(x4-x1)*(y1+y2) -y1) % p #2M
return x4,y4
If kG = (x1,y1), mG = (x2,y2) , kG+mG = (x3,y3) then you have: kG-mG = (x4,y4) = ( x3+4*y1*y2)/(x2-x1)^2 , (x4-x1)*(y1+y2)/(x2-x1) -y1 ) ******************************************************************* First compute kG (in affine coordinates, I changed my mind) (remember: my k stands for your k+2048) You could compute then: 1) first k+1, k+2, k+3, ..., k+2048 ("A"+"A"->"J") 4M + 2S for each point with the function add_a_a_j 2) then jacobian to affine change 6M + 1S for 2048 points (you have already this function, don't look at mine for that) 3) then you compute k-1, k-2, k-3, ...., k-4, k-2048 ( at 1) you have to memorize the inverse of k+1,k+2,k+3,... to do that): 4M using the function symmetric. Total: 14M + 3S for 2 points, 7M + 1,5S for each point (including jacobian to affine) I didn't took care of the generation of the first point, k*G (more precisely: (k+2048)G) With my proposal you have to perform 2 inverse for batch, 1 to get (k+2048)G in affine coordinates, 1 to the points from k+2049 to k+4096. You save then 3M x 2048 points (at least) ----------------------------------------------------------------------------------------------------------------------------- EDIT: maybe an another improvement is possible: if we use the symmetric function for generate all points? If we have kG and kG+mG (and mG) --> we get kG-mG and viceversa (with symmetric function) if we have kG and kG-mG (and mG) --> we get kG+mG . Now, if we have kG+mG and kG (and mG), we can get kG+2mG!  Infact kG and kG+2mG are symmetric respect to the point kG+mG kG=(kG+mG)-mG, kG+2mG=(kG+mG)+mG The only problem is: we don't have yet kG+mG in affine coordinates, I have to do some computations... maybe tomorrow |
|
|
|
I had another idea. First we take a look at your code, then my proposal. *********************************************************************************************************** *********************************************************************************************************** FROM JACOBIAN TO AFFINE COORDINATESLet's start from static void hrdec_ge_set_all_gej_new(secp256k1_ge *r, const secp256k1_gej *a) Your code: ....
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 <---- You perform only 1 inverse
while (--i) {
secp256k1_fe_mul(&az[i + 1], &az[i], &u);
secp256k1_fe_mul(&u, &u, &a[i + 1].z);
}
To avoid to compute 4096 inverse field elements, you are using the "Simultaneous inversion" algorithm in this way you perform only 1 inverse + 3*4095M = 1I + 12285M. You trade each inverse for 3 multiplication. My proposal: only 1,5 multiplication for each inverse --> 1 inverse + 1,5*4095M = 1I + 6144M (the details later) Your code: for (i = 0; i < 4096; i++) {
r[i].infinity = a[i].infinity;
secp256k1_ge_set_gej_zinv(&r[i], &a[i], &az[i]);
}
From secp256k1 ( https://github.com/bitcoin-core/secp256k1/blob/master/src/group_impl.h ): static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) {
75 secp256k1_fe zi2;
76 secp256k1_fe zi3;
77 secp256k1_fe_sqr(&zi2, zi); --> you can compute this only 2048 instead of 4096
78 secp256k1_fe_mul(&zi3, &zi2, zi) --> you can compute this only 2048 instead of 4096
79 secp256k1_fe_mul(&r->x, &a->x, &zi2);
80 secp256k1_fe_mul(&r->y, &a->y, &zi3);
81 r->infinity = a->infinity;
82 }
So you perform additional operations: (3M + 1S) * 4096 = 11228M + 4096S to pass from jacobian to affine coordinates (X,Y,Z) --> (X/Z^2,Y/Z^3) I think there is a way to perform only (3M + 1S)*2048 + 2M*2048 = 10240M + 2048STotal: 1I + 23513M + 4096S <-> 1I + 16384M + 2048S (about -33%)
*********************************************************************************************************** *********************************************************************************************************** Then let's look at the generation of uncompressed public keys: Your code:
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
}
.....
static void hrdec_mult_gen2(secp256k1_gej *r,
const uchar *seckey) {
secp256k1_gej o1;
secp256k1_gej s1, s2, s3, s4, s5, s6, s7, s8,
s9,s10,s11,s12,s13,s14,s15,s16;
secp256k1_gej_set_ge(&o1, &prec[ seckey[31]]);
secp256k1_gej_add_ge_var(&s1, &o1, &prec[ 256 + seckey[30]], NULL);
secp256k1_gej_set_ge(&o1, &prec[512 + seckey[29]]);
secp256k1_gej_add_ge_var(&s2, &o1, &prec[ 768 + seckey[28]], NULL);
secp256k1_gej_set_ge(&o1, &prec[1024 + seckey[27]]);
secp256k1_gej_add_ge_var(&s3, &o1, &prec[1280 + seckey[26]], NULL);
secp256k1_gej_set_ge(&o1, &prec[1536 + seckey[25]]);
secp256k1_gej_add_ge_var(&s4, &o1, &prec[1792 + seckey[24]], NULL);
secp256k1_gej_set_ge(&o1, &prec[2048 + seckey[23]]);
secp256k1_gej_add_ge_var(&s5, &o1, &prec[2304 + seckey[22]], NULL);
....
secp256k1_gej t1;
secp256k1_gej_add_var(&t1, &s1, &s2, NULL);
secp256k1_gej_add_var(&s1, &s3, &s4, NULL);
secp256k1_gej_add_var(&s2, &s5, &s6, NULL);
secp256k1_gej_add_var(&s3, &s7, &s8, NULL);
secp256k1_gej_add_var(&s4, &s9, &s10, NULL);
secp256k1_gej_add_var(&s5, &s11, &s12, NULL);
secp256k1_gej_add_var(&s6, &s13, &s14, NULL);
secp256k1_gej_add_var(&s7, &s15, &s16, NULL);
secp256k1_gej_add_var(&s8, &t1, &s1, NULL);
secp256k1_gej_add_var(&s1, &s2, &s3, NULL);
secp256k1_gej_add_var(&s2, &s4, &s5, NULL);
secp256k1_gej_add_var(&s3, &s6, &s7, NULL);
secp256k1_gej x1,x2;
secp256k1_gej_add_var(&x1, &s1, &s2, NULL);
secp256k1_gej_add_var(&x2, &s3, &s8, NULL);
secp256k1_gej_add_var(r, &x1, &x2, NULL);
}
From secp256k1 ( https://github.com/bitcoin-core/secp256k1/blob/master/src/group_impl.h ) static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr) {
362 /* Operations: 12 mul, 4 sqr, 2 normalize, 12 mul_int/add/negate */
363 secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, i2, h2, h3, t;
364
.....
So you are using the Point Addition (12M + 4S) (J+J --> J) https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates#Point_Addition_.2812M_.2B_4S.29 instead of the more efficient : Mixed Addition (with affine point) (8M + 3S) (J+A --> J) (same link) 414 static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr) {
415 /* 8 mul, 3 sqr, 4 normalize, 12 mul_int/add/negate */
416 secp256k1_fe z12, u1, u2, s1, s2, h, i, i2, h2, h3, t;
Maybe there is a reason (if you compute kG, kG + G, (k+1)G + G, why G is not in affine coordinates?), I must admite I don't understand well these piece of code. Do you use the same function (secp256k1_gej_add_var) in hrdec_gej_add_ge too? for (i = 1; i < 4096; ++i) {
hrdec_gej_add_ge(&batchpj[i], &batchpj[i-1], &incr_a); // increment public key
}
In any case, I understand that you perform at least (8M +3S)*4096 op (or not?) And it seems to me that you don't exploit at all the fact that the keys are consecutive (I'm sorry in advance if I'm wrong, I really can't read code in general, not only yours  ) *********************************************************************************** *********************************************************************************** My proposal: instead of generating k*G, k*G + G, (k+1)*G + G, .... you could 1) precompute G, 2*G, 3*G, ...., 2048*G 2) then generate as first point of the batch: (k+2048)*G = k'*G ( jacobian coordinates -> (X1, Y1, Z1)) better (X1,Y1,1) 3) then generate the following couples: k'*G+1*G , k'*G-1*G k'*G+2*G, k'*G-2*G ....................................... k'*G+m*G, k'*G-m*G ....................................... k'*G+2048*G, k'*G-2048*G In this way: a) k'G is always equals to (X1,Y1, Z1,1) ( jacobian affine coordinates) b) m*G = (X2,Y2,1) is always in affine coordinates! c) k'*G - m*G = k'*G+(-m*G) and +m*G / -m*G have the same X2, and Y2 opposite then you can use the same X2 in 2 operations (and the same inverse!) Mixed Addition (with affine point) in your case --> (4M 3M + 1,5S):
U1 = X1 (Z2=1)
U2 = X2*Z1^2 --> 1/2M (you have to compute Z1^2 only once in the batch, X2 is the same in +mG and -mG)
S1 = Y1
S2 = Y2*Z1^3 --> 1/2M (you have to compute Z1^3 only once in the batch, and remember that mG ->Y2, -mG -> -Y2)
H = U2 - U1 = X2*Z1^2 - X1 --> 0 M
R = S2 - S1 = Y2*Z1^3 - Y1 --> 0 M
X3 = R^2 - H^3 - 2*X1*H^2 --> (1 + 1/2)S + 2*1/2 M = 1,5S + 1M (H is the same each 2 addition)
Y3 = R*(X1*H^2 - X3) - Y1*H^3. --> 1M + 1/2M = 1,5M (Y1 is the same, H is the same each 2 addition )
Z3 = H*Z1 --> 1/2 M --> (Z3 is the same each 2 addition, then the inverse is the same too!)
return (X3, Y3, Z3)
Total: 4M 3M + 1,5SWhat do you think about? |
|
|
|
The pool found: Private key: 000000000000000000000000000000000000000000000000000022306e3f1a72 Public key : 04 E7D529CEA967BDFCA1F4096C91A35E3BAC67E87EAF5A03895889BEE00412FEC6 59F5D0823DBAAF3768684D3625C7D72909E6C2F56CEAA0DE608A0F3AAB27F4E2 hash 160 --> f6cc30532dba44efe592733887f4f74c589c9602 Address: 1PVwqUXrD5phy6gWrqJUrhpsPiBkTnftGg From here: http://prnt.sc/e0nsqpI don't see a complete pk : 5Km2kuu7vtFDPpxywn4u3NLpbr5jKpTB3jsuDVwj9... then there is not (yet) a proof of collision. |
|
|
|
Depending on time available, urgency, personal preferences and mood (hey - I'm doing it for fun) I'll shift my attention between these 3.
Great job, keep on working ! I have a (probably stupid) question about the main purpose: This is a collision finders pool, because its main purpose is to find a hash160 collision
You could generate 10 millions of random private keys (public keys / addresses). You should only check that all keys are greater than 2^160. Then you can make a new *.blf file with your addresses. Obviously you have to save the private keys somewhere. If the pool finds a collision, then it is automatically a real collision. And you have two keys and two curve points as proof, without problems with btc holders. Furthermore if you double the 10 millions, you'll find a collision in half time (like to speedup x2 your program, but more simple). Am I missing something? |
|
|
|
Basically the LBC generator is now about twice as fast as supervanitygen, as it does 730 000 keys/s (supervanitygen 767 000), but contrary to supervanitygen HRD-core does both uncompressed and compressed (supervanitygen only compressed).
Your suggestion about doubling the key rate by using the complement private keys is as of now the only thing that could significantly raise keygen rate. Maybe I could hit 1Mkeys/s on one core on my CPU, but I believe this is really it what can be done with CPU - unless someone can come up with something really surprising.
Looking at the equation y^2 = x^3 +7 1) my first suggestion was exploiting the symmetry with respect to the X-Axis, in that case I took care of the first term y^2 --> (X,Y), (X-Y) 2) now another suggestion (to generate other public keys almost free, but unfortunately not in your range) concerns the term x^3; you could exploit endomorphism for your specific task (not to perform faster a single multiplication k*G). Endomorphism: --> https://bitcointalk.org/index.php?topic=3238.msg45565#msg45565
--> http://crypto.stackexchange.com/questions/22738/how-do-you-derive-the-lambda-and-beta-values-for-endomorphism-on-the-secp256k1-c lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72 (lambda^3 = 1 mod n) beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee (beta^3 = 1 mod p) private key --> public key k --> k*G = (X,Y) (lambda*k) mod n --> (lambda*k)*G = (beta*X, Y) only 2 field multiplications (lambda*k beta*X) (lambda^2*k) mod n --> (lambda^2*k)*G = (beta^2*X, Y) only 2 field multiplications (lambda^2*k beta^2*X) (beta*X and beta^2*X are mod p) In this way you can perform 3 private keys and 3 public keys, all with the same Y. 3) If you implement 1) + 2) you'll have: 6 public keys (+ 6 compressed) (X,Y) , (X,-Y) (beta*X,Y) , (beta*X, -Y) <-- these points are out of the range 1-2^160 (beta^2*X,Y), (beta^2*X, -Y) <-- these points are out of the range 1-2^160 and 6 private keys (+ 6 compressed): k, n-k, lambda*k n-lambda*k <-- these keys are out of the range 1-2^160 lambda^2*k n-lambda^2*k <-- these keys are out of the range 1-2^160 then 12 addresses at a very low computational cost. |
|
|
|
If I am not entirely mistaken, I compute 1 inverse each 4096 private keys (8192 addresses).
Ok, then I cannot read correctly your code, these piece of code: for (i = 0; i < 4096; i++)
......
secp256k1_ge_set_gej_zinv( &r[i], &a[i], &az[i]);
doesn't mean: "compute 4096 inverse field"! I definitely misunderstood the meaning of that line. At the moment the time cost for generating 16777216 uncompressed public keys is ~ 6 seconds on my machine. Which - if I compute correctly - boils down to ~0.36 us per private key. the other 16 seconds are required for creating a compressed key (negligible), to compute the hash160 of both the uncompressed and the compressed key and to check these hash160s against the bloom filter.
Of these 16seconds, 7s is the two RIPEMD160 computations and 8s the two SHA256 computations. Rest is bloom, startup/init etc.
The bottleneck is then SHA256, you need mining hardware. |
|
|
|
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);
}
................
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. The code from libsecp256k1 you are using has a different purpose than yours: The process of cracking Bitcoin brain wallets is to repeatedly generate public keys using guessed passwords.
Key generation method as we described in 2.1.1, is to compute Q = dP . Here d is a SHA256 hash of the generated password,
P is a xed point which is the base point G for secp256k1...
The time cost for computing one public key given a random private key takes : 47.2 us.
sourceYou don't have to generate one public key given a random private key, neither do you generate a lot of public keys from a lot of sparse random keys, but you have to generate a batch of "consecutive" public keys, a very more specific (and less expensive) task. Furthermore you don't have to worry about side-channel attack and other security issues. How do you generate each public key (in batchpj)? And how do you convert jacobian coordinates to affine (hrdec_ge_set_all_gej_new(batchpa, batchpj))? How many operations (multiplication, inverse) are involved? Once you have k*G , you have to add only 1*G in each step: k*G --> (k+1)*G --> (k+2)*G, .... so the effort should be focused on optimizing the addition '+G': minimizing number of operations for each addition '+G'The computation of a multiplicative inverse is the most time consuming operation (1 inverse = 22 multiplication - see table 2 ), so I would start cutting there: goal: less #inverse for each public key or better: less #inverse for each address (IA) --------------------------------------------------------------------------------------------------------------------------------- For example, given a,b elements of the field: a*b, inv(a*b) --> inv(a)=b*inv(a*b), inv(b)=a*inv(a*b) --> 1 inverse + 3 multiplication instead of 2 inverse So: private key k --> k*G = (X1,Y1,Z1) (jacobian coordinates) no inverse private key k+1 --> k*G + G = (X1,Y1,Z1)+ (XG,YG,1)=(X2,Y2,Z2) (jacobian coordinates) no inverse Z=Z1*Z2, inv(Z) --> inv(Z1)=Z2*inv(Z), inv(Z2)=Z1*inv(Z) only 1 inverse jacobian coordinates (X1,Y1,Z1) --> (X1*inv(Z1)^2, Y1*inv(Z1)^3) affine jacobian coordinates (X2,Y2,Z2) --> (X2*inv(Z2)^2, Y2*inv(Z2)^3) affine 2 private keys --> 2 public keys (only 1 inverse) --> IA = 1/2 = 0.5 ----------------------------------------------------------------------------------------------------------------------------- better: 2 private keys --> 4 private keys (k, n-k, k+1, n-k-1) --> 4 uncompressed public keys (only 1 inverse) --> IA = 0.25 --------------------------------------------------------------------------------------------------------------------------------------------------- much better: 2 private keys --> 4 private keys --> 8 public keys, 4 compressed and 4 uncompressed, 8 addresses (only 1 inverse) --> IA=0.125 |
|
|
|
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) Example: k: 0xf3bb9dc5a (65426545754)
-->
X: 0x6ee5f74076df253037be5956bd169d1ce1a2e586cf3b233df6f9f4a31d9b955b
Y: 0xf9680b09669f0df113b9b0bb4d37b531858a73913ac38025a31d322801d660f0
-->
Address: 1LjMTsSMPrXoFFbiSExHpXsBuDamRxjs8R
n-k: 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e7d947c64e7 (115792089237316195423570985008687907852837564279074904382605163141452734948583)
-->
X': 0x6ee5f74076df253037be5956bd169d1ce1a2e586cf3b233df6f9f4a31d9b955b (X'=X)
Y': 0x697f4f69960f20eec464f44b2c84ace7a758c6ec53c7fda5ce2cdd6fe299b3f (Y'=p-0xf9680b09669f0df113b9b0bb4d37b531858a73913ac38025a31d322801d660f0)
-->
Address: 1MutomTTupZ1XVvzUmzivGfWH1HCP9Y5wE
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. |
|
|
|
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:
....
(*) 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.
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. b) I see your point. Furthermore, finding the inverse of an element in finite field is the most of the workload, much more than multiplication. |
|
|
|
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) From here :  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? |
|
|
|
If anyone's interested, from this article: 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? |
|
|
|
Più che tolta è stata disabilitata di default a causa della crescente dimensione della mempool:
Chissa poi perchè la dimensione della mempool è aumentata  E' aumentata in maniera del tutto inaspettata, è stato un fulmine a ciel sereno, proprio nessuno l'aveva minimamente previsto, non c'è stato neanche il tempo per prendere le dovute contromisure ... |
|
|
|
Più che tolta è stata disabilitata di default a causa della crescente dimensione della mempool: https://bitcoin.org/en/developer-guide#transaction-fees-and-change : a concept of so-called “high-priority transactions” which spend satoshis that have not moved for a long time.
In the past, these “priority” transaction were often exempt from the normal fee requirements. Before Bitcoin Core 0.12, 50 KB of each block would be reserved for these high-priority transactions, however this is now set to 0 KB by default. After the priority area, all transactions are prioritized based on their fee per byte, with higher-paying transactions being added in sequence until all of the available space is filled
https://bitcoin.org/en/release/v0.12.0/#relay-and-mining-priority-transactionsBitcoin Core has a heuristic ‘priority’ based on coin value and age. This calculation is used for relaying of transactions which do not pay the minimum relay fee, and can be used as an alternative way of sorting transactions for mined blocks. Bitcoin Core will relay transactions with insufficient fees depending on the setting of -limitfreerelay=<r> (default: r=15 kB per minute) and -blockprioritysize=<s>.
In Bitcoin Core 0.12, when mempool limit has been reached a higher minimum relay fee takes effect to limit memory usage. Transactions which do not meet this higher effective minimum relay fee will not be relayed or mined even if they rank highly according to the priority heuristic.
The mining of transactions based on their priority is also now disabled by default. To re-enable it, simply set -blockprioritysize=<n> where is the size in bytes of your blocks to reserve for these transactions. The old default was 50k, so to retain approximately the same policy, you would set -blockprioritysize=50000.
|
|
|
|
|
Show Posts
