Trong bài viết này, tôi mô tả ngắn gọn nhu cầu về ứng dụng khách nhẹ trong Bitcoin và tại sao "bộ lọc khối nhỏ gọn" phục vụ nhu cầu này tốt hơn "bộ lọc Bloom". Sau đó, tôi sẽ giải thích sâu về cách thức hoạt động của bộ lọc khối dày đặc, với hướng dẫn từng bước về cách xây dựng bộ lọc như vậy trên mạng thử nghiệm.
Ý nghĩa của bộ lọc khối
Ứng dụng khách bitcoin light (phần mềm bitcoin light) là phần mềm có mục tiêu không phải là lưu trữ chuỗi khối bitcoin mà là hỗ trợ ví bitcoin. Điều này có nghĩa là nó cần có khả năng phát các giao dịch lên mạng, nhưng quan trọng nhất là nó phải có khả năng tìm các giao dịch mới từ chuỗi liên quan đến ví này. Có hai loại giao dịch liên quan như vậy: gửi tiền vào ví này (tạo đầu ra mới cho địa chỉ của ví này) và chi tiêu một trong các UTXO do ví này kiểm soát.
Có vấn đề gì với bộ lọc nở hoa?
Trước BIP 158, phương pháp phổ biến nhất cho các máy khách nhẹ là bộ lọc Bloom được mô tả trong BIP 371. Mẫu của bộ lọc Bloom là bạn lấy tất cả các đối tượng dữ liệu mà bạn quan tâm (ví dụ: khóa công khai tập lệnh của UTXO đã được sử dụng và tạo), băm từng cái một nhiều lần và thêm từng kết quả vào một bitmap được gọi là "bộ lọc nở hoa". Bộ lọc này đại diện cho những gì bạn quan tâm. Sau đó, bạn gửi bộ lọc này đến một nút Bitcoin mà bạn tin tưởng và yêu cầu họ gửi cho bạn mọi thứ phù hợp với bộ lọc này.
Vấn đề là quá trình này không riêng tư lắm, vì bạn vẫn rò rỉ một số thông tin cho nút Bitcoin chấp nhận bộ lọc. Họ có thể biết những giao dịch mà bạn quan tâm và những giao dịch mà bạn hoàn toàn không quan tâm; họ cũng không thể gửi cho bạn những thứ phù hợp với bộ lọc. Vì vậy, nó không lý tưởng cho các khách hàng nhẹ. Nhưng đồng thời, nó không lý tưởng cho các nút Bitcoin phục vụ các khách hàng nhẹ. Mỗi khi bạn gửi một bộ lọc, họ phải tải khối có liên quan từ đĩa và sau đó xác định xem có giao dịch nào khớp với bộ lọc của bạn hay không. Chỉ cần tiếp tục gửi các bộ lọc giả và bạn có thể đánh bom chúng - về cơ bản là một cuộc tấn công DOS. Cần rất ít năng lượng để tạo bộ lọc, nhưng lại tốn rất nhiều năng lượng để đáp ứng yêu cầu như vậy.
Bộ lọc khối dày đặc
OK, sau đó các thuộc tính chúng ta cần là:
Quyền riêng tư mạnh mẽ hơn
Máy khách-máy chủ tải bất đối xứng ít hơn. Nghĩa là, sẽ có ít công việc phải làm hơn ở phía máy chủ.
Ít tin tưởng. Các máy khách nhẹ không cần lo lắng về việc máy chủ không trả lại các giao dịch liên quan.
Sử dụng bộ lọc khối dày đặc, máy chủ (nút đầy đủ) sẽ xây dựng bộ lọc xác định cho từng khối, bao gồm tất cả các đối tượng dữ liệu trong khối này. Bộ lọc này chỉ cần được tính toán một lần và được lưu trữ mãi mãi. Nếu một máy khách nhẹ yêu cầu bộ lọc cho một khối nhất định, thì không có sự bất đối xứng ở đây - bởi vì máy chủ không cần thực hiện thêm bất kỳ công việc nào so với máy khách yêu cầu. Máy khách nhẹ cũng có thể chọn nhiều nguồn thông tin để tải xuống toàn bộ khối để đảm bảo rằng chúng nhất quán, hơn nữa, máy khách nhẹ luôn có thể tải xuống toàn bộ khối để kiểm tra xem bộ lọc do máy chủ cung cấp có đúng không (khớp với khối liên quan nội dung). Một lợi ích khác là nó riêng tư hơn theo cách này. Máy khách nhẹ không còn cần gửi dấu vân tay của dữ liệu mà nó muốn đến máy chủ. Việc phân tích hoạt động của một khách hàng nhẹ cũng trở nên khó khăn hơn. Sau khi ứng dụng khách nhẹ lấy bộ lọc như vậy từ máy chủ, nó sẽ kiểm tra xem bộ lọc có chứa dữ liệu mà nó muốn hay không và nếu có, ứng dụng khách nhẹ sẽ yêu cầu khối hoàn chỉnh. Cũng cần chỉ ra rằng để phục vụ các máy khách nhẹ theo cách này, các nút đầy đủ cần duy trì các bộ lọc này và các máy khách nhẹ cũng có thể muốn duy trì một vài bộ lọc, vì vậy hãy giữ cho các bộ lọc càng nhẹ càng tốt. Số lượng là rất quan trọng ( đây là lý do tại sao nó được gọi là "bộ lọc khối dày đặc").
rất tốt! Bây giờ chúng ta đang đi vào những thứ quý hiếm. Làm thế nào là một bộ lọc như vậy được tạo ra? Nó trông như thế nào?
Nhu cầu của chúng ta là gì?
Chúng tôi muốn đặt dấu vân tay của một đối tượng cụ thể trong bộ lọc, để khi khách hàng muốn kiểm tra xem một khối có thể chứa thứ gì đó liên quan đến mình hay không, họ có thể liệt kê tất cả các đối tượng và kiểm tra bộ lọc có khớp với các đối tượng này hay không.
Chúng tôi muốn bộ lọc này càng nhỏ càng tốt.
Về bản chất, thứ chúng ta muốn là thứ có thể tóm tắt một số thông tin của một khối với khối lượng nhỏ hơn nhiều so với khối.
Thông tin cơ bản có trong bộ lọc là: khóa công khai tập lệnh của từng đầu vào của từng giao dịch (nghĩa là khóa công khai tập lệnh của từng UTXO đã sử dụng) và khóa công khai tập lệnh của từng đầu ra của mỗi giao dịch. Về cơ bản nó là như thế này:
đối tượng = {spk1, spk2, spk3, spk4, ..., spkN} // danh sách N khóa công khai tập lệnh
Về mặt kỹ thuật, chúng ta có thể dừng ở đây - chỉ một danh sách các khóa công khai của tập lệnh cũng có thể đóng vai trò là bộ lọc của chúng ta. Đây là phiên bản rút gọn của một khối chứa thông tin cần thiết cho các ứng dụng khách nhẹ. Với danh sách như vậy, một khách hàng nhẹ có thể xác nhận 100% liệu có giao dịch quan tâm trong một khối hay không. Nhưng một danh sách như vậy là rất lớn. Do đó, các bước tiếp theo của chúng tôi là làm cho danh sách này càng gọn càng tốt. Đây là nơi mà mọi thứ trở nên thú vị.
Đầu tiên, chúng ta có thể chuyển đổi từng đối tượng thành một số trong một phạm vi nhất định và làm cho mỗi số đối tượng được phân bổ đều trong phạm vi này. Giả sử chúng ta có 10 đối tượng (N = 10), và sau đó chúng ta có một số loại hàm chuyển đổi từng đối tượng thành một số. Giả sử chúng ta chọn phạm vi [0, 10] (vì chúng ta có 10 đối tượng). Bây giờ, hàm "băm thành số" của chúng tôi sẽ lấy từng đối tượng làm đầu vào và tạo ra một số có kích thước [0, 10] tương ứng. Các con số được phân bổ đều trên phạm vi này. Điều này có nghĩa là, sau khi sắp xếp, chúng ta sẽ có một biểu đồ như thế này (trong một trường hợp rất, rất lý tưởng):
Trước hết, điều này thật tuyệt vì chúng tôi đã giảm đáng kể kích thước dấu vân tay của từng đối tượng. Bây giờ mỗi đối tượng chỉ là một con số. Vì vậy, bộ lọc mới của chúng tôi trông như thế này:
số := {1,2,3,4,5,6,7,8,9,10}
Một ứng dụng khách nhẹ tải xuống một bộ lọc như vậy, với hy vọng biết liệu một đối tượng mà nó đang tìm kiếm có khớp với bộ lọc hay không. Họ chỉ lấy đối tượng mà họ quan tâm và chạy cùng chức năng "băm thành số" để xem liệu kết quả có nằm trong bộ lọc này hay không. Vấn đề ở đâu? Vấn đề là các số trong bộ lọc đã chiếm mọi khả năng trong không gian đó! Điều này có nghĩa là bất kể đối tượng nào mà light client quan tâm, kết quả số thu được phải khớp với bộ lọc này. Nói cách khác, bộ lọc này có "tỷ lệ dương tính giả" là 1 (Ghi chú của người dịch: "Dương tính giả" ở đây có nghĩa là khối có thể không chứa. Kết quả mà bộ lọc thu được là có). Điều này không tốt lắm. Điều đó cũng cho thấy trong quá trình nén dữ liệu để tạo bộ lọc, chúng ta đã làm mất quá nhiều thông tin. Chúng tôi cần một tỷ lệ dương tính giả cao hơn. Sau đó, giả sử chúng ta muốn tỷ lệ dương tính giả là 5. Sau đó, chúng ta có thể làm cho các đối tượng trong khối khớp đồng đều với các số trong phạm vi [0, 50]:
Nó trông tốt hơn theo cách đó. Nếu tôi là khách hàng và tải xuống bộ lọc như vậy, tôi cần kiểm tra xem đối tượng tôi quan tâm có nằm trong khối tương ứng thông qua bộ lọc hay không và xác suất bộ lọc nói có nhưng không có trong khối (dương tính giả) sẽ giảm xuống còn 1/5. Tuyệt, bây giờ chúng ta đang ánh xạ 10 đối tượng thành các số từ 0 đến 50. Danh sách số mới này là bộ lọc của chúng tôi. Một lần nữa, chúng ta có thể dừng bất cứ lúc nào, tuy nhiên, chúng ta có thể nén chúng hơn nữa!
Bây giờ chúng ta có một danh sách sắp xếp các số phân bố đều trong khoảng [0, 50]. Chúng tôi biết rằng có 10 số trong danh sách này. Điều này có nghĩa là, chúng ta có thể suy ra rằng chênh lệch giữa hai số liền kề trong danh sách các số được sắp xếp này rất có thể là 5. Nói chung, nếu chúng ta có N đối tượng và muốn tỷ lệ dương tính giả là M, thì kích thước của không gian phải là N * M . Nghĩa là, kích thước của những số này phải nằm trong khoảng từ 0 đến N * M, nhưng (sau khi sắp xếp), xác suất nội suy của hai số liền kề được kiểm tra là M. Và M phải được lưu trữ nhỏ hơn số trong không gian N * M. Vì vậy, thay vì lưu trữ từng số, chúng ta có thể lưu trữ sự khác biệt giữa hai số liền kề. Trong ví dụ trên, điều này có nghĩa là thay vì lưu trữ [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] làm bộ lọc, chúng tôi lưu trữ [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], từ đó việc xây dựng lại danh sách ban đầu là không cần thiết. Nếu bạn thu nhỏ lại, lưu trữ số 50 rõ ràng sẽ chiếm nhiều dung lượng hơn so với lưu trữ số 5. Nhưng tại sao lại dừng lại ở đó? Hãy nén lại một chút nữa!
Bước tiếp theo là sử dụng "mã hóa Golomb-Rice". Phương pháp mã hóa này có thể mã hóa tốt một danh sách trong đó mỗi số trong bảng rất gần với một số nhất định. Và danh sách của chúng tôi tình cờ chỉ có vậy! Mỗi số trong danh sách của chúng tôi có khả năng gần bằng 5 (hoặc gần với tỷ lệ dương tính giả của chúng tôi, là M), vì vậy hãy lấy thương của mỗi số cho M (chia mỗi số cho 5 và bỏ qua phần còn lại), rất có thể sẽ là 0 (nếu số nhỏ hơn 5 một chút) hoặc 1 (nếu số lớn hơn 5 một chút). Cũng có thể thương là 2, 3, v.v., nhưng xác suất nhỏ hơn nhiều. Tuyệt! Vì vậy, chúng tôi có thể tận dụng điều này: chúng tôi sẽ sử dụng càng ít bit càng tốt để mã hóa các thương số nhỏ hơn, trong khi sử dụng nhiều bitcoin hơn để mã hóa các thương số lớn hơn nhưng ít có khả năng xảy ra hơn. Sau đó, chúng tôi cũng cần mã hóa phần còn lại (vì chúng tôi muốn có thể xây dựng lại chính xác toàn bộ danh sách), phần còn lại sẽ luôn nằm trong phạm vi [0, M - 1] (trong trường hợp này là [0, 4]). Đối với bộ mã hóa, chúng tôi sử dụng các ánh xạ sau:
Ánh xạ trên rất dễ hiểu: số chữ số 1 biểu thị thương số chúng ta muốn mã hóa và 0 biểu thị kết thúc mã hóa thương số. Vì vậy, đối với mỗi số trong danh sách của chúng tôi, chúng tôi có thể sử dụng bảng trên để mã hóa thương số, sau đó chuyển đổi phần còn lại thành nhị phân bằng cách sử dụng bittruck có thể biểu thị giá trị tối đa là M-1. Ở đây phần còn lại là 4 và chỉ cần 3 bit. Đây là bảng hiển thị các phần còn lại có thể có và mã hóa của chúng cho ví dụ của chúng tôi:
Vì vậy, lý tưởng nhất là danh sách [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] của chúng ta có thể được mã hóa thành:
Trước khi chúng tôi chuyển sang trường hợp thực tế hơn, hãy xem liệu chúng tôi có thể khôi phục danh sách ban đầu của mình bằng bộ lọc này hay không.
Bây giờ những gì chúng ta có là "0000100001000010000100001000010000100001000010000". Chúng tôi biết mã Golomb-Rice và chúng tôi biết rằng M là 5 (vì đây sẽ là kiến thức công khai, được mọi người sử dụng cấu trúc bộ lọc này biết đến). Vì chúng tôi biết rằng M là 5, chúng tôi biết rằng sẽ có 3 bit để mã hóa phần còn lại. Vì vậy, chúng ta có thể chuyển đổi bộ lọc này thành danh sách mảng "số dư thương số" sau:
Biết rằng thương số thu được bằng cách chia cho M(5), chúng ta có thể phục hồi:
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Ngoài ra, chúng tôi biết rằng danh sách này đại diện cho sự khác biệt giữa hai số liền kề, vì vậy chúng tôi có thể khôi phục danh sách ban đầu:
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Một ví dụ thực tế hơn
Bây giờ chúng ta sẽ cố gắng xây dựng một bộ lọc cho một khối testnet Bitcoin thực sự. Tôi sẽ sử dụng khối 2101914. Hãy xem bộ lọc của nó trông như thế nào:
Được rồi, hãy xem cách chúng ta có thể xây dựng một bộ lọc như vậy từ các khối.
Mã đầy đủ được sử dụng ở đây có thể được tìm thấy trong kho lưu trữ github này. Tôi sẽ chỉ hiển thị một số đoạn mã giả ở đây. Cốt lõi của mã này là một chức năng được gọi là constructorFilter, có thể được sử dụng bởi các máy khách bitcoin để gọi bitcoind và các khối tương ứng. Chức năng trông như thế này:
func buildFilter(bc *bitcoind.Bitcoind, chặn bitcoind.Block) ([]byte, lỗi) {
// 1 thu thập tất cả các đối tượng từ khối mà chúng tôi muốn thêm vào bộ lọc
// 2 Chuyển các đối tượng này thành số và sắp xếp chúng
// 3 Lấy hiệu giữa 2 số liền kề trong danh sách số đã sắp xếp
// 4 Sử dụng mã hóa Golomb-Rice để mã hóa những khác biệt này
}
Vì vậy, bước đầu tiên là thu thập tất cả các đối tượng từ khối mà chúng tôi muốn thêm vào bộ lọc. Bắt đầu từ BIP, chúng tôi biết rằng các đối tượng này bao gồm tất cả các khóa công khai của tập lệnh đã sử dụng và mọi khóa công khai của tập lệnh đầu ra. BIP cũng đặt ra một số quy tắc bổ sung: chúng tôi bỏ qua các đầu vào cho giao dịch coinbase (điều này không hợp lý vì nó không có đầu vào) và chúng tôi chuyển tất cả các đầu ra OP_RETURN. Chúng tôi cũng loại bỏ dữ liệu trùng lặp. Nếu có hai khóa công khai tập lệnh giống hệt nhau, chúng tôi chỉ thêm một lần vào bộ lọc.
// danh sách các đối tượng chúng tôi muốn thêm vào bộ lọc
// Bao gồm tất cả các khóa công khai của tập lệnh đã sử dụng và mọi khóa công khai của tập lệnh đầu ra
// Chúng tôi sử dụng "bản đồ", loại bỏ các khóa công khai của tập lệnh trùng lặp
đối tượng := make(map [string] cấu trúc{})
// tạo điều kiện thuận lợi cho mọi giao dịch trong khối
for i, tx := range block.Tx {
// Thêm khóa công khai tập lệnh cho mỗi đầu ra
// vào danh sách các đối tượng của chúng tôi
cho _, txOut := phạm vi tx.Vout {
PubKey := txOut.PubKey
nếu len(PubKey) == 0 {
Tiếp tục
}
// Bỏ qua nếu xuất ra OP_RETURN (0x6a)
nếu spk [0] == 0x6a {
Tiếp tục
}
các đối tượng [skpStr] = cấu trúc{}{}
}
// không thêm đầu vào của giao dịch coinbase
nếu tôi == 0 {
Tiếp tục
}
// Đối với mỗi đầu vào, lấy khóa công khai tập lệnh của nó
cho _, txIn := phạm vi tx.Vin {
prevTx, err := bc.GetRawTransaction(txIn.Txid)
nếu sai != nil {
trả về con số không, lỗi
}
PubKey := prevTx.Vout[txIn.Vout].PubKey
nếu len(PubKey) == 0 {
Tiếp tục
}
các đối tượng [spkStr] = cấu trúc{}{}
}
}
OK, bây giờ tất cả các đối tượng được thu thập. Bây giờ, chúng ta định nghĩa biến N là độ dài của đồ thị đối tượng. Ở đây, N là 85 .
Bước tiếp theo là chuyển đổi đối tượng của chúng ta thành các số được phân bố đều trong một khoảng thời gian. Một lần nữa, phạm vi phụ thuộc vào tỷ lệ dương tính giả mà bạn muốn cao bao nhiêu. BIP158 định nghĩa hằng số M là 784931. Điều này có nghĩa là xác suất dương tính giả là 1 trên 784931. Giống như chúng tôi đã làm trước đây, chúng tôi lấy tỷ lệ dương tính giả M nhân với N và nhận được phạm vi phân phối của tất cả các số. Chúng tôi xác định phạm vi này là F, nghĩa là F = M * N . Ở đây, F = 66719135. Tôi sẽ không đi vào chi tiết các chức năng ánh xạ đối tượng thành số (bạn có thể tìm thấy chi tiết trong kho lưu trữ github được liên kết ở trên). Tất cả những gì bạn cần biết là nó lấy đầu vào là đối tượng, hằng số F (xác định phạm vi mà đối tượng cần được ánh xạ tới) và một khóa (hàm băm khối). Khi chúng tôi có tất cả các số, chúng tôi sắp xếp danh sách theo thứ tự tăng dần và sau đó tạo một danh sách mới có tên là chênh lệch chứa chênh lệch giữa hai số liền kề trong danh sách số được sắp xếp.
số := make([]uint64, 0, N)
// Lặp qua tất cả các đối tượng và chuyển đổi chúng thành các số phân bố đều trong phạm vi [0, F]
// và lưu những số này dưới dạng danh sách số
cho o := phạm vi đối tượng {
// Sử dụng khóa đã cho, số tối đa (F) và byte đối tượng (o),
// chuyển đổi đối tượng thành một số từ 0 đến F.
v := convertToNumber(b, F, phím)
số = nối thêm (số, v)
}
// sắp xếp danh sách số
sort.Slice(số, func(i, j int) bool { trả lại số [i] < số [j] })
//Chuyển danh sách số thành danh sách chênh lệch
khác biệt := make([]uint64, N)
for i, num := dãy số {
nếu tôi == 0 {
khác biệt [i] = số
Tiếp tục
}
khác biệt [i] = num - số[i-1]
}
Tuyệt! Đây là một hình ảnh hiển thị một danh sách các số và sự khác biệt.
Khi bạn thu nhỏ, 85 số được phân bố đều khắp không gian! Vì vậy, các giá trị trong danh sách khác biệt cũng rất nhỏ.
Bước cuối cùng là mã hóa danh sách các khác biệt bằng cách sử dụng mã hóa Golomb-Rice. Nhớ lại lời giải thích trước đó rằng chúng ta cần chia mỗi chênh lệch cho giá trị có khả năng xảy ra nhất, sau đó mã hóa thương và số dư. Trong ví dụ trước của chúng tôi, tôi đã nói rằng giá trị có khả năng nhất là M và phần còn lại sẽ nằm trong khoảng [0, M]. Tuy nhiên, BIP158 không làm điều này, vì chúng tôi đã tìm thấy 2, đây không phải là tham số thực sự giảm thiểu kích thước bộ lọc cuối cùng. Vì vậy, thay vì sử dụng M, chúng tôi xác định một hằng số P mới và sử dụng 2^P làm tham số Golomb-Rice. P được định nghĩa là 19 . Điều này có nghĩa là chúng tôi chia mỗi chênh lệch cho 2^19 để lấy thương và phần dư, phần còn lại được mã hóa ở dạng nhị phân với 19 bit.
bộ lọc := bstream.NewBStreamWriter(0)
// Đối với mỗi giá trị trong danh sách chênh lệch, lấy thương và số dư bằng cách chia cho 2^P.
cho _, d := chênh lệch phạm vi {
q := math.Floor(float64(d)/math.Exp2(float64(P)))
r := d - uint64(math.Exp2(float64(P))*q)
// Mã hoá
cho tôi := 0; i < int(q); i++ {
bộ lọc.WriteBit (đúng)
}
bộ lọc.WriteBit (sai)
bộ lọc.WriteBits(r, P)
}
Tuyệt! Bây giờ chúng ta có thể xuất bộ lọc, nhận được:
Chính xác là bộ lọc giống như chúng ta có trong bitcoin ngoại trừ hai byte đầu tiên! Tại sao có sự khác biệt trong 2 byte đầu tiên? Bởi vì BIP nói rằng giá trị của N cần được mã hóa ở định dạng CompactSize và xuất hiện trước bộ lọc để bộ thu có thể giải mã được. Điều này được thực hiện bởi:
fd := filter.Bytes()
bộ đệm byte.Buffer
bộ đệm.Grow(wire.IntSerializeSize(uint64(N)) + len(fd))
err = wire.WriteInt(&buffer, 0, uint64(N))
nếu sai != nil {
trả về con số không, lỗi
}
_, err = bộ đệm.Write(fd)
nếu sai != nil {
trả về con số không, lỗi
}
Nếu bây giờ chúng ta in lại bộ lọc, chúng ta sẽ thấy rằng nó hoàn toàn giống với kết quả của bitcoind:
Tuy nhiên, hiểu biết cá nhân của tôi là không cần thêm N vào bộ lọc. Nếu bạn biết giá trị của P, thì bạn có thể tìm được giá trị của N. Hãy xem liệu chúng ta có thể khôi phục danh sách số ban đầu bằng cách sử dụng đầu ra của bộ lọc đầu tiên hay không:
b := bstream.NewBStreamReader(bộ lọc)
(
số []uint64
trướcNum uint64
)
vì {
// Đọc thương từ chuỗi byte. Số 0 đầu tiên gặp phải cho biết kết thúc thương số
// Trước khi gặp 0, số 1 đại diện cho thương số
q uint64
c, lỗi := b.ReadBit()
nếu sai != nil {
trả lại lỗi
}
cho c{
q++
c, lỗi = b.ReadBit()
nếu lỗi.Is(err, io.EOF) {
phá vỡ
} other if err != nil {
trả lại lỗi
}
}
// P bit tiếp theo mã hóa phần còn lại
r, err := b.ReadBits(P)
nếu lỗi.Is(err, io.EOF) {
phá vỡ
} other if err != nil {
trả lại lỗi
}
n := q*uint64(math.Exp2(float64(P))) + r
num := n + prevNum
số = nối thêm (số, số)
prevNum = số
}
fmt.Println(số)
Hoạt động trên tạo ra cùng một danh sách các số, vì vậy chúng tôi có thể xây dựng lại nó mà không cần biết N. Vì vậy, tôi không chắc lý do căn bản để thêm N vào bộ lọc là gì. Nếu bạn biết tại sao N phải được đưa vào, vui lòng cho tôi biết!
Cảm ơn vì đã đọc!
Xem bản gốc
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.
Giải thích bộ lọc khối dày đặc BIP 158
Bởi Elle Mouton
Trong bài viết này, tôi mô tả ngắn gọn nhu cầu về ứng dụng khách nhẹ trong Bitcoin và tại sao "bộ lọc khối nhỏ gọn" phục vụ nhu cầu này tốt hơn "bộ lọc Bloom". Sau đó, tôi sẽ giải thích sâu về cách thức hoạt động của bộ lọc khối dày đặc, với hướng dẫn từng bước về cách xây dựng bộ lọc như vậy trên mạng thử nghiệm.
Ý nghĩa của bộ lọc khối
Ứng dụng khách bitcoin light (phần mềm bitcoin light) là phần mềm có mục tiêu không phải là lưu trữ chuỗi khối bitcoin mà là hỗ trợ ví bitcoin. Điều này có nghĩa là nó cần có khả năng phát các giao dịch lên mạng, nhưng quan trọng nhất là nó phải có khả năng tìm các giao dịch mới từ chuỗi liên quan đến ví này. Có hai loại giao dịch liên quan như vậy: gửi tiền vào ví này (tạo đầu ra mới cho địa chỉ của ví này) và chi tiêu một trong các UTXO do ví này kiểm soát.
Có vấn đề gì với bộ lọc nở hoa?
Trước BIP 158, phương pháp phổ biến nhất cho các máy khách nhẹ là bộ lọc Bloom được mô tả trong BIP 371. Mẫu của bộ lọc Bloom là bạn lấy tất cả các đối tượng dữ liệu mà bạn quan tâm (ví dụ: khóa công khai tập lệnh của UTXO đã được sử dụng và tạo), băm từng cái một nhiều lần và thêm từng kết quả vào một bitmap được gọi là "bộ lọc nở hoa". Bộ lọc này đại diện cho những gì bạn quan tâm. Sau đó, bạn gửi bộ lọc này đến một nút Bitcoin mà bạn tin tưởng và yêu cầu họ gửi cho bạn mọi thứ phù hợp với bộ lọc này.
Vấn đề là quá trình này không riêng tư lắm, vì bạn vẫn rò rỉ một số thông tin cho nút Bitcoin chấp nhận bộ lọc. Họ có thể biết những giao dịch mà bạn quan tâm và những giao dịch mà bạn hoàn toàn không quan tâm; họ cũng không thể gửi cho bạn những thứ phù hợp với bộ lọc. Vì vậy, nó không lý tưởng cho các khách hàng nhẹ. Nhưng đồng thời, nó không lý tưởng cho các nút Bitcoin phục vụ các khách hàng nhẹ. Mỗi khi bạn gửi một bộ lọc, họ phải tải khối có liên quan từ đĩa và sau đó xác định xem có giao dịch nào khớp với bộ lọc của bạn hay không. Chỉ cần tiếp tục gửi các bộ lọc giả và bạn có thể đánh bom chúng - về cơ bản là một cuộc tấn công DOS. Cần rất ít năng lượng để tạo bộ lọc, nhưng lại tốn rất nhiều năng lượng để đáp ứng yêu cầu như vậy.
Bộ lọc khối dày đặc
OK, sau đó các thuộc tính chúng ta cần là:
Sử dụng bộ lọc khối dày đặc, máy chủ (nút đầy đủ) sẽ xây dựng bộ lọc xác định cho từng khối, bao gồm tất cả các đối tượng dữ liệu trong khối này. Bộ lọc này chỉ cần được tính toán một lần và được lưu trữ mãi mãi. Nếu một máy khách nhẹ yêu cầu bộ lọc cho một khối nhất định, thì không có sự bất đối xứng ở đây - bởi vì máy chủ không cần thực hiện thêm bất kỳ công việc nào so với máy khách yêu cầu. Máy khách nhẹ cũng có thể chọn nhiều nguồn thông tin để tải xuống toàn bộ khối để đảm bảo rằng chúng nhất quán, hơn nữa, máy khách nhẹ luôn có thể tải xuống toàn bộ khối để kiểm tra xem bộ lọc do máy chủ cung cấp có đúng không (khớp với khối liên quan nội dung). Một lợi ích khác là nó riêng tư hơn theo cách này. Máy khách nhẹ không còn cần gửi dấu vân tay của dữ liệu mà nó muốn đến máy chủ. Việc phân tích hoạt động của một khách hàng nhẹ cũng trở nên khó khăn hơn. Sau khi ứng dụng khách nhẹ lấy bộ lọc như vậy từ máy chủ, nó sẽ kiểm tra xem bộ lọc có chứa dữ liệu mà nó muốn hay không và nếu có, ứng dụng khách nhẹ sẽ yêu cầu khối hoàn chỉnh. Cũng cần chỉ ra rằng để phục vụ các máy khách nhẹ theo cách này, các nút đầy đủ cần duy trì các bộ lọc này và các máy khách nhẹ cũng có thể muốn duy trì một vài bộ lọc, vì vậy hãy giữ cho các bộ lọc càng nhẹ càng tốt. Số lượng là rất quan trọng ( đây là lý do tại sao nó được gọi là "bộ lọc khối dày đặc").
rất tốt! Bây giờ chúng ta đang đi vào những thứ quý hiếm. Làm thế nào là một bộ lọc như vậy được tạo ra? Nó trông như thế nào?
Nhu cầu của chúng ta là gì?
Thông tin cơ bản có trong bộ lọc là: khóa công khai tập lệnh của từng đầu vào của từng giao dịch (nghĩa là khóa công khai tập lệnh của từng UTXO đã sử dụng) và khóa công khai tập lệnh của từng đầu ra của mỗi giao dịch. Về cơ bản nó là như thế này:
đối tượng = {spk1, spk2, spk3, spk4, ..., spkN} // danh sách N khóa công khai tập lệnh
Về mặt kỹ thuật, chúng ta có thể dừng ở đây - chỉ một danh sách các khóa công khai của tập lệnh cũng có thể đóng vai trò là bộ lọc của chúng ta. Đây là phiên bản rút gọn của một khối chứa thông tin cần thiết cho các ứng dụng khách nhẹ. Với danh sách như vậy, một khách hàng nhẹ có thể xác nhận 100% liệu có giao dịch quan tâm trong một khối hay không. Nhưng một danh sách như vậy là rất lớn. Do đó, các bước tiếp theo của chúng tôi là làm cho danh sách này càng gọn càng tốt. Đây là nơi mà mọi thứ trở nên thú vị.
Đầu tiên, chúng ta có thể chuyển đổi từng đối tượng thành một số trong một phạm vi nhất định và làm cho mỗi số đối tượng được phân bổ đều trong phạm vi này. Giả sử chúng ta có 10 đối tượng (N = 10), và sau đó chúng ta có một số loại hàm chuyển đổi từng đối tượng thành một số. Giả sử chúng ta chọn phạm vi [0, 10] (vì chúng ta có 10 đối tượng). Bây giờ, hàm "băm thành số" của chúng tôi sẽ lấy từng đối tượng làm đầu vào và tạo ra một số có kích thước [0, 10] tương ứng. Các con số được phân bổ đều trên phạm vi này. Điều này có nghĩa là, sau khi sắp xếp, chúng ta sẽ có một biểu đồ như thế này (trong một trường hợp rất, rất lý tưởng):
số := {1,2,3,4,5,6,7,8,9,10}
Một ứng dụng khách nhẹ tải xuống một bộ lọc như vậy, với hy vọng biết liệu một đối tượng mà nó đang tìm kiếm có khớp với bộ lọc hay không. Họ chỉ lấy đối tượng mà họ quan tâm và chạy cùng chức năng "băm thành số" để xem liệu kết quả có nằm trong bộ lọc này hay không. Vấn đề ở đâu? Vấn đề là các số trong bộ lọc đã chiếm mọi khả năng trong không gian đó! Điều này có nghĩa là bất kể đối tượng nào mà light client quan tâm, kết quả số thu được phải khớp với bộ lọc này. Nói cách khác, bộ lọc này có "tỷ lệ dương tính giả" là 1 (Ghi chú của người dịch: "Dương tính giả" ở đây có nghĩa là khối có thể không chứa. Kết quả mà bộ lọc thu được là có). Điều này không tốt lắm. Điều đó cũng cho thấy trong quá trình nén dữ liệu để tạo bộ lọc, chúng ta đã làm mất quá nhiều thông tin. Chúng tôi cần một tỷ lệ dương tính giả cao hơn. Sau đó, giả sử chúng ta muốn tỷ lệ dương tính giả là 5. Sau đó, chúng ta có thể làm cho các đối tượng trong khối khớp đồng đều với các số trong phạm vi [0, 50]:
Bây giờ chúng ta có một danh sách sắp xếp các số phân bố đều trong khoảng [0, 50]. Chúng tôi biết rằng có 10 số trong danh sách này. Điều này có nghĩa là, chúng ta có thể suy ra rằng chênh lệch giữa hai số liền kề trong danh sách các số được sắp xếp này rất có thể là 5. Nói chung, nếu chúng ta có N đối tượng và muốn tỷ lệ dương tính giả là M, thì kích thước của không gian phải là N * M . Nghĩa là, kích thước của những số này phải nằm trong khoảng từ 0 đến N * M, nhưng (sau khi sắp xếp), xác suất nội suy của hai số liền kề được kiểm tra là M. Và M phải được lưu trữ nhỏ hơn số trong không gian N * M. Vì vậy, thay vì lưu trữ từng số, chúng ta có thể lưu trữ sự khác biệt giữa hai số liền kề. Trong ví dụ trên, điều này có nghĩa là thay vì lưu trữ [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] làm bộ lọc, chúng tôi lưu trữ [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], từ đó việc xây dựng lại danh sách ban đầu là không cần thiết. Nếu bạn thu nhỏ lại, lưu trữ số 50 rõ ràng sẽ chiếm nhiều dung lượng hơn so với lưu trữ số 5. Nhưng tại sao lại dừng lại ở đó? Hãy nén lại một chút nữa!
Bước tiếp theo là sử dụng "mã hóa Golomb-Rice". Phương pháp mã hóa này có thể mã hóa tốt một danh sách trong đó mỗi số trong bảng rất gần với một số nhất định. Và danh sách của chúng tôi tình cờ chỉ có vậy! Mỗi số trong danh sách của chúng tôi có khả năng gần bằng 5 (hoặc gần với tỷ lệ dương tính giả của chúng tôi, là M), vì vậy hãy lấy thương của mỗi số cho M (chia mỗi số cho 5 và bỏ qua phần còn lại), rất có thể sẽ là 0 (nếu số nhỏ hơn 5 một chút) hoặc 1 (nếu số lớn hơn 5 một chút). Cũng có thể thương là 2, 3, v.v., nhưng xác suất nhỏ hơn nhiều. Tuyệt! Vì vậy, chúng tôi có thể tận dụng điều này: chúng tôi sẽ sử dụng càng ít bit càng tốt để mã hóa các thương số nhỏ hơn, trong khi sử dụng nhiều bitcoin hơn để mã hóa các thương số lớn hơn nhưng ít có khả năng xảy ra hơn. Sau đó, chúng tôi cũng cần mã hóa phần còn lại (vì chúng tôi muốn có thể xây dựng lại chính xác toàn bộ danh sách), phần còn lại sẽ luôn nằm trong phạm vi [0, M - 1] (trong trường hợp này là [0, 4]). Đối với bộ mã hóa, chúng tôi sử dụng các ánh xạ sau:
0000 10000 10000 10000 10000 10000 10000 10000 10000 10000
Trước khi chúng tôi chuyển sang trường hợp thực tế hơn, hãy xem liệu chúng tôi có thể khôi phục danh sách ban đầu của mình bằng bộ lọc này hay không.
Bây giờ những gì chúng ta có là "0000100001000010000100001000010000100001000010000". Chúng tôi biết mã Golomb-Rice và chúng tôi biết rằng M là 5 (vì đây sẽ là kiến thức công khai, được mọi người sử dụng cấu trúc bộ lọc này biết đến). Vì chúng tôi biết rằng M là 5, chúng tôi biết rằng sẽ có 3 bit để mã hóa phần còn lại. Vì vậy, chúng ta có thể chuyển đổi bộ lọc này thành danh sách mảng "số dư thương số" sau:
[(0, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), ( 1, 0), (1, 0)]
Biết rằng thương số thu được bằng cách chia cho M(5), chúng ta có thể phục hồi:
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Ngoài ra, chúng tôi biết rằng danh sách này đại diện cho sự khác biệt giữa hai số liền kề, vì vậy chúng tôi có thể khôi phục danh sách ban đầu:
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Một ví dụ thực tế hơn
Bây giờ chúng ta sẽ cố gắng xây dựng một bộ lọc cho một khối testnet Bitcoin thực sự. Tôi sẽ sử dụng khối 2101914. Hãy xem bộ lọc của nó trông như thế nào:
$ bitcoin-cli getblockhash 2101914 0000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ bitcoin-cli getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { "bộ lọc": "5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df574378640 23833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a6 5a5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34 b56ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", "tiêu đề": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }
Được rồi, hãy xem cách chúng ta có thể xây dựng một bộ lọc như vậy từ các khối.
Mã đầy đủ được sử dụng ở đây có thể được tìm thấy trong kho lưu trữ github này. Tôi sẽ chỉ hiển thị một số đoạn mã giả ở đây. Cốt lõi của mã này là một chức năng được gọi là constructorFilter, có thể được sử dụng bởi các máy khách bitcoin để gọi bitcoind và các khối tương ứng. Chức năng trông như thế này:
func buildFilter(bc *bitcoind.Bitcoind, chặn bitcoind.Block) ([]byte, lỗi) { // 1 thu thập tất cả các đối tượng từ khối mà chúng tôi muốn thêm vào bộ lọc // 2 Chuyển các đối tượng này thành số và sắp xếp chúng // 3 Lấy hiệu giữa 2 số liền kề trong danh sách số đã sắp xếp // 4 Sử dụng mã hóa Golomb-Rice để mã hóa những khác biệt này }
Vì vậy, bước đầu tiên là thu thập tất cả các đối tượng từ khối mà chúng tôi muốn thêm vào bộ lọc. Bắt đầu từ BIP, chúng tôi biết rằng các đối tượng này bao gồm tất cả các khóa công khai của tập lệnh đã sử dụng và mọi khóa công khai của tập lệnh đầu ra. BIP cũng đặt ra một số quy tắc bổ sung: chúng tôi bỏ qua các đầu vào cho giao dịch coinbase (điều này không hợp lý vì nó không có đầu vào) và chúng tôi chuyển tất cả các đầu ra OP_RETURN. Chúng tôi cũng loại bỏ dữ liệu trùng lặp. Nếu có hai khóa công khai tập lệnh giống hệt nhau, chúng tôi chỉ thêm một lần vào bộ lọc.
// danh sách các đối tượng chúng tôi muốn thêm vào bộ lọc // Bao gồm tất cả các khóa công khai của tập lệnh đã sử dụng và mọi khóa công khai của tập lệnh đầu ra // Chúng tôi sử dụng "bản đồ", loại bỏ các khóa công khai của tập lệnh trùng lặp đối tượng := make(map [string] cấu trúc{}) // tạo điều kiện thuận lợi cho mọi giao dịch trong khối for i, tx := range block.Tx { // Thêm khóa công khai tập lệnh cho mỗi đầu ra // vào danh sách các đối tượng của chúng tôi cho _, txOut := phạm vi tx.Vout { PubKey := txOut.PubKey nếu len(PubKey) == 0 { Tiếp tục } // Bỏ qua nếu xuất ra OP_RETURN (0x6a) nếu spk [0] == 0x6a { Tiếp tục } các đối tượng [skpStr] = cấu trúc{}{} } // không thêm đầu vào của giao dịch coinbase nếu tôi == 0 { Tiếp tục } // Đối với mỗi đầu vào, lấy khóa công khai tập lệnh của nó cho _, txIn := phạm vi tx.Vin { prevTx, err := bc.GetRawTransaction(txIn.Txid) nếu sai != nil { trả về con số không, lỗi } PubKey := prevTx.Vout[txIn.Vout].PubKey nếu len(PubKey) == 0 { Tiếp tục } các đối tượng [spkStr] = cấu trúc{}{} } }
OK, bây giờ tất cả các đối tượng được thu thập. Bây giờ, chúng ta định nghĩa biến N là độ dài của đồ thị đối tượng. Ở đây, N là 85 .
Bước tiếp theo là chuyển đổi đối tượng của chúng ta thành các số được phân bố đều trong một khoảng thời gian. Một lần nữa, phạm vi phụ thuộc vào tỷ lệ dương tính giả mà bạn muốn cao bao nhiêu. BIP158 định nghĩa hằng số M là 784931. Điều này có nghĩa là xác suất dương tính giả là 1 trên 784931. Giống như chúng tôi đã làm trước đây, chúng tôi lấy tỷ lệ dương tính giả M nhân với N và nhận được phạm vi phân phối của tất cả các số. Chúng tôi xác định phạm vi này là F, nghĩa là F = M * N . Ở đây, F = 66719135. Tôi sẽ không đi vào chi tiết các chức năng ánh xạ đối tượng thành số (bạn có thể tìm thấy chi tiết trong kho lưu trữ github được liên kết ở trên). Tất cả những gì bạn cần biết là nó lấy đầu vào là đối tượng, hằng số F (xác định phạm vi mà đối tượng cần được ánh xạ tới) và một khóa (hàm băm khối). Khi chúng tôi có tất cả các số, chúng tôi sắp xếp danh sách theo thứ tự tăng dần và sau đó tạo một danh sách mới có tên là chênh lệch chứa chênh lệch giữa hai số liền kề trong danh sách số được sắp xếp.
số := make([]uint64, 0, N) // Lặp qua tất cả các đối tượng và chuyển đổi chúng thành các số phân bố đều trong phạm vi [0, F] // và lưu những số này dưới dạng danh sách số cho o := phạm vi đối tượng { // Sử dụng khóa đã cho, số tối đa (F) và byte đối tượng (o), // chuyển đổi đối tượng thành một số từ 0 đến F. v := convertToNumber(b, F, phím) số = nối thêm (số, v) } // sắp xếp danh sách số sort.Slice(số, func(i, j int) bool { trả lại số [i] < số [j] }) //Chuyển danh sách số thành danh sách chênh lệch khác biệt := make([]uint64, N) for i, num := dãy số { nếu tôi == 0 { khác biệt [i] = số Tiếp tục } khác biệt [i] = num - số[i-1] }
Tuyệt! Đây là một hình ảnh hiển thị một danh sách các số và sự khác biệt.
Bước cuối cùng là mã hóa danh sách các khác biệt bằng cách sử dụng mã hóa Golomb-Rice. Nhớ lại lời giải thích trước đó rằng chúng ta cần chia mỗi chênh lệch cho giá trị có khả năng xảy ra nhất, sau đó mã hóa thương và số dư. Trong ví dụ trước của chúng tôi, tôi đã nói rằng giá trị có khả năng nhất là M và phần còn lại sẽ nằm trong khoảng [0, M]. Tuy nhiên, BIP158 không làm điều này, vì chúng tôi đã tìm thấy 2, đây không phải là tham số thực sự giảm thiểu kích thước bộ lọc cuối cùng. Vì vậy, thay vì sử dụng M, chúng tôi xác định một hằng số P mới và sử dụng 2^P làm tham số Golomb-Rice. P được định nghĩa là 19 . Điều này có nghĩa là chúng tôi chia mỗi chênh lệch cho 2^19 để lấy thương và phần dư, phần còn lại được mã hóa ở dạng nhị phân với 19 bit.
bộ lọc := bstream.NewBStreamWriter(0) // Đối với mỗi giá trị trong danh sách chênh lệch, lấy thương và số dư bằng cách chia cho 2^P. cho _, d := chênh lệch phạm vi { q := math.Floor(float64(d)/math.Exp2(float64(P))) r := d - uint64(math.Exp2(float64(P))*q) // Mã hoá cho tôi := 0; i < int(q); i++ { bộ lọc.WriteBit (đúng) } bộ lọc.WriteBit (sai) bộ lọc.WriteBits(r, P) }
Tuyệt! Bây giờ chúng ta có thể xuất bộ lọc, nhận được:
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0 b0c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade 12fa2e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
Chính xác là bộ lọc giống như chúng ta có trong bitcoin ngoại trừ hai byte đầu tiên! Tại sao có sự khác biệt trong 2 byte đầu tiên? Bởi vì BIP nói rằng giá trị của N cần được mã hóa ở định dạng CompactSize và xuất hiện trước bộ lọc để bộ thu có thể giải mã được. Điều này được thực hiện bởi:
fd := filter.Bytes() bộ đệm byte.Buffer bộ đệm.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) err = wire.WriteInt(&buffer, 0, uint64(N)) nếu sai != nil { trả về con số không, lỗi } _, err = bộ đệm.Write(fd) nếu sai != nil { trả về con số không, lỗi }
Nếu bây giờ chúng ta in lại bộ lọc, chúng ta sẽ thấy rằng nó hoàn toàn giống với kết quả của bitcoind:
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df5743786402383 3f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5 b0b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b5 6ade12fa 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
thành công!
Tuy nhiên, hiểu biết cá nhân của tôi là không cần thêm N vào bộ lọc. Nếu bạn biết giá trị của P, thì bạn có thể tìm được giá trị của N. Hãy xem liệu chúng ta có thể khôi phục danh sách số ban đầu bằng cách sử dụng đầu ra của bộ lọc đầu tiên hay không:
b := bstream.NewBStreamReader(bộ lọc) ( số []uint64 trướcNum uint64 ) vì { // Đọc thương từ chuỗi byte. Số 0 đầu tiên gặp phải cho biết kết thúc thương số // Trước khi gặp 0, số 1 đại diện cho thương số q uint64 c, lỗi := b.ReadBit() nếu sai != nil { trả lại lỗi } cho c{ q++ c, lỗi = b.ReadBit() nếu lỗi.Is(err, io.EOF) { phá vỡ } other if err != nil { trả lại lỗi } } // P bit tiếp theo mã hóa phần còn lại r, err := b.ReadBits(P) nếu lỗi.Is(err, io.EOF) { phá vỡ } other if err != nil { trả lại lỗi } n := q*uint64(math.Exp2(float64(P))) + r num := n + prevNum số = nối thêm (số, số) prevNum = số } fmt.Println(số)
Hoạt động trên tạo ra cùng một danh sách các số, vì vậy chúng tôi có thể xây dựng lại nó mà không cần biết N. Vì vậy, tôi không chắc lý do căn bản để thêm N vào bộ lọc là gì. Nếu bạn biết tại sao N phải được đưa vào, vui lòng cho tôi biết!
Cảm ơn vì đã đọc!