No, non c'entra nulla. Del soft fork (segwit) si parla in un altro thread -->https://bitcointalk.org/index.php?topic=1665779.msg16725510#msg16725510

1.6 Mega (after segwit) * 144 * 365 = 80 Giga per year

80 * 4 + 90 = 410 GB    by the end of 2020

It will be happening in 12 years' time.

Ho preso alcune cose dai link indicati e poi ho rielaborato, se hai capito lo scopo è stato raggiunto. D'altronde per deformazione professionale tendo a rielaborare i concetti, semplificarli e spiegarli a qualcuno per capire meglio anch'io (così fanno di solito quelli che fanno il mio mestiere )





Bisogna scendere proprio nei dettagli dell'implementazione del BIP 141/142 e nel come è fatta una transazione.

Ogni transazione contiene due componenti principali.
La prima sblocca i bitcoin che erano vincolati in transazioni precedenti (UTXO : Unspent Transaction Output), e per fare questo si usano dei dati detti "input".  Gli input includono uno o più script, cioè delle istruzioni su come sbloccare gli UTXO, questi script si chiamano "scriptSig".
L'altra parte della transazione consiste in uno o più nuovi "lucchetti" detti output, i quali ribloccano la stessa quantità (o meno) di bitcoin; gli output includono script detti "scriptPubKeys".

Le istruzioni per sbloccare i bitcoin lavorano su una firma e sulla chiave pubblica relativi all'indirizzo mittente,
le istruzioni sul blocco dei bitcoin (i lucchetti) vincolano i bitcoin all'indirizzo del destinatario.
In questo modo i bitcoin effettivamente si muovono dagli input agli output all'interno di una singola transazione (vengono svincolati e rivincolati allo stesso tempo), e così "passano" istantaneamente da una transazione all'altra (e da un address all'altro, cioè da un vincolo a un altro).

Che differenza c'è tra una transazione normale e una transazione segwit?

In sostanza si operano  due cambiamenti nella transazione.

1) la firma (con la chiave pubblica del mittente) viene spostata dal campo "scriptSig" a un nuovo campo "witness" (che è sempre un campo della transazione!); questo vuol dire "segregated witness", firma separata (segregata in un campo della transazione che non verrà incluso nell'hash della transazione, cioè non impatterà sulla txid)

2) il testo del campo "scriptPubKey" viene modificato in modo che abbia due significati diversi per un vecchio nodo e per un nuovo nodo (ecco il soft fork!); NB: in quel campo rimane sempre la condizione che blocca i bitcoin (i bitcoin vengono bloccati con l'indirizzo del ricevente, ovvero i fondi vengono vincolati alla chiave pubblica che genera l'indirizzo del ricevente);
in questo caso la condizione di blocco diventa per il vecchio nodo un "non vincolo", cioè un generico "ANYONE CAN SPEND" (un output solo apparentemente non vincolato a nessun indirizzo e quindi spendibile da chiunque) poichè il vecchio nodo non legge i nuovi indirizzi/script "pay-to-witness-public-key-hash" P2WPKH (per ulteriori dettagli vedi in fondo al post ***), mentre per i nuovi nodi che conoscono i nuovi indirizzi e il nuovo modo di interpretare quei dati si tratta sempre di una transazione che manda dei bitcoin a un indirizzo preciso





I vecchi client non vedono proprio il nuovo campo "witness" (essi scaricano i blocchi depurati dal campo "witness"), i nuovi sì. Quando si fa l'hash della transazione però per creare il suo ID (txid), il campo "witness" non viene incluso (questo fatto sistema la questione della malleabilità).

Quindi nella blockchain quel campo (la firma) in realtà c'è (anche se un nodo a cui non interessa fare una validazione completa può fare il pruning di quel campo), sicuramente non c'è però (non viene considerata) nell'hash della transazione (txid).
Quest'ultimo fatto di per sè renderebbe la parte "witness" l'unica parte della blockchain potenzialmente modificabile, in quanto svincolata dalla txid e di conseguenza dall'hash del blocco che a sua volta dipende dall'hash delle transazioni che contiene; per ovviare a questo fatto viene costruito un altro Merkle Tree e di conseguenza ricavato un Merkle Root relativo solo ai campi "witness" di tutte le transazioni del blocco, e quest'ultimo dato viene infine inserito nel campo di input della coinbase del blocco (in questo modo cambia l'ID solo di quella transazione ma questo è sufficiente per modificare l'hash del blocco,  di conseguenza la presenza di ogni campo witness del blocco viene fissata per sempre anche nell'hash del blocco stesso, ma ripeto non nell'hash della transazione.)

