ES2961304T3 - Sistema y método que implementa un algoritmo de consenso de gráfico acíclico dirigido (DAG) a través de un protocolo epidémico - Google Patents
Sistema y método que implementa un algoritmo de consenso de gráfico acíclico dirigido (DAG) a través de un protocolo epidémico Download PDFInfo
- Publication number
- ES2961304T3 ES2961304T3 ES20020031T ES20020031T ES2961304T3 ES 2961304 T3 ES2961304 T3 ES 2961304T3 ES 20020031 T ES20020031 T ES 20020031T ES 20020031 T ES20020031 T ES 20020031T ES 2961304 T3 ES2961304 T3 ES 2961304T3
- Authority
- ES
- Spain
- Prior art keywords
- node
- information
- given
- events
- dag
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/01—Protocols
- H04L67/10—Protocols in which an application is distributed across nodes in the network
- H04L67/1095—Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9024—Graphs; Linked lists
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
- H04L9/0643—Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/27—Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F16/273—Asynchronous replication or reconciliation
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/54—Interprogram communication
- G06F9/542—Event management; Broadcasting; Multicasting; Notifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/01—Protocols
- H04L67/10—Protocols in which an application is distributed across nodes in the network
- H04L67/1097—Protocols in which an application is distributed across nodes in the network for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
- H04L69/03—Protocol definition or specification
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
- H04L69/26—Special purpose or proprietary protocols or architectures
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/50—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using hash chains, e.g. blockchains or hash trees
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Theoretical Computer Science (AREA)
- Databases & Information Systems (AREA)
- Computer Security & Cryptography (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Power Engineering (AREA)
- Computing Systems (AREA)
- Multimedia (AREA)
- Information Transfer Between Computers (AREA)
- Mobile Radio Communication Systems (AREA)
- Computer And Data Communications (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
La invención se refiere a un método implementado por computadora para intercambiar información, a través de un algoritmo de consenso DAG/Hashgraph a través de un protocolo de chismes, el método comprende pasos para hacer que un primer nodo dado (N1) seleccione un segundo nodo dado (N4) aleatoriamente y envíe información de referencia (8);- determinar en base a la información de referencia (8) qué eventos de nodo están delante de los demás;- si la información de referencia (8) implica que los eventos del primer nodo dado (N1) están en delante del del segundo nodo dado (N4), - luego enviando una información de cancelación (9) al primer nodo dado (N1), impidiendo, en consecuencia, que el primer nodo dado (N1) envíe información de evento DAG a el segundo nodo dado (N4); - Si la información de referencia (8) implica que los eventos del segundo nodo dado (N4) están delante de los del primer nodo dado (N1), - entonces hacer que el primer nodo dado (N1) enviar información de evento DAG (6) al segundo nodo dado (N4); y próximamente a través de la red. (Traducción automática con Google Translate, sin valor legal)
Description
DESCRIPCIÓN
Sistema y método que implementa un algoritmo de consenso de gráfico acíclico dirigido (DAG) a través de un protocolo epidémico
[0001] La presente invención se refiere al campo del intercambio de información relativa, en particular, a una lista de acciones o transacciones, entre nodos informáticos distribuidos conectados en una red específica.
[0002] La invención se refiere a un sistema y un método que implementa un algoritmo de consenso de gráfico acíclico dirigido (DAG), como un algoritmo de consenso Hashgraph a través de un protocolo epidémico.* ;[0003] El Hashgraph es conocido en la técnica como una nueva forma de llegar a un consenso en una red descentralizada. A menudo se le denomina algoritmo de votación. El Hashgraph es un gráfico acíclico dirigido (DAG) específico. ;[0004] El objetivo de Hashgraph es principalmente llegar a un consenso entre los nodos del sistema de distribución. El algoritmo Hashgraph es una forma de resolver el problema de los generales bizantinos. ;[0005] Además, los algoritmos Hashgraph pueden impedir que un atacante apague o congele la red, impidiendo así que alcance un consenso. ;[0006] Una idea de esta invención es tener una forma eficiente de intercambiar información entre nodos, así como un método de soporte y un sistema de soporte para Hashgraph u otros sistemas DAG que necesitan intercambiar información DAG. ;[0007] La Figura 1 ilustra esquemáticamente un Hashgraph tal como se desarrolla en la técnica. El Hashgraph se basa en una red de nodos informáticos (N<a>, N<b>, N<c>, N<d>, N<e>) dispuestos verticalmente en la figura 1. Cada nodo informático (N<a>, N<b>, N<c>, N<d>, Ne) puede registrar lo que se llama un evento 1 representado como un círculo, y más detallado en la figura 2. El evento es generalmente una secuencia de información/bytes y memoria, que luego se procesa mediante hash. El evento será registrado por el nodo. El evento comprende una información que se distribuirá a la red. La información generalmente se codifica para protegerla. El Hashgraph permite así distribuir información segura que se distribuye en la red. ;[0008] El evento está firmado por el nodo. ;[0009] En la implementación de un Hashgraph, un nodo seleccionará aleatoriamente otro nodo y le transmitirá toda la información que obtuvo sobre la comunicación. Esto se repite hasta que la información se propaga por toda la red. ;[0010] El Hashgraph implica un número infinito de transmisiones de información en la red. Además, en el algoritmo Hashgraph, un evento siempre incluye una marca de tiempo para alcanzar una marca de tiempo de consenso en la red. ;[0011] Con referencia a la figura 2, la información del evento incluye: ;- un hash del auto-padre 2 recibido del nodo del auto-padre representado verticalmente en la figura 2. El hash del autopadre 2 se relaciona con eventos anteriores en la memoria del auto-padre nodo padre; ;- un hash del “otro” padre 3 recibido del otro nodo padre representado diagonalmente en la figura 2. El hash del otro padre 3 se relaciona con eventos anteriores en la memoria del otro nodo padre; ;- información del evento actual 1 i; y ;- una marca de tiempo 4 del evento actual. ;[0012] Un objetivo de la invención es limitar/reducir el número de transmisiones de información y disminuir el uso de recursos informáticos en los cálculos, almacenamiento y transmisión de la información. ;[0013] Otro objetivo general de la invención es intercambiar información de manera eficiente entre nodos de computadora y evitar que los nodos entren en un eco infinito donde siempre envían información de un lado a otro. ;[0014] Otro objetivo es proteger los nodos y determinar fácilmente qué información se debe compartir entre los nodos, sin enviar información innecesaria entre ellos. ;[0015] Para cumplir con estos objetivos, la invención se refiere a un método implementado por ordenador * 1.
[0016] Más precisamente, según un aspecto, el método comprende una etapa para
- hacer que el segundo nodo dado envíe una información de cancelación al primer nodo dado,
cuando el segundo nodo dado recibe la información de referencia del primer nodo dado,
si el segundo nodo dado envió previamente una información de referencia al primer nodo dado, de modo que el primer nodo dado no envía información de evento DAG al segundo nodo dado.
[0017] La “ información de evento DAG” se refiere a la información que se intercambia en relación con un evento del DAG. En particular, las informaciones están conectadas mediante punteros hash. Significa que el hash de un evento es un hash único (huella digital), y las huellas digitales del hash del padre propio y del otro padre están contenidas en el evento, que actúa como identificadores/punteros únicos entre eventos en el DAG.
[0018] Ventajosamente, el método permite limitar el número de transmisiones de información a través de la información de cancelación de manera que el nodo detenga la comunicación de la información. Eso implica disminuir el uso de recursos informáticos en los cálculos, almacenamiento y transmisión de la información.
[0019] La idea con esta invención es tener una manera eficiente de intercambiar información entre nodos (epidémico sobre epidémico). Por lo tanto, el método de frente de ola se utiliza como sistema de soporte para Hashgraph u otros sistemas DAG que necesitan intercambiar información DAG.
[0020] Además, limita el número de información enviando el estado de la cadena de eventos de cada nodo, que se indica mediante el número de referencia/altitud. De esta manera, el nodo puede decidir si el último evento de una cadena de eventos está detrás o delante de la otra cadena de evento del nodo.
[0021] Además, la cancelación permite evitar el eco infinito entre dos nodos.
[0022] Además, el método de frente de ola permite proteger los nodos fácilmente y determinar qué información se debe compartir entre los nodos compartiendo el estado de “frente de ola” (que se detalla más adelante) sin enviar información innecesaria entre ellos.
[0023] Según otros aspectos del método tomados individualmente o combinados en cualquier combinación técnicamente posible:
- la información de referencia se refiere al orden de los eventos de los nodos; y/o
- el orden de los eventos de los nodos se determina realizando un seguimiento de un valor de ordenadas de cada evento; y/o
- el orden de los eventos de los nodos se determina haciendo que cada nodo realice un seguimiento de un valor entero llamado Altitud, que aumenta para cada evento creado en un nodo; y/o
- la información de referencia se envía mediante un maremoto; y/o
- la información de cancelación se envía a través de ola rompiente; y/o nodo al primer nodo dado es la segunda y última ola de información de evento DAG; y/o
- el método comprende una etapa para enviar otra información de cancelación si un nodo recibe información que no está en una secuencia predeterminada de intercambio de información y/o si un nodo recibe información de un nodo con el que ya intercambió información.
[0024] La invención se refiere además a un sistema para intercambiar información según la reivindicación 8.
[0025] Las ventajas mencionadas anteriormente para el método también se aplican al sistema que implementa el método.
[0026] Según otros aspectos del sistema tomados individualmente o combinados en cualquier combinación técnicamente posible:
- la información de referencia se refiere al orden de los eventos de los nodos; y/o
- el sistema comprende medios para realizar un seguimiento de un valor de ordenadas de cada evento para determinar el orden de los eventos de los nodos; y/o
- el sistema comprende medios para hacer que cada nodo realice un seguimiento de un valor entero llamado Altitud, que aumenta para cada evento creado en un nodo para determinar el orden de los eventos de los nodos; y/o
- el sistema comprende medios para enviar la información de referencia a través de una ola de marea, y medios para enviar la información de cancelación a través de una ola rompiente; y/o
- el sistema comprende medios para limitar el número de transmisiones de información de eventos DAG entre el primer nodo dado y el segundo nodo dado; y/o
- el sistema comprende medios para enviar otra información de cancelación si un nodo recibe información que no está en una secuencia predeterminada de intercambio de información.
[0027] Otro objeto de la invención es una red que comprende una o más unidades centrales, en particular, una o más unidades centrales computarizadas, y conexión(es) a unidades de comando adicionales que implementan transacciones, en particular, unidades de comando computarizadas, la(s) unidad(es) central(es) que comprende un sistema según la invención.
[0028] La invención se presentará ahora en detalle mediante la descripción de realizaciones no limitativas de la invención y basándose en los dibujos adjuntos, entre los cuales:
- la figura 1 es una ilustración esquemática de un Hashgraph en un método según la técnica anterior;
- la figura 2 es una ilustración esquemática de un evento en el Hashgraph de la figura 1;
- la figura 3 es una ilustración esquemática de un sistema según una forma de realización de la invención;
- la figura 4 es una ilustración esquemática de un Hashgraph en un método según una forma de realización de la invención; y
- la figura 5 es una ilustración detallada de los intercambios de información entre dos nodos de la invención.
[0029] La invención se refiere al intercambio de información.
[0030] La invención incluye implementar un algoritmo de consenso DAG a través de un protocolo epidémico sobre epidémico, tal como un algoritmo de consenso Hashgraph a través de un protocolo epidémico sobre epidémico.
[0031] Los medios de la invención distribuyen la información mediante un protocolo epidémico, enviando información sobre los datos recibidos del resto de nodos de una red específica 5.
[0032] La invención se refiere a un método implementado por computadora, así como al correspondiente sistema 5a y red 5. El método de la invención permite procesar e intercambiar información, tal como la que se necesita con respecto a las transacciones de cadena de bloques y las aplicaciones de Hashgraphs.
[0033] El DAG, como un Hashgraph, se utiliza para intercambiar información entre nodos informáticos distribuidos conectados en una red específica. La información está asegurada y codificada. La información del DAG/Hashgraph transmitida se denominará “ información del evento DAG”.
[0034] Un protocolo epidémico implica que los nodos informáticos se transmiten entre sí la información que tienen en la memoria.
[0035] El método de la invención comprende una etapa para determinar un orden de eventos de nodo para determinar los eventos de nodo que están al frente y los eventos de nodo que están detrás.
[0036] En la forma de realización, el orden delante y detrás no se basa en el tiempo. Esta forma de realización no necesita el consenso de tiempo. Ventajosamente, esto evita el problema de tener que hacer eco del nodo informático para acordar al mismo tiempo.
[0037] Determinar el orden de los eventos para saber qué evento está delante y cuál detrás. De esta manera la información sobre el evento es más precisa. Preferiblemente, esta determinación no se limita a tener una marca de tiempo del nodo en el evento.
[0038] Según una forma de realización de la invención, el orden de los eventos de los nodos se determina realizando un seguimiento de un valor de ordenadas de cada evento. Ventajosamente, el uso de un valor de ordenadas evita el problema de que los nodos del ordenador de eco coincidan al mismo tiempo.
[0039] En particular, el orden de los eventos de los nodos se determina haciendo que cada nodo realice un seguimiento de un valor entero llamado Altitud, que aumenta con cada evento creado en un nodo. Las altitudes juegan un papel en el procesamiento de la información.
[0040] En otra etapa del método de la invención, un primer nodo N1 determinado selecciona aleatoriamente un segundo nodo N4 determinado y puede enviarle información de evento DAG 6 , 7 en las redes. De manera más general, el sistema está hecho de manera que el primer nodo N1 seleccione un segundo nodo dado N4 aleatoriamente y, si corresponde, envíe información de evento dAg (6 , 7).
[0041] Todos los nodos N0, N1,..., N5,... de la red 5 proceden así hasta que la información del evento DAG (6, 7) se propaga en la red 5.
[0042] La invención tiene como objetivo evitar algunas transmisiones de información de eventos DAG y aún así hacer que la información relevante se propague en la red 5.
[0043] Según la invención, el método comprende una etapa para, cuando el primer nodo dado N1 selecciona aleatoriamente el segundo nodo dado N4, hacer que el primer nodo dado N1 envíe al segundo nodo dado N4 una información de referencia específica (8) antes de enviar cualquier información de evento DAG (6, 7). El envío de la información de referencia puede denominarse maremoto. el maremoto es un flujo de información.
[0044] El “maremoto” podrá definir un valor de altitud para cada nodo. Cada nodo realiza un seguimiento del evento DAG; esto significa que cada nodo tiene la altitud actual conocida por el nodo para cada nodo.
[0045] En particular, la información de referencia (8 ) se refiere al orden de los eventos de los nodos. Más particularmente, la información de referencia 8 comprende las altitudes anteriores, aquí, una lista de todas las altitudes para cada nodo.
[0046] Además, según la invención, el método comprende una etapa para enviar una información de cancelación (9) al primer nodo N1 dado bajo ciertas condiciones para evitar una transmisión adicional de información de eventos DAG, 7 desde el primer nodo N1 dado al segundo nodo N4 dado. El envío de la información de cancelación 9 puede denominarse ola rompiente. La ola rompiente es un flujo de información enviado como respuesta, para que el nodo vuelva al estado inicial.
[0047] La información de cancelación 9 se envía cuando el segundo nodo dado N4 recibe la información de referencia 8 del primer nodo dado N1 si, en vista de la información de referencia 8 , los eventos del segundo nodo dado N4 no están delante de los del primer nodo dado N1. Esto se hace fácilmente al analizar las altitudes.
[0048] La información de cancelación 9 puede ir directamente desde el segundo nodo N4 al primer nodo N1 en la forma de realización preferida.
[0049] El método comprende además una etapa para, como consecuencia de la información de cancelación, impedir que el primer nodo N1 dado envíe información de evento DAG al segundo nodo N4 dado.
[0050] En otras palabras: el segundo nodo N4 dado envía una información de cancelación al primer nodo N1 dado, de manera que el primer nodo N1 dado no envía información de evento DAG al segundo nodo N4 dado.
[0051] Ventajosamente, el método permite limitar el número de transacciones a través de la información de cancelación de manera que el nodo detenga la comunicación de la información. Esto implica disminuir el uso de recursos informáticos en los cálculos, almacenamiento y transmisión de la información.
[0052] Si, en vista de la información de referencia (8 ), los eventos del segundo nodo N4 dado están delante de los del primer nodo N1 dado, entonces continúa la transmisión de información de evento DAG.
[0053] En particular, el segundo nodo N4 envía la información del evento DAG, incluidos los eventos que tiene en la memoria, al primer nodo N1. Este primer envío de información de evento DAG puede denominarse primera ola 6. La primera ola es un flujo de información conocido como tal por el experto en la técnica. La información de eventos DAG de la primera ola 6 incluye una lista de todos los eventos que el segundo nodo dado N4 tiene en la memoria.
[0054] Además, en particular, después de que el primer nodo N1 dado reciba la información del evento DAG del segundo nodo N4 dado, el primer nodo N1 dado puede enviar la información del evento DAG, incluidos los eventos que tiene en la memoria, al segundo nodo N4 dado. Este segundo envío de información de eventos DAG puede denominarse Segunda ola (7). La Segunda ola es un flujo de información conocido como tal por el experto en la técnica.
[0055] Después de la primera y la segunda oleada, se detienen los intercambios de información entre el primer nodo N1 y el segundo nodo N4.
[0056] Esta es una segunda forma de evitar el eco infinito de la información transmitida. En otras palabras, cuando se recibe/envía la segunda ola, el estado de ola para este nodo ID vuelve al estado inicial.
[0057] Según una forma de realización preferida, el método incluye una etapa de enviar otra (segunda) información de cancelación si un nodo recibe información que no está en una secuencia predeterminada de intercambio de información, en particular la secuencia de primero la información de referencia (8), luego la primera ola (6) y, a continuación, la segunda ola (7) de la información del evento DAG. La información de cancelación es en particular del mismo tipo que anteriormente, pero se activa si, por ejemplo, el segundo nodo N4 dado recibe primero una segunda ola.
[0058] Según otra forma de realización, el método incluye una etapa de enviar otra (tercera) información de cancelación si un nodo recibe información de un nodo con el que ya intercambió información. La información de cancelación es en particular del mismo tipo que anteriormente, pero se activa si, por ejemplo, el segundo nodo N4 dado recibe posteriormente otra información de referencia 8 del primer nodo N1. Ventajosamente, estos pasos limitan aún más la redundancia/eco con respecto a la transmisión de información.
[0059] La invención se refiere además a un sistema 5a para implementar el método descrito anteriormente. El sistema 5a es un sistema computarizado y comprende módulos de hardware y software inherentes configurados para implementar el método descrito anteriormente. Puede denominarse sistema de frente de ola 5a.
[0060] El sistema 5a permite intercambiar información entre nodos informáticos distribuidos conectados en una red específica, implementando un algoritmo de consenso DAG/Hashgraph a través de un protocolo epidémico sobre epidémico.
[0061] El sistema 5a comprende medios para determinar un orden de eventos de nodo para determinar eventos de nodo que están delante y eventos de nodo que están detrás;
- medios para hacer que un primer nodo dado N1 seleccione un segundo nodo dado N4 aleatoriamente y envíe una información de referencia (8 ) y, cuando corresponda, información de evento DAG (6 , 7),
- medios para propagar la información de evento DAG (6 , 7) en la red 5.
[0062] Según un aspecto, el sistema 5a comprende
- medios para hacer que el segundo nodo N4 dado envíe una información de cancelación al primer nodo N1 dado, cuando el segundo nodo N1 dado recibe la información de referencia del primer nodo N1 dado,
si el segundo nodo N1 dado el nodo N4 envió previamente la información de referencia al primer nodo N1 dado, - medios para impedir, en consecuencia, que el primer nodo N1 dado envíe información de evento DAG al segundo nodo N4 dado.
[0063] El sistema 5a comprende además preferiblemente medios para enviar otra información de cancelación si un nodo recibe información que no está en una secuencia predeterminada de intercambio de información; y/o si un nodo recibe información de un nodo con el que ya intercambió información.
[0064] Las ventajas mencionadas anteriormente para el método también se aplican al sistema que implementa el método.
[0065] Otro objeto de la invención es una red que comprende una o más unidades centrales 10, en particular, una o más unidades centrales informatizadas, y conexiones 12 a unidades de comando adicionales 11 que implementan transacciones, en particular, unidades de comando informatizadas comprendiendo la(s) unidad(es) central(es) un sistema 5a como se describe anteriormente. Esto puede denominarse red de frente de ola. La red se puede conectar a través de Internet a las unidades de mando adicionales.
[0066] Las ventajas mencionadas anteriormente para el método y el sistema 5a también se aplican a la red 5 que incluye el sistema 5a correspondiente.
Ejemplo
[0067] Un ejemplo se describe en detalle en las figuras 4 y 5.
[0068] La figura 4 muestra un Hashgraph de información epidémico que representa el flujo de información entre los nodos de red N0, N1 , N2,..., N5. Otros nodos están preferiblemente en la misma red, pero no están representados.
[0069] En un tiempo finito, todos los nodos de la red podrán crear el mismo evento-DAG.
[0070] Cada línea vertical representa un nodo de cálculo y cada círculo un evento. Las líneas entre los eventos representan la comunicación de los eventos entre los nodos.
[0071] Los eventos que solo ven los respectivos Nodos están en círculos blancos con líneas continuas. Los eventos vistos por dos o más nodos están en círculos blancos con líneas discontinuas. Los últimos eventos del nodo respectivo están en círculos de colores lisos.
[0072] El último evento a crear es un círculo de puntos.
[0073] El algoritmo Hashgraph utiliza un protocolo epidémico llamado “epidémico sobre epidémico” para propagar información entre los nodos. Esto significa que un primer nodo N1 envía toda la información de la comunicación que conoce a un segundo nodo N4 seleccionado aleatoriamente. Esto permite al nodo N4 construir el mismo Hashgraph que el nodo N1.
[0074] En la red de la invención 5, se utiliza un protocolo llamado de frente de ola para intercambiar información entre dos nodos, asegurando que los nodos N1 y N4 solo necesitan comunicarse tres veces para intercambiar el estado del gráfico.
[0075] Cada nodo realiza un seguimiento de un valor entero llamado Altitud. La altitud aumenta en uno por cada evento creado por el nodo. Cada nodo almacena su vista actual de Altitud para cada nodo de la red.
[0076] Al intercambiar información sobre la altitud entre dos nodos, ambos pueden determinar cuál de los eventos está delante.
[0077] Para determinar qué evento está en el evento actual y al evento recibido se le resta este valor es mayor que 0 significa que el evento actual está delante del evento recibido y viceversa.
Ocorriente - Orecibido< 0
si el evento recibido está delante del evento actual.
[0078] El intercambio de información de frente de ola tiene cuatro estados:
1. El nodo Ni selecciona aleatoriamente el nodo N4 y envía una lista de las últimas altitudes conocidas para cada nodo. Este estado se llama maremoto.
2. El nodo N4 recibe un maremoto del nodo Ni. Si, según el maremoto, los eventos del nodo N4 no están delante de los eventos del nodo Ni, entonces el nodo N4 enviará lo que se llama ola rompiente al nodo Ni. De lo contrario, el nodo N4 devolverá una lista de todos los eventos que están delante del Maremoto del Nodo Ni. Este estado se llama primera ola.
3. Si el Nodo Ni recibe una primera ola del Nodo N4, devuelve una lista de todos los eventos que están delante del Nodo N4. Cuando se alcanza este estado, finaliza el intercambio de frente de ola.
4. Si el Nodo Ni o el Nodo N4 reciben una ola rompiente, la comunicación del frente de ola se interrumpe.
[0079] Respecto al estado 2, de forma alternativa o en combinación, si el Nodo N4 ya intercambió información con el nodo Ni a través de un Maremoto anterior, entonces el Nodo N4 enviaría una ola rompiente. Además, de forma alternativa o en combinación, si el Nodo N4 recibiera al principio una segunda ola del nodo Ni, entonces el Nodo N4 enviaría una ola rompiente.
[0080] Esto evita que ambos nodos entren en un eco infinito en el que envían información de un lado a otro para siempre.
[0081] En la red, un nodo suele tener muchas conexiones de frente de ola simultáneas, por lo que a veces recibirá el mismo paquete de eventos de otros nodos. Simplemente eliminará cualquier evento duplicado que reciba.
[0082] Los ejemplos de las Figuras 4 y 5 ilustran eventos y se muestran valores de altitud.
[0083] El nodo i se sincroniza con el nodo N4. El evento b5 (coloreado) es el último evento generado por el nodo Ni y todos los eventos anteriores conocidos por b5 están debajo de la línea de puntos.
[0084] El evento e5 (de color) es el último evento generado por el Nodo N4 y todos los eventos anteriores conocidos por este evento están debajo de la línea discontinua.
[0085] Todos los eventos conocidos tanto por b5 como por e5 se dibujan como círculos discontinuos.
[0086] El frente de ola del nodo Ni (marcado con la línea de puntos) es la lista de todas las altitudes de los últimos eventos conocidos.
[0087] Esto significa que el nodo de frente de ola Ni es
[0088] Lo mismo para el Nodo N4 marcado con una línea discontinua azul
[0089] Los pasos de la comunicación son los siguientes:
[0090] El primer nodo Ni es el primero en estado inactivo en la parte inferior de la figura. El primer nodo Ni inicia un chisme hacia el segundo nodo N4 y pasa a un estado inicial /.
1. Frente de ola inicial:
[0091] El nodo Ni se conecta al nodo N4 y envía el frente de ola Wi,b5 al nodo N4.
[0092] Este mensaje está marcado como tipo Maremoto. Esto hace que el Nodo 4 pase de un estado inactivo a un estado de Maremoto T.
2. Si se recibe un mensaje marcado como tipo Maremoto:
[0093] El nodo N4 recibe el frente de ola y lo compara con su frente de ola W4,e5 y recopila todos los eventos que están delante de W 1,b5, esto significa que los eventos e3, e4, e5, f3 y f4 se devuelven al nodo N1.
[0094] Este mensaje está marcado como del tipo de primera ola. Hace que el Nodo N1 pase al estadoFde primera ola.
3. Si se recibe un mensaje marcado primera ola:
[0095] El nodo N1 recibe el frente de ola del nodo N4 y almacena los eventos que desconoce el nodo N1.
[0096] El frente de ola recibido se comprará con su frente de ola y los eventos frente al frente de ola recibido se recopilan y devuelven al nodo N1.
[0097] Lo recogido en este ejemplo es a1, b1, b2, b4, b5, c2, c3 y d3.
[0098] Este mensaje está marcado como del tipo de segunda ola. Hace que el nodo N4 pase al estado S de segunda ola.
[0099] Si el Nodo N4 ya ha enviado un mensaje de la primera ola al Nodo N1, el Nodo N4 enviará un mensaje marcado como de tipo ola rompiente al Nodo 1 y deberá establecer el estado de comunicación con el Nodo N1 en ninguno.
4. Si se recibe un mensaje marcado como segunda ola:
[0100] Los eventos se almacenan si el Nodo N4 los desconoce.
5. Si se recibe un mensaje marcado ola rompiente:
[0101] Este estado de comunicación del canal recibido se establece en ninguno.
[0102] El flujo de comunicación del ejemplo se muestra en la Figura 5.
[0103] En este ejemplo, el maremoto 8 incluye la lista de altitudes ^W1,b5—[-3,-2,1,-10,2].
[0104] La primera ola 6 incluye la lista de altitudes W4e5—[-4 ,-6 ,-1 ,-2 ,3 ,4 ], y también la lista de eventos 1: {e3, e4, e5, f3, f4}.
[0105] La segunda ola 7 incluye la lista de eventos 1: {a1, b1, b2, b4, b5, c2, c3, d3}.
Claims (15)
1. Método implementado por computadora para intercambiar información entre nodos de computadora distribuidos conectados en una red específica, el método que implementa un algoritmo de consenso de gráfico acíclico dirigido, DAG, que es un
algoritmo de consenso de Hashgraph, mediante el uso de un protocolo epidémico sobre epidémico, comprendiendo el método pasos para
- hacer que un primer nodo dado (N1) seleccione un segundo nodo dado (N4) aleatoriamente y envíe información de referencia (8);
- determinar en base a la información de referencia (8) qué eventos de nodo están delante del otro (N1); caracterizándose el método por:
- Si la información de referencia (8) implica que los eventos del primer nodo dado (N1) están delante de los eventos del segundo nodo dado (N4),
--entonces enviar una información de cancelación (9) al primer nodo dado (N1), impidiendo, en consecuencia, que el primer nodo dado (N1) envíe información de evento DAG al segundo nodo dado (N4);
- Si la información de referencia (8) implica que los eventos del segundo nodo dado (N4) están delante de los eventos del primer nodo dado (N1),
--entonces hacer que el primer nodo dado (N1) envíe un evento DAG información (6) al segundo nodo dado (N4);
--luego hacer que el segundo nodo dado (N4) envíe información de evento DAG (7) al primer nodo dado (N1);
- y así sucesivamente para otros nodos, para sincronizar y propagar la información del evento DAG (6, 7) a través de la red.
2. Método implementado por ordenador según la reivindicación anterior, en el que la información de referencia se refiere al orden de los eventos de los nodos.
3. Método implementado por ordenador según cualquiera de las reivindicaciones anteriores, en el que el orden de los eventos de los nodos se determina realizando un seguimiento de un valor de ordenadas de cada evento.
4. Método implementado por ordenador según la reivindicación anterior, en el que el orden de los eventos de los nodos se determina haciendo que cada nodo realice un seguimiento de un valor entero llamado Altitud, que aumenta con cada evento creado en un nodo.
5. Método implementado por ordenador según cualquiera de las reivindicaciones anteriores, en el que la información de referencia se envía a través de un primer flujo de información (8), y/o la información de cancelación se envía a través de un primer segundo flujo de información (9).
6. Método implementado por ordenador según cualquiera de las reivindicaciones anteriores, caracterizado porque el segundo envío de información de evento DAG desde el segundo nodo dado al primer nodo dado es la segunda y última ola de información de evento DAG.
7. Método implementado por ordenador según cualquiera de las reivindicaciones anteriores, que comprende una etapa para enviar otra información de cancelación si un nodo recibe información que no está en una secuencia predeterminada de intercambio de información y/o si un nodo recibe información de un nodo con que ya intercambió información.
8. Sistema para intercambiar información entre nodos informáticos distribuidos conectados en una red específica, implementando el sistema un algoritmo de consenso de Gráfico Acíclico Dirigido, DAG, que es un algoritmo de consenso Hashgraph, mediante el uso de un protocolo epidémico sobre epidémico, comprendiendo el sistema
- medios para hacer un primer nodo dado (N1), seleccionar un segundo nodo dado (N4) aleatoriamente y enviar información de referencia (8);
- medios para determinar basándose en la información de referencia (8) qué eventos de nodo están delante de los demás;
caracterizado por
- medios para enviar una información de cancelación (8) al primer nodo dado (N1) si la información de referencia (8) implica que los eventos del primer nodo dado (N1) están delante de los eventos del segundo nodo dado (N4), impidiendo, en consecuencia, que el primer nodo dado (N1) envíe información de evento DAG (6, 7) al segundo nodo dado (N4); y
- medios para hacer que el primer nodo dado envíe información de evento DAG (6) al segundo nodo dado (N4) si la información de referencia (8) implica que los eventos del segundo nodo dado (N4) están delante de los eventos del primer nodo dado (N1),
--y medios para hacer que el segundo nodo dado (N4) envíe información de evento DAG (7) al primer nodo dado (N1);
- y así sucesivamente para otros nodos, para sincronizar y propagar la información del evento DAG (6, 7) a través de la red.
9. Sistema según la reivindicación anterior, en el que la información de referencia se refiere al orden de los eventos de los nodos.
10. Sistema según la reivindicación 8 o 9, que comprende medios para realizar un seguimiento de un valor de ordenadas de cada evento para determinar el orden de los eventos de los nodos.
11. Sistema según la reivindicación anterior, que comprende medios para hacer que cada nodo realice un seguimiento de un valor entero denominado Altitud, que aumenta para cada evento creado en un nodo para determinar el orden de los eventos de los nodos.
12. Sistema según cualquiera de las reivindicaciones 8 a 11, que comprende medios para enviar la información de referencia a través de un primer flujo de información (8), y medios para enviar la información de cancelación a través de un segundo flujo de información (9).
13. Sistema según cualquiera de las reivindicaciones 8 a 12, caracterizado por medios para limitar el número de transmisiones de información de eventos DAG entre el primer nodo dado (N1) y el segundo nodo dado (N4).
14. Sistema según cualquiera de las reivindicaciones 8 a 13, que comprende medios para enviar otra información de cancelación si un nodo recibe información que no está en una secuencia predeterminada de intercambio de información; y/o si un nodo recibe información de un nodo con el que ya intercambió información.
15. Red que comprende una o más unidades centrales, en particular, una o más unidades centrales computarizadas (10), y conexión(es) (12) a unidades de comando adicionales (11) que implementan transacciones, en particular, unidades de comando computarizadas, la(s) unidad(es) central(es) (10) que comprenden un sistema (5a) según cualquiera de las reivindicaciones 8 a 14.
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| EP20020031.9A EP3851974B1 (en) | 2020-01-20 | 2020-01-20 | System and a method implementing a directed acyclic graph (dag) consensus algorithm via a gossip protocol |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2961304T3 true ES2961304T3 (es) | 2024-03-11 |
Family
ID=69191849
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES20020031T Active ES2961304T3 (es) | 2020-01-20 | 2020-01-20 | Sistema y método que implementa un algoritmo de consenso de gráfico acíclico dirigido (DAG) a través de un protocolo epidémico |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US11706295B2 (es) |
| EP (1) | EP3851974B1 (es) |
| JP (1) | JP7727277B2 (es) |
| KR (1) | KR20210094484A (es) |
| CN (1) | CN113225175B (es) |
| ES (1) | ES2961304T3 (es) |
| PL (1) | PL3851974T3 (es) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US12197968B1 (en) * | 2022-06-09 | 2025-01-14 | Cisco Technology, Inc. | Ingest preview of events in a network computing environment |
Family Cites Families (20)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR102432731B1 (ko) * | 2015-08-28 | 2022-08-12 | 스월즈, 인크. | 네트워크 내의 분산 데이터베이스를 위한 방법 및 장치 |
| US9529923B1 (en) * | 2015-08-28 | 2016-12-27 | Swirlds, Inc. | Methods and apparatus for a distributed database within a network |
| US9390154B1 (en) * | 2015-08-28 | 2016-07-12 | Swirlds, Inc. | Methods and apparatus for a distributed database within a network |
| US10747753B2 (en) * | 2015-08-28 | 2020-08-18 | Swirlds, Inc. | Methods and apparatus for a distributed database within a network |
| US20170308648A1 (en) | 2016-04-20 | 2017-10-26 | Loop Med, Inc. | Patient status update and third party engagement system |
| US10862959B2 (en) * | 2016-11-28 | 2020-12-08 | Keir Finlow-Bates | Consensus system and method for adding data to a blockchain |
| CN116820695A (zh) * | 2016-12-19 | 2023-09-29 | 海德拉哈希图有限责任公司 | 用于启用事件删除的分布式数据库的方法和设备 |
| EP3560136B1 (en) * | 2016-12-22 | 2020-12-02 | Itext Group NV | Distributed blockchain-based method for saving the location of a file |
| US10944546B2 (en) * | 2017-07-07 | 2021-03-09 | Microsoft Technology Licensing, Llc | Blockchain object interface |
| AU2018300147B2 (en) * | 2017-07-11 | 2020-07-16 | Hedera Hashgraph, Llc | Methods and apparatus for efficiently implementing a distributed database within a network |
| US11461310B2 (en) * | 2017-07-17 | 2022-10-04 | Rdx Works Ltd | Distributed ledger technology |
| EP3543940A1 (de) * | 2018-03-23 | 2019-09-25 | Siemens Aktiengesellschaft | Computerimplementiertes verfahren zum bereitstellen von daten, insbesondere für eine konformitätsverfolgung |
| US20210209885A1 (en) * | 2018-05-23 | 2021-07-08 | Centiglobe Ab | A system and a method for achieving consensus between multiple parties on an event |
| CN109344623B (zh) * | 2018-09-27 | 2021-03-26 | 福建福链科技有限公司 | 一种基于dag的去中心化方法及终端 |
| US20200118131A1 (en) * | 2018-10-11 | 2020-04-16 | International Business Machines Corporation | Database transaction compliance |
| SG11202103504UA (en) * | 2018-10-23 | 2021-05-28 | Tzero Ip Llc | Context based filtering within subsets of network nodes implementing a trading system |
| CA3041463C (en) * | 2018-11-07 | 2020-08-25 | Alibaba Group Holding Limited | Facilitating practical byzantine fault tolerance blockchain consensus and node synchronization |
| US12468697B2 (en) * | 2019-06-12 | 2025-11-11 | Subramanya R. Jois | System and method of executing, confirming and storing a transaction in a serverless decentralized node network |
| CN110198233B (zh) * | 2019-05-09 | 2021-11-19 | 中国人民解放军国防科技大学 | 基于可信执行环境和有向无环图的区块链共识方法及系统 |
| PH12021553118A1 (en) * | 2019-06-13 | 2022-08-01 | Gutierrez Sheris Luis Eduardo | System and method using a fitness-gradient blockchain consensus and providing advanced distributed ledger capabilities via specialized data records |
-
2020
- 2020-01-20 PL PL20020031.9T patent/PL3851974T3/pl unknown
- 2020-01-20 EP EP20020031.9A patent/EP3851974B1/en active Active
- 2020-01-20 ES ES20020031T patent/ES2961304T3/es active Active
-
2021
- 2021-01-19 JP JP2021006777A patent/JP7727277B2/ja active Active
- 2021-01-20 KR KR1020210007909A patent/KR20210094484A/ko active Pending
- 2021-01-20 CN CN202110077870.9A patent/CN113225175B/zh active Active
- 2021-01-20 US US17/153,227 patent/US11706295B2/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| JP7727277B2 (ja) | 2025-08-21 |
| EP3851974C0 (en) | 2023-07-26 |
| EP3851974A1 (en) | 2021-07-21 |
| JP2021131850A (ja) | 2021-09-09 |
| KR20210094484A (ko) | 2021-07-29 |
| PL3851974T3 (pl) | 2024-03-04 |
| CN113225175B (zh) | 2024-08-23 |
| US20210227027A1 (en) | 2021-07-22 |
| US11706295B2 (en) | 2023-07-18 |
| EP3851974B1 (en) | 2023-07-26 |
| CN113225175A (zh) | 2021-08-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US12401531B2 (en) | Blockchain-based transaction data clearing after synchronization | |
| US11722318B2 (en) | Message transmission methods and apparatuses | |
| US10084756B2 (en) | Anonymous communications in software-defined networks via route hopping and IP address randomization | |
| US10887091B2 (en) | Multi-hop security amplification | |
| KR102230471B1 (ko) | 블록체인 네트워크 상에서 효율적인 트랜젝션을 수행하기 위한 그룹 증명 생성 방법 | |
| ES2961304T3 (es) | Sistema y método que implementa un algoritmo de consenso de gráfico acíclico dirigido (DAG) a través de un protocolo epidémico | |
| US12273354B2 (en) | Systems and methods for random differential relay and network coding | |
| Kohlweiss et al. | On the anonymity guarantees of anonymous proof-of-stake protocols | |
| JP7145937B2 (ja) | ブラインド化された帰結の多様化を用いてブロックチェーンのエントロピーを増加させるための方法および装置 | |
| CN113259461A (zh) | 跨链交互方法和区块链系统 | |
| CN114095507B (zh) | 跨链交互方法和区块链系统 | |
| Basyoni et al. | Empirical performance evaluation of QUIC protocol for Tor anonymity network | |
| Serena et al. | Simulation of dissemination strategies on temporal networks | |
| US20250323784A1 (en) | Providing quantum key distribution key delivery proof of origin and transit | |
| CN113064951B (zh) | 基于区块链的数据同步方法和装置 | |
| Taheri-Boshrooyeh et al. | Privacy-Preserving Spam-Protected Gossip-Based Routing | |
| RU2833868C2 (ru) | Система и способ для реализации алгоритма достижения консенсуса на основе ориентированного ациклического графа с применением эпидемического протокола | |
| Paavolainen et al. | Decentralized beacons: Attesting the ground truth of blockchain state for constrained IoT devices | |
| CN116645178A (zh) | 一种反洗钱数据处理方法、装置、设备及存储介质 | |
| JP2012216904A (ja) | 分散ルーティング処理装置およびコンピュータプログラム | |
| CN107453991B (zh) | 一种msti收敛的方法及网络设备 | |
| CN121037381A (zh) | 基于联盟区块链的数据共享系统网络部署方法及装置 |