...
La distruzione di ricchezza si ha quando il surplus di consumo (rispetto al reddito) è intergenerazionale: come nel ns Paese dove stiamo distruggendo la ricchezza messa da parte dalle generazioni precedenti.
E' vero che "distruggere" è una parola non corretta: la ricchezza non si distrugge, si trasferisce: nel caso italiano si accentra nelle mani di pochi, sempre più stranieri.
Credo anche che il “lavoratore puro” non esista più da almeno un secolo: i proletari esistevano forse nell'800. Già negli anni 50-60 nonostante gli italiani fossero mediamente molto più poveri di quelli di ora la capacità di risparmiare esisteva eccome.
So di fare un discorso antipatico e poco popolare, ma il crollo della capacità di risparmio nell'Italia attuale è figlio di scelte ben precise e non di una oggettiva impossibilità a mettere da parte a causa dei bassi redditi.
E qui si passa dalla sfera economica a quella sociale: il messaggio, più o meno subliminale, che trasuda da ogni poro della nostra società è quello di incentivare il più possibile la spesa in ognuno di noi.
Tempo fa ero con amici ad una cena. Gente che non vedevo da un pò. Entriamo nell'argomento figli. Una ragazza, single, sui 30 anni se ne esce con queste parole: "A me i figli non interessano, nella mia vita non ho intenzione di farli". Silenzio, sguardi gelidi. La ragazza ha appena toccato un tasto proibito. Qualcosa che nella società di oggi non si può dire e nemmeno pensare. Fossimo in 1984 sarebbe uno psicoreato
Però è un pensiero legittimo o vogliamo fare come in Cina dove lo Stato decide il numero di figli?
....
Come al solito fai considerazioni molto molto interessanti. Il mio punto però era un altro: negli anni 50-60 non è che gli italiani fossero intrinsecamente 'migliori' degli italiani odierni, semplicemente avevano meno di tutto (soldi, tempo, ricchezza in senso lato) ma erano ricchi di un'altra cosa: di 'futuro'. La loro mentalità volta al risparmio (che io non condanno in principio) era più che altro dettata da 2 fattori: 1) dalla necessità (poco da spendere, non potevi viaggiare, comprare libri, smartphone, ... ) 2) da una situazione in cui non spendere era un EVIDENTE vantaggio, visto che il mondo attorno migliorava a vista d'occhio e il futuro appariva senz'altro migliore del presente: risparmiare vuol dire guardare al futuro, e oggi in Italia non hai l'impressione che il futuro sarà migliore, anzi (non cerco scuse, mi limito a descrivere quello che vedo). Se vuoi un confronto: i cinesi negli ultimi decenni per alcuni aspetti si sono trovati in una situazione simile a quella dei nostri nonni: forte crescita economica (facile se parti da molto in basso) e ottime prospettive di crescita, quindi tendenza al risparmio; non è un caso che da quelle parti la capacità di sacrificio dell'oggi per il domani sia molto alta (pensa solo a quanto studia in media un ragazzo cinese contro un ragazzo italiano oggi) Altro esempio: chi oggi compra un bitcoin, perchè è un risparmiatore? Perchè ha una mentalità migliore o perchè ha visto un'opportunità (rara di questi tempi) di miglioramento per il futuro? La mia tesi è che il concentrarsi sul presente (godere e consumare) anzichè sul futuro (programmazione e risparmio) nasca semplicemente dal fatto che oggi in Italia c'è abbondanza di materia prima da spendere nel presente (leggi denaro e oggetti) da una parte e mancanza di futuro, inteso come prospettiva di miglioramento, dall'altra (vedi i primi 28 secondi di https://www.youtube.com/watch?v=4N3uZGF_mCw ) Avere l'impressione di aver già raggiunto tutto quello che c'era da raggiungere e che non ci sia più nulla da fare facilmente ti porta a concentrarti sul presente, anzichè sul futuro. E direi che sono almeno 30-40 anni che l'Italia non va avanti sotto molti punti di vista (a partire dall'economia, ma non solo). |
|
|
|
Il problema è che le persone non capiscono che c'è una "spesa sana" e una "spesa malata". Quando si parla di consumismo, ci si riferisce a quest'ultima.
....
Nessuno che voglia spendere per creare qualcosa, per lasciare qualcosa. Un'impresa, un sogno nel cassetto grande o piccolo, un' idea, un progetto.
Io ho un sogno nella vita: arrivare in punto di morte sapendo che ho creato più ricchezza di quanta ne ho consumata.
Che passo un testimone di maggior valore a quelli che verranno dopo.
Non importa chi sono quelli che vengono dopo: i figli, la moglie, il cane, il WWF, la ganza moldava.
L'importante è CREARE qualcosa, è GENERARE VALORE CHE DURI, altrimenti cosa si vive a fare? Che gusto c'è a passare un'intera esistenza solo a nutrirsi, dormire, consumare, produrre rifiuti? Distruggendo ricchezza creata da quelli prima?
...
Altrimenti una società che pensa solo al godimento presente è destinata alla rovina. Che poi la cosa che mi fa incazzare di più è che il godimento deve pure essere senza fatica.
La funzione del consumatore 'puro' non è distruggere ricchezza, è consumare ricchezza più velocemente fornendo così un senso alla produzione e al lavoro di altri. Pensate a un consumatore come a un bambino: per definizione un bambino consuma solo, non è in grado di produrre: la presenza di bambini in una casa è un grande incentivo affinchè i genitori producano/lavorino di più, fornisce un senso al loro lavoro. Il consumatore 'puro' è l'altra faccia della medaglia di chi pensa solo a lavorare (lavoratore 'puro'). Io, che per natura spendo pochissimo, sono affascinato da alcuni personaggi su Youtube che passano il loro tempo per esempio a comprare e provare pc o altri oggetti: anche nel loro caso è consumismo? Entrambe le figure (consumatore e lavoratore 'puro') sono forzature, ma secondo me se nel passato c'erano più lavoratori 'puri', oggi per forza di cosa ci si sta muovendo nell'altra direzione. I miei nonni hanno lavorato sempre finchè hanno potuto, una volta c'erano tantissimi lavoratori a tempo pieno (per necessità, anche se dalla produttività bassa, magari uno faceva il contadino e veniva aiutato dalla moglie e anche dai figli, e passavano un'intera esistenza solo a coltivare, nutrirsi, dormire, consumare quello che producevano). Nella società attuale (almeno in Occidente) la produzione invece supera ormai abbondantemente le necessità di consumo delle persone. E' anche per questo che si stanno moltiplicando le settimane corte al lavoro e che molti giovani danno sempre più peso all'orario di lavoro e agli spostamenti: il tempo delle persone ha un valore. Il problema è che non siamo abituati a gestire questo valore, il tempo libero (nè siamo abituati a gestire denaro in abbondanza rispetto alle pure necessità di base): è un fatto relativamente recente avere tempo libero a disposizione (una volta era una prerogativa di nicchia, non di massa). Non sto difendendo il consumismo sfrenato, dico solo che: 1) chi pone l'accento 'sul godere la vita' ha almeno intuito che c'era un problema nella vita dei nostri nonni (solo lavoro e poco o nulla piacere) 2) se da una parte certi consumatori non si pongono affatto il problema di creare qualcosa che duri nel tempo, dall'altra parte anche molte attività cosiddette 'produttive' producono ben poco di significativo (si potrebbe dire che producano direttamente rifiuti). 3) molti lavori non ti danno la sensazione di produrre qualcosa di valore, che duri nel tempo (esempio: il corriere Amazon, ma ce ne sono tanti altri), dove impari a produrre qualcosa che duri nel tempo allora? Se molte persone passano 8 ore al giorno producendo cose effimere? E' molto difficile distinguere non solo tra spesa sana e spesa malata, tra tempo libero speso bene e speso male, ma anche tra produzione sana e produzione malata. Per esempio, molti accusano la rete Bitcoin di essere una produzione 'malata' (bruciare energia per produrre numeri). Il senso del mio intervento è: non mi stupisco che la società attuale attraversi un periodo difficile, non è questione che siamo uomini deboli mentre una volta c'erano uomini forti, semplicemente le sfide del nostro tempo sono altre (e il passato non ci ha consegnato molte indicazioni utili al riguardo). Un uomo forte di 200 anni fa trapiantato ai giorni nostri incontrerebbe le stesse nostre difficoltà (se non peggio). |
|
|
|
randbelow(n-1)+1
how to replace this line private_keys = list(map(secrets.randbelow,n)) Try this code: #!/usr/bin/env python3
# 2023/Jan/01, citb0in_multicore_secrets.py
import concurrent.futures
import os
import secrets
import secp256k1 as ice
# how many cores to use
num_cores = 10
#num_cores = os.cpu_count()
# Set the number of addresses to generate
num_addresses = 10000000
# Define a worker function that generates a batch of addresses and returns them
def worker(start, end, i):
# Generate a list of random private keys using "secrets" library
n = [0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141] * (end - start) #n
one = [1] * (end - start)
my_secure_rng = secrets.SystemRandom()
private_keys = list(map(my_secure_rng.randrange,one,n)) #from 1 to n-1
# Use secp256k1 to convert the private keys to addresses
addr_type = [2] * (end - start)
is_compressed = [True] * (end - start)
thread_addresses = list(map(ice.privatekey_to_address, addr_type, is_compressed, private_keys))
# Write the addresses in the thread file
f = open("addresses_1M_multicore_secrets" + str(i) + ".txt", "w")
list(map(lambda x:f.write(x+"\n"),thread_addresses))
#####or, if you want to store the private keys, along with the addresses###############
#list(map(lambda x,y: f.write(hex(x)[2:].rjust(64,'0') + ' -> ' + y + '\n'),private_keys,thread_addresses)
f.close()
return
# Use a ProcessPoolExecutor to generate the addresses in parallel
with concurrent.futures.ProcessPoolExecutor() as executor:
# Divide the addresses evenly among the available CPU cores
addresses_per_core = num_addresses // num_cores
# Submit a task for each batch of addresses to the executor
tasks = []
for i in range(num_cores):
start = i * addresses_per_core
end = (i+1) * addresses_per_core
tasks.append(executor.submit(worker, start, end, i))
|
|
|
|
With last code, you should save at least 2.5 - 3s on your hardware, I guess from 25,8s to < 23s to compute 10 million keys. Did you try? I'm curious. Absolutely correct arulbero. Thanks for pointing out. I used 2**256 as a quick'n'dirty solution and forgot about the edge of the finite field 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Good catch.
To be more precise, randbelow(n-1)+1 otherwise with randbelow(n) could occur '0' (extremely unlikely). ...
==> I have generated 1,007,862 addresses (about 1 million keys) in about 15 seconds using one single core with your program.
==> I have generated exactly 1 millions addresses in 10 seconds using one single core with my program.
Conclusion:
The originally enormous speed advantage is therefore, according to these tests, not really to be found in the code difference but in the fact that randomly generated keys are simply more computationally intensive and cost more time than simple sequential key generation. So just as you originally said arulbero.
It always depends on the purpose of use, of course, but I have my doubts that the sequential generation of private keys is not the best way. I therefore think, also in terms of security for other applications, that random private keys are always preferable to sequential ones despite the fact they are more time-intensive.
If you try to substitute randbelow(n) with randbelow(10000000) (or another small number), you'll see how much time it requires to sum up many keys to get a high key. I think you may get almost 1 Million keys per sec. |
|
|
|
I have modified to create 10 million addresses to make the difference more clear. $ time python3 citb0in_multicore_secrets.py
real 0m38,349s
user 5m47,453s
sys 0m16,060s
$ time python3 citb0in_multicore_secrets_splitsave.py
real 0m25,835s
user 5m57,795s
sys 0m14,681s
10 million addresses generated in less than 26 seconds. Rate = 387.071 (Python). ==> this is a performance boost of additional + 32.7 % on my computer. Crazy!    thank you for pointing out @arulbero. Great! You don't use any specific function from numpy, then I suggest you to eliminate numpy besides you have to generate a random key k with k < n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 not k < 2**256 you can comment the check at this line: https://github.com/iceland2k14/secp256k1/blob/main/secp256k1.py#L290This is your code optimized: #!/usr/bin/env python3
# 2023/Jan/01, citb0in_multicore_secrets.py
import concurrent.futures
import os
import secrets
import secp256k1 as ice
# how many cores to use
num_cores = 10
#num_cores = os.cpu_count()
# Set the number of addresses to generate
num_addresses = 10000000
# Define a worker function that generates a batch of addresses and returns them
def worker(start, end, i):
addr_type = [2] * (end - start)
is_compressed = [True] * (end - start)
n = [0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141] * (end - start)
f = open("addresses_1M_multicore_secrets" + str(i) + ".txt", "w")
# Generate a list of random private keys using "secrets" library
private_keys = list(map(secrets.randbelow,n))
# Use secp256k1 to convert the private keys to addresses
thread_addresses = list(map(ice.privatekey_to_address, addr_type, is_compressed, private_keys))
# Write the addresses in the thread file
list(map(lambda x:f.write(x+"\n"),thread_addresses))
f.close()
return
# Use a ProcessPoolExecutor to generate the addresses in parallel
with concurrent.futures.ProcessPoolExecutor() as executor:
# Divide the addresses evenly among the available CPU cores
addresses_per_core = num_addresses // num_cores
# Submit a task for each batch of addresses to the executor
tasks = []
for i in range(num_cores):
start = i * addresses_per_core
end = (i+1) * addresses_per_core
tasks.append(executor.submit(worker, start, end, i))
|
|
|
|
To speed up slightly this code (with multi core), you can write on different files: [...]
np.savetxt('addresses_1M_multicore_secrets'+ str(i) +'.txt', thread_addresses, fmt='%s')
return
[...]
This will finish faster, yes. But it will create only one single output file which contains only 62,500 addresses. My example have all 1 million addresses listed. I'm kinda puzzled  what exactly you mean, can you explain, please? If num_cores = 10, this code saves 100k addresses x 10 files. It doesn't create only 1 file, but 1 file for each thread. On my computer works. |
|
|
|
here's the updated complete code variant with using multicore functionality and the secrets library for enhanded speed: #!/usr/bin/env python3
# 2023/Jan/01, citb0in_multicore_secrets.py
import concurrent.futures
import os
import numpy as np
import secrets
import secp256k1 as ice
# how many cores to use
#num_cores = 1
num_cores = os.cpu_count()
# Set the number of addresses to generate
num_addresses = 1000000
# Define a worker function that generates a batch of addresses and returns them
def worker(start, end):
# Generate a NumPy array of random private keys using "secrets" library
private_keys = np.array([secrets.randbelow(2**256) for _ in range(start, end)])
# Use secp256k1 to convert the private keys to addresses
thread_addresses = np.array([ice.privatekey_to_address(2, True, dec) for dec in private_keys])
return thread_addresses
# Use a ProcessPoolExecutor to generate the addresses in parallel
with concurrent.futures.ProcessPoolExecutor() as executor:
# Divide the addresses evenly among the available CPU cores
addresses_per_core = num_addresses // num_cores
# Submit a task for each batch of addresses to the executor
tasks = []
for i in range(num_cores):
start = i * addresses_per_core
end = (i+1) * addresses_per_core
tasks.append(executor.submit(worker, start, end))
# Wait for the tasks to complete and retrieve the results
addresses = []
for task in concurrent.futures.as_completed(tasks):
addresses.extend(task.result())
# Write the addresses to a file
np.savetxt('addresses_1M_multicore_secrets.txt', addresses, fmt='%s')
To speed up slightly this code (with multi core), you can write on different files: #!/usr/bin/env python3
# 2023/Jan/01, citb0in_multicore_secrets.py
import concurrent.futures
import os
import numpy as np
import secrets
import secp256k1 as ice
# how many cores to use
#num_cores = 1
num_cores = os.cpu_count()
# Set the number of addresses to generate
num_addresses = 1000000
# Define a worker function that generates a batch of addresses and returns them
def worker(start, end, i):
# Generate a NumPy array of random private keys using "secrets" library
private_keys = np.array([secrets.randbelow(2**256) for _ in range(start, end)])
# Use secp256k1 to convert the private keys to addresses
thread_addresses = np.array([ice.privatekey_to_address(2, True, dec) for dec in private_keys])
np.savetxt('addresses_1M_multicore_secrets'+ str(i) +'.txt', thread_addresses, fmt='%s')
return
# Use a ProcessPoolExecutor to generate the addresses in parallel
with concurrent.futures.ProcessPoolExecutor() as executor:
# Divide the addresses evenly among the available CPU cores
addresses_per_core = num_addresses // num_cores
# Submit a task for each batch of addresses to the executor
tasks = []
for i in range(num_cores):
start = i * addresses_per_core
end = (i+1) * addresses_per_core
tasks.append(executor.submit(worker, start, end, i))
Your code doesn't store private keys, are you sure you want to have only a list of addresses without their private keys? |
|
|
|
==> I have generated 1,007,862 addresses (about 1 million keys) in about 15 seconds using one single core with your program.
==> I have generated exactly 1 millions addresses in 10 seconds using one single core with my program.
Conclusion:
The originally enormous speed advantage is therefore, according to these tests, not really to be found in the code difference but in the fact that randomly generated keys are simply more computationally intensive and cost more time than simple sequential key generation. So just as you originally said arulbero.
You said : "compare apples with apples" but now you are comparing a library written in C against pure python, it seems not fair For the record: I wrote a library in C with a single function: from public keys to address (without b58 encoding) Private key : 0000000000000000000000000000000000000000000000000000000000000001
Public key :
x: 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y: 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
PrKey WIF c.: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73sVHnoWn
Address before b58 encode : 751e76e8199196d454941c45d1b3a323f1433bd6
Address with b58 encode : 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH
I imported this function as file .so in my python script, result: 1 core, 1M of addresses
time python3 gen_batches.py > addresses.out
real 0m3,961s
user 0m3,910s
sys 0m0,055s
16 cores, 1M of addresses
time python3 gen_batches.py > addresses.out
real 0m0,527s
user 0m7,404s
sys 0m0,151s
1 core, 16.4M of addresses
time python3 gen_batches.py > addresses.out
real 1m1,757s
user 1m1,382s
sys 0m0,348s
16 cores, 16.4M of addresses
time python3 gen_batches.py > addresses.out
real 0m6,672s
user 2m2,989s
sys 0m0,698s
less addresses.out
c71c6741ae4862dadaf2d9c9295d47410a27e194
1d9a3ef1efeec75b05f0ece73ad9402cac767843
44abfeb8701c716380ed2a40aeb72370ef61d7aa
d6a2aa6799f42078faa889dcda92b29c6005d84d
f3a0e804269feeba68d8c1facf68206b73b2a987
7a795a7b4500f80101e489e9ad5d7bc1855edf13
d8e619b13be4c2d6182aa10c0e7237a35ba0ab05
be801790f2cefb432bdf5dce2946fd22364b36b0
531a9c231f3e42d4bdb02d44bf01104e6eccd83d
7c8391a816b578f0d6e0a56595b67e12a314f945
6d0b359ba6f3d382eb99a346f99f0d27c29e2963
aa4116886a8631699f5077d78f47e6013a1af05f
2574970ffa9d5b26d52d89a76eef9c3c1bfbe798
...
then the speed is now about 2.4 MKeys/s. I'm pretty sure that more c functions you introduce in your python script, more fast it becomes. |
|
|
|
The example I originally showed using iceland2k14/libsecp256k1 was about half the speed. With it I can generate 1 million addresses using all cores (in my case 16 cores) and write to the file in 4.8 seconds, this is a rate of about 208,300 keys/sec. I have modified my initial program so that you can now also configure the cores under which the program is executed. So one can select specifically "1" as value, so that we also compare apples with apples. #!/usr/bin/env python3
# 2022/Dec/30, citb0in
import concurrent.futures
import os
import numpy as np
import fastecdsa.keys as fkeys
import fastecdsa.curve as fcurve
import secp256k1 as ice
# how many cores to use
num_cores = 1
#num_cores = os.cpu_count()
# Set the number of addresses to generate
num_addresses = 1000000
# Define a worker function that generates a batch of addresses and returns them
def worker(start, end):
# Generate a NumPy array of random private keys using fastecdsa
private_keys = np.array([fkeys.gen_private_key(fcurve.P256) for _ in range(start, end)])
# Use secp256k1 to convert the private keys to addresses
thread_addresses = np.array([ice.privatekey_to_address(2, True, dec) for dec in private_keys])
return thread_addresses
# Use a ProcessPoolExecutor to generate the addresses in parallel
with concurrent.futures.ProcessPoolExecutor() as executor:
# Divide the addresses evenly among the available CPU cores
addresses_per_core = num_addresses // num_cores
# Submit a task for each batch of addresses to the executor
tasks = []
for i in range(num_cores):
start = i * addresses_per_core
end = (i+1) * addresses_per_core
tasks.append(executor.submit(worker, start, end))
# Wait for the tasks to complete and retrieve the results
addresses = []
for task in concurrent.futures.as_completed(tasks):
addresses.extend(task.result())
# Write the addresses to a file
np.savetxt('addresses_1M_with_singleCore.txt', addresses, fmt='%s')
Running this under one single core, now I get 26.5 sec for 1 million generated addresses. This is a rate of 37,735 keys/second. I am curious to see your program using all available cores. Ok, finally I managed to use your multithread program with my script. Results: 30s to generate 16.4 M of addresses, about 540k addresses / s, and store them in a file. time python3 gen_batches.py > addresses.out
real 0m29,810s
user 8m22,402s
sys 0m6,273s
wc addresses.out
16474040 16474040 575934502
less addresses.out
18GW1MFwpYZgmRSy8R4wgjUtBnscJtXeUZ
1FXUP9HViWxrtgAvqbpgVrd69yarx6Njdp
1MuxV99fRFnhoNopdxV7kkQB4u14chCtqA
17AzXPYExdE8nxkiV6zJGLuJq32WkAZ134
12DUcGmFMkmXV8tYihM2jLQ36pc4zLBDP6
1AqwPisfi9hDHoF95SEoSEVN89fX8NSGjo
17qRbvdShkoCDw3XJGhEqxaFkQHaK36Yk1
187x8hPiVpRLGDRsvy4nreeMNW7aW9zuFv
1EGSDnc2j7p3qsPJsPakKgavCTz4szYU3w
1F4KjKLNqQSbmw9xsJurRVQ3RciL7Kox7g
1AKaHBfhMEedrtnjGgmFFsdG3SzyN3hpcZ
1GaWuuPPM747Na3CTwaR3DcewoBHc9VVSv
12VeWT4jZCep17HJswMtfCEqh14oDcRr3L
16MBC6WLWMvNeexYYX853Ucf2ZsPoYLRoS
1JVrhzEKTcgzGtSc9u9LpFjksFZiQveFT6
17kz2Wpry3vnLM6RMjB3KXoG6kRxjeDQcj
1TBh3q7vQoTmgX6pY75ADHDSkcaWkmCvd
13QVDFeeWkErhTAFqX3SP2YzrzWt3Bh7iu
1GPyzJC8Ey8PasHn2Qa8aFanjrXuE1aNK5
17QE8iNrtLnju5pinG1vdoCVZpn8zbrM7S
17nKRy1XdKdroWXPsnsd4RvxWKVySZxath
1KWaY8K824oEFk5q4tZioCZ86viLJuKNgS
141m3BUZNjMxbs4a9Cb6SbCmEzx4nPJKCL
12ueqsLkT1XCVheGM34uQWW2fpnhVvtwmE
14eH2SFvCq3fxmrK9NgKTxfMCeKixNwQ6c
1G9CaAqoKJSfTRyGcvPhVFewLRXKWzkwh7
15RthH7DBuDSmYcFCYanUhBsrdEYzBahNw
13BTmQ2gCaZ8x4T7Sba9k2MRBSDRrZLy6u
1NpbKVze4pPVCghjaa2CV7LfRkotCNu76Y
1HfQ42v7DEDHEuQMhH5caPzX2RgtSmoYWw
...
Only 1.3 s to generate 16.4 M public keys (without writing) 30s to generate 16.4 M addresses and store them in a file (24s if each thread writes on the file without waiting for the others) |
|
|
|
@arulbero
Impressive how you're getting those speeds on Python, considering that multithreading is complicated to do efficiently in that language, and GPU/FPGA support is lackluster to nonexistent.
It is not programming related, computing P+G is much more easier than compute P=3512878756844563653653674365654352352*G |
|
|
|
what is third and fourth element representing?
54338240394213138931889225770364196918256374885639854771044914499200701239376
91288621757068410199936994202114003372515557459679014336095768812037691308008
As I recognize, they seem not to be the public keys of the consequent keys 36028797808045094, 36028797808045095, 36028797808045096
The keys are generated in this way: P (P + 1*G , P - 1*G) -> 4 coordinates, x and y * 2 points (P + 2*G , P - 2*G) (P + 3*G , P - 3*G) (P + 4*G , P - 4*G) (P + 5*G , P - 5*G) (P + 6*G , P - 6*G) ..... ..... (P + 2048*G, P - 2048*G) each batch has all the consecutive keys from P - 2048*G to P+2048*G (4097 public keys), but they are not in order batch=[(0,0,0,0)]*2048
#the element number 0 of the list will be the middle point kG=(kx,ky), you can see it as the couple ((k+0)G, (k-0)G)
#the element number 1 will be the couple (k+1)G, (k-1)G
#the element number 2 will be the couple (k+2)G, (k-2)G
#...
#the element number 2048 will be the couple (k+2048)G, (k-2048)G
#each element of this list is a couple of points -> 4 scalars: x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G,
#but the first element is only a fake couple
batch = [(kx,ky,kx,ky)]+batch #the element number 0 of the list is now the middle point kG=(kx,ky), you can see it as the fake couple (k+0)G, (k-0)G
|
|
|
|
I realized that you output tuples of addresses using list(map). I suggest to adjust your program so it outputs a single address on each line so we compares apples by apples. I am not sure if the list output affects performance in some way, that's why I am pointing to it.
The example I originally showed using iceland2k14/libsecp256k1 was about half the speed. With it I can generate 1 million addresses using all cores (in my case 16 cores) and write to the file in 4.8 seconds, this is a rate of about 208,300 keys/sec. I have modified my initial program so that you can now also configure the cores under which the program is executed. So one can select specifically "1" as value, so that we also compare apples with apples.
To generate 1 address for line you need to replace print (*addresses,sep="\n") print (*addresses2,sep="\n") print (*addresses3,sep="\n") with for i in addresses: print (*i, sep="\n") for i in addresses2: print (*i, sep="\n") for i in addresses3: print (*i, sep="\n") The results are the same (slightly faster): time python3 gen_batches.py > addresses.out
real 3m5,736s
user 3m5,268s
sys 0m0,404s
wc addresses.out
16400196 16400196 573355137
less addresses.out
1K9oVg45UaApB1SmkxKFBZPCKsj2XiKCYw
1K9oVg45UaApB1SmkxKFBZPCKsj2XiKCYw
13hXNkmedXJ5UXt4RY5rLGAZGBgeSHUNT7
17G6zU4yVBM8WJ7TvJvkVkZr8qtJheAYVy
1LZtUG1S8V7yfwthDfJBy1Yg7LWxpZKmQX
1PDBxaiy3bp8woFbrErNAPoMF8W442B1Nb
1CAapBviMeMp91UjqgTaUfr1tGc5Lsvhgx
1Lmrc69RFRbwGUc3UTRGxumAApEDsJKUrf
1JNGqSWZdJFptRrLaCtmUJ6Hq1necKuTCd
18aQxp32qDDHEFWgVjexS1BG9MdFbQAc6N
....
|
|
|
|
@arulbero: thanks for sharing, sounds interesting. I need to dig into it, unfortunately I have to go right now but I certainly will check your code later when back at home. I need to think about the consecutive vs. random part and make some comparisons each other. Currently when I run your code it says it generated 1 million keys in average of 1.22 seconds. I just need to test if this speed is realistisc. Can you modify your code so it will generate an address and output all the generated addresses to a file called address.out ?
I don't have a fast 'pub_to_addr' function from 12.3 s to 3m and 9s to generate 16.4 M of addresses, 16.4 M / 190 s = about 86k addresses/s. 12 seconds to generate 16.4 M public keys, almost 3m to compute 16.4 M addresses. time python3 gen_batches.py > address.out
real 3m8,827s
user 3m8,252s
sys 0m0,520s
wc address.out
8200098 16400196 630754794
less address.out
('1K9oVg45UaApB1SmkxKFBZPCKsj2XiKCYw', '1K9oVg45UaApB1SmkxKFBZPCKsj2XiKCYw')
('13hXNkmedXJ5UXt4RY5rLGAZGBgeSHUNT7', '17G6zU4yVBM8WJ7TvJvkVkZr8qtJheAYVy')
('1LZtUG1S8V7yfwthDfJBy1Yg7LWxpZKmQX', '1PDBxaiy3bp8woFbrErNAPoMF8W442B1Nb')
('1CAapBviMeMp91UjqgTaUfr1tGc5Lsvhgx', '1Lmrc69RFRbwGUc3UTRGxumAApEDsJKUrf')
('1JNGqSWZdJFptRrLaCtmUJ6Hq1necKuTCd', '18aQxp32qDDHEFWgVjexS1BG9MdFbQAc6N')
('1CMNQMqqZdyABzU5bms6sE1J4hz2z7w86J', '1Awa5kf9npJ9sJKK65yA1vXFXaqC75tWvt')
('1GXDr1MF5ee5HfZHK98QQrDb8Mk785Hwtj', '14R3fvJcA8SSFgiCAPSQCvrquEG1NM7JcQ')
('1G578XchMTjHTuWduB37XNzNxEyvKxNNGC', '1E2aoTr22SDH18NJdamF3zqjztjtA5i5Cz')
('13BdD8vK9xaN1aw2WXn73rtLfjFvLAs3ES', '1Hgi86UjskxQpCmiKWPBK4Qjr97awHgZ7q')
('1Bnh87jjfNFy9QmRmnsW9vEDWbMDbBbjrF', '1P5wAX3U4v4oNde8yGUcg4YHwQdGRw33wo')
('1DXzgTcLD86LJDxrZerLEBXgQTLpCCRHRC', '1Ce5FYPKPSd9nf5Fv3KtKnzbpdCzJ7bPjg')
...
new ecc.py import hashlib
from hashlib import sha256
from binascii import a2b_hex, b2a_hex
from ripemd import ripemd160 #https://pypi.org/project/ripemd-hash/ --> pip install ripemd-hash
#see http://www.secg.org/sec2-v2.pdf at page 9
#Gx=55066263022277343669578718895168534326250603453777594175500187360389116729240
#Gy=32670510020758816978083085130507043184471273380659243275938904335757337482424
#p=115792089237316195423570985008687907853269984665640564039457584007908834671663
#n=115792089237316195423570985008687907852837564279074904382605163141518161494337
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F # Fp
n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # E(Fp)
#endomorphism
lambd=0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72 # (lambda^3 = 1 mod n)
lambd2=0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce #(lambda^2)
beta=0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee # (beta^3 = 1 mod p)
beta2=0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40 # (beta^2)
############################################################################################
###Field operations
#a must be a number between 1 and p-1; input: a output: 1/a
#see http://www.springer.com/?SGWID=4-102-45-110359-0 page 40 alg. 2.20
def inv(a,p):
u, v = a%p, p
x1, x2 = 1, 0
while u != 1:
#q = v//u
#r = v-q*u
q, r = divmod(v,u)
x = x2-q*x1
v = u
u = r
x2 = x1
x1 = x
return x1%p
#inverse of a batch of x
#input: batch of x : [x1,x2,x3,x4,x5,x6,x7,x8,...,x2048]
#x is known (x of kG)
#output: batch of inverse: 1/(x1-x), 1/(x2-x), 1/(x3-x), ....
#3M for each inverse
def inv_batch(x,batchx,p):
a = (batchx[1]-x) % p
partial= [0]*2049
partial[1]=a
for i in range(2,2049):
a = (a*(batchx[i]-x)) % p #2047M
partial[i]=a
inverse=inv(partial[2048],p) # 1I
batch_inverse=[0]*2049
for i in range(2048,1,-1):
batch_inverse[i-1]=(partial[i-1]*inverse) % p #2047M
inverse=(inverse*(batchx[i]-x)) %p #2047M
batch_inverse[0]=inverse
return batch_inverse
############################################################################################
##Group operations
# https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition
#'double' addition
#add 2 points P and Q --> P+Q
#add 2 points P and Q --> P-Q
#
#(X1,Y1) + (X2,Y2) --> (X3,Y3) (the inverse of (x2-x1) must be known)
#(X1,Y1) + (X2,-Y2) --> (X4,Y4) (the inverse of (x2-x1) must be known)
#
#input: (X1,Y1), (X2,Y2), the inverse of (X2 - X1): 5 scalars
#output: (X3,Y3), (X4,Y4) : 4 scalars
#4M + 2S
def double_add_P_Q_inv(x1, y1, x2, y2, invx2x1):
dy = (y2-y1) #% p
a = dy*invx2x1 % p #1M
a2 = a**2 #1S
x3 = (a2 - x1 -x2) % p
y3 = (a*(x1-x3) -y1) % p #1M
dy = p-(y2+y1) #% p # only the sign of y2 changes, "y of -Q = -y of +Q"
a = dy*invx2x1 % p #1M x2 and then the inverse invx2x1 are the same
a2 = a**2 #1S
x4 = (a2 - x1 -x2) % p
y4 = (a*(x1-x4) -y1) % p #1M
return x3, y3, x4, y4
#https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates
#jacobian coordinates
def add_j_j(jax, jay, jaz, jbx, jby, jbz):
u1 = (jax*jbz**2) % p
u2 = (jbx*jaz**2) % p
s1 = (jay*jbz**3) % p
s2 = (jby*jaz**3) % p
h = (u2-u1) % p
r = (s2-s1) % p
jcx = (r**2 -h**3-2*u1*h**2) % p
jcy = (r*(u1*h**2-jcx)-s1*h**3) % p
jcz = (h*jaz*jbz) % p
return jcx, jcy, jcz
def double_j_j(jx, jy, jz):
s = (4*jx*jy**2) % p
m = (3*jx**2) % p
jx2 = (m**2 - 2*s) % p
jy2 = (m*(s-jx2) - 8*jy**4) % p
jz2 = (2*jy*jz) % p
return jx2, jy2, jz2
def mul(k,jx,jy,jz):
jkx, jky, jkz = 0, 0, 1
if (k%2 == 1):
jkx, jky, jkz = jx, jy, jz #only if d is odd
q=k//2
while q>0:
jx, jy, jz = double_j_j(jx,jy,jz)
a=q%2
if (a > jkx):
jkx, jky, jkz = jx, jy, jz #only if d is even
elif (a):
jkx, jky, jkz = add_j_j(jx, jy, jz, jkx, jky, jkz)
q=q//2
return jkx, jky, jkz
############################################################################################
#Coordinates
#from jacobian to affine
def jac_to_aff(jax, jay, jaz, invjaz):
ax, ay = (jax*invjaz**2) % p, (jay*invjaz**3) % p
return ax, ay
############################################################################################
# 58 character alphabet used
__b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
__b58base = len(__b58chars)
def b58encode(v): #encode v, which is a string of bytes, to base58.
long_value = 0
if bytes == str: # python2
for (i, c) in enumerate(v[::-1]):
long_value += ord(c) << (8*i) # 2x speedup vs. exponentiation
else: # python3
for (i, c) in enumerate(v[::-1]):
long_value += ord(chr(c)) << (8*i) # 2x speedup vs. exponentiation
result = ''
#long_value = v
while long_value >= __b58base:
div, mod = divmod(long_value, __b58base)
result = __b58chars[mod] + result
long_value = div
result = __b58chars[long_value] + result
#return result
# Bitcoin does a little leading-zero-compression:
# leading 0-bytes in the input become leading-1s
nPad = 0
#if bytes == str: # python2
# for c in v:
# if c == '\0': nPad += 1
# else: break
#else: # python3
for c in v:
if chr(c) == '\0': nPad += 1
else: break
return (__b58chars[0]*nPad) + result
def b58decode(v, length):
""" decode v into a string of len bytes."""
print(type(v))
long_value = 0
for (i, c) in enumerate(v[::-1]):
long_value += __b58chars.find(c) * (__b58base**i)
div, mod = divmod(long_value, 256)
result = struct.pack("B", mod) #converte numero intero tra 0 e 255 in 1 byte https://docs.python.org/2/library/struct.html
long_value = div
while long_value >= 256:
div, mod = divmod(long_value, 256)
result = struct.pack("B", mod) + result #stringa di byte
long_value = div
result = struct.pack("B", long_value) + result
nPad = 0
for c in v:
if c == __b58chars[0]: nPad += 1
else: break
result = struct.pack("B", 0)*nPad + result
if length is not None and len(result) != length:
return None
print(type(result))
return result
def pub_to_addr(couple):
#d = int(d1,16)
#Px, Py = mul2G(d) # P = d*G
Px=couple[0]
Py=couple[1]
Px2=couple[2]
Py2=couple[3]
#if (compressed == 1):
if (Py % 2) == 0:
P_string = '02' + hex(Px)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari
else:
P_string = '03' + hex(Px)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari
#else: #uncompressed
# P_string = '04' + hex(Px)[2:].rstrip('L').rjust(64,'0') + hex(Py)[2:].rstrip('L').rjust(64,'0')
h = sha256(a2b_hex(P_string)) #sha256
h1=ripemd160.new() #ripmed160
h1.update(h.digest())
a = b'\x00' + h1.digest() #aggiunge byte 00 all'inizio
h2 = sha256(sha256(a).digest()).digest() #doppio sha256 per controllo
addr = a + h2[:4]
address1 = b58encode(addr) #ultimo passaggio: codifica in base 58
if (Py2 % 2) == 0:
P_string = '02' + hex(Px2)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari
else:
P_string = '03' + hex(Px2)[2:].rstrip('L').rjust(64,'0') #formato compresso - caso y pari
#else: #uncompressed
# P_string = '04' + hex(Px)[2:].rstrip('L').rjust(64,'0') + hex(Py)[2:].rstrip('L').rjust(64,'0')
h = sha256(a2b_hex(P_string)) #sha256
h1=ripemd160.new() #ripmed160
h1.update(h.digest())
a = b'\x00' + h1.digest() #aggiunge byte 00 all'inizio
h2 = sha256(sha256(a).digest()).digest() #doppio sha256 per controllo
addr = a + h2[:4]
address2 = b58encode(addr) #ultimo passaggio: codifica in base 58
return address1, address2
#print (address)
new gen_batches.py #!/usr/bin/env python
#this script computes 3x1334 batchs of 4097 points (1 single point + 2048 couples of points -> (kG+mG, kG-mg))
#16,4 millions of points
#3 : 1 batch + 2 endomorphism
from ecc import *
########################################################################
#in this section the script pre-computes 1G, 2G, 3G, ..., 2048G
mG = [(0,0)]*2049
mGx = [0]*2049
mGy = [0]*2049
mGx[1]=Gx
mGy[1]=Gy
mG[1]=(Gx,Gy) #list of multiples of G,
#you have to precompute and store these multiples somewhere
mGx[2]=0xC6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
mGy[2]=0x1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A
mG[2]=(mGx[2],mGy[2])
for i in range(3,2049):
jx,jy,jz=add_j_j(Gx, Gy, 1, mGx[i-1], mGy[i-1], 1) #this is not a efficient way, but it is not important
jzinv = inv(jz,p)
(x,y) = jac_to_aff(jx, jy, jz, jzinv)
mG[i] = (x,y)
mGx[i] = x
mGy[i] = y
###########################################################################
lowest_key=2**55+789079076 #put here the lowest key you want to generate
number_of_batches=1334 #put here how many consecutive batches you want to generate
number_of_keys=4097*3*number_of_batches #this is the number of consecutive keys you are going to generate
#this number is always a multiple of 3*4097=12291, because 12291 is the minimum size
#remember: you generate always 3 batches at once, 1 in (1,2^160) and 2 out of this range
#their name are: batch (the main), batch2, batch3 (that are derived from the main with endomorphism)
id_batch=lowest_key+2048 #id_batch is now the private key of the middle point of the first batch that you want compute
distance_between_successive_batches=4097 #this is the distance from the middle point of the first batch and the middle point of the successive batch in (1,2^160)
#4097 means that I'm generating only consecutive batches in (1,2^160), this is the default
start=id_batch #the first key to generate of the the first batch is the lowest key + 2048 --> the middle point of the first batch
stop=id_batch + number_of_batches*distance_between_successive_batches #the key of the middle point of the last batch
#k is always the id of the current main batch and the key of the middle point of the current main batch
for k in range(start,stop,distance_between_successive_batches):
jkx,jky,jkz = mul(k,Gx,Gy,1) #here we use the slow function mul to generate the middle point
invjkz = inv(jkz,p)
(kx,ky) = jac_to_aff(jkx, jky, jkz, invjkz)
kminverse = [0]*2048
kminverse = inv_batch(kx,mGx,p) #you need to compute 2048 inverse, 1 for each couple
#to perform this task you need only the x coordinates of the multiples of G and the x coordinate of kG: kx
kminverse = [invjkz]+kminverse
#the element number 0 of the list is the inverse invjkz that you have computed to get kG=(kx,ky)
#the element number 1 of the list is the inverse necessary to perform kG + 1G (and kG-1G) ---> 1/(x_of_1G - kx)
#the element number 2 of the list is the inverse necessary to perform kG + 2G (and kG-2G) ---> 1/(x_of_2G - kx)
#...
#the element number m of the list is the inverse necessary to perform kG + mG (and kG-mG) ---> 1/(x_of_mG - kx)
#then the name: "kminverse", the inverse to get the generic kG+mG
#...
#the element number 2048 of the list is the inverse necessary to perform kG+2048G and kG-2048G ---> 1/(x_of_2048G - kx)
kxl = [kx] * 2049 #this is a list of kx, all elements are the same, only to use the function map of python
kyl = [ky] * 2049 #this is a list of ky, all elements are the same, only to use the function map of python
batch=[(0,0,0,0)]*2048
#the element number 0 of the list will be the middle point kG=(kx,ky), you can see it as the couple ((k+0)G, (k-0)G)
#the element number 1 will be the couple (k+1)G, (k-1)G
#the element number 2 will be the couple (k+2)G, (k-2)G
#...
#the element number 2048 will be the couple (k+2048)G, (k-2048)G
#each element of this list is a couple of points -> 4 scalars: x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G,
#but the first element is only a fake couple
batch = list(map(double_add_P_Q_inv,kxl[1:],kyl[1:],mGx[1:],mGy[1:],kminverse[1:]))
#the function double_add_P_Q_inv computes kG +/-mG, it uses the list of the inverse and return a list of couple of points
#each element of this list is a couple of points, 4 scalars, x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G
#this list has 2049 elements
batch = [(kx,ky,kx,ky)]+batch #the element number 0 of the list is now the middle point kG=(kx,ky), you can see it as the fake couple (k+0)G, (k-0)G
#batch_tot = batch_tot + batch
addresses = list(map(pub_to_addr, batch))
print (*addresses, sep="\n")
batch2=[(0,0,0,0)] * 2049 #this is the batch2 with lambda*kG, ( lambda*(k+1)G, lambda*(k-1)G ), ( lambda*(k+2)G, lambda*(k-2)G ), ....,
# (lambda*(k+2048)G, lambda*(k-2048)G)
#this list actually has only the x-cooordinates of the points, because the y-coordinates are the same of main batch
#each element of this list is a couple of x -> 2 scalars: x_lambda*(k+m)G, x_lambda*(k-m)G
#this list has 2049 elements
batch3=[(0,0,0,0)] * 2049 #this is the batch3 with lambda^2*kG, ( lambda^2*(k+1)G, lambda^2*(k-1)G ), ( lambda^2*(k+2)G, lambda^2*(k-2)G ), ....,
# (lambda^2*(k+2048)G, lambda^2*(k-2048)G)
#this list actually has only the x-cooordinates of the points, because the y-coordinates are the same of main batch
#each element of this list is a couple of x -> 2 scalars: x_lambda^2*(k+m)G, x_lambda^2*(k-m)G
#this list has 2049 elements
for i in range(0,2049): #endomorphism
batch2[i] = ((batch[i][0]*beta % p), batch[i][1], (batch[i][2]*beta % p), batch[i][3]) #only x coordinates, the first and the third scalar of each element of the main batch
#private key: lambda*k mod n, coordinate x: beta*x mod p
batch3[i] = ((batch[i][0]*beta2 % p), batch[i][1], (batch[i][2]*beta2 % p), batch[i][3]) #only x coordinates, the first and the third scalar of each element of the main batch
#private key: lambda^2*k mod n, coordinate x: beta^2*x mod p
addresses2 = list(map(pub_to_addr, batch2))
print (*addresses2, sep="\n")
addresses3 = list(map(pub_to_addr, batch3))
print (*addresses3, sep="\n")
#k in this case is the id of the last batch (or if you prefer, k is the private key of the middle point of the last batch)
"""
m=465 #a random number between 0 and 2048, you can pick up a couple of points in the last main batch (or in batch2 / batch3)
(kmx1,kmy1,kmx2,kmy2)=batch[m]
(kmx1,kmx2)=batch3[m] #in this case the points chosen are in batch3
#the y are from main batch, because batch3 (and batch2) have only x coordinates
print ('kG+mG')
print (hex(lambd2*(k+m)%n)) #private key
print (hex(kmx1), hex(kmy1)) #public key (first and second coordinate)
print ('*******')
print ('kG-mG')
print (hex(lambd2*(k-m)%n)) #private key
print (hex(kmx2), hex(kmy2)) #public key (first and second coordinate)
print ('*******')
"""
"""
print (' ')
a=number_of_keys//1000000
print ('You have just generated ' + str(a) + ' Millions of keys!!!')
"""
|
|
|
|
real 0m4,768s
user 0m54,444s
sys 0m1,894s
Perfect! Now I'm under 5 seconds for 1 million addresses. That's a rate of roughly 208,000 addresses/secHow can we further improve the performance without using GPU? Is there anything else you can suggest, that will speed up the process? Let's make a contest-like game. Create a simple code like this and try to beat the high score of currently 4.7 seconds for 1million bech32 addresses without using GPU. The next step would be ==> how can we shuffle this code to the GPU for ultra-fast performance ? Long time ago I wrote a python script that computes 16.4 million of consecutive (non random) public keys (not addresses) in 12.3 s. No numpy, pure python, only 1 thread. ecc.py
#see http://www.secg.org/sec2-v2.pdf at page 9
#Gx=55066263022277343669578718895168534326250603453777594175500187360389116729240
#Gy=32670510020758816978083085130507043184471273380659243275938904335757337482424
#p=115792089237316195423570985008687907853269984665640564039457584007908834671663
#n=115792089237316195423570985008687907852837564279074904382605163141518161494337
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F # Fp
n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # E(Fp)
#endomorphism
lambd=0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72 # (lambda^3 = 1 mod n)
lambd2=0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce #(lambda^2)
beta=0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee # (beta^3 = 1 mod p)
beta2=0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40 # (beta^2)
############################################################################################
###Field operations
#a must be a number between 1 and p-1; input: a output: 1/a
#see http://www.springer.com/?SGWID=4-102-45-110359-0 page 40 alg. 2.20
def inv(a,p):
u, v = a%p, p
x1, x2 = 1, 0
while u != 1:
#q = v//u
#r = v-q*u
q, r = divmod(v,u)
x = x2-q*x1
v = u
u = r
x2 = x1
x1 = x
return x1%p
#inverse of a batch of x
#input: batch of x : [x1,x2,x3,x4,x5,x6,x7,x8,...,x2048]
#x is known (x of kG)
#output: batch of inverse: 1/(x1-x), 1/(x2-x), 1/(x3-x), ....
#3M for each inverse
def inv_batch(x,batchx,p):
a = (batchx[1]-x) % p
partial= [0]*2049
partial[1]=a
for i in range(2,2049):
a = (a*(batchx[i]-x)) % p #2047M
partial[i]=a
inverse=inv(partial[2048],p) # 1I
batch_inverse=[0]*2049
for i in range(2048,1,-1):
batch_inverse[i-1]=(partial[i-1]*inverse) % p #2047M
inverse=(inverse*(batchx[i]-x)) %p #2047M
batch_inverse[0]=inverse
return batch_inverse
############################################################################################
##Group operations
# https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition
#'double' addition
#add 2 points P and Q --> P+Q
#add 2 points P and Q --> P-Q
#
#(X1,Y1) + (X2,Y2) --> (X3,Y3) (the inverse of (x2-x1) must be known)
#(X1,Y1) + (X2,-Y2) --> (X4,Y4) (the inverse of (x2-x1) must be known)
#
#input: (X1,Y1), (X2,Y2), the inverse of (X2 - X1): 5 scalars
#output: (X3,Y3), (X4,Y4) : 4 scalars
#4M + 2S
def double_add_P_Q_inv(x1, y1, x2, y2, invx2x1):
dy = (y2-y1) #% p
a = dy*invx2x1 % p #1M
a2 = a**2 #1S
x3 = (a2 - x1 -x2) % p
y3 = (a*(x1-x3) -y1) % p #1M
dy = p-(y2+y1) #% p # only the sign of y2 changes, "y of -Q = -y of +Q"
a = dy*invx2x1 % p #1M x2 and then the inverse invx2x1 are the same
a2 = a**2 #1S
x4 = (a2 - x1 -x2) % p
y4 = (a*(x1-x4) -y1) % p #1M
return x3, y3, x4, y4
#https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates
#jacobian coordinates
def add_j_j(jax, jay, jaz, jbx, jby, jbz):
u1 = (jax*jbz**2) % p
u2 = (jbx*jaz**2) % p
s1 = (jay*jbz**3) % p
s2 = (jby*jaz**3) % p
h = (u2-u1) % p
r = (s2-s1) % p
jcx = (r**2 -h**3-2*u1*h**2) % p
jcy = (r*(u1*h**2-jcx)-s1*h**3) % p
jcz = (h*jaz*jbz) % p
return jcx, jcy, jcz
def double_j_j(jx, jy, jz):
s = (4*jx*jy**2) % p
m = (3*jx**2) % p
jx2 = (m**2 - 2*s) % p
jy2 = (m*(s-jx2) - 8*jy**4) % p
jz2 = (2*jy*jz) % p
return jx2, jy2, jz2
def mul(k,jx,jy,jz):
jkx, jky, jkz = 0, 0, 1
if (k%2 == 1):
jkx, jky, jkz = jx, jy, jz #only if d is odd
q=k//2
while q>0:
jx, jy, jz = double_j_j(jx,jy,jz)
a=q%2
if (a > jkx):
jkx, jky, jkz = jx, jy, jz #only if d is even
elif (a):
jkx, jky, jkz = add_j_j(jx, jy, jz, jkx, jky, jkz)
q=q//2
return jkx, jky, jkz
############################################################################################
#Coordinates
#from jacobian to affine
def jac_to_aff(jax, jay, jaz, invjaz):
ax, ay = (jax*invjaz**2) % p, (jay*invjaz**3) % p
return ax, ay
gen_batches.py #!/usr/bin/env python
#this script computes 3x1334 batchs of 4097 points (1 single point + 2048 couples of points -> (kG+mG, kG-mg))
#16,4 millions of points
#3 : 1 batch + 2 endomorphism
from ecc import *
########################################################################
#in this section the script pre-computes 1G, 2G, 3G, ..., 2048G
mG = [(0,0)]*2049
mGx = [0]*2049
mGy = [0]*2049
mGx[1]=Gx
mGy[1]=Gy
mG[1]=(Gx,Gy) #list of multiples of G,
#you have to precompute and store these multiples somewhere
mGx[2]=0xC6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
mGy[2]=0x1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A
mG[2]=(mGx[2],mGy[2])
for i in range(3,2049):
jx,jy,jz=add_j_j(Gx, Gy, 1, mGx[i-1], mGy[i-1], 1) #this is not a efficient way, but it is not important
jzinv = inv(jz,p)
(x,y) = jac_to_aff(jx, jy, jz, jzinv)
mG[i] = (x,y)
mGx[i] = x
mGy[i] = y
###########################################################################
lowest_key=2**55+789079076 #put here the lowest key you want to generate
number_of_batches=1334 #put here how many consecutive batches you want to generate
number_of_keys=4097*3*number_of_batches #this is the number of consecutive keys you are going to generate
#this number is always a multiple of 3*4097=12291, because 12291 is the minimum size
#remember: you generate always 3 batches at once, 1 in (1,2^160) and 2 out of this range
#their name are: batch (the main), batch2, batch3 (that are derived from the main with endomorphism)
id_batch=lowest_key+2048 #id_batch is now the private key of the middle point of the first batch that you want compute
distance_between_successive_batches=4097 #this is the distance from the middle point of the first batch and the middle point of the successive batch in (1,2^160)
#4097 means that I'm generating only consecutive batches in (1,2^160), this is the default
start=id_batch #the first key to generate of the the first batch is the lowest key + 2048 --> the middle point of the first batch
stop=id_batch + number_of_batches*distance_between_successive_batches #the key of the middle point of the last batch
#k is always the id of the current main batch and the key of the middle point of the current main batch
for k in range(start,stop,distance_between_successive_batches):
jkx,jky,jkz = mul(k,Gx,Gy,1) #here we use the slow function mul to generate the middle point
invjkz = inv(jkz,p)
(kx,ky) = jac_to_aff(jkx, jky, jkz, invjkz)
kminverse = [0]*2048
kminverse = inv_batch(kx,mGx,p) #you need to compute 2048 inverse, 1 for each couple
#to perform this task you need only the x coordinates of the multiples of G and the x coordinate of kG: kx
kminverse = [invjkz]+kminverse
#the element number 0 of the list is the inverse invjkz that you have computed to get kG=(kx,ky)
#the element number 1 of the list is the inverse necessary to perform kG + 1G (and kG-1G) ---> 1/(x_of_1G - kx)
#the element number 2 of the list is the inverse necessary to perform kG + 2G (and kG-2G) ---> 1/(x_of_2G - kx)
#...
#the element number m of the list is the inverse necessary to perform kG + mG (and kG-mG) ---> 1/(x_of_mG - kx)
#then the name: "kminverse", the inverse to get the generic kG+mG
#...
#the element number 2048 of the list is the inverse necessary to perform kG+2048G and kG-2048G ---> 1/(x_of_2048G - kx)
kxl = [kx] * 2049 #this is a list of kx, all elements are the same, only to use the function map of python
kyl = [ky] * 2049 #this is a list of ky, all elements are the same, only to use the function map of python
batch=[(0,0,0,0)]*2048
#the element number 0 of the list will be the middle point kG=(kx,ky), you can see it as the couple ((k+0)G, (k-0)G)
#the element number 1 will be the couple (k+1)G, (k-1)G
#the element number 2 will be the couple (k+2)G, (k-2)G
#...
#the element number 2048 will be the couple (k+2048)G, (k-2048)G
#each element of this list is a couple of points -> 4 scalars: x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G,
#but the first element is only a fake couple
batch = list(map(double_add_P_Q_inv,kxl[1:],kyl[1:],mGx[1:],mGy[1:],kminverse[1:]))
#the function double_add_P_Q_inv computes kG +/-mG, it uses the list of the inverse and return a list of couple of points
#each element of this list is a couple of points, 4 scalars, x_(k+m)G,y_(k+m)G,x_(k-m)G,y_(k-m)G
#this list has 2049 elements
batch = [(kx,ky,kx,ky)]+batch #the element number 0 of the list is now the middle point kG=(kx,ky), you can see it as the fake couple (k+0)G, (k-0)G
batch2=[0] * 2049 #this is the batch2 with lambda*kG, ( lambda*(k+1)G, lambda*(k-1)G ), ( lambda*(k+2)G, lambda*(k-2)G ), ....,
# (lambda*(k+2048)G, lambda*(k-2048)G)
#this list actually has only the x-cooordinates of the points, because the y-coordinates are the same of main batch
#each element of this list is a couple of x -> 2 scalars: x_lambda*(k+m)G, x_lambda*(k-m)G
#this list has 2049 elements
batch3=[0] * 2049 #this is the batch3 with lambda^2*kG, ( lambda^2*(k+1)G, lambda^2*(k-1)G ), ( lambda^2*(k+2)G, lambda^2*(k-2)G ), ....,
# (lambda^2*(k+2048)G, lambda^2*(k-2048)G)
#this list actually has only the x-cooordinates of the points, because the y-coordinates are the same of main batch
#each element of this list is a couple of x -> 2 scalars: x_lambda^2*(k+m)G, x_lambda^2*(k-m)G
#this list has 2049 elements
for i in range(0,2049): #endomorphism
batch2[i] = [(batch[i][0]*beta % p), (batch[i][2]*beta % p)] #only x coordinates, the first and the third scalar of each element of the main batch
#private key: lambda*k mod n, coordinate x: beta*x mod p
batch3[i] = [(batch[i][0]*beta2 % p), (batch[i][2]*beta2 % p)] #only x coordinates, the first and the third scalar of each element of the main batch
#private key: lambda^2*k mod n, coordinate x: beta^2*x mod p
#k in this case is the id of the last batch (or if you prefer, k is the private key of the middle point of the last batch)
m=465 #a random number between 0 and 2048, you can pick up a couple of points in the last main batch (or in batch2 / batch3)
(kmx1,kmy1,kmx2,kmy2)=batch[m]
(kmx1,kmx2)=batch3[m] #in this case the points chosen are in batch3
#the y are from main batch, because batch3 (and batch2) have only x coordinates
print ('kG+mG')
print (hex(lambd2*(k+m)%n)) #private key
print (hex(kmx1), hex(kmy1)) #public key (first and second coordinate)
print ('*******')
print ('kG-mG')
print (hex(lambd2*(k-m)%n)) #private key
print (hex(kmx2), hex(kmy2)) #public key (first and second coordinate)
print ('*******')
print (' ')
a=number_of_keys//1000000
print ('You have just generated ' + str(a) + ' Millions of keys!!!')
time python3 gen_batches.py
You have just generated 16.4 Millions of keys!!!
real 0m12,303s
user 0m12,302s
sys 0m0,000s
Generating consecutive public keys is way faster than generate random public keys. |
|
|
|
Incuriosito dai dubbi di babo, ho approfondito il punto accennato nell'EDIT 2, sempre in risposta alla domanda "è possibile usare un seed utilizzando una sola parola?" Ho cercato quali erano le parole (o meglio: le posizioni) che permettevano di costruire una frase mnemonica costituita da un'unica parola che si ripete 24 volte. Ho costruito quindi un programmino python (con l'aiuto di ChatGPT) che per ognuna della 2048 parole possibili calcola il checksum (sha256 della sequenza: parola x 23) e controlla così se anche l'ultima parola viene a coincidere (per puro caso) proprio con la parola scelta all'inizio: import hashlib
import binascii
def compute_sha256_hash(input_number):
h = int(input_number, 2).to_bytes(32, byteorder='big')
a = binascii.hexlify(hashlib.sha256(h).digest()).decode()
return a
#Crea una lista di tutte le stringhe di 11 bit da 00000000000 a 11111111111
all_strings = [bin(i)[2:].zfill(11) for i in range(2048)]
# Per ogni stringa di 11 bit, costruisci una stringa di 253 bit ripetendo la stringa di 11 bit 23 volte + 3 bit iniziali
input_strings = [s*23+s[0:3] for s in all_strings]
# Cerca tra tutte le stringhe solo quelle che producono una parola finale uguale a quella iniziale
for s in input_strings:
# I primi 11 bit rappresentano la posizione dell'unica parola con cui si cerca di costruire la frase mnemonica
first_11_bit = s[0:11]
# Calcola l'hash SHA-256 della stringa di input
hash_value = compute_sha256_hash(s)
# Converte l'hash in formato esadecimale in una stringa di bit
hash_value_bin = bin(int(hash_value, 16))[2:]
# Aggiunge gli zero mancanti alla stringa di bit per renderla lunga 256 caratteri
hash_value_bin = hash_value_bin.zfill(256)
# Calcola il check_sum 8 bit
check_sum = hash_value_bin[0:8]
# Posizione dell'ultima parola
last_word_pos = s[0:3] + check_sum
# Stampa le posizioni relative alle parole che stiamo cercando
if s[3:11] == check_sum:
print(first_11_bit)
print(int(last_word_pos,base=2)+1)
Ho così verificato, in linea con la teoria, dopo aver effettuato tutti i 2048 tentativi possibili (ognuno con probabilità 1/256 di determinare gli ultimi 8 bit in modo tale da ottenere come ultima parola esattamente la stessa utilizzata per le prime 23) esistono esattamente 11 parole che permettono una costruzione di una mnemonica 'monotona': 00010001010 -> 139
01011000001 -> 706
01100000000 -> 769
01100110001 -> 818
11001011011 -> 1628
11001110110 -> 1655
11011001001 -> 1738
11100000100 -> 1797
11100110101 -> 1846
11100111010 -> 1851
11111111100 -> 2045
La parola numero 139 corrisponde nel dizionario: italiano: arnese -> https://github.com/bitcoin/bips/blob/master/bip-0039/italian.txtmnemonica: arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese arnese
Bip 39 Seed: f92660b63f8f671d4afca69ffbb979dc1aaedb8b6764623a38234242cb025de2130a835435ca31747695733a0c51b6aefbef5f568bd44ef800b96441672614c3
primo address: 18x5P5xiGTPezm1vHa6LRd8ZYGbTQeLxAe
inglese: bacon -> https://github.com/bitcoin/bips/blob/master/bip-0039/english.txtmnemonica: bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon bacon
Bip 39 Seed: 241e86356db60a686bb8c30b1054eac70701493b6702ed5f4a0e54cd3d13f0ccfd6d8b37506dc5c65af5575e720196d6d81aca24f0f083a5c65597541ada0e32
primo address: 159ysWF6HKJHvzCFEkVvDnHNgBjkbqj6K4
spagnolo: archivio -> https://github.com/bitcoin/bips/blob/master/bip-0039/spanish.txtmnemonica: archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio archivio
Bip 39 Seed: 7939cac0ec8f1bce6f0a131b97612733ef7bf2582fd339ef9cf270a971e60ca3e134ec5d3632fe801413f2956360044743dc0d5ae656e22aa063f175df7579fe
primo address: 1K7D5NwuL9xtiS9KMCz1HF7hy1ipwdX2RH
Al solito, solo l'address inglese: https://www.blockchain.com/explorer/addresses/btc/159ysWF6HKJHvzCFEkVvDnHNgBjkbqj6K4 mostra attività in passato. L'entropia (139 -> 00010001010 per 23 volte + 000 = 256 bit) corrispondente è : 0001000101000010001010000100010100001000101000010001010000100010100001000101000010001010000100010100001000101000010001010000100010100001000101000010001010000100010100001000101000010001010000100010100001000101000010001010000100010100001000101000010001010000
Per quanta riguarda le mnemoniche con 12 parole, poichè in quel caso si utilizzano solo 4 bit come check sum: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch05.asciidoc#table_4-5una stima del numero di parole che permettono una sequenza ripetitiva è : 2048 * 1/16 = 128 parole (+ o meno, il dato reale non lo so, non ho fatto anche questa verifica). Da notare che se una parola può consentire una frase 'monotona' di lunghezza 24 non è detto che la stessa consenta anche la formazione di una frase monotona di lunghezza 12 (e viceversa), in quanto il cheksum dipende dallo sha256 dell'entropia, e passando da 256 bit a 128 bit il risultato cambia. --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- In generale, vedendo come si costruisce la mnemonica a partire da una stringa di 256 bit,si può dire: 1) fissate le prime 23 parole, ci sono solo 8 parole che possono completare la frase, non 2048; sono 8 perchè dopo aver fissato 11 bit * 23 = 253 bit, avanzano solo 3 bit per 'impostare' l'ultima parola 2) nel caso di 12 parole (128 bit di entropia), fissate le prime 11 parole , ci sono 128 parole che possono completare la frase, non 2048. 3) le prime 23 parole su 24 (o 11 su 12) possono essere qualsiasi, anche ripetute, per l'ultima parola invece ci sono meno possibilità |
|
|
|
it appears to be that the multiplication has the secp256k1 characteristic modulus hardcoded into the algorithm, making it suitable only for public key multiplication.
I was thinking about making an adapted version of the multiplication algorithm that uses the curve order (subtracted from 2^256) in its place, so that private key multiplication is covered as well.
I haven't explored the 10x26 legs imply too deep, but I'm assuming it's a similar case.
Since you're here though, let me ask: Was the multiplication assembly (and possibly the C version of it in another file using int128) only intended for public keys?
You have to distinguish between: 1) field operations (mod p, space of coordinates x and y): https://github.com/bitcoin-core/secp256k1/tree/master/src/ all files with name : field* and 2) scalar operations (mod n, space of private keys): https://github.com/bitcoin-core/secp256k1/tree/master/src/ all files with name : scalar* If you want to multiply 2 private keys (mod n): you could use secp256k1_scalar_mul_512 (256bit * 256 bit -> 512 bit) (assembly multiplication) https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_4x64_impl.h#L587inline void secp256k1_scalar_mul_512(uint64_t* l, const uint64_t *a, const uint64_t *b) {
//uint64_t l[8];
__asm__ __volatile__ (
/* Preload */
"movq 0(%%rdi), %%r15\n"
"movq 8(%%rdi), %%rbx\n"
"movq 16(%%rdi), %%rcx\n"
"movq 0(%%rdx), %%r11\n"
"movq 8(%%rdx), %%r12\n"
"movq 16(%%rdx), %%r13\n"
"movq 24(%%rdx), %%r14\n"
/* (rax,rdx) = a0 * b0 */
"movq %%r15, %%rax\n"
"mulq %%r11\n"
/* Extract l0 */
"movq %%rax, 0(%%rsi)\n"
/* (r8,r9,r10) = (rdx) */
"movq %%rdx, %%r8\n"
"xorq %%r9, %%r9\n"
"xorq %%r10, %%r10\n"
/* (r8,r9,r10) += a0 * b1 */
"movq %%r15, %%rax\n"
"mulq %%r12\n"
"addq %%rax, %%r8\n"
"adcq %%rdx, %%r9\n"
"adcq $0, %%r10\n"
/* (r8,r9,r10) += a1 * b0 */
"movq %%rbx, %%rax\n"
"mulq %%r11\n"
"addq %%rax, %%r8\n"
"adcq %%rdx, %%r9\n"
"adcq $0, %%r10\n"
/* Extract l1 */
"movq %%r8, 8(%%rsi)\n"
"xorq %%r8, %%r8\n"
/* (r9,r10,r8) += a0 * b2 */
"movq %%r15, %%rax\n"
"mulq %%r13\n"
"addq %%rax, %%r9\n"
"adcq %%rdx, %%r10\n"
"adcq $0, %%r8\n"
/* (r9,r10,r8) += a1 * b1 */
"movq %%rbx, %%rax\n"
"mulq %%r12\n"
"addq %%rax, %%r9\n"
"adcq %%rdx, %%r10\n"
"adcq $0, %%r8\n"
/* (r9,r10,r8) += a2 * b0 */
"movq %%rcx, %%rax\n"
"mulq %%r11\n"
"addq %%rax, %%r9\n"
"adcq %%rdx, %%r10\n"
"adcq $0, %%r8\n"
/* Extract l2 */
"movq %%r9, 16(%%rsi)\n"
"xorq %%r9, %%r9\n"
/* (r10,r8,r9) += a0 * b3 */
"movq %%r15, %%rax\n"
"mulq %%r14\n"
"addq %%rax, %%r10\n"
"adcq %%rdx, %%r8\n"
"adcq $0, %%r9\n"
/* Preload a3 */
"movq 24(%%rdi), %%r15\n"
/* (r10,r8,r9) += a1 * b2 */
"movq %%rbx, %%rax\n"
"mulq %%r13\n"
"addq %%rax, %%r10\n"
"adcq %%rdx, %%r8\n"
"adcq $0, %%r9\n"
/* (r10,r8,r9) += a2 * b1 */
"movq %%rcx, %%rax\n"
"mulq %%r12\n"
"addq %%rax, %%r10\n"
"adcq %%rdx, %%r8\n"
"adcq $0, %%r9\n"
/* (r10,r8,r9) += a3 * b0 */
"movq %%r15, %%rax\n"
"mulq %%r11\n"
"addq %%rax, %%r10\n"
"adcq %%rdx, %%r8\n"
"adcq $0, %%r9\n"
/* Extract l3 */
"movq %%r10, 24(%%rsi)\n"
"xorq %%r10, %%r10\n"
/* (r8,r9,r10) += a1 * b3 */
"movq %%rbx, %%rax\n"
"mulq %%r14\n"
"addq %%rax, %%r8\n"
"adcq %%rdx, %%r9\n"
"adcq $0, %%r10\n"
/* (r8,r9,r10) += a2 * b2 */
"movq %%rcx, %%rax\n"
"mulq %%r13\n"
"addq %%rax, %%r8\n"
"adcq %%rdx, %%r9\n"
"adcq $0, %%r10\n"
/* (r8,r9,r10) += a3 * b1 */
"movq %%r15, %%rax\n"
"mulq %%r12\n"
"addq %%rax, %%r8\n"
"adcq %%rdx, %%r9\n"
"adcq $0, %%r10\n"
/* Extract l4 */
"movq %%r8, 32(%%rsi)\n"
"xorq %%r8, %%r8\n"
/* (r9,r10,r8) += a2 * b3 */
"movq %%rcx, %%rax\n"
"mulq %%r14\n"
"addq %%rax, %%r9\n"
"adcq %%rdx, %%r10\n"
"adcq $0, %%r8\n"
/* (r9,r10,r8) += a3 * b2 */
"movq %%r15, %%rax\n"
"mulq %%r13\n"
"addq %%rax, %%r9\n"
"adcq %%rdx, %%r10\n"
"adcq $0, %%r8\n"
/* Extract l5 */
"movq %%r9, 40(%%rsi)\n"
/* (r10,r8) += a3 * b3 */
"movq %%r15, %%rax\n"
"mulq %%r14\n"
"addq %%rax, %%r10\n"
"adcq %%rdx, %%r8\n"
/* Extract l6 */
"movq %%r10, 48(%%rsi)\n"
/* Extract l7 */
"movq %%r8, 56(%%rsi)\n"
: "+d"(b)
: "S"(l), "D"(a)
: "rax", "rbx", "rcx", "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", "cc", "memory");
}
where for example const uint64_t a[4] = {0x59f2815b16f81798, 0x029bfcdb2dce28d9, 0x55a06295ce870b07, 0x79be667ef9dcbbac};
const uint64_t b[4] = {0x9c47d08ffb10d4b8, 0xfd17b448a6855419, 0x5da4fbfc0e1108a8, 0x483ada7726a3c465};
uint64_t c[8] = {0};
secp256k1_scalar_mul_512(c, a, b);
printf("%016lx%016lx%016lx%016lx%016lx%016lx%016lx%016lx\n", c[7], c[6], c[5], c[4], c[3], c[2], c[1], c[0]);
Result:
225989dbbc349b6f319ca3eed777a46f55b1dc22e97af11261167d213c1f060d29520a21508989b06ed1194129efb1517cee385a708abe44718bc509775ad540
and then apply the function secp256k1_scalar_reduce_512 (from 512 bit to 256 bit mod n) https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_4x64_impl.h#L274to get the result mod n https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_4x64_impl.h#L761-L765805714a252d0c0b58910907e85b5b801fff610a36bdf46847a4bf5d9ae2d10ed
I got the same results with my function, with libsecp256k1 functions and with python3 too: >>> n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
>>> a=0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
>>> b=0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
>>> hex(a*b)
'0x225989dbbc349b6f319ca3eed777a46f55b1dc22e97af11261167d213c1f060d29520a21508989b06ed1194129efb1517cee385a708abe44718bc509775ad540'
>>> hex(a*b % n)
'0x805714a252d0c0b58910907e85b5b801fff610a36bdf46847a4bf5d9ae2d10ed'
|
|
|
|
sono dubbi che mi porto dietro da una vita, oggi sn al pronto soccorso e mi annoio, quindi studio
Spero non sia nulla di grave. - si puo creare un seed con una sola parola? esempio (sobrio sobrio sobrio sobrio... x12)
- creare un seed con le parole inglesi numero:2, 5, 7, 10, 12... eqiuvale a creare un seed con le medesime parole del dizionario.. italiano?
Le tue domande non sono stupide, dopo un breve ripasso https://learnmeabitcoin.com/technical/mnemonicle risposte sono: 1) sì (quasi, a parte l'ultima**) 2) no ho provato a inserire a mano una entropia banale qui: https://bip32jp.github.io/english/entropy : 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
mnemonic: abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon art
comparando con altre lingue si ottengono risultati diversi: (stessa entropia, stessa sequenza numerica delle parole, ma diversi dizionari e quindi diverso seed finale): https://iancoleman.io/bip39/#italianhttps://iancoleman.io/bip39/#englishhttps://iancoleman.io/bip39/#spanishitaliano:
mnemonica: abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco abaco angelo
Bip 39 Seed: cbda07ec2ff567c93b1777de30b468da16768d053d2fc1b9f206b10106bfa0744bfa469554ec40ead097f9ede9b77192562ce16ef89290b33de8971befe9053f
inglese:
mnemonica: abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon art
Bip 39 Seed: 408b285c123836004f4b8842c89324c1f01382450c0d439af345ba7fc49acf705489c6fc77dbd4e3dc1dd8cc6bc9f043db8ada1e243c4a0eafb290d399480840
spagnolo:
mnemonica: ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ábaco ancla
Bip 39 Seed: 1e0de8aa97db3c7988f692d9c6151968be89debdbd71b1e34cab15d15ec10eed33412891129e1274fb84624565fd835f7e56df22a997439fca3da05c9c82a156
Quindi direi proprio che la funzione PBKDF2 fa l'hash della mnemonica intesa come stringa di parole, non fa direttamente l'hash delle 'posizioni' (cioè dell'entropia iniziale). I risultati, partendo dalla stessa entropia ma utilizzando diversi dizionari, sono pertanto diversi.* *EDIT 1: nell'esempio che ho fatto, questi sono i primi 3 indirizzi btc rispettivamente derivati (bip 44) dai 3 seed per le 3 lingue: italiano: 1Ad4nEriiHEHUDseZ2yVfUGS7fBZb1xkF5 -> https://www.blockchain.com/explorer/addresses/btc/1Ad4nEriiHEHUDseZ2yVfUGS7fBZb1xkF5inglese : 1KBdbBJRVYffWHWWZ1moECfdVBSEnDpLHi -> https://www.blockchain.com/explorer/addresses/btc/1KBdbBJRVYffWHWWZ1moECfdVBSEnDpLHispagnolo: 1EisMpzAj64HgFErbCoetANcZj4pQWoDxo -> https://www.blockchain.com/explorer/addresses/btc/1EisMpzAj64HgFErbCoetANcZj4pQWoDxocome si può vedere dai link, solo nel caso dell'indirizzo 'inglese' è presente un'attività passata, non è così invece per quello 'italiano' e per quello 'spagnolo'. ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- **l'ultima parola dipende da un checksum aggiunto alla fine (sha256 dei bit dell'entropia, perciò l'ultima parola non è uguale alle altre e non puoi sceglierla nemmeno a caso; nell'esempio di sopra "angelo / art / ancla" corrispondono tutte e 3 alla posizione 103 dei rispettivi dizionari). https://github.com/bitcoin/bips/blob/master/bip-0039/italian.txthttps://github.com/bitcoin/bips/blob/master/bip-0039/english.txthttps://github.com/bitcoin/bips/blob/master/bip-0039/spanish.txt**EDIT 2: visto che si ritagliano 11 bit dall'entropia iniziale per ogni parola, mentre per l'ultima parola si utilizzano solo 3 bit di entropia + 8 bit di cheksum, ogni volta che si prova a costruire una entropia 'artificiale' di soli 11 bit (tipo 00011100010 x 23 + 000) per costruire una sequenza di 24 termini utilizzando un'unica parola, c'è esattamente 1 sola possibilità su 256 (2^8) che anche l'ultima parola sia uguale alle precedenti; quindi è probabile che esistano alcune parole nella lista di 2048 parole che consentono di generare una sequenza costituita solo da quella parola (ultima parola compresa). ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
|
|
|
could you add mod n after mult?
i'm intresting to see the benchmark.
in your example we have only multiply without mod n
My mul function has mod too. // compute a * b = (low. high)
#define MultiplyWordsLoHi(low, high, a, b) asm ( "mulx %2, %0, %1;" : "=r"(low), "=r"(high) : "gr" (a), "d" (b) : "cc");
#define AccAdd4WordsBy4_wc(a0, a1, a2, a3, b0, b1, b2) asm ("addq %4, %0; adcx %5, %1; adcx %6, %2; adcq $0, %3;" : "+r"(a0), "+r"(a1), "+r"(a2), "+r"(a3) : "r"(b0), "r"(b1), "r"(b2) : "cc");
// (a0, a1, a2, a3) = (a0, a1, a2, a3) + (b0, b1, b2, 0) without carry
#define MulAcc(c, a0, a1, a, b) asm ("mulx %3, %3, %4; addq %3, %1; adcq %4, %2; adcq $0, %0;" : "+r"(c), "+r"(a0), "+r"(a1), "=a"(a), "=d"(b) : "a"(a), "d"(b) : "cc");
#define MulAcc_11(a0, a1, c0, a, b) asm ("mulx %3, %0, %1; addq %2, %0; adcq $0, %1;" : "+r"(a0), "+r"(a1): "r"(c0), "r"(a), "d"(b) : "cc");
// compute u*v mod p
inline void
mul(uint64_t *r, uint64_t *u, uint64_t *v) {
uint64_t u0 = u[0];
uint64_t u1 = u[1];
uint64_t u2 = u[2];
uint64_t u3 = u[3];
uint64_t v0 = v[0];
uint64_t v1 = v[1];
uint64_t v2 = v[2];
uint64_t v3 = v[3];
uint64_t r0, r1, r2, r3, r4, r5, r6, r7;
uint64_t z1, z2, z3, z4, z5, z6, z7, z8, z44, z66;
z2 = z3 = z4 = z5 = z6 = z7 = z8 = r1 = r2 = r3 = r4 = r5 = r6 = r7 = 0;
MultiplyWordsLoHi(r0, z1, u0, v0) //x1 --> r0 ok
MultiplyWordsLoHi(z2, z3, u1, v0)
MultiplyWordsLoHi(z4, z5, u2, v0)
MultiplyWordsLoHi(z6, z7, u3, v0)
AccAdd4WordsBy4_wc(z2, z4, z6, z7, z1, z3, z5)
MulAcc_11(r1, z1, z2, u0, v1) //x1 --> r1 ok
MultiplyWordsLoHi(z2, z3, u1, v1)
MultiplyWordsLoHi(z44, z5, u2, v1)
MultiplyWordsLoHi(z66, z8, u3, v1)
AccAdd4WordsBy4_wc(z1, z3, z5, z8, z4, z6, z7)
AccAdd4WordsBy4_wc(z2, z44, z66, z8, z1, z3, z5)
MulAcc_11(r2, z1, z2, u0, v2) //x1 --> r2 ok
MultiplyWordsLoHi(z2, z3, u1, v2)
MultiplyWordsLoHi(z4, z5, u2, v2)
MultiplyWordsLoHi(z6, z7, u3, v2)
AccAdd4WordsBy4_wc(z1, z3, z5, z7, z44, z66, z8)
AccAdd4WordsBy4_wc(z2, z4, z6, z7, z1, z3, z5)
MulAcc_11(r3, z1, z2, u0, v3) //x1 --> r3 ok
MultiplyWordsLoHi(r4, z3, u1, v3)
MultiplyWordsLoHi(r5, z5, u2, v3)
MultiplyWordsLoHi(r6, r7, u3, v3)
AccAdd4WordsBy4_wc(z1, z3, z5, r7, z4, z6, z7)
AccAdd4WordsBy4_wc(r4, r5, r6, r7, z1, z3, z5) //r4, r5, r6, r7 ok
//Reduction, mod 2^256 - 0x1000003d1
uint64_t p = 0x1000003d1;
MulAcc_11(z1, z2, r0, r4, p)
MultiplyWordsLoHi(z3, z4, r5, p)
MultiplyWordsLoHi(z5, z6, r6, p)
MultiplyWordsLoHi(z7, z8, r7, p)
//MulAcc_11(z1, z2, r0, r4, p)
AccAdd4WordsBy4_wc(z2, z4, z6, z8, r1, r2, r3)
uint64_t c = 0;
AccAdd4WordsBy4_wc(z3, z5, z7, z8, z2, z4, z6)
MulAcc(c, z1, z3, p, z8)
r[0] = z1;
r[1] = z3;
if(c == 1){
asm (
"addq $1, %0; adcq $0, %1; \n"
: "=r" (z5), "=r" (z7)
: : "cc");
}
r[2] = z5;
r[3] = z7;
}
EDIT: With 1 000 000 000 iterations: mul without mod: real 0m5,771s user 0m5,770s sys 0m0,000s mul with mod: real 0m8,438s user 0m8,434s sys 0m0,004s |
|
|
|
I have done implement parts of secp256k1 in pure asm
I would like to inform that performance is fucking fast (for me):
100 000 000 performs modulo n on secp256k1 vals:
ubuntu@ubuntu2004:~/Downloads/ma$ nasm -f elf64 main.asm
ubuntu@ubuntu2004:~/Downloads/ma$ ld -s -o main main.o
ubuntu@ubuntu2004:~/Downloads/ma$ time ./main
real 0m4.856s
user 0m4.850s
sys 0m0.005s
ubuntu@ubuntu2004:~/Downloads/ma$
Can you explain what kind of numbers are those 100 Million inputs. What is your hardware and against what other implementation are you comparing your results? so: test was performed on: Intel Core i5-1240P - without multithreading - on just one core. Power set up on balance (not maximum performance) test has been done on: xor rcx,rcx _loop: x*x mod n so first multiply x by x ( x is value Point of generator Secp256k1 ( i mean the x value of G(x,y)) then mod n so 256 bit *256 bit value then mod n inc rcx cmp rcx,100 000 000 jne _loop I tried a similar test with my mul function: int main(){
uint64_t x[4] = {0x59f2815b16f81798, 0x029bfcdb2dce28d9, 0x55a06295ce870b07, 0x79be667ef9dcbbac};
uint64_t a[4] = {0x59f2815b16f81798, 0x029bfcdb2dce28d9, 0x55a06295ce870b07, 0x79be667ef9dcbbac};
uint64_t* ptrx = &x[0];
uint64_t* ptra = &a[0];
uint32_t i;
for(i=0; i < 100000000; i++){
mul(ptrx,ptra,ptrx); //a*x -> x
}
}
12th Gen Intel(R) Core(TM) i7-12700H - without multithreading - on just one core. Power set up on balance (not maximum performance) $ gcc -O2 main.c $ time ./a.out real 0m0,886s user 0m0,882s sys 0m0,005s |
|
|
|
It is not clear to me to what this 1 inversion would be applied to. At a first glance, I only see the (x2 - x1) being inverted, but it's not clear how you'd do the inversion last, or only once, because x1 && x2 will usually not both be constant.
Of course you have to get many different inversions, 1/(x2-x1), 1/(x2'-x1') and so on, but you can get these values by computing only one inversion for the entire group. The idea is: imagine you need 1/a and 1/b you don't want to compute 2 inversions, because inversion is a very expensive operation. Then: 1) compute a*b -> 1 multiplication 2) compute 1/(a*b) -> 1 inversion, you invert only a*b 3) compute 1((a*b) * b = 1/a -> 1 multiplication 4) compute 1/(a*b) * a = 1/b -> 1 multiplication now you got 2 inversions (1/a and 1/b) computing only 3 multiplications and 1 'real' inversion. If you have more than 2 elements, for example a,b,c,d,e 1) compute a*b -> 1 mul (you have to store this result) 2) compute (a*b)*c -> 1 mul (you have to store this result) 3) compute (a*b*c)*d -> 1 mul (you have to store this result) 4) compute (a*b*c*d)*e -> 1mul (you have to store this result) 5) compute 1/(a*b*c*d*e) -> 1 inv --> about 1 mul for each element + 1 inversion -> (n-1)mul + 1 inv 6) compute 1/(a*b*c*d*e) * (a*b*c*d) = 1/e -> 1 mul 7) compute 1/(a*b*c*d*e) * e = 1/(a*b*c*d) -> 1 mul 8 ) compute 1/(a*b*c*d) * (a*b*c) = 1/d -> 1 mul 9) compute 1/(a*b*c*d) * d = 1/(a*b*c) -> 1 mul 10) compute 1/(a*b*c) * (a*b) = 1/c -> 1 mul 11) compute 1/(a*b*c) * c = 1/(a*b) -> 1 mul 12) compute 1/(a*b) * (a) = 1/b -> 1 mul 13) compute 1/(a*b) * (b) = 1/a -> 1 mul -> 2*(n-2) + 2 = 2*(n-1) mul If you do the same with a very long batch, you need then 3*(n-1) mul + only 1 real inversion, in this way you minimize the impact of the real inversion. On average you can consider then 3 mul for each element to invert. ------------------------------------------------------------------------------------------------------------------------------------------------------- The function that implements this idea in Vanitysearch is 'ModInv' : https://github.com/JeanLucPons/VanitySearch/blob/master/IntGroup.cpp/#L35first n-1 mul -> https://github.com/JeanLucPons/VanitySearch/blob/master/IntGroup.cpp/#L42-L44the only one real inversion -> https://github.com/JeanLucPons/VanitySearch/blob/master/IntGroup.cpp/#L48second and third n-1 mul -> https://github.com/JeanLucPons/VanitySearch/blob/master/IntGroup.cpp/#L50-L54that function belongs to the class IntGroup: https://github.com/JeanLucPons/VanitySearch/blob/master/IntGroup.h#L24This trick works only if you know many 'x1' and 'x2' before starting the computation. |
|
|
|
|
Show Posts