In sostanza le firme vengono collegate (dal punto di vista della verifica della consistenza della blockchain) per sempre al blocco tramite il suo hash, mentre rimangono scollegate dalla txid della transazione a cui appartengono, e questo porta diversi vantaggi dal punto di vista tecnico (ad esempio finora per ricostruire il database degli UTXO bisogna identificare gli input delle transazioni facendo riferimento a una txid che dipende a sua volta dalla firma, ma la firma dovrebbe servire solo ad autorizzare una transazione, non a identificarla!  Con le transazioni witness la firma manterrà solo la sua funzione specifica e non creerà ulteriore lavoro inutile per identificare gli input).



Quale sarà allora la dimensione di ogni blocco?

Esso potrà contenere delle transazioni purchè sia rispettata questa disequazione:

lo spazio occupato dalla parte "standard" delle transazioni (senza contare il campo witness) + 1/4 dello spazio occupato dal campo witness delle stesse transazioni <= 1 Mega


In questo modo quindi la dimensione del blocco può (e lo farà) superare tranquillamente 1 Mega per i nuovi client (si stima possa arrivare a 1,5/2 Mega effettivi?) mentre i vecchi nodi scaricheranno sempre meno di 1 Mega (poichè essi non vedono il "witness").
Il fatto di considerare solo 1/4 del peso del witness (cioè delle firme) mira a favorire l'uso del sigwit, pochè esso porta molti vantaggi (ad esempio il fatto che la ID di una transazione non dipenda più da "scriptSig" rende più facile ricostruire l'insieme degli UTXO mentre finora bisognava scaricare anche le firme solo per ricostruire le txid; l'elenco completo dei vari vantaggi si trova qui https://bitcoincore.org/en/2016/01/26/segwit-benefits/)


In futuro quindi potremo finalmente liberarci di giga di firme non più necessarie (solo quelle nel campo witness però! non quelle tradizionali che sono legate alle txid e quindi sono necessarie per ricostruire il database degli UTXO), come afferma lo stesso Pieter Wuille, il promotore di questo soft fork:



fonti:
https://diyhpl.us/wiki/transcripts/scalingbitcoin/hong-kong/segregated-witness-and-its-impact-on-scalability/
https://bitcoinmagazine.com/articles/segregated-witness-part-how-a-clever-hack-could-significantly-increase-bitcoin-s-potential-1450553618
https://bitcoinmagazine.com/articles/segregated-witness-part-why-you-should-care-about-a-nitty-gritty-technical-trick-1450827675
https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#Examples
https://github.com/bitcoin/bips/blob/master/bip-0142.mediawiki



***

Vorrei fare qualche considerazione sui numeri grandi relativi al bitcoin. Una delle cose che sconcerta maggiormente chi si avvicina a questo mondo e cerca di capirlo è il fatto di dover ragionare con numeri il cui ordine di grandezza è assolutamente fuori dall'ordinario. Lavoriamo qui nel "finitamente" grande.


La dimensione dello spazio delle chiavi possibili (2^256) e la potenza (in hash/s) necessaria a minare i blocchi sono solo due esempi estremamente significativi di cosa significa lavorare con grandezze che sembrano infinite (ma non lo sono) e di probabilità che vengono approssimate a 0 (ma non sono 0). Non è affatto scontata la capacità di stimare in modo adeguato queste quantità (e di conseguenza capire realmente di che tipo di sicurezza si parla in relazione alle transazioni e alla blockchain, per esempio);ancor più difficile diventa quindi fare discorsi quantitativi ragionevoli legati alle prospettive di crescita della rete e del valore del bitcoin (non parlerò qui del prezzo del bitcoin, ci sono già troppi thread al riguardo).  


EDIT: facciamo un esempio pratico: in questo articolo http://motherboard.vice.com/read/bitcoin-could-consume-as-much-electricity-as-denmark-by-2020 si prevede, nello scenario più pessimistico, che il consumo elettrico mondiale del mining diventerà nel 2020 equivalente a quello di una piccola nazione come la Danimarca  


