Mining di bitcoin su un Computer di bordo delle missioni Apollo

Qualcuno di voi si è mai chiesto come sarebbe minare bitcoin utilizzando uno dei computer di bordo delle missioni Apollo?

Alcuni ragazzi hanno avuto il coraggio di provarci, ripristinandone uno e implementando l’algoritmo di hashing per il mining di Bitcoin. L’Apollo Guidance Computer è un computer a 15 bit e l’algoritmo in questione è stato implementando in Assembly.

Apollo Guidance Computer: un pezzo di ingegneria

L’Apollo Guidance Computer è stato sviluppato negli anni ’60. A bordo della navicella Apollo, questi computer fornivano funzionalità di guida, navigazione e controllo di motori. Era l’era dei computer che spaziavano dalla grandezza di un frigorifero a quelle di un’intera stanza, ma l’AGC era abbastanza piccolo da poter volare nello spazio.

Per la sua realizzazione, sono stati spinti i confini dell’ingegneria del software sotto la guida di Margaret Hamilton. Grazie a lei, aveva a disposizione un sistema operativo in real time all’avanguardia, con supporto a lavori prioritari multipli e al rilevamento e gestione dei guasti.

Gran parte del software era scritto in linguaggio assembly, ma l’AGC possedeva anche un interprete progettato per gli algoritmi di navigazione. L’interprete in questione implementava una macchina virtuale che forniva aritmetica vettoriale e matriciale insieme a trigonometria e numeri con precisione doppia e tripla.

Il processore dell’Apollo Guidance Computer

Questo calcolatore è stato sviluppato diversi anni prima dello sviluppo dei primi microprocessori. Quindi il suo processore è stato realizzato in maniera abbastanza particolare: vennero impiegate, infatti, 5600 porte NOR per l’implementazione di Flip-Flop e logica combinatoria varia.

Fu uno dei primissimi ad utilizzare circuiti integrati. Ogni circuito integrato conteneva due porte NOR. Il computer era composto da 24 moduli, ognuno dei quali conteneva 120 circuiti integrati. Uno o più di questi moduli andava a formare le unità funzionali del compuer. Un esempio era l’Arithmetic Logic Unit, implementata tramite 4 moduli, ognuno dei quali implementava 4 bit del processore.

L’architettura era molto insolita rispetto agli standard moderni. Le word erano, infatti, di soli 15 bit (più uno di parità), questo perchè allora i computer spesso avevano le dimensioni delle word che si adattavano all’applicazione che dovevano far girare, e non necessariamente una potenza di 2, come in questo caso.

L’AGC aveva di RAM solo 2K word, insieme a 36K word di ROM.

L’algoritmo SHA-256 utilizzato da Bitcoin

Per chi non lo sapesse, il Bitcoin è il leader delle criptovalute digitali. La caratteristica principale del Bitcoin è che non esiste una macchina centrale o un’autorità che tenga traccia delle monete: i dati sono distribuiti su migliaia di macchine in giro per il web.

Per garantire che tutti siano d’accordo su quali transazioni sono valide, Bitcoin utilizza un processo chiamato mining: circa ogni 10 minuti viene generato un blocco di transazioni.

Ma non è semplice: il mining di Bitcoin è infatti progettato in modo tale da richiedere un enorme sforzo computazionale per estrarre un blocco, in modo che nessuno possa prendere il controllo del processo di mining.

I miner in giro per il mondo competono l’uno contro l’altro, generando trilioni e trilioni di hash casuali fino a quando qualcuno non trova uno dei tanti fortunati che inizia con 18 zeri. Un hash con questa forma corrisponde ad un blocco minato con successo, e una volta trovato, tutti passano al blocco successivo.

L’idea è che ottenere 18 zeri casualmente in fila è estremamente improbabile, quindi ci vuole un numero enorme di tentativi prima che qualcuno riesca. È un po’ come una lotteria, dove i minatori continuano a provare fino a quando qualcuno vince. Peccato che trovare un hash valido è meno probabile che trovare uno specifico granello di sabbia tra tutta la sabbia presente sulla Terra.

