(2^4) ^ 7 = 2^28 combinations, it is pretty simple to generate that number of addresses. But these keys are not consecutive, then you have to modify BitCrack or vanitygen. A Cpu is enough, 2^28 is a small number.

If you want I can give you a program that works like that:

generate_address file_input file_output

where file_input contains private key in hex format and file_output contains addresses in hex format.

I have to modify my program that generates only consecutive addresses.


What kind of speed do you need? It is enough Python or you need a C program?

First, you have to look only at the UTXO set, you don't care about addresses used in the past and now empties

Updated at block # 547944   30/10/2018

 output               # addresses                       Tot bitcoin
                                                                                          
P2PKH                        18.453.794                    10.541.332  
P2SH                            3.865.985                      4.906.667  
P2PK                                 38.678                      1.759.927      
P2WPKH                           62.643                          126.738  
P2WSH                             18.662                            11.812    
MULTISIG 1-1                        357                                    0.056
MULTISIG 1-2                 142.354                             23.24      
MULTISIG 1-3                 205.226                             17.85        

TOT                          22.787.699                       17.346.536


so we are talking about 20 million, not 300.



With bloom filter the searching time becomes the neglegible part. If you have a list of all addresses (not base58 encoded) in UTXO

addresses.hex

you can use the program I linked to get from that list a 512 MB bloom filter called funds_h160.blf (addresses with funds)

First you have to download the program (I assume you use Linux) and compile it:

you can download it from https://github.com/ryancdotorg/brainflayer/archive/master.zip and unzip or use the 'git' command:


then run it



To perform a search in the bloom filter, suppose you have a list of 1000 addresses generated from 1000 private keys to check against the bloom filter:


where the bloom_chk_hash160 function is defined here -> https://github.com/ryancdotorg/brainflayer/blob/master/bloom.h

You don't know
1) the private key
2) the address?

If you have to check each address you generate against the blockchain, you need a bloom filter like in this program https://github.com/ryancdotorg/brainflayer

2 180 000 000 addresses are not too many.  Besides you can save the time of the encode58.

Ringrazio per le "perle" ma non esageriamo.

Ovviamente sarebbe l'ideale riscrivere tutto in LaTeX, ma diventerebbe ai miei occhi tutto troppo professionale, alla fine mi va bene scrivere le cose man mano che mi vengono in mente senza dovermi preoccupare troppo della forma. Si tratta di spunti, voglio buttare giù delle idee che possono tornare utili a me e a chi legge, non voglio scrivere un trattato o qualcosa di livello accademico, certo sarebbe comodo se il forum permettesse di inserire formule matematiche, ma qui hanno pensato solo a come inserire pezzi di codice, pazienza.

Grazie per i link, in effetti sarebbe meglio, bisogna solo trovare tempo e voglia

Giant means giant, baby baby.

You have 2 possibilities:

1)
Baby-steps:  0, 1*G, 2*G, ..., (m-1)*G  //  Giant-steps:  P, P - m*G, P - 2*m*G, ...., P - (m-1)*(m)*G

or

2)
Baby-steps:  P, P - 1*G, P - 2*G, ...., P - (m-1)*G //  Giant-steps:  0, m*G,  2*m*G, ...., (m-1)*m*G


In either cases  you can find a key between 1 (P = 1G) and m^2 - 1 (P - (m-1)*G = (m-1)*m*G  -->  P = (m^2 - 1)*G)
You have two lists of m elements.

If you need a search space from k to k + m^2 - 1 (size of search = n = m^2),

in the case 1)  add k*G in the baby-steps list:  k*G, (k+1)*G, (k+2)*G,...., (k+m-1)*G or sub k*G from P in the giant-steps list
in the case 2)  add k*G in the giant-steps list:  k*G, (k+m)*G, (k+2*m)*G,...., (k+(m-1)*m)*G or sub k*G from P in the baby-steps list

baby: step of 1G
giant: step of mG (where m is sqrt(n))

How it works

imagine you have:

a) a partial private key d:
f461d7473a944648de9630a2062fc29f676fab0c6e9c344a472f70bef31dca17 (you lost the last digit, 7)

b) the public key P:
x : 4461130191898d8b22c00c474a5903a679afcf7988c2db3636223ab4ce7883e2
y:  50abf843d037afdb1a40ae565c8c72b7b29740282bd335a63d369e6eeced21a2

You lost the last hex digit, 7,  16 is then the search space size.
How can you retrieve the correct value?

Option:
 
1) brute force, there are max 16 tries to do:  from f461....dca10 to f461....dca1e, for each private key you compute the public key and compare the result with P.


