Dalam artikel ini, saya menjelaskan secara singkat kebutuhan klien ringan dalam Bitcoin dan mengapa "filter blok kompak" melayani kebutuhan ini lebih baik daripada "filter Bloom". Saya kemudian menjelaskan secara mendalam cara kerja filter blok padat, dengan panduan langkah demi langkah membangun filter semacam itu di testnet.
Arti filter blok
Klien ringan bitcoin (perangkat lunak ringan bitcoin) adalah perangkat lunak yang tujuannya bukan untuk menyimpan blockchain bitcoin tetapi untuk mendukung dompet bitcoin. Artinya, ia harus dapat menyiarkan transaksi ke jaringan, tetapi yang terpenting, ia harus dapat menemukan transaksi baru dari rantai yang terkait dengan dompet ini. Ada dua jenis transaksi terkait seperti itu: mengirim dana ke dompet ini (membuat keluaran baru untuk alamat dompet ini), dan membelanjakan salah satu UTXO yang dikendalikan oleh dompet ini.
Apa yang salah dengan filter mekar?
Sebelum BIP 158, pendekatan yang paling umum untuk klien ringan adalah filter Bloom yang dijelaskan dalam BIP 371. Pola filter Bloom adalah Anda mengambil semua objek data yang Anda minati (mis., kunci publik skrip UTXO yang digunakan dan dibuat), hash mereka satu per satu beberapa kali, dan tambahkan setiap hasil ke In bitmap yang disebut "filter mekar". Filter ini mewakili apa yang Anda minati. Kemudian, Anda mengirim filter ini ke simpul Bitcoin yang Anda percayai dan meminta mereka mengirimkan semua yang cocok dengan filter ini.
Masalahnya adalah proses ini tidak terlalu pribadi, karena Anda masih membocorkan beberapa informasi ke node Bitcoin yang menerima filter tersebut. Mereka dapat mengetahui penawaran yang Anda minati dan penawaran yang sama sekali tidak Anda minati; mereka juga tidak dapat mengirimi Anda hal-hal yang cocok dengan filter. Jadi, ini tidak ideal untuk klien ringan. Tetapi pada saat yang sama, ini tidak ideal untuk node Bitcoin yang melayani klien ringan. Setiap kali Anda mengirim filter, mereka harus memuat blok yang relevan dari disk dan kemudian menentukan apakah ada transaksi yang cocok dengan filter Anda. Terus kirimkan filter palsu dan Anda dapat mengebomnya - pada dasarnya serangan DOS. Dibutuhkan sangat sedikit energi untuk membuat filter, tetapi membutuhkan banyak energi untuk menanggapi permintaan semacam itu.
Filter blok padat
OK, maka atribut yang kita butuhkan adalah:
Privasi yang lebih kuat
Asimetri beban klien-server lebih sedikit. Artinya, harus ada lebih sedikit pekerjaan yang harus dilakukan di sisi server.
Kurang percaya. Klien ringan tidak perlu khawatir server tidak mengembalikan transaksi terkait.
Menggunakan filter blok padat, server (node penuh) akan membuat filter deterministik untuk setiap blok, termasuk semua objek data di blok ini. Filter ini hanya perlu dihitung sekali dan disimpan selamanya. Jika klien ringan meminta filter untuk blok tertentu, tidak ada asimetri di sini - karena server tidak perlu melakukan pekerjaan lebih dari klien yang meminta. Klien ringan juga dapat memilih beberapa sumber informasi untuk mengunduh blok lengkap untuk memastikan konsistensinya; selain itu, klien ringan selalu dapat mengunduh blok lengkap untuk memeriksa apakah filter yang disediakan oleh server sudah benar. Benar (cocok dengan blok yang relevan isi). Manfaat lain adalah lebih pribadi dengan cara ini. Klien ringan tidak perlu lagi mengirim sidik jari dari data yang diinginkannya ke server. Juga menjadi lebih sulit untuk menganalisis aktivitas klien ringan. Setelah klien ringan mendapatkan filter seperti itu dari server, ia memeriksa apakah filter berisi data yang diinginkan, dan jika demikian, klien ringan meminta blok lengkap. Juga harus ditunjukkan bahwa untuk melayani klien ringan dengan cara ini, node penuh perlu mempertahankan filter ini, dan klien ringan mungkin juga ingin mempertahankan beberapa filter, jadi pertahankan filter seringan mungkin Kuantitas sangat penting ( inilah mengapa ini disebut "filter blok padat").
sangat bagus! Sekarang kita masuk ke barang langka. Bagaimana filter seperti itu dibuat? Seperti apa bentuknya?
Apa kebutuhan kita?
Kami ingin memasukkan sidik jari dari objek tertentu ke dalam filter, sehingga ketika klien ingin memeriksa apakah suatu blok mungkin berisi sesuatu yang terkait dengan dirinya sendiri, mereka dapat menghitung semua objek dan memeriksa filter Apakah cocok dengan objek ini.
Kami ingin filter ini sekecil mungkin.
Intinya, yang kita inginkan adalah sesuatu yang dapat meringkas beberapa informasi dari sebuah blok dengan volume yang jauh lebih kecil dari blok tersebut.
Informasi dasar yang terkandung dalam filter adalah: kunci publik skrip dari setiap masukan dari setiap transaksi (yaitu, kunci publik skrip dari setiap UTXO yang digunakan), dan kunci publik skrip dari setiap keluaran dari setiap transaksi. Pada dasarnya seperti ini:
objek = {spk1, spk2, spk3, spk4, ..., spkN} // daftar kunci publik skrip N
Secara teknis, kita dapat berhenti di sini - daftar kunci publik skrip seperti itu juga dapat berfungsi sebagai filter kita. Ini adalah versi ringkas dari blok yang berisi informasi yang dibutuhkan oleh klien ringan. Dengan daftar seperti itu, klien ringan dapat memastikan 100% apakah ada transaksi yang menarik dalam suatu blok. Tetapi daftar seperti itu sangat besar. Oleh karena itu, langkah kita selanjutnya adalah membuat daftar ini sekompak mungkin. Di sinilah segalanya menjadi menarik.
Pertama, kita dapat mengonversi setiap objek menjadi angka dalam rentang tertentu, dan membuat setiap nomor objek terdistribusi secara merata dalam rentang ini. Misalkan kita memiliki 10 objek (N = 10), dan kemudian kita memiliki semacam fungsi yang mengubah setiap objek menjadi angka. Katakanlah kita memilih rentang [0, 10] (karena kita memiliki 10 objek). Sekarang, fungsi "hash to number" kita akan mengambil setiap objek sebagai input dan menghasilkan angka dengan ukuran masing-masing [0, 10]. Angka-angka didistribusikan secara merata di seluruh rentang ini. Artinya, setelah menyortir, kita akan mendapatkan grafik seperti ini (dalam kasus yang sangat, sangat ideal):
Pertama-tama, ini bagus karena kami telah secara drastis mengurangi ukuran sidik jari setiap objek. Sekarang setiap objek hanyalah sebuah angka. Jadi, filter baru kami terlihat seperti ini:
angka := {1,2,3,4,5,6,7,8,9,10}
Klien ringan mengunduh filter semacam itu, berharap untuk mengetahui apakah objek yang dicarinya cocok dengan filter tersebut. Mereka hanya mengambil objek yang mereka minati dan menjalankan fungsi "hash to number" yang sama untuk melihat apakah hasilnya ada di filter ini. Dimana masalahnya? Masalahnya adalah angka-angka di filter sudah mengambil setiap kemungkinan di ruang itu! Ini berarti bahwa objek apa pun yang menjadi perhatian klien ringan, hasil numerik yang dihasilkan harus cocok dengan filter ini. Dengan kata lain, filter ini memiliki "laju positif palsu" sebesar 1 (Catatan Penerjemah: "false positive" di sini berarti bahwa blok tersebut mungkin tidak berisi Hasil yang diperoleh filter adalah ya). Ini tidak begitu baik. Ini juga menunjukkan bahwa dalam proses mengompresi data untuk menghasilkan filter, kami kehilangan terlalu banyak informasi. Kami membutuhkan tingkat positif palsu yang lebih tinggi. Kemudian, misalkan kita ingin tingkat positif palsu menjadi 5. Kemudian, kita dapat membuat objek di blok tersebut sama rata dengan angka dalam rentang [0, 50]:
Itu terlihat lebih baik seperti itu. Jika saya klien dan mengunduh filter seperti itu, saya perlu memeriksa apakah objek yang saya pedulikan ada di blok yang sesuai melalui filter, dan kemungkinan filter mengatakan ya tetapi tidak di blok (false positive) akan berkurang menjadi 1/5. Bagus, sekarang kita memetakan 10 objek ke angka antara 0 dan 50. Daftar nomor baru ini adalah filter kami. Sekali lagi, kami dapat berhenti kapan saja, namun kami dapat mengompresnya lebih jauh!
Kami sekarang memiliki daftar nomor terurut yang didistribusikan secara merata dalam interval [0, 50]. Kita tahu bahwa ada 10 nomor dalam daftar ini. Ini berarti, kita dapat menyimpulkan bahwa perbedaan antara dua angka yang berdekatan dalam daftar urutan angka ini kemungkinan besar adalah 5. Secara umum, jika kita memiliki N objek dan menginginkan laju positif palsu M, maka ukuran ruangnya harus N * M . Artinya, ukuran angka-angka ini harus antara 0 dan N * M, tetapi (setelah disortir) probabilitas interpolasi dari dua angka yang berdekatan yang diperiksa adalah M. Dan M harus disimpan lebih kecil dari angka di ruang N*M. Jadi, alih-alih menyimpan setiap angka, kita dapat menyimpan selisih antara dua angka yang berdekatan. Dalam contoh di atas, ini berarti bahwa alih-alih menyimpan [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] sebagai filter, kami menyimpan [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], yang darinya mudah untuk merekonstruksi daftar awal. Jika Anda memperkecil, menyimpan angka 50 jelas membutuhkan lebih banyak ruang daripada menyimpan angka 5. Tapi mengapa berhenti di situ? Mari kompres sedikit lagi!
Langkah selanjutnya adalah menggunakan "Golomb-Rice encoding". Metode pengkodean ini dapat dengan baik menyandikan daftar di mana setiap angka dalam tabel sangat dekat dengan angka tertentu. Dan daftar kami kebetulan hanya itu! Setiap angka dalam daftar kami kemungkinan besar mendekati 5 (atau mendekati tingkat positif palsu kami, yaitu M), jadi ambil hasil bagi setiap angka dengan M (bagi setiap angka dengan 5 dan abaikan sisanya), kemungkinan besar akan menjadi 0 (jika jumlahnya sedikit kurang dari 5) atau 1 (jika jumlahnya sedikit lebih besar dari 5). Mungkin juga hasil bagi adalah 2, 3, dst., tetapi probabilitasnya jauh lebih kecil. Besar! Jadi kita dapat mengambil keuntungan dari ini: kita akan menggunakan bit sesedikit mungkin untuk menyandikan hasil bagi yang lebih kecil, sambil menggunakan lebih banyak bitcoin untuk menyandikan hasil bagi yang lebih besar, tetapi kecil kemungkinannya. Kemudian, kita juga perlu menyandikan sisanya (karena kita ingin dapat merekonstruksi seluruh daftar dengan tepat), yang akan selalu berada dalam rentang [0, M - 1] (dalam hal ini [0, 4]). Untuk pembuat enkode, kami menggunakan pemetaan berikut:
Pemetaan di atas mudah dipahami: jumlah digit 1 menunjukkan hasil bagi yang ingin kita enkode, dan 0 menunjukkan akhir dari hasil bagi pengkodean. Jadi, untuk setiap angka dalam daftar kita, kita dapat menggunakan tabel di atas untuk menyandikan hasil bagi, lalu mengonversi sisanya menjadi biner menggunakan bittruck yang dapat mewakili nilai maksimum M-1. Di sini sisanya adalah 4, dan hanya diperlukan 3 bit. Berikut adalah tabel yang menunjukkan kemungkinan sisa dan penyandiannya untuk contoh kita:
Jadi, idealnya, daftar kita [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] akan dikodekan sebagai:
Sebelum kita pindah ke kasus yang lebih realistis, mari kita lihat apakah kita bisa memulihkan daftar asli kita dengan filter ini.
Sekarang apa yang kita miliki adalah "0000100001000010000100001000010000100001000010000". Kami tahu kode Golomb-Rice, dan kami tahu bahwa M adalah 5 (karena ini akan menjadi pengetahuan umum, diketahui semua orang yang menggunakan konstruksi filter ini). Karena kita tahu bahwa M adalah 5, kita tahu bahwa akan ada 3 bit untuk menyandikan sisanya. Jadi, kita dapat mengonversi filter ini menjadi daftar larik "hasil bagi-sisa" berikut:
Baiklah sayang, mari kita lihat bagaimana kita bisa membuat filter seperti itu dari blok.
Kode lengkap yang digunakan di sini dapat ditemukan di repositori github ini. Saya hanya akan menampilkan beberapa potongan pseudocode di sini. Inti dari kode ini adalah fungsi yang disebut constructFilter, yang dapat digunakan oleh klien bitcoin untuk memanggil bitcoind dan blok terkait. Fungsinya terlihat seperti ini:
func constructFilter(bc *bitcoind.Bitcoind, blokir bitcoind.Block) ([]byte, error) {
// 1 mengumpulkan semua objek dari blok yang ingin kita tambahkan ke filter
// 2 Ubah objek ini menjadi angka dan urutkan
// 3 Dapatkan selisih antara dua angka yang berdekatan dalam daftar angka yang diurutkan
// 4 Gunakan pengkodean Golomb-Rice untuk menyandikan perbedaan ini
}
Jadi, langkah pertama adalah mengumpulkan semua objek dari blok yang ingin kita tambahkan ke filter. Mulai dari BIP, kita tahu bahwa objek ini menyertakan semua kunci publik skrip yang dihabiskan, dan setiap kunci publik skrip keluaran. BIP juga menetapkan beberapa aturan tambahan: kami melewatkan input ke transaksi coinbase (yang tidak masuk akal karena tidak memiliki input), dan kami meneruskan semua output OP_RETURN. Kami juga menghapus duplikat data. Jika ada dua kunci publik skrip yang identik, kami hanya menambahkannya sekali ke filter.
// daftar objek yang ingin kita tambahkan ke filter
// Sertakan semua kunci publik skrip yang digunakan, dan setiap kunci publik skrip keluaran
// Kami menggunakan "peta", yang menghapus kunci publik skrip duplikat
objek := make(peta [string] struktur{})
// fasilitasi setiap transaksi di blok
untuk i, tx := range block.Tx {
// Tambahkan kunci publik skrip untuk setiap output
// ke dalam daftar objek kita
untuk _, txOut := range tx.Vout {
PubKey := txOut.PubKey
jika len(PubKey) == 0 {
melanjutkan
}
// Lewati jika OP_RETURN (0x6a) adalah output
jika spk [0] == 0x6a {
melanjutkan
}
objek [skpStr] = struktur{}{}
}
// jangan tambahkan input transaksi coinbase
jika saya == 0 {
melanjutkan
}
// Untuk setiap input, dapatkan kunci publik skripnya
untuk _, txIn := range tx.Vin {
prevTx, err := bc.GetRawTransaction(txIn.Txid)
jika salah != nihil {
kembali nihil, err
}
PubKey := prevTx.Vout[txIn.Vout].PubKey
jika len(PubKey) == 0 {
melanjutkan
}
objek [spkStr] = struktur{}{}
}
}
Oke, sekarang semua objek sudah terkumpul. Sekarang, kita definisikan variabel N sebagai panjang grafik objek. Di sini, N adalah 85 .
Langkah selanjutnya adalah mengubah objek kita menjadi angka yang terdistribusi secara merata dalam suatu interval. Sekali lagi, kisarannya bergantung pada seberapa tinggi tingkat positif palsu yang Anda inginkan. BIP158 mendefinisikan konstanta M sebagai 784931. Ini berarti probabilitas positif palsu adalah 1 dalam 784931. Sama seperti yang kita lakukan sebelumnya, kita mengambil laju positif palsu M dikalikan N dan mendapatkan jangkauan distribusi semua bilangan. Kami mendefinisikan rentang ini sebagai F, yaitu, F = M * N . Di sini, F = 66719135. Saya tidak akan membahas detail fungsi yang memetakan objek ke angka (Anda dapat menemukan detailnya di repositori github yang ditautkan di atas). Yang perlu Anda ketahui adalah bahwa dibutuhkan sebagai input objek, konstanta F (yang menentukan cakupan objek yang perlu dipetakan), dan kunci (hash blok). Setelah kami memiliki semua angka, kami mengurutkan daftar dalam urutan menaik dan kemudian membuat daftar baru yang disebut perbedaan yang menyimpan perbedaan antara dua angka yang berdekatan dalam daftar angka yang diurutkan.
angka := make([]uint64, 0, N)
// Ulangi semua objek dan ubah menjadi angka yang didistribusikan secara merata dalam rentang [0, F]
// dan simpan nomor ini sebagai daftar nomor
untuk o := rentang objek {
// Menggunakan kunci yang diberikan, nomor maks (F) dan byte objek (o),
// ubah objek menjadi angka antara 0 dan F.
v := convertToNumber(b, F, kunci)
angka = tambahkan(angka, v)
}
// mengurutkan daftar angka
sort.Slice(angka, func(i, j int) bool { mengembalikan angka [i] < angka [j] })
// Ubah daftar angka menjadi daftar perbedaan
perbedaan := make([]uint64, N)
untuk i, num := rentang angka {
jika saya == 0 {
perbedaan [i] = bil
melanjutkan
}
perbedaan [i] = bil - angka[i-1]
}
Besar! Berikut adalah gambar yang menunjukkan daftar angka dan perbedaan.
Saat Anda memperkecil, 85 angka didistribusikan secara merata ke seluruh ruang! Jadi nilai di daftar perbedaan juga sangat kecil.
Langkah terakhir adalah menyandikan daftar perbedaan menggunakan pengkodean Golomb-Rice. Ingat dari penjelasan sebelumnya bahwa kita perlu membagi setiap perbedaan dengan nilai yang paling mungkin dan kemudian menyandikan hasil bagi dan sisanya. Dalam contoh kami sebelumnya, saya mengatakan bahwa nilai yang paling mungkin adalah M, dan sisanya akan berada di antara [0, M]. Namun, BIP158 tidak melakukan ini, karena kami menemukan 2, yang sebenarnya bukan parameter yang meminimalkan ukuran filter akhir. Jadi daripada menggunakan M, kita mendefinisikan konstanta baru P dan menggunakan 2^P sebagai parameter Golomb-Rice. P didefinisikan sebagai 19 . Ini berarti kita membagi setiap perbedaan dengan 2^19 untuk mendapatkan hasil bagi dan sisa, dan sisanya dikodekan dalam biner dengan 19 bit.
filter := bstream.NewBStreamWriter(0)
// Untuk setiap nilai dalam daftar selisih, dapatkan hasil bagi dan sisanya dengan membaginya dengan 2^P.
untuk _, d := rentang perbedaan {
q := matematika.Floor(float64(d)/math.Exp2(float64(P)))
r := d - uint64(math.Exp2(float64(P))*q)
// Pembuat kode
untuk saya := 0; saya < int(q); saya++ {
filter.WriteBit(benar)
}
filter.WriteBit(false)
filter.WriteBits(r, P)
}
Besar! Sekarang kita dapat mengeluarkan filter, mendapatkan:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0 c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa2 e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
Filter yang persis sama dengan yang kami dapatkan di bitcoind kecuali untuk dua byte pertama! Mengapa ada perbedaan dalam 2 byte pertama? Karena BIP mengatakan bahwa nilai N perlu dikodekan dalam format CompactSize dan muncul di depan filter agar dapat didekodekan oleh penerima. Ini dilakukan dengan:
fd := filter.Bytes()
buffer bytes.Buffer
buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd))
err = wire.WriteInt(&buffer, 0, uint64(N))
jika salah != nihil {
kembali nihil, err
}
_, err = penyangga.Tulis(fd)
jika salah != nihil {
kembali nihil, err
}
Jika sekarang kami mencetak filter lagi, kami akan menemukan bahwa itu persis sama dengan hasil bitcoind:
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0 b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12 fa 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
kesuksesan!
Namun, pemahaman pribadi saya adalah tidak perlu menambahkan N ke filter. Jika kamu mengetahui nilai P, maka kamu dapat mencari nilai N. Mari kita lihat apakah kita dapat mengembalikan daftar angka asli menggunakan output dari filter pertama:
b := bstream.NewBStreamReader(filter)
(
angka []uint64
prevNum uint64
)
untuk {
// Baca hasil bagi dari string byte. Angka 0 pertama yang ditemukan menunjukkan akhir dari hasil bagi
// Sebelum menemukan 0, angka 1 mewakili hasil bagi
q uint64
c, err := b.ReadBit()
jika salah != nihil {
kembali salah
}
untuk c {
q++
c, err = b.ReadBit()
jika kesalahan.Is(err, io.EOF) {
merusak
} lain jika err != nil {
kembali salah
}
}
// P bit berikutnya menyandikan sisanya
r, err := b.ReadBits(P)
jika kesalahan.Is(err, io.EOF) {
merusak
} lain jika err != nil {
kembali salah
}
n := q*uint64(math.Exp2(float64(P))) + r
num := n + prevNum
angka = tambahkan(angka, bil)
prevNum = bil
}
fmt.Println(angka)
Operasi di atas menghasilkan daftar angka yang sama, sehingga kita dapat merekonstruksinya tanpa mengetahui N. Jadi saya tidak yakin apa alasan menambahkan N ke filter. Jika Anda tahu mengapa N harus disertakan, beri tahu saya!
Terima kasih sudah membaca!
Lihat Asli
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 Penjelasan Filter Blok Padat
Oleh Elle Mouton
Dalam artikel ini, saya menjelaskan secara singkat kebutuhan klien ringan dalam Bitcoin dan mengapa "filter blok kompak" melayani kebutuhan ini lebih baik daripada "filter Bloom". Saya kemudian menjelaskan secara mendalam cara kerja filter blok padat, dengan panduan langkah demi langkah membangun filter semacam itu di testnet.
Arti filter blok
Klien ringan bitcoin (perangkat lunak ringan bitcoin) adalah perangkat lunak yang tujuannya bukan untuk menyimpan blockchain bitcoin tetapi untuk mendukung dompet bitcoin. Artinya, ia harus dapat menyiarkan transaksi ke jaringan, tetapi yang terpenting, ia harus dapat menemukan transaksi baru dari rantai yang terkait dengan dompet ini. Ada dua jenis transaksi terkait seperti itu: mengirim dana ke dompet ini (membuat keluaran baru untuk alamat dompet ini), dan membelanjakan salah satu UTXO yang dikendalikan oleh dompet ini.
Apa yang salah dengan filter mekar?
Sebelum BIP 158, pendekatan yang paling umum untuk klien ringan adalah filter Bloom yang dijelaskan dalam BIP 371. Pola filter Bloom adalah Anda mengambil semua objek data yang Anda minati (mis., kunci publik skrip UTXO yang digunakan dan dibuat), hash mereka satu per satu beberapa kali, dan tambahkan setiap hasil ke In bitmap yang disebut "filter mekar". Filter ini mewakili apa yang Anda minati. Kemudian, Anda mengirim filter ini ke simpul Bitcoin yang Anda percayai dan meminta mereka mengirimkan semua yang cocok dengan filter ini.
Masalahnya adalah proses ini tidak terlalu pribadi, karena Anda masih membocorkan beberapa informasi ke node Bitcoin yang menerima filter tersebut. Mereka dapat mengetahui penawaran yang Anda minati dan penawaran yang sama sekali tidak Anda minati; mereka juga tidak dapat mengirimi Anda hal-hal yang cocok dengan filter. Jadi, ini tidak ideal untuk klien ringan. Tetapi pada saat yang sama, ini tidak ideal untuk node Bitcoin yang melayani klien ringan. Setiap kali Anda mengirim filter, mereka harus memuat blok yang relevan dari disk dan kemudian menentukan apakah ada transaksi yang cocok dengan filter Anda. Terus kirimkan filter palsu dan Anda dapat mengebomnya - pada dasarnya serangan DOS. Dibutuhkan sangat sedikit energi untuk membuat filter, tetapi membutuhkan banyak energi untuk menanggapi permintaan semacam itu.
Filter blok padat
OK, maka atribut yang kita butuhkan adalah:
Menggunakan filter blok padat, server (node penuh) akan membuat filter deterministik untuk setiap blok, termasuk semua objek data di blok ini. Filter ini hanya perlu dihitung sekali dan disimpan selamanya. Jika klien ringan meminta filter untuk blok tertentu, tidak ada asimetri di sini - karena server tidak perlu melakukan pekerjaan lebih dari klien yang meminta. Klien ringan juga dapat memilih beberapa sumber informasi untuk mengunduh blok lengkap untuk memastikan konsistensinya; selain itu, klien ringan selalu dapat mengunduh blok lengkap untuk memeriksa apakah filter yang disediakan oleh server sudah benar. Benar (cocok dengan blok yang relevan isi). Manfaat lain adalah lebih pribadi dengan cara ini. Klien ringan tidak perlu lagi mengirim sidik jari dari data yang diinginkannya ke server. Juga menjadi lebih sulit untuk menganalisis aktivitas klien ringan. Setelah klien ringan mendapatkan filter seperti itu dari server, ia memeriksa apakah filter berisi data yang diinginkan, dan jika demikian, klien ringan meminta blok lengkap. Juga harus ditunjukkan bahwa untuk melayani klien ringan dengan cara ini, node penuh perlu mempertahankan filter ini, dan klien ringan mungkin juga ingin mempertahankan beberapa filter, jadi pertahankan filter seringan mungkin Kuantitas sangat penting ( inilah mengapa ini disebut "filter blok padat").
sangat bagus! Sekarang kita masuk ke barang langka. Bagaimana filter seperti itu dibuat? Seperti apa bentuknya?
Apa kebutuhan kita?
Informasi dasar yang terkandung dalam filter adalah: kunci publik skrip dari setiap masukan dari setiap transaksi (yaitu, kunci publik skrip dari setiap UTXO yang digunakan), dan kunci publik skrip dari setiap keluaran dari setiap transaksi. Pada dasarnya seperti ini:
objek = {spk1, spk2, spk3, spk4, ..., spkN} // daftar kunci publik skrip N
Secara teknis, kita dapat berhenti di sini - daftar kunci publik skrip seperti itu juga dapat berfungsi sebagai filter kita. Ini adalah versi ringkas dari blok yang berisi informasi yang dibutuhkan oleh klien ringan. Dengan daftar seperti itu, klien ringan dapat memastikan 100% apakah ada transaksi yang menarik dalam suatu blok. Tetapi daftar seperti itu sangat besar. Oleh karena itu, langkah kita selanjutnya adalah membuat daftar ini sekompak mungkin. Di sinilah segalanya menjadi menarik.
Pertama, kita dapat mengonversi setiap objek menjadi angka dalam rentang tertentu, dan membuat setiap nomor objek terdistribusi secara merata dalam rentang ini. Misalkan kita memiliki 10 objek (N = 10), dan kemudian kita memiliki semacam fungsi yang mengubah setiap objek menjadi angka. Katakanlah kita memilih rentang [0, 10] (karena kita memiliki 10 objek). Sekarang, fungsi "hash to number" kita akan mengambil setiap objek sebagai input dan menghasilkan angka dengan ukuran masing-masing [0, 10]. Angka-angka didistribusikan secara merata di seluruh rentang ini. Artinya, setelah menyortir, kita akan mendapatkan grafik seperti ini (dalam kasus yang sangat, sangat ideal):
angka := {1,2,3,4,5,6,7,8,9,10}
Klien ringan mengunduh filter semacam itu, berharap untuk mengetahui apakah objek yang dicarinya cocok dengan filter tersebut. Mereka hanya mengambil objek yang mereka minati dan menjalankan fungsi "hash to number" yang sama untuk melihat apakah hasilnya ada di filter ini. Dimana masalahnya? Masalahnya adalah angka-angka di filter sudah mengambil setiap kemungkinan di ruang itu! Ini berarti bahwa objek apa pun yang menjadi perhatian klien ringan, hasil numerik yang dihasilkan harus cocok dengan filter ini. Dengan kata lain, filter ini memiliki "laju positif palsu" sebesar 1 (Catatan Penerjemah: "false positive" di sini berarti bahwa blok tersebut mungkin tidak berisi Hasil yang diperoleh filter adalah ya). Ini tidak begitu baik. Ini juga menunjukkan bahwa dalam proses mengompresi data untuk menghasilkan filter, kami kehilangan terlalu banyak informasi. Kami membutuhkan tingkat positif palsu yang lebih tinggi. Kemudian, misalkan kita ingin tingkat positif palsu menjadi 5. Kemudian, kita dapat membuat objek di blok tersebut sama rata dengan angka dalam rentang [0, 50]:
Kami sekarang memiliki daftar nomor terurut yang didistribusikan secara merata dalam interval [0, 50]. Kita tahu bahwa ada 10 nomor dalam daftar ini. Ini berarti, kita dapat menyimpulkan bahwa perbedaan antara dua angka yang berdekatan dalam daftar urutan angka ini kemungkinan besar adalah 5. Secara umum, jika kita memiliki N objek dan menginginkan laju positif palsu M, maka ukuran ruangnya harus N * M . Artinya, ukuran angka-angka ini harus antara 0 dan N * M, tetapi (setelah disortir) probabilitas interpolasi dari dua angka yang berdekatan yang diperiksa adalah M. Dan M harus disimpan lebih kecil dari angka di ruang N*M. Jadi, alih-alih menyimpan setiap angka, kita dapat menyimpan selisih antara dua angka yang berdekatan. Dalam contoh di atas, ini berarti bahwa alih-alih menyimpan [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] sebagai filter, kami menyimpan [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], yang darinya mudah untuk merekonstruksi daftar awal. Jika Anda memperkecil, menyimpan angka 50 jelas membutuhkan lebih banyak ruang daripada menyimpan angka 5. Tapi mengapa berhenti di situ? Mari kompres sedikit lagi!
Langkah selanjutnya adalah menggunakan "Golomb-Rice encoding". Metode pengkodean ini dapat dengan baik menyandikan daftar di mana setiap angka dalam tabel sangat dekat dengan angka tertentu. Dan daftar kami kebetulan hanya itu! Setiap angka dalam daftar kami kemungkinan besar mendekati 5 (atau mendekati tingkat positif palsu kami, yaitu M), jadi ambil hasil bagi setiap angka dengan M (bagi setiap angka dengan 5 dan abaikan sisanya), kemungkinan besar akan menjadi 0 (jika jumlahnya sedikit kurang dari 5) atau 1 (jika jumlahnya sedikit lebih besar dari 5). Mungkin juga hasil bagi adalah 2, 3, dst., tetapi probabilitasnya jauh lebih kecil. Besar! Jadi kita dapat mengambil keuntungan dari ini: kita akan menggunakan bit sesedikit mungkin untuk menyandikan hasil bagi yang lebih kecil, sambil menggunakan lebih banyak bitcoin untuk menyandikan hasil bagi yang lebih besar, tetapi kecil kemungkinannya. Kemudian, kita juga perlu menyandikan sisanya (karena kita ingin dapat merekonstruksi seluruh daftar dengan tepat), yang akan selalu berada dalam rentang [0, M - 1] (dalam hal ini [0, 4]). Untuk pembuat enkode, kami menggunakan pemetaan berikut:
0000 10000 10000 10000 10000 10000 10000 10000 10000 10000
Sebelum kita pindah ke kasus yang lebih realistis, mari kita lihat apakah kita bisa memulihkan daftar asli kita dengan filter ini.
Sekarang apa yang kita miliki adalah "0000100001000010000100001000010000100001000010000". Kami tahu kode Golomb-Rice, dan kami tahu bahwa M adalah 5 (karena ini akan menjadi pengetahuan umum, diketahui semua orang yang menggunakan konstruksi filter ini). Karena kita tahu bahwa M adalah 5, kita tahu bahwa akan ada 3 bit untuk menyandikan sisanya. Jadi, kita dapat mengonversi filter ini menjadi daftar larik "hasil bagi-sisa" berikut:
[(0, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), ( 1, 0), (1, 0)]
Mengetahui bahwa hasil bagi diperoleh dengan membaginya dengan M(5), kita dapat memulihkan:
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Selain itu, kami mengetahui bahwa daftar ini mewakili perbedaan antara dua angka yang berdekatan, sehingga kami dapat memulihkan daftar aslinya:
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Contoh yang lebih realistis
Kami sekarang akan mencoba membuat filter untuk blok testnet Bitcoin asli. Saya akan menggunakan blok 2101914. Mari kita lihat seperti apa filternya:
$ bitcoin-cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ bitcoin-cli getblockfilter 0000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { filter 833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a 5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade 12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", "tajuk": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }
Baiklah sayang, mari kita lihat bagaimana kita bisa membuat filter seperti itu dari blok.
Kode lengkap yang digunakan di sini dapat ditemukan di repositori github ini. Saya hanya akan menampilkan beberapa potongan pseudocode di sini. Inti dari kode ini adalah fungsi yang disebut constructFilter, yang dapat digunakan oleh klien bitcoin untuk memanggil bitcoind dan blok terkait. Fungsinya terlihat seperti ini:
func constructFilter(bc *bitcoind.Bitcoind, blokir bitcoind.Block) ([]byte, error) { // 1 mengumpulkan semua objek dari blok yang ingin kita tambahkan ke filter // 2 Ubah objek ini menjadi angka dan urutkan // 3 Dapatkan selisih antara dua angka yang berdekatan dalam daftar angka yang diurutkan // 4 Gunakan pengkodean Golomb-Rice untuk menyandikan perbedaan ini }
Jadi, langkah pertama adalah mengumpulkan semua objek dari blok yang ingin kita tambahkan ke filter. Mulai dari BIP, kita tahu bahwa objek ini menyertakan semua kunci publik skrip yang dihabiskan, dan setiap kunci publik skrip keluaran. BIP juga menetapkan beberapa aturan tambahan: kami melewatkan input ke transaksi coinbase (yang tidak masuk akal karena tidak memiliki input), dan kami meneruskan semua output OP_RETURN. Kami juga menghapus duplikat data. Jika ada dua kunci publik skrip yang identik, kami hanya menambahkannya sekali ke filter.
// daftar objek yang ingin kita tambahkan ke filter // Sertakan semua kunci publik skrip yang digunakan, dan setiap kunci publik skrip keluaran // Kami menggunakan "peta", yang menghapus kunci publik skrip duplikat objek := make(peta [string] struktur{}) // fasilitasi setiap transaksi di blok untuk i, tx := range block.Tx { // Tambahkan kunci publik skrip untuk setiap output // ke dalam daftar objek kita untuk _, txOut := range tx.Vout { PubKey := txOut.PubKey jika len(PubKey) == 0 { melanjutkan } // Lewati jika OP_RETURN (0x6a) adalah output jika spk [0] == 0x6a { melanjutkan } objek [skpStr] = struktur{}{} } // jangan tambahkan input transaksi coinbase jika saya == 0 { melanjutkan } // Untuk setiap input, dapatkan kunci publik skripnya untuk _, txIn := range tx.Vin { prevTx, err := bc.GetRawTransaction(txIn.Txid) jika salah != nihil { kembali nihil, err } PubKey := prevTx.Vout[txIn.Vout].PubKey jika len(PubKey) == 0 { melanjutkan } objek [spkStr] = struktur{}{} } }
Oke, sekarang semua objek sudah terkumpul. Sekarang, kita definisikan variabel N sebagai panjang grafik objek. Di sini, N adalah 85 .
Langkah selanjutnya adalah mengubah objek kita menjadi angka yang terdistribusi secara merata dalam suatu interval. Sekali lagi, kisarannya bergantung pada seberapa tinggi tingkat positif palsu yang Anda inginkan. BIP158 mendefinisikan konstanta M sebagai 784931. Ini berarti probabilitas positif palsu adalah 1 dalam 784931. Sama seperti yang kita lakukan sebelumnya, kita mengambil laju positif palsu M dikalikan N dan mendapatkan jangkauan distribusi semua bilangan. Kami mendefinisikan rentang ini sebagai F, yaitu, F = M * N . Di sini, F = 66719135. Saya tidak akan membahas detail fungsi yang memetakan objek ke angka (Anda dapat menemukan detailnya di repositori github yang ditautkan di atas). Yang perlu Anda ketahui adalah bahwa dibutuhkan sebagai input objek, konstanta F (yang menentukan cakupan objek yang perlu dipetakan), dan kunci (hash blok). Setelah kami memiliki semua angka, kami mengurutkan daftar dalam urutan menaik dan kemudian membuat daftar baru yang disebut perbedaan yang menyimpan perbedaan antara dua angka yang berdekatan dalam daftar angka yang diurutkan.
angka := make([]uint64, 0, N) // Ulangi semua objek dan ubah menjadi angka yang didistribusikan secara merata dalam rentang [0, F] // dan simpan nomor ini sebagai daftar nomor untuk o := rentang objek { // Menggunakan kunci yang diberikan, nomor maks (F) dan byte objek (o), // ubah objek menjadi angka antara 0 dan F. v := convertToNumber(b, F, kunci) angka = tambahkan(angka, v) } // mengurutkan daftar angka sort.Slice(angka, func(i, j int) bool { mengembalikan angka [i] < angka [j] }) // Ubah daftar angka menjadi daftar perbedaan perbedaan := make([]uint64, N) untuk i, num := rentang angka { jika saya == 0 { perbedaan [i] = bil melanjutkan } perbedaan [i] = bil - angka[i-1] }
Besar! Berikut adalah gambar yang menunjukkan daftar angka dan perbedaan.
Langkah terakhir adalah menyandikan daftar perbedaan menggunakan pengkodean Golomb-Rice. Ingat dari penjelasan sebelumnya bahwa kita perlu membagi setiap perbedaan dengan nilai yang paling mungkin dan kemudian menyandikan hasil bagi dan sisanya. Dalam contoh kami sebelumnya, saya mengatakan bahwa nilai yang paling mungkin adalah M, dan sisanya akan berada di antara [0, M]. Namun, BIP158 tidak melakukan ini, karena kami menemukan 2, yang sebenarnya bukan parameter yang meminimalkan ukuran filter akhir. Jadi daripada menggunakan M, kita mendefinisikan konstanta baru P dan menggunakan 2^P sebagai parameter Golomb-Rice. P didefinisikan sebagai 19 . Ini berarti kita membagi setiap perbedaan dengan 2^19 untuk mendapatkan hasil bagi dan sisa, dan sisanya dikodekan dalam biner dengan 19 bit.
filter := bstream.NewBStreamWriter(0) // Untuk setiap nilai dalam daftar selisih, dapatkan hasil bagi dan sisanya dengan membaginya dengan 2^P. untuk _, d := rentang perbedaan { q := matematika.Floor(float64(d)/math.Exp2(float64(P))) r := d - uint64(math.Exp2(float64(P))*q) // Pembuat kode untuk saya := 0; saya < int(q); saya++ { filter.WriteBit(benar) } filter.WriteBit(false) filter.WriteBits(r, P) }
Besar! Sekarang kita dapat mengeluarkan filter, mendapatkan:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0 c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa2 e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
Filter yang persis sama dengan yang kami dapatkan di bitcoind kecuali untuk dua byte pertama! Mengapa ada perbedaan dalam 2 byte pertama? Karena BIP mengatakan bahwa nilai N perlu dikodekan dalam format CompactSize dan muncul di depan filter agar dapat didekodekan oleh penerima. Ini dilakukan dengan:
fd := filter.Bytes() buffer bytes.Buffer buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) err = wire.WriteInt(&buffer, 0, uint64(N)) jika salah != nihil { kembali nihil, err } _, err = penyangga.Tulis(fd) jika salah != nihil { kembali nihil, err }
Jika sekarang kami mencetak filter lagi, kami akan menemukan bahwa itu persis sama dengan hasil bitcoind:
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0 b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12 fa 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
kesuksesan!
Namun, pemahaman pribadi saya adalah tidak perlu menambahkan N ke filter. Jika kamu mengetahui nilai P, maka kamu dapat mencari nilai N. Mari kita lihat apakah kita dapat mengembalikan daftar angka asli menggunakan output dari filter pertama:
b := bstream.NewBStreamReader(filter) ( angka []uint64 prevNum uint64 ) untuk { // Baca hasil bagi dari string byte. Angka 0 pertama yang ditemukan menunjukkan akhir dari hasil bagi // Sebelum menemukan 0, angka 1 mewakili hasil bagi q uint64 c, err := b.ReadBit() jika salah != nihil { kembali salah } untuk c { q++ c, err = b.ReadBit() jika kesalahan.Is(err, io.EOF) { merusak } lain jika err != nil { kembali salah } } // P bit berikutnya menyandikan sisanya r, err := b.ReadBits(P) jika kesalahan.Is(err, io.EOF) { merusak } lain jika err != nil { kembali salah } n := q*uint64(math.Exp2(float64(P))) + r num := n + prevNum angka = tambahkan(angka, bil) prevNum = bil } fmt.Println(angka)
Operasi di atas menghasilkan daftar angka yang sama, sehingga kita dapat merekonstruksinya tanpa mengetahui N. Jadi saya tidak yakin apa alasan menambahkan N ke filter. Jika Anda tahu mengapa N harus disertakan, beri tahu saya!
Terima kasih sudah membaca!