В этой статье я кратко описываю потребность в легких клиентах в биткойнах и почему «компактные блочные фильтры» удовлетворяют эту потребность лучше, чем «фильтры Блума». Затем я подробно объясню, как работает плотный блочный фильтр, с пошаговым описанием создания такого фильтра в тестовой сети.
Значение блочного фильтра
Биткойн-лайт-клиент (программное обеспечение для биткойн-лайт) — это программное обеспечение, целью которого является не хранение биткойн-блокчейна, а поддержка биткойн-кошелька. Это означает, что он должен иметь возможность транслировать транзакции в сеть, но самое главное, он должен иметь возможность находить новые транзакции из цепочки, связанные с этим кошельком. Существует два типа таких связанных транзакций: отправка средств на этот кошелек (создание нового вывода для адреса этого кошелька) и расходование одного из UTXO, контролируемых этим кошельком.
Что не так с фильтрами Блума?
До BIP 158 наиболее распространенным подходом для легких клиентов был фильтр Блума, описанный в BIP 371. Шаблон фильтра Блума заключается в том, что вы берете все интересующие вас объекты данных (например, открытые ключи сценариев UTXO, которые были потрачены и созданы), хешируете их один за другим несколько раз и добавляете каждый результат в In. растровое изображение, называемое «фильтром цветения». Этот фильтр представляет то, что вас интересует. Затем вы отправляете этот фильтр на узел Биткойн, которому вы доверяете, и просите их прислать вам все, что соответствует этому фильтру.
Проблема в том, что этот процесс не очень приватный, потому что вы все равно передаете некоторую информацию узлу Биткойн, который принимает фильтр. Они могут знать предложения, которые вас интересуют, и предложения, которые вас совсем не интересуют, а также не могут отправлять вам вещи, соответствующие фильтрам. Таким образом, это не идеально для легких клиентов. Но в то же время он не идеален для биткойн-узлов, обслуживающих легких клиентов. Каждый раз, когда вы отправляете фильтр, они должны загрузить соответствующий блок с диска, а затем определить, соответствуют ли какие-либо транзакции вашему фильтру. Просто продолжайте посылать поддельные фильтры, и вы сможете их взорвать — по сути, DOS-атака. Для создания фильтра требуется очень мало энергии, но для ответа на такой запрос требуется много энергии.
Плотный блочный фильтр
Хорошо, тогда нам нужны следующие атрибуты:
Более сильная конфиденциальность
Асимметрия клиент-серверной нагрузки меньше. То есть на стороне сервера должно быть меньше работы.
Меньше доверия. Легким клиентам не нужно беспокоиться о том, что сервер не вернет связанные транзакции.
Используя плотный блочный фильтр, сервер (полный узел) создаст детерминированный фильтр для каждого блока, включая все объекты данных в этом блоке. Этот фильтр нужно вычислить только один раз и сохранить навсегда. Если легкий клиент запрашивает фильтр для определенного блока, здесь нет асимметрии — ведь серверу не нужно делать больше работы, чем запрашивающему клиенту. Легкий клиент также может выбрать несколько источников информации для загрузки полного блока, чтобы убедиться, что они непротиворечивы, более того, легкий клиент всегда может загрузить весь блок, чтобы проверить правильность фильтра, предоставляемого сервером. содержание). Еще одним преимуществом является то, что это более конфиденциально. Легкому клиенту больше не нужно отправлять отпечаток нужных данных на сервер. Также становится сложнее анализировать активность легкого клиента. После того, как легкий клиент получает такой фильтр с сервера, он проверяет, содержит ли фильтр нужные ему данные, и если да, легкий клиент запрашивает полный блок. Следует также отметить, что для обслуживания легких клиентов таким образом полные узлы должны сохранять эти фильтры, а легкие клиенты также могут захотеть сохранить несколько фильтров, поэтому держите фильтры как можно более легкими. Количество очень важно ( вот почему он называется «плотным блочным фильтром»).
очень хороший! Теперь мы переходим к редким вещам. Как создается такой фильтр? Как это выглядит?
Каковы наши потребности?
Мы хотим поместить отпечаток определенного объекта в фильтр, чтобы, когда клиенты хотят проверить, может ли блок содержать что-то, связанное с ними, они могли перечислить все объекты и проверить фильтр, соответствуют ли эти объекты.
Мы хотим, чтобы этот фильтр был как можно меньше.
По сути, мы хотим что-то, что может обобщать некоторую информацию о блоке с объемом, намного меньшим, чем сам блок.
Основная информация, содержащаяся в фильтре: открытый ключ сценария каждого входа каждой транзакции (то есть открытый ключ сценария каждого потраченного UTXO) и открытый ключ сценария каждого выхода каждой транзакции. В основном это так:
objects = {spk1, spk2, spk3, spk4, ..., spkN} // список из N открытых ключей скрипта
Технически на этом можно остановиться — именно такой список публичных ключей скрипта тоже может выступать в роли нашего фильтра. Это сжатая версия блока, содержащая информацию, необходимую легким клиентам. С таким списком легкий клиент может на 100% подтвердить, есть ли интересующая транзакция в блоке. Но такой список очень велик. Поэтому наши следующие шаги — сделать этот список максимально компактным. Здесь все становится интереснее.
Во-первых, мы можем преобразовать каждый объект в число в определенном диапазоне и сделать так, чтобы каждый номер объекта был равномерно распределен в этом диапазоне. Предположим, у нас есть 10 объектов (N = 10), а затем у нас есть какая-то функция, которая преобразует каждый объект в число. Допустим, мы выбираем диапазон [0, 10] (поскольку у нас есть 10 объектов). Теперь наша функция «хэш в число» будет принимать каждый объект в качестве входных данных и создавать число размером [0, 10] соответственно. Цифры равномерно распределены по этому диапазону. Это означает, что после сортировки мы получим такой график (в очень и очень идеальном случае):
Во-первых, это здорово, потому что мы значительно уменьшили размер отпечатка каждого объекта. Теперь каждый объект — это просто число. Итак, наш новый фильтр выглядит так:
числа: = {1,2,3,4,5,6,7,8,9,10}
Легкий клиент загружает такой фильтр, надеясь узнать, соответствует ли искомый объект фильтру. Они просто берут интересующий их объект и запускают ту же функцию «хеширования в число», чтобы увидеть, попадает ли результат в этот фильтр. В чем проблема? Проблема в том, что числа в фильтре уже занимают все возможности в этом пространстве! Это означает, что независимо от того, какие объекты волнуют легкий клиент, результирующий числовой результат должен соответствовать этому фильтру. Другими словами, этот фильтр имеет «коэффициент ложных срабатываний» 1 (Примечание переводчика: «ложноположительные» здесь означают, что блок не может содержать результат, полученный фильтром, «да»). Это не очень хорошо. Это также показывает, что в процессе сжатия данных для создания фильтра мы теряем слишком много информации. Нам нужен более высокий уровень ложных срабатываний. Затем предположим, что мы хотим, чтобы процент ложных срабатываний был равен 5. Затем мы можем сделать так, чтобы объекты в блоке равномерно совпадали с числами в диапазоне [0, 50]:
Так выглядит лучше. Если я клиент и загружаю такой фильтр, мне нужно проверить, находится ли интересующий меня объект в соответствующем блоке через фильтр, и вероятность того, что фильтр скажет да, но не в блоке (ложное срабатывание), уменьшится до 1/5. Отлично, теперь мы сопоставляем 10 объектов с числами от 0 до 50. Этот новый список чисел является нашим фильтром. Опять же, мы можем остановиться в любой момент, однако мы можем сжать их еще больше!
Теперь у нас есть упорядоченный список чисел, равномерно распределенных в интервале [0, 50]. Мы знаем, что в этом списке 10 номеров. Это означает, что мы можем сделать вывод, что разница между двумя соседними числами в этом упорядоченном списке чисел, скорее всего, будет равна 5. В общем, если у нас есть N объектов и мы хотим получить ложноположительный результат M, тогда размер пространства должен быть N * M . То есть размер этих чисел должен быть между 0 и N*M, но (после сортировки) интерполяционная вероятность двух проверенных соседних чисел равна M. А М надо хранить меньше, чем число в пространстве N*M. Таким образом, вместо того, чтобы хранить каждое отдельное число, мы можем хранить разницу между двумя соседними числами. В приведенном выше примере это означает, что вместо сохранения [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] в качестве фильтра мы сохраняем [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], по которым тривиально восстановить исходный список. Если вы уменьшите масштаб, хранение числа 50, очевидно, займет больше места, чем хранение числа 5. Но зачем останавливаться на достигнутом? Сжимаем еще немного!
Следующим шагом является использование «кодирования Голомба-Райса». Этот метод кодирования может хорошо кодировать список, где каждое число в таблице очень близко к определенному числу. И наш список как раз такой! Каждое из чисел в нашем списке, вероятно, будет близко к 5 (или близко к нашей частоте ложных срабатываний, которая равна M), поэтому возьмем частное каждого числа на M (разделим каждое число на 5 и проигнорируем остаток). скорее всего будет 0 (если число чуть меньше 5) или 1 (если число чуть больше 5). Также возможно, что частное равно 2, 3 и т. д., но вероятность этого намного меньше. большой! Таким образом, мы можем воспользоваться этим: мы будем использовать как можно меньше битов для кодирования меньших частных, в то время как используем больше биткойнов для кодирования больших, но менее вероятных частных. Затем нам также нужно закодировать остаток (поскольку мы хотим иметь возможность точно восстановить весь список), который всегда будет в диапазоне [0, M - 1] (в данном случае [0, 4]). Для кодировщика мы используем следующие отображения:
Приведенное выше сопоставление легко понять: количество цифр 1 указывает на частное, которое мы хотим закодировать, а 0 указывает на конец частного кодирования. Итак, для каждого числа в нашем списке мы можем использовать приведенную выше таблицу, чтобы закодировать частное, а затем преобразовать остаток в двоичный код с помощью биттрака, который может представлять максимальное значение M-1. Здесь остаток равен 4, а нужны только 3 бита. Вот таблица, показывающая возможные остатки и их кодировку для нашего примера:
Итак, в идеале наш список [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] должен быть закодирован как:
Прежде чем мы перейдем к более реалистичному случаю, давайте посмотрим, сможем ли мы восстановить исходный список с помощью этого фильтра.
Теперь у нас есть "0000100001000010000100001000010000100001000010000". Нам известен код Голомба-Райса, и мы знаем, что M равно 5 (поскольку это будет общеизвестно, известное всем, кто использует эту конструкцию фильтра). Поскольку мы знаем, что M равно 5, мы знаем, что для кодирования остатка будет 3 бита. Итак, мы можем преобразовать этот фильтр в следующий список массивов «частное-остаток»:
Хорошо, дорогая, давайте посмотрим, как мы можем построить такой фильтр из блоков.
Полный код, используемый здесь, можно найти в этом репозитории github. Я просто покажу здесь несколько фрагментов псевдокода. Ядром этого кода является функция под названием «constructFilter», которая может использоваться биткойн-клиентами для вызова bitcoind и соответствующих блоков. Функция выглядит следующим образом:
func ConstructionFilter(bc *bitcoind.Bitcoind, block bitcoind.Block) ([]byte, error) {
// 1 собирает все объекты из блока, которые мы хотим добавить в фильтр
// 2 Преобразовать эти объекты в числа и отсортировать их
// 3 Получить разницу между двумя соседними числами в отсортированном списке чисел
// 4 Используйте кодировку Голомба-Райса для кодирования этих различий
}
Итак, первый шаг — собрать все объекты из блока, которые мы хотим добавить в фильтр. Начиная с BIP, мы знаем, что эти объекты включают в себя все израсходованные открытые ключи скрипта и каждый открытый ключ выходного скрипта. BIP также устанавливает некоторые дополнительные правила: мы пропускаем входы в транзакцию coinbase (что не имеет смысла, поскольку у нее нет входов), и мы передаем все выходы OP_RETURN. Мы также делаем дедупликацию данных. Если есть два одинаковых публичных ключа скрипта, мы добавляем их в фильтр только один раз.
// список объектов, которые мы хотим добавить в фильтр
// Включить все израсходованные открытые ключи скрипта и каждый выходной открытый ключ скрипта
// Мы используем «карту», которая удаляет повторяющиеся открытые ключи скрипта
объекты := сделать(карта [string] структура{})
// облегчить каждую транзакцию в блоке
для i, tx := блок диапазона.Tx {
// Добавляем открытый ключ скрипта для каждого вывода
// в наш список объектов
для _, txOut := диапазон tx.Vout {
ПубКей := txOut.PubKey
если len(PubKey) == 0 {
продолжать
}
// Пропустить, если выводится OP_RETURN (0x6a)
если спк [0] == 0x6a {
продолжать
}
объекты [skpStr] = структура{}{}
}
// не добавляйте ввод транзакции coinbase
если я == 0 {
продолжать
}
// Для каждого ввода получаем открытый ключ скрипта
для _, txIn: = диапазон tx.Vin {
prevTx, ошибка: = bc.GetRawTransaction(txIn.Txid)
если ошибка != ноль {
вернуть ноль, ошибиться
}
PubKey := prevTx.Vout[txIn.Vout].PubKey
если len(PubKey) == 0 {
продолжать
}
объекты [spkStr] = структура{}{}
}
}
Хорошо, теперь все объекты собраны. Теперь мы определяем переменную N как длину графа объектов. Здесь N равно 85 .
Следующим шагом является преобразование нашего объекта в числа, равномерно распределенные по интервалу. Опять же, диапазон зависит от желаемого уровня ложных срабатываний. BIP158 определяет константу M как 784931. Это означает, что вероятность ложного срабатывания составляет 1 из 784931. Как и раньше, мы берем коэффициент ложных срабатываний M, умноженный на N, и получаем диапазон распределения всех чисел. Определим этот диапазон как F, то есть F = M * N . Здесь F = 66719135. Я не буду вдаваться в детали функций, которые сопоставляют объекты с числами (вы можете найти подробности в репозитории github, ссылка на который приведена выше). Все, что вам нужно знать, это то, что он принимает в качестве входных данных объект, константу F (которая определяет область, в которую необходимо сопоставить объект) и ключ (хэш блока). Когда у нас есть все числа, мы сортируем список в порядке возрастания, а затем создаем новый список, называемый различиями, который содержит разницу между двумя соседними числами в отсортированном списке чисел.
числа := make([]uint64, 0, N)
// Перебрать все объекты и преобразовать их в числа, равномерно распределенные в диапазоне [0, F]
// и сохранить эти числа как список чисел
для o := объекты диапазона {
// Используя заданный ключ, максимальное число (F) и байты объекта (o),
// преобразовать объект в число от 0 до F.
v := convertToNumber(b, F, ключ)
числа = добавить (числа, v)
}
// сортируем список чисел
sort.Slice (числа, func (i, j int) bool { возвращаемые числа [i] < номера [j] })
// Преобразование списка чисел в список различий
различия := make([]uint64, N)
для i, num := диапазон чисел {
если я == 0 {
различия [i] = число
продолжать
}
различия [i] = число - числа [i-1]
}
большой! Вот картинка, показывающая список чисел и различий.
Когда вы уменьшаете масштаб, 85 чисел равномерно распределяются по всему пространству! Так что значения в списке отличий тоже очень маленькие.
Последним шагом является кодирование списка различий с использованием кодирования Голомба-Райса. Вспомните из предыдущего объяснения, что нам нужно разделить каждую разность на наиболее вероятное значение, а затем закодировать частное и остаток. В нашем предыдущем примере я сказал, что наиболее вероятное значение равно M, а остаток будет между [0, M]. Однако BIP158 этого не делает, так как мы нашли 2, что не является тем параметром, который на самом деле минимизирует конечный размер фильтра. Поэтому вместо использования M мы определяем новую константу P и используем 2^P в качестве параметра Голомба-Райса. P определяется как 19 . Это означает, что мы делим каждую разность на 2 ^ 19, чтобы получить частное и остаток, а остаток кодируется в двоичном формате с 19 битами.
фильтр := bstream.NewBStreamWriter(0)
// Для каждого значения в списке различий получаем частное и остаток путем деления на 2^P.
для _, d := разность диапазонов {
q := math.Floor(float64(d)/math.Exp2(float64(P)))
r := d - uint64(math.Exp2(float64(P))*q)
// Кодировщик
для я := 0; я < интервал (д); я++ {
filter.WriteBit (истина)
}
filter.WriteBit(false)
filter.WriteBits(r, P)
}
Точно такой же фильтр, как и в биткойне, за исключением первых двух байтов! Почему разница в первых 2 байтах? Потому что BIP говорит, что значение N должно быть закодировано в формате CompactSize и отображаться перед фильтром, чтобы получатель мог его декодировать. Это делается:
fd := filter.Bytes()
байты буфера. Буфер
buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd))
ошибка = провод.WriteInt(&buffer, 0, uint64(N))
если ошибка != ноль {
вернуть ноль, ошибиться
}
_, ошибка = буфер. Запись (fd)
если ошибка != ноль {
вернуть ноль, ошибиться
}
Если теперь мы снова распечатаем фильтр, мы обнаружим, что он точно такой же, как и у биткойна:
Однако мое личное понимание состоит в том, что нет необходимости добавлять N к фильтру. Если вы знаете значение P, то вы можете найти значение N. Давайте посмотрим, сможем ли мы восстановить исходный список чисел, используя вывод первого фильтра:
b := bstream.NewBStreamReader(фильтр)
(
числа []uint64
предыдущийNum uint64
)
для {
// Чтение частного из строки байтов. Первый встреченный 0 указывает на конец частного
// До встречи с 0 число 1 представляет собой частное
q uint64
c, ошибка := b.ReadBit()
если ошибка != ноль {
вернуть ошибку
}
для с {
д++
c, ошибка = b.ReadBit()
если error.Is(ошибка, io.EOF) {
перерыв
} иначе если ошибка != ноль {
вернуть ошибку
}
}
// Следующие P бит кодируют остаток
г, ошибка := b.ReadBits(P)
если error.Is(ошибка, io.EOF) {
перерыв
} иначе если ошибка != ноль {
вернуть ошибку
}
n := q*uint64(math.Exp2(float64(P))) + r
число := n + предыдущее число
числа = добавить (числа, число)
предыдущее число = число
}
fmt.Println(числа)
Описанная выше операция дает тот же список чисел, поэтому мы можем восстановить его, не зная N. Поэтому я не уверен, в чем причина добавления N к фильтру. Если вы знаете, почему N должен быть включен, пожалуйста, дайте мне знать!
Спасибо за прочтение!
Посмотреть Оригинал
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.
Объяснение фильтра плотных блоков BIP 158
Эль Мутон
В этой статье я кратко описываю потребность в легких клиентах в биткойнах и почему «компактные блочные фильтры» удовлетворяют эту потребность лучше, чем «фильтры Блума». Затем я подробно объясню, как работает плотный блочный фильтр, с пошаговым описанием создания такого фильтра в тестовой сети.
Значение блочного фильтра
Биткойн-лайт-клиент (программное обеспечение для биткойн-лайт) — это программное обеспечение, целью которого является не хранение биткойн-блокчейна, а поддержка биткойн-кошелька. Это означает, что он должен иметь возможность транслировать транзакции в сеть, но самое главное, он должен иметь возможность находить новые транзакции из цепочки, связанные с этим кошельком. Существует два типа таких связанных транзакций: отправка средств на этот кошелек (создание нового вывода для адреса этого кошелька) и расходование одного из UTXO, контролируемых этим кошельком.
Что не так с фильтрами Блума?
До BIP 158 наиболее распространенным подходом для легких клиентов был фильтр Блума, описанный в BIP 371. Шаблон фильтра Блума заключается в том, что вы берете все интересующие вас объекты данных (например, открытые ключи сценариев UTXO, которые были потрачены и созданы), хешируете их один за другим несколько раз и добавляете каждый результат в In. растровое изображение, называемое «фильтром цветения». Этот фильтр представляет то, что вас интересует. Затем вы отправляете этот фильтр на узел Биткойн, которому вы доверяете, и просите их прислать вам все, что соответствует этому фильтру.
Проблема в том, что этот процесс не очень приватный, потому что вы все равно передаете некоторую информацию узлу Биткойн, который принимает фильтр. Они могут знать предложения, которые вас интересуют, и предложения, которые вас совсем не интересуют, а также не могут отправлять вам вещи, соответствующие фильтрам. Таким образом, это не идеально для легких клиентов. Но в то же время он не идеален для биткойн-узлов, обслуживающих легких клиентов. Каждый раз, когда вы отправляете фильтр, они должны загрузить соответствующий блок с диска, а затем определить, соответствуют ли какие-либо транзакции вашему фильтру. Просто продолжайте посылать поддельные фильтры, и вы сможете их взорвать — по сути, DOS-атака. Для создания фильтра требуется очень мало энергии, но для ответа на такой запрос требуется много энергии.
Плотный блочный фильтр
Хорошо, тогда нам нужны следующие атрибуты:
Используя плотный блочный фильтр, сервер (полный узел) создаст детерминированный фильтр для каждого блока, включая все объекты данных в этом блоке. Этот фильтр нужно вычислить только один раз и сохранить навсегда. Если легкий клиент запрашивает фильтр для определенного блока, здесь нет асимметрии — ведь серверу не нужно делать больше работы, чем запрашивающему клиенту. Легкий клиент также может выбрать несколько источников информации для загрузки полного блока, чтобы убедиться, что они непротиворечивы, более того, легкий клиент всегда может загрузить весь блок, чтобы проверить правильность фильтра, предоставляемого сервером. содержание). Еще одним преимуществом является то, что это более конфиденциально. Легкому клиенту больше не нужно отправлять отпечаток нужных данных на сервер. Также становится сложнее анализировать активность легкого клиента. После того, как легкий клиент получает такой фильтр с сервера, он проверяет, содержит ли фильтр нужные ему данные, и если да, легкий клиент запрашивает полный блок. Следует также отметить, что для обслуживания легких клиентов таким образом полные узлы должны сохранять эти фильтры, а легкие клиенты также могут захотеть сохранить несколько фильтров, поэтому держите фильтры как можно более легкими. Количество очень важно ( вот почему он называется «плотным блочным фильтром»).
очень хороший! Теперь мы переходим к редким вещам. Как создается такой фильтр? Как это выглядит?
Каковы наши потребности?
Основная информация, содержащаяся в фильтре: открытый ключ сценария каждого входа каждой транзакции (то есть открытый ключ сценария каждого потраченного UTXO) и открытый ключ сценария каждого выхода каждой транзакции. В основном это так:
objects = {spk1, spk2, spk3, spk4, ..., spkN} // список из N открытых ключей скрипта
Технически на этом можно остановиться — именно такой список публичных ключей скрипта тоже может выступать в роли нашего фильтра. Это сжатая версия блока, содержащая информацию, необходимую легким клиентам. С таким списком легкий клиент может на 100% подтвердить, есть ли интересующая транзакция в блоке. Но такой список очень велик. Поэтому наши следующие шаги — сделать этот список максимально компактным. Здесь все становится интереснее.
Во-первых, мы можем преобразовать каждый объект в число в определенном диапазоне и сделать так, чтобы каждый номер объекта был равномерно распределен в этом диапазоне. Предположим, у нас есть 10 объектов (N = 10), а затем у нас есть какая-то функция, которая преобразует каждый объект в число. Допустим, мы выбираем диапазон [0, 10] (поскольку у нас есть 10 объектов). Теперь наша функция «хэш в число» будет принимать каждый объект в качестве входных данных и создавать число размером [0, 10] соответственно. Цифры равномерно распределены по этому диапазону. Это означает, что после сортировки мы получим такой график (в очень и очень идеальном случае):
числа: = {1,2,3,4,5,6,7,8,9,10}
Легкий клиент загружает такой фильтр, надеясь узнать, соответствует ли искомый объект фильтру. Они просто берут интересующий их объект и запускают ту же функцию «хеширования в число», чтобы увидеть, попадает ли результат в этот фильтр. В чем проблема? Проблема в том, что числа в фильтре уже занимают все возможности в этом пространстве! Это означает, что независимо от того, какие объекты волнуют легкий клиент, результирующий числовой результат должен соответствовать этому фильтру. Другими словами, этот фильтр имеет «коэффициент ложных срабатываний» 1 (Примечание переводчика: «ложноположительные» здесь означают, что блок не может содержать результат, полученный фильтром, «да»). Это не очень хорошо. Это также показывает, что в процессе сжатия данных для создания фильтра мы теряем слишком много информации. Нам нужен более высокий уровень ложных срабатываний. Затем предположим, что мы хотим, чтобы процент ложных срабатываний был равен 5. Затем мы можем сделать так, чтобы объекты в блоке равномерно совпадали с числами в диапазоне [0, 50]:
Теперь у нас есть упорядоченный список чисел, равномерно распределенных в интервале [0, 50]. Мы знаем, что в этом списке 10 номеров. Это означает, что мы можем сделать вывод, что разница между двумя соседними числами в этом упорядоченном списке чисел, скорее всего, будет равна 5. В общем, если у нас есть N объектов и мы хотим получить ложноположительный результат M, тогда размер пространства должен быть N * M . То есть размер этих чисел должен быть между 0 и N*M, но (после сортировки) интерполяционная вероятность двух проверенных соседних чисел равна M. А М надо хранить меньше, чем число в пространстве N*M. Таким образом, вместо того, чтобы хранить каждое отдельное число, мы можем хранить разницу между двумя соседними числами. В приведенном выше примере это означает, что вместо сохранения [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] в качестве фильтра мы сохраняем [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], по которым тривиально восстановить исходный список. Если вы уменьшите масштаб, хранение числа 50, очевидно, займет больше места, чем хранение числа 5. Но зачем останавливаться на достигнутом? Сжимаем еще немного!
Следующим шагом является использование «кодирования Голомба-Райса». Этот метод кодирования может хорошо кодировать список, где каждое число в таблице очень близко к определенному числу. И наш список как раз такой! Каждое из чисел в нашем списке, вероятно, будет близко к 5 (или близко к нашей частоте ложных срабатываний, которая равна M), поэтому возьмем частное каждого числа на M (разделим каждое число на 5 и проигнорируем остаток). скорее всего будет 0 (если число чуть меньше 5) или 1 (если число чуть больше 5). Также возможно, что частное равно 2, 3 и т. д., но вероятность этого намного меньше. большой! Таким образом, мы можем воспользоваться этим: мы будем использовать как можно меньше битов для кодирования меньших частных, в то время как используем больше биткойнов для кодирования больших, но менее вероятных частных. Затем нам также нужно закодировать остаток (поскольку мы хотим иметь возможность точно восстановить весь список), который всегда будет в диапазоне [0, M - 1] (в данном случае [0, 4]). Для кодировщика мы используем следующие отображения:
0000 10000 10000 10000 10000 10000 10000 10000 10000 10000
Прежде чем мы перейдем к более реалистичному случаю, давайте посмотрим, сможем ли мы восстановить исходный список с помощью этого фильтра.
Теперь у нас есть "0000100001000010000100001000010000100001000010000". Нам известен код Голомба-Райса, и мы знаем, что M равно 5 (поскольку это будет общеизвестно, известное всем, кто использует эту конструкцию фильтра). Поскольку мы знаем, что M равно 5, мы знаем, что для кодирования остатка будет 3 бита. Итак, мы можем преобразовать этот фильтр в следующий список массивов «частное-остаток»:
[(0, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), ( 1, 0), (1, 0)]
Зная, что частное получается делением на M(5), мы можем восстановить:
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Кроме того, мы знаем, что этот список представляет собой разницу между двумя соседними числами, поэтому мы можем восстановить исходный список:
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Более реалистичный пример
Теперь мы попытаемся создать фильтр для реального блока тестовой сети Биткойн. Я буду использовать блок 2101914. Посмотрим, как выглядит его фильтр:
$ биткойн-cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ биткойн-кли getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { "фильтр": "5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df574378640 23833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a6 5a5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b3 4b56ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", "заголовок": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }
Хорошо, дорогая, давайте посмотрим, как мы можем построить такой фильтр из блоков.
Полный код, используемый здесь, можно найти в этом репозитории github. Я просто покажу здесь несколько фрагментов псевдокода. Ядром этого кода является функция под названием «constructFilter», которая может использоваться биткойн-клиентами для вызова bitcoind и соответствующих блоков. Функция выглядит следующим образом:
func ConstructionFilter(bc *bitcoind.Bitcoind, block bitcoind.Block) ([]byte, error) { // 1 собирает все объекты из блока, которые мы хотим добавить в фильтр // 2 Преобразовать эти объекты в числа и отсортировать их // 3 Получить разницу между двумя соседними числами в отсортированном списке чисел // 4 Используйте кодировку Голомба-Райса для кодирования этих различий }
Итак, первый шаг — собрать все объекты из блока, которые мы хотим добавить в фильтр. Начиная с BIP, мы знаем, что эти объекты включают в себя все израсходованные открытые ключи скрипта и каждый открытый ключ выходного скрипта. BIP также устанавливает некоторые дополнительные правила: мы пропускаем входы в транзакцию coinbase (что не имеет смысла, поскольку у нее нет входов), и мы передаем все выходы OP_RETURN. Мы также делаем дедупликацию данных. Если есть два одинаковых публичных ключа скрипта, мы добавляем их в фильтр только один раз.
// список объектов, которые мы хотим добавить в фильтр // Включить все израсходованные открытые ключи скрипта и каждый выходной открытый ключ скрипта // Мы используем «карту», которая удаляет повторяющиеся открытые ключи скрипта объекты := сделать(карта [string] структура{}) // облегчить каждую транзакцию в блоке для i, tx := блок диапазона.Tx { // Добавляем открытый ключ скрипта для каждого вывода // в наш список объектов для _, txOut := диапазон tx.Vout { ПубКей := txOut.PubKey если len(PubKey) == 0 { продолжать } // Пропустить, если выводится OP_RETURN (0x6a) если спк [0] == 0x6a { продолжать } объекты [skpStr] = структура{}{} } // не добавляйте ввод транзакции coinbase если я == 0 { продолжать } // Для каждого ввода получаем открытый ключ скрипта для _, txIn: = диапазон tx.Vin { prevTx, ошибка: = bc.GetRawTransaction(txIn.Txid) если ошибка != ноль { вернуть ноль, ошибиться } PubKey := prevTx.Vout[txIn.Vout].PubKey если len(PubKey) == 0 { продолжать } объекты [spkStr] = структура{}{} } }
Хорошо, теперь все объекты собраны. Теперь мы определяем переменную N как длину графа объектов. Здесь N равно 85 .
Следующим шагом является преобразование нашего объекта в числа, равномерно распределенные по интервалу. Опять же, диапазон зависит от желаемого уровня ложных срабатываний. BIP158 определяет константу M как 784931. Это означает, что вероятность ложного срабатывания составляет 1 из 784931. Как и раньше, мы берем коэффициент ложных срабатываний M, умноженный на N, и получаем диапазон распределения всех чисел. Определим этот диапазон как F, то есть F = M * N . Здесь F = 66719135. Я не буду вдаваться в детали функций, которые сопоставляют объекты с числами (вы можете найти подробности в репозитории github, ссылка на который приведена выше). Все, что вам нужно знать, это то, что он принимает в качестве входных данных объект, константу F (которая определяет область, в которую необходимо сопоставить объект) и ключ (хэш блока). Когда у нас есть все числа, мы сортируем список в порядке возрастания, а затем создаем новый список, называемый различиями, который содержит разницу между двумя соседними числами в отсортированном списке чисел.
числа := make([]uint64, 0, N) // Перебрать все объекты и преобразовать их в числа, равномерно распределенные в диапазоне [0, F] // и сохранить эти числа как список чисел для o := объекты диапазона { // Используя заданный ключ, максимальное число (F) и байты объекта (o), // преобразовать объект в число от 0 до F. v := convertToNumber(b, F, ключ) числа = добавить (числа, v) } // сортируем список чисел sort.Slice (числа, func (i, j int) bool { возвращаемые числа [i] < номера [j] }) // Преобразование списка чисел в список различий различия := make([]uint64, N) для i, num := диапазон чисел { если я == 0 { различия [i] = число продолжать } различия [i] = число - числа [i-1] }
большой! Вот картинка, показывающая список чисел и различий.
Последним шагом является кодирование списка различий с использованием кодирования Голомба-Райса. Вспомните из предыдущего объяснения, что нам нужно разделить каждую разность на наиболее вероятное значение, а затем закодировать частное и остаток. В нашем предыдущем примере я сказал, что наиболее вероятное значение равно M, а остаток будет между [0, M]. Однако BIP158 этого не делает, так как мы нашли 2, что не является тем параметром, который на самом деле минимизирует конечный размер фильтра. Поэтому вместо использования M мы определяем новую константу P и используем 2^P в качестве параметра Голомба-Райса. P определяется как 19 . Это означает, что мы делим каждую разность на 2 ^ 19, чтобы получить частное и остаток, а остаток кодируется в двоичном формате с 19 битами.
фильтр := bstream.NewBStreamWriter(0) // Для каждого значения в списке различий получаем частное и остаток путем деления на 2^P. для _, d := разность диапазонов { q := math.Floor(float64(d)/math.Exp2(float64(P))) r := d - uint64(math.Exp2(float64(P))*q) // Кодировщик для я := 0; я < интервал (д); я++ { filter.WriteBit (истина) } filter.WriteBit(false) filter.WriteBits(r, P) }
большой! Теперь мы можем вывести фильтр, получив:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0 b0c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56 ade12fa2e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
Точно такой же фильтр, как и в биткойне, за исключением первых двух байтов! Почему разница в первых 2 байтах? Потому что BIP говорит, что значение N должно быть закодировано в формате CompactSize и отображаться перед фильтром, чтобы получатель мог его декодировать. Это делается:
fd := filter.Bytes() байты буфера. Буфер buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) ошибка = провод.WriteInt(&buffer, 0, uint64(N)) если ошибка != ноль { вернуть ноль, ошибиться } _, ошибка = буфер. Запись (fd) если ошибка != ноль { вернуть ноль, ошибиться }
Если теперь мы снова распечатаем фильтр, мы обнаружим, что он точно такой же, как и у биткойна:
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df5743786402383 3f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5 b0b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b 56ade12fa 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
успех!
Однако мое личное понимание состоит в том, что нет необходимости добавлять N к фильтру. Если вы знаете значение P, то вы можете найти значение N. Давайте посмотрим, сможем ли мы восстановить исходный список чисел, используя вывод первого фильтра:
b := bstream.NewBStreamReader(фильтр) ( числа []uint64 предыдущийNum uint64 ) для { // Чтение частного из строки байтов. Первый встреченный 0 указывает на конец частного // До встречи с 0 число 1 представляет собой частное q uint64 c, ошибка := b.ReadBit() если ошибка != ноль { вернуть ошибку } для с { д++ c, ошибка = b.ReadBit() если error.Is(ошибка, io.EOF) { перерыв } иначе если ошибка != ноль { вернуть ошибку } } // Следующие P бит кодируют остаток г, ошибка := b.ReadBits(P) если error.Is(ошибка, io.EOF) { перерыв } иначе если ошибка != ноль { вернуть ошибку } n := q*uint64(math.Exp2(float64(P))) + r число := n + предыдущее число числа = добавить (числа, число) предыдущее число = число } fmt.Println(числа)
Описанная выше операция дает тот же список чисел, поэтому мы можем восстановить его, не зная N. Поэтому я не уверен, в чем причина добавления N к фильтру. Если вы знаете, почему N должен быть включен, пожалуйста, дайте мне знать!
Спасибо за прочтение!