Proviamo allora a fare un semplice collegamento tra potenza e numero di chiavi, giusto per chiarire il concetto.

Al momento la potenza computazionale complessiva di tutti i miner del mondo è di circa 2 exahash/sec, cioè vengono effettuate circa 2*(10^18) operazioni al secondo (in sostanza hash dei blocchi per minarli), ovvero 2^61 operazioni al secondo.

Supponendo per semplicità che queste operazioni siano equiparabili (non lo sono) a quelle necessarie per craccare una chiave privata, in questo momento una chiave di 61 bit potrebbe essere individuata in 1 secondo con un attacco mondiale brute force, mentre per una chiave di 80 bit sarebbero necessari 2^19 secondi, ovvero soli 6 giorni.

Per una chiave di 128 bit invece bisognerebbe impiegare 2^48 * 6 giorni, ovvero 4600 miliardi di anni.

Se la potenza computazionale dovesse però continuare a raddoppiare ogni anno (cosa alquanto improbabile), ogni anno il tempo necessario per craccare una chiave dimezzerebbe.
Tra 20 anni ci vorrebbero 2^28 * 6 giorni = 4,4 milioni di anni per craccare la chiave di 128 bit  e solo mezzo secondo per craccare una chiave da 80 bit.
Tra 48 anni teoricamente sarebbero necessari soli 6 giorni per craccare una chiave di 128 bit.

A parte le ovvie considerazioni sull'impossibilità di una crescita esponenziale sostenuta per così tanto tempo, c'è un limite teorico alla crescita della potenza computazionale della rete? Sì.
E' vero che all'aumentare della potenza complessiva aumenta anche la sicurezza? Solo fino a un certo punto.

Esiste una difficoltà massima prevista dall'algoritmo che fa il retarget della difficoltà ogni 2016 blocchi:


