Retransmisión eficiente de transacciones P2P
Fecha: October 8, 2018
Transcripción De: Bryan Bishop
Traducción Por: Blue Moon
Tags: P2 p
Categoría: Core dev tech
Mejoras del protocolo de retransmisión de transacciones p2p con reconciliación de conjuntos
gleb
No sé si necesito motivar este problema. Presenté una sesión de trabajo en curso en Scaling. El coste de retransmitir transacciones o anunciar una transacción en una red: ¿cuántos anuncios tienes? Cada enlace tiene un anuncio en cualquier dirección en este momento, y luego está el número de nodos multiplicado por el número de conexiones por nodo. Esto es como 8 conexiones de media. Si hay más transacciones, la situación empeora. Idealmente, queremos tener un número de nodos sin ese multiplicador..
La observación es que cada nodo necesita enterarse de cada transacción sólo una vez, pero ahora mismo se entera de cada transacción una vez por cada conexión que tiene. No es justo decir que cada nodo quiere enterarse de la transacción sólo una vez, porque también es bueno sincronizar su estado con otros pares, así que sigue queriendo obtener esa información de que su par conoce la transacción. También hace que la retransmisión compacta de bloques funcione de verdad. No sólo quieres enterarte de cada transacción una vez, sino enterarte de cada transacción una vez dentro de un marco de tiempo razonable. Además, quieres asegurarte de que tus pares también se enteran de la transacción. Queremos que el coste sea igual al número de nodos; queremos hablar con cada par y asegurarnos de que conocen todas las transacciones que se realizan. Aún así, queremos que cada nodo escuche cada mensaje al menos una vez.
Ahora mismo esto escala mal; el número de mensajes en la red sube y a la derecha con el número de mensajes. El protocolo que nos gustaría construir tendría una pendiente más lenta. Es un gráfico exponencial discontinuo, por eso el eje horizontal cambia aquí. El eje x no es lineal en ese gráfico. Queremos que la escalabilidad del ancho de banda con el número de nodos y el aumento de mensajes crezca aceptablemente.
Diseño del protocolo, métricas a tener en cuenta: ancho de banda, latencia (retardo de propagación al 100% de los nodos) y robustez frente a comportamientos adversos. No queremos filtrar mucha información. Siempre se trata de hacer concesiones.
El protocolo eficiente de retransmisión de transacciones consiste en que tú retransmites una transacción a un subconjunto de tus pares, y el siguiente nodo hace lo mismo. Así se extiende por una gran parte de la red. Otros nodos hacen la reconciliación basándose en un periodo determinado o en algún otro programa y se enteran de las transacciones de una forma más eficiente que simplemente enviando todos los anuncios que tienen.
Para ello, se realiza la reconciliación de transacciones. Cada nodo mantiene un conjunto de transacciones que habría enviado a cada par. Supongamos que el nodo B elige algún otro peer en la red para retransmitir una transacción y no C, sólo retransmitimos a algún subconjunto de peers. B retransmite a algún otro. El nodo B almacena esta lista para cada par al que habría anunciado una transacción, pero no lo hizo. Recibimos el mensaje de A, así que no lo almacenamos. Pero para el nodo D, normalmente habríamos anunciado a ese nodo. Por ahora podemos pensar en almacenar sólo el hash de la transacción, pero en realidad lo estamos almacenando en una estructura de datos diferente. Después de que el nodo D se entera de otra transacción y la anuncia en otro lugar de la red, entonces la registra en este conjunto para el par B. El nodo D también tiene un conjunto para A y C pero no importa en este ejemplo. El nodo B tiene un temporizador para reconciliarse con cada peer. El temporizador dice, consulta con el nodo D. Y entonces intercambian alguna información basada en este conjunto para que el nodo D y el nodo B sepan qué transacciones les faltan. La forma más sencilla de hacer esto es enviarse conjuntos entre sí y eso es sólo batching, pero no es eficiente. Después de la reconciliación, los conjuntos de memoria se borran para ese peer en el que ocurrió la reconciliación. Esto obviamente no es el protocolo inv, getdata, tx. Cuando B termina la reconciliación con D, puede o no hacer el anuncio a sus pares. Eso aún no está claro. Todavía se está midiendo.
En dandelion, hay una fase de tallo. Dandelion es estrictamente sobre el envío a un solo par. Esto es acerca de la propagación eficiente que es exactamente lo que dandelion no está tratando de hacer. Sí, esto está reemplazando la fase ploomb para dandelion.
Una vez conciliado, la decisión sobre qué hacer no está clara. Hay que sopesar el ancho de banda de los anuncios, el tiempo que se quiere esperar para la retransmisión de las transacciones, etcétera. La cuestión es, ¿debería el nodo B retransmitir las nuevas transacciones? Si lo hace, reducirá la latencia, pero es probable que algunos de sus pares ya lo supieran. La reconciliación es más lenta que la inundación. Por eso hay una alta probabilidad de que el nodo B elija un peer que ya sepa de esta transacción. Dicho de otra forma, si usamos un relé normal con envíos a 3 pares cada uno, por lo que se tiene un factor de ramificación de 3, esto tiene una alta probabilidad de llegar ya a casi todos los nodos de la red. Así que, en teoría, con uno es suficiente. Si consigues formar un ciclo que llegue a todos, es muy improbable. Si eliges 2 ó 3, llegarás a casi todo el mundo, sólo cuando los compañeros se desconecten o haya algún ciclo altamente improbable. La reconciliación es sólo para asegurarse de que los que no se han enterado a través del protocolo normal todavía tienen la garantía de enterarse. Lo ideal es que apenas se dedique ancho de banda a la reconciliación porque suponemos que el mecanismo normal ha llegado a casi todo el mundo. Hay que tener en cuenta muchos parámetros.
P: Si te enteras de algo nuevo a través de la reconciliación de conjuntos, ¿no cambia eso la probabilidad a priori de que otros nodos conozcan la transacción? Probablemente no muchos otros nodos la conozcan todavía si tú no la conoces.
Tras la reconciliación, los nodos borran sus conjuntos y vuelven a empezar. Durante la reconciliación de conjuntos, hay dos viajes de ida y vuelta.
Diferencias de conjuntos con códigos BCH
Usamos códigos BCH para hacer esto eficiente. Digamos que Alice tiene 7 transacciones en su conjunto, y Bob tiene 7 transacciones en su conjunto, y no tienen ni idea de cuáles son compartidas y cuáles no. Asumen que la mayoría son compartidas. Cada cinco segundos, un nodo elige un par de una cola. Así que, básicamente, lo que significa, si usted tiene 8 compañeros, entonces cada reconciliación ocurre en promedio cada 40 segundos, porque es 5 * 8. Durante ese tiempo, aprendemos mucho de otros pares y así sucesivamente.
P: ¿Has considerado hacer algo… estás actualmente sincronizando todo el mempool cada vez?
R: No. Estás reconciliando el conjunto de transacciones que habrías retransmitido desde la reconciliación anterior.
Cada 40 segundos, este conjunto se vacía, y entonces se vuelve a llenar con nuevas transacciones. Por eso es justo suponer que la mayoría de los elementos del conjunto ya están compartidos entre los dos nodos. Una vez que se enteran de transacciones que desconocen mutuamente, entonces hacen las conciliaciones. Es posible hacer que esto ocurra de la siguiente manera: si el ID de una transacción es de 32 bytes, basta con enviar simplemente …….. Alice estima el tamaño del conjunto, Alice calcula un resumen de su conjunto, Alice envía el resumen a Bob, Bob calcula su resumen, Bob XORs los resúmenes, Bob puede entonces encontrar las transacciones que le faltan. Si Alice subestimó y envió un resumen de tamaño 1, Bob fallará en el último paso porque la subestimación… sí, simplemente no puede recuperarse, y observará el fallo y solicitará otra iteración del protocolo o algo así. Si Alice sobreestimó y envió 3 elementos, está bien, sólo hay un poco de ancho de banda extra porque no es óptimo en ninguna parte.
Resultados de la simulación
En este momento esto es lo que estoy observando. Esto es con 10.000 nodos. Necesitamos reducir la redundancia en el fan-out inicial. También parte de esto se debe a fallos de reconciliación (subestimaciones). La mitad de los nodos nunca se enteran de las transacciones, y la otra mitad se enteran de las mismas transacciones dos veces o más. La subestimación se produce cuando falla la reconciliación de conjuntos y tenemos que enviar más datos a través de la red. En caso de que falle la reconciliación de conjuntos, Alice puede volver al protocolo original y enviarlo completo.
Si los nodos se desconectan y se forman ciclos, incluso sin otras cosas, habrá nodos que no se enteren de ciertas cosas.
P: ¿Están modelando nodos que caen fuera de línea?
R: No.
Si tu gráfico está conectado y tienes una retransmisión inicial a 3 pares, entonces asumo que toda la red recibe todo. Un porcentaje muy pequeño no recibirá todas las transacciones sin reconciliación. Es porque se forman ciclos. Estaba simulando con un 20% de conexiones salientes, emites a 1/5 de las conexiones entrantes. La mayoría de los nodos tienen 60 conexiones entrantes en mi simulación. Actualmente en la red hay una proporción de 1 a 10 de 1 nodo alcanzable a 10 nodos privados. Cada uno tiene 8 conexiones salientes, por lo que un nodo alcanzable tiene 60 conexiones entrantes de media. Así es como está ahora en mainnet. Hay cierta distribución porque algunos viejos son nodos y algunos nodos alcanzables son nuevos. Sólo tienes dos clases de nodos.
P: ¿Simulan retrasos en la propagación?
R: Sí.
Hay una buena propiedad en esta reconciliación de conjuntos que utiliza códigos BCH.
Cada elemento se expande en este boceto de un cierto tamaño que estimas, luego XOR todos los bocetos juntos de los diferentes elementos, luego los cancelas a través de- ambos lados calculan los XOR de sus bocetos, luego los XOR juntos, luego los que ocurren en ambos lados se cancelan. Hay un algoritmo (sin entrar en detalles de lo que es un sketch) donde si hay menos elementos en el sketch después de cancelarlos, entonces el tamaño del sketch, puedes encontrarlos.
Si este es tu número de cosas que quieres reconciliar, pero hay demasiadas para que coincida con el otro lado, el XOR de todas ellas supongo, si esto tiene demasiadas diferencias, puedo reintentarlo enviando el XOR de sólo la primera mitad y puedes calcular el boceto de la segunda mitad tomando lo que te envié antes y XORing con lo que había enviado ahora. Así que envías todo, y si no es suficiente, envías la primera mitad, y el otro lado vuelve a calcular la segunda mitad y ahora pueden hacer la reconciliación por separado en la primera mitad y la segunda mitad. También puede recurrir de nuevo, no sé cuántas iteraciones de profundidad que desea ir … Pero esto es bastante limpio porque si lo haces de forma iterativa y con pequeños excesos, nunca vas a tener demasiado o no demasiado demasiado. Reduce el costo del fracaso en la primera iteración. Tu compañero está bisecando el conjunto de la misma manera. La alternativa es que te doy un sketch más grande y esto funciona, puedes reutilizar la primera parte de- un sketch que tiene mayor capacidad es sólo uno de menor capacidad ampliado con algunos datos más. Si te envío uno que puede reconstruir 100 elementos y no es suficiente, también puedes enviar aquí están los siguientes 100 elementos para el sketch y ahora tienes algo que puede reconstruir 200. El algoritmo de reconstrucción es cuadrático en la diferencia. Pero esto tiene un coste de CPU lineal en lugar de cuadrático. También puedo entrar en la construcción real de los bocetos si hay interés.
También podemos bisecarlas. La bisección es en el id, no en una lista ordenada. Si usas los ids y sus salts y hashes cortos, salted by- elegidos por el peer… es por conexión, o por nodo. Un nodo, todas sus conexiones usan la misma sal. Necesitas tener la misma sal que el otro lado, pero es un lado el que elige la sal.
Utilizamos ids cortos de transacciones por dos razones. Podemos reducir drásticamente el ancho de banda utilizando ids cortos para los anuncios, y la tasa de colisión es bastante baja, y podemos sobrevivir a una cierta tasa de colisión. Esta construcción puede funcionar con ids cortos. El coste de CPU sube dramáticamente si haces los ids más grandes, creo que cúbicos o algo así. Creo que los ids son de 20, 30, 40 bits. Son cantidades muy pequeñas de datos. Estás hablando de las transacciones que se habrían retransmitido en el marco de un par de minutos, así que puedes hacer cosas bastante cortas.
Las colisiones pueden ser malas en el sentido de que una transacción puede atascarse… la misma transacción con el mismo short id en ambos lados, y la reconciliación podría pensar que son la misma. Esto es un problema. Si salas cada conexión con una sal diferente, entonces está bien. Si tienen el mismo short id, entonces la transacción no se propagará al otro nodo. No es un problema si hay colisiones sólo dentro de las transacciones que estás tratando de retransmitir; es sólo cuando hay una transacción diferente en ambos lados que colisiona. Si tienes dos transacciones con el mismo short id, simplemente envías la transacción. Usted no necesita resalt, sólo tiene que enviar, porque usted está perdiendo eso.
Algunos puntos de referencia de las bibliotecas BCH
Los códigos BCH son bastante caros sin optimización. IBLT es otro método de reconciliación de conjuntos. IBLT es mucho más simple de implementar, y computacionalmente es mejor que los códigos BCH, pero para conjuntos pequeños tiene una sobrecarga bastante alta de enteros pequeños. No un 10% de sobrecarga, sino 3 veces. Teóricamente, la información está muy cerca: si puedes predecir con exactitud la diferencia, entonces el ancho de banda es sólo la diferencia, lo cual es bastante sorprendente.
Bibliotecas de código BCH- se pueden calcular 50 diferencias en 4,48 ms, esto se calcula cada 5 segundos en cada nodo que ejecuta el protocolo en mi simulación. En un procesador Kaby Lake, son 0,3 ms para 50 elementos. 150 elementos son 26,91 ms en un ARM iMX.6, y 2,1 ms en el procesador Kaby Lake i7-7820HQ.
La construcción del croquis es prácticamente gratuita, es extremadamente rápida. Dado un sketch, intentar encontrar los elementos en él, es costoso. El protocolo está diseñado para que el que solicita la reconciliación haga todo el trabajo. Eso son 5 segundos con 1 peer, y si tienes 8 peers entonces son 40 segundos. El número de diferencias está en una ventana de 40 segundos o más, si tienes más peers. Si el coste de CPU del esquema fuera menor, entonces elegiríamos mayor… no escala linealmente si haces… si aumentas el tiempo entre eventos, el número de diferencias no va a seguir subiendo linealmente. ¿Puedes ajustar tu nodo para que solicite menos a menudo, y entonces tus compañeros hacen el trabajo? ((risas))
Eso puede no ser cierto. Algunas de mis mediciones, eso no está confirmado. Hay asimetría en los nodos. Los nodos privados siempre aprenden más que los nodos alcanzables. Los nodos alcanzables tienen 60 conexiones y si cada enlace se reconcilia de media una vez cada 40 segundos, entonces cada nodo alcanzable se reconcilia con alguien 2 veces por segundo. Así que habrá colisiones en los nodos alcanzables que reciban… incluso en la reconciliación de conjuntos, recibirán el mismo anuncio unas cuantas veces. Así que por eso estoy tratando de no enviar anuncios de vuelta a veces. Estoy probando de las dos maneras. Probablemente sea mejor pedir los datos que te faltan y ya está; lo estoy investigando.
¿Los identificadores cortos se basan en el wtxid? No he pensado en ello. Sí, supongo. Usa wtxids. ¿Qué pasa si manipulas el wtxid? Si dos nodos tienen diferentes versiones de la misma transacción, entonces no van a aceptar otra versión de la misma ya de todos modos. Así es como funcionan las cosas ahora, ¿verdad? Entonces, si tienes el mismo txid pero diferente wtxid, entonces la reconciliación no hará nada. Porque no le ayudará a conciliar. Intentarías reconciliar, pero… podrías evitar todo eso enviando simplemente el txid. Si tienes una versión maleada que rechazaste antes, entonces no sé… deberíamos volver a mirar lo del rechazo. No tenemos buenos datos. Nada está siendo rechazado por una tasa demasiado baja en este momento, por lo que no tenemos buenos datos sobre el filtro de rechazo que se utiliza. No obtenemos el beneficio del filtro de rechazo, porque no estamos rechazando nada por tasas demasiado bajas, así que no tenemos datos. En este momento tenemos 8x costo en segwit transacciones que están por debajo de la .. lo que sea .. Incluso en ausencia de malleation, no estamos usando el filtro de rechazo para las transacciones segwit. Así que no sabemos qué ancho de banda es. El filtro de tarifas esta diseñado para proteger contra esto sin el filtro de rechazo.. el filtro de tarifas deberia subir. Pero si no está en el pool de rechazos, entonces los bloques compactos no lo usarán. Oh.
Combinado con identificaciones cortas, este método de reconciliación de conjuntos utiliza hasta 44 veces menos ancho de banda. Me gustaría tener más revisores o más gente probando con mi simulador o escribiendo sus propios simuladores.
https://github.com/naumenkogs/Bitcoin-Simulator
¿Debemos anunciar las transacciones para conciliar? Quiero que el protocolo se acerque al caso ideal. Estoy considerando escribir un prototipo para Bitcoin Core. Tengo algunas ideas. Quería hacer una red de 100 nodos. ¿Es una buena idea hacer un millón de nodos? ¿O es malo ejecutar 100 nodos en un solo ordenador?
Yo no sugeriría ejecutar tantos nodos en una sola máquina. No, quiero ejecutar 100 nodos reales. En regtest estará bien. Todo el mundo tiene 64 gigabytes de RAM, ¿verdad?
Una vez que sipa publique algo acerca de los códigos BCH, entonces publicaremos cosas de retransmisión de transacciones. Primero deberíamos hacer que todos escriban cómo creen que funciona, luego hacemos una reconciliación entre ellos. O podríamos hacer algo sobre códigos BCH ahora mismo y luego publicar lo que kanzure escriba.
Conciliación de bocetos
sipa
En realidad hay dos maneras de explicarlo. Una es como un código BCH. El código BCH es un código de corrección de errores que algunas personas pueden conocer, ahora que tenemos un formato de dirección que lo utiliza. Digamos que estamos trabajando con identificaciones cortas de 20 bits. Necesitamos una función hash que nunca produzca 0 como salida; si es 0 entonces conviértelo en 1 en su lugar. Podemos hacerlo mejor. Tratamos las identificaciones cortas como elementos de campo en un campo característico. Podemos multiplicarlos juntos, podemos resolver conjuntos de ecuaciones sobre ellos, podemos sumarlos, todas esas cosas. Una forma de verlo es que… puedes pensar en ello como un código donde tus palabras código tienen de hecho 2^20 bits de longitud. Cada elemento del conjunto es una palabra de código con todos 0s y … así que nuestro hash es, tenemos mucha suerte, en este ejemplo es un número bajo, como 4700000 .. y podemos encontrar un código de corrección de errores sobre esta construcción que es algo que se puede hacer en una variedad de formas estándar. Esto resuelve el problema porque tomamos… los códigos de corrección de errores son lineales, lo que significa que le agrego una suma de comprobación, con algunas propiedades que definiremos más adelante. La propiedad importante es que son lineales. Para cada elemento, calculo mi boceto, que es mi código de palabras, calculo la suma de comprobación para él, y los XOR. Tengo una suma de comprobación y una palabra con un número de 1s en ella. Si el número de 1s en este conjunto es inferior a 7, entonces lo que sea. Y mi código está diseñado para corregir 7 errores. Haces una corrección de error asumiendo que todo lo anterior es 0, y ahora encuentras las posiciones de error y te dirá cuáles estaban mal. Esta es una explicación intuitiva, pero hay una serie de optimizaciones para hacer esto eficiente.
El tamaño de la suma de comprobación está relacionado con el número de errores que quieres poder corregir. Esto es tanto para la corrección como para la detección. En circunstancias normales, se necesita una distancia para codificar… Nuestro objetivo es corregir errores, no sólo la detección. Debido al hecho de que si nuestro campo base es solo 0s y 1s, no nos importa aprender sobre los errores si conocemos sus posiciones es suficiente porque si un bit es incorrecto entonces siempre es incorrecto por 1. Una vez que hable sobre la otra formulación, verás que la regla normal de necesitar 2x tantos elementos en tu checksum para corregir tus errores no se aplica porque la información teóricamente la razón por la que necesitas esos 2n es porque necesitas aprender tanto las posiciones como los errores.
P: ¿Importa qué campo se utilice? ¿Es sólo un código binario?
R: Tiene que ser un campo de característica 2, de lo contrario se produce inmediatamente una explosión de factor 2.
Esta es una descripción del origen de los códigos BCH. Voy a empezar de nuevo, y vamos a llegar a otro punto de vista para volver a eso.
Bocetos
Si mis elementos son x, y y z, entonces el boceto consiste en x+y+z, que es realmente el XOR de los bits. Ese es el primer elemento del sketch. El segundo es x^3 + y^3 + z^3… y el siguiente es x^5 + y^5 + z^5. Todos ellos deben ser elevados a estas potencias.. El primer paso al hacer la corrección…. ves que, tengo… Si necesitas 10, entonces subes a x^19 y claramente esto tiene propiedades de linealidad. Si tengo un sketch para x, y y z, y los xor juntos, entonces tengo uno que los ha sumado así que obtendré un sketch de salida. … La raíz cuadrada es una transformación lineal, puedes derivar todo tipo de propiedades divertidas de esto. Si tienes x + y + z, puedes calcular x^2 + y^2 + z^2 porque es simplemente elevar este número al cuadrado. Para la suma de las potencias 4ª, calculas elevando al cuadrado los números de las potencias 2ª. Y 6ª, haces ti para las terceras potencias. Lo que quiero decir es que, aunque sólo envíes los números impares, el receptor puede calcularlos todos. Esto es específico del uso de un campo de característica 2. Si no estuvieras haciendo eso, necesitarías dar todos los intermedios.
Los objetos matemáticos son elementos de campo, y estamos hablando de la suma sobre elementos de campo. Si los elementos del campo son bits sobre un número entero, entonces XOR representa la suma de los bits sobre el número entero. La multiplicación es mucho más difícil. Toda la optimización del código consiste en hacer que la multiplicación sea rápida.
Si me dan un número entero de elementos, ¿cómo averiguo qué son x, y y z? No se trata de simples ecuaciones u operaciones lineales. Digamos que sólo hay un elemento en nuestro conjunto, como x, así que después de la expansión de nuestros cuadrados tenemos esta secuencia de x, x^2, x^3, x^4, x^5… Ignorando que x está ahí sin más, puedes encontrar x tomando el cociente de los elementos. Hay una relación de recursividad que se mantiene sobre esta secuencia. La relación es… si tomas dos elementos cualesquiera y le aplicas esta multiplicación… dos elementos cualesquiera subsiguientes en esta secuencia, puedo aplicarle esta transformación lineal y obtendré cero. Así que esta es una relación de recursividad, elemento multiplicado por x más uno veces el siguiente elemento que se mantiene para cada elemento en esta secuencia.
Lo que también es cierto es que, si ves esta relación de recursión como un polinomio, entonces multiplicar esta transformación lineal por cualquier otra cosa también la mapeará a cero. Cualquiera de los dos elementos a los que aplico esta transformación, se mapea a cero. Si multiplico ese resultado por cualquier otra cosa, sigue siendo cero. Así que el conjunto de todas las transformaciones lineales que los elementos posteriores mapa a cero, son todos los múltiplos de este polinomio aquí (x-1) … estos son los coeficientes del polinomio. Si hago lo mismo con y, y^2, y^3, y^4, etc., obviamente mi relación es ahora (y, -1). Esto se mantendrá. La observación es que si XOR estos juntos, la relación que se llevará a cabo es de hecho (x-1) * (y-1) donde se multiplica por (y-1). Cualquier relación que fuera cierta tanto para esta secuencia como para esta otra, seguirá siendo cierta después de sumarlas. Si encuentras los factores comunes en estas transformaciones lineales y los escribes juntos, eso será algo que se mantiene para la suma. Supongo que me estoy adelantando.
Esta relación lineal se mantiene para la secuencia de y, y^2, y^3, etc., porque sumarían cero. Y (x, -1) transformación lineal sostiene para este otro. Así que (x, -1) * (y, -1) es lo mismo que multiplicarlos como polinomios. Así que de acuerdo en que esta relación inevitablemente celebrará para esta secuencia y esta secuencia. Es una transformación lineal. Suma estos dos, y esta transformación se mantiene para la suma. No es necesariamente la más simple que se mantiene para la suma, pero está garantizada.
Lo que quiero decir aquí es que si fuéramos capaces de encontrar a partir de la secuencia de números, la relación que se mantiene entre ellos, y luego encontrar y factorizar esto, encontraríamos los valores x e y. Resulta que hay un algoritmo para hacer esto, llamado Burlycam Massy. Te da la relación lineal más simple que se mantiene para todos los elementos. Es la base de los códigos Reed-Solomon y los códigos BCH, y ahí es donde entra esto. La cosa es, tomas tus sumas de potencias, las expandes usando un endomorfismo para obtener las potencias pares, usas Burlycam Massy para obtener la transformación lineal que se mantiene para todos los elementos, entonces encuentras las raíces para este polinomio y esas raíces para el polinomio son tus números x e y y z. Y entonces toda la complejidad está en hacer eso computacionalmente rápido.
También puedo explicar cómo encontrar raíces.
Si usted no tiene una característica 2 campo, entonces usted no puede utilizar el el endomorfismo para calcular la suma de las potencias de los otros..
P: ¿Se trata de un código BCH? ¿Cuáles son los parámetros del código? ¿Cómo lo describiría sucintamente?
R: En realidad no es un código BCH, pero se le parece mucho. Se podría decir que es uno en el que… la relación sólo ordena los elementos, pero es importante para la eficiencia. Es un código BCH en el que el tamaño del campo base es 2, el tamaño del campo de extensión que utilizas es el tamaño de tus elementos… no, espera, eso no está bien.
P: Podrías imaginar un código en el que el campo que utilizas no importa en absoluto. Podría ser un campo de 2^n.
R: La longitud del código es 2^20. El campo de extensión es sólo el número de elementos que estás actualmente…. Es una buena pregunta.
P: He aquí una manera tonta de ver esto. Piensa en los códigos Hamming.
R: Los códigos Hamming no son muy largos. Supongo que se pueden hacer más largos. Es una buena pregunta.
¿Por qué quieres hacer corrección y no detección? Si se detecta un error, entonces usted quiere conseguir de nuevo ¿no? El objetivo no es para las direcciones aquí. Esto se establece la reconciliación para las transacciones. Está utilizando un código BCH como bech32, pero es para otro propósito.