2) baby-step-giant-step (--> http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/):

you create two lists, the first one (giant steps list) in a hash table stored in Ram and the second one (baby steps list) dynamic:

a) (giant steps list): each giant step is equal to the sqrt(space size), in our case sqrt(16) = 4, namely the distance between 2 elements is 4*G .  

Then we create the list:
k*G, (k+4)*G, (k+8)*G, (k+12)*G   where k is the first possible key to check (k = f461....dca10)

b) now we generate the baby-steps list (the distance beween 2 consecutive elements is 1*G) on fly, starting from

P  

and we check if it is equal to an element in the giant-steps list, if not try with

P - 1*G, P - 2*G and so on (P-3*G is the last element).

In our case, P - 3*G =  (k+4)*G

--> P = (k+7)*G  --> private key k+7


If you don't know the last 2 hex digits, the search space is 256 elements, then you need to create a list of 16 elements (baby-steps: k*G, (k+16)*G, (k+2*16)*G, ...,(k+15*16)*G) and the baby-steps list (P, P - 1*G, P - 2*G, ...., P - 15*G).

16 elements * 16 elements = 256 comparisons



A software (not mine) that works in this way: https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89

Parliamo un po' più a fondo di endomorfismi, vediamo da dove nascono i valori beta di cui ho parlato un paio di post sopra e cerchiamo così di entrare più a fondo nel mondo delle curve ellittiche (sempre privilegiando la nostra curva secp256k1).

ENDOMORFISMI

Una mappa f: E -> E si dice un ENDOMORFISMO (endomorfismo di E sul campo Fp) se

1) manda il punto all'infinito di E nel punto all'infinito di E

2) f(P) = (g(P),h(P)) per tutti i punti P di E, dove g e h sono funzioni razionali (rapporto tra 2 polinomi) i cui coefficienti sono nel campo Fp.

In pratica facendo una serie di operazioni - g - sul punto P (cioè sulla sua x e sulla sua y) si ottiene la x di un nuovo punto, il punto f(P), analogamente facendo un'altra serie di operazioni - h - sulle coordinate x e y di P si ottiene la y di f(P).

Questa mappa quindi consente di passare da un punto P della curva a un punto f(P) sempre della curva, facendo alcune operazioni particolari sulle x e y di P.

Un esempio semplice di mappa che soddisfa il requisito 2) ma non 1) è la mappa che prende P qualsiasi e aggiunge a P sempre lo stesso punto, chiamiamolo G.

f : P  -->  P+G  per ogni P di E

Questa mappa (una sorta di traslazione) è quella che viene usata in programmi tipo vanitygen per generare nella maniera più veloce possibile le chiavi pubbliche (tenendo traccia delle chiavi private, che vengono incrementate di 1 ad ogni iterazione).

Nell'ipotesi che P sia diverso da G e da O (punto all'infinito), questa mappa si compone delle seguenti due parti:

a) la x di f(P) = g(P) = ((yG - yP) / (xG -xP))^2 -xP -xG

b) la y di f(P) = h(P) = ((yG - yP) / (xG -xP)) * (xP - g(P)) - yP

ovvero la solita formule di addizione.

Però questa mappa manda O in O+G = G, e quindi non rispetta il primo criterio e non è un endomorfismo. Vedremo invece che la mappa:

f : P  --> k*P

che associa a ogni punto il suo prodotto per uno scalare k fissato è un endomorfismo.


Nel termine ENDOMORFISMO il prefisso ENDO significa INTERNO, il termine MORFISMO vuol dire che questa mappa rispetta la "forma" (struttura) algebrica di E, nel senso che sommare prima due punti in E e poi applicare la mappa f produce lo stesso risultato che applicare prima f ai due punti separatamente e poi sommare i risultati:

f(P1 + P2) = f(P1) + f(P2) per ogni P1, P2 in E.


Per fare un parallelo con un esempio più noto, la mappa

f : R -> R,  f(x) = ln(x)

si chiama OMOMORFISMO nel senso che traduce la struttura algebrica (operazione) della moltiplicazione in una struttura algebrica analoga, dello stesso tipo, cioè nella addizione:

ln(a*b) = ln(a) + ln(b)


In R se vogliamo costruire un ENDOMORFISMO che rispetti l'operazione di addizione possiamo farlo così:

f : R -> R   f(x) = k*x

k*(a+b) = k*a + k*b

(si noti il parallelismo con k*P delle curve ellittiche, dove k*(P1 + P2) = k*P1 + k*P2)

Nota: possono sembrare cose molto astratte, ma quanti sbagliano trattando la funzione x^2 o la funzione radice come fossero endomorfismi rispetto all'operazione di addizione!

