Alpha: jugando con la aleatoriedad
Si has estado siguiendo la Introducción Ilustrada a la serie Tangle, podrías recordar un misterioso parámetro llamado α, que afecta el nivel de aleatoriedad en el recorrido aleatorio. En este artículo entraremos en la forma específica en la que α afecta a la selección de consejos, y mencionaremos algunos aspectos a tener en cuenta a la hora de escribir una implementación de software.
Nótese que este artículo asume una comprensión básica de cómo se construye el Tangle, y en particular lo que son los aprobadores y los pesos acumulativos. También debe sentirse cómodo con la función exponencial, y tener alguna comprensión de la teoría de probabilidad.
¿Por qué necesitamos el azar de nuevo?
Para establecer el escenario para la comprensión de α, necesitamos recordar por qué realizamos una caminata al azar en primer lugar. El contexto es la selección de consejos: cada nueva transacción debe aprobar dos transacciones anteriores. La manera en que se hace esta elección es crucial para determinar cómo se ve y se comporta el Tangle.
El método de selección de la punta debe proporcionar idealmente las dos características siguientes:
- Una vez que una transacción acumula un gran número de aprobadores, es muy poco probable que sea abandonada.
- Las transacciones honestas deben ser aprobadas rápidamente.
Para lograr el primer objetivo, podríamos decidir realizar un recorrido determinista desde la génesis hasta las puntas, siempre hacia el aprobador de mayor peso acumulativo. Sin embargo, esto perjudicaría el segundo objetivo: sólo una sola cadena central obtendría aprobaciones, mientras que la mayoría de las transacciones se quedarían atrás.
Para llegar a un compromiso entre estos dos objetivos, introducimos una cierta aleatoriedad. Preferimos los aprobadores más pesados, pero también damos cierta probabilidad a los más ligeros.
Definición matemática
Estamos definiendo una función de transición, que nos dice la probabilidad de pasar de approvee a approver durante el recorrido aleatorio. Nos gustaría que esta probabilidad fuera grande para los aprobadores con un peso acumulativo alto, y pequeña para los aprobadores más ligeros.
La función de transición que utilizamos se define de la siguiente manera:
Donde Pxy es la probabilidad de caminar de x a y, Hy es el peso acumulativo de la transacción y, y z ~> x significa «z aprueba directamente x».
En otras palabras, la probabilidad de caminar de x a y aumenta exponencialmente con el peso acumulativo de y, multiplicado por α. La suma en el denominador es un factor de normalización, que establece la suma total de probabilidades de transición a uno.
Ejemplo
En el ejemplo siguiente, el camino aleatorio alcanzó la transacción X, que tiene tres autorizadores: A, B y C. Para calcular las probabilidades de transición, primero tenemos que calcular las ponderaciones acumulativas. A tiene un autorizador único y, por lo tanto, un peso acumulado 2. B tiene dos aprobadores, así que tiene peso 3. Finalmente, C no tiene aprobadores, por lo que su peso es 1.
Comencemos con α=1, y conectemos los números a la fórmula anterior:
Podemos ver que C tiene una probabilidad mucho menor de ser elegido que A o B; ya que su peso es menor.
Si establecemos α a un valor menor, reducimos el sesgo en contra de C. Por ejemplo, para α=0.1, obtenemos las siguientes probabilidades:
Todavía hay un ligero sesgo en contra de la transacción C, pero es mucho menos pronunciado.
Si examinamos el escenario extremo de α=0, todos los aprobadores son completamente equivalentes, y tienen una probabilidad de 1/3. Este es el caso cuando los pesos dejan de importar, y la caminata es completamente aleatoria.
En el otro extremo, tenemos el caso de un alfa muy grande. En este escenario, la probabilidad de caminar hacia A es 1, y B y C tienen probabilidad de transición cero. Este caso es análogo a una cadena de bloques: sólo aprobamos la punta más probable y nunca fusionamos diferentes ramas.
Fuente: https://blog.iota.org