Ogni volta che un blocco viene estratto con successo, vengono creati nuovi Bitcoin. Come dati indicativi, si può dire che ogni miner che riesce a minare con successo un blocco riceve 12.5 Bitcoin, corrispondenti a ben $140.000. La possibilità, bassa, di ricevere $140.000 ogni 10 minuti motiva i minatori a costruire datacenter pieni di hardware specializzato utilizzando enormi quantitativi di energia elettrica.

Per il Bitcoin, questi hash vengono generati tramite un algoritmo di hashing conosciuto come SHA-256. Questo algoritmo è pensato per essere facile da implementare, e lo si può eseguire anche a mano, ma quasi impossibile da ricalcolare all’indietro. Tant’è che se volete calcolarvi manualmente un hash con le caratteristiche ideali per avere un blocco adatto al bitcoin, dovreste provare trilioni di hash diversi prima di trovare quello valido.

L’implementazione di SHA-256 sull’AGC

I ragazzi che hanno provato a realizzare questa strabiliante impresa hanno caricato il codice su GitHub, reperibile a questo indirizzo. Se siete curiosi potete provarlo da voi, tramite il Virtual AGC Project.

La stesura del codice non è stata per niente banale. L’instruction set disponibile sull’AGC è veramente scarno, e manca di molte features disponibili nelle architetture moderne. Non è nemmeno disponibile uno Stack, quindi le chiamate a procedure sono un po’ rognose da effettuare dovendo mantenere da qualche parte i vari indirizzi di ritorno.

Inoltre, l’algoritmo di hashing scelto prevede l’utilizzo di numberi senza segno a 32 bit. L’AGC però aveva word da 15 bit con segno basato sul complemento a 1. Da qui si deduce come le operazioni di somma non siano del tutto banali, e i ragazzi hanno scelto di dividere ogni numero da 32 bit in 2 chunk da 14 bit (non 15 perchè c’era bisogno di avere numeri senza segno) e un chunk da 4 bit.

Un altro problema è stata la poca disponibilità di memoria. L’AGC, come la maggior parte dei computer del suo periodo, utilizzava memorie con nucleo magnetico, immagazzinando ogni singolo bit in un minuscolo anello di ferrite magnetizzato.

Poiché questo sistema era abbastanza voluminoso, l’AGC aveva solo 2K word. Lo schema di indirizzamento della memoria non era poi così banale: è possibile infatti accedere a 256 parole tramite un meccanismo di bank switching. Il problema è che l’algoritmo SHA-256 utilizza otto valori hash da 32 bit, una tabella da 64 word e 8 word di valori intermedi. In totale quindi sono 240 word, lasciando circa 16 parole per tutto il resto (valori temporanei, indirizzi di ritorno di subroutine, contatori di loop, puntatori, ecc.).

Il risultato finale

Lo sviluppatore è quindi riuscito a superare tutti questi problemi, incontrando diverse difficoltà. L’algoritmo così implementato richiede un totale di 10.3 secondi per il calcolo di un singolo hash.

Attualmente, la rete Bitcoin esegue circa 65 quintilioni di hash al secondo. Considerando che a questa velocità ogni blocco viene generato in media ogni 10 minuti, l’AGC impiegherebbe in media 4 × 10 ^ 23 secondi per trovare un blocco.

Non male, se non si considera che l’universo ha un’età di soli è solo 4.3 × 10 ^ 17 secondi. Ciò equivale a dire che l’AGC impiegherebbe circa un milione di volte l’età dell’universo per estrarre con successo un blocco.

Da notare che l’hash visualizzato a video è uno valido per la generazione di un blocco per Bitcoin. Peccato che è solo una dimostrazione: è stato usato come input un blocco che era stato estratto con successo in passato, in particolare il blocco #286819, che non vale quindi nulla.