La idea de la aceleración del algoritmo de reequilibrio (Rebalancing) en la red de canales

Tras el último estudio exhaustivo sobre el problema de enrutamiento en la red de pago, Shor, un compañero Nervos que ama la investigación, ha realizado un estudio detallado sobre el algoritmo de reequilibrio en la red de canales.

En este artículo, presentaremos el problema de reequilibrio en Channel Network (CN). Primero presentaremos la definición del problema y los algoritmos existentes para resolverlo. Después de eso, presentaremos los fundamentos de la teoría de grafos y los métodos de modelado necesarios para este problema. Finalmente, proporcionamos una idea de aceleración de algoritmo. (Este artículo asume que los lectores tienen un conocimiento común de las redes de canales).

Introducción al problema de reequilibrio en la red de pago Consideramos una red de pago como un gráfico no dirigido, cada nodo en el gráfico representa un PID, cada borde representa un canal de pago y cada borde tiene un stock en ambos extremos del nodo. Nota: Se toma por defecto la conservación del stock interno total de cada canal de pago (bidireccional), es decir, en el canal compuesto por A y B, si A tiene un saldo de 50 y B tiene un saldo de 80, después B le paga a A 10 yuanes, A tiene un saldo de 60 , B tiene un saldo de 70.

A veces, debido a la topología de la red y otras razones, una dirección de un canal de pago siempre es "más popular" que la otra. El tráfico de direcciones de bienvenida está agotado. Por lo tanto, la red de pago con frecuencia se quedará sin tráfico de canal y tendrá que "enlace ascendente" para abrir un nuevo canal nuevamente. Las técnicas de reequilibrio intentan paliar este problema de las siguientes maneras.

Por ejemplo, en la siguiente figura, consideramos un circuito compuesto por cuatro aristas, y el margen de 10 unidades en su dirección principal se ha agotado.

donde cada flecha 

10 millones de cuentas han comprado Bitcoin a través de Cash App: Noticias del 6 de mayo, según la carta de accionistas del primer trimestre emitida por Block, Inc (anteriormente Square) el jueves, desde la introducción de Bitcoin en Cash App, ha habido más de 10 millones de cuentas compraron algunas de las criptomonedas originales. [2022/5/6 2:55:43]

Representa un canal no dirigido que conecta A y B, donde la acción de A es a y la acción de B es b. Vale la pena señalar que la dirección de la flecha representa la dirección principal, por lo que dibujamos un gráfico dirigido, pero los últimos canales de pago basados ​​en RbR son bidireccionales. Revive completa un trabajo de reequilibrio a través de la coordinación de un líder global (en este artículo, no consideramos cómo se implementa este líder). Por ejemplo, es posible coordinar B para transferir 5 unidades a A, coordinar A para transferir 5 unidades a C, coordinar C para transferir 5 unidades a D y coordinar D para transferir 5 unidades a B, de modo que la estructura gráfica general se muestra en la siguiente figura. Su esencia es encontrar un "bucle" y, en este bucle, dejar que todos los canales fluyan juntos en contra de la dirección principal y contrarrestar algún flujo.   

¿Qué problemas estamos tratando de resolver cuando mencionamos Rebalance? El autor cree que la clave debe resolver dos problemas: 

El primer problema es el problema de encontrar el esquema de programación del grafo completo conocido (se presentará más adelante).

El segundo problema es el problema del protocolo: ¿quién realizará el proceso de cálculo anterior? Si lo hacen nodos de entidades individuales (líderes), ¿cómo pueden recibir información en tiempo real de una parte del gráfico y tomar decisiones de reequilibrio en tiempo real? ¿Cómo evitar que hagan el mal? Si se implementa de manera descentralizada, ¿cómo se pueden viabilizar los tres eslabones de recolección de información, cálculo e implementación? ¿Cómo participan los nodos de la red y siguen las reglas que queremos establecer?

The Sandbox comenzará una nueva ola de ventas de terrenos el 4 de noviembre: Noticias del 4 de noviembre, la nueva ola de ventas de terrenos de The Sandbox comenzará a las 9:00 p. m. el 4 de noviembre, incluidos 200 terrenos ordinarios y 100 terrenos de alta calidad. El personaje de calcomanía de mensajero japonés Quan se une a The Sandbox. La venta de terrenos de Quan comenzará a las 9:00 p. Los legendarios QuanNFT se venderán a través de subastas OpenSea. [2021/11/4 21:24:26]

En este artículo, dejamos de lado la segunda pregunta y nos enfocamos en la primera.

El problema de reequilibrio existente en la red de pago se puede describir de manera abstracta de la siguiente manera:

Dada una red de pago, encuentre suficientes bucles para maximizar el flujo que se puede ajustar. Este es sin duda un problema de programación lineal.

