Vitalik: Phân mảnh + Lấy mẫu dữ liệu sẵn có

Tác giả | Vitalik Buterin

Tác giả | Vitalik Buterin"Ngoài Proof of Stake, một thay đổi đáng kể khác trong thiết kế của eth2 là sharding. Đề xuất này giới thiệu một hình thức hạn chế của sharding, "data sharding", dựa trên"Lộ trình tập trung vào rollup

Để tránh gánh nặng của các nút tự tải xuống tất cả dữ liệu, hai kỹ thuật này có thể được áp dụng cho nhau để xác minh tính khả dụng của một lượng lớn dữ liệu: 1) Bằng chứng của một ủy ban được lấy mẫu ngẫu nhiên; 2) Lấy mẫu tính khả dụng của dữ liệu (tính khả dụng của dữ liệu lấy mẫu, DAS).

tiêu đề cấp đầu tiên

"Ủy ban lấy mẫu ngẫu nhiên" bản ngữ

Giả sử bạn có nhiều dữ liệu, chẳng hạn 16 MB, đây là dung lượng mà chuỗi eth2 (ít nhất là ban đầu) có thể xử lý trên mỗi vị trí. Chúng tôi biểu thị dữ liệu này dưới dạng 64 đốm màu, mỗi đốm có kích thước 256 kB. Giả sử chúng ta cũng có một hệ thống PoS với khoảng 6400 trình xác thực. Làm cách nào để chúng tôi xác minh dữ liệu này mà không cần 1) yêu cầu bất kỳ ai tải xuống tất cả dữ liệu đó và 2) không tạo cơ hội cho kẻ tấn công đang chạy một số trình xác thực?

Vấn đề đầu tiên, chúng ta có thể giải quyết bằng cách phân công lao động: trình xác minh 1-100 cần tải xuống và xác minh đốm đầu tiên, trình xác minh 101-200 tải xuống và xác minh đốm thứ hai, v.v. Những người xác thực trong mỗi tập hợp con (ủy ban) chỉ cần ký để chứng minh rằng họ đã xác minh blob tương ứng và sau đó toàn bộ mạng có thể chấp nhận blob sau khi nhận được chữ ký của đa số người xác nhận trong ủy ban tương ứng.

Nhưng điều này dẫn đến một vấn đề: điều gì sẽ xảy ra nếu kẻ tấn công chiếm quyền kiểm soát một nhóm trình xác thực liền kề (ví dụ: 1971-2070)? Nếu đúng như vậy, ngay cả khi kẻ tấn công chỉ kiểm soát khoảng 1,5% toàn bộ bộ trình xác nhận, thì chúng vẫn có thể kiểm soát một ủy ban duy nhất (trong trường hợp trên, chúng có thể kiểm soát 70% trình xác thực 2001-2100 trong ủy ban 20), vì vậy tấn công Người vận hành có thể thêm các đốm màu không hợp lệ/không sử dụng được vào chuỗi.

RNG (Trình tạo số ngẫu nhiên) được tạo sau khi ký gửi trình xác thực và chỉ mục của mỗi trình xác thực là cố định, vì vậy kẻ tấn công không thể cố gắng đưa tất cả các trình xác thực vào cùng một ủy ban. Kẻ tấn công có thể gặp may, nhưng chỉ khi chúng kiểm soát hơn 1/3 số trình xác thực.

tiêu đề cấp đầu tiên

"Lấy mẫu sẵn có của dữ liệu" bản ngữ

Ở một số khía cạnh, lấy mẫu sẵn có của dữ liệu là hình ảnh phản chiếu của các ủy ban lấy mẫu ngẫu nhiên. Quá trình lấy mẫu vẫn xảy ra do mỗi nút cuối cùng chỉ tải xuống một phần nhỏ của tất cả dữ liệu, nhưng quá trình lấy mẫu diễn ra trong ứng dụng khách và trên mỗi đốm màu, không phải trên các đốm màu.

Mỗi nút (bao gồm cả các nút máy khách không tham gia đặt cược) kiểm tra từng đốm màu, thay vì tải xuống toàn bộ đốm màu, họ chọn riêng N chỉ số ngẫu nhiên từ nó và sau đó thử tải xuống dữ liệu tại các vị trí đó.

