If we attack #64, we will try all priv key one by one, compute the HASH160 until we get a match.
With few mods, the vanitySearch engine can do that. Kangaroo is not usefull here.
I suppose that computing HASH160 is more expensive than computing P+Q, then searching for #120 (2^61 steps) should be faster than computing #63 (2^61 steps on average) |
|
|
|
You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1])
Yes you're right. I ve forgotten that the start range was shifted to zero. shame on me  It will help to solve #120.  Instead of 2^61 steps, you need to compute (2^60 - 2^58.36) steps for tame + 2^60 for wild. If you spread the old DPs like I have suggested you in a previous post. It would be convenient to start with only wild (for the first 2^58.36 steps) and then continue with wild and tame, but with many machines it should be not simple to do this. You can save in this way about 15.8% of the work. An other way it could be: you know that you have already DPs in [1,2^114-1], then you generate tame only in the [2^114, 2^119-1] space --> you have enough DP's (2^33.36) already in the first 1/32. In the first case you should use 300GB * 2^2.5 = 1700 GB, in the second case I guess you need more RAM and more time. |
|
|
|
i think all DPs from previous work will be in the left 1/32 part of interval(in the begining). If you just multiply DPs by 32 then they will be just points not DPs becouse they will not have leading zeros. If i wrong can you explaine in very small range how transform DP by 32 times and do not loose leading zeros? Thanks. No, you don't transform the old DPs, you change only their private keys (changing the generator G). The same for the old jumps. The only point you change is P, the public key for which you are looking the private key. Instead of multiplying the old points by 32 you divide (= multiply by inv(32)) the new public point P -> P'=inv(32)*P. If P lies in the [1, 2^119 - 1] interval, then P' lies in the [1/32, ...., 31/32, 1, 33/32, ....., 2, ......3, .......4, ................., 2^114 -1/32] interval. Note that the private keys of the old DPs are 'integer'. In this way you spread the old DPs uniformly in a set x32 bigger. This interval contains all the previous points [1,2,3,..., 2^114-1], but not at the beginning! You can change now the private keys changing the generator, G -> G' = inv(32)*G: [1, .........,31, 32, 33, .........2*32,..........3*32, .............., 4*32,.................32*2^114 - 1] the private keys of the old DPs have become all multiplies of 32. If for example a DP has private key = 78543 respect of G, it has private key = 32*78543 respect of G', the point remains the same (same x-coordinate), you have changed only the point G. The private key of P' respect of G' is the same private key of P respect of G. ------------------------------------------------------------------------------------------------------------------ Example: first interval = [1,2,3,4,5,6,7] (3 bit) DPs = 2*G, 5*G
second interval = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,....,27,28,29,30,31] (5 bit) you want to find P = 11*G, you know only that the P lies in this interval instead of searching P in the second interval [1*G, 2*G, ...., 31*G] you search P'=inv(4)*P (a different point) in a third interval [1*G', 2*G', ......, 31*G'] (that contains the first interval but not at the beginning + P') The old DPs are now: 8*G' and 20*G' (same points, different private keys). All the points of the first interval are now in the third one too. The private key of P' = 11, in fact 11*G' = 11*inv(4)*G --> P = 4*P' = 4*11*inv(4)*G = 11*G |
|
|
|
Unfortunately I don't see how to reuse the work file on a different range.
This work file is for [2^114,2^115-1]
If you translate the kangaroos, the paths will differ so you have to redo all the job.
You can (see here -> https://bitcointalk.org/index.php?topic=5244940.msg54546770#msg54546770, it is enough to map the new task [1, 2^119 - 1] to the previous one [1, 2^114 - 1]) but it's not worth it. You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs are in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P is in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1]) In theory, to have 50% to get a collision in the #120 search, if you reuse the 300GB of DPs you need to do other 2^61.70 steps (only wild). If you restart instead from scratch, you need to do about 2^61 steps. |
|
|
|
To recap (and to return in topic):
#115 -> 114 bit
steps needed to have 50% chance of a collision: about (114/2)+1 = 58 bit -> 2^58
DP = 25
steps performed: 2**25 * 2**33.14 = 2**58.14, then you are close to the result?
I expect a result at any time. You had to add ~ 5% tolerance limit due to inconsistency in ~ 00.05% files, so in my case from 2 ^ 33.167 gives 52%. I have already crossed 2 ^ 33.18 just so it is exactly as you wrote :-) Any news? It may take more time finding #115 than finding #120 ... |
|
|
|
As far as I understand the main principle of Bitcoin addresses is that it has ALL POSSIBLE combinations.
This is true, a bitcoin address is a simple number (160-bit), the 'problem' arises with the Base58 encoding format. I've read about btc addresses, how it's generated, how hashing works yet I haven't found the answer to the above question
Read this page too: https://www.oreilly.com/library/view/mastering-bitcoin-2nd/9781491954379/ch04.htmlTo add extra security against typos or transcription errors, Base58Check is a Base58 encoding format, frequently used in bitcoin, which has a built-in error-checking code. The checksum is an additional four bytes added to the end of the data that is being encoded. The checksum is derived from the hash of the encoded data and can therefore be used to detect and prevent transcription and typing errors.
...we compute the “double-SHA” checksum, meaning we apply the SHA256 hash-algorithm twice on the previous result (prefix and data):
checksum = SHA256(SHA256(prefix+data))
From the resulting 32-byte hash (hash-of-a-hash), we take only the first four bytes. These four bytes serve as the error-checking code, or checksum. The checksum is concatenated (appended) to the end.
 |
|
|
|
l'informazione in sé non degrada, ma il supporto fisico su cui è memorizzata sì. Può esistere informazione in astratto senza un supporto fisico? Sia che si tratti di un cervello umano o di una memoria magnetica piuttosto che ottica, anche nell'ultimo caso la capacità di mantenere inalterata l'informazione permane per un tempo lungo, ma non infinito.
In sè non degrada, appunto. Perchè si mantenga nel tempo è necessario che l'informazione sia trasmessa/riscritta più volte nel tempo, è chiaro che serve un supporto fisico, che un individuo deve trovare il modo di trasmetterla ad un altro, ma la conoscenza di per sè tende ad accumularsi. E quella è una ricchezza veramente inconfiscabile. Ce ne è talmente tanta che oggi il problema principale riguardo alla conoscenza/informazione in senso lato è che il singolo individuo non ha il tempo materiale per poter conoscere e studiare il prodotto di secoli di accumulo della conoscenza umana, anche se ci fermassimo per qualche anno nella produzione/scoperta di nuova 'informazione'. L'informazione importante inoltre non solo non tende a deteriorarsi, ma migliora con il tempo: pensa ad esempio alla legge di gravitazione universale, la sua formulazione ha 300 anni e continua a produrre 'ricchezza' ad oggi, sia poichè su essa si è basata la produzione di molta altra conoscenza, sia perchè la stessa legge è stata capita meglio ed è stata integrata nel tempo in un quadro concettuale diverso da quello originario. A me sembra che nel caso della conoscenza la freccia del tempo sia invertita rispetto a quello che succede con energia e materia, dove "tempo trascorso" significa automaticamente "perdita di qualità"; per la conoscenza di solito "maggiore è il tempo trascorso", migliore diventa la qualità e la comprensione della stessa informazione. |
|
|
|
Dire che il vero indicatore di ricchezza possa essere l'energia è qualcosa che può valere già oggi, mentre sostenere questa cosa per l'informazione è più difficile da argomentare.
L'energia già oggi è ricchezza: la paghi per usarla, per stockarla, per trasferirla..... e se ognuno di noi ne avesse a disposizione quantità "illimitate" probabilmente la useremmo per fare tante altre cose che oggi non facciamo oppure facciamo in modo molto più faticoso.
Con l'informazione invece oggi non riesci a sostituire altre cose che fai usando altri strumenti, è un mezzo che può consentirti di ottimizzare processi, di conoscere nuove cose, di.... chissà quant'altro, ma non diventa ricchezza di per sé (se non per alcuni pochi che la usano per vendere ad altri cose sulla base di informazione raccolta, appunto).
Anche l'energia da sola è un mezzo, se non sai che siedi sopra un giacimento di petrolio o non sai come fare a estrarlo il petrolio/energia è una ricchezza solo potenziale. L'energia elettrica è ricchezza perchè abbiamo inventato le lavatrici, i televisori, i computer, le macchine, ..., altrimenti che valore avrebbe l'energia elettrica di per sè? |
|
|
|
l'articolo secondo me offre un spunto estremamente interessante: anche se usa ripetutamente il termine "informazione", in realtà quello di cui sta discutendo è il concetto più generale di entropia. L'energia da sola non basta a caratterizzare i processi fisici, né tanto meno a descrivere le attività umane e a sviluppare modelli economici.
...
E questo non può che farmi pensare all'intuizione straordinaria che l'economista Nicholas Georgescu-Roegen
... Secondo il principio definito da Georgescu-Roegen come "Quarto principio della termodinamica", la materia che si ottiene come output da un processo potrà quindi essere riutilizzata nel successivo ciclo economico solo in misura molto minore, e con un sempre crescente dispendio di energia. Sia la materia che l'energia, quindi, sono soggette nel corso del processo economico ad un aumento complessivo di entropia che lo rende irreversibile. Questo con buona pace di chi cerca di aggirare il problema della crescita infinita, su cui si basano gli insostenibili modelli economici attualmente in essere, coltivando l'illusione di un'economia circolare a impatto zero, di cui si sente parlare tanto ultimamente ma che appare in quest'ottica come un falso mito, di fatto irrealizzabile.
Se ci pensi energia e materia obbediscono al principio di entropia, mentre l'informazione no. Per esempio in via teorica la conoscenza e l'informazione sul mondo si può accumulare, si può immagazzinare in modo quasi gratuito e illimitato e si può riutilizzare (un'informazione come una legge fisica non si degrada una volta utilizzata, anzi più circola e si condivide maggiore è la possibilità che essa generi altra informazione/conoscenza). E tornando in topic, bitcoin alla fine è un'informazione ben custodita e non falsificabile. |
|
|
|
Chiaro, allo stato dell'arte è come dici tu Paolo.
Io parlo per assurdo e in teoria.
Considero gli investimenti attuali una forma degradata di energia. Ma non ci sono forme pure di energia.
Una piccola digressione: tu insisti tanto sul tema dell'energia, ma la vera ricchezza non potrebbe consistere piuttosto nell'informazione invece che nell'energia? L'informazione (o meglio la sua mancanza) ha fatto sì che trascorressimo secoli su questo pianeta senza utilizzare gran parte dell'energia a disposizione; e chissà quanta energia abbiamo anche adesso tra le mani che semplicemente non siamo in grado di sfruttare perchè non sappiamo come fare. Linko un articolo di Carlo Rovelli (fisico): https://st.ilsole24ore.com/art/cultura/2014-04-01/ogni-cosa-e-informata-085339.shtml?uuid=ABRyuN7&refresh_ce=1 |
|
|
|
For a change, this is current progress  To recap (and to return in topic): #115 -> 114 bit steps needed to have 50% chance of a collision: about (114/2)+1 = 58 bit -> 2^58 DP = 25 steps performed: 2**25 * 2**33.14 = 2**58.14, then you are close to the result? |
|
|
|
interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?
You can't. Let P be a public key with unknown private key k (that means P = k*G) By definition, you can get a public key Q such that 10*Q = P in this way: Q = inv(10)*P = inv(10)*k*G that's all you can have (if you don't know k, you don't know inv(10)*k neither) But it’s really possible to divide any public key into 10 without knowing the private one. But to divide by 3, 6, 7, 9, 14 .... is already more difficult. It is the same thing. Inv(10) or inv(3), where is the difference? |
|
|
|
interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?
You can't. Let P be a public key with unknown private key k (that means P = k*G) By definition, you can get a public key Q such that 10*Q = P in this way: Q = inv(10)*P = inv(10)*k*G that's all you can have (if you don't know k, you don't know inv(10)*k neither) |
|
|
|
Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001 for 0.1 a = 1/3 b = a/2 result = 0.1 Real privat key? 0.1 = 10^-1 mod n inverse of a = a^(n-1) mod n n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
b=pow(10,n-1,n)
b
81054462466121336796499689506081535496986294995352433067823614199062713046036 <-- inverse of 10 mod n
hex(b)
0xb33333333333333333333333333333324f7a676e477fa35d0646756291bf9414 <-- inverse of 10 mod n
Verify: |
|
|
|
-snip-
With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.
you can use what ever you want amount of DPs, but less amount of DP then more GS you need. here is 16k DPs The goal is to use less RAM than classic BSGS. Let's say we want to find a key in 120 bit range. With the classic BSGS you need 2^60 BS (huge amount of RAM) and 2^60 GS. With BSGS + (DP = 10): 2^50 BABYSTEPS + on average 2^59 GIANTSTEPS * 2^10 = 2^69 steps. Then less RAM but more steps. With BSGS + (DP = 10): if you want to use more BABYSTEPS: 2^80 BABYSTEPS + on average 2^29 GIANTSTEPS * 2^10 = 2^80 steps + 2^39 GIANTSTEPS. The advantage is that you can precompute this 2^80 BABYSTEPS, but you don't have space to store them. |
|
|
|
-snip-
How do you use DPs with BSGS?
First fill baby steps, but not each point put to table but only DP and distance when you reach last DP you will get final distance. Doubled distance it will be Giant steps. Before GS you need to find 2 DP (+/-) for known pubkey, compare with hashtable this DP if not success sub GS from pubkey and repeat.. But in this way you find the private key at 100%? EDIT: In ex. i generate random pubkey b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82bbfbb9d25748a27 92fcac6ec1b892db592556534f1b6155a37804522d1ff2194
private key is 0xA0300879 in range 2^32
I set DPsize=8, and maxDP in table around 262144
when i fill baby steps i get 262346 DPs
It is very small hashtable ofcourse it is just for test..
In this case i should make 20 giant steps to find key.
Total add point op was 6981.
With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less. |
|
|
|
For this Kangaroo ECDLP solver, if RAM was not an issue, what is the optimal DP setting?
Would lower always be better? Small DP means you have to find more DPs.
Expected group operations remains the same no matter how you adjust the DP, right?
So what is the optimal DP setting if RAM is not an issue?
If the RAM was not a issue, it would be better to use a low DP, because high DP means long time between a collision and its detection, especially if you use many kangaroos in parallel. But not too low, with DP = 0 ** you would have the minimum number of steps, but the generation of the the start points is much slower than the generation of the other points of the path. Let's say that the cost of generating a start point is about x50 the cost of generating the next point with a single jump, with an average length of 10k points (about 2^13) you should have a good value. Then DP = 12 / 13 / 14, not more. ** A note: if you use equivalence classes with DP = 0, you need only sqrt(2).sqrt(N) steps, this is the expected group operations. |
|
|
|
Anybody think about using bsgs algo but with DP?
bsgs fast but have a problem due to memory usage. maybe using DP can solve this issues?
Extremely fast, it gets through a FFFFFFFFFFF range in 2 seconds total. Including step build time. Only uses 600Mb. I thought about how to implement it differently. Use DP or build the table on harddrive and when giants start stepping compare back to the saved table. After so long, save the giant file with previously created file, and continue with giant step. How do you use DPs with BSGS? |
|
|
|
part 3 of private_to_address.py:
-snip-
Your script works fine with random numbers, but not with all numbers. You should add some check and do not perform inverse for zero - it immediately lead to mistake. Try for example to calculate address for private key 1,2,3,4,... or 13, or 2^109 or 2^110 or for number 1298074214633706907135958430033862 - it will not work for these numbers. There a lot of other numbers the script will not work. leads to this error: invb = inv(b5*b6,p)
ZeroDivisionError: invert() no inverse exists I know, that function is not perfect. I have just fixed some (not all) errors. If you need a correct function replace mul2G with mulG: def mulG(d): # d -> d*G
dax, day = 0, 0
r = d%16
if (r > 0):
rr = 2*r-1
#dax, day = ax, ay #solo se d e' dispari
dax, day = G[rr-1], G[rr]
q = d>>4
i = 30 #2*(16-1)
while q > 0:
#ax, ay = double(ax,ay)
#ax, ay = G[i], G[i+1]
r = q%16
rr = 2*r+i-1
if (r > dax): #puo' succedere solo se dax = 0 e r > 0 cioe' la prima volta
dax, day = G[rr-1], G[rr] #solo se d e' pari
elif (r):
dax, day = add(G[rr-1], G[rr], dax, day)
q = q>>4
i = i + 30
return dax, day
|
|
|
|
The ComputePublicKey() in kangaroo use 32 blocks of 256 precomputed points and zero are checked so it performs:
31 adds max for a full privkey (nothing when a zero byte is present) and a modular inversion.
There is also a ComputePublicKeys() which group modular inversions.
That means you need only 16 blocks of 255 (why 256?) precomputed points for a 128-bit privkey, only 15 adds, not too much respect to a single addition. Split a 128-bit in 16 pieces (each piece has 128/16=8 bit -> 255 elements) and compute only 16-1 = 15 group additions for each key. Just for example, if you have a 128 bit key: key = 10101010 10100000 11111111 01000010 ... 11101010 split in 16 pieces of 128/16=8 bits: (10101010)*2^120 + (10100000)*2^112 + (11111111)*2^104 + (01000010)*2^96 + .... + (11101010)2^0 00000001 00000010 00000011 ... 11111111 --> 255 possibilities
2^0 2*2^0 3*2^0 ... 255*2^0 --> one of these is (11101010)*2^0
... ... ... ... ...
2^(12*8) 2*2^(12*8) 3*2^(12*8) ... 255*2^(12*8) --> one of these is (01000010)*2^96
2^(13*8) 2*2^(13*8) 3*2^(13*8) ... 255*2^(13*8) --> one of these is (11111111)*2^104
2^(14*8) 2*2^(14*8) 3*2^(14*8) ... 255*2^(14*8) --> one of these is (10100000)*2^112
2^(15*8) 2*2^(15*8) 3*2^(15*8) ... 255*2^(15*8) --> one of these is (10101010)*2^120
|
|
|
|
|
Show Posts
