🇮🇹 "Presentazione di Ofelimos: un protocollo di consenso proof-of-useful-work"

[lordwotton]

Traduzione italiana di “Introducing Ofelimos: a proof-of-useful-work consensus protocol - IOHK Blog”

Traduzione italiana a cura di Lordwotton di RIOT Stake Pools. Se apprezzi queste traduzioni, per favore valuta di supportare il mio lavoro delegando i tuoi ada a RIOT entra nel nostro gruppo Telegram

---

Presentazione di Ofelimos: un protocollo di consenso proof-of-useful-work

La ricerca dello IOG introduce un nuovo protocollo di consenso sicuro e dimostrabile per ridurre al minimo lo spreco di energia delle blockchain proof-of-work.

La minimizzazione del costo energetico e dell’impronta di carbonio della proof of work (PoW) è uno degli argomenti più discussi nello spazio crittografico. La sostituzione della primitiva PoW nel protocollo longest-chain di Nakamoto con una prova di lavoro utile (PoUW) è stata a lungo teorizzata come una soluzione ideale sotto molti punti di vista ma, fino ad oggi, il concetto non ha trovato una realizzazione convincente e sicura.

Oggi, in occasione della principale conferenza internazionale di crittologia, Crypto, Input Output Global, Inc (IOG) presenta Ofelimos, un nuovo protocollo blockchain basato su PoUW il cui meccanismo di consenso realizza contemporaneamente un risolutore di problemi di ottimizzazione decentralizzato. Il meccanismo di consenso utilizza il lavoro per risolvere problemi computazionali di interesse pratico per mantenere la blockchain.

Proof of work (prova di lavoro) contro proof of useful work (prova di lavoro utile)

I protocolli blockchain basati su PoW sfruttano il lavoro svolto dai partecipanti al protocollo, chiamati minatori. Il PoW garantisce la sicurezza del libro mastro incoraggiando i minatori a competere nella risoluzione di problemi computazionali per essere idonei a produrre un nuovo blocco. Questo lavoro computazionale mantiene la sicurezza del protocollo, ma richiede un uso significativo di energia e risorse. Al momento in cui scriviamo, Bitcoin ha un dispendio energetico annualizzato pari a quello di molti Paesi medio-piccoli.

La prova del lavoro utile affronta il problema dell’efficienza energetica riutilizzando lo sforzo computazionale richiesto per mantenere la sicurezza del protocollo per risolvere problemi complessi del mondo reale, come l’ottimizzazione della logistica aziendale o la programmazione di eventi, ad esempio.

Una delle sfide di PoUW consiste nel risolvere il seguente dilemma: se i problemi da risolvere sono veramente utili (provenienti dal mondo reale), l’attaccante può indirizzare il sistema a porre istanze di problemi facilmente risolvibili (o già risolti dall’attaccante). Ciò farebbe leva sulle risorse dell’attaccante per produrre più blocchi rispetto a un partecipante onesto con la stessa quantità di risorse, riducendo così la sicurezza della blockchain. D’altra parte, ridurre al minimo la capacità dell’attaccante di sfruttare la propria produzione di blocchi può richiedere la presentazione di istanze problematiche casuali, rendendo così inutili i calcoli del sistema nella pratica.

Ofelimos risolve questo dilemma con un’analisi formale della sicurezza e dell’utilità.

Panoramica di Ofelimos

I clienti pubblicano i problemi da risolvere e le ricompense da pagare ai minatori che hanno avuto successo. Proprio come in PoW, i minatori lavorano su questi problemi per partecipare a una lotteria che decide l’idoneità alla creazione di blocchi.

In PoW puro, questa lotteria consiste tipicamente nel ripetere l’hashing di una sfida (insieme a un contatore) rispetto a un determinato valore target. La lotteria viene vinta se il valore di hash è inferiore al valore target. Si noti che in PoW puro, una singola interrogazione è veloce mentre la probabilità di raggiungere l’obiettivo è molto piccola.