Cơ chế này hiệu quả vì khách hàng chỉ cần tải xuống một phần nhỏ dữ liệu trong mỗi đốm màu để xác minh tính khả dụng của nó. Cơ chế này cũng có tính bảo mật cao vì ngay cả kẻ tấn công 51% cũng không thể lừa khách hàng chấp nhận một đốm màu không sử dụng được.

xóa mã hóa

chữ

Để tránh trường hợp kẻ tấn công cung cấp 50-99% dữ liệu có sẵn (điều này có thể khiến một số khách hàng từ chối blob và sau đó được chấp nhận bởi những người khác), chúng tôi sử dụng một kỹ thuật gọi là mã hóa xóa. Mã hóa xóa cho phép chúng tôi mã hóa các đốm màu theo cách mà nếu hơn một nửa dữ liệu trong một đốm màu đã được xuất bản, thì bất kỳ ai trong mạng cũng có thể tái tạo và xuất bản dữ liệu còn lại.

Sau khi dữ liệu được xuất bản lại đã được phát, các máy khách ban đầu từ chối đốm màu sẽ hội tụ để chấp nhận (lưu ý rằng không có giới hạn thời gian để chấp nhận một đốm màu, mỗi khi máy khách nhận được phản hồi cho tất cả các chỉ số được lấy mẫu, nó sẽ chấp nhận một đốm màu có sẵn) .

Phép loại suy toán học đơn giản nhất để hiểu mã hóa xóa là "hai điểm luôn đủ để khôi phục một dòng": nếu tôi có bốn điểm ở dạng ((1, 4), (2, 7), (3, 10), (4 , 13)) để tạo một "tệp", mỗi điểm nằm trên một đường thẳng, sau đó miễn là bạn có tọa độ của hai trong số các điểm, bạn có thể tạo lại đường thẳng và tính toán hai điểm còn lại ( Chúng tôi giả sử rằng x- tọa độ 1, 2, 3, 4 là các tham số cố định của hệ thống, không phải do người tạo tệp lựa chọn).

Sử dụng đa thức bậc cao hơn, chúng ta có thể mở rộng ý tưởng này để tạo 3 trong số 6 tệp, 4 trên 8 tệp hoặc nói chung là n trong số 2n tệp nếu bạn có n điểm trong số tệp, các điểm còn lại trong 2n có thể được tính.

Chúng tôi sử dụng các cam kết đa thức, cụ thể là các cam kết Kate thay vì gốc Merkle làm máy in cho các đốm màu dữ liệu, vì các cam kết đa thức cho phép chúng tôi dễ dàng chứng minh rằng một giá trị đã cho thực sự là đa thức ở một mức độ n nhất định trong ước tính chính xác tại tọa độ được yêu cầu. Mặt khác, chúng tôi sẽ phải chứng minh (ví dụ: sử dụng SNARK) rằng gốc Merkle mã hóa đa thức bậc thấp hoặc dựa vào bằng chứng gian lận để phát nếu mã hóa không chính xác (điều này làm tăng thêm các giả định về độ phức tạp cao và đồng bộ hơn ).

tiêu đề cấp đầu tiên

Việc lấy mẫu tính khả dụng của dữ liệu có còn cần thiết với cơ chế ủy ban không?

Nếu bạn chỉ dựa vào ủy ban, có thể có những nhược điểm sau:

➤ Khả năng phòng thủ yếu hơn trong trường hợp bị tấn công 51%. Trên các chuỗi khối hiện tại (không thể mở rộng), cuộc tấn công 51% chỉ có thể khôi phục hoặc kiểm duyệt các giao dịch và không thể thêm các khối không hợp lệ vào chuỗi. Các hệ thống dựa trên ủy ban mất đi sự đảm bảo này.

Hơn nữa, sẽ rất khó để trừng phạt hiệu quả những kẻ tấn công 51%, vì họ chỉ có một lượng tiền gửi rất nhỏ (tiền gửi tham gia vào ủy ban cụ thể đó) có thể được chứng minh là có liên quan đến hành vi nguy hiểm và bị trừng phạt dựa trên đó.

