Nelle criptovalute le transazioni sono collegate tra loro tramite hash. Questa relazione inalterabile conferisce all'insieme delle transazioni una struttura matematica naturale chiamata ordine parziale. In questo post, Wiliam Sanders spiega gli ordini parziali e come sono utili per IOTA.
I numeri reali, ℝ, hanno un ordine naturale indicato con ≤. Da bambini, abbiamo imparato che tutti i numeri, x,y,z, e la relazione ≤ soddisfano le seguenti condizioni:
Relazioni di questo tipo sono pervasive in matematica e sono così denominate: un ordine totale è una qualsiasi relazione ≤ che soddisfa queste proprietà. Un insieme con un ordine totale si chiama insieme totalmente ordinato.
Inoltre, ogni sottoinsieme di ℝ è totalmente ordinato, come i numeri naturali ℕ e l'intervallo [0,1]. Tuttavia, ci sono altri esempi più esotici di set totalmente ordinati. Per esempio, un'aula X di bambini è ordinata totalmente in base all'altezza, a condizione che non vi siano due bambini in X di altezza identica. In particolare, per i bambini x e y in X, possiamo dichiarare che x≤y se x è più basso di y. Infatti varie caratteristiche come l'età, il peso o le classi producono molti ordini totali diversi su X.
Tuttavia, non tutti gli ordini sono totali. Per esempio in ℝ² sia (a,b)≤(c,d) se a≤c e b≤d. Sebbene questa relazione soddisfi le Condizioni (1)-(3), ℝ² non è totalmente ordinata poiché, per esempio, gli elementi (2,3) e (3,2) sono incomparabili, perché a<c mentre b<d. Questo esempio motiva un diverso tipo di ordine.
Un ordine parziale è una relazione ≤ che soddisfa tutte le condizioni di cui sopra tranne la condizione 4, e quindi alcuni elementi possono essere incomparabili. Un poset (abbreviazione di insieme parzialmente ordinato) è un insieme con un ordine parziale. Per esempio ℝ² è un poset con la relazione di cui sopra.
Per un altro esempio, che X sia il seguente insieme di film: Star Wars Holiday Special, The Matrix, Shrek ed Il Padrino. Dico che x≤y se il film y è migliore del film x. Star Wars Holiday Special è spesso considerato uno dei peggiori film di tutti i tempi, mentre Il Padrino è considerato uno dei migliori.
Così, è chiaro che:
Tuttavia, a mio parere, The Matrix e Shrek sono incomparabili. Così X è un poset, ma non un insieme totalmente ordinato.
Ricordiamo che un DAG, o un grafo aciclico diretto, è un insieme di vertici collegati da frecce senza cicli, cioè ha una sequenza non banale di frecce.
x→x₁→x₂→ᐧᐧᐧ→xₙ→x
che inizia e finisce nello stesso punto. In questa sezione, spieghiamo la stretta relazione tra i DAG e i poset.
In primo luogo, possiamo ordinare parzialmente l'insieme dei vertici di qualsiasi DAG D. Per i vertici x,y in D, sia x≤y se c'è un percorso da x a y. Ricordiamo che un percorso da x a y è una sequenza di frecce:
x→x₁ →x₂ →ᐧᐧᐧ →xₙ →y
Lasciamo al lettore il compito di verificare che la relazione ≤ ordina parzialmente i vertici di D. Si noti che x≤y e y≤x se e solo se esiste un ciclo comprendente x e y. Quindi ≤ soddisfa la Condizione (2) se e solo se D è aciclico.
Al contrario, per un poset X, possiamo definire un DAG il cui vertice è X. Per ogni elemento x in X, tracciamo una freccia per ogni y in X che copre x. Un elemento y copre x se x<y ma non esiste z in X tale che x<z<y. Per esempio, nei numeri naturali, 3 copre 2, ma 4 non lo fa.
Nel caso finito, queste operazioni sono inversioni reciproche, che producono una corrispondenza uno a uno tra DAG finiti e poset finiti. Così ogni DAG finito è essenzialmente un poset finito, e viceversa, permettendoci di confondere liberamente i concetti. Per esempio, l'insieme {1,2,3,4} può essere rappresentato sia come poset che come DAG:
1 →2→3→4
1≤2≤3≤4.
In matematica diciamo che i DAG finiti ed i poset finiti sono categorie equivalenti.
Ricordiamo che IOTA memorizza le transazioni in un DAG T chiamato Tangle: una freccia x→y esiste se e solo se la transazione x approva direttamente la transazione y. Così il tangle T è anche un poset con x≤y ogni volta che x approva indirettamente y.
Il protocollo IOTA dà priorità alle transazioni più grandi: quando x≤y, la transazione y è più importante di x. Per esempio, la genesi è sia l'elemento più grande o massimo in T, sia la più importante di tutte le transazioni.
Tuttavia, abbiamo ancora un problema: supponiamo che x e y siano in conflitto, e x e y sono incomparabili, cioè nessuna delle due transazioni approva l'altra. In questo caso, dobbiamo decidere quale transazione è più importante.
IOTA risolve questo problema utilizzando il livello di confidenza per ordinare totalmente T: scrivi x⪣y se il livello di confidenza di y è maggiore di x. Infatti, sotto ⪣ due transazioni sono paragonabili, e quindi ⪣ è davvero un ordine totale. Inoltre, ⪣ affina ≤, cioè x≤y (x approva y) implica che x⪣y.
Con l'ordine totale ⪣, ogni coppia di transazioni è paragonabile, e quindi siamo in grado di risolvere eventuali conflitti. Ad esempio, se le transazioni x e y spendono gli stessi soldi dallo stesso conto, allora sono in conflitto. Alla fine o x⪣y o y⪣x o y⪣x. Se y⪣x, allora il protocollo accetta x, la più grande delle due transazioni.
Facciamo un avvertimento: la relazione ⪣ è veramente un ordine totale solo se ci sono due transazioni senza lo stesso livello di confidenza, altrimenti la condizione (2) viene violata. Tuttavia, questa è in realtà un'ipotesi abbastanza ragionevole, poiché la probabilità che due transazioni abbiano esattamente lo stesso livello di confidenza è piuttosto bassa.
Gli ordini parziali compaiono anche nelle blockchain tradizionali. In una blockchain, le transazioni sono ordinate in base al punto in cui appaiono sulla catena più lunga. Tuttavia, poiché qualsiasi transazione non presente sulla catena principale viene ignorata, esse sono collocate in una posizione negativamente infinita.
Come si è visto con il protocollo IOTA, gli ordini parziali racchiudono i meccanismi di consenso nelle DLT. Se due transazioni sono potenzialmente in conflitto, allora un protocollo DLT deve in qualche modo dare priorità ad esse. Tuttavia, la priorità è un ordine parziale sull'insieme delle transazioni. Così tutti i nodi di una DLT devono raggiungere un consenso sull'ordine parziale delle transazioni.
Questa storia è simile all'equivalenza del consenso classico alla trasmissione atomica. Un protocollo in un sistema distribuito raggiunge la trasmissione atomica se stabilisce tra i nodi un registro ordinato di messaggi. Gli informatici hanno dimostrato che il consenso e le trasmissioni atomiche sono problemi equivalenti. Stabilire un ordine parziale sulle transazioni sembra essere l'equivalente DLT della trasmissione atomica.
Allora, come ci aiutano i poset? In primo luogo, i poset sono oggetti matematici ricchi e ben studiati. Così abbiamo l'opportunità di importare linguaggio, algoritmi e teoremi dal mondo dei poset al mondo delle DLT. Considerare un problema da più prospettive rivela spesso soluzioni innovative.
I poset ci aiutano anche a capire come una DLT specifica raggiunge il consenso analizzando come ordina le transazioni. Questa analisi può evidenziare i punti deboli della sicurezza: qualsiasi luogo in cui l'ordine può essere modificato è un punto che può essere attaccato. Per esempio, in IOTA, i livelli di fiducia possono essere manipolati e nelle blockchain, la catena più lunga può cambiare.
Il testo originale in lingua inglese si trova qui: https://blog.iota.org/posets-and-consensus-fe4c034595ab
Per ulteriori informazioni in italiano o tedesco trovate i miei contatti a questa pagina.
Se avete trovato utile la mia libera traduzione, accetto volentieri delle donazioni ;)
IOTA:QOQJDKYIZYKWASNNILZHDCTWDM9RZXZV9DUJFDRFWKRYPRMTYPEXDIVMHVRCNXRSBIJCJYMJ9EZ9USHHWKEVEOSOZB
BTC:1BFgqtMC2nfRxPRge5Db3gkYK7kDwWRF79
Non garantisco nulla e mi libero da ogni responsabilità.
