Neste artigo, descrevo brevemente a necessidade de clientes leves no Bitcoin e por que os "filtros de blocos compactos" atendem melhor a essa necessidade do que os "filtros Bloom". Em seguida, explico detalhadamente como funciona o filtro de bloco denso, com uma explicação passo a passo da construção desse filtro em uma rede de teste.
Significado do filtro de bloco
Um cliente bitcoin light (software bitcoin light) é um software cujo objetivo não é armazenar o blockchain bitcoin, mas dar suporte a uma carteira bitcoin. Isso significa que ele precisa ser capaz de transmitir transações para a rede, mas o mais importante, deve ser capaz de encontrar novas transações da cadeia relacionadas a esta carteira. Existem dois tipos de transações relacionadas: enviar fundos para esta carteira (criando uma nova saída para um endereço desta carteira) e gastar um dos UTXOs controlados por esta carteira.
O que há de errado com os filtros bloom?
Antes do BIP 158, a abordagem mais comum para clientes leves era o filtro Bloom descrito no BIP 371. O padrão de um filtro Bloom é que você pegue todos os objetos de dados nos quais está interessado (por exemplo, as chaves públicas do script dos UTXOs que foram gastos e criados), faça hash deles um por um várias vezes e adicione cada resultado ao In um bitmap chamado "filtro de florescimento". Este filtro representa o que você está interessado. Em seguida, você envia esse filtro para um nodo Bitcoin em que confia e pede que ele envie tudo o que corresponde a esse filtro.
O problema é que esse processo não é muito privado, pois você ainda vaza algumas informações para o nodo Bitcoin que aceita o filtro. Eles podem saber negócios nos quais você está interessado e negócios nos quais você não está interessado; eles também podem não enviar coisas que correspondam aos filtros. Portanto, não é ideal para clientes leves. Mas, ao mesmo tempo, não é ideal para nós Bitcoin que atendem a clientes leves. Toda vez que você envia um filtro, eles precisam carregar o bloco relevante do disco e determinar se alguma transação corresponde ao seu filtro. Continue enviando filtros falsos e você pode bombardeá-los - essencialmente um ataque do DOS. É preciso muito pouca energia para criar um filtro, mas é preciso muita energia para responder a tal solicitação.
Filtro de bloco denso
OK, então os atributos que precisamos são:
Privacidade mais forte
A assimetria de carga cliente-servidor é menor. Ou seja, deve haver menos trabalho a ser feito no lado do servidor.
Menos confiança. Os clientes leves não precisam se preocupar com o fato de o servidor não retornar transações relacionadas.
Usando um filtro de bloco denso, o servidor (nó completo) irá construir um filtro determinístico para cada bloco, incluindo todos os objetos de dados neste bloco. Este filtro só precisa ser calculado uma vez e armazenado para sempre. Se um cliente leve solicita um filtro para um determinado bloco, não há assimetria aqui - porque o servidor não precisa fazer mais trabalho do que o cliente solicitante. O light client também pode escolher várias fontes de informação para baixar o bloco completo para garantir que sejam consistentes, além disso, o light client sempre pode baixar o bloco completo para verificar se o filtro fornecido pelo servidor está correto. Correto (corresponde ao bloco relevante contente). Outro benefício é que é mais privado desta forma. O light client não precisa mais enviar a impressão digital dos dados que deseja para o servidor. Também fica mais difícil analisar a atividade de um cliente leve. Depois que o light client obtém tal filtro do servidor, ele verifica se o filtro contém os dados que deseja e, em caso afirmativo, o light client solicita o bloco completo. Também deve ser apontado que, para atender clientes leves dessa maneira, nós completos precisam persistir esses filtros, e clientes leves também podem querer persistir alguns filtros, portanto, mantenha os filtros o mais leve possível A quantidade é muito importante ( é por isso que é chamado de "filtro de bloco denso").
muito bom! Agora estamos entrando no material raro. Como esse filtro é criado? Com o que se parece?
Quais são as nossas necessidades?
Queremos colocar a impressão digital de um objeto específico no filtro, para que quando os clientes quiserem verificar se um bloco pode conter algo relacionado a eles mesmos, eles possam enumerar todos os objetos e verificar em um filtro Se devem corresponder a esses objetos.
Queremos que este filtro seja o menor possível.
Em essência, o que queremos é algo que possa resumir algumas informações de um bloco com um volume bem menor que o bloco.
As informações básicas contidas no filtro são: a chave pública do script de cada entrada de cada transação (ou seja, a chave pública do script de cada UTXO gasto) e a chave pública do script de cada saída de cada transação. Basicamente é assim:
objects = {spk1, spk2, spk3, spk4, ..., spkN} // uma lista de N chaves públicas de script
Tecnicamente, podemos parar aqui - apenas uma lista de chaves públicas de script também pode atuar como nosso filtro. Esta é uma versão condensada de um bloco que contém informações necessárias para clientes leves. Com essa lista, um cliente light pode confirmar 100% se existe uma transação de interesse em um bloco. Mas essa lista é muito grande. Portanto, nossos próximos passos são todos para tornar esta lista o mais compacta possível. É onde as coisas começam a ficar interessantes.
Primeiro, podemos converter cada objeto em um número dentro de um determinado intervalo e fazer com que cada número de objeto seja distribuído uniformemente dentro desse intervalo. Suponha que temos 10 objetos (N = 10) e então temos algum tipo de função que converte cada objeto em um número. Digamos que escolhemos o intervalo [0, 10] (já que temos 10 objetos). Agora, nossa função "hash to number" receberá cada objeto como entrada e produzirá um número com tamanho [0, 10] respectivamente. Os números são distribuídos uniformemente por esse intervalo. Isso significa que, após a ordenação, teremos um gráfico como este (em um caso muito, muito ideal):
Em primeiro lugar, isso é ótimo porque reduzimos drasticamente o tamanho da impressão digital de cada objeto. Agora cada objeto é apenas um número. Então, nosso novo filtro fica assim:
números:= {1,2,3,4,5,6,7,8,9,10}
Um cliente leve baixa esse filtro, esperando saber se um objeto que está procurando corresponde ao filtro. Eles apenas pegam o objeto em que estão interessados e executam a mesma função "hash to number" para ver se o resultado está neste filtro. Onde está o problema? O problema é que os números do filtro já ocupam todas as possibilidades daquele espaço! Isso significa que não importa com quais objetos o light client se preocupa, o resultado numérico resultante deve corresponder a esse filtro. Em outras palavras, este filtro tem uma "taxa de falso-positivo" de 1 (Nota do tradutor: O "falso positivo" aqui significa que o bloco pode não conter O resultado obtido pelo filtro é sim). Isso não é tão bom. Também mostra que no processo de compressão dos dados para gerar o filtro, perdemos muita informação. Precisamos de uma taxa de falsos positivos mais alta. Então, suponha que queremos que a taxa de falsos positivos seja 5. Então, podemos fazer com que os objetos no bloco correspondam uniformemente aos números no intervalo [0, 50]:
Parece melhor assim. Se eu for um cliente e baixar tal filtro, preciso verificar se um objeto que me interessa está no bloco correspondente por meio do filtro, e a probabilidade do filtro dizer sim, mas não no bloco (falso positivo) diminuirá para 1/5. Ótimo, agora estamos mapeando 10 objetos para números entre 0 e 50. Esta nova lista de números é o nosso filtro. Novamente, podemos parar a qualquer momento, porém, podemos comprimi-los ainda mais!
Agora temos uma lista ordenada de números uniformemente distribuídos no intervalo [0, 50]. Sabemos que existem 10 números nesta lista. Isso significa que podemos deduzir que a diferença entre dois números adjacentes nesta lista ordenada de números provavelmente é 5. Em geral, se tivermos N objetos e quisermos uma taxa de falsos positivos de M, o tamanho do espaço deve ser N * M . Ou seja, o tamanho desses números deve estar entre 0 e N * M, mas (após a classificação) a probabilidade de interpolação de dois números adjacentes verificados é M. E M deve ser armazenado menor que o número no espaço N * M. Assim, em vez de armazenar cada número, podemos armazenar a diferença entre dois números adjacentes. No exemplo acima, isso significa que, em vez de armazenar [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] como um filtro, armazenamos [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], a partir do qual é trivial reconstruir a lista inicial. Se você reduzir, armazenar o número 50 obviamente ocupa mais espaço do que armazenar o número 5. Mas por que parar por aí? Vamos comprimir um pouco mais!
O próximo passo é usar a "codificação Golomb-Rice". Esse método de codificação pode codificar bem uma lista em que cada número na tabela está muito próximo de um determinado número. E nossa lista é exatamente isso! Cada um dos números em nossa lista provavelmente está próximo de 5 (ou próximo de nossa taxa de falsos positivos, que é M), então pegue o quociente de cada número por M (divida cada número por 5 e ignore o resto), provavelmente será 0 (se o número for um pouco menor que 5) ou 1 (se o número for um pouco maior que 5). Também é possível que o quociente seja 2, 3, etc., mas a probabilidade é muito menor. ótimo! Portanto, podemos tirar proveito disso: usaremos o mínimo possível de bits para codificar quocientes menores, enquanto usamos mais bitcoins para codificar quocientes maiores, mas menos prováveis. Em seguida, também precisamos codificar o restante (já que queremos poder reconstruir a lista inteira exatamente), que sempre estará no intervalo [0, M - 1] (neste caso [0, 4]). Para o codificador, usamos os seguintes mapeamentos:
O mapeamento acima é fácil de entender: o número de dígitos 1 indica o quociente que queremos codificar e 0 indica o final da codificação do quociente. Portanto, para cada número em nossa lista, podemos usar a tabela acima para codificar o quociente e, em seguida, converter o restante em binário usando um bittruck que pode representar um valor máximo de M-1. Aqui o resto é 4, e apenas 3 bits são necessários. Aqui está uma tabela mostrando os possíveis restos e suas codificações para o nosso exemplo:
Portanto, idealmente, nossa lista [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] seria codificada como:
Antes de passarmos para um caso mais realista, vamos ver se conseguimos recuperar nossa lista original com este filtro.
Agora o que temos é "000010000100001000010000100001000010000100001000010000". Conhecemos o código Golomb-Rice e sabemos que M é 5 (já que isso será de conhecimento público, conhecido por todos que usam essa construção de filtro). Como sabemos que M é 5, sabemos que haverá 3 bits para codificar o restante. Assim, podemos converter este filtro na seguinte lista de matrizes "quociente-restante":
Tudo bem querida, vamos ver como podemos construir tal filtro de blocos.
O código completo usado aqui pode ser encontrado neste repositório github. Vou apenas mostrar alguns trechos de pseudocódigo aqui. O núcleo desse código é uma função chamada constructFilter, que pode ser usada por clientes bitcoin para chamar bitcoind e os blocos correspondentes. A função fica assim:
func constructFilter(bc *bitcoind.Bitcoind, bloco bitcoind.Block) ([]byte, erro) {
// 1 coleta todos os objetos do bloco que queremos adicionar a um filtro
// 2 Converte esses objetos em números e os classifica
// 3 Obtém a diferença entre dois números adjacentes na lista de números ordenados
// 4 Use a codificação Golomb-Rice para codificar essas diferenças
}
Assim, o primeiro passo é coletar todos os objetos do bloco que queremos adicionar ao filtro. A partir do BIP, sabemos que esses objetos incluem todas as chaves públicas de script gastas e todas as chaves públicas de script de saída. O BIP também define algumas regras adicionais: ignoramos as entradas para a transação coinbase (o que não faz sentido, pois não possui entradas) e passamos todas as saídas OP_RETURN. Também desduplicamos dados. Se houver duas chaves públicas de script idênticas, adicionamos apenas uma vez ao filtro.
// lista de objetos que desejamos adicionar ao filtro
// Inclui todas as chaves públicas de script gastas e todas as chaves públicas de script de saída
// Usamos um "mapa", que remove chaves públicas de script duplicadas
objetos := make(mapa [string] estrutura{})
// facilita todas as transações no bloco
para i, tx := intervalo de bloco.Tx {
// Adiciona a chave pública do script para cada saída
// em nossa lista de objetos
for _, txOut := range tx.Vout {
PubKey := txOut.PubKey
if len(PubKey) == 0 {
continuar
}
// Ignora se OP_RETURN (0x6a) é a saída
se falar [0] == 0x6a {
continuar
}
objetos [skpStr] = estrutura{}{}
}
// não adiciona a entrada da transação coinbase
se eu == 0 {
continuar
}
// Para cada entrada, obtém sua chave pública de script
para _, txIn := intervalo tx.Vin {
prevTx, err := bc.GetRawTransaction(txIn.Txid)
se errar != nil {
retorno nulo, erro
}
PubKey := prevTx.Vout[txIn.Vout].PubKey
if len(PubKey) == 0 {
continuar
}
objetos [spkStr] = estrutura{}{}
}
}
OK, agora todos os objetos são coletados. Agora, definimos a variável N como sendo o comprimento do grafo do objeto. Aqui, N é 85 .
O próximo passo é converter nosso objeto em números uniformemente distribuídos em um intervalo. Novamente, o intervalo depende de quão alta é a taxa de falsos positivos que você deseja. BIP158 define a constante M como 784931. Isso significa que a probabilidade de um falso positivo é de 1 em 784931. Assim como fizemos antes, pegamos a taxa de falsos positivos M vezes N e obtemos o intervalo de distribuição de todos os números. Definimos esse intervalo como F, ou seja, F = M * N . Aqui, F = 66719135. Não vou entrar em detalhes das funções que mapeiam objetos para números (você pode encontrar os detalhes no repositório do github vinculado acima). Tudo o que você precisa saber é que ele recebe como entrada o objeto, a constante F (que define o escopo para o qual o objeto precisa ser mapeado) e uma chave (o hash do bloco). Assim que tivermos todos os números, classificamos a lista em ordem crescente e, em seguida, criamos uma nova lista chamada diferenças que contém a diferença entre dois números adjacentes na lista de números classificados.
números := make([]uint64, 0, N)
// Percorre todos os objetos e os converte em números uniformemente distribuídos no intervalo [0, F]
// e armazena esses números como uma lista de números
para o := objetos de alcance {
// Usando a chave fornecida, número máximo (F) e bytes de objeto (o),
// converte o objeto para um número entre 0 e F.
v := convertToNumber(b, F, chave)
números = append(números, v)
}
// ordena a lista de números
sort.Slice(números, func(i, j int) bool { return números [i] < números [j] })
// Converte a lista de números em uma lista de diferenças
diferenças := make([]uint64, N)
para i, num := números de intervalo {
se eu == 0 {
diferenças [i] = num
continuar
}
diferenças [i] = num - números[i-1]
}
ótimo! Aqui está uma imagem mostrando uma lista de números e diferenças.
À medida que você diminui o zoom, os 85 números são distribuídos uniformemente por todo o espaço! Portanto, os valores na lista de diferenças também são muito pequenos.
A etapa final é codificar a lista de diferenças usando a codificação Golomb-Rice. Lembre-se da explicação anterior de que precisamos dividir cada diferença pelo valor mais provável e, em seguida, codificar o quociente e o resto. Em nosso exemplo anterior, eu disse que o valor mais provável é M, e o restante ficará entre [0, M]. No entanto, o BIP158 não faz isso, pois encontramos 2, que não é o parâmetro que realmente minimiza o tamanho final do filtro. Portanto, em vez de usar M, definimos uma nova constante P e usamos 2^P como o parâmetro Golomb-Rice. P é definido como 19 . Isso significa que dividimos cada diferença por 2 ^ 19 para obter o quociente e o resto, e o resto é codificado em binário com 19 bits.
filtro := bstream.NewBStreamWriter(0)
// Para cada valor na lista de diferenças, obtenha o quociente e o resto dividindo por 2^P.
para _, d := diferenças de alcance {
q := math.Floor(float64(d)/math.Exp2(float64(P)))
r := d - uint64(math.Exp2(float64(P))*q)
// Codificador
para i := 0; i < int(q); i++ {
filtro.WriteBit(verdadeiro)
}
filtro.WriteBit(falso)
filtro.WriteBits(r, P)
}
Exatamente o mesmo filtro que obtivemos no bitcoind, exceto pelos dois primeiros bytes! Por que há uma diferença nos primeiros 2 bytes? Porque o BIP diz que o valor de N precisa ser codificado no formato CompactSize e aparecer na frente do filtro para que possa ser decodificado pelo receptor. Isso é feito por:
No entanto, meu entendimento pessoal é que não há necessidade de adicionar N ao filtro. Se você conhece o valor de P, pode encontrar o valor de N. Vamos ver se podemos restaurar a lista original de números usando a saída do primeiro filtro:
b := bstream.NewBStreamReader(filtro)
(
números []uint64
prevNum uint64
)
para {
// Lê o quociente da string de bytes. O primeiro 0 encontrado indica o fim do quociente
// Antes de encontrar 0, o número 1 representa o quociente
q uint64
c, erro := b.ReadBit()
se errar != nil {
retornar erro
}
para c {
q++
c, erro = b.ReadBit()
if errors.Is(err, io.EOF) {
quebrar
} senão se errar != nil {
retornar erro
}
}
// Os próximos P bits codificam o resto
r, err := b.ReadBits(P)
if errors.Is(err, io.EOF) {
quebrar
} senão se errar != nil {
retornar erro
}
n := q*uint64(math.Exp2(float64(P))) + r
num := n + anteriorNum
números = append(números, num)
prevNum = num
}
fmt.Println(números)
A operação acima produz a mesma lista de números, então podemos reconstruí-la sem conhecer N. Portanto, não tenho certeza de qual é a justificativa para adicionar N ao filtro. Se você sabe por que N deve ser incluído, por favor me avise!
Obrigado por ler!
Ver original
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.
Filtro de bloco denso BIP 158 explicado
Por Elle Mouton
Neste artigo, descrevo brevemente a necessidade de clientes leves no Bitcoin e por que os "filtros de blocos compactos" atendem melhor a essa necessidade do que os "filtros Bloom". Em seguida, explico detalhadamente como funciona o filtro de bloco denso, com uma explicação passo a passo da construção desse filtro em uma rede de teste.
Significado do filtro de bloco
Um cliente bitcoin light (software bitcoin light) é um software cujo objetivo não é armazenar o blockchain bitcoin, mas dar suporte a uma carteira bitcoin. Isso significa que ele precisa ser capaz de transmitir transações para a rede, mas o mais importante, deve ser capaz de encontrar novas transações da cadeia relacionadas a esta carteira. Existem dois tipos de transações relacionadas: enviar fundos para esta carteira (criando uma nova saída para um endereço desta carteira) e gastar um dos UTXOs controlados por esta carteira.
O que há de errado com os filtros bloom?
Antes do BIP 158, a abordagem mais comum para clientes leves era o filtro Bloom descrito no BIP 371. O padrão de um filtro Bloom é que você pegue todos os objetos de dados nos quais está interessado (por exemplo, as chaves públicas do script dos UTXOs que foram gastos e criados), faça hash deles um por um várias vezes e adicione cada resultado ao In um bitmap chamado "filtro de florescimento". Este filtro representa o que você está interessado. Em seguida, você envia esse filtro para um nodo Bitcoin em que confia e pede que ele envie tudo o que corresponde a esse filtro.
O problema é que esse processo não é muito privado, pois você ainda vaza algumas informações para o nodo Bitcoin que aceita o filtro. Eles podem saber negócios nos quais você está interessado e negócios nos quais você não está interessado; eles também podem não enviar coisas que correspondam aos filtros. Portanto, não é ideal para clientes leves. Mas, ao mesmo tempo, não é ideal para nós Bitcoin que atendem a clientes leves. Toda vez que você envia um filtro, eles precisam carregar o bloco relevante do disco e determinar se alguma transação corresponde ao seu filtro. Continue enviando filtros falsos e você pode bombardeá-los - essencialmente um ataque do DOS. É preciso muito pouca energia para criar um filtro, mas é preciso muita energia para responder a tal solicitação.
Filtro de bloco denso
OK, então os atributos que precisamos são:
Usando um filtro de bloco denso, o servidor (nó completo) irá construir um filtro determinístico para cada bloco, incluindo todos os objetos de dados neste bloco. Este filtro só precisa ser calculado uma vez e armazenado para sempre. Se um cliente leve solicita um filtro para um determinado bloco, não há assimetria aqui - porque o servidor não precisa fazer mais trabalho do que o cliente solicitante. O light client também pode escolher várias fontes de informação para baixar o bloco completo para garantir que sejam consistentes, além disso, o light client sempre pode baixar o bloco completo para verificar se o filtro fornecido pelo servidor está correto. Correto (corresponde ao bloco relevante contente). Outro benefício é que é mais privado desta forma. O light client não precisa mais enviar a impressão digital dos dados que deseja para o servidor. Também fica mais difícil analisar a atividade de um cliente leve. Depois que o light client obtém tal filtro do servidor, ele verifica se o filtro contém os dados que deseja e, em caso afirmativo, o light client solicita o bloco completo. Também deve ser apontado que, para atender clientes leves dessa maneira, nós completos precisam persistir esses filtros, e clientes leves também podem querer persistir alguns filtros, portanto, mantenha os filtros o mais leve possível A quantidade é muito importante ( é por isso que é chamado de "filtro de bloco denso").
muito bom! Agora estamos entrando no material raro. Como esse filtro é criado? Com o que se parece?
Quais são as nossas necessidades?
As informações básicas contidas no filtro são: a chave pública do script de cada entrada de cada transação (ou seja, a chave pública do script de cada UTXO gasto) e a chave pública do script de cada saída de cada transação. Basicamente é assim:
objects = {spk1, spk2, spk3, spk4, ..., spkN} // uma lista de N chaves públicas de script
Tecnicamente, podemos parar aqui - apenas uma lista de chaves públicas de script também pode atuar como nosso filtro. Esta é uma versão condensada de um bloco que contém informações necessárias para clientes leves. Com essa lista, um cliente light pode confirmar 100% se existe uma transação de interesse em um bloco. Mas essa lista é muito grande. Portanto, nossos próximos passos são todos para tornar esta lista o mais compacta possível. É onde as coisas começam a ficar interessantes.
Primeiro, podemos converter cada objeto em um número dentro de um determinado intervalo e fazer com que cada número de objeto seja distribuído uniformemente dentro desse intervalo. Suponha que temos 10 objetos (N = 10) e então temos algum tipo de função que converte cada objeto em um número. Digamos que escolhemos o intervalo [0, 10] (já que temos 10 objetos). Agora, nossa função "hash to number" receberá cada objeto como entrada e produzirá um número com tamanho [0, 10] respectivamente. Os números são distribuídos uniformemente por esse intervalo. Isso significa que, após a ordenação, teremos um gráfico como este (em um caso muito, muito ideal):
números:= {1,2,3,4,5,6,7,8,9,10}
Um cliente leve baixa esse filtro, esperando saber se um objeto que está procurando corresponde ao filtro. Eles apenas pegam o objeto em que estão interessados e executam a mesma função "hash to number" para ver se o resultado está neste filtro. Onde está o problema? O problema é que os números do filtro já ocupam todas as possibilidades daquele espaço! Isso significa que não importa com quais objetos o light client se preocupa, o resultado numérico resultante deve corresponder a esse filtro. Em outras palavras, este filtro tem uma "taxa de falso-positivo" de 1 (Nota do tradutor: O "falso positivo" aqui significa que o bloco pode não conter O resultado obtido pelo filtro é sim). Isso não é tão bom. Também mostra que no processo de compressão dos dados para gerar o filtro, perdemos muita informação. Precisamos de uma taxa de falsos positivos mais alta. Então, suponha que queremos que a taxa de falsos positivos seja 5. Então, podemos fazer com que os objetos no bloco correspondam uniformemente aos números no intervalo [0, 50]:
Agora temos uma lista ordenada de números uniformemente distribuídos no intervalo [0, 50]. Sabemos que existem 10 números nesta lista. Isso significa que podemos deduzir que a diferença entre dois números adjacentes nesta lista ordenada de números provavelmente é 5. Em geral, se tivermos N objetos e quisermos uma taxa de falsos positivos de M, o tamanho do espaço deve ser N * M . Ou seja, o tamanho desses números deve estar entre 0 e N * M, mas (após a classificação) a probabilidade de interpolação de dois números adjacentes verificados é M. E M deve ser armazenado menor que o número no espaço N * M. Assim, em vez de armazenar cada número, podemos armazenar a diferença entre dois números adjacentes. No exemplo acima, isso significa que, em vez de armazenar [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] como um filtro, armazenamos [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], a partir do qual é trivial reconstruir a lista inicial. Se você reduzir, armazenar o número 50 obviamente ocupa mais espaço do que armazenar o número 5. Mas por que parar por aí? Vamos comprimir um pouco mais!
O próximo passo é usar a "codificação Golomb-Rice". Esse método de codificação pode codificar bem uma lista em que cada número na tabela está muito próximo de um determinado número. E nossa lista é exatamente isso! Cada um dos números em nossa lista provavelmente está próximo de 5 (ou próximo de nossa taxa de falsos positivos, que é M), então pegue o quociente de cada número por M (divida cada número por 5 e ignore o resto), provavelmente será 0 (se o número for um pouco menor que 5) ou 1 (se o número for um pouco maior que 5). Também é possível que o quociente seja 2, 3, etc., mas a probabilidade é muito menor. ótimo! Portanto, podemos tirar proveito disso: usaremos o mínimo possível de bits para codificar quocientes menores, enquanto usamos mais bitcoins para codificar quocientes maiores, mas menos prováveis. Em seguida, também precisamos codificar o restante (já que queremos poder reconstruir a lista inteira exatamente), que sempre estará no intervalo [0, M - 1] (neste caso [0, 4]). Para o codificador, usamos os seguintes mapeamentos:
0000 10000 10000 10000 10000 10000 10000 10000 10000 10000
Antes de passarmos para um caso mais realista, vamos ver se conseguimos recuperar nossa lista original com este filtro.
Agora o que temos é "000010000100001000010000100001000010000100001000010000". Conhecemos o código Golomb-Rice e sabemos que M é 5 (já que isso será de conhecimento público, conhecido por todos que usam essa construção de filtro). Como sabemos que M é 5, sabemos que haverá 3 bits para codificar o restante. Assim, podemos converter este filtro na seguinte lista de matrizes "quociente-restante":
[(0, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), ( 1, 0), (1, 0)]
Sabendo que o quociente é obtido dividindo por M(5), podemos recuperar:
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Além disso, sabemos que esta lista representa a diferença entre dois números adjacentes, então podemos restaurar a lista original:
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Um exemplo mais realista
Agora vamos tentar construir um filtro para um bloco de teste real do Bitcoin. Vou usar o bloco 2101914. Vamos ver como é o filtro:
$ bitcoin-cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ bitcoin-cli getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { "filtro": "5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864 023833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a 65a5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b3 4b56ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", "cabeçalho": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }
Tudo bem querida, vamos ver como podemos construir tal filtro de blocos.
O código completo usado aqui pode ser encontrado neste repositório github. Vou apenas mostrar alguns trechos de pseudocódigo aqui. O núcleo desse código é uma função chamada constructFilter, que pode ser usada por clientes bitcoin para chamar bitcoind e os blocos correspondentes. A função fica assim:
func constructFilter(bc *bitcoind.Bitcoind, bloco bitcoind.Block) ([]byte, erro) { // 1 coleta todos os objetos do bloco que queremos adicionar a um filtro // 2 Converte esses objetos em números e os classifica // 3 Obtém a diferença entre dois números adjacentes na lista de números ordenados // 4 Use a codificação Golomb-Rice para codificar essas diferenças }
Assim, o primeiro passo é coletar todos os objetos do bloco que queremos adicionar ao filtro. A partir do BIP, sabemos que esses objetos incluem todas as chaves públicas de script gastas e todas as chaves públicas de script de saída. O BIP também define algumas regras adicionais: ignoramos as entradas para a transação coinbase (o que não faz sentido, pois não possui entradas) e passamos todas as saídas OP_RETURN. Também desduplicamos dados. Se houver duas chaves públicas de script idênticas, adicionamos apenas uma vez ao filtro.
// lista de objetos que desejamos adicionar ao filtro // Inclui todas as chaves públicas de script gastas e todas as chaves públicas de script de saída // Usamos um "mapa", que remove chaves públicas de script duplicadas objetos := make(mapa [string] estrutura{}) // facilita todas as transações no bloco para i, tx := intervalo de bloco.Tx { // Adiciona a chave pública do script para cada saída // em nossa lista de objetos for _, txOut := range tx.Vout { PubKey := txOut.PubKey if len(PubKey) == 0 { continuar } // Ignora se OP_RETURN (0x6a) é a saída se falar [0] == 0x6a { continuar } objetos [skpStr] = estrutura{}{} } // não adiciona a entrada da transação coinbase se eu == 0 { continuar } // Para cada entrada, obtém sua chave pública de script para _, txIn := intervalo tx.Vin { prevTx, err := bc.GetRawTransaction(txIn.Txid) se errar != nil { retorno nulo, erro } PubKey := prevTx.Vout[txIn.Vout].PubKey if len(PubKey) == 0 { continuar } objetos [spkStr] = estrutura{}{} } }
OK, agora todos os objetos são coletados. Agora, definimos a variável N como sendo o comprimento do grafo do objeto. Aqui, N é 85 .
O próximo passo é converter nosso objeto em números uniformemente distribuídos em um intervalo. Novamente, o intervalo depende de quão alta é a taxa de falsos positivos que você deseja. BIP158 define a constante M como 784931. Isso significa que a probabilidade de um falso positivo é de 1 em 784931. Assim como fizemos antes, pegamos a taxa de falsos positivos M vezes N e obtemos o intervalo de distribuição de todos os números. Definimos esse intervalo como F, ou seja, F = M * N . Aqui, F = 66719135. Não vou entrar em detalhes das funções que mapeiam objetos para números (você pode encontrar os detalhes no repositório do github vinculado acima). Tudo o que você precisa saber é que ele recebe como entrada o objeto, a constante F (que define o escopo para o qual o objeto precisa ser mapeado) e uma chave (o hash do bloco). Assim que tivermos todos os números, classificamos a lista em ordem crescente e, em seguida, criamos uma nova lista chamada diferenças que contém a diferença entre dois números adjacentes na lista de números classificados.
números := make([]uint64, 0, N) // Percorre todos os objetos e os converte em números uniformemente distribuídos no intervalo [0, F] // e armazena esses números como uma lista de números para o := objetos de alcance { // Usando a chave fornecida, número máximo (F) e bytes de objeto (o), // converte o objeto para um número entre 0 e F. v := convertToNumber(b, F, chave) números = append(números, v) } // ordena a lista de números sort.Slice(números, func(i, j int) bool { return números [i] < números [j] }) // Converte a lista de números em uma lista de diferenças diferenças := make([]uint64, N) para i, num := números de intervalo { se eu == 0 { diferenças [i] = num continuar } diferenças [i] = num - números[i-1] }
ótimo! Aqui está uma imagem mostrando uma lista de números e diferenças.
A etapa final é codificar a lista de diferenças usando a codificação Golomb-Rice. Lembre-se da explicação anterior de que precisamos dividir cada diferença pelo valor mais provável e, em seguida, codificar o quociente e o resto. Em nosso exemplo anterior, eu disse que o valor mais provável é M, e o restante ficará entre [0, M]. No entanto, o BIP158 não faz isso, pois encontramos 2, que não é o parâmetro que realmente minimiza o tamanho final do filtro. Portanto, em vez de usar M, definimos uma nova constante P e usamos 2^P como o parâmetro Golomb-Rice. P é definido como 19 . Isso significa que dividimos cada diferença por 2 ^ 19 para obter o quociente e o resto, e o resto é codificado em binário com 19 bits.
filtro := bstream.NewBStreamWriter(0) // Para cada valor na lista de diferenças, obtenha o quociente e o resto dividindo por 2^P. para _, d := diferenças de alcance { q := math.Floor(float64(d)/math.Exp2(float64(P))) r := d - uint64(math.Exp2(float64(P))*q) // Codificador para i := 0; i < int(q); i++ { filtro.WriteBit(verdadeiro) } filtro.WriteBit(falso) filtro.WriteBits(r, P) }
ótimo! Agora podemos produzir o filtro, obtendo:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0 b0c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade 12fa2e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
Exatamente o mesmo filtro que obtivemos no bitcoind, exceto pelos dois primeiros bytes! Por que há uma diferença nos primeiros 2 bytes? Porque o BIP diz que o valor de N precisa ser codificado no formato CompactSize e aparecer na frente do filtro para que possa ser decodificado pelo receptor. Isso é feito por:
fd := filtro.Bytes() bytes de buffer.Buffer buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) err = wire.WriteInt(&buffer, 0, uint64(N)) se errar != nil { retorno nulo, erro } _, erro = buffer.Write(fd) se errar != nil { retorno nulo, erro }
Se agora imprimirmos o filtro novamente, descobriremos que é exatamente igual ao resultado do bitcoind:
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df5743786402383 3f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5 b0b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b5 6ade12fa 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
sucesso!
No entanto, meu entendimento pessoal é que não há necessidade de adicionar N ao filtro. Se você conhece o valor de P, pode encontrar o valor de N. Vamos ver se podemos restaurar a lista original de números usando a saída do primeiro filtro:
b := bstream.NewBStreamReader(filtro) ( números []uint64 prevNum uint64 ) para { // Lê o quociente da string de bytes. O primeiro 0 encontrado indica o fim do quociente // Antes de encontrar 0, o número 1 representa o quociente q uint64 c, erro := b.ReadBit() se errar != nil { retornar erro } para c { q++ c, erro = b.ReadBit() if errors.Is(err, io.EOF) { quebrar } senão se errar != nil { retornar erro } } // Os próximos P bits codificam o resto r, err := b.ReadBits(P) if errors.Is(err, io.EOF) { quebrar } senão se errar != nil { retornar erro } n := q*uint64(math.Exp2(float64(P))) + r num := n + anteriorNum números = append(números, num) prevNum = num } fmt.Println(números)
A operação acima produz a mesma lista de números, então podemos reconstruí-la sem conhecer N. Portanto, não tenho certeza de qual é a justificativa para adicionar N ao filtro. Se você sabe por que N deve ser incluído, por favor me avise!
Obrigado por ler!