➤ DAS dễ dàng hơn một chút so với các cơ chế của ủy ban để chống lại các cuộc tấn công lượng tử (có thể yêu cầu chữ ký tổng hợp sau lượng tử).

tiêu đề cấp đầu tiên

Vẫn cần một cơ chế ủy ban với việc lấy mẫu dữ liệu sẵn có?

Nếu chỉ sử dụng DAS, các vấn đề sau có thể phát sinh:

➤ DAS là một công nghệ mới chưa được thử nghiệm, cốt lõi của nó (xem tại đây) chỉ mới được phát triển vào năm ngoái. Do đó, nên sử dụng ủy ban để cung cấp sự bảo vệ trong trường hợp xảy ra sự cố DAS hoặc kéo dài thời gian phát triển ngoài dự kiến.

➤ DAS có độ trễ cao hơn các ủy ban.

➤ DAS có nhiều trường hợp khó khăn hơn mà các ủy ban có thể hỗ trợ. Một ví dụ là trong hệ thống chỉ dành cho DAS, rất khó tránh khỏi việc người đề xuất khối đèn hiệu là người đầu tiên bắt đầu yêu cầu DAS để xác minh tính khả dụng của blob.

Điều này làm tăng nguy cơ kẻ tấn công xuất bản một đốm màu không sử dụng được và chỉ đáp ứng yêu cầu của người đề xuất. Điều này sẽ không khiến các nút khác của mạng chấp nhận các đốm màu không sử dụng được, nhưng có thể làm cho các cuộc tấn công khác dễ dàng hơn, khiến các khối đèn hiệu do những người đề xuất trung thực xây dựng bị từ chối và rẽ nhánh khỏi chuỗi chính. Ủy ban có thể khắc phục điều này.

➤ Khả năng tương thích chuyển tiếp của cơ chế ủy ban mạnh hơn, giúp có thể thêm các chức năng thực thi vào các phân đoạn trong tương lai.

Tầm quan trọng của dữ liệu sẵn có? Thách thức là gì?

Điều này đã được thảo luận ở nơi khác vì vậy tôi sẽ không đăng nó ở đây, nhưng tôi khuyên bạn nên đọc:

➤Lưu ý về tính khả dụng của dữ liệu và mã xóa (giới thiệu ban đầu về tính khả dụng của dữ liệu)

➤ Một bài báo của Alberto Sonnino, Mustafa Al-Bassam và Vitalik Buterin mở rộng khái niệm

➤ The Dawn of Hybrid Layer 2 Protocols thảo luận về lý thuyết trò chơi về tính khả dụng của dữ liệu

➤ Lớp cơ sở và Tốc độ thoát chức năng, dựa trên các khái niệm trên, phần khả năng mở rộng dữ liệu được mô tả

➤ Vấn đề về tính khả dụng của dữ liệu (Cuộc gặp gỡ tại Thung lũng Silicon của Ethereum), một cuộc thảo luận video về vấn đề về tính khả dụng của dữ liệu

Rõ ràng, BitTorrent và IPFS và các hệ thống tương tự không giải quyết được vấn đề về tính khả dụng của dữ liệu. Mặc dù BitTorrent là một công nghệ phân phối dữ liệu có khả năng mở rộng tốt, nhưng nó không thể đạt được sự đồng thuận về việc liệu có sẵn dữ liệu hay không, điều này tạo ra khả năng xảy ra một cuộc tấn công "trường hợp cực đoan". 2 giao thức không hiệu quả. Để đạt được sự đồng thuận về tính khả dụng của dữ liệu, cần sử dụng các kỹ thuật hiệu quả hơn được mô tả trong tài liệu này.

Làm thế nào để sharding hoạt động trên lớp P2P?

