En cualquier criptomoneda, las transacciones están vinculadas entre sí mediante hashes. Esta relación inalterable dota al conjunto de transacciones de una estructura matemática natural llamada orden parcial. En este post, discutimos los ordenes parciales y cómo son útiles para IOTA.
Ordenes totales vs. parciales
Los números reales, ℝ, tienen un orden natural denotado por ≤. Como niños, aprendimos que todos los números, x,y,z, y la relación ≤ satisfacen las siguientes condiciones:
- Reflexividad: x≤x
2. Antisimetría: x≤y y y≤x implica x=y
3. Transitividad: x≤y y y≤z implica x≤z
4. Totalidad: Ya sea x≤y o y≤x
Las relaciones de este tipo son omnipresentes en las matemáticas y se denominan así: una orden total es cualquier relación ≤ que satisfaga estas propiedades. Un set con una orden total se llama set totalmente ordenado.
Además, cada subconjunto de ℝ está totalmente ordenado, como los números naturales ℕ y el intervalo[0,1]. Sin embargo, hay otros ejemplos más exóticos de conjuntos totalmente ordenados. Por ejemplo, un aula X de niños está totalmente ordenada por altura, siempre que no haya dos niños en X que tengan la misma altura. Específicamente, para los niños x e y en X, podemos declarar que x≤y si x es más corto que y. De hecho, varias características como la edad, el peso o las calificaciones producen muchos pedidos totales diferentes en X.
Sin embargo, no todos los pedidos son totales. Por ejemplo, en ℝ², deje (a,b)≤(c,d) si a≤c y b≤d. Aunque esta relación satisface las condiciones (1)-(3), ℝ² no está totalmente ordenada ya que, por ejemplo, los elementos (2,3) y (3,2) son incomparables, ya que a<c mientras que b<d. Este ejemplo motiva un tipo diferente de orden.
Un pedido parcial es una relación ≤ que satisface todas las condiciones anteriores excepto la condición 4, por lo que algunos elementos pueden ser incomparables. Un poste (abreviatura de conjunto parcialmente ordenado) es un conjunto con un pedido parcial. Por ejemplo ℝ² es un poste con la relación anterior.
Para otro ejemplo, que X sea el siguiente conjunto de películas: Star Wars Holiday Special, The Matrix, Shrek y The Godfather. Yo digo que x≤y si la película es mejor que la película x. El especial de Star Wars es a menudo considerado una de las peores películas de todos los tiempos, mientras que El Padrino es considerado uno de los mejores. Por lo tanto, está claro que:
Sin embargo, en mi opinión, The Matrix y Shrek son incomparables. Por lo tanto, X es un poste, pero no un conjunto totalmente ordenado.
Puestos y DAGs
Recordemos que un DAG, o gráfico acíclico dirigido, es un conjunto de vértices conectados por flechas sin ciclos, es decir, sin una secuencia no trivial de flechas.
x→x₁→x₂→ᐧᐧᐧ→xₙ→x
comenzando y terminando en el mismo lugar. En esta sección se explica la estrecha relación entre los DAG y los posets.
Primero, podemos ordenar parcialmente el conjunto de vértices de cualquier DAG D. Para los vértices x,y en D, deja x≤y si hay una ruta de x a y. Recuerda que una ruta de x a y es una secuencia de flechas:
x→x₁→x₂→ᐧᐧᐧ→xₙ→y
Dejamos que el lector compruebe que la relación ≤ ordena parcialmente los vértices de D. Nótese que x≤y y y≤x si y sólo si hay un ciclo que incluya x e y. Así ≤ satisface la Condición (2) si y sólo si D es acíclico.
Por el contrario, para un poset X, podemos definir un DAG cuyo vértice es X. Para cada elemento x en X, dibujamos una flecha a cada y en X que cubre x. Un elemento y cubre x si x<y pero no existe z en X tal que x<z<y. Por ejemplo, en los números naturales, 3 cubre 2, pero 4 no.
En el caso finito, estas operaciones son inversas mutuas, produciendo una correspondencia uno a uno entre los DAG finitos y los posets finitos. Así, cada DAG finito es esencialmente un poset finito, y viceversa, lo que nos permite confundir libremente los conceptos. Por ejemplo, el conjunto {1,2,3,4} puede representarse como un poset y como un DAG:
1 →2→3→4
1≤2≤3≤4.
En las matemáticas decimos que los DAGs finitos y los posets finitos son categorías equivalentes.
Posets e IOTA
Recordemos que IOTA almacena las transacciones en un DAG T llamado Tangle: una flecha x→y existe si y sólo si la transacción x aprueba directamente la transacción y. Así el enredo T es también un poste con x≤y siempre que x indirectamente aprueba y.
El protocolo IOTA da prioridad a las transacciones mayores: cuando x≤y, la transacción y es más importante que x. Por ejemplo, la génesis es el elemento más grande o máximo en T y también la más importante de todas las transacciones.
Sin embargo, todavía tenemos un problema: supongamos que x e y entran en conflicto, y x e y son incomparables, es decir, que ninguna de las dos transacciones aprueba a la otra. En este caso, tenemos que decidir qué transacción es más importante.
IOTA resuelve este problema utilizando nivel de confianza para ordenar totalmente T: escriba a x⪣y si el nivel de confianza de y es mayor que x. De hecho, bajo ⪣ dos transacciones son comparables, por lo que ⪣ es en realidad un pedido total. Además, ⪣ refina ≤, es decir x≤y (x aprueba y) implica que x⪣y.
Con el total de pedidos ⪣, cada par de transacciones es comparable, y por lo tanto podemos resolver cualquier conflicto. Por ejemplo, si las transacciones x e y gastan el mismo dinero de la misma cuenta, entonces entran en conflicto. Eventualmente ya sea x⪣y o y⪣x. Si y⪣x, entonces el protocolo acepta x, la mayor de las dos transacciones.
Hacemos una advertencia: la relación ⪣ sólo es realmente un pedido total si no hay dos transacciones con el mismo nivel de confianza, ya que de lo contrario se viola la condición (2). Sin embargo, se trata en realidad de una hipótesis bastante razonable, ya que la probabilidad de que dos transacciones tengan exactamente el mismo nivel de confianza es bastante baja.
Las órdenes parciales también aparecen en las blockchains tradicionales. En una blockchain las transacciones se ordenan por el lugar donde aparecen en la cadena más larga. Sin embargo, como se ignora cualquier transacción que no esté en la cadena principal, se colocan en una posición negativamente infinita.
Conclusión
Como se ha visto con el protocolo IOTA, las órdenes parciales encapsulan los mecanismos de consenso en los DLTs. Si dos transacciones entran en conflicto, entonces un protocolo DLT necesita priorizarlas de alguna manera. Sin embargo, la prioridad es un orden parcial en el conjunto de operaciones. Por lo tanto, todos los nodos de un DLT deben llegar a un consenso sobre el orden parcial de las transacciones.
Esta historia es similar a la equivalencia del consenso clásico con la radiodifusión atómica. Un protocolo en un sistema distribuido logra la difusión atómica si establece entre los nodos un registro ordenado de mensajes. Los informáticos han demostrado que el consenso y las emisiones atómicas son problemas equivalentes. El establecimiento de una orden parcial sobre las transacciones parece ser el equivalente en DLT de la radiodifusión atómica.
Entonces, ¿cómo nos ayudan los posets? En primer lugar, los posets son objetos matemáticos ricos y bien estudiados. Así tenemos la oportunidad de importar lenguaje, algoritmos y teoremas del mundo de los posets al mundo de los DLTs. Considerar un problema desde múltiples perspectivas a menudo revela soluciones innovadoras.
Los posets también nos ayudan a entender cómo un DLT específico alcanza el consenso al analizar cómo ordena las transacciones. Este análisis puede poner de relieve las debilidades de seguridad: cualquier lugar donde se pueda cambiar el orden es un punto que puede ser atacado. Por ejemplo, en IOTA, los niveles de confianza pueden ser manipulados y en las blockchains, la cadena más larga puede cambiar.
Original post: Posets and Consensus by William Sanders
