|
I am only getting 4 connections. I used to get a lot more. What do I need to do to increase my connection count. Thanks.
|
|
|
|
#################
BurtW, maybe I'm too active here, if you don’t like it, then you can ask me to leave and create a separate topic.
#################
No problem. We enjoy your informative posts and have used several of your ideas in our program. Right now I am very busy with work and my daughter is very busy in school so we have not had time to work on the program. We will get back to our version when things slow down a bit. BTW we keep all our points in memory in a hash table also. Disk access is a no no, especially when we are targeting a GPU (eventually). |
|
|
|
--sinip--
The chances to find the key (randomly) during the priod of 10,000 years with the speed 1130MKey/sec are (1 130 000 * 60 * 60 * 24 * 365 * 10 000) / (2^63) = 0.038636 ≈ 3.8%
--sinip--
if someone took the key space 2^256 and start ruining his bots with speed 200 address/sec (generating and testing for tx and balance 200/s) what is his chance to find an address with tx or balance from all addresses that ever used?  to be honest i start working on similar project but need to increase speed and few option to working on  For all practical purposes: no chance at all. |
|
|
|
There appears to be several scams like this. That is why we decided to just write our own. The project has been very educational! We have a few more improvements to do then we will be moving our code on to a GPU some time later this year (when we can find the time to work on the project). https://bitcointalk.org/index.php?topic=5173445.0 |
|
|
|
Ah, thanks for the link, it definitely helped clear a few things up.
I understand the formula y^2 = x^3+7 generates the secp256k1 curve, and that bitcoin specifies a point on that curve as a generator/base point.
As far as I've found, this base point is added with itself x times, where x is your private key, to get the public key. What I'm trying to figure out is, how to express this point addition/multiplication in algebraic terms.
Thanks pooya87 for your very detailed answer. Also, if you like to look at code instead of mathematical equations we just wrote the code for point addition using the secp256k1 library and posted it. Here is that post repeated here. You can read through the code and see that this code implements exactly the mathematical equations that pooya87 detailed in their post. We have our first pass of our A+A->A implementation which we did from scratch using only the wikipedia page for the formula. It runs and is faster but we have not finish optimizing it - we just got through the bugs and got it to run. Since Telariust shared his implementation we will share ours. I am very surprised this function is not already a standard function in the secp256k1 library. We are still running tests and optimizing our entire system. I will post the results in the OP when the runs finish and we will see how much faster it is in our implementation. static void secp256k1_add_ge_var(secp256k1_ge * const r, const secp256k1_ge * const P, const secp256k1_ge * const Q)
{
// From https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
//
// P + Q, P not equal to Q:
// l = (Qy - Py) / (Qx - Px)
// Rx = l² - Px - Qx
// Ry = l(Px - Rx) - Py
//
// P + Q, P equal to Q:
// l = (3Px² + a) / 2Py, but for secp256k1: y² = x³ + 7 so a = 0 and
// l = 3Px² / 2Py
// Rx = l² - Px - Qx
// Ry = l(Px - Rx) - Py
//
// Rewritten in terms of the available secp256k1_fe operations:
//
// r = -a static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m);
// Set a field element equal to the additive inverse of another.
// Takes a maximum magnitude of the input as an argument.
// The magnitude of the output is one higher.
//
// r += a static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a);
// Adds a field element to another.
// The result has the sum of the inputs' magnitudes as magnitude.
//
// r = inv(a) static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a);
// Sets a field element to be the (modular) inverse of another.
// Requires the input's magnitude to be at most 8.
// The output magnitude is 1 (but not guaranteed to be normalized).
// Potentially faster version of secp256k1_fe_inv, without constant-time guarantee.
//
// r = a * b static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b);
// Sets a field element to be the product of two others.
// Requires the inputs' magnitudes to be at most 8.
// The output magnitude is 1 (but not guaranteed to be normalized).
// NOTE: r != b, a != b
//
// r *= n static void secp256k1_fe_mul_int(secp256k1_fe *r, int n);
// Multiplies the passed field element with a small integer constant.
// Multiplies the magnitude by that small integer.
//
// r = a * a static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a);
// Sets a field element to be the square of another.
// Requires the input's magnitude to be at most 8.
// The output magnitude is 1 (but not guaranteed to be normalized).
//
// r %= p static void secp256k1_fe_normalize_var(secp256k1_fe *r);
// Normalize a field element, without constant-time guarantee.
//
// Px, Py, Qx and Qy all start out normalized
// In other words: m(Px), m(Py), m(Qx) and m(Qy) all equal 1
//
// if (P == Q) {
// l = 3Px² / 2Py
// } else {
// l = (Qy - Py) / (Qx - Px)
// }
// Rx = l² - Px - Qx
// Ry = l(Px - Rx) - Py
//
// Common/Reused terms are -Px, -Py and -Qx
//
// nPx = -Px // m(nPx) = 1 + 1 = 2
// nPy = -Py // m(nPy) = 1 + 1 = 2
// nQx = -Qx // m(nQx) = 1 + 1 = 2
//
// if (P == Q) {
//
// // l = 3Px² / 2Py = n / d
//
// n = Px² // m(n) = 1
// n *= 3 // m(n) = 1 * 3 = 3
//
// d = Py // m(d) = 1
// d *= 2 // m(d) = 1 * 2 = 2
//
// } else {
//
// // l = (Qy - Py) / (Qx - Px) = n / d
//
// n = Qy // m(n) = 1
// n += nPy // m(n) = 1 + 2 = 3
//
// d = Qx // m(d) = 1
// d += nPx // m(d) = 1 + 2 = 3
// }
//
// // l = n / d = n * (1 / d)
//
// l = inv(d) // m(l) = 1
// l = n * l // m(l) = 1
//
// // Rx = l² - Px - Qx
//
// Rx = l² // m(Rx) = 1
// Rx += nPx // m(Rx) = 1 + 2 = 3
// Rx += nQx // m(Rx) = 3 + 2 = 5
//
// // Ry = l(Px - Rx) - Py
//
// Ry = -Rx // m(Ry) = 5 + 1 = 6
// Ry += Px // m(Ry) = 6 + 1 = 7
// Ry = l * Ry // m(Ry) = 1
// Ry += nPy // m(Ry) = 1 + 2 = 3
//
// Rx %= p // m(Rx) = 1 and normalized
// Ry %= p // m(Ry) = 1 and normalized
//
// Implement:
secp256k1_ge RR; // Place to temporarily store the result in the case (R == P)
secp256k1_ge * const R = &RR; //
RR.infinity = 0; //
#define secp256k1_fe_cpy(d, s) *d = *s // Dump_fe only turned on for debug
const secp256k1_fe * const Px = &P->x; Dump_fe("Px", Px);
const secp256k1_fe * const Py = &P->y; Dump_fe("Py", Py);
const secp256k1_fe * const Qx = &Q->x; Dump_fe("Qx", Qx);
const secp256k1_fe * const Qy = &Q->y; Dump_fe("Qy", Qy);
secp256k1_fe * const Rx = &R->x;
secp256k1_fe * const Ry = &R->y;
// nPx = -Px // m(nPx) = 1 + 1 = 2
// nPy = -Py // m(nPy) = 1 + 1 = 2
// nQx = -Qx // m(nQx) = 1 + 1 = 2
secp256k1_fe npx;
secp256k1_fe npy;
secp256k1_fe nqx;
secp256k1_fe * const nPx = &npx;
secp256k1_fe * const nPy = &npy;
secp256k1_fe * const nQx = &nqx;
secp256k1_fe_negate(nPx, Px, 1); Dump_fe("nPx", nPx);
secp256k1_fe_negate(nPy, Py, 1); Dump_fe("nPy", nPy);
secp256k1_fe_negate(nQx, Qx, 1); Dump_fe("nQx", nQx);
secp256k1_fe N;
secp256k1_fe D;
secp256k1_fe L;
secp256k1_fe * const n = &N;
secp256k1_fe * const d = &D;
secp256k1_fe * const l = &L;
++cmps;
if (memcmp(P, Q, sizeof(secp256k1_ge)) == 0) {
// // l = 3Px² / 2Py = n / d
//
// n = Px² // m(n) = 1
// n *= 3 // m(n) = 1 * 3 = 3
secp256k1_fe_sqr(n, Px); Dump_fe("n", n);
secp256k1_fe_mul_int(n, 3); Dump_fe("n", n);
// d = Py // m(d) = 1
// d *= 2 // m(d) = 1 * 2 = 2
secp256k1_fe_cpy(d, Py); Dump_fe("d", d);
secp256k1_fe_mul_int(d, 2); Dump_fe("d", d);
} else {
// // l = (Qy - Py) / (Qx - Px) = n / d
//
// n = Qy // m(n) = 1
// n += nPy // m(n) = 1 + 2 = 3
secp256k1_fe_cpy(n, Qy); Dump_fe("n", n);
secp256k1_fe_add(n, nPy); Dump_fe("n", n);
//
// d = Qx // m(d) = 1
// d += nPx // m(d) = 1 + 2 = 3
secp256k1_fe_cpy(d, Qx); Dump_fe("d", d);
secp256k1_fe_add(d, nPx); Dump_fe("d", d);
}
//
// // l = n / d = n * (1 / d)
//
// l = inv(d) // m(l) = 1
// l = n * l // m(l) = 1
secp256k1_fe_inv_var(l, d); Dump_fe("l", l);
secp256k1_fe_mul(l, l, n); Dump_fe("l", l);
// // Rx = l² - Px - Qx
//
// Rx = l² // m(Rx) = 1
// Rx += nPx // m(Rx) = 1 + 2 = 3
// Rx += nQx // m(Rx) = 3 + 2 = 5
//
secp256k1_fe_sqr(Rx, l); Dump_fe("Rx", Rx);
secp256k1_fe_add(Rx, nPx); Dump_fe("Rx", Rx);
secp256k1_fe_add(Rx, nQx); Dump_fe("Rx", Rx);
// // Ry = l(Px - Rx) - Py
//
// Ry = -Rx // m(Ry) = 5 + 1 = 6
// Ry += Px // m(Ry) = 6 + 1 = 7
// Ry = l * Ry // m(Ry) = 1
// Ry += nPy // m(Ry) = 1 + 2 = 3
secp256k1_fe_negate(Ry, Rx, 5); Dump_fe("Ry", Ry);
secp256k1_fe_add(Ry, Px); Dump_fe("Ry", Ry);
secp256k1_fe_mul(Ry, Ry, l); Dump_fe("Ry", Ry);
secp256k1_fe_add(Ry, nPy); Dump_fe("Ry", Ry);
// Rx %= p // m(Rx) = 1 and normalized
// Ry %= p // m(Ry) = 1 and normalized
secp256k1_fe_normalize_var(Rx); Dump_fe("Rx", Rx);
secp256k1_fe_normalize_var(Ry); Dump_fe("Ry", Ry);
// secp256k1_ge * const r is passed in
// secp256k1_ge * const R = &RR where
// secp256k1_ge RR is on the stack
//
// r->x = R->x;
// r->y = R->y;
// r->infinity = R->infinity;
*r = *R;
}
NOTE: fixed a couple of minor bugs in the above code. It should be good to go now. |
|
|
|
This seems like a noobish question but, with the secp256k1 curve, what is the formula for calculating the Galois field?
The bitcoin wiki gives the parameters for the curve, but I haven't been able to find a formula for how the parameters interact.
Any extra reading materials would also be helpful.
Not sure exactly what you are asking here. First of all the points on the elliptical curve for a group, not a field. Here is a pretty good primer on the defined addition operation for the group. https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3 |
|
|
|
It is impossible to add to the algorithm a kangaroo so that it does not search by public key, but by address? Suppose this takes longer, but you can search for keys for addresses without an outgoing transaction. Or is the kangaroo algorithm not suitable for this?
The Kangaroo algorithm requires that you know the public key in order for it to work. Knowing the Bitcoin address, which is the hash of the public key, cannot be used. You need to know the actual public key or you cannot use the Kangaroo algorithm. If you are interested in exactly how the Kangaroo algorithm works you can check out our thread here: https://bitcointalk.org/index.php?topic=5173445.0Or, just read about it here: Pollard Kangaroo algorithm |
|
|
|
|
So now the race is on between #64 by brute force and #110 by kangaroos!
|
|
|
|
We have a new record for our little program: 57 bit private key in 1.73 hours averaging 153,791 hops per second using only 310,784 bytes of dynamically allocated memory. We still have not yet implemented all of the great ideas in this thread that will improve the hop rate and implementation/algorithm. ver = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test = 56
seed = none (default value)
b = 2 ^ 57 = 0x0200000000000000
a = 2 ^ 56 = 0x0100000000000000
P = 0x02A521A07E98F78B03FC1E039BC3A51408CD73119B5EB116E583FE57DC8DB07AEA (33 bytes)
k0000 = 0x2DCF462904B478D8
s = 0x01EB25C90795D61C
s*G = 0x02A521A07E98F78B03FC1E039BC3A51408CD73119B5EB116E583FE57DC8DB07AEA (33 bytes)
numt = 0x8 (8)
mem = 0x4BE00 (310784) bytes
cmps = 0x34C9808B (885620875)
hops = 0x39144058 (957628504)
hps = 153790.653757
time = 1.7297 hours (6226831609100 nsecs)
so as not to create possible problems for you, I will publish the source code only after you.
At this time, I will try to write addition in affine coordinates, which is the fastest way, +30% expected speed-up.
We are doing this to learn. It would be no problem for us if you publish your source code. We already have the published python source code and have looked at it in order to improve our program. You do not need to wait for us to publish. The science fair is not until next year so we have a lot of time to get everything just right and then move the code on to a GPU. Statistics from our most recent run: test time hps hops compares mem(bytes) total time
---- -------------- ------- ---------- ------------ ---------- --------------
0 0.8564 msecs 1167 1 3 1232 856400
1 0.7479 msecs 1337 1 3 1232 747900
2 0.6127 msecs 1632 1 3 1232 612700
3 8.6445 msecs 925 8 10 1232 8644500
4 1.6279 msecs 6757 11 13 1232 1627900
5 1.9472 msecs 7703 15 17 1232 1947200
6 12.3022 msecs 4226 52 54 1232 12302200
7 2.0009 msecs 15992 32 34 1232 2000900
8 3.2746 msecs 13742 45 47 1232 3274600
9 10.7214 msecs 47568 510 512 1232 10721400
10 18.3054 msecs 48783 893 895 1232 18305400
11 26.3645 msecs 53594 1413 1415 1232 26364500
12 78.4207 msecs 37949 2976 2978 1232 78420700
13 13.5507 msecs 61841 838 338 21888 13550700
14 15.4483 msecs 45441 702 38 23360 15448300
15 22.4275 msecs 48378 1085 143 26304 22427500
16 25.1679 msecs 36355 915 305 32192 25167900
17 31.0598 msecs 24050 747 141 43968 31059800
18 44.3618 msecs 60975 2705 2132 67520 44361800
19 63.4771 msecs 23866 1515 949 114624 63477100
20 120.1801 msecs 32010 3847 3128 208832 120180100
21 200.2294 msecs 26854 5377 5145 397248 200229400
22 397.8554 msecs 30810 12258 11740 774080 397855400
23 91.7390 msecs 97635 8957 5788 40896 91739000
24 64.6165 msecs 60897 3935 770 42368 64616500
25 130.9894 msecs 108573 14222 10071 45312 130989400
26 105.1900 msecs 92489 9729 6966 51200 105190000
27 152.1824 msecs 115979 17650 13956 62976 152182400
28 103.3762 msecs 76613 7920 4563 86528 103376200
29 1.3121 secs 190967 250564 245502 133632 1312076400
30 860.7668 msecs 175329 150918 146792 227840 860766800
31 6.7634 secs 194092 1312726 1302011 416256 6763397900
32 8.2153 secs 195437 1605582 1592230 793088 8215338900
33 2.5348 secs 136228 345314 276375 78336 2534806300
34 1.2517 secs 62445 78166 8225 79808 1251746900
35 4.6382 secs 163879 760109 689150 82752 4638222000
36 38.0879 secs 187772 7151877 6987945 89152 38087934000
37 18.5839 secs 182235 3386646 3302690 100416 18583879400
38 25.5975 secs 183080 4686411 4596034 123968 25597487500
39 46.6920 secs 160988 7516894 8474293 171072 46691996800
40 1.7609 secs 95305 167826 98613 265280 1760925900
41 3.6092 mins 163432 35391791 40060843 453696 216552401100
42 23.0696 mins 181027 250574243 249647494 830528 1384178187200
43 58.8688 secs 113200 6663978 4542748 152544 58868821100
44 1.8608 mins 148273 16554034 14381807 154016 111645595700
45 2.2344 mins 154316 20688475 18479327 156960 134065352000
46 46.5020 secs 83000 3859681 1996004 162848 46501976100
47 48.5642 mins 176154 513288902 505356026 175136 2913854013900
48 17.2490 mins 174174 180259712 176439508 198176 1034938770000
49 23.4304 mins 175194 246292149 242207587 245280 1405822811400
50 18.4636 mins 151963 168347310 188535204 339488 1107817430400
51 58.0994 mins 153719 535862165 606643869 527904 3485962802800
52 34.3880 mins 153038 315762297 357149197 904736 2063282714200
53 40.2602 mins 120565 291240607 223324940 300480 2415611495500
54 41.4377 mins 121698 302574766 234686603 301952 2486260671300
55 54.7941 mins 135532 445582526 376662553 304896 3287646391600
56 1.7297 hours 153790 957628504 885620875 310784 6226831609100
|
|
|
|
Thanks for all of your help! We have been very carefully implementing all the best suggestions. The latest test results using my laptop computer are as follows. Average h/s over all runs from test 0 through test 49: 80,028Max h/s reached was: 194,547We have updated the run results in the OP. test hps
---- -------
0 2,420
1 1,211
2 2,197
3 13,367
4 11,451
5 9,942
6 23,740
7 18,849
8 22,703
9 48,497
10 49,485
11 51,391
12 55,693
13 66,687
14 44,872
15 50,782
16 44,037
17 31,128
18 62,800
19 24,245
20 27,484
21 27,204
22 30,454
23 97,422
24 62,548
25 97,612
26 90,048
27 110,399
28 63,970
29 163,713
30 147,993
31 194,547
32 167,280
33 132,836
34 58,530
35 163,698
36 173,776
37 128,880
38 138,391
39 121,995
40 83,115
41 140,884
42 123,750
43 95,156
44 105,499
45 121,877
46 79,010
47 139,557
48 138,639
49 139,645
|
|
|
|
Thanks for all your input. We are reading it over carefully to see what we can use in our project and will get back to you. We have already rewritten the following functions to make them as fast as possible: static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn) SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigned int overflow) static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) We are working on rewriting: static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) Our internal function #define ec_point_mul_and_add(r,a,n)
{
secp256k1_gej rj;
secp256k1_ecmult_gen(&ecgrp->ecmult_gen_ctx, &rj, n); // highly optimized
secp256k1_gej_add_ge_var(&rj, &rj, a, NULL); // optimization is work in progress
secp256k1_ge_set_gej_var(r, &rj);
}
We heavily rely on and use the following observation to inform our parameter choices: If the PRF is defined as follows:
x = 1 << (X % m)
The PRF will generate one of the numbers: 2**0, 2**1, .., 2**(m-1) with equal probability
So the average hop distance as a function of m can be calculated as follows:
ahd = (1/m)(2**0) + (1/m)(2**1) + .. + (1/m)(2**(m-1))
= (1/m)[(2**0) + (2**1) + .. + (2**(m-1))]
= (1/m)[(2**m) - 1]
= ((2**m) - 1)/m
Therefore the entire distance hopped by the kangaroo, given nn hops, can be estimated as:
c = nn(ahd)
= (nn/m)((2**m) - 1)
|
|
|
|
We have updated the OP with our latest results. Here is a summary of the results of runs for tests 0 through 49: test time hps hops compares mem(bytes) total time time hopping not hopping
---- -------------- ------- ---------- ------------ ---------- -------------- -------------- -----------
0 0.3237 msecs 10,504 1 3 1032 323 95 228
1 0.2853 msecs 11,062 1 3 1032 285 90 194
2 0.2785 msecs 11,111 1 3 1032 278 90 188
3 1.8730 msecs 11,271 8 10 1032 1,873 709 1,163
4 1.8351 msecs 11,147 11 13 1032 1,835 986 848
5 2.1243 msecs 11,123 15 17 1032 2,124 1,348 775
6 5.2260 msecs 11,069 52 54 1032 5,226 4,697 528
7 3.9406 msecs 11,065 32 34 1032 3,940 2,891 1,048
8 4.6425 msecs 10,174 45 47 1032 4,642 4,423 219
9 46.8674 msecs 11,052 510 512 1032 46,867 46,146 721
10 84.2980 msecs 10,674 893 895 1032 84,298 83,661 636
11 122.2013 msecs 11,662 1413 1415 1032 122,201 121,162 1,039
12 257.2438 msecs 11,579 2976 2978 1032 257,243 257,019 224
13 514.6517 msecs 11,402 5840 5842 1032 514,651 512,196 2,455
14 501.1961 msecs 11,791 5901 5903 1032 501,196 500,466 729
15 1.1839 secs 11,886 14026 14028 1032 1,183,908 1,180,079 3,829
16 3.0370 secs 11,631 35249 35251 1032 3,037,005 3,030,586 6,419
17 5.6526 secs 11,230 63475 63477 1032 5,652,638 5,652,025 613
18 14.0759 secs 11,847 166753 166755 1032 14,075,930 14,075,708 222
19 15.5404 secs 11,922 185259 185261 1032 15,540,417 15,539,472 945
20 742.1446 msecs 11,882 8804 5677 32088 742,144 740,944 1,200
21 475.1973 msecs 11,881 5627 1903 32696 475,197 473,623 1,574
22 561.2366 msecs 11,555 6359 3169 33912 561,236 550,304 10,932
23 428.6246 msecs 11,867 5044 1167 36344 428,624 425,047 3,577
24 2.2156 secs 11,842 26026 22985 41208 2,215,606 2,197,825 17,780
25 350.9793 msecs 11,864 4025 695 50936 350,979 339,275 11,704
26 650.9386 msecs 11,695 7326 4443 70392 650,938 626,434 24,504
27 11.2562 secs 11,793 132214 128675 109304 11,256,223 11,211,378 44,845
28 4.5728 secs 11,819 52883 49679 187128 4,572,770 4,474,294 98,476
29 4.2294 secs 11,907 48300 45216 342776 4,229,449 4,056,522 172,927
30 10.6122 secs 11,759 124766 56010 62808 10,612,244 10,610,509 1,735
31 9.2328 secs 11,884 109705 41191 63416 9,232,760 9,231,168 1,592
32 14.3117 secs 11,922 170592 103053 64632 14,311,717 14,309,552 2,165
33 55.8702 secs 11,902 664893 596368 67064 55,870,151 55,862,085 8,066
34 22.1413 secs 11,923 263922 195453 71928 22,141,326 22,135,223 6,103
35 1.0531 mins 11,927 753508 683623 81656 63,186,883 63,175,281 11,602
36 28.3459 secs 11,924 337734 269198 101112 28,345,873 28,323,662 22,210
37 9.2387 mins 11,860 6573832 6505951 140024 554,319,152 554,275,660 43,492
38 11.2025 secs 11,926 132534 64338 217848 11,202,535 11,113,380 89,154
39 4.5557 mins 11,925 3257543 3189102 373496 273,342,973 273,170,580 172,393
40 13.1216 mins 11,927 9389808 7285993 124248 787,294,602 787,289,468 5,133
41 10.3313 mins 11,929 7394352 5292081 124856 619,880,117 619,878,329 1,787
42 3.8015 mins 11,935 2722138 620876 126072 228,090,413 228,087,570 2,842
43 5.7648 mins 11,924 4124314 2019820 128504 345,888,060 345,884,231 3,828
44 3.2043 mins 11,930 2293481 193018 133368 192,258,803 192,252,406 6,397
45 33.9166 mins 11,919 24254078 22153676 143096 2,034,994,703 2,034,982,887 11,815
46 47.9810 mins 11,922 34321486 32221012 162552 2,878,859,972 2,878,832,117 27,854
47 2.4000 hours 11,918 102968649 100868429 201464 8,639,864,920 8,639,820,958 43,962
48 4.1320 hours 11,924 177371081 175268406 279288 14,875,131,910 14,875,045,149 86,760
49 23.9987 hours 11,914 1029325281 1027225432 434936 86,395,345,966 86,395,170,751 175,214
============== ====== ============== ============== ===========
11,630 118,106,695,147 118,105,560,480 1,134,666
Where test test number
time run time needed to find the private key
hps hops per second (averaged 11,630 on my laptop with a highly modified secp256k1 library)
hops total number of hops it took to find the private key
cmps total number of point comparisons it took to find the private key
mem amount of memory dynamically allocated during the run
total time total run time in msec
time hopping total time spent hopping in msec
not hopping the overhead (time not hopping) in msec
|
|
|
|
Terminology for the science fair project We have created the following terminology, inspired by the ITU radio bands, that we will be using to describe the relative entropy of the various private keys. For example private keys that have between 61 and 70 bits are called "low entropy" or LE private keys. Keys that use between 91 and 100 bits are called "high entropy" or HE private keys. The entire scale is as follows: max bits entropy range designation
-------- -----------------------------
10 RLE Ridiculously Low Entropy
20 TLE Tremendously Low Entropy
30 ELE Extremely Low Entropy
40 SLE Super Low Entropy
50 ULE Ultra Low Entropy
60 VLE Very Low Entropy
70 LE Low Entropy
80 MLE Medium Low Entropy
90 MHE Medium High Entropy
100 HE High Entropy
110 VHE Very High Entropy
120 UHE Ultra High Entropy
130 SHE Super High Entropy
140 EHE Extremely High Entropy
150 THE Tremendously High Entropy
160 RHE Ridiculously High Entropy
Using this terminology everyone is currently searching for a HE private key (105) and our program is currently only capable of finding ULE private keys in a 24 hour period: ver = 138 with 128 bit integers, sizeof(int) = 4
test = 53
seed = none (default value)
bits = 54
a = 0x20000000000000
b = 0x3FFFFFFFFFFFFF
P = 0x034AF4B81F8C450C2C870CE1DF184AFF1297E5FCD54944D98D81E1A545FFB22596 (33 bytes)
ba = 0x1FFFFFFFFFFFFF
k0000 = 0x2DCF462904B478D8
s = 0x236FB6D5AD1F43
s*G = 0x034AF4B81F8C450C2C870CE1DF184AFF1297E5FCD54944D98D81E1A545FFB22596 (33 bytes)
time = 13.6929 hours(49294385241200 nsecs)
hps = 5460.352734
We are making progress and we still have not converted our unique implementation of the algorithm to be run on a GPU or FPGA yet. Using this terminology we can say that our program can pretty easily find all RLE and TLE keys in simple brute force mode [set the PRF to always return 1]. Here are the execution times and number of hops in brute force mode from our program for the RLE, TLE and ELE private keys: bits brute force time hops (of 1*G)
---- ---------------- -------------
1 0.8077 msecs 1
2 0.8464 msecs 1
3 9.8947 msecs 1
4 7.3781 msecs 8
5 12.5342 msecs 11
6 10.0498 msecs 15
7 20.7085 msecs 52
8 16.8994 msecs 32
9 15.0751 msecs 45
10 114.3055 msecs 510
11 207.3905 msecs 893
12 298.7654 msecs 1413
13 642.6892 msecs 2976
14 1.2877 secs 5840
15 1.2414 secs 5901
16 2.9654 secs 14026
17 7.3875 secs 35249
18 13.4464 secs 63475
19 34.9504 secs 166753
20 38.9897 secs 185259
0x034AF4B81F8C450C2C870CE1DF184AFF1297E5FCD54944D98D81E1A545FFB22596 54 bit 222872.369 h/s 223958.708 h/s 223408.635 h/s ... 221374.437 h/s 222090.945 h/s 220270.176 h/s total time: 1089.12 sec SOLVED: 9974455244496707 Hops: 246139766 Very impressive h/s. Thanks for the numbers. It gives us something to shoot for. |
|
|
|
I am up for testing also? It is live on GitHub yet?
Hello, I am glad to participate in this project.
Regarding the Elliptic Curve, I think there is a weakness in the current Algorithm.
Also, I'm interested in testing... the fpga port.
I realise that is a far way off, and I'm willing to help with the development if you and your daughter are open to the idea.
You have been added to the list of possible testers. See the OP of this thread. Whatup whatup, all doing their own test, nice to have something to test on a pkey or address,
how should i know how it works, i don't know, any news fpga or gpu or cpu dont matter, i'm in,
systems ready, got two days off,
so love peace out,
You are already on the list. We are still working on our first release of code. |
|
|
|
Does anyone know why this post has been erased? it is still here because "brainless" quoted it?
Yes, your entire conversation is still in the thread, again: Please note that since this thread will be used as reference material in a science fair project we delete most posts in this thread just to keep it clean. In other words, once a post is quoted then we delete the original post. Your posts will all still be in the thread.The thread stays shorter and cleaner this way. I hope this is not an issue for anyone. It is just to keep the thread as short and clean as possible. It is not because we do not appreciate your posts. We do!Thanks! |
|
|
|
I draw your attention, secp256k1_scalar_set_int() has x32-x64 problem my fix void secp256k1_scalar_set_uint64(secp256k1_scalar *r, uint64_t v){
#if defined(USE_SCALAR_4X64)
r->d[0] = v;
r->d[1] = r->d[2] = r->d[3] = 0;
#elif defined(USE_SCALAR_8X32)
r->d[0] = (uint32_t)(v);
r->d[1] = (uint32_t)(v>>32);
r->d[2]=r->d[3]=r->d[4]=r->d[5]=r->d[6]=r->d[7]=0;
#endif
}
I must probably unsubscribe to the developers  I completely forgot maybe your problems grow from here. We also found this issue and also quickly created our own functions to get it to work. We also called our new functions secp256k1_scalar_set/get_uint64 so I guess great minds think alike!  We were just trying to quickly get everything to work so we have not optimized anything yet. Our function was: static uint64_t secp256k1_scalar_get_uint64(secp256k1_scalar * a)
{
uint8_t b32[32];
secp256k1_scalar_get_b32(b32, a);
const uint64_t ret =
((uint64_t)b32[24] << 56 ) |
((uint64_t)b32[25] << 48 ) |
((uint64_t)b32[26] << 40 ) |
((uint64_t)b32[27] << 32 ) |
((uint64_t)b32[28] << 24 ) |
((uint64_t)b32[29] << 16 ) |
((uint64_t)b32[30] << 8 ) |
((uint64_t)b32[31] << 0 ) ;
return ret;
}
Obviously yours is much better/faster so we have replaced ours with yours. Thanks! ENDOMORMPHSIM
Endomorphism is implemented here only to accelerate the signing of the transaction, so do not expect this to accelerate the usual multiplication. When we ran our benchmark there was no difference. That explains it, so thanks. We have turned off this flag since it does not help us. We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance?
table #1 eprint.iacr.org/2016/103.pdf The size of a pre-computed table in memory is created just for this. Speeds up multiplication in exchange for RAM. Ryan also used the increased size -w 18/20/22/24.. in the brainflayer. ECMULT_WINDOW_SIZE? maybe ECMULT_TABLE_SIZE with WINDOW_G? ecmult_impl.h #else
/** One table for window size 16: 1.375 MiB. */
#define WINDOW_G 16
#endif We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance?
questions like these can only be answered with a well designed benchmark. in this case you have to measure how long it takes to do the precomputation with different values ∈ [2, 24] and how that compares with the rest of computation. if the rest is significantly longer then it can justify that long initial precomputation and allocation of memory. Thanks for the very useful information. We will play with this setting in the future. We also found this in the code: /** Larger values for ECMULT_WINDOW_SIZE result in possibly better
* performance at the cost of an exponentially larger precomputed
* table. The exact table size is
* (1 << (WINDOW_G - 2)) * sizeof(secp256k1_ge_storage) bytes,
* where sizeof(secp256k1_ge_storage) is typically 64 bytes but can
* be larger due to platform-specific padding and alignment.
* If the endomorphism optimization is enabled (USE_ENDOMORMPHSIM)
* two tables of this size are used instead of only one.
*/
# define WINDOW_G ECMULT_WINDOW_SIZE
/* Noone will ever need more than a window size of 24. The code might
* be correct for larger values of ECMULT_WINDOW_SIZE but this is not
* not tested.
*
* The following limitations are known, and there are probably more:
* If WINDOW_G > 27 and size_t has 32 bits, then the code is incorrect
* because the size of the memory object that we allocate (in bytes)
* will not fit in a size_t.
* If WINDOW_G > 31 and int has 32 bits, then the code is incorrect
* because certain expressions will overflow.
*/
#if ECMULT_WINDOW_SIZE < 2 || ECMULT_WINDOW_SIZE > 24
# error Set ECMULT_WINDOW_SIZE to an integer in range [2..24].
#endif
|
|
|
|
We now have a compile time switch between OpenSSL, secp256k1(SCALAR_8X32, FIELD_10X26), secp256k1(SCALAR_4X64, FIELD_5X52), and secp256k1(SCALAR_4X64, FIELD_5X52, ENDOMORMPHSIM). Here is the run time and hops per second comparison for the 32 unit tests: pkey Standard OpenSSL library secp256k1 (S 8X32, F 10X26) secp256k1(S 4X64, F 5X52) secp256k1(S4X64, F5X52, EM)
bits hops/second test run time hops/second test run time hops/second test run time hops/second test run time
==== =========================== =========================== =========================== ===========================
1 2003.205128 6.0950 msecs 5114.435494 6.3592 msecs 4318.255425 6.4021 msecs 5269.397971 5.8835 msecs
2 1757.199025 8.3635 msecs 4655.764418 7.8586 msecs 5142.049107 7.0887 msecs 4802.497299 7.6262 msecs
3 1716.811880 5.9904 msecs 5003.752815 6.9754 msecs 5110.514884 6.0526 msecs 4268.487888 6.8087 msecs
4 1960.438354 26.3895 msecs 5092.427560 27.7752 msecs 5187.260089 7.4309 msecs 4996.252810 7.7770 msecs
5 1880.119970 30.0658 msecs 5013.009954 31.3478 msecs 5215.318134 9.4163 msecs 5236.254831 9.7029 msecs
6 1608.708475 30.6862 msecs 4410.467510 30.2971 msecs 4926.917392 22.3417 msecs 5644.933672 20.1065 msecs
7 1866.896315 34.8628 msecs 5558.843043 31.2577 msecs 5131.685676 21.5328 msecs 5181.347150 20.9325 msecs
8 1990.502460 31.4858 msecs 5039.596832 30.4067 msecs 4838.430966 20.6268 msecs 5072.279990 28.5510 msecs
9 1928.760658 40.3494 msecs 4950.639215 41.2204 msecs 5260.714838 22.1908 msecs 5241.170939 20.5226 msecs
10 1890.373754 81.8738 msecs 5256.467332 57.0551 msecs 5429.994625 32.7629 msecs 5453.290894 41.4165 msecs
11 1694.971872 101.2429 msecs 4763.924918 61.4267 msecs 5340.172912 41.3388 msecs 5439.249145 46.5306 msecs
12 1858.940556 1.0718 secs 5145.349959 527.2134 msecs 5326.737472 410.4776 msecs 5221.758623 434.4509 msecs
13 1895.071971 51.6923 msecs 5386.060874 38.1821 msecs 5233.349227 23.4991 msecs 5373.390968 31.1977 msecs
14 1908.767643 896.4858 msecs 5082.972044 385.9540 msecs 5430.446276 321.9922 msecs 5441.145301 317.7290 msecs
15 1939.352878 439.6496 msecs 5326.381969 195.0367 msecs 5488.742759 160.9818 msecs 5420.695712 179.5955 msecs
16 1918.732814 530.3667 msecs 5258.277326 219.2995 msecs 5510.868625 188.6750 msecs 5466.555751 201.7339 msecs
17 1895.048388 205.8168 msecs 5430.753319 95.6410 msecs 5453.448080 79.5526 msecs 5339.284536 85.5150 msecs
18 1930.620117 1.3492 secs 5136.760660 546.6825 msecs 5545.967087 474.6491 msecs 5433.455762 484.8219 msecs
19 1959.292325 594.2687 msecs 5364.976931 228.5351 msecs 5407.810389 219.3399 msecs 5489.027106 219.1785 msecs
20 1937.090596 1.2060 secs 5519.443944 438.4141 msecs 5567.924674 427.1013 msecs 5487.179193 432.8127 msecs
21 1934.545311 2.1349 secs 5493.508717 774.8660 msecs 5504.112724 758.1783 msecs 5469.417987 766.5974 msecs
22 1929.260673 3.4962 secs 5376.994864 1.2774 secs 5564.087823 1.2174 secs 5465.781801 1.2414 secs
23 1934.889761 7.0861 secs 5476.220007 2.5224 secs 5548.504187 2.4744 secs 5465.500565 2.5118 secs
24 1939.683627 5.8652 secs 5461.486912 2.1110 secs 5548.744349 2.0488 secs 5417.722111 2.1042 secs
25 1925.342112 47.4712 secs 5476.818503 16.7678 secs 5557.570589 16.4377 secs 5479.097929 16.6700 secs
26 1930.362383 16.1728 secs 5486.557150 5.7494 secs 5553.792419 5.6187 secs 5544.780029 5.6293 secs
27 1945.269663 7.2153 secs 5443.169561 2.6035 secs 5534.059747 2.5462 secs 5507.743611 2.5530 secs
28 1920.384111 37.4526 secs 5479.914967 13.1715 secs 5553.680361 12.9380 secs 5507.436467 13.0454 secs
29 1940.307975 7.8315 secs 5530.787084 2.7661 secs 5547.749218 2.7347 secs 5510.767015 2.7558 secs
30 1927.658333 1.1905 mins 5468.604811 25.2139 secs 5438.685448 25.3136 secs 5555.456216 24.7841 secs
31 1942.378857 28.4496 secs 5520.634781 10.0240 secs 5501.207943 10.0433 secs 5510.264398 10.0245 secs
32 1904.831829 59.7541 secs 5521.457239 20.6445 secs 5537.529539 20.5532 secs 5496.131886 20.7084 secs
Standard OpenSSL library averaged 1897 hops per second secp256k1 (S 8X32, F 10X26) averaged 5258 hops per second secp256k1(S 4X64, F 5X52) averaged 5352 hops per second secp256k1(S 4X64, F 5X52, , ENDOMORMPHSIM) averaged 5350 hops per second We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance? |
|
|
|
One weird thing is that the runs on the Linux machine took longer than the ones on Windows (usually is the other way around). And the other weird thing is that the program is called 'roo' in Windows and 'ROO.exe' in Linux It is actually ROO.exe in Windows but Windows adds the .exe for you and is not case sensitive. ..OpenSSL library is pretty slow.
... ideally you need C bitcoin/secp256k1 ... Thanks for the suggestion! I should have thought of that first. It is silly to use OpenSSL for secp256k1 when there is a highly optimized specialized implementation available. Results available soon. |
|
|
|
We are about to release the first executable of our project for feedback. There will be a Windows 64 bit cygwin version and a 64 bit Linux version. The program is written in C using the standard OpenSSL library BIGNUM and EC_POINT objects. The main thing we are interested in for this release of the program is the number of hops per second on various machines. It seems to us the OpenSSL library is pretty slow. Here is what three runs of the program, for a 35 bit key, looks like on my Windows laptop: C:\ROO\Debug>roo
ver = 121 with 128 bit integers
test = 34
seed = 1566657361 (randomly selected)
bits = 35
a = 0x400000000
b = 0x7FFFFFFFF
P = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba = 0x3FFFFFFFF
k0000 = 0x9D8358B56E7B4401A459C0D828A75681
s = 0x4AED21170
% = 17.0723
s*G = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time = 9.0817 mins (544899402700 nsecs)
hps = 1968.057310
C:\ROO\Debug>roo
ver = 121 with 128 bit integers
test = 34
seed = 1566658074 (randomly selected)
bits = 35
a = 0x400000000
b = 0x7FFFFFFFF
P = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba = 0x3FFFFFFFF
k0000 = 0xC7B9A08889DCE535759804A45AE046BC
s = 0x4AED21170
% = 17.0723
s*G = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time = 9.0295 mins (541767121800 nsecs)
hps = 1986.290418
C:\ROO\Debug>roo
ver = 121 with 128 bit integers
test = 34
seed = 1566658634 (randomly selected)
bits = 35
a = 0x400000000
b = 0x7FFFFFFFF
P = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba = 0x3FFFFFFFF
k0000 = 0xDF1DD25825020380D574A71285072428
s = 0x4AED21170
% = 17.0723
s*G = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time = 9.0542 mins (543253475900 nsecs)
hps = 1981.294420
C:\ROO\Debug>
And here are three runs on my Linux machine. Maybe I just need to buy a much faster computer. burt@burt-MS-7640:~/ROO1/Debug$ ./ROO.exe
ver = 121 with 128 bit integers
test = 34
seed = 1566661363 (randomly selected)
bits = 35
a = 0x400000000
b = 0x7FFFFFFFF
P = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba = 0x3FFFFFFFF
k0000 = 0xE6A6C5C436EBA130AD726DC36B710275
s = 0x4AED21170
% = 17.0723
s*G = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time = 15.0364 mins (902182961776 nsecs)
hps = 1225.428980
burt@burt-MS-7640:~/ROO1/Debug$ ./ROO.exe
ver = 121 with 128 bit integers
test = 34
seed = 1566663911 (randomly selected)
bits = 35
a = 0x400000000
b = 0x7FFFFFFFF
P = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba = 0x3FFFFFFFF
k0000 = 0x1970EBB70E07E6F19E9D0390432AD93C
s = 0x4AED21170
% = 17.0723
s*G = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time = 14.6529 mins (879173107944 nsecs)
hps = 1219.290980
burt@burt-MS-7640:~/ROO1/Debug$ ./ROO.exe
ver = 121 with 128 bit integers
test = 34
seed = 1566665966 (randomly selected)
bits = 35
a = 0x400000000
b = 0x7FFFFFFFF
P = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba = 0x3FFFFFFFF
k0000 = 0x504A020DE4246A5FF39CD676B27DD5A3
s = 0x4AED21170
% = 17.0723
s*G = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time = 14.7170 mins (883021823424 nsecs)
hps = 1217.660480
burt@burt-MS-7640:~/ROO1/Debug$
|
|
|
|
(auto-translate) Now some super secret asic boost algorithm is being heard. Who knows what about him?
Consider several ways to find a hash with a given complexity
1. Sequential nonce from zero
2. Sequential search not from zero, but from a random point
3. Random search nonce.
Now each of the methods is separate. For clarity, let nonce vary from 0 to 1,000,000 and let us look for a hash with three zeros
Sequential nonce from zero .
In this case, the miner will find the hash on average for 3845 iterations, but with a probability of 61% iterations will be less. That is, Of the 100 hashes found, 61 hashes will be found faster than in 3845 iterations.
Sequential enumeration not from zero, but from a random point
In this case, the miner will find the hash on average for 3845/2 = 1923 iterations, while with a probability of 39.4% iterations will be less (I calculated this additionally). That is, out of 100 hashes, 40 will be found faster than in 1923 iterations.
Twice as fast as in the first case! This is because the random beginning, with a normal distribution, will fall on average to the center of the segment for enumeration.
Also in this method with a probability of 259/1000000 the hash will be found immediately.
Random brute force nonce.
In this case, you can never find the desired hash at all, but with a probability of 259/1000000, the hash will be found on the first try. If the random distribution is distributed normally, then the probabilities should add up, which means after 1923 iterations the probability of finding a hash will be already 50%. That is, out of 100 hashes, 50 will be found faster than in 1923 iterations.
As a result, it turns out that the first algorithm is the slowest. The third algorithm is the fastest. If I haven’t messed up anything of course ...
and googling "Probabilistic Bitcoin Mining Method" What u know about this? (given the probabilistic nature of the kangaroo, this can help) This is all about hashing, kangaroo does not use hashing anywhere in the algorithm. Kangaroo only works when the public key is known. |
|
|
|
|
Show Posts
