Se non apro, monetizzo il fork, nessuno mi può dire che ho qualcosa che non esiste (diverso se lo faccio e lo nascondo)...mi viene contestato?...lo faccio al momento e ti dimostro che non ne sono mai stato in possesso e non è mia intenzione esserlo.
Tu mi puoi anche regalare dei soldi...se io non li voglio...non li prendo.....di certo non li dichiaro come regalo o cavolo si debbano dichiarare
Tecnicamente se tu possedevi un btc prima del fork bch, dopo il fork hai un btc + un bch. La stessa chiave privata li controlla entrambi. Il fatto poi che tu non muova il bch non dimostra affatto "che non ne sono mai stato in possesso e non è mia intenzione esserlo", è proprio vero il contrario, tu sei stato in possesso di quella informazione e di conseguenza di quella moneta. Se non muovere una moneta fosse una dimostrazione di non possesso, allora basterebbe tenere fermi 5 anni i propri btc per potersi dichiarare "innocenti". Anche il concetto di "se non li voglio ... non li prendo" non si adatta bene al mondo delle criptovalute, se conosci la chiave privata di fatto ne sei il proprietario, l'unico modo per "rifiutarli" sarebbe bruciarli in qualche burn address. |
|
|
|
|
Recap of my tests:
1)
normal generation of jumps
20000 walks
num_jumps: 32 + 32
max_length of each walk = 32
jumpbit = 20
7516 loops of length 2, 118 of length 4:
(7516+118+4+2) / 20000 = 38,2 % of the walks have a loop before 32 steps
7516/20000 = 37,58% of the walks have a loop with 2 only points
[7516, 0, 118, 0, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------------------------------------------------------------------------------------------------------------------------------
2)
if(next_jump != -prev_jump): ok
else
next_jump = prev_jump #(you double the previous jump)
20000 walks
num_jumps: 32 + 32
max_length of each walk = 32
jumpbit = 20
0 loops of length 2, only 139 loops of length 4 and 7 of length 6:
(139+7+9+1+3) / 20000 = 0,795 % against 38,2%!
[0, 0, 139, 0, 7, 0, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
----------------------------------------------------------------------------------------------------------------------------------------------------
3)
if(next_jump != -prev_jump): ok
else
next_jump = -sign(next_jump)*floor(distAvg)*G #a different step, with the opposite sign of the normal step
20000 walks
num_jumps: 32 + 32
max_length of each walk = 32
jumpbit = 20
0 loops of length 2, only 128 loops of length 4 and 6 of length 6, 2 of length 8:
(128 + 1 + 6 +2 + 1 + 1) / 20000 = 0,695% of the walks have a loop before 32 steps
[0, 0, 128, 1, 6, 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-------------------------------------------------------------------------------------------------------------------------------------------------------
4)
if(next_jump != -prev_jump): ok
else
next_jump = prev_jump #(you double the previous jump)
20000 walks
num_jumps: 64 + 64
max_length of each walk = 32
jumpbit = 20
0 loops of length 2, only 40 loops of length 4:
(40+1+1) / 20000 = 0,21 % of the walks enter in a loop in less than 32 steps
[0, 0, 0, 40, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
loops of length 4 are of "second order":
probability that (a+b+c+d=0) = (1/128)*(127/128)*(1/128)
probability that each sequence of 4 consecutive points don't create a loop = (1 - (1/128)*(127/128)*(1/128))^32
probability to find a loop in a walk of 32 steps: 1 - (1 - (1/128)*(127/128)*(1/128))^32 = 0.001936
expected value of number of walks with a loop of 4 points: 2000 * 0.001936 = 38,7
-------------------------------------------------------------------------------------------------------------------------------------------------------
5)
if(next_jump != -prev_jump): ok
else
next_jump = prev_jump #(you double the previous jump)
20000 walks
num_jumps: 64 + 64
max_length of each walk = 128
jumpbit = 20
157 loops of length 4, only 4 loops of length 6:
(157+4+2+1+1+1+1+1+1+2+1+1+1+1+1+1+1) / 20000 = 0,89% of the walks enter in a loop in less than 128 steps
[0, 0, 157, 0, 4, 0, 2, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
|
|
|
|
Many thanks. I will try this tomorrow. Hope the test of the last jump and the symmetry will no kill GPU performance. We have to find a determinist logic to get an other jump if we get the opposite. Thanks  It is only a test between 2 integers (32 bit <-> 32 bit, a previous index with a current index in an array of 32/64 elements, I don't think it is too much ) you compute the next jump as usual, then if(next_jump != -prev_jump): ok else next_jump = prev_jump (you double the previous jump) P -> P+k*G -> P+k*G+k*G Note: in this case the inverse of (x2-x1) is the same: (P + k*G) + k*G has the same inverse of (P+k*G) - k*G, then you can compute the inverse before to check the sign of the y-coordinate and the prev_jump |
|
|
|
I use a random jump table with a controlled average. I store as before, no inforamtion on symetry is needed, the key is solved later. void Kangaroo::CreateJumpTable() {
int jumpBit = rangePower / 2;
if(jumpBit > 128) jumpBit = 128;
int maxRetry = 100;
bool ok = false;
double maxAvg = pow(2.0,(double)jumpBit - 0.95);
double minAvg = pow(2.0,(double)jumpBit - 1.05);
double distAvg;
//::printf("Jump Avg distance min: 2^%.2f\n",log2(minAvg));
//::printf("Jump Avg distance max: 2^%.2f\n",log2(maxAvg));
// Kangaroo jumps
// Positive only
while(!ok && maxRetry>0 ) {
Int totalDist;
totalDist.SetInt32(0);
for(int i = 0; i < NB_JUMP; ++i) {
jumpDistance[i].Rand(jumpBit);
if(jumpDistance[i].IsZero())
jumpDistance[i].SetInt32(1);
totalDist.Add(&jumpDistance[i]);
}
distAvg = totalDist.ToDouble() / (double)(NB_JUMP);
ok = distAvg>minAvg && distAvg<maxAvg;
maxRetry--;
}
for(int i = 0; i < NB_JUMP; ++i) {
Point J = secp->ComputePublicKey(&jumpDistance[i]);
jumpPointx[i].Set(&J.x);
jumpPointy[i].Set(&J.y);
}
if(!ok) {
::printf("Warning, jump Avg distance out of bounds: 2^%.2f (restart the program)\n",log2(distAvg));
} else {
::printf("Jump Avg distance: 2^%.2f\n",log2(distAvg));
}
}
I simulated many walks with your CreateJumpTable (I did a porting in python). I found a very interesting thing: finally I know how are these loops!! I started 2000 walks (not together, I was interested in 'selfcollisions' only) from a position '0', and using only integer numbers I found out that: almost all cycles have length exactly = 2!I generated 32 positive jumps (and the 32 negative, don't worry, it is like you did but I prefer to write them) jumpBit = 20
[b]Jump Avg distance[/b]:
minAvg, [b]distAvg[/b], maxAvg
506428.82601934916 [b]530326.5625[/b] 542776.9763909484
[907868, -907868, 716251, -716251, 1007711, -1007711, 720977, -720977, 901512, -901512, 835718, -835718, 363381, -363381, 475363, -475363, 770732, -770732, 217555, -217555, 67168, -67168, 615504, -615504, 584908, -584908, 768134, -768134, 450427, -450427, 926634, -926634, 458021, -458021, 854265, -854265, 589522, -589522, 280841, -280841, 172112, -172112, 32886, -32886, 279644, -279644, 525179, -525179, 200017, -200017, 372430, -372430, 66448, -66448, 905754, -905754, 1000160, -1000160, 331424, -331424, 170629, -170629, 401275, -401275]
and these are the results: I got 787 (39,35%) collisions (only cycles!!) over 2000 walks (I stopped each walk after 32 steps) but the most important thing is that I understood why. 783 over 787 has length 2!! Only 2 loops have length 4 and other 2 loops have length 6. This is logic: what is the chance that a point Q produces a loop of length 2? Q -> R -> Q The probability is 1/64 (1/(number of effectively different jumps), if the jumps from R and Q is opposite to the jumps from Q and R. Then when you produce a sequence of points, each point you generate has the probability 1/(number of effectively different jumps)) to create a loop of length 2 with the next point! Some basic computation: probability to meet a 1 point that create a loop of length 2 with the next point: 1/NUM_JUMPS probability to generate 32 (or 2^DP) consecutive points that not produce a 2-loop : (1 - 1/NUM_JUMPS)^32 probability to generate 32 consecutive points with at least one that produces a 2-loop: 1 - (1-NUM_JUMPS)^32 in my case: 1 - (1 - 1/64)^32 = 0.39586 probability of collision in a walk The bad news is that I had to put a large number of random jump (65536) to avoid cycles and this will decrease GPU performance  I will investigate on choosing these jumps in order to reduce probability of cycle and having the smallest possible jump table. This explain perfectly why you have to use 65536 jumps instead of 32, because in this way you got: 1 - (1 - 1/65536)^32 = 0.000488The simplest way to avoid to use a large number of jumps and to avoid almost all loops is to modify the condition of the jump, you have to store the last movement (jump): you have: P -> Q -> R when you have to decide how to do the next jump (from Q to R), do it normally unless the random jump is the opposite of the previous, in that case instead of doing -k*G do +k*G (in this way you avoid the loop and mantain the symmetry). EDIT: the probability to have a loop of length 3 is instead very low, because you should have 3 numbers (jump) a,b,c such that a + b + c = 0 and that is not frequent (a,b,c are 3 random numbers between 32(64) generated in a 2^20 space!) Second test: 20000 walks: 7610 loops of length 2, 101 loops of length 4, 5 loops of length 6, .... this is the sequence of lenght of each loop: -> 7610, 0, 101, 0, 5, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 9, 0 38,05 % of walk fall in a 2-loop! 38,66 % of loops in walks limited to 32 steps ... |
|
|
|
There are only positive jumps in this table.
Loop are still possible because of the equivalence class switch "(xP,min{yP,q−yP})".
Only positive? Why? You mean you store only +k*G but you do -k*G too? The bad news is that I had to put a large number of random jump (65536) to avoid cycles and this will decrease GPU performance I will investigate on choosing these jumps in order to reduce probability of cycle and having the smallest possible jump table. I will try with python to do some tests. Could you provide me only the array of jumps you used? like: [+-1,+-2,+-4,+-8,+-16]. Given m and DP I want to see if we can set up a suitable array of jumps such that we minimize the probability of cycle. You have to change your jumps. But choose them in a "intelligent" way, I think it is not too difficult.
'Intelligent' means that a man can't do this, let the probability do it. I think that the main problem is that you want to choose the jumps by yourself. Why?
You should study separately a sequence of jumps such that the probability to come back before 2^DP steps is low. This study depends only from jumps, DP and m (the average jump), not from points/coordinates/N!
For example, with these jumps [+-1,+-2,+-4,+-8,+-16] you try to generate many sequences (starting from 0). If the number of sequences with lenght < 2^DP (or < k*2^DP) is too high, change randomly the jumps and retry. Lenght of sequence: number of steps before to get back to 0. Deal simply with integer numbers.
This setting phase should be done automatically at the start of the program. In this way for each DP you will have configured the jumps in order to get a lower probability of generating loops.
|
|
|
|
The number field sieve is applicable to finite fields and to elliptic curves that admit embeddings into relatively small finite fields. Such elliptic curves are called pairing-friendly, and are not normally used for ordinary ECDH key agreement or ECDSA or EdDSA signatures like Bitcoin—secp256k1, for instance, ...
It is not allowed to copy something without quoting the source: https://crypto.stackexchange.com/questions/52655/what-are-the-fastest-attacks-on-ecdlp |
|
|
|
It works with dp=0 because random walk are not really important, they just generate random sequence, and you don't care about the path, so it correctly solve the key (the distance is also stored in the hastable) but with dp>0 paths are of course important.
You're right there is probably a bug with my storage of symmetric point.
I have explained the bug, the bug is not in the storage, is in the way you generate the next step of each sequence: only symmetric jumps (+-G, +-2G, +-4G, +- 17G) lead a tame and a wild from 2 symmetric points (first collision) to other 2 symmetric points until they meet the 'same' 2 DPs (other 2 symmetric points). If we call 2 symmetric point (a collision) T and W=-T , and DP > 0, the next step produces 2 different points: T, W=-T -> T1, W1 -> Tk = DP, Wk != Tk Wk is not a DP!! (x,y), (x,-y) -> (x1,y1), (x1',y1') -> (xk, yk), (xk',yk') same x -> same jump = +s*G -> different points x1 != x1' xk !=xk' if T and W are 2 symmetric points, T1=T+s*G and W1=-T+s*G are not!!! because you use +s*G for T and W, even if they have 2 opposite y-coordinates! You have to use +s*G for T and -s*G for W (or viceversa)!! In this way: T, W=-T -> T1=T+s*G , W1=-T-s*G and T1 = -W1 ! (x,y), (x,-y) -> (x1,y1) , (x1,-y1) same x -> opposite jumps = +-s*G -> symmetric points x1 = x1 |
|
|
|
You still exploit the symmetry. Instead of searching between [0,N] you search between [0,N/2] and there is few calculation to make when a collision on a tame.x and wild.x is reached in order to get the good key. I did test and it works as expected.
I think the trick may be that after sqrt(N) total steps the kangaroos starts to overlap each other, still investigating...
No at all. You are simply searching in the second half of the interval, and you concentrate all the tame there. In fact i have removed the negative jump.
... you search a priv key between [0,N/2]. I spread my tame between [0,N/2.G] and the wild between [P-N/4.G,P+N/4.G] and it converges to expected average of 1.47sqrt(N) using dp=0.
You would have the same exact result (with DP > 0) of this: given [a,b], translate to [0,N] and search between [N/2, N]tame start from [N/2,N] wild from [(P-N/2) - N/4, (P-N/2) + N/4] = [P - 3N/4, P - N/4] you don't need the symmetry to do this. You are using the old algorithm with different start ranges. Instead of searching between [0,N] you search between [0,N/2] and there is few calculation to make when a collision on a tame.x and wild.x is reached in order to get the good key.
with dp=0 there is not much bad collisions, no more than expected.
Strangely when using dp > 0, lots of dead kangaroos appear and probably cycle, even with a small number of kangaroo. I have to understand why may be bug somewhere...
Bug found!if tame.x = wild.x how can you detect the collision? they move from (-Q , Q) to (-Q+k*G , +Q+k*G) same x, same jump, different paths. If you don't use negative jumps (+kG and -kG), this is not possible. This explain pefectly why when you set DP > 0 you pass from 1.47.sqrt(N) to 2.sqrt(N), because: -Q != Q tame.x = wild.x could be a collision, but at next step: -Q != Q --> -Q+k*G != Q+k*G you have now 2 separate walks tame.x = wild.x tame.x != wild.x then tame and wild don't reach a common DP, unless you turn -Q and Q into distinguished points setting DP=0. With DP>0 tame.x = wild.x (-Q != Q) becomes a collision not detectable. |
|
|
|
In fact i have removed the negative jump.
There is no need to do complex thing in order to take benefit of symmetry, the main trick is just to translate the public key by -N/2.G and you search a priv key between [0,N/2]. The symmetry is 100% free.
If you have removed the negative jumps you are not exploiting the symmetry! If a tame and a wild meet 2 symmetric points (same coordinate-x), they don't collide! As I have a large number of kangaroo, each kangaroo does not move a lot. The average distance for sqrt(N/2) steps in (N/2)/numberOfKangaroo.
with dp=0 there is not much bad collisions, no more than expected.
Strangely when using dp > 0, lots of dead kangaroos appear and probably cycle, even with a small number of kangaroo. I have to understand why may be bug somewhere...
Loops are not possible if you go always in one direction. |
|
|
|
I must say I'm a bit lost, they announced an algorithm in 1.36√N and they measured 1.47√N. They say that the complexity is actually (1.36 + epsilon)√N and they estimate this epsilon to ~0.1 without being clear on it. https://www.iacr.org/archive/pkc2010/60560372/60560372.pdfIf we compute the complexity of a symmetric set, we have well : (2(2−√2)PI)/√2 √N = 1.468√N ! So i would rather say that the complexity is (1.47+epsilon)√N with an epsilon which depend on number of kangaroo, dp and N as for the standard version. Very interesting. I'm still fighting with collision, when using dp > 0, it seems that the symmetry generates a lot of wrong collisions.
From your tests the algorithm converges in 1.47.sqrt(N) with dp=0: I did a test using dp 0 (much slower):
The algorithm runs in 2^20.554 = ~1.47 sqrt(N) (1000 trials) as announced on the paper so it seems ok
but 2.sqrt(N) with dp=3: i did a test with dp 3 and it also converge to 2^21 (same algorithm, no change on the range in function of dp).
This is tricky, there is something I need to understand with those random walks...
Assuming you used the same jumps, there is only one explanation: the algorithm produces a useful collision in 1.47*sqrt(n) steps but you take a long time to detect it because the walks are too short, they collapse in a loop before to reach a DP. It is not a problem of bad collisions between different tames or between different wilds but "between" the same tame / the same wild (loops). Then a wild and a tame meet frequently (first collision after 1.47.sqrt(n)) but they die immediately after. This issue can be fixed (in my opinion), because these bad collisions (I call them "bad collisions 2" = collision with itself = loop) are distinguishable from the others and you can lower them without increasing the other ones. With DP = 3 means that the lenght of many walks are less than 8!!! It takes +36% (1.47 -> 2) to produce a collision followed by a DP!!! You have to change your jumps. But choose them in a "intelligent" way, I think it is not too difficult. 'Intelligent' means that a man can't do this, let the probability do it. I think that the main problem is that you want to choose the jumps by yourself. Why? You should study separately a sequence of jumps such that the probability to come back before 2^DP steps is low. This study depends only from jumps, DP and m (the average jump), not from points/coordinates/N!For example, with these jumps [+-1,+-2,+-4,+-8,+-16] you try to generate many sequences (starting from 0). If the number of sequences with lenght < 2^DP (or < k*2^DP) is too high, change randomly the jumps and retry. Lenght of sequence: number of steps before to get back to 0. Deal simply with integer numbers. This setting phase should be done automatically at the start of the program. In this way for each DP you will have configured the jumps in order to get a lower probability of generating loops. |
|
|
|
Anyway i did a test with dp 3 and it also converge to 2^21 (same algorithm, no change on the range in function of dp).
This is tricky, there is something I need to understand with those random walks...
The data of the article are: N = 2^40 m = 2^11 θ = 2^−5 with 1.47*2^20, very strange... Anyway I learned a lot of things in these 2 days, thank you! I found that distinguished points are not all equal from the point of view of the probability, if you want to precompute them you have to choose carefully (don't simple reuse the DP you found in one run) https://eprint.iacr.org/2012/458.pdfChoosing the most useful distinguished points. Instead of randomly generating T distinguished points, we propose generating more distinguished points, say 2T or 10T or 1000T, and then keeping the T most useful distinguished points.
(This presumably means storing 2T or 10T or 1000T points during the precomputation, but we follow standard practice in distinguishing between the space consumed during the precomputation and the space required for the output of the precomputation. As an illustrative example in support of this practice, consider the precomputed rainbow tables distributed by the A5/1 Cracking Project [26]; the cost of local RAM used temporarily by those computations is much less important than the network cost of distributing these tables to users and the long-term cost of storing these tables.)
The natural definition of “most useful” is “having the largest number of ancestors”. By definition the ancestors of a distinguished point are the group elements that walk to this point; the chance of a uniform random group element walking to this point is exactly the number of ancestors divided by L.
Unfortunately, without taking the time to survey all L group elements, one does not know the number of ancestors of a distinguished point. Fortunately, one has a statistical estimate of this number: a distinguished point found by many walks is very likely to be more useful than a distinguished point found by fewer walks.
This estimate is unreliable for a distinguished point found by very few walks, especially for distinguished points found by just one walk.
I have the feeling that this algorithm win in average complexity by favoriting keys on the middle of the range as the density of wild is increased in the center. It has a worse 'worst case' and a much better 'best case' than the classic algorithm.
Maybe a hybrid approach, with some precomputed DP loaded in hashtable (with the precomputed DP near only to the extreme of the range) to compensate. |
|
|
|
I did a test using dp 0 (much slower):
The algorithm runs in 2^20.554 = ~1.47 sqrt(N) (1000 trials) as announced on the paper so it seems ok but I have to figure out why it is not the case for dp > 0. There is a relationship betwen dp and range size (m√2/3πθ) that I missed.
Will try to undersand, how to choose this m.
this is the difference ? To detect small cycles we stored the previous 30 group elements in the walk
in the case N ≈ 2^34 (respectively, 30, 45 group elements for N ≈ 2^40, 2^48). Each
new step in the walk was compared with the previous 30 (respectively, 35, 45)
group elements visited. If this group element had already been visited then the
walk is in a cycle. We used a deterministic method to jump out of the cycle (using
a jump of distinct length from the other jumps used in the pseudorandom walk)
so that the pseudorandom walk as a whole remained deterministic. The cost of
searching the list of previous group elements is not included in our experimental
results, but our count of group operations does include the “wasted” steps from
being in a cycle.
With these data: N = 2^40 m = 2^11
θ = 2^−5still 2^21? |
|
|
|
In realtà l'acquisto è avvenuto su Conio passando da Hype....e non l'ho fatto io direttamente...ma un mio amico.
Abbiamo 2 possibilità:
1) Hype non ti permette di gestire nulla e fa tutto lui.
2) Il mio amico mi ha detto una cavolata...
Io uso solo Conio, non Hype, mi pare strano però che lo stesso wallet funzioni diversamente A questo punto vi domando il wallet che deve ricevere i bitcoin pur non essendo gestito da Conio può pagare una fee per accelerare la ricezione  Sì, se supporta questo metodo: Attraverso il meccanismo “Children pay for parents” (CPFP) vengono usati gli unspent del destinatario della transazione.
Gli UTXOs (unspent transaction outputs) generati dalla transazione in ingresso sono spendibili dal destinatario in quanto proprietario della chiave privata associata all’indirizzo su cui i Bitcoin devono essere depositati. Utilizzando la sua chiave pubblica, firmando la transazione con la chiave privata, infatti il destinatario dimostra di avere la titolarità dell’indirizzo di destinazione e dei relativi Bitcoin in arrivo.
Viene creata una nuova transazione che spende gli UTXOs generati dalla transazione in ingresso. Questa nuova transazione viene inviata ad un indirizzo controllato dal destinatario della prima transizione e prevede Mining Fee superiori alla prima.
Le nuove fee devono essere di un ammontare sufficiente ad incentivare i Miner ad includere entrambe le transazioni nel blocco.
Per ottenere le fee della seconda transazione infatti i Miner devono per forza includere nel blocco anche la prima transazione, altrimenti la seconda non risulterebbe valida.
ma io proverei a rifare la tx da Conio. |
|
|
|
non ho intenzione di fare altri acquisti per il momento anche perché non capisco come gestisce CONIO queste cose. Mi dispiace che non dia la possibilità di gestire i costi di trasferimento.
Grazie per la tua disponibilità
Guarda che nel wallet conio, quando invii una transazione, ti esce una schermata con 3 opzioni per quanto riguarda le fee, sta a te scegliere; inoltre se clicchi anche adesso sulla transazione già inviata e non ancora confermata puoi reinviarla con fee maggiorate, se proprio hai fretta e ti accorgi di aver sbagliato le fee. E' tutto spiegato qui molto chiaramente: https://support.conio.com/hc/it/articles/360008901213-Come-scegliere-o-cambiare-il-tempo-di-invio-o-di-ricezione-di-Bitcoin-Conio utilizza il meccanismo di RBF - Replace By Fee per accelerare le transazioni in uscita e il meccanismo di CPFP - Child Pays for Parents per accelerare quelle in ricezione. |
|
|
|
Stavo proprio per condividerlo, mi è arrivato tramite mail, vedo che hanno un po spiegato alla buona buona il fattore seed a 12 frasi Sarà veramente interessante il primo servizio che, oltre a consentirti di acquistare e vendere bitcoin con 2 click, faccia da sorta di sostituto d'imposta, cioè calcoli l'eventuale plusvalenza e ci pensi lui a sistemare l'aspetto fiscale (come avviene quando compri un'azione in banca). |
|
|
|
This is a more update article: https://www.ams.org/journals/mcom/2013-82-282/S0025-5718-2012-02641-X/S0025-5718-2012-02641-X.pdfA natural choice for the wild set is the set of equivalence classes coming from elements of the form hg^x with −N/2 < x ≤ N/2. Note that the size of the wild set now depends on the discrete logarithm problem: if h = g^0= 1 then the wild set has 1 + N/2 elements while if h = g^N/2 then the wild set has N elements. Even more confusingly, sampling from the wild set by uniformly choosing x does not, in general, lead to uniform sampling from the wild set. This is because the equivalence class {hg^x, (hg^x)−1} can arise in either one or two ways, depending on h. To analyse the algorithm it is necessary to use a non-uniform version of the birthday paradox (see, for example, Galbraith and Holmes [223]).The main result of [228] is an algorithm that solves the DLP in heuristic average-case expected (1.36 + o(1))√N group operations.
The number of bad collision is also link to the kangaroo density.
A note: probably half of your tames start from a even position (+24G, +1466G,... ) and the other half from a odd position (37G, 54365G, ....), and if you use the jumps: 1G, 2G, 4G, 8G,16G,... they are (except one) all even, then you have actually 2 groups that move in distinct areas. The same for the wild kangaroos. It is like you worked in 2 subintervals, not good for the collision probability. At least you should concentrate all the wild kangaroos in a unique subinterval (all even or odd). see this: Four Kangaroo Method. We can make a further improvement. The starting points of W1 and W2,
namely x and −x, are integers of the same parity. Hence, to obtain wild-wild collisions more quickly one
should take walks whose jumps are all even length. However, now there is the possibility that the wild walks
will never collide with the tame walk. The solution is to have two tame kangaroos, T1 and T2, starting on
adjacent integers (one even and one odd). There is no possibility of a useless tame-tame collision, but there
is a chance of tame-wild collisions, as desired (though with only one of the tame kangaroos).
...
We now estimate the complexity of the method.
...
Hence, using 4 kangaroos gives an algorithm for the DLP in an interval whose heuristic average case
expected running time is (1.714 + o(1)).sqrt(N) group operations.
|
|
|
|
Yes, i think this might be due to the average jump size which is too large for wild.
I will try other things and what you suggest.
Remember this too: To guard against bad steps of type 1 van Oorschot and Wiener [22] set a maximum number of steps in
a walk. They choose this maximum to be 20/θ steps and show that the proportion of bad
points of type 1 is at most 5 × 10^−8
...
Steven D. Galbraith and Raminder S. Ruprai:
We terminated walks which ran for 5/θ steps without arriving at a distinguished point (the usual recommendation is 20/θ steps; see [22]). This will give
us a slightly worse running time than optimal.
https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch14.pdfExercise 14.5.12.
The distance between −a and a is even, so a natural trick is to use jumps of even length. Since we don’t know whether a is even or odd, if this is done we don’t know whether to start the tame kangaroo at g^u or g^u+1. However, one can consider a variant of the algorithm with two wild kangaroos (one starting from h and one from h−1) and two tame kangaroos (one starting from g^u and one from g^u+1) and with jumps of even length.
This is called the four-kangaroo algorithm.
Explain why the correct choice for the mean step size is m = 0.375√2w and why the heuristic average-case expected number of group operations is approximately 1.714√w. Galbraith, Pollard and Ruprai [226] have combined the idea of Exercise 14.5.12 and the Gaudry-Schost algorithm (see Section 14.7) to obtain an algorithm for the discrete logarithm problem in an interval of length w that performs (1.660 + o(1))√w group operations.
Galbraith, Ruprai and Pollard [226] showed that one can improve the kangaroo method by exploiting inversion in the group. This research actually grew out of writing this chapter. Sometimes it pays to work slowly.
|
|
|
|
Good news !
By changing the spreading of wild kangaroo to -N/8 N/8 the it seems to improve things. (using the Steven D. Galbraith?and Raminder S. method).
I got an average of 2^20.997 ~ 2.sqrt(n) on 1000 trials.
Great!! Now under 2.sqrt(n)! I would be nice too a comparison with the classic approach (no equivalence classes) with these modifications: T' = [−2N/3, 2N/3 - (m/theta)] W' = [k − N, k − N/3 - m/theta] ∪ [k + N/3, k + N - m/theta] To recap: the standard 1.4 version takes 2.21.sqrt(n) and the new 'equivalence classes/symmetry' based version takes 2.sqrt(n), -15% ! There is room for improvement! |
|
|
|
I think you are missing the point I am making.
You will find a collision if the solution is in one of the additional ranges opened up by the endomorphism.
First what is "our problem"? Finding a that some point Q = kP has a discrete log with respect to some point P in a specific compact range of k -- [0, 2^80]. But why? Instead you can solve a related problem: Find k for Q = kP where k's value is [+/-]1*[0, 2^78]*lambda^[0,2] in less time, even though that 'sparse' range has 1.5x the possible values.
Thanks. I admittedly didn't understand your previous post. I think also if the interest is just in DL solving bragging rights or just the intellectual challenge in exploiting all the struture, the endomorphism is also interesting-- for that there isn't a particular problem structure so why not use the one that results in the fastest solver.  In the prime order group essentially all k values are equivalent, which is why you're able to shift the search around to look for that range wherever you want it in the 2^256 interval. I'm trying to resolve the classic discrete logarithm problem via a 3-dimensional discrete logarithm problem ( https://www.math.auckland.ac.nz/~sgal018/RamCiren.pdf) using endomorphism, probably not a good idea. If you resolve Q=a*P + b*P' + c*P'' with P'=lambda*P, P'' = lambda^2*P, then you have that Q = k*P, where k=a + b*lambda + c*lambda^2 |
|
|
|
still have lots of collision in same herd (using -d 0, it disable the distinguished point, so all collision and cycle are detected). The size of this table seems to no impact the bad collision number. I will read the ref[8] asap.
https://www.math.auckland.ac.nz/~sgal018/RamCiren.pdfHi, for your tuning's problems you can apply the following considerations to the classic version. This paper doesn't deal with equivalence classes. “type 1” bad points: it could happen that some processor never finds a distinguished point
--> To guard against bad steps of type 1 van Oorschot and Wiener [22] set a maximum number of steps in
a walk. They choose this maximum to be 20/θ steps and show that the proportion of bad
points of type 1 is at most 5 × 10^−8. If a processor takes this many steps without hitting a distinguished point then it restarts on a new random starting point.
“type 2” bad points: it seems to be impossible to design pseudorandom walks which cover T or W uniformly but which do not sometimes overstep the boundaries. Steps outside the regions of interest cannot be included in our probabilistic analysis and so such steps are “wasted”. We call these “type 2” bad points.
We now give the main result of the paper, which is a version of the Gaudry-Schost algorithm which has a
faster running time. The key observation is that the running time of the Gaudry-Schost algorithm depends
on the size of the overlap between the tame and wild sets. If it is possible to make the size of this overlap
constant for all possible Q then the expected running time will be constant for all problem instances. We
achieve this by choosing walks which only cover certain subsets of T and W.
Precisely, instead of using the sets T and W of the previous section
T = [-N,N]
W = [k-N,k+N]
we use
T0 = [−2N/3, 2N/3] ⊆ T
W0 = [k − N, k − N/3] ∪ [k + N/3, k + N] ⊆ W (see Figure 1).
Running time: 2.05*sqrt(N)
Considering the DP too: In the 1-dimensional case we use a standard pseudorandom walk as used by Pollard [15] and van Oorschot
and Wiener [22] i.e., small positive jumps in the exponent. The average distance in the exponent traveled
by a walk is m/θ, where m is the mean step size and θ is the probability that a point is distinguished. For
example, one may have m = c1√N and θ = c2/√N for some constants 0 < c1 < 1 and 1 < c2. Therefore, to
reduce the number of bad steps of type 2 we do not start walks within this distance of the right hand end
of the interval. In other words,
we do not start walks in the following subset of T0
[2N/3 - (m/theta), 2N/3]
we do not start walks in the following subset of W0
[k − N/3 - m/theta, k − N/3] ⊆ W and [k + N -m/theta, k + N] ⊆ W
Let m be the mean step size and max the maximum step size.
The probability that a walk has bad points of type 2 is at most
p =(20 max −m) / (2N*θ/3 − m)
For the values m = c1√N1, max = 2m and θ = c2/√N1 the value of p in equation is 39c1/(2c2/3 −
c1) which can be made arbitrarily small by taking c2 sufficiently large (i.e., by storing sufficiently many
distinguished points). Hence, even making the over-cautious assumption that all points are wasted if a walk
contains some bad points of type 2, the expected number of walks in the improved Gaudry-Schost algorithm
can be made arbitrarily close to the desired value when N is large. In practice it is reasonable to store at
least 2^30 distinguished points, which is quite sufficient to minimise the number of bad points of type 2.
We stress that the choices of m, max and θ are not completely arbitrary. Indeed, if one wants to bound
the number of bad points of type 2 as a certain proportion of the total number of steps (e.g., 1%) then for
a specific N there may be limits to how large θ and max can be. For smaller N we cannot have too small a
probability of an element being distinguished or too large a mean step size.
|
|
|
|
|
Show Posts