(a + b)^2 = a^2 + b^2

radice (a + b) = radice(a) + radice(b)

mentre ovviamente x^2 e radice(x)  sono endomorfismi solo rispetto all'operazione di moltiplicazione.



Torniamo alle curve ellittiche.

Un endomorfismo f è una mappa da E a E che soddisfa certi requisiti, ovvero che manda punti di E in punti di E con l'unica avvertenza che il punto O va mandato nel punto O.

Si può verificare che un endomorfismo da E in E è sempre un omomorfismo di gruppo, ovvero che:

f(P1 + P2) = f(P1) + f(P2)

Esempi di endomorfismi da E in E

1) la moltiplicazione per uno scalare k fissato

la mappa f: P --> k*P è endomorfismo di E, è immediato verificare infatti che k*(P1 + P2) = k*P1 + k*P2

casi particolari della mappa appena vista si hanno per k = 1 (identità) e k = -1 (la mappa negazione, quella che associa ad ogni punto P il suo opposto -P, nel qual caso f è definita come (x,y) --> (x,-y) ).


2) la mappa f: (x,y) --> (beta*x, y)  dove beta è un elemento di ordine 3 di Fp (è una radice cubica di 1, questo si ha solo se p = 1 mod 3)

in quest'ultimo caso si ha quindi la possibilità di calcolare le coordinate di un nuovo punto in modo rapidissimo, con una sola moltiplicazione nel campo Fp. Se si applica 3 volte di seguito la mappa f appena descritta

P      -->   f(P) = P1  --> f(P1) = P2      --> f(P2) =  P

(x,y) --> (beta*x, y) --> (beta^2*x, y) --> (beta^3*x,y) = (x,y)

si vede che si torna sempre al punto dal quale si era partiti.  Quindi, ragionando senza le coordinate, si ha

P -> lambda * P -> lambda^2 * P -> lambda^3 * P = P   dove lambda è uno scalare di Zn

ovvero che lambda è un elemento di ordine 3 di Fn. Sottolineiamo che, quando si passa da un elemento P a un elemento P1 = f(P), si può sempre scrivere P1 come k*P, poichè ogni punto P diverso dal punto all'infinito genera ogni altro elemento di E, ovvero ogni punto P1 è multiplo di ogni altro punto P, per un opportuno fattore k.

Quindi di fatto la mappa 2) è un caso particolare della mappa 1), dove m = lambda e i calcoli sulle coordinate risultano particolarmente semplici (g(P) = beta*x, h(P) = y)


Piccola osservazione: sia p - 1 che n - 1 sono multipli di 3:



Come si fanno a calcolare gli elementi beta e lambda (rispettivamente elementi di ordine 3 di Zp e di Zn)?

Basta prendere un elemento a caso di Zp (Zn) ed elevarlo alla (p-1)/3 ((n-1/3)), si otterrà sicuramente un elemento di ordine 3, se non è uguale a 1 otterremo una delle due radici non banali dell'unità che stiamo cercando:





Facciamo un rapido controllo che la seguente mappa :

f:        P        --> lambda*P

         (x,y)   --> (beta*x, y)

sia verificata per P = G:

1) Only if you know the public key too (not the address).

2) baby-step-giant-step in this case (80 bits) would require more than 2^40 work, because you don't have enough Ram to store 2^40 public keys.


To retrieve the last 60 bits (bitcoin case) my program takes about 5 minutes (it run on a single cpu). It uses baby-step-giant-step algorithm and 32 GB.

If you know the public key (not the address) and the first ~ 180 bits of the private key, it is possible to retrieve the other 70 / 80 bits using smarter ways than brute force attack.

@fillippone : grazie per l'aiuto.

Adesso il discorso fila.

Ho provato a togliere temporaneamente tutte le persone della mia trust list e quindi ho aggiunto solo "l'utente" DefaultTrust (la cosiddetta DT1 una volta scelta direttamente da Theymos e ora scelta in modo più democratico **):


Depth 0

    DefaultTrust (1)
    arulbero (0)

Depth 1

    theymos (1)
    dooglus (1)
    gmaxwell (1)
    OgNasty (-1)
    SebastianJu (1)
    qwk (1)
    Vod (1)
    mprep (1)
    Cyrus (1)
    monkeynuts (1)
    Welsh (1)
    ibminer (1)
    TMAN (1)
    Lauda (1)
    ...


In DT0 c'è solo il mio nome (con 0 voti) e l'utente DefaultTrust (con 1 voto, il mio che sono la radice del depth). In sostanza è una lista personale con 1 solo utente (il mio nome non conta).

