En este artículo, describo brevemente la necesidad de clientes ligeros en Bitcoin y por qué los "filtros de bloques compactos" satisfacen mejor esta necesidad que los "filtros Bloom". Luego explico en profundidad cómo funciona el filtro de bloque denso, con un tutorial paso a paso para construir dicho filtro en una red de prueba.
Significado de filtro de bloque
Un cliente de bitcoin light (software de bitcoin light) es un software cuyo objetivo no es almacenar la cadena de bloques de bitcoin, sino admitir una billetera de bitcoin. Esto significa que debe poder transmitir transacciones a la red, pero lo más importante, debe poder encontrar nuevas transacciones de la cadena relacionadas con esta billetera. Hay dos tipos de transacciones relacionadas: enviar fondos a esta billetera (crear una nueva salida para una dirección de esta billetera) y gastar uno de los UTXO controlados por esta billetera.
¿Qué hay de malo con los filtros de floración?
Antes de BIP 158, el enfoque más común para clientes ligeros era el filtro Bloom descrito en BIP 371. El patrón de un filtro Bloom es que usted toma todos los objetos de datos que le interesan (p. ej., las claves públicas del script de los UTXO que se gastaron y crearon), los codifica uno por uno varias veces y agrega cada resultado al In un mapa de bits llamado "filtro de floración". Este filtro representa lo que le interesa. Luego, envía este filtro a un nodo de Bitcoin en el que confía y les pide que le envíen todo lo que coincida con este filtro.
El problema es que este proceso no es muy privado, porque todavía se filtra cierta información al nodo de Bitcoin que acepta el filtro. Pueden conocer las ofertas que le interesan y las ofertas que no le interesan en absoluto; tampoco pueden enviarle cosas que coincidan con los filtros. Por lo tanto, no es ideal para clientes ligeros. Pero al mismo tiempo, no es ideal para los nodos de Bitcoin que atienden a clientes ligeros. Cada vez que envía un filtro, tienen que cargar el bloque relevante del disco y luego determinar si alguna transacción coincide con su filtro. Simplemente siga enviando filtros falsos y puede bombardearlos, esencialmente un ataque DOS. Se necesita muy poca energía para crear un filtro, pero se necesita mucha energía para responder a tal solicitud.
Filtro de bloque denso
OK, entonces los atributos que necesitamos son:
Mayor privacidad
La asimetría de carga cliente-servidor es menor. Es decir, debería haber menos trabajo por hacer en el lado del servidor.
Menos confianza. Los clientes ligeros no necesitan preocuparse de que el servidor no devuelva las transacciones relacionadas.
Usando un filtro de bloque denso, el servidor (nodo completo) construirá un filtro determinista para cada bloque, incluidos todos los objetos de datos en este bloque. Este filtro solo necesita calcularse una vez y almacenarse para siempre. Si un cliente ligero solicita un filtro para un determinado bloque, aquí no hay asimetría, porque el servidor no necesita hacer más trabajo que el cliente solicitante. El cliente ligero también puede elegir múltiples fuentes de información para descargar el bloque completo para garantizar que sean consistentes, además, el cliente ligero siempre puede descargar el bloque completo para verificar si el filtro proporcionado por el servidor es correcto. contenido). Otro beneficio es que es más privado de esta manera. El cliente ligero ya no necesita enviar la huella digital de los datos que quiere al servidor. También se vuelve más difícil analizar la actividad de un cliente ligero. Después de que el cliente ligero obtiene dicho filtro del servidor, verifica si el filtro contiene los datos que desea y, de ser así, el cliente ligero solicita el bloque completo. También se debe señalar que para atender a los clientes ligeros de esta manera, los nodos completos deben conservar estos filtros, y es posible que los clientes ligeros también deseen conservar algunos filtros, por lo que mantenga los filtros lo más ligeros posible. La cantidad es muy importante ( por eso se llama "filtro de bloque denso").
¡muy bien! Ahora nos estamos metiendo en las cosas raras. ¿Cómo se crea ese filtro? Cómo se ve?
¿Cuáles son nuestras necesidades?
Queremos poner la huella digital de un objeto específico en el filtro, de modo que cuando los clientes quieran comprobar si un bloque puede contener algo relacionado con ellos mismos, puedan enumerar todos los objetos y comprobar si un filtro coincide con estos objetos.
Queremos que este filtro sea lo más pequeño posible.
En esencia, lo que queremos es algo que pueda resumir alguna información de un bloque con un volumen mucho más pequeño que el bloque.
La información básica contenida en el filtro es: la clave pública del script de cada entrada de cada transacción (es decir, la clave pública del script de cada UTXO gastado) y la clave pública del script de cada salida de cada transacción. Básicamente es así:
objetos = {spk1, spk2, spk3, spk4, ..., spkN} // una lista de N claves públicas de script
Técnicamente, podemos detenernos aquí: esa lista de claves públicas de secuencia de comandos también puede actuar como nuestro filtro. Esta es una versión condensada de un bloque que contiene información que necesitan los clientes ligeros. Con tal lista, un cliente ligero puede confirmar al 100% si hay una transacción de interés en un bloque. Pero esa lista es muy grande. Por lo tanto, nuestros próximos pasos son todos para hacer esta lista lo más compacta posible. Aquí es donde las cosas se ponen interesantes.
Primero, podemos convertir cada objeto en un número dentro de un rango determinado y hacer que cada número de objeto se distribuya uniformemente dentro de este rango. Supongamos que tenemos 10 objetos (N = 10) y luego tenemos algún tipo de función que convierte cada objeto en un número. Digamos que elegimos el rango [0, 10] (ya que tenemos 10 objetos). Ahora, nuestra función "hash to number" tomará cada objeto como entrada y producirá un número con tamaño [0, 10] respectivamente. Los números se distribuyen uniformemente en este rango. Esto significa que, después de ordenar, terminaremos con un gráfico como este (en un caso muy, muy ideal):
En primer lugar, esto es genial porque hemos reducido drásticamente el tamaño de la huella digital de cada objeto. Ahora cada objeto es solo un número. Entonces, nuestro nuevo filtro se ve así:
numeros := {1,2,3,4,5,6,7,8,9,10}
Un cliente ligero descarga dicho filtro con la esperanza de saber si un objeto que está buscando coincide con el filtro. Simplemente toman el objeto que les interesa y ejecutan la misma función "hash to number" para ver si el resultado está en este filtro. ¿Dónde está el problema? ¡El problema es que los números en el filtro ya ocupan todas las posibilidades en ese espacio! Esto significa que, independientemente de los objetos que le interesen al cliente ligero, el resultado numérico resultante debe coincidir con este filtro. En otras palabras, este filtro tiene una "tasa de falsos positivos" de 1 (Nota del traductor: el "falso positivo" aquí significa que el bloque puede no contener El resultado obtenido por el filtro es sí). Esto no es tan bueno. También muestra que en el proceso de comprimir los datos para generar el filtro, perdimos demasiada información. Necesitamos una tasa de falsos positivos más alta. Luego, supongamos que queremos que la tasa de falsos positivos sea 5. Luego, podemos hacer que los objetos en el bloque coincidan uniformemente con números en el rango [0, 50]:
Se ve mejor así. Si soy un cliente y descargo dicho filtro, necesito verificar si un objeto que me importa está en el bloque correspondiente a través del filtro, y la probabilidad de que el filtro diga que sí pero no en el bloque (falso positivo) disminuirá a 1/5. Genial, ahora estamos asignando 10 objetos a números entre 0 y 50. Esta nueva lista de números es nuestro filtro. Nuevamente, podemos detenernos en cualquier momento, sin embargo, ¡podemos comprimirlos aún más!
Ahora tenemos una lista ordenada de números distribuidos uniformemente en el intervalo [0, 50]. Sabemos que hay 10 números en esta lista. Esto significa que podemos deducir que la diferencia entre dos números adyacentes en esta lista ordenada de números probablemente sea 5. En general, si tenemos N objetos y queremos una tasa de falsos positivos de M, entonces el tamaño del espacio debe ser N * M . Es decir, el tamaño de estos números debe estar entre 0 y N * M, pero (después de ordenar) la probabilidad de interpolación de dos números adyacentes marcados es M. Y M debe almacenarse más pequeño que el número en el espacio N * M. Entonces, en lugar de almacenar cada número, podemos almacenar la diferencia entre dos números adyacentes. En el ejemplo anterior, esto significa que en lugar de almacenar [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] como filtro, almacenamos [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], a partir del cual es trivial reconstruir la lista inicial. Si reduce la escala, almacenar el número 50 obviamente ocupa más espacio que almacenar el número 5. Pero ¿por qué detenerse allí? ¡Comprimamos un poco más!
El siguiente paso es utilizar la "codificación Golomb-Rice". Este método de codificación puede codificar bien una lista en la que cada número de la tabla está muy cerca de un número determinado. ¡Y nuestra lista resulta ser solo eso! Es probable que cada uno de los números de nuestra lista esté cerca de 5 (o cerca de nuestra tasa de falsos positivos, que es M), así que tome el cociente de cada número por M (divida cada número entre 5 e ignore el resto), Lo más probable es que sea 0 (si el número es ligeramente inferior a 5) o 1 (si el número es ligeramente superior a 5). También es posible que el cociente sea 2, 3, etc., pero la probabilidad es mucho menor. ¡excelente! Entonces podemos aprovechar esto: usaremos la menor cantidad de bits posible para codificar cocientes más pequeños, mientras usamos más bitcoins para codificar cocientes más grandes, pero menos probables. Luego, también necesitamos codificar el resto (ya que queremos poder reconstruir toda la lista exactamente), que siempre estará en el rango [0, M - 1] (en este caso [0, 4]). Para el codificador, usamos las siguientes asignaciones:
El mapeo anterior es fácil de entender: el número de dígitos 1 indica el cociente que queremos codificar y 0 indica el final de la codificación del cociente. Entonces, para cada número en nuestra lista, podemos usar la tabla anterior para codificar el cociente y luego convertir el resto a binario usando un bittruck que puede representar un valor máximo de M-1. Aquí el resto es 4 y solo se necesitan 3 bits. Aquí hay una tabla que muestra los posibles restos y sus codificaciones para nuestro ejemplo:
Antes de pasar a un caso más realista, veamos si podemos recuperar nuestra lista original con este filtro.
Ahora lo que tenemos es "0000100001000010000100001000010000100001000010000". Conocemos el código Golomb-Rice y sabemos que M es 5 (ya que esto será de conocimiento público, conocido por todos los que usen esta construcción de filtro). Como sabemos que M es 5, sabemos que habrá 3 bits para codificar el resto. Entonces, podemos convertir este filtro en la siguiente lista de matriz "cociente-resto":
Muy bien querido, veamos cómo podemos construir un filtro de este tipo a partir de bloques.
El código completo utilizado aquí se puede encontrar en este repositorio de github. Solo mostraré algunos fragmentos de pseudocódigo aquí. El núcleo de este código es una función llamada constructFilter, que los clientes de bitcoin pueden usar para llamar a bitcoind y los bloques correspondientes. La función se ve así:
func constructFilter(bc *bitcoind.Bitcoind, bloque bitcoind.Block) ([]byte, error) {
// 1 recoge todos los objetos del bloque que queremos añadir a un filtro
// 2 Convertir estos objetos en números y ordenarlos
// 3 Obtener la diferencia entre dos números adyacentes en la lista de números ordenados
// 4 Use la codificación Golomb-Rice para codificar estas diferencias
}
Entonces, el primer paso es recopilar todos los objetos del bloque que queremos agregar al filtro. A partir de BIP, sabemos que estos objetos incluyen todas las claves públicas de script gastadas y todas las claves públicas de script de salida. El BIP también establece algunas reglas adicionales: omitimos las entradas a la transacción de coinbase (lo que no tiene sentido ya que no tiene entradas) y pasamos todas las salidas OP_RETURN. También deduplicamos datos. Si hay dos claves públicas de script idénticas, solo las agregamos una vez al filtro.
// lista de objetos que deseamos agregar al filtro
// Incluir todas las claves públicas de script gastadas y cada clave pública de script de salida
// Usamos un "mapa", que elimina las claves públicas duplicadas del script
objetos := hacer(mapa [string] estructura{})
// facilita cada transacción en el bloque
for i, tx := bloque de rango.Tx {
// Agregar clave pública de secuencia de comandos para cada salida
// en nuestra lista de objetos
for _, txOut := rango tx.Vout {
PubKey := txOut.PubKey
if len(PubKey) == 0 {
continuar
}
// Omitir si se emite OP_RETURN (0x6a)
si habla [0] == 0x6a {
continuar
}
objetos [skpStr] = estructura{}{}
}
// no agregue la entrada de la transacción coinbase
si yo == 0 {
continuar
}
// Para cada entrada, obtenga su clave pública de secuencia de comandos
para _, txIn := rango tx.Vin {
prevTx, err := bc.GetRawTransaction(txIn.Txid)
si yerra != nil {
devuelve cero, err
}
PubKey := prevTx.Vout[txIn.Vout].PubKey
if len(PubKey) == 0 {
continuar
}
objetos [spkStr] = estructura{}{}
}
}
Bien, ahora todos los objetos están recopilados. Ahora, definimos la variable N como la longitud del gráfico de objetos. Aquí, N es 85 .
El siguiente paso es convertir nuestro objeto en números que se distribuyen uniformemente en un intervalo. Nuevamente, el rango depende de cuán alta sea la tasa de falsos positivos que desee. BIP158 define la constante M como 784931. Esto significa que la probabilidad de un falso positivo es de 1 en 784931. Tal como lo hicimos antes, tomamos la tasa de falsos positivos M veces N y obtenemos el rango de distribución de todos los números. Definimos este rango como F, es decir, F = M * N . Aquí, F = 66719135. No voy a entrar en los detalles de las funciones que asignan objetos a números (puede encontrar los detalles en el repositorio de github vinculado anteriormente). Todo lo que necesita saber es que toma como entrada el objeto, la constante F (que define el alcance al que se debe asignar el objeto) y una clave (el bloque hash). Una vez que tenemos todos los números, ordenamos la lista en orden ascendente y luego creamos una nueva lista llamada diferencias que contiene la diferencia entre dos números adyacentes en la lista ordenada de números.
numeros := hacer([]uint64, 0, N)
// Iterar a través de todos los objetos y convertirlos en números distribuidos uniformemente en el rango [0, F]
// y almacenar estos números como lista de números
para o := rango de objetos {
// Usando la clave dada, número máximo (F) y bytes de objeto (o),
// convierte el objeto en un número entre 0 y F.
v := convertToNumber(b, F, clave)
números = agregar (números, v)
}
// ordenar la lista de números
sort.Slice(numbers, func(i, j int) bool { devolver números [i] < números [j] })
// Convierte la lista de números en una lista de diferencias
diferencias := hacer([]uint64, N)
para i, num := numeros de rango {
si yo == 0 {
diferencias [i] = número
continuar
}
diferencias [i] = número - números[i-1]
}
¡excelente! Aquí hay una imagen que muestra una lista de números y diferencias.
A medida que se aleja, los 85 números se distribuyen uniformemente por todo el espacio. Entonces los valores en la lista de diferencias también son muy pequeños.
El paso final es codificar la lista de diferencias utilizando la codificación Golomb-Rice. Recuerda de la explicación anterior que necesitamos dividir cada diferencia por el valor más probable y luego codificar el cociente y el resto. En nuestro ejemplo anterior, dije que el valor más probable es M, y el resto estará entre [0, M]. Sin embargo, BIP158 no hace esto, ya que encontramos 2, que no es el parámetro que realmente minimiza el tamaño final del filtro. Entonces, en lugar de usar M, definimos una nueva constante P y usamos 2^P como el parámetro Golomb-Rice. P se define como 19 . Esto significa que dividimos cada diferencia por 2^19 para obtener el cociente y el resto, y el resto se codifica en binario con 19 bits.
filtro := bstream.NewBStreamWriter(0)
// Para cada valor en la lista de diferencias, obtenga el cociente y el resto dividiendo por 2^P.
for _, d := diferencias de rango {
q := matemáticas.Piso(flotante64(d)/matemáticas.Exp2(flotante64(P)))
r := d - uint64(matemáticas.Exp2(float64(P))*q)
// codificador
para yo := 0; yo < int(q); yo++ {
filtro.WriteBit(verdadero)
}
filtro.WriteBit(falso)
filtro.WriteBits(r, P)
}
¡excelente! Ahora podemos generar el filtro, obteniendo:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa 2e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
¡Exactamente el mismo filtro que obtuvimos en bitcoind excepto por los dos primeros bytes! ¿Por qué hay una diferencia en los primeros 2 bytes? Porque BIP dice que el valor de N debe codificarse en formato CompactSize y aparecer frente al filtro para que el receptor pueda decodificarlo. Esto se hace por:
Sin embargo, mi entendimiento personal es que no hay necesidad de agregar N al filtro. Si conoce el valor de P, entonces puede encontrar el valor de N. Veamos si podemos restaurar la lista original de números usando la salida del primer filtro:
b := bstream.NewBStreamReader(filtro)
(
números []uint64
prevNum uint64
)
para {
// Leer el cociente de la cadena de bytes. El primer 0 encontrado indica el final del cociente
// Antes de encontrar el 0, el número 1 representa el cociente
q uint64
c, err := b.ReadBit()
si yerra != nil {
error de retorno
}
para c {
q++
c, err = b.ReadBit()
si errores.Es (err, io.EOF) {
romper
} else if err != nil {
error de retorno
}
}
// Los siguientes P bits codifican el resto
r, err := b.ReadBits(P)
si errores.Es (err, io.EOF) {
romper
} else if err != nil {
error de retorno
}
n := q*uint64(math.Exp2(float64(P))) + r
num := n + prevNum
números = agregar (números, número)
numprev = num
}
fmt.Println(números)
La operación anterior produce la misma lista de números, por lo que podemos reconstruirla sin conocer N. Entonces, no estoy seguro de cuál es la razón para agregar N al filtro. Si sabe por qué se debe incluir N, ¡hágamelo saber!
¡Gracias por leer!
Ver originales
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Explicación del filtro de bloque denso BIP 158
Por Elle Mouton
En este artículo, describo brevemente la necesidad de clientes ligeros en Bitcoin y por qué los "filtros de bloques compactos" satisfacen mejor esta necesidad que los "filtros Bloom". Luego explico en profundidad cómo funciona el filtro de bloque denso, con un tutorial paso a paso para construir dicho filtro en una red de prueba.
Significado de filtro de bloque
Un cliente de bitcoin light (software de bitcoin light) es un software cuyo objetivo no es almacenar la cadena de bloques de bitcoin, sino admitir una billetera de bitcoin. Esto significa que debe poder transmitir transacciones a la red, pero lo más importante, debe poder encontrar nuevas transacciones de la cadena relacionadas con esta billetera. Hay dos tipos de transacciones relacionadas: enviar fondos a esta billetera (crear una nueva salida para una dirección de esta billetera) y gastar uno de los UTXO controlados por esta billetera.
¿Qué hay de malo con los filtros de floración?
Antes de BIP 158, el enfoque más común para clientes ligeros era el filtro Bloom descrito en BIP 371. El patrón de un filtro Bloom es que usted toma todos los objetos de datos que le interesan (p. ej., las claves públicas del script de los UTXO que se gastaron y crearon), los codifica uno por uno varias veces y agrega cada resultado al In un mapa de bits llamado "filtro de floración". Este filtro representa lo que le interesa. Luego, envía este filtro a un nodo de Bitcoin en el que confía y les pide que le envíen todo lo que coincida con este filtro.
El problema es que este proceso no es muy privado, porque todavía se filtra cierta información al nodo de Bitcoin que acepta el filtro. Pueden conocer las ofertas que le interesan y las ofertas que no le interesan en absoluto; tampoco pueden enviarle cosas que coincidan con los filtros. Por lo tanto, no es ideal para clientes ligeros. Pero al mismo tiempo, no es ideal para los nodos de Bitcoin que atienden a clientes ligeros. Cada vez que envía un filtro, tienen que cargar el bloque relevante del disco y luego determinar si alguna transacción coincide con su filtro. Simplemente siga enviando filtros falsos y puede bombardearlos, esencialmente un ataque DOS. Se necesita muy poca energía para crear un filtro, pero se necesita mucha energía para responder a tal solicitud.
Filtro de bloque denso
OK, entonces los atributos que necesitamos son:
Usando un filtro de bloque denso, el servidor (nodo completo) construirá un filtro determinista para cada bloque, incluidos todos los objetos de datos en este bloque. Este filtro solo necesita calcularse una vez y almacenarse para siempre. Si un cliente ligero solicita un filtro para un determinado bloque, aquí no hay asimetría, porque el servidor no necesita hacer más trabajo que el cliente solicitante. El cliente ligero también puede elegir múltiples fuentes de información para descargar el bloque completo para garantizar que sean consistentes, además, el cliente ligero siempre puede descargar el bloque completo para verificar si el filtro proporcionado por el servidor es correcto. contenido). Otro beneficio es que es más privado de esta manera. El cliente ligero ya no necesita enviar la huella digital de los datos que quiere al servidor. También se vuelve más difícil analizar la actividad de un cliente ligero. Después de que el cliente ligero obtiene dicho filtro del servidor, verifica si el filtro contiene los datos que desea y, de ser así, el cliente ligero solicita el bloque completo. También se debe señalar que para atender a los clientes ligeros de esta manera, los nodos completos deben conservar estos filtros, y es posible que los clientes ligeros también deseen conservar algunos filtros, por lo que mantenga los filtros lo más ligeros posible. La cantidad es muy importante ( por eso se llama "filtro de bloque denso").
¡muy bien! Ahora nos estamos metiendo en las cosas raras. ¿Cómo se crea ese filtro? Cómo se ve?
¿Cuáles son nuestras necesidades?
La información básica contenida en el filtro es: la clave pública del script de cada entrada de cada transacción (es decir, la clave pública del script de cada UTXO gastado) y la clave pública del script de cada salida de cada transacción. Básicamente es así:
objetos = {spk1, spk2, spk3, spk4, ..., spkN} // una lista de N claves públicas de script
Técnicamente, podemos detenernos aquí: esa lista de claves públicas de secuencia de comandos también puede actuar como nuestro filtro. Esta es una versión condensada de un bloque que contiene información que necesitan los clientes ligeros. Con tal lista, un cliente ligero puede confirmar al 100% si hay una transacción de interés en un bloque. Pero esa lista es muy grande. Por lo tanto, nuestros próximos pasos son todos para hacer esta lista lo más compacta posible. Aquí es donde las cosas se ponen interesantes.
Primero, podemos convertir cada objeto en un número dentro de un rango determinado y hacer que cada número de objeto se distribuya uniformemente dentro de este rango. Supongamos que tenemos 10 objetos (N = 10) y luego tenemos algún tipo de función que convierte cada objeto en un número. Digamos que elegimos el rango [0, 10] (ya que tenemos 10 objetos). Ahora, nuestra función "hash to number" tomará cada objeto como entrada y producirá un número con tamaño [0, 10] respectivamente. Los números se distribuyen uniformemente en este rango. Esto significa que, después de ordenar, terminaremos con un gráfico como este (en un caso muy, muy ideal):
numeros := {1,2,3,4,5,6,7,8,9,10}
Un cliente ligero descarga dicho filtro con la esperanza de saber si un objeto que está buscando coincide con el filtro. Simplemente toman el objeto que les interesa y ejecutan la misma función "hash to number" para ver si el resultado está en este filtro. ¿Dónde está el problema? ¡El problema es que los números en el filtro ya ocupan todas las posibilidades en ese espacio! Esto significa que, independientemente de los objetos que le interesen al cliente ligero, el resultado numérico resultante debe coincidir con este filtro. En otras palabras, este filtro tiene una "tasa de falsos positivos" de 1 (Nota del traductor: el "falso positivo" aquí significa que el bloque puede no contener El resultado obtenido por el filtro es sí). Esto no es tan bueno. También muestra que en el proceso de comprimir los datos para generar el filtro, perdimos demasiada información. Necesitamos una tasa de falsos positivos más alta. Luego, supongamos que queremos que la tasa de falsos positivos sea 5. Luego, podemos hacer que los objetos en el bloque coincidan uniformemente con números en el rango [0, 50]:
Ahora tenemos una lista ordenada de números distribuidos uniformemente en el intervalo [0, 50]. Sabemos que hay 10 números en esta lista. Esto significa que podemos deducir que la diferencia entre dos números adyacentes en esta lista ordenada de números probablemente sea 5. En general, si tenemos N objetos y queremos una tasa de falsos positivos de M, entonces el tamaño del espacio debe ser N * M . Es decir, el tamaño de estos números debe estar entre 0 y N * M, pero (después de ordenar) la probabilidad de interpolación de dos números adyacentes marcados es M. Y M debe almacenarse más pequeño que el número en el espacio N * M. Entonces, en lugar de almacenar cada número, podemos almacenar la diferencia entre dos números adyacentes. En el ejemplo anterior, esto significa que en lugar de almacenar [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] como filtro, almacenamos [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], a partir del cual es trivial reconstruir la lista inicial. Si reduce la escala, almacenar el número 50 obviamente ocupa más espacio que almacenar el número 5. Pero ¿por qué detenerse allí? ¡Comprimamos un poco más!
El siguiente paso es utilizar la "codificación Golomb-Rice". Este método de codificación puede codificar bien una lista en la que cada número de la tabla está muy cerca de un número determinado. ¡Y nuestra lista resulta ser solo eso! Es probable que cada uno de los números de nuestra lista esté cerca de 5 (o cerca de nuestra tasa de falsos positivos, que es M), así que tome el cociente de cada número por M (divida cada número entre 5 e ignore el resto), Lo más probable es que sea 0 (si el número es ligeramente inferior a 5) o 1 (si el número es ligeramente superior a 5). También es posible que el cociente sea 2, 3, etc., pero la probabilidad es mucho menor. ¡excelente! Entonces podemos aprovechar esto: usaremos la menor cantidad de bits posible para codificar cocientes más pequeños, mientras usamos más bitcoins para codificar cocientes más grandes, pero menos probables. Luego, también necesitamos codificar el resto (ya que queremos poder reconstruir toda la lista exactamente), que siempre estará en el rango [0, M - 1] (en este caso [0, 4]). Para el codificador, usamos las siguientes asignaciones:
0000 10000 10000 10000 10000 10000 10000 10000 10000 10000
Antes de pasar a un caso más realista, veamos si podemos recuperar nuestra lista original con este filtro.
Ahora lo que tenemos es "0000100001000010000100001000010000100001000010000". Conocemos el código Golomb-Rice y sabemos que M es 5 (ya que esto será de conocimiento público, conocido por todos los que usen esta construcción de filtro). Como sabemos que M es 5, sabemos que habrá 3 bits para codificar el resto. Entonces, podemos convertir este filtro en la siguiente lista de matriz "cociente-resto":
[(0, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), ( 1, 0), (1, 0)]
Sabiendo que el cociente se obtiene dividiendo por M(5), podemos recuperar:
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Además, sabemos que esta lista representa la diferencia entre dos números adyacentes, por lo que podemos restaurar la lista original:
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Un ejemplo más realista
Ahora vamos a intentar construir un filtro para un bloque de red de prueba de Bitcoin real. Usaré el bloque 2101914. Veamos cómo se ve su filtro:
$ bitcoin-cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ bitcoin-cli getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { "filtro": "5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864 023833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a 5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b5 6ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", "encabezado": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }
Muy bien querido, veamos cómo podemos construir un filtro de este tipo a partir de bloques.
El código completo utilizado aquí se puede encontrar en este repositorio de github. Solo mostraré algunos fragmentos de pseudocódigo aquí. El núcleo de este código es una función llamada constructFilter, que los clientes de bitcoin pueden usar para llamar a bitcoind y los bloques correspondientes. La función se ve así:
func constructFilter(bc *bitcoind.Bitcoind, bloque bitcoind.Block) ([]byte, error) { // 1 recoge todos los objetos del bloque que queremos añadir a un filtro // 2 Convertir estos objetos en números y ordenarlos // 3 Obtener la diferencia entre dos números adyacentes en la lista de números ordenados // 4 Use la codificación Golomb-Rice para codificar estas diferencias }
Entonces, el primer paso es recopilar todos los objetos del bloque que queremos agregar al filtro. A partir de BIP, sabemos que estos objetos incluyen todas las claves públicas de script gastadas y todas las claves públicas de script de salida. El BIP también establece algunas reglas adicionales: omitimos las entradas a la transacción de coinbase (lo que no tiene sentido ya que no tiene entradas) y pasamos todas las salidas OP_RETURN. También deduplicamos datos. Si hay dos claves públicas de script idénticas, solo las agregamos una vez al filtro.
// lista de objetos que deseamos agregar al filtro // Incluir todas las claves públicas de script gastadas y cada clave pública de script de salida // Usamos un "mapa", que elimina las claves públicas duplicadas del script objetos := hacer(mapa [string] estructura{}) // facilita cada transacción en el bloque for i, tx := bloque de rango.Tx { // Agregar clave pública de secuencia de comandos para cada salida // en nuestra lista de objetos for _, txOut := rango tx.Vout { PubKey := txOut.PubKey if len(PubKey) == 0 { continuar } // Omitir si se emite OP_RETURN (0x6a) si habla [0] == 0x6a { continuar } objetos [skpStr] = estructura{}{} } // no agregue la entrada de la transacción coinbase si yo == 0 { continuar } // Para cada entrada, obtenga su clave pública de secuencia de comandos para _, txIn := rango tx.Vin { prevTx, err := bc.GetRawTransaction(txIn.Txid) si yerra != nil { devuelve cero, err } PubKey := prevTx.Vout[txIn.Vout].PubKey if len(PubKey) == 0 { continuar } objetos [spkStr] = estructura{}{} } }
Bien, ahora todos los objetos están recopilados. Ahora, definimos la variable N como la longitud del gráfico de objetos. Aquí, N es 85 .
El siguiente paso es convertir nuestro objeto en números que se distribuyen uniformemente en un intervalo. Nuevamente, el rango depende de cuán alta sea la tasa de falsos positivos que desee. BIP158 define la constante M como 784931. Esto significa que la probabilidad de un falso positivo es de 1 en 784931. Tal como lo hicimos antes, tomamos la tasa de falsos positivos M veces N y obtenemos el rango de distribución de todos los números. Definimos este rango como F, es decir, F = M * N . Aquí, F = 66719135. No voy a entrar en los detalles de las funciones que asignan objetos a números (puede encontrar los detalles en el repositorio de github vinculado anteriormente). Todo lo que necesita saber es que toma como entrada el objeto, la constante F (que define el alcance al que se debe asignar el objeto) y una clave (el bloque hash). Una vez que tenemos todos los números, ordenamos la lista en orden ascendente y luego creamos una nueva lista llamada diferencias que contiene la diferencia entre dos números adyacentes en la lista ordenada de números.
numeros := hacer([]uint64, 0, N) // Iterar a través de todos los objetos y convertirlos en números distribuidos uniformemente en el rango [0, F] // y almacenar estos números como lista de números para o := rango de objetos { // Usando la clave dada, número máximo (F) y bytes de objeto (o), // convierte el objeto en un número entre 0 y F. v := convertToNumber(b, F, clave) números = agregar (números, v) } // ordenar la lista de números sort.Slice(numbers, func(i, j int) bool { devolver números [i] < números [j] }) // Convierte la lista de números en una lista de diferencias diferencias := hacer([]uint64, N) para i, num := numeros de rango { si yo == 0 { diferencias [i] = número continuar } diferencias [i] = número - números[i-1] }
¡excelente! Aquí hay una imagen que muestra una lista de números y diferencias.
El paso final es codificar la lista de diferencias utilizando la codificación Golomb-Rice. Recuerda de la explicación anterior que necesitamos dividir cada diferencia por el valor más probable y luego codificar el cociente y el resto. En nuestro ejemplo anterior, dije que el valor más probable es M, y el resto estará entre [0, M]. Sin embargo, BIP158 no hace esto, ya que encontramos 2, que no es el parámetro que realmente minimiza el tamaño final del filtro. Entonces, en lugar de usar M, definimos una nueva constante P y usamos 2^P como el parámetro Golomb-Rice. P se define como 19 . Esto significa que dividimos cada diferencia por 2^19 para obtener el cociente y el resto, y el resto se codifica en binario con 19 bits.
filtro := bstream.NewBStreamWriter(0) // Para cada valor en la lista de diferencias, obtenga el cociente y el resto dividiendo por 2^P. for _, d := diferencias de rango { q := matemáticas.Piso(flotante64(d)/matemáticas.Exp2(flotante64(P))) r := d - uint64(matemáticas.Exp2(float64(P))*q) // codificador para yo := 0; yo < int(q); yo++ { filtro.WriteBit(verdadero) } filtro.WriteBit(falso) filtro.WriteBits(r, P) }
¡excelente! Ahora podemos generar el filtro, obteniendo:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa 2e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
¡Exactamente el mismo filtro que obtuvimos en bitcoind excepto por los dos primeros bytes! ¿Por qué hay una diferencia en los primeros 2 bytes? Porque BIP dice que el valor de N debe codificarse en formato CompactSize y aparecer frente al filtro para que el receptor pueda decodificarlo. Esto se hace por:
fd := filtro.Bytes() bytes de búfer.Buffer buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) err = cable.WriteInt(&buffer, 0, uint64(N)) si yerra != nil { devuelve cero, err } _, err = búfer.Escribir(fd) si yerra != nil { devuelve cero, err }
Si ahora imprimimos el filtro nuevamente, encontraremos que es exactamente el mismo que el resultado de bitcoind:
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df5743786402383 3f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade1 2fa 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
¡éxito!
Sin embargo, mi entendimiento personal es que no hay necesidad de agregar N al filtro. Si conoce el valor de P, entonces puede encontrar el valor de N. Veamos si podemos restaurar la lista original de números usando la salida del primer filtro:
b := bstream.NewBStreamReader(filtro) ( números []uint64 prevNum uint64 ) para { // Leer el cociente de la cadena de bytes. El primer 0 encontrado indica el final del cociente // Antes de encontrar el 0, el número 1 representa el cociente q uint64 c, err := b.ReadBit() si yerra != nil { error de retorno } para c { q++ c, err = b.ReadBit() si errores.Es (err, io.EOF) { romper } else if err != nil { error de retorno } } // Los siguientes P bits codifican el resto r, err := b.ReadBits(P) si errores.Es (err, io.EOF) { romper } else if err != nil { error de retorno } n := q*uint64(math.Exp2(float64(P))) + r num := n + prevNum números = agregar (números, número) numprev = num } fmt.Println(números)
La operación anterior produce la misma lista de números, por lo que podemos reconstruirla sin conocer N. Entonces, no estoy seguro de cuál es la razón para agregar N al filtro. Si sabe por qué se debe incluir N, ¡hágamelo saber!
¡Gracias por leer!