Để đạt được mục đích về khả năng mở rộng của sharding, chúng tôi cần một hệ thống P2P để mọi nút không cần tải xuống tất cả dữ liệu. May mắn thay, chúng tôi đã có một dạng bảo vệ lớp P2P trong Giai đoạn 0. Cụ thể, 64 tập hợp con đã được sử dụng để chứng minh tập hợp. Mỗi trình xác thực chỉ cần tồn tại trong "mạng con toàn cầu" chính và mạng con tổng hợp chứng thực của riêng chúng mà không cần tìm nạp bất kỳ dữ liệu nào từ 63 tập hợp con chứng thực tổng hợp khác.

Trong phân đoạn loại ủy ban + DAS, chúng tôi mở rộng nó thành kiến ​​trúc "lưới", với 2048 mạng con ngang (mạng con ngang), nghĩa là có một tập hợp con trong mỗi cặp khe cắm phân đoạn của mỗi kỷ nguyên và 2048 mạng con dọc (dọc mạng con), tức là có một tập hợp con của mỗi chỉ mục trong mỗi đốm màu.

Trong mỗi vị trí, chúng tôi chọn một người đề xuất cho mỗi phân đoạn. Mỗi người đề xuất có quyền đề xuất một blob: một khối dữ liệu tùy ý lên tới 512 kB (có thể hiểu là tập hợp các “mẫu” khoảng 512 byte), với phần mở rộng mã hóa xóa và bằng chứng bổ sung cho mỗi phần trong blob. được kiểm chứng độc lập.

Cấu trúc của một đốm màu Cấu trúc của một đốm màu

Cấu trúc "phần thân" của một blob bao gồm dữ liệu gốc, dữ liệu mở rộng và bằng chứng (nếu muốn, dữ liệu mở rộng có thể được bỏ qua để đảm bảo hiệu quả dữ liệu, vì mỗi nút nhận blob có thể tái tạo lại nó tương đối nhanh).

"Tiêu đề" của blob chứa cam kết Kate tương ứng của nó, cùng với một số dữ liệu khác (vị trí, phân đoạn và bằng chứng về độ dài) và chữ ký của người đề xuất.

Quá trình phát sóng Blob

Khi một đốm màu được phát, tiêu đề của nó được phát tới mạng con toàn cầu và phần thân được phát tới mạng con ngang tương ứng với ID vị trí và phân đoạn.

Trong thực tế, sẽ có 2048 mạng con ngang, do đó, có một mạng con ngang cho mỗi cặp khe phân đoạn trong mỗi kỷ nguyên. Điều này được thực hiện để đảm bảo rằng mỗi người xác thực có thể tham gia mạng con ngang và họ sẽ chỉ nhận được các đốm màu tương ứng với ủy ban của họ (không bao gồm một số lượng nhỏ mạng con dọc mà họ tham gia lấy mẫu).

Mỗi trình xác thực cần tham gia các mạng con sau:

➤ Mạng con toàn cầu

➤ Mạng con dọc, tương ứng với chỉ mục mà nó được chỉ định (được tính bằng cách sử dụng hạt giống riêng cho mỗi trình xác thực)

khối phát sóng

chữ

Người đề xuất blob có thể phân phối các mẫu cho tất cả các mạng con, nhưng không nhất thiết phải là một phần của mạng con. Quá trình này như sau:

➤ Công bố: Người đề xuất công bố blob theo đúng mạng con ngang, mỗi mẫu đi kèm với một bằng chứng

➤ Phân phối mẫu trực tiếp: những người tham gia khác trong mạng con ngang xuất bản các khối tới từng mạng con dọc mà họ tham gia

➤ Phân phối mẫu gián tiếp: Người đề xuất thông báo cho các đồng nghiệp về một số mạng con dọc mà nó nằm trong đó. Do đó, mỗi người tham gia trong mạng con ngang cũng có thể thấy mạng con dọc mà các đồng nghiệp của họ đang tham gia và phát khối tương ứng cho các đồng nghiệp đó

Giả sử kích thước khối dữ liệu là 512 byte và khối dữ liệu tối đa là 512 kB (không bao gồm mã hóa xóa), tức là khoảng 1 MB khi bao gồm mã hóa xóa, có 2048 mạng con dọc. Nếu mỗi nút tồn tại trong 15 mạng con dọc riêng tư, 5 mạng con dọc công cộng và có 50 mạng ngang hàng, giả sử trường hợp xấu nhất là 128 thành viên trong mỗi mạng con ngang (chỉ dành cho ủy ban), thì riêng các thành viên Mạng con sẽ được phân phối trực tiếp tới 128 * 20 = 2560 mạng con (khoảng .1461 sau khi loại bỏ xuất bản dư thừa) và nếu thêm các nút ngang hàng, nó sẽ tăng lên 128 * 4 * 50 = 25600 mạng con.