Infatti il target minimo (cioè quello che si raggiunge con la difficoltà massima, vedi https://en.bitcoin.it/wiki/Target) che si può avere è la stringa di 256 bit **:

                                                    00000.....001

(cioè per minare un blocco bisogna modificarlo in modo che il suo hash non superi una stringa di tutti 0 più un 1 finale).
Se vogliamo che in media la rete raggiunga questo risultato 1 volta ogni 10 minuti, la potenza complessiva dovrebbe essere  di 2^256/10 minuti, ovvero circa 2^247 hash/secondo. In pratica si dovrebbe raggiungere una potenza complessiva che permetta di fare un brute force attack di una chiave di 256 bit in 10 minuti, ma a quel punto il sistema sarebbe già divenuto insicuro da un pezzo!


**Per curiosità aggiungo che non si può ottenere come hash di un blocco una stringa di 256 zeri poichè questo hash è riservato per identificare il blocco (virtuale) che precede il blocco 0 --> https://blockchain.info/block/000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f


Questo mio ragionamento vuole solo evidenziare come al momento lavoriamo con un sistema dagli ampi margini di crescita, ma che lo spazio di manovra apparentemente infinito non lo è affatto, ci sono dei limiti intrinseci che apparentemente sembrano non esserci perchè troppo lontani al momento ma in realtà di cui bisogna tener conto per poter fare dei ragionamenti che abbiano una base.  

Provo un po' a semplificare riassumendo quello che ho capito io.

Premessa:  fork significa innanzitutto "divisione a causa del cambio di una regola nel protocollo bitcoin ", la questione è capire di che tipo di divisione si tratta

La differenza tra hard fork e soft fork si può sintetizzare nella seguente espressione:
I soft fork rendono non valide situazioni valide (o non standard) in precedenza, gli hard fork rendono valide cose che prima non erano valide.


Esempio:

soft fork:
se diminuissimo la dimensione dei blocchi a mezzo mega, questo sarebbe un soft fork, in quanto non sarebbe più possibile minare un blocco da 1 mega come si faceva in precedenza;  in questo caso si passerebbe da una regola più permissiva (blocchi fino a 1 mega) a una meno permissiva (blocchi fino a 1/2 mega) --> si rendono non valide situazioni che prima erano consentite (ad esempio la generazione di un blocco da 750 kb)

NB: si parla di soft fork poichè la divisione si crea soltanto a livello software, divisione tra chi ha software aggiornato e chi invece mantiene il software pre-fork (ma non avviene alcuna divisione della blockchain)

                                      soft fork : vecchi client - nuovi client

chi mantiene un client vecchio (pre-soft fork, tipo Core 0.12.0 invece di Core 0.13.1 ad esempio) non si accorge nemmeno del cambio di regole; infatti se il vecchio client supporta e riconosce blocchi fino a 1 mega mentre i miner minano blocchi solo fino a 1/2 mega, questi nuovi blocchi (nuovi nel senso minati con le nuove regole) sono perfettamente validi anche agli occhi dei nuovi client, poichè se accetti un blocco fino a 1 mega a maggior ragione consideri valido un blocco da 200kb; se con il vecchio client provi a minare dei nuovi blocchi, quando ti capita di minare un blocco minore di 1/2 mega questo verrà accettato dal resto della rete, quando mini un blocco da 750 kb inspiegabilmente la rete lo rifiuterà

chi ha un client aggiornato semplicemente evita di minare un blocco maggiore di 1/2 mega, e considera non valido un blocco da 750kb se gli arriva poichè conosce esplicitamente la nuova regola (ovviamente continua a considerare sempre validi tutti i blocchi pre-fork, le regole non si cambiano a posteriori).


                                              
                                     hard fork:  la blockchain si divide in 2 rami diversi
 
se aumentassimo invece la dimensione dei blocchi a due mega, questo sarebbe un hard fork, in quanto avremmo una situazione fino ad ora non valida (blocchi fino a due mega) che d'ora in poi diventa consentita.

Qual è il problema dell'hard fork? A differenza del soft fork, dove uno può decidere di mantenere il vecchio client senza apprezzabili controindicazioni, con un hard fork non è più possibile mantenere il vecchio client senza conseguenze, poichè questo ha delle regole di funzionamento più restrittive rispetto alle nuove; dopo il primo blocco minato maggiore di 1 mega, si creerebbe una suddivisione della blockchain (hard fork), in quanto i nuovi client e i vecchi client lavorerebbero con regole incompatibili. Di fatto si creano due rami, due set di regole diverse cioè due monete diverse da una.  

L'idea di base del soft fork invece è quella di nascondere le modifiche ai vecchi client, in modo che questi vecchi programmi siano in grado di leggere ancora i nuovi dati (blocchi) senza neanche accorgersi delle modifiche;


Azzardo un paragone informatico:

BitCoin Core   --  Word

blocchi        --  documenti

se si immagina Bitcoin Core come fosse Word, un hard fork consiste nel creare una nuova versione del programma che realizza documenti in un formato illeggibile dalla versione precedente (di fatto si hanno due tipi di documenti, ad  esempio .doc e .docx <---hard fork);
un soft fork invece consiste nel creare una nuova versione del programma che realizza documenti leggibili anche dalla versione precedente (quindi stesso formato) ma con qualche caratteristica/tag in più che può essere sfruttata a dovere solo dal nuovo software ma non pregiudica l'utilizzo da parte di quello vecchio. In questo caso non ci sono due formati di documenti (no hard fork), ma semplicemente due versioni di programma che creano e leggono lo stesso formato di documento (soft fork).


                                     il soft fork di Segregated Witness (segwit)

Cosa succederà (se succederà) con il soft fork di segwit? I blocchi saranno sempre di 1 mega* (*solo per le vecchie versioni di Core per retrocompatibilità) ma si usa un "trucco" per inserire delle transazioni apparentemente "alleggerite" (con una parte di byte - la firma "witness" - "segregata" che viene allocata "altrove", cioè in un nuovo campo separato della transazione). Si tratta di un trucco poichè i vecchi client non capiranno esattamente che c'è solo una parte della transazione e non tutta (loro non scaricano quel campo nuovo, il nuovo "tag" delle transazioni witness) e soprattutto poichè la reale dimensione dei blocchi aumenterà per i nuovi client, anche se essa verrà calcolata in un nuovo modo; questo fatto ha contribuito a suscitare molte polemiche, si tratta infatti di un soft fork che si propone di realizzare qualcosa che dovrebbe poter essere fatto in teoria solo con un hard fork, e cioè rendere valide situazioni - come i blocchi più grandi - in precedenza non permesse. Si riesce a fare ciò poichè una parte delle transazioni - le firme segregate - non viene considerata più come il resto delle transazioni, e il loro peso in byte viene scontato del 100% per i vecchi client, che neanche le scaricano, e del 75% per i nuovi client, per i quali alla fine il conto virtuale rimane di 1 mega a blocco, ma si tratta appunto solo di un calcolo virtuale.  


Più tecnicamente il nuovo tipo di transazioni appariranno, almeno ai vecchi nodi, transazioni del tipo "ANYONE CAN SPEND"; infatti i vecchi nodi non riusciranno più a interpretare i nuovi comandi che vincolano i bitcoin nel campo scriptPubKeys e di conseguenza questi btc appariranno a loro non vincolati a nessun indirizzo; questo fatto si rende necessario poichè questi vecchi nodi dovranno accettare e considerare valide anche le nuove transazioni (presenti nei blocchi futuri della blockchain) che poi spenderanno questi bitcoin, e poichè essi non saranno più in grado di vedere le firme segregate in un altro campo, l'unico modo affinchè possano considerare regolare (anche se non standard) una transazione che spenda questi bitcoin consiste nel non considerarli vincolati affatto (cioè nel considerarli già svincolati in partenza quindi):


Per essere pignoli cosa succederà a chi non aggiornerà il suo wallet/client? Quando questi dovesse ricevere una transazione  del nuovo tipo (diciamo "alleggerita") il suo vecchio client la etichetterà come 'non standard' (le transazioni*** possono essere valide, non valide, non standard; non standard significa: non capisco bene cosa sia anche se non viola nessuna regola da me conosciuta). Poichè le transazioni non standard non possono essere create nè inoltrate, di fatto il suo client non la accetterà quando la vedrà per la prima volta nello stato di transazione non confermata, mentre quando la rivedrà all'interno di un blocco minato le accetterà (così funzionano le transazioni non standard, non si facilita il loro uso ma neanche si rifiutano in toto).

Quindi chi non aggiorna non vedrà subito (dal suo client) la transazione non confermata ma dovrà
aspettare che questa abbia almento una conferma (sia inclusa in un blocco) per vederla apparire nel suo programma.

fonti:
https://bitcoincore.org/en/2016/01/26/segwit-benefits/
https://bitcoinmagazine.com/articles/segregated-witness-officially-introduced-with-release-of-bitcoin-core-1477611260


***


EDIT: se vi serve solo sapere come comportarvi in questo soft fork e come/quando aggiornare (sia che siate un miner, un full node, o un semplice utente) queste sono le istruzioni: https://bitcoincore.org/en/2016/10/27/segwit-upgrade-guide/

Quindi dal 15 novembre partono periodi di 2016 blocchi ciascuno, all'interno di ogni periodo si fa ogni volta una sorta di votazione, se in una di queste votazioni si raggiunge il 95% allora si attiva il soft fork.

Visto che c'è tempo massimo un anno, ci saranno all'incirca 52 settiamane / 2 = 26 periodi diversi di voto oppure la finestra dei 2016 blocchi è "mobile"?

Se al 15 novembre 2017 non si è attivato il soft fork, segwit non potrà più essere riproposto in nessuna forma più avanti? Cioè ogni singola proposta è solo una tantum?

Allora, riguardando bene:
nella scelta dei parametri a' e b' necessari per passare da un elemento

                                   Y = aP + bQ  al successivo elemento Y'= a'P + b'Q

si usa effettivamente una specie di quadrato (ogni elemento Y viene raddoppiato in Y+Y=2Y , almeno se si trova in una certa parte dello spazio, il che equivale ad elevare alla seconda). La scelta dei parametri (a',b')  è ovviamente deterministica ma soprattutto dipende solo dai valori (a,b) dell'elemento precedente.

Quindi si simula solo la classica passeggiata casuale nello spazio di tutti gli elementi della curva.  

Si può quindi non tenere traccia di tutti gli elementi Y=aP+bQ generati poichè si sa che a un certo punto si deve entrare in un "sottogruppo" ciclico della curva ellittica (la parte chiusa della lettera rho, anche se non è propriamente un sottogruppo nel senso matematico del termine; non appena si genera una collisione gli elementi per forza iniziano a ripetersi a causa del modo univoco con cui viene generato un elemento a partire dal precedente).
L'entrata nel ciclo (o la sua "chiusura", se si immagina visivamente la lettera rho greca) è causata quindi da una prima collisione (vedi paradosso dei compleanni, che avviene in media dopo rad(n) passi), prima collisione però (e qui c'è il punto importante) che non è necessario che sia rilevata (quindi non c'è necessità di memorizzare enormi montagne di dati!). A partire da quella prima collisione si genera quindi (a causa del metodo deterministico) sempre la stessa sequenza di elementi (che formano appunto un ciclo); da notare che il ciclo è una sottosequenza del percorso effettuato per arrivare alla prima collisione, quindi il ciclo stesso non è costituito da più di rad(n) punti.

Per rilevare una qualsiasi ripetizione tra due elementi (percorrendo il ciclo si deve tornare ogni volta sugli stessi elementi, non serve individuare il primo elemento che si ripete, quello che ha chiuso il ciclo!) è sufficiente usare un buffer con pochissimi dati in memoria; i dati vengono aggiornati di tanto in tanto mediante un algoritmo che non impatta in maniera sostanziale sul lavoro computazionale complessivo fino a che non si realizza una collisione anche all'interno del buffer di memoria (collisione che deve arrivare per forza quando si è dentro un ciclo, si registra così una collisione utilizzabile dal punto di vista pratico per ricavare la chiave privata).

L'algoritmo di rilevazione della collisione all'interno del buffer nel caso migliore trova la collisione appena si è entrati nel ciclo, nel caso peggiore impiega un numero di iterazioni ulteriori pari alla lunghezza del ciclo stesso

L'algoritmo è il seguente (tratto da https://maths-people.anu.edu.au/~brent/pd/rpb231.pdf):

Per trovare l'inverso di un numero mod n si può usare l'algoritmo di Euclide che si usa di solito per trovare il MCD tra 2 numeri (se poi dal punto di vista dell'implementazione nel calcolatore ci sono dei modi più efficienti non lo so).

Ad esempio:   n = 31  
Qual è l'inverso di 7 modulo 31?

Il problema può essere riscritto così:   7 * s = 1  mod 31  

Ora 7 e 31 sono coprimi, e si può quindi dimostrare che esistono s e t tali che 7s + 31t = 1 (mod 31)

Se riesco a trovare i 2 numeri "s" e "t"  tali che 7s + 31t = 1 (mod 31), allora ho finito, infatti in tal caso

7s = 1 (mod 31) e  s è l'inverso di 7.


L'algoritmo euclideo  (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) permette, dati due numeri
 a e b, di trovare il loro MCD mediante una combinazione lineare:

a*s + b*t = MCD(a,b)  (e nel nostro caso MCD(a,b) = 1 poichè sicuramente ogni numero è coprimo con n che è primo!)

Questo è lo pseudocodice:

 
      

Hai ragione, Baby Giants - Pollard - Pollard Roh ... quante distinzioni!

E dire che avevo linkato anche il file http://www.mat.uniroma2.it/~geo2/pollardro.pdf con la spiegazione  

EDIT: @gbianchi sei sicuro che i moduli quadratici non si usino solo nella fattorizzazione dei numeri primi ma non nel problema del logaritmo discreto?

Io ho guardato qui a pag.7

https://www.google.it/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiLt--qg4DQAhUJcRQKHfaHDToQFgghMAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D8EF3BF1FB7E6DA875FF3D8F4904BC0AD%3Fdoi%3D10.1.1.114.5683%26rep%3Drep1%26type%3Dpdf&usg=AFQjCNHbmP8spzOswu9cJWbePXZZmMBspA

e viene descritto il metodo così come lo ho spiegato io, senza quadrati... Anche in questo caso si forma la rho greca.

Se pensi a un brute force attack allora hai ragione tu. Ma nel caso di ECDSA non avrebbe senso, ci sono 2^256 chiavi!

Si tratta di affrontare il problema del logaritmo discreto, per risolvere il quale ci sono algoritmi che hanno bisogno in media di 2^128 operazioni, quindi in tal caso ha ragione gbianchi, serve anche un po' di memoria per lo stoccaggio dati (ma neanche così tanta se l'algoritmo è buono).

Il problema del logaritmo dicreto è: dati P e Q, trova x tale che

                                                          xP = Q

Nel caso di bitcoin, x è la chiave privata, P è il punto G (fissato) della curva ellittica secp256k1, Q la chiave pubblica.
In sostanza, per quante volte devo sommare G con se stesso per ottenere la chiave privata Q?

G + G + .... + G = Q     dove x è il numero di addendi del primo membro (la chiave privata).

Ora l'algoritmo di Pollard (inizialmente studiato per la fattorizzazione dei numeri primi http://www.ams.org/journals/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf  e poi adattato al caso del logaritmo discreto di ECDSA) consiste in questo caso nel trovare 2 coppie di numeri (A,B) e (a,b) tali che:

                                                  aP+bQ=AP+BQ

Se trovi queste due coppie di valori numerici allora è fatta, hai trovato anche x (la chiave privata).

Infatti:
                      aP+bQ   =  AP+BQ
                      aP+bxP  =  AP+BxP
                      (a+bx)P = (A+Bx)P
                      (a-A)P    = (B-b)xP

-->                 (a-A) = (B-b)x              mod n (dove n è l'ordine della curva)
                         x = (a-A)(B-b)^-1      mod n

Tradotto:  bisogna impostare una sequenza (a,b) di numeri pseudo-casuali, si otterrà una sequenza di punti della forma aP+bQ;  mi fermo quando trovo un'altra coppia di (a,b) che produce un punto già calcolato in precedenza, cioè quando nella mia lista ci sono 2 volte lo stesso punto: è questa la collisione trovata (di qui l'applicazione del paradosso del compleanno http://www.mat.uniroma2.it/~geo2/pollardro.pdf), che non è tra due chiavi della stessa chiave pubblica (-> indirizzo bitcoin).

Chiamo le due coppie di numeri che producono lo stesso punto (a,b) e (A,B) e con il ragionamento precedente ricavo così la chiave privata x che costituisce il collegamento tra P e Q (cioè tra G e la chiave pubblica).

EDIT:

Da qui (http://residentrf.ucoz.ru/_ld/0/34_Digital_Signatu.pdf pag. 27) capisco che in realtà l'algoritmo Pollard Rho non occupa troppo spazio/memoria:

Come è possibile minarsi il blocco da soli? O si possiede l'hardware adatto (cioè si è un miner), ma praticamente quasi nessuno soddisfa questa condizione!
La seconda opzione è quella di affidarsi a un servizio terzo, ma allora la questione della sicurezza e soprattutto del meccanismo trustless di funzionamento del protocollo bitcoin va a farsi benedire...

Hai PM.

EDIT: transazione conclusa positivamente, ottimo prezzo!

Una domanda e una considerazione:

1) ma allora qual è il senso dell'articolo "Ultimate physical limits to computation", se in realtà sarà fisicamente possibile effettuare quel tipo di calcolo? Il limite fisico è solo sulla dimensione dello stoccaggio dei dati ma non sulla potenza di calcolo?

2) come notava già 3 anni Vitalik Buterin --> https://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150 c'è anche il problema del tempo di conferma delle transazioni.
In sostanza, poichè nel momento in cui decidi di spendere i tuoi bitcoin sei costretto a esporre la tua chiave pubblica e la tua transazione prima di essere confermata rimane per un po' di tempo sospesa (da pochi secondi a delle ore), l'unica protezione che rimane in quel momento è quella data da ECDSA, non da RIPEMD160. Ovviamente si fa affidamento sul fatto che nessuno, a maggior ragione in un lasso di tempo così esiguo, sia in grado di violare questa protezione.

Quindi c'è un proprio un limite fisico anche ben calcolato ...
Ma quando si parla invece di "qubit" e di computer quantici, valgono sempre gli stessi limiti? A me sembrava di aver capito che teoricamente dovrebbe essere possibile costruire dei computer quantici nel futuro che risolvano chiavi a 128 bit senza usare una quantità di energia del genere, ma potrei aver capito male io.

@Jack Liver

Grazie per il link.
In pratica la sicurezza dipenderebbe dal fatto che, insieme ai bit, si riduce parallelamente in maniera drastica anche la platea dei possibili attaccanti (allora la cosa ha un senso). Inoltre non avevo considerato il problema dello spazio di archiviazione dei dati, stavo pensando solo alla potenza computazionale necessaria.


@gbianchi :   mi sa che hai proprio centrato il punto. Ho trovato il seguente principio di crittografia:

Il principio di Kerckhoffs --> https://it.wikipedia.org/wiki/Principio_di_Kerckhoffs è esattamente opposto al principio che stavo seguendo io, detto principio della sicurezza mediante segretezza https://it.wikipedia.org/wiki/Sicurezza_tramite_segretezza

Secondo me però ci sono dei dati personali che non possono essere conosciuti da quasi nessun altro, quindi in questo caso la segretezza avrebbe un suo senso. Sicuramente l'esempio delle età non era dei migliori, forse qualcosa legato al dna?

Io in sostanza vorrei fondere un dato pubblico come la blockchain (accessibile a tutti) con un dato privato (e quindi segreto alla stragrande maggioranza dei possibili attaccanti del mondo), quindi vorrei lavorare con un algoritmo semiprivato/semipubblico, unendo (ammesso che sia possibile) i benefici dei due principi.

In pratica chi mi conosce magari può accedere facilmente al mio dna, ma non ha la potenza computazionale necessaria / le competenze per mettere in piedi un attacco decente, chi non mi conosce non può, nonostante possa essere bravissimo e avere ingenti risorse computazionali, accedere ai miei dati personali.

Poco fa è stato rilasciato Bitcoin Core 0.13.1.

Tra le note di rilascio ho trovato le seguenti:

Non sapevo che gli indirizzi P2SH avessero una sicurezza diversa da quella dei più tradizionali indirizzi P2PKH e soprattutto non immaginavo che questa sicurezza potesse essere così più bassa ("solo" 80 bit).
Allora l'anello debole della catena che protegge un indirizzo P2SH non sarebbe più ECDSA a questo punto, come si ritiene invece di solito.  Discorso da approfondire.

Da notare inoltre come venga ribadito che i 128 bit di sicurezza delle chiavi private relative a ECDSA sono in realtà solo una stima della sicurezza effettiva di ECDSA (la quale potrebbe essere anche minore).

O anche:

http://www.tariffando.it/amazon-offre-60e-coupon-tutti-clienti-prime/

Ma nella descrizione della procedura il codice fiscale non viene inserito dall'addetto nel terminale pos, quindi qualcosa non torna, a meno che la lettura del codice a barre non eviti semplicemente all'addetto di dover ridigitare "CODICE ACQUISTO --> Amazon" 

No, personalmente non ho mai acquistato buoni in contanti.

Qui però https://www.sisalpay.it/servizi/pagamenti/altri/amazon è descritta esplicitamente la procedura di acquisto,  e non si menziona affatto la presentazione di documenti:


Da qui
https://www.lottomaticaitalia.it/servizi/ricariche/pdf/dett_codici_acquisto_amazon.pdf
si vede il tipo di ricevuta/scontrino rilasciata presso una ricevitoria "LIS CARICA"; non sembra vi siano riportati dati personali, anche se appare un messaggio ambiguo


non capisco a cosa può servire lo scontrino precedente se i vari acquisti non sono collegati alla persona che acquista? 

Come ha consigliato HostFat, attenti a utilizzare solo le richieste italiane:

https://app.purse.io/earn#country=IT

poichè i buoni amazon italiani valgono solo per amazon italiano.

Anche se non usate buoni per l'acquisto, è consigliabile rimanere sulle offerte italiane per sfruttare tutti i vantaggi dello store italiano; a me è successo infatti di acquistare bitcoin su purse.io accettando un'offerta di solo il 2% superiore al prezzo di mercato del momento (24,95 euro per 0.04063725 BTC,  tasso "effettivo" €613.97 / BTC) , ma alla fine mi sono ritrovato a spendere 26,94 euro poichè la spedizione (l'ordine era su amazon spagnolo) non era coperta dal prime italiano. Quindi alla fine ho pagato il 12% di commissione, tipo un acquisto su BitBoat.

In generale dovete tener conto delle spese di spedizione, che spesso non sono incluse nelle offerte della lista "earn", che possono incidere sul tasso reale di acquisto, soprattutto per gli ordini di pochi euro.

Se inoltre non vi interessa l'anonimato assoluto e volete correre qualche rischio in più per risparmiare ulteriormente, anche su questo forum si trovano rivenditori di buoni amazon che praticano sconti dell'ordine del 10% (ovviamente il discorso ha senso se accettano anche euro, non solo btc). In questi casi uno potrebbe alla fine (almeno teoricamente) riuscire anche a comprare dei btc quasi sotto al prezzo di mercato.