In DT1 quindi ci possono essere solo le persone presenti nella lista dell'utente DefaultTrust, ovvero la famosa DT1 approvata dal forum. E' per questo motivo infatti che la trust lista "personale"  dell'utente DefaultTrust si chiama DT1, perchè come lista si trova effettivamente al livello di depth1  e non di depth0 (dove invece è presente come singolo utente)


Da notare che i voti ottenibili (numeretto in nero) per ciascuno degli utenti della DT1 sono:

(1) : ad esempio theymos ha 1 voto perchè la maggioranza di DefaultTrust lo supporta (DefaultTrust quindi in questo caso si comporta come un normale utente che vota la persona presente nella propria lista).

(-1) : come succede ad esempio a OgNasty, in questo caso DefaultTrust rivela la sua natura ambigua di uno e molteplice, infatti il suo voto è il risultato di un voto a maggioranza che risulta negativo. Quando parlo di voto sottintendo il bilancio netto tra voti positivi e voti negativi. Dare un voto positivo ad A consiste nell'includere A nella propria trust list, dare un voto negativo ad A consiste nell'inserire ~A nella propria trust list; quindi con il termine "voto" non ci si riferisce ai feedback che invece concorrono a determinare i 3 numeri relativi al trust (il punteggio di trust dovrebbe essere lo scopo finale di tutto questo sistema di filtraggio dei feedback costruito mediante l'impostazione di liste personalizzate di utenti fidati nel rilasciare i feedback)


Il meccanismo del voto funziona in questo modo (se ho ben capito):

dato un livello n e il livello successivo n+1, gli utenti del livello n+1 sono gli utenti appartenenti alle liste degli utenti del livello n;

ogni utente del livello n dà un voto positivo (o negativo con il simbolo ~) a tutti gli utenti del livello n+1 presenti nella propria lista.

In questo modo se ad esempio ho 10 persone nella mia personale trust list (DT0), ogni singolo utente della DT1 non potrà avere un voto maggiore di (10), perchè non potrà essere incluso in più di 10 liste. Man mano che si procede con i livelli aumentano ovviamente il numero delle persone e quindi il numero delle liste (cioè dei voti possibili che ciascun utente può ottenere).  Ad ogni livello aggiunto si amplia la platea di votanti e di persone votate, con l'osservazione che quando subentrano ad esempio 50 nuove persone, queste rappresentano 50 potenziali voti in più per ogni utente a partire dal livello successivo.

Quindi se ho 3 livelli (DT0, DT1, DT2) ho anche 3 insiemi, ma ogni insieme è contenuto nel successivo? Non è detto, in quanto i nuovi voti potrebbero essere negativi quindi un utente DT1 potrebbe non essere incluso nella lista dei DT2 qualora il suo bilancio di voti diventasse negativo. Infatti nella mia DT2 trovo OgNasty (1), mentre nella mia DT3 trovo OgNasty (-1).

Di fatto il meccanismo del voto si articola in 2 passi:

a) un nome viene proposto al livello n+1 se compare in almeno una lista degli utenti del livello n

b) su questo nome viene fatto una votazione automatica (voti positivi - voti negativi) e il risultato determina se quel nome rimane o no in modo effettivo a quel livello; se ad esempo n + 1 = 2 e io ho impostato la depth proprio a 2, allora vuol dire che considero affidabili tutti i feedback rilasciati dagli utenti della mia DT0, DT1 e DT2. Un utente DT2 che riceva un voto complessivo negativo dagli utenti DT1 compare con il nome barrato, ad indicare che i feedback da lui rilasciati non incideranno sui trust degli utenti del forum che io visualizzo. Ma rimane la possibilità che riceva più voti ai livelli successivi e rientri quindi in una lista successiva, tipo DT3. Ma ricordando che di solito si tiene la depth a 1 o 2, la DT3 e la DT4 (l'ultimo livello possibile) spesso non contano.

Questo meccanismo prevede l'eccezione come si è già detto solo del caso DT1 =  DefaulTrust list (la DefaultTrust list concettualmente è diversa dal DefaultTrust user, che infatti si trova un livello sopra). In questo caso infatti, poichè il DefaultTrust user in depth0 è uno solo (non può stare insieme ad altri utenti), il suo voto per determinare gli utenti effettivi del livello successivo DT1 (1 o -1) diventa di fatto il risultato di una votazione interna allo stesso insieme di utenti.
Negli altri casi invece è il livello precedente che decide con il suo voto la composizione del livello successivo.


Nell'immagine qui sotto si vede la differenza nel modo di selezionare la DT1 prima (da Theymos) e ora dove persone con requisiti sufficienti forniscono la lista dei nomi su ciascuno dei quali l'utente DefaultTrust (la lista stessa) ha l'ultima parola: (1) o (-1).  

Da quello che ho capito il sistema attuale è dinamico in tempo reale per quanto riguardo l'autoselezione dei membri della lista, mentre la selezione della lista che precede questa autoselezione dovrebbe avvenire ogni tot giorni (ovviamente sempre mediante uno script automatico che controlla periodicamente chi soddisfa tutti i prerequisiti per poter accedere in DT1)

**

Quindi riassumendo:

in depth0 vedo solo le persone della mia personale trust list; tutte queste persone (eccetto me) hanno accanto come numeretto (1); poichè io non ho rilasciato loro nessun feedback, ne deduco che quel numero 1 significa che appartengono tutte alla lista generata da me medesimo che sono l'origine della depth (quindi i feedback non c'entrano). Questa lista si chiama dt1 o dt0?