La idea existente (es decir, la idea del trabajo de Revive) es resolver directamente este problema de programación lineal. Sin embargo, el costo de resolver directamente este problema de programación lineal es muy alto (es aceptable para la escala actual de la red de pago, pero no factible para una futura red de pago hipotética con millones o miles de millones de nodos). La complejidad teórica del último algoritmo de programación lineal es O(M^w), donde M es el número de variables y restricciones, y w es una constante ligeramente menor que 3. Para la red de pago actual con decenas de miles de nodos, esta complejidad es aceptable, pero creemos que esta complejidad será mayor para la red de pago con millones de nodos en el futuro. ¡Pero no demasiado alto! Si la complejidad se puede optimizar ligeramente, es aceptable.

A continuación, daremos nuestras ideas de solución. Pero antes de eso, introduzcamos algunos conceptos básicos necesarios.

Fundamentos de teoría de grafos de conocimientos previos necesarios (componentes fuertemente conectados)  

Para un gráfico dirigido, un componente fuertemente conectado se refiere a un subgráfico entre dos puntos que se pueden alcanzar mediante bordes dirigidos en el gráfico. Un componente máximamente conectado es un subgrafo que no tiene la propiedad de componentes fuertemente conectados después de agregar cualquier otro nodo. Por ejemplo, en la figura anterior, podemos usar el área gris para delinear sus cuatro componentes extremadamente conectados.

Podemos observar lo siguiente:

El componente fuertemente conectado al máximo completa una partición para todos los nodos de cualquier gráfico dirigido.

Cualquier bucle solo puede existir en el mismo componente fuertemente conectado al máximo.

Existe un algoritmo O(N) extremadamente eficiente para encontrar todos los componentes conectados al máximo de cualquier gráfico dirigido (el algoritmo específico no se describirá en este artículo).

Donde N es el número de nodos en toda la red.

Considerando cada componente máximamente conectado como un todo, conectando todos los componentes con relación de acceso con bordes y puntos de contracción, obtenemos un gráfico acíclico dirigido.

Métodos de optimización específicos A continuación, presentamos algoritmos específicos.

Primero, hacemos una transformación simplificada del gráfico de red de pago original, transformando cada canal bidireccional en un borde dirigido desde el lado con más stock hacia el lado con menos stock, y la capacidad del borde es la mitad de la diferencia de stock entre los dos extremos. Por ejemplo, en la figura de abajo, transformamos la figura de arriba en la figura de abajo.

Así, transformamos el problema de encontrar circuitos en el problema de encontrar ciclos en grafos dirigidos. Cada borde del gráfico dirigido representa una "energía potencial" que requiere un flujo de reflujo para que el canal correspondiente del gráfico original esté más equilibrado. Cada bucle se puede ver como un esquema de reflujo. Después de reducir los componentes fuertemente conectados, solo necesitamos resolver el problema de reequilibrio dentro de cada componente extremadamente conectado a través de la programación lineal existente.  

La solución es clara: solo necesita resolver todas las componentes fuertemente conectadas al máximo de este grafo dirigido, y obtener un esquema de programación óptimo a través de la programación lineal convencional en cada componente fuertemente conectada al máximo. Debido a que creemos que cada ciclo no abarca dos componentes diferentes con una conexión máxima fuerte, creemos que este método encuentra el esquema de programación óptimo global.  

En realidad, hay una pequeña pregunta aquí: ¿es realmente una conversión equivalente? En la práctica no lo es (aunque a simple vista lo es). Puede haber una situación en la que haya bucles en el esquema de programación global óptimo que abarque dos componentes extremadamente conectados, porque puede haber una "necesidad de sufrir por la mayoría" ("necesidad de hacer que el lado de la minoría esté más desequilibrado para permitir que más lados se vuelvan más equilibrado") para obtener la posibilidad de una mejor solución. Sin embargo, el autor cree temporalmente que esta desviación vale la pena. Además, cuando se trata de la realidad, tal vez esas pocas personas no acepten tal despacho.  

Los lectores atentos deberían haber descubierto dos problemas que no se explican claramente en este artículo:

Esta pregunta esencialmente pregunta cuántos componentes extremadamente conectados tendrá la futura red de pago a gran escala.Cuantos más componentes haya, más obvio será el efecto de optimización. Esencialmente, esta pregunta es cuál es la topología de la futura red de pago a gran escala. Se puede esperar que la cantidad esperada de componentes conectados al máximo crezca a una tasa sublineal con respecto a la cantidad de nodos en la red si la mayoría de los nodos de la multitud tienen un grado de solo alrededor de 4.

De hecho, estas dos preguntas son esencialmente: ¿cuál es la topología de la futura red de canales a gran escala?

El autor cree que no solo el autor no puede responder a esta pregunta, sino que me temo que nadie puede responderla con precisión. Este punto se ha explicado en el artículo anterior "Un estudio exhaustivo sobre los problemas de enrutamiento en las redes de pago".

Tags：

FTT