It happened when solving the problem with DP 13, I also wanted to add with over 6 million kangaroos dead.
The problem occurred in v2.1
What do you mean by "adding 6 million kangaroos dead" ? Did you modify the code ? |
|
|
|
Could someone explain to me why this happened?
This should not happen. Which release is producing wrong collisions and in which cases (merging work file, basic usage, ..) ? Could someone tell me how to set the parameter -m ? And what does 'expected operations' number mean?
On the plot in github I see that there is chance like +- 99% when the number of group operations is 6*sqrt(n).
If for example program shows 'Expected operations: 2^44.10', when may I assume there is no result? 2^44.10? 2^45? Sooner, later?
The expected number of operation is the average number of group operations needed to solve the key (including the DP overhead). It correspond to ~50% probability. If you use -m 3 and if the search is aborted, you are sure at ~99.7% that the key is not in the given range. |
|
|
|
I won't implement a rho method for secp256k1. It is not feasible to reach a solution using this method. I haven't seen this paper discussed here: https://cr.yp.to/dlog/cuberoot-20120919.pdfThere are a number of good points in it but particularly the point of generating *better* distinguished points by preferentially keeping ones that have longer walk lengths is interesting. Thanks for the reading. I didn't read it yet. I suppose that when you speak of walk length, you mean the total number of jumps of the walk, not the total traveled distance. The problem of storing length of walk is that on GPU access to global memory is very slow. I will see if I manage to improve things. |
|
|
|
Thanks for the reading  It seems they have built a very similar algorithm than my DRS62 modular inversion. It is clearly faster than the Fermat/Euler method for secp256k1 prime. Depending on platform, the DRS62 cost is around 150 ModSquare (with ModSquare optimized for secp256k1 prime). |
|
|
|
|
Searching on range larger than 126 bits will decrease performance a lot.
If you want to modify the code, the modification are not very difficult.
You have to change the structure and the interface in the HashTable to accept larger distance and restore 256 bit distance in the GPU code.
|
|
|
|
A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller |
|
|
|
Yes and the overlap between these ranges will be very small unless you search on very large range. I'm wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution. Of course computing a modexp is expensive but just for try... 0^((P-1)/3): 0
1^((P-1)/3): 1
2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
6^((P-1)/3): 1
7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
8^((P-1)/3): 1
9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
10^((P-1)/3): 1
11^((P-1)/3): 1
12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
13^((P-1)/3): 1
14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
17^((P-1)/3): 1
18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
19^((P-1)/3): 1
20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
|
|
|
|
All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back
Yes I know, but I don't see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles. If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk. Any idea would be welcome |
|
|
|
Jean_Luc, hi. Then you include endomorfism to yout project - vanitysearch and kangaroo ?
VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry. Now we need a rule to define a unique representative for each equivalence class {P,−P}. A simple rule in this case is: treat they-coordinate of P as an integer 0≤yP< qand let the unique representative be (xP,min{yP,q−yP}). The pseudorandomwalk is then defined using the unique equivalence class representative.
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdfBut symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance. |
|
|
|
Thanks I found the issue. |
|
|
|
I implemented the algorithm 3.74 of the above book and I found different results: At iteration #70/#71, I well found the same constants a1 and a2 that are mentioned in the comment of the code. but b1 and b2 are different and strangely b2=a1 in the comment  I would expect b1 = -1839468DB3DC795B42AD17D3CA5C15137 and b2 = 4A5AC2BF7B5F37F9F1DB10D7A2A9C981. I didn't check yet g1 and g1 constants. * "Guide to Elliptic Curve Cryptography" (Hankerson, Menezes, Vanstone) gives an algorithm
* (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1
* and k2 have a small size.
* It relies on constants a1, b1, a2, b2. These constants for the value of lambda above are:
*
* - a1 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
* - b1 = -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3}
* - a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8}
* - b2 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
s0=1
t0=0
r0=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
s1=0
t1=1
r1=5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72
s2=1
t2=E
r2=5D4F819BEEB6D5E108DABF867C8D2F0842474284DC46CD122CA9B187ECB08EB
...
s70=FCE9B1DD4EB7DD2718A2906787061B2
t70=4A5AC2BF7B5F37F9F1DB10D7A2A9C981
r70=114CA50F7A8E2F3F657C1108D9D44CFD8 (>sqrt(n))
s71=4A5AC2BF7B5F37F9F1DB10D7A2A9C981
t71=1839468DB3DC795B42AD17D3CA5C15137
r71=3086D221A7D46BCDE86C90E49284EB15 (<sqrt(n))
|
|
|
|
@gmaxwell Many thanks I discovered this book "Guide to Elliptic Curve Cryptography" which is great |
|
|
|
The existence of the endomorphism is a roughly 20% speedup in a plain multi-exp due to halving the number of doublings. What it does is gives many algorithms which could be batched across multiple point the efficiency they'd have at twice the number of pubkeys. It's a pretty big speedup and AFAIK at an equivalent level of optimization it makes secp256k1 the fastest to verify of any widely deployed curve. So the motivation there is pretty clear, I think.
Could you give more info on this because I don't see how to have efficient decomposition k.P= (k1+k2.lambda).P using such lambda. Thanks |
|
|
|
|
I don't think these parameters have been chosen more or less randomly, just to ease some calculations, and that we can say that "bitcoin is lucky".
They probably make a search to get a prime near 2^256 for the field, a prime order, a large enough embedding degree, etc, ...
However, the endormposhism (x,y)->(beta.x,y) is strange. There is well a (lamba,beta) such as lambda^2 + lamda + 1 = 0 (mod n) and beta^2 + beta + 1 = 0 (mod p) (a primitive cubic root of unity, p=1(mod 3) and n=1(mod 3)) but the value of lambda does not bring very interesting things. No speed up in doubling or adding formula. This choice is strange and may be the weakness (if there is a weakness) will come from complex multiplication or something in this area...
|
|
|
|
|
If you know a way with stride/variable increment/etc to solve #120 faster than kangaroo with bitcrak then you should write a tool that just compute pubkeys without hashing as you have it. It will be faster than bitcrack mods...
|
|
|
|
So probably a few seconds of planned LHC successor... Is yours as sensitive as LHC and also detects TGVs?
No, I'm not working in a collisioner but in a light source. We accelerate electron (6Gev) to produce hard Xrays. Coal-running GPUs ;-) It would be interesting to calculate how much CO2 was produced for it.
Something like ~15/20tons of CO2 if considering that all coming from coal. |
|
|
|
Wow... 1000 years of of 1000W coffee machine running 5minutes per day ;-)
And few hours of operation of the accelerator where I'm working and few minutes of operation of the LHC  However this value I gave is a overestimated because we got an unwanted interruption during the run due to a storm and when Zielar restarted the GPUs he forget a setting and GPU were not running at 100%. I also probably overestimated the power of the ~80 hosts which hosting GPUs and of the infrastructure. GPUs are in Poland?
Yes |
|
|
|
how many kW is it consuming per hour?
20? 150?
Power: ~94KW For #115 it consumed 94*13*24 = 29.3 MWh and the prize was 1.15BTC (+1.15 BCH) |
|
|
|
|
Show Posts