in depth1 vedo le persone che sono nelle trust list delle persone presenti nella mia trust list; il numeretto accanto a ciascun nome indica in quante liste diverse questo nome è presente (quanti "voti" ha preso tra le persone della mia personale trust list)

in depth2 vedo le persone che sono nelle trust list delle persone presenti al punto precedente con i rispettivi voti e così via.

Se quei numeri (ma allora non è così) rappresentano il bilancio dei feedback rilasciati rispettivamente dagli utenti delle liste dt1 dt2 dt3, ed essendo queste liste uniche, non dovrebbero comparire gli stessi punteggi?

Sì, penso anch'io che sia così, a questo punto è l'unica spiegazione.

Questi valori sono gli unici valori "oggettivi" presenti nel forum, nel senso che mentre il punteggio di trust (il numerino verde) dell'utente A è diverso se visto da me (in quanto è giudicato dai feedback rilasciati dagli utenti della mia trust list) o se visto da te (se hai una trust list diversa dalla mia), quando invece guardiamo quel numeretto tra parentesi in nero dell'utente A vediamo entrambi lo stesso valore, in quanto stiamo guardando in quel caso al giudizio degli utenti della lista dt1 (in depth0) e della list dt2 (in depth1), che sono liste uniche appunto per tutto il forum.

EDIT: ho appena ricontrollato:

depth0:
  arulbero(0)
  fillippone(1)

depth1:
  arulbero(7)
  fillippone(2)

tu vedi la stessa cosa riguardo noi due?

Ok, ma se fosse così ogni username dovrebbe avere un solo numero vicino, nel mio caso ad esempio vedo a volte arulbero(1) e a volte arulbero(7) : perchè?

Forse in un caso vuol dire che c'è 1 solo utente dt1 che mi ha inserito nella sua trust list, mentre nel secondo caso ci sono 7 utenti dt2 che mi hanno incluso?

Linko un articolo un po' off topic: https://www.linkiesta.it/it/article/2019/01/18/la-disuguaglianza-sara-sempre-piu-una-questione-di-intelligenza/40784/

L'articolo analizza la distribuzione del QI (il quoziente d'intelligenza, distribuito come una gaussiana) in relazione all'aumento della complessità che si incontra nell'usare in modo proficuo le nuove tecnologie; questo fatto sta determinando una sempre maggiore disuguaglianza tra chi è in grado a livello cognitivo di muoversi in questi nuovi mondi sempre più complessi sfruttandone al massimo le potenzialità e chi invece si trova nella parte sinistra della gaussiana:


Leggendolo mi è venuto da pensare a bitcoin. Anche se l'articolo si riferisce in maniera evidente soprattutto alle professioni (laddove saper usare in modo proficuo le nuove tecnologie è fondamentale per reggere alla competizione del mercato) mi sembra che con il passare del tempo si stia ingrandendo la classe di persone che, anche al di fuori di un contesto lavorativo, non riesce a sfruttare appieno le novità tecnologiche, tipo bitcoin.

Ho riletto i post su questo punto ma non mi è chiaro il significato di quei numeri: cosa sono? Ho notato che la stessa persona se si trova sia in depth0 che in depth1 ha numeretti accanto diversi.

Grazie! Quindi il discorso che pesava anche il numero dei btc "rischiati" è precedente a quel post e non vale più?

Comunque adesso è molto più chiaro.

Non per fare il pignolo, ma dove vedi tu la spiegazione in dettaglio?
Io leggo: è il punteggio di Trust calcolato in base ai feedback positivi ricevuti, ok, ma come è calcolato?