Parte 3 – Pesos acumulados y caminatas aleatorias ponderadas
Anteriormente aprendimos acerca de la caminata aleatoria no ponderada, y hoy aprenderemos acerca de su primo más avanzado: la caminata aleatoria ponderada.
Empecemos con un poco de motivación para estudiarlo. Una de las cosas que queremos que haga nuestro algoritmo de selección de tips es evitar las tips perezosos. Una tip perezosa es aquella que aprueba las transacciones viejas en vez de las recientes. Es perezosa porque no se molesta en mantenerse al día con el estado más reciente de la tangle, y sólo emite sus propias transacciones basadas en datos antiguos. Esto no ayuda a la red, ya que no se confirma ninguna operación nueva.
En el ejemplo anterior, la transacción 14 es una tip perezosa, que aprueba algunas transacciones muy antiguas. Si usamos el algoritmo de selección aleatoria de tip, la transacción 14 es tan probable que sea aprobada como cualquier otra, por lo que no está siendo penalizada en absoluto. Usando la caminata no ponderada, incluso se fomenta este mal comportamiento, al menos en este ejemplo en particular.
¿Cómo podemos hacer frente a este problema? Una cosa que no podemos hacer es obligar a los participantes a aprobar solamente las transacciones recientes, ya que eso chocaría con la idea de descentralización. Las transacciones pueden aprobar a quien quieran. Tampoco tenemos una manera confiable de saber exactamente cuándo llegó cada transacción, por lo que no podemos hacer cumplir esa regla. Nuestra solución es construir nuestro sistema con incentivos incorporados contra tal comportamiento, de modo que las tips perezosas probablemente no serán aprobadas por nadie.
Nuestra estrategia será sesgar nuestra caminata al azar, por lo que es menos probable que escojamos tips perezosas. Usaremos el término peso acumulado para indicar la importancia de una transacción. Es más probable que caminemos hacia una transacción pesada que hacia una ligera. La definición del peso acumulativo es muy simple: contamos cuántos aprobadores tiene una transacción y añadimos uno. Contamos con aprobadores directos e indirectos. En el ejemplo siguiente, la operación 3 tiene un peso acumulado de cinco, porque tiene cuatro operaciones que la aprueban (5 directamente; 7,8 y 10 indirectamente).
¿Por qué funciona esto? Echemos un vistazo a otra situación de tip perezosa. En el ejemplo siguiente, la transacción 16 es una tip perezosa. Para que se apruebe, el caminante aleatorio debe alcanzar la transacción 7 y, a continuación, seleccionar la transacción 16 en lugar de la transacción 9. Pero es poco probable que esto suceda, porque la transacción 16 tiene un peso acumulado de 1, y la transacción 9 tiene un peso acumulado de 7! Esta es una manera efectiva de desalentar el comportamiento perezoso.
A estas alturas podríamos preguntarnos: ¿necesitamos el azar? Podemos inventar el paseo aleatorio superponderado, donde en cada cruce elegimos la transacción más pesada, sin ninguna probabilidad involucrada. Entonces conseguiremos algo así:
Los cuadrados grises son tips, con cero aprobadores. Aunque es normal tener algunas puntas en el extremo derecho del diagrama, es un problema ver tantas puntas esparcidas por la línea de tiempo. Estas tips son transacciones que se dejan atrás, y nunca serán aprobadas. Este es el lado negativo de predisponer demasiado nuestro caminar: si insistimos en elegir sólo la transacción más pesada en un momento dado, un gran porcentaje de las tips nunca serán aprobadas. Sólo nos queda un corredor central de transacciones aprobadas y consejos tips olvidadas al margen.
Necesitamos un método para definir qué tan probable es que caminemos hacia un aprobador en particular en un cruce dado. La fórmula exacta que elegimos no es importante, siempre y cuando demos algún sesgo a las transacciones más pesadas, y tengamos un parámetro para controlar cuán fuerte es este sesgo. Esto introduce nuestro nuevo parámetro α, que establece la importancia del peso acumulativo de una transacción. Su definición exacta se puede encontrar en el white paper, y si hay demanda podría escribir un post futuro dando más detalles sobre él.
Si ponemos α a cero, volvemos a la caminata no ponderada. Si ponemos α muy alto, tendremos la caminata superponderada. Mientras tanto, podemos encontrar un buen equilibrio entre castigar el comportamiento perezoso y no dejar demasiados consejos. Determinar un valor ideal para α es un tema de investigación importante en IOTA.
Este método de establecer una regla para decidir la probabilidad de cada paso en una caminata aleatoria se llama técnica de Cadena de Markov Monte Carlo, o MCMC (siglas en ingles). En una cadena Markov cada paso no depende del anterior, sino que sigue una regla que se decide por adelantado.
Como siempre, tenemos una simulación para demostrar estas nuevas ideas. Recomendamos jugar con los valores de α y λ, y ver qué interesantes tangles puedes hacer. La próxima semana entraremos en más detalles sobre lo que significa decir que la transacción A aprueba la transacción B, y definiremos cuándo se considera que una transacción está confirmada.
Parte 1: Introducción a la tangle.
Parte 2: tasas de transacciones, latencia y caminatas aleatorias.
Parte 3: Pesos acumulados y caminatas aleatorias ponderadas.
Parte 4: Aprobadores, balances, y doble-gastos.
Parte 5: Consenso, intervalo de confianza, y el coordinador.
Traducido por deepl.