Lưu ý rằng về mặt lý thuyết, những người đề xuất khối độc hại có thể xuất bản các mẫu lên mạng con dọc mà không xuất bản các khối đầy đủ. Để giải quyết tình trạng này, chúng tôi đã thêm một quy trình trong đó các khối được xuất bản chưa hoàn chỉnh (có nghĩa là có sẵn từ 50% trở lên, nhưng không có sẵn 100%) có thể "tự phục hồi". Quá trình bao gồm ba bước cơ bản:

1. Phân phối ngược: Quá trình phân phối tương tự như trên, ngoại trừ trong trường hợp này, các đồng nghiệp trên mạng con dọc truyền mẫu từ mạng con dọc đó sang mạng con ngang tương ứng với đốm màu mà mẫu thuộc về.

3. Phân phối: Lặp lại các bước phân phối ở trên

tiêu đề cấp đầu tiên

Chuỗi đèn hiệu hoạt động như thế nào?

Trong mỗi vị trí, chúng tôi chọn ngẫu nhiên một người đề xuất cho mỗi trong số 64 phân đoạn. Người đề xuất có quyền tạo một shard blob, quảng bá nó thông qua quy trình trên và quảng bá ShardHeader của blob tới mạng con toàn cầu. ShardHeader có thể được đóng gói vào cùng một vị trí trên chuỗi đèn hiệu và cũng có thể được đưa vào bất kỳ vị trí tiếp theo nào trong cùng một kỷ nguyên/kỷ nguyên tiếp theo.

Chuỗi báo hiệu theo dõi danh sách các đối tượng PendingShardHeader. PendingShardHeader lưu trữ: 1) thông tin chính trong ShardHeader (phân đoạn và vị trí, cam kết của blob và độ dài của nó); 2) một trường bit theo dõi trình xác nhận nào trong ủy ban được chọn ngẫu nhiên đã ký vào blob (thực ra, ủy ban giai đoạn 0 đã được giới thiệu) . Cấu trúc AttestationData được mở rộng để bao gồm shard_header_root, hàm băm gốc của ShardHeader mà trình xác thực được chọn để bỏ phiếu. Người kiểm chứng cũng có thể bỏ phiếu cho hàm băm gốc trống nếu họ không thấy đốm màu phân đoạn hợp lệ và có thể sử dụng được đã được chỉ định cho cặp vị trí phân đoạn của họ.

Nếu ShardHeader được chứng thực bởi 2/3 số người xác thực trong ủy ban, nó sẽ được xác nhận ngay lập tức. Nếu vào cuối kỷ nguyên tiếp theo, người phân mảnh nhận được nhiều sự hỗ trợ từ ủy ban hơn bất kỳ người phân mảnh nào khác, thì điều đó sẽ được xác nhận vào cuối kỷ nguyên đó.

Quy tắc lựa chọn ngã ba

Các quy tắc lựa chọn ngã ba đã được thay đổi để một khối chỉ hợp lệ nếu tất cả các đốm màu hoặc tổ tiên của chúng được xác nhận trong khối đó để vượt qua kiểm tra tính khả dụng. Điều này được gọi là khớp nối chặt chẽ: nếu một chuỗi trỏ đến (đã xác nhận) một đốm màu không hợp lệ, thì toàn bộ chuỗi được coi là không hợp lệ. Đây là sự khác biệt chính so với cấu trúc "sidechain": trong một sidechain, sidechain có thể bị lỗi trong khi mainchain vẫn còn hiệu lực.

Đây là một khám phá sâu hơn về khớp nối chặt chẽ và lý do tại sao nó có giá trị.

Khi số lượng trình xác nhận thấp