Per diverse ragioni, in PoUW è anche consigliabile mantenere una singola query (relativamente) veloce, il che minimizza la probabilità che più blocchi vengano pubblicati simultaneamente, ad esempio. D’altra parte, le istanze del problema del cliente dovrebbero essere non banali da risolvere, in modo da rendere interessante l’esternalizzazione del calcolo. Per PoUW, è quindi naturale puntare a classi di calcoli complessi nel loro insieme, ma divisibili in piccoli passi “uniformi”. Ogni passo dovrebbe richiedere la stessa quantità di lavoro (in previsione) e corrispondere a una singola query di PoW puro.

La ricerca locale stocastica (SLS) è una classe ovvia di tali calcoli. Gli algoritmi SLS vengono applicati a problemi di ottimizzazione per i quali non sono noti algoritmi deterministici efficienti. Piuttosto, SLS esegue una passeggiata casuale nello spazio delle soluzioni cercando di ottimizzare gradualmente la soluzione utilizzando alcune euristiche. Poiché ogni passo di esplorazione nella camminata casuale è un’istanza diversa dello stesso calcolo, SLS è un candidato eccellente per PoUW in base ai requisiti di cui sopra. Inoltre, SLS ha un’elevata rilevanza pratica con applicazioni nell’economia reale in settori quali la pianificazione logistica, la programmazione di eventi, ecc.

Una trasformazione graduale da PoW a PoUW

I minatori raccolgono e risolvono le istanze dei problemi dei clienti pubblicate sulla blockchain. Gli aggiornamenti dei problemi vengono continuamente memorizzati nella blockchain fino a quando non si verifica un criterio di terminazione, ad esempio dopo un numero fisso di passi di esplorazione o se è stata trovata una soluzione appropriata.

Ricostruiamo ora come trasformare il PoW puro in PoUW in questo contesto.

1. Nel PoW puro, un minatore deve estendere la sua catena più lunga con un nuovo blocco, eseguendo ripetutamente l’hashing del nuovo blocco rispetto a un determinato obiettivo (variando un contatore incluso nel blocco). Come primo passo, sostituiamo l’hashing ripetitivo con il calcolo ripetuto del passo di esplorazione SLS M su uno stato di esplorazione precedente s memorizzato sulla catena, dove il blocco determina il seme casuale per il passo di esplorazione. Si veda la Figura 1 (lato destro): Uno stato di esplorazione precedente s viene esteso dal passo di esplorazione randomizzato M utilizzando il seme risultante dall’hashing del blocco insieme allo stato s, ottenendo un nuovo stato di esplorazione (possibilmente migliore) s’. Questo processo viene ripetuto finché non viene soddisfatta una condizione non ancora specificata, che consente al miner di pubblicare il blocco. Durante questo processo, il minatore tiene traccia del miglior stato sbest che è stato trovato durante questo processo ripetitivo.

Figura 1: Hashing contro un obiettivo T (PoW, sinistra). Ripetizione del passo di esplorazione M (PoUW, a destra).

2. Ora fissiamo la condizione di successo mancante “?”. Per ottenere buone proprietà stocastiche che non siano influenzate dal calcolo concreto, la ricerca di un blocco è disaccoppiata dalla qualità dello stato calcolato s’, aggiungendo, dopo il passo di esplorazione, un “post-hash” al passo di esplorazione (riutilizzando il seme iniziale) - si veda la Figura 2 - e il blocco è idoneo alla pubblicazione se questo valore di hash è inferiore a un certo target T3. Oltre alla soluzione attualmente migliore sbest, questo introduce un nuovo stato sT che deve essere pubblicato con il blocco, lo stato che porta l’hash al di sotto di T3, per dimostrare l’idoneità alla pubblicazione del blocco. Si noti che solo sbest serve come aggiornamento dello stato (per essere ulteriormente esplorato dai minatori), mentre sT serve solo come testimonianza dell’idoneità a pubblicare il blocco.

