У цій статті я коротко описую потребу в легких клієнтах у Bitcoin і чому «компактні блокові фільтри» задовольняють цю потребу краще, ніж «фільтри Блума». Потім я докладно поясню, як працює фільтр щільних блоків, із покроковим описом створення такого фільтра в тестовій мережі.
Значення блокового фільтра
Клієнт біткойн-лайт (програмне забезпечення біткойн-лайт) — це програмне забезпечення, метою якого є не зберігання блокчейну біткойнів, а підтримка гаманця біткойнів. Це означає, що він повинен мати можливість транслювати транзакції в мережу, але, що найважливіше, він повинен мати можливість знаходити нові транзакції в ланцюжку, пов’язаному з цим гаманцем. Існує два типи таких пов’язаних транзакцій: надсилання коштів на цей гаманець (створення нового виводу для адреси цього гаманця) і витрачання одного з UTXO, контрольованих цим гаманцем.
Що не так із фільтрами bloom?
До BIP 158 найпоширенішим підходом для легких клієнтів був фільтр Блума, описаний у BIP 371. Шаблон фільтра Блума полягає в тому, що ви берете всі об’єкти даних, які вас цікавлять (наприклад, відкриті ключі сценаріїв UTXO, які були використані та створені), хешуєте їх один за одним кілька разів і додаєте кожен результат до In растрове зображення, яке називається "фільтр цвітіння". Цей фільтр відображає те, що вас цікавить. Потім ви надсилаєте цей фільтр на біткойн-вузол, якому довіряєте, і просите їх надіслати вам усе, що відповідає цьому фільтру.
Проблема полягає в тому, що цей процес не дуже конфіденційний, тому що ви все одно передаєте деяку інформацію до вузла Bitcoin, який приймає фільтр. Вони можуть знати угоди, які вас цікавлять, і угоди, які вас взагалі не цікавлять; вони також не можуть надсилати вам речі, які відповідають фільтрам. Отже, це не ідеально для легких клієнтів. Але в той же час він не ідеальний для біткоін-вузлів, які обслуговують легких клієнтів. Кожного разу, коли ви надсилаєте фільтр, вони повинні завантажити відповідний блок з диска, а потім визначити, чи збігаються будь-які транзакції з вашим фільтром. Просто продовжуйте надсилати фальшиві фільтри, і ви можете бомбити їх - по суті 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. І 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 (або близьким до нашого коефіцієнта помилкових позитивних результатів, який дорівнює М), тому візьміть частку кожного числа на М (діліть кожне число на 5 і ігноруйте відкидання залишку), швидше за все буде 0 (якщо число трохи менше 5) або 1 (якщо число трохи більше 5). Також можливо, що частка дорівнює 2, 3 і т. д., але ймовірність набагато менша. здорово! Тож ми можемо скористатися цим: ми використовуватимемо якомога менше бітів для кодування менших часток, тоді як використовуватимемо більше біткойнів для кодування більших, але менш імовірних часток. Потім нам також потрібно закодувати залишок (оскільки ми хочемо мати можливість точно реконструювати весь список), який завжди буде в діапазоні [0, M - 1] (у цьому випадку [0, 4]). Для кодувальника ми використовуємо такі відображення:
Наведене вище відображення легко зрозуміти: кількість цифр 1s вказує на частку, яку ми хочемо закодувати, а 0 вказує на кінець кодування частки. Таким чином, для кожного числа в нашому списку ми можемо використати наведену вище таблицю для кодування частки, а потім перетворити залишок у двійковий за допомогою бітового трака, який може представляти максимальне значення M-1. Тут залишок дорівнює 4, а потрібні лише 3 біти. Ось таблиця, що показує можливі залишки та їх кодування для нашого прикладу:
Отже, в ідеалі наш список [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] можна було б закодувати так:
Перш ніж перейти до більш реалістичного випадку, давайте подивимося, чи зможемо ми відновити наш початковий список за допомогою цього фільтра.
Тепер ми маємо «0000100001000010000100001000010000100001000010000». Ми знаємо код Голомба-Райса, і ми знаємо, що M дорівнює 5 (оскільки це буде загальновідомо, відомо кожному, хто використовує цю конструкцію фільтра). Оскільки ми знаємо, що M дорівнює 5, ми знаємо, що буде 3 біти для кодування залишку. Таким чином, ми можемо перетворити цей фільтр у наступний список масиву "частка-залишок":
Знаючи, що приватне отримано діленням на M(5), ми можемо відновити:
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Крім того, ми знаємо, що цей список представляє різницю між двома суміжними числами, тому ми можемо відновити вихідний список:
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Більш реалістичний приклад
Зараз ми спробуємо побудувати фільтр для реального блоку тестової мережі Bitcoin. Я буду використовувати блок 2101914. Давайте подивимося, як виглядає його фільтр:
Гаразд, шановний, давайте подивимося, як ми можемо побудувати такий фільтр із блоків.
Повний код, використаний тут, можна знайти в цьому репозиторії github. Я просто покажу тут деякі фрагменти псевдокоду. Ядром цього коду є функція під назвою constructFilter, яка може використовуватися біткойн-клієнтами для виклику біткойн і відповідних блоків. Функція виглядає так:
func constructFilter(bc *bitcoind.Bitcoind, блокувати bitcoind.Block) ([]байт, помилка) {
// 1 збирає всі об’єкти з блоку, які ми хочемо додати до фільтра
// 2 Перетворіть ці об'єкти на числа та відсортуйте їх
// 3 Отримати різницю між двома сусідніми числами в списку сортованих чисел
// 4 Для кодування цих відмінностей використовуйте кодування Голомба-Райса
}
Отже, перший крок — зібрати всі об’єкти з блоку, які ми хочемо додати до фільтра. Починаючи з BIP, ми знаємо, що ці об’єкти включають усі використані відкриті ключі сценарію та кожен вихідний відкритий ключ сценарію. BIP також встановлює деякі додаткові правила: ми пропускаємо вхідні дані для транзакції coinbase (що не має сенсу, оскільки вона не має вхідних даних), і ми передаємо всі виходи OP_RETURN. Ми також видаляємо дублікати даних. Якщо є два ідентичних відкритих ключа сценарію, ми додаємо його до фільтра лише один раз.
// список об'єктів, які ми хочемо додати до фільтра
// Включити всі використані відкриті ключі сценарію та кожен вихідний відкритий ключ сценарію
// Ми використовуємо "карту", яка видаляє дублікати відкритих ключів сценарію
objects := make(map [string] структура{})
// сприяти кожній транзакції в блоці
for i, tx := range block.Tx {
// Додати відкритий ключ сценарію для кожного виводу
// в наш список об'єктів
для _, txOut := діапазон tx.Vout {
PubKey := txOut.PubKey
if len(PubKey) == 0 {
продовжувати
}
// Пропустити, якщо виводиться OP_RETURN (0x6a).
якщо спк [0] == 0x6a {
продовжувати
}
об'єктів [skpStr] = struct{}{}
}
// не додавати введення транзакції coinbase
if i == 0 {
продовжувати
}
// Для кожного введення отримати його відкритий ключ сценарію
для _, txIn := діапазон tx.Vin {
prevTx, помилка := bc.GetRawTransaction(txIn.Txid)
if err != nil {
повернути нуль, помилка
}
PubKey := prevTx.Vout[txIn.Vout].PubKey
if len(PubKey) == 0 {
продовжувати
}
об'єктів [spkStr] = struct{}{}
}
}
Добре, тепер усі об’єкти зібрано. Тепер ми визначаємо змінну N як довжину графа об’єкта. Тут N дорівнює 85 .
Наступним кроком є перетворення нашого об’єкта на числа, рівномірно розподілені на інтервалі. Знову ж таки, діапазон залежить від того, наскільки високий рівень помилкових позитивних результатів ви хочете. BIP158 визначає постійну M як 784931. Це означає, що ймовірність помилкового позитивного результату становить 1 з 784931. Так само, як ми робили раніше, ми беремо коефіцієнт помилкових позитивних результатів M помножити на N і отримуємо діапазон розподілу всіх чисел. Ми визначимо цей діапазон як F, тобто F = M * N . Тут F = 66719135. Я не збираюся вдаватися в подробиці функцій, які відображають об’єкти на числа (ви можете знайти подробиці в репозиторії github, посилання на яке наведене вище). Все, що вам потрібно знати, це те, що він приймає як вхідні дані об’єкт, константу F (яка визначає область, до якої потрібно відобразити об’єкт) і ключ (хеш блоку). Отримавши всі числа, ми сортуємо список у порядку зростання, а потім створюємо новий список під назвою різниці, який містить різницю між двома сусідніми числами у відсортованому списку чисел.
числа := make([]uint64, 0, N)
// Перебираємо всі об’єкти та перетворюємо їх на числа, рівномірно розподілені в діапазоні [0, F]
// і зберегти ці числа як список чисел
for o := діапазон об'єктів {
// Використовуючи заданий ключ, максимальну кількість (F) і байти об’єкта (o),
// перетворити об'єкт на число від 0 до F.
v := convertToNumber(b, F, ключ)
числа = додати(числа, v)
}
// сортування списку чисел
sort.Slice(numbers, func(i, j int) bool { повертає числа [i] < числа [j] })
// Перетворення списку чисел на список різниць
відмінності := make([]uint64, N)
for i, num := діапазон чисел {
if i == 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)
// Кодувальник
для i := 0; i < int(q); i++ {
filter.WriteBit(true)
}
filter.WriteBit(false)
filter.WriteBits(r, P)
}
здорово! Тепер ми можемо вивести фільтр, отримавши:
Точно такий же фільтр, як ми отримали в bitcoin, за винятком перших двох байтів! Чому є різниця в перших 2 байтах? Оскільки BIP каже, що значення N має бути закодовано у форматі CompactSize і з’являтися перед фільтром, щоб його міг декодувати приймач. Це робиться:
fd := filter.Bytes()
буфер байтів.Буфер
buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd))
err = wire.WriteInt(&buffer, 0, uint64(N))
if err != nil {
повернути нуль, помилка
}
_, err = buffer.Write(fd)
if err != nil {
повернути нуль, помилка
}
Якщо ми тепер знову роздрукуємо фільтр, ми побачимо, що він точно такий же, як і результат bitcoin:
Однак я особисто розумію, що немає потреби додавати N до фільтра. Якщо ви знаєте значення P, ви можете знайти значення N. Давайте подивимося, чи зможемо ми відновити вихідний список чисел, використовуючи вихідні дані першого фільтра:
b := bstream.NewBStreamReader(фільтр)
(
числа []uint64
prevNum uint64
)
для {
// Читання частки з байтового рядка. Перший зустрічається 0 означає кінець частки
// До зустрічі з 0 число 1 представляє приватне
q uint64
c, err := b.ReadBit()
if err != nil {
повернення помилка
}
для c {
q++
c, err = b.ReadBit()
if errors.Is(err, io.EOF) {
перерва
} else if err != nil {
повернення помилка
}
}
// Наступні P бітів кодують залишок
r, err := b.ReadBits(P)
if errors.Is(err, io.EOF) {
перерва
} else if err != nil {
повернення помилка
}
n := q*uint64(math.Exp2(float64(P))) + r
num := n + prevNum
числа = додати(числа, кількість)
prevNum = число
}
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
Автор Ель Мутон
У цій статті я коротко описую потребу в легких клієнтах у Bitcoin і чому «компактні блокові фільтри» задовольняють цю потребу краще, ніж «фільтри Блума». Потім я докладно поясню, як працює фільтр щільних блоків, із покроковим описом створення такого фільтра в тестовій мережі.
Значення блокового фільтра
Клієнт біткойн-лайт (програмне забезпечення біткойн-лайт) — це програмне забезпечення, метою якого є не зберігання блокчейну біткойнів, а підтримка гаманця біткойнів. Це означає, що він повинен мати можливість транслювати транзакції в мережу, але, що найважливіше, він повинен мати можливість знаходити нові транзакції в ланцюжку, пов’язаному з цим гаманцем. Існує два типи таких пов’язаних транзакцій: надсилання коштів на цей гаманець (створення нового виводу для адреси цього гаманця) і витрачання одного з UTXO, контрольованих цим гаманцем.
Що не так із фільтрами bloom?
До BIP 158 найпоширенішим підходом для легких клієнтів був фільтр Блума, описаний у BIP 371. Шаблон фільтра Блума полягає в тому, що ви берете всі об’єкти даних, які вас цікавлять (наприклад, відкриті ключі сценаріїв UTXO, які були використані та створені), хешуєте їх один за одним кілька разів і додаєте кожен результат до In растрове зображення, яке називається "фільтр цвітіння". Цей фільтр відображає те, що вас цікавить. Потім ви надсилаєте цей фільтр на біткойн-вузол, якому довіряєте, і просите їх надіслати вам усе, що відповідає цьому фільтру.
Проблема полягає в тому, що цей процес не дуже конфіденційний, тому що ви все одно передаєте деяку інформацію до вузла Bitcoin, який приймає фільтр. Вони можуть знати угоди, які вас цікавлять, і угоди, які вас взагалі не цікавлять; вони також не можуть надсилати вам речі, які відповідають фільтрам. Отже, це не ідеально для легких клієнтів. Але в той же час він не ідеальний для біткоін-вузлів, які обслуговують легких клієнтів. Кожного разу, коли ви надсилаєте фільтр, вони повинні завантажити відповідний блок з диска, а потім визначити, чи збігаються будь-які транзакції з вашим фільтром. Просто продовжуйте надсилати фальшиві фільтри, і ви можете бомбити їх - по суті 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. І 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 (або близьким до нашого коефіцієнта помилкових позитивних результатів, який дорівнює М), тому візьміть частку кожного числа на М (діліть кожне число на 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, 5]
Крім того, ми знаємо, що цей список представляє різницю між двома суміжними числами, тому ми можемо відновити вихідний список:
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Більш реалістичний приклад
Зараз ми спробуємо побудувати фільтр для реального блоку тестової мережі Bitcoin. Я буду використовувати блок 2101914. Давайте подивимося, як виглядає його фільтр:
$ bitcoin-cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ bitcoin-cli getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { "фільтр": "5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864 023833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e694 5a65a5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558 f62b34b56ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", "заголовок": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }
Гаразд, шановний, давайте подивимося, як ми можемо побудувати такий фільтр із блоків.
Повний код, використаний тут, можна знайти в цьому репозиторії github. Я просто покажу тут деякі фрагменти псевдокоду. Ядром цього коду є функція під назвою constructFilter, яка може використовуватися біткойн-клієнтами для виклику біткойн і відповідних блоків. Функція виглядає так:
func constructFilter(bc *bitcoind.Bitcoind, блокувати bitcoind.Block) ([]байт, помилка) { // 1 збирає всі об’єкти з блоку, які ми хочемо додати до фільтра // 2 Перетворіть ці об'єкти на числа та відсортуйте їх // 3 Отримати різницю між двома сусідніми числами в списку сортованих чисел // 4 Для кодування цих відмінностей використовуйте кодування Голомба-Райса }
Отже, перший крок — зібрати всі об’єкти з блоку, які ми хочемо додати до фільтра. Починаючи з BIP, ми знаємо, що ці об’єкти включають усі використані відкриті ключі сценарію та кожен вихідний відкритий ключ сценарію. BIP також встановлює деякі додаткові правила: ми пропускаємо вхідні дані для транзакції coinbase (що не має сенсу, оскільки вона не має вхідних даних), і ми передаємо всі виходи OP_RETURN. Ми також видаляємо дублікати даних. Якщо є два ідентичних відкритих ключа сценарію, ми додаємо його до фільтра лише один раз.
// список об'єктів, які ми хочемо додати до фільтра // Включити всі використані відкриті ключі сценарію та кожен вихідний відкритий ключ сценарію // Ми використовуємо "карту", яка видаляє дублікати відкритих ключів сценарію objects := make(map [string] структура{}) // сприяти кожній транзакції в блоці for i, tx := range block.Tx { // Додати відкритий ключ сценарію для кожного виводу // в наш список об'єктів для _, txOut := діапазон tx.Vout { PubKey := txOut.PubKey if len(PubKey) == 0 { продовжувати } // Пропустити, якщо виводиться OP_RETURN (0x6a). якщо спк [0] == 0x6a { продовжувати } об'єктів [skpStr] = struct{}{} } // не додавати введення транзакції coinbase if i == 0 { продовжувати } // Для кожного введення отримати його відкритий ключ сценарію для _, txIn := діапазон tx.Vin { prevTx, помилка := bc.GetRawTransaction(txIn.Txid) if err != nil { повернути нуль, помилка } PubKey := prevTx.Vout[txIn.Vout].PubKey if len(PubKey) == 0 { продовжувати } об'єктів [spkStr] = struct{}{} } }
Добре, тепер усі об’єкти зібрано. Тепер ми визначаємо змінну N як довжину графа об’єкта. Тут N дорівнює 85 .
Наступним кроком є перетворення нашого об’єкта на числа, рівномірно розподілені на інтервалі. Знову ж таки, діапазон залежить від того, наскільки високий рівень помилкових позитивних результатів ви хочете. BIP158 визначає постійну M як 784931. Це означає, що ймовірність помилкового позитивного результату становить 1 з 784931. Так само, як ми робили раніше, ми беремо коефіцієнт помилкових позитивних результатів M помножити на N і отримуємо діапазон розподілу всіх чисел. Ми визначимо цей діапазон як F, тобто F = M * N . Тут F = 66719135. Я не збираюся вдаватися в подробиці функцій, які відображають об’єкти на числа (ви можете знайти подробиці в репозиторії github, посилання на яке наведене вище). Все, що вам потрібно знати, це те, що він приймає як вхідні дані об’єкт, константу F (яка визначає область, до якої потрібно відобразити об’єкт) і ключ (хеш блоку). Отримавши всі числа, ми сортуємо список у порядку зростання, а потім створюємо новий список під назвою різниці, який містить різницю між двома сусідніми числами у відсортованому списку чисел.
числа := make([]uint64, 0, N) // Перебираємо всі об’єкти та перетворюємо їх на числа, рівномірно розподілені в діапазоні [0, F] // і зберегти ці числа як список чисел for o := діапазон об'єктів { // Використовуючи заданий ключ, максимальну кількість (F) і байти об’єкта (o), // перетворити об'єкт на число від 0 до F. v := convertToNumber(b, F, ключ) числа = додати(числа, v) } // сортування списку чисел sort.Slice(numbers, func(i, j int) bool { повертає числа [i] < числа [j] }) // Перетворення списку чисел на список різниць відмінності := make([]uint64, N) for i, num := діапазон чисел { if i == 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) // Кодувальник для i := 0; i < int(q); i++ { filter.WriteBit(true) } filter.WriteBit(false) filter.WriteBits(r, P) }
здорово! Тепер ми можемо вивести фільтр, отримавши:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5 b0b0c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b3 4b56ade12fa2e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
Точно такий же фільтр, як ми отримали в bitcoin, за винятком перших двох байтів! Чому є різниця в перших 2 байтах? Оскільки BIP каже, що значення N має бути закодовано у форматі CompactSize і з’являтися перед фільтром, щоб його міг декодувати приймач. Це робиться:
fd := filter.Bytes() буфер байтів.Буфер buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) err = wire.WriteInt(&buffer, 0, uint64(N)) if err != nil { повернути нуль, помилка } _, err = buffer.Write(fd) if err != nil { повернути нуль, помилка }
Якщо ми тепер знову роздрукуємо фільтр, ми побачимо, що він точно такий же, як і результат bitcoin:
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df5743786402383 3f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65 a5b0b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62 b34b56ade12fa 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
успіх!
Однак я особисто розумію, що немає потреби додавати N до фільтра. Якщо ви знаєте значення P, ви можете знайти значення N. Давайте подивимося, чи зможемо ми відновити вихідний список чисел, використовуючи вихідні дані першого фільтра:
b := bstream.NewBStreamReader(фільтр) ( числа []uint64 prevNum uint64 ) для { // Читання частки з байтового рядка. Перший зустрічається 0 означає кінець частки // До зустрічі з 0 число 1 представляє приватне q uint64 c, err := b.ReadBit() if err != nil { повернення помилка } для c { q++ c, err = b.ReadBit() if errors.Is(err, io.EOF) { перерва } else if err != nil { повернення помилка } } // Наступні P бітів кодують залишок r, err := b.ReadBits(P) if errors.Is(err, io.EOF) { перерва } else if err != nil { повернення помилка } n := q*uint64(math.Exp2(float64(P))) + r num := n + prevNum числа = додати(числа, кількість) prevNum = число } fmt.Println(числа)
Наведена вище операція створює той самий список чисел, тому ми можемо реконструювати його, не знаючи N. Тож я не впевнений, у чому причина додавання N до фільтра. Якщо ви знаєте, чому N потрібно включити, дайте мені знати!
Дякуємо за читання!