Nếu có ít hơn 262144 người xác thực (32 vị trí * 64 phân đoạn * 128 kích thước ủy ban tối thiểu), thì thay vì chọn một người đề xuất cho tất cả các phân đoạn, chúng tôi chọn một người đề xuất cho một tập hợp con giới hạn và lặp qua các mảnh. Ví dụ: nếu có trình xác thực 32 * 128 * 50 và phân đoạn bắt đầu ở vị trí N là 0, thì vị trí N sẽ chỉ định người đề xuất cho các phân đoạn 0-49 và vị trí N+1 sẽ chỉ định một người đề xuất cho các phân đoạn 50- Phân đoạn 63 và 0-35 sẽ chỉ định một người đề xuất, vị trí N+2 sẽ chỉ định những người đề xuất cho các phân đoạn 36-63 và 0-21, v.v. Điều này được thực hiện để đảm bảo rằng ngay cả khi tỷ lệ tham gia thấp, quy mô của ủy ban vẫn phù hợp.

Đã thêm một cơ chế tương tự như EIP-1559, thanh toán dữ liệu phân đoạn theo byte và điều chỉnh giá: nếu dung lượng trung bình của khối vượt quá 50%, phí sẽ tăng lên và ngược lại. Do đó, chỉ báo là 50% kích thước khối trung bình.

tiêu đề cấp đầu tiên

giả định an toàn

Phương pháp bảo vệ chỉ blob dữ liệu rất hiệu quả vì nó ít dựa vào các giả định về an toàn hơn so với các chương trình bảo vệ khác. Đặc biệt, nó tránh được các giả định đa số trung thực (vì DAS có thể phát hiện các đốm màu không sử dụng được do đa số đưa ra) và các giả định về thời gian (không giống như các cơ chế DAS trước đó, sử dụng các cam kết Kate thay vì bằng chứng gian lận và do đó không dựa vào giả định rằng cần có bằng chứng gian lận sẽ được phát sóng cực kỳ nhanh chóng).

Giả định mới chính là "giả định DAS thiểu số trung thực": có một mẫu nút đủ lớn mà kẻ tấn công phải xuất bản hơn một nửa khối. Nếu có 2048 mẫu trong một blob, thì 1024 mẫu cần được khôi phục (xét rằng một số khách hàng sẽ lấy mẫu các điểm giống nhau, vì vậy 2048 * ln(2) ~= 1419) và mỗi khách hàng thực hiện 20 mẫu, hệ thống có thể được xem xét an toàn nếu có khoảng hơn 70 khách hàng trên mỗi phân đoạn đang lấy mẫu.

tiêu đề cấp đầu tiên

Thiết kế sharding chỉ hỗ trợ các đốm màu dữ liệu tương thích với nhiều tình huống bổ sung khả năng thực thi trong sharding trong tương lai. Cụ thể, chúng tôi có thể sửa đổi sơ đồ sao cho blob chứa các gốc trước và sau trạng thái, đồng thời chúng tôi cũng có thể sử dụng bằng chứng gian lận hoặc ZK-SNARK để xác minh rằng các chuyển đổi trạng thái trong blob là chính xác. Lưu ý rằng bất kể cách tiếp cận nào được chọn, việc đảm bảo tính chính xác của việc thực thi phân đoạn không phụ thuộc vào bất kỳ giả định đa số trung thực nào.

chữ

https://github.com/ethereum/eth2.0-specs/pull/2146

Tài khoản chính thức: Trạm Trung Quốc ETH

Protolambda’s work-in-progress implementation

Liên kết gốc:https://hackmd.io/@HWeNw8hNRimMm2m2GH56Cw/sharding_proposal

Công việc dịch thuật của ECN nhằm mục đích cung cấp thông tin và tài nguyên học tập chất lượng cao cho cộng đồng Ethereum Trung Quốc. Bản quyền của bài viết thuộc về tác giả gốc và phải ghi rõ nguồn của văn bản gốc cũng như trang web ETH Trung Quốc khi in lại. Để tái bản dài hạn, vui lòng liên hệ với eth@ecn.co để được ủy quyền.

Tài khoản chính thức: Trạm Trung Quốc ETH

Trang web: ethereum.cn