Figura 2: randomizzazione dell’idoneità a pubblicare il blocco

3. Considerando che M è più difficile da calcolare di H e che non tutte le istanze di M possono richiedere la stessa quantità di lavoro, l’avversario potrebbe cercare semi che gli permettano di accelerare il calcolo di M rispetto a un minatore onesto, ottenendo così un vantaggio nel produrre blocchi più velocemente e degradando la sicurezza del sistema. Attenuiamo questo tipo di grinding richiedendo che l’hash iniziale sia inferiore a un obiettivo T1. Ad esempio, prima di eseguire la fase di esplorazione M, il minatore deve trovare un valore di hash basso variando il contatore di blocchi secondo le linee del PoW puro. Si veda la Figura 3. Concretamente, T1 è scelto in modo tale che il lavoro previsto per trovare un valore di hash inferiore all’obiettivo T1 costi almeno quanto la complessità temporale del caso peggiore del calcolo di M - facendo in modo che il grinding per un’istanza facile sia costoso quanto il calcolo di un’istanza “scomoda” di M. Una tripletta (Bctr, sbest, sT) che soddisfa le condizioni di cui sopra costituisce quindi un PoUW.

Figura 3: Difesa dal grinding tramite pre-hashing contro l’obiettivo T1

4. A differenza del PoW puro, non possiamo permetterci che i nodi verifichino i PoUW ripetendo il calcolo M del minatore, poiché ciò implicherebbe un’enorme quantità di calcolo replicato e quindi ridurrebbe drasticamente la frazione di calcolo veramente utile nel sistema. Per evitare ciò, quando “trova” un blocco pubblicabile, il minatore è tenuto a creare un argomento succinto non interattivo (SNARG) per dimostrare tale successo, con il vantaggio che la complessità della verifica diventa indipendente dalla complessità di calcolo di M. Inoltre, viene dimostrato il corretto calcolo della soluzione migliore sbest. Si veda la Figura 4.

5. Per trarre vantaggio dal mining concorrente distribuito, l’istanza SLS è parallelizzata (ad esempio, mantenendo percorsi di esplorazione multipli) poiché, altrimenti, tutti i minatori esplorerebbero simultaneamente lo stesso stato, introducendo molte fasi di esplorazione (essenzialmente) ridondanti. Si noti che, per ragioni di sicurezza, la produzione di blocchi in PoW standard “Nakamoto” è lenta e che gli aggiornamenti di stato sono legati ai blocchi. D’altra parte, gli aggiornamenti di stato dovrebbero procedere velocemente per evitare che i minatori esplorino stati “obsoleti”. Introduciamo quindi due tipi di blocchi: i blocchi di classificazione “difficili da trovare”, con la stessa funzione del consenso Nakamoto, e i blocchi di input “facili da trovare”, che funzionano come transazioni a cui i blocchi di classificazione fanno eventualmente riferimento. In questo modo, la soluzione migliore di un minatore può essere diffusa in tempi relativamente brevi, mantenendo così tutti i minatori aggiornati. In particolare, ciò si ottiene valutando prima l’hash finale rispetto a un obiettivo “facile” T3. Se è inferiore, si qualifica come blocco pubblicabile, ma solo se l’obiettivo è inferiore a un obiettivo “più difficile” T2, il blocco si qualifica come blocco di classifica “rilevante per il consenso”, altrimenti viene definito come blocco di input. Si veda la Figura 5.

Figura 5: Un post-hash inferiore a T2 qualifica il blocco come blocco di classificazione. Un post-hash tra T2 e T3 qualifica il blocco come blocco di input.

Proprietà del protocollo

Un’analisi approfondita della sicurezza e dell’utilità del protocollo esula dagli scopi di questo articolo. Può comunque essere utile ribadire alcune intuizioni sul perché il protocollo è sicuro e concludere esaminando l’efficienza del protocollo.

Sicurezza della blockchain:

• Rettifica: l’avversario non ha alcun vantaggio nella rettifica di istanze di M facili da calcolare. Ciò si ottiene adattando la soglia di pre-hashing T1 in modo tale che calcolare M su qualsiasi istanza sia al massimo altrettanto difficile che trovare un nuovo pre-hash inferiore a T1 (in previsione).
• Resistenza al vantaggio avversario: Il vantaggio dell’avversario nel calcolare il PoUW più velocemente delle parti oneste è limitato. Ciò si ottiene disaccoppiando il successo del blocco dal calcolo effettivo e effettuando il pre-hash al di sotto dell’obiettivo T1. In particolare, seguendo il modello standard di [GKL14, PSS16] e assumendo che l’avversario non abbia alcun vantaggio nel calcolare M più velocemente delle parti oneste, il protocollo tollera che un avversario controlli qualsiasi minoranza di potenza di calcolo dedicata alla rete, come fa Bitcoin. Al contrario, anche se l’avversario dovesse essere in grado di calcolare M a costo zero su ogni istanza, il protocollo tollera comunque che un avversario controlli fino a un terzo di tutte le risorse computazionali, poiché queste opererebbero comunque a un costo “dimezzato” a causa del pre-hashing contro T1.
• Difficoltà variabile: Nei protocolli di consenso PoW/PoUW, la difficoltà di trovare un blocco deve essere continuamente adattata al livello di potenza di calcolo attualmente dedicato al sistema. In Ofelimos questo si ottiene facilmente adattando l’obiettivo T2 per il (singolo) post-hash eseguito dopo la fase di esplorazione - che si qualifica per la pubblicazione di un blocco di classificazione.

Efficienza:

• Aggiornamenti frequenti: La separazione tra blocchi di classificazione e blocchi di input garantisce una rapida diffusione degli aggiornamenti di stato.
• Utilità: Per utilità intendiamo il rapporto tra il lavoro computazionale complessivo speso per il problema SLS (si tratta di una semplificazione: una definizione più accurata e un’analisi più approfondita sono disponibili in questo documento). Le principali fonti di lavoro “inutile” nel sistema sono il pre-hashing ripetitivo contro T1 e il calcolo dello SNARG. Si noti che:

• il post-hashing viene eseguito solo una volta per ogni invocazione di M e, rispetto alla complessità di M, può essere trascurato per ragioni pratiche.

• l’SNARG deve essere calcolato solo rispetto a due delle tante invocazioni di M, quella che produce sT (che implica il successo del blocco) e sbest (la soluzione migliore). L’overhead causato dal calcolo degli SNARG può quindi essere minimizzato abbassando la soglia T3 che determina il successo del blocco, in un compromesso con aggiornamenti di stato più lenti.

L’utilità dipende dalle caratteristiche di M. Se il tempo di esecuzione di M è sufficientemente concentrato, la durezza del pre-hash può essere impostata in modo da essere vicina alla complessità media di M. Considerando le osservazioni di cui sopra, l’utilità di circa ½ si ottiene quando il minatore spende circa la metà del suo tempo a calcolare M. Molti problemi SLS classici sembrano rientrare in questa categoria. Tuttavia, se M non è “ben educato”, l’utilità può essere prossima allo zero. La scelta degli algoritmi SLS concreti e delle loro fasi di esplorazione M è quindi cruciale per ottenere PoUW con un’utilità ragionevole.

Conclusione

Ofelimos è solo un primo passo verso una PoUW provabilmente sicura e utile. Mentre il lavoro attuale fornisce facilmente una sicurezza dimostrabile per livelli di corruzione elevati, sono ancora necessarie ulteriori ricerche sul lato algoritmico per fornire classi adeguate di problemi di ottimizzazione per i quali sia possibile dimostrare un’elevata utilità.

Il progetto “Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work” è stato pubblicato per la prima volta nell’ottobre 2021.

Vorrei ringraziare Matthias Fitzi per il suo contributo e il suo supporto nella preparazione di questo blog post.