Ofelimos - giao thức đồng thuận mới

Ngày 19 tháng 08 năm 2022

Nghiên cứu của IOG giới thiệu một giao thức đồng thuận mới, an toàn có thể chứng minh được để giảm thiểu sự lãng phí năng lượng của các blockchains bằng chứng công việc, đó chính là Bằng chứng về công việc hữu ích (PoUW).

Giảm thiểu chi phí năng lượng Bằng chứng công việc (PoW) và lượng khí thải carbon là một trong những chủ đề được thảo luận sôi nổi nhất trong lĩnh vực crypto. Việc thay thế PoW nguyên thủy trong giao thức chuỗi dài nhất của Nakamoto bằng một Bằng chứng về công việc hữu ích (PoUW) từ lâu đã được biết đến ở dạng lý thuyết. Đó là một giải pháp lý tưởng ở nhiều khía cạnh, nhưng cho đến ngày nay, khái niệm này vẫn chưa được xác thực một cách thuyết phục.

Hôm nay, tại hội nghị mật mã quốc tế hàng đầu, Crypto , Input Output Global, Inc (IOG) giới thiệu Ofelimos , một giao thức blockchain mới dựa trên PoUW có cơ chế đồng thuận đồng thời nhận ra một trình giải quyết vấn đề tối ưu hóa phi tập trung. Cơ chế đồng thuận sử dụng công việc để giải quyết các vấn đề tính toán quan tâm thực tế để duy trì chuỗi khối.

So sánh PoW với PoUW

Các giao thức blockchain dựa trên PoW tận dụng công việc được thực hiện bởi những người tham gia giao thức, được gọi là thợ đào. PoW đảm bảo tính bảo mật của sổ cái bằng cách khuyến khích các thợ đào cạnh tranh trong việc giải quyết các vấn đề tính toán để đủ điều kiện tạo ra một khối mới. Công việc tính toán này duy trì tính bảo mật của giao thức nhưng yêu cầu sử dụng năng lượng và tài nguyên đáng kể. Tại thời điểm viết bài, Bitcoin có mức chi tiêu năng lượng hàng năm ngang bằng với nhiều quốc gia vừa và nhỏ.

Bằng chứng về công việc hữu ích (PoUW) giải quyết vấn đề hiệu quả năng lượng bằng cách tái định vị nỗ lực tính toán cần thiết để duy trì bảo mật giao thức nhằm giải quyết các vấn đề phức tạp trong thế giới thực, chẳng hạn như tối ưu hóa hậu cần của công ty hoặc lập lịch sự kiện.

Một trong những thách thức của PoUW là giải quyết tình huống khó xử sau: nếu các vấn đề cần giải quyết thực sự hữu ích (đến từ thế giới thực), kẻ tấn công có thể chiếm quyền hệ thống đặt ra các trường hợp hay vấn đề có thể giải quyết dễ dàng (hoặc đã được kẻ tấn công giải quyết). Điều này sẽ tận dụng các nguồn lực của kẻ tấn công để nó có thể tạo ra nhiều khối (block) hơn so với những người tham gia trung thực khác với cùng một lượng tài nguyên và do đó sẽ làm giảm tính bảo mật của blockchain. Nếu muốn giảm thiểu khả năng của kẻ tấn công, có thể dùng các thuật toán ngẫu nhiên, nhưng nó sẽ làm cho các tính toán của hệ thống trở nên vô dụng trong thực tế.

Ofelimos giải quyết tình huống khó xử này cùng với phân tích tính hữu ích và bảo mật chính thức.

Tổng quan về Ofelimos

Các máy trạm công bố các vấn đề cần giải quyết và phần thưởng sẽ được trả cho những người khai thác thành công. Cũng giống như trong PoW, các thợ đào giải quyết những vấn đề này để tham gia vào một cuộc chơi xổ số để quyết định điều kiện đủ để được tạo khối.

Trong PoW thuần túy, cuộc chơi xổ số này thường bao gồm việc hash lặp đi lặp lại một thử thách (cùng với một bộ đếm) và so với một giá trị mục tiêu nhất định. Bạn sẽ giành phần thắng nếu giá trị hash nằm dưới giá trị mục tiêu. Lưu ý rằng trong PoW thuần túy, một tính toán đơn lẻ là rất nhanh nhưng xác suất để đạt được mục tiêu lại là rất nhỏ.

Vì nhiều lý do, trong PoUW, bạn cũng nên giữ cho một tính toán (tương đối) nhanh, điều này giảm thiểu xác suất nhiều khối được sản xuất cùng lúc. Mặt khác, khả năng giải quyết vấn đề của máy trạm phải đủ lớn để việc được thuê tính toán là đủ hấp dẫn. Đối với PoUW, điều tự nhiên là hướng đến các lớp tính toán phức tạp như một tổng thể, nhưng có thể chia thành các bước nhỏ 'đồng nhất'. Mỗi bước phải yêu cầu cùng một lượng công việc (theo kỳ vọng) và tương ứng với một tính toán PoW thuần túy.

Tìm kiếm cục bộ ngẫu nhiên (Stochastic local search - SLS) là một loại tính toán rõ ràng như vậy. Các thuật toán SLS được áp dụng cho các bài toán tối ưu hóa mà không có thuật toán xác định hiệu quả nào được biết đến. Thay vào đó, SLS thực hiện một bước đi ngẫu nhiên trong lĩnh vực giải pháp cố gắng tối ưu hóa dần dần giải pháp bằng cách sử dụng các phương pháp heuristics nhất định. Vì mỗi bước tính toán trong bước đi ngẫu nhiên là một ví dụ khác nhau của cùng một phép tính, SLS là một ứng cử viên tuyệt vời cho PoUW theo các yêu cầu trên. Hơn nữa, SLS có mức độ liên quan thực tế cao với các ứng dụng kinh tế thực trong các lĩnh vực như lập kế hoạch hậu cần, lập lịch sự kiện, v.v.

Chuyển đổi từng bước từ PoW sang PoUW

Các thợ mỏ tiếp nhận và giải quyết các thách thức do các máy trạm đăng trên blockchain. Các thách thức được cập nhật liên tục và được lưu trữ trong blockchain cho đến khi một số tiêu chí chấm dứt xuất hiện, ví dụ: con số mục tiêu đã được tìm thấy tại một bước tính toán hoặc nếu một giải pháp thích hợp đã được đưa ra.

Bây giờ chúng tôi xây dựng lại cách chuyển đổi PoW thuần túy thành PoUW trong cài đặt này.

1. Trong PoW thuần túy, người khai thác phải mở rộng chuỗi dài nhất của họ bằng một khối mới, hash lặp lại khối mới theo một mục tiêu nhất định (bằng cách thay đổi bộ đếm có trong khối). Bước đầu tiên, chúng tôi thay thế hash lặp lại bằng tính toán lặp lại của bước tính toán SLS Mtrên trạng thái tính toán trước đó được lưu trữ trên chuỗi, trong đó khối xác định hạt giống ngẫu nhiên cho bước tính toán. Xem Hình 1 (bên phải): Trạng thái tính toán trước s được mở rộng bằng bước tính toán ngẫu nhiên Mbằng cách sử dụng hạt giống kết quả từ việc hash khối cùng với trạng thái s, tạo ra trạng thái tính toán mới (có thể tốt hơn) s'. Quá trình này được lặp lại cho đến khi điều kiện chưa được giải quyết ? được đáp ứng, cho phép người khai thác xuất bản khối. Trong quá trình này, người khai thác theo dõi trạng thái tốt nhất đã được tìm thấy trong quá trình lặp đi lặp lại này.

Hình 1: Hashing mục tiêu T (PoW, bên trái). Lặp lại bước tính toán M(PoUW, bên phải).

2. Bây giờ chúng tôi khắc phục điều kiện thành công bị thiếu ?. Để đạt được các đặc tính ngẫu nhiên tốt mà không bị sai lệch bởi tính toán cụ thể, việc tìm kiếm một khối được tách ra khỏi chất lượng của trạng thái được tính toán, bằng cách thêm, sau bước tính toán, một 'Hậu hashing' (post-hashing) vào bước tính toán (sử dụng lại ban đầu hạt giống) - xem Hình 2 - và khối đủ điều kiện để xuất bản nếu giá trị hash này thấp hơn một số mục tiêu T3. Bên cạnh giải pháp tốt nhất hiện tại là tốt nhất , điều này giới thiệu trạng thái mới của T phải được xuất bản với khối, trạng thái dẫn đến hash bên dưới T3 - để chứng minh tính đủ điều kiện để xuất bản khối. Lưu ý rằng chỉ s phục vụ tốt nhất như một bản cập nhật trạng thái (được các thợ mỏ khám phá thêm) trong khi sT chỉ đóng vai trò là nhân chứng cho việc đủ điều kiện xuất bản khối.

Hình 2: Ngẫu nhiên hóa tính đủ điều kiện để xuất bản khối

3. Xét rằng M khó tính toán hơn H và không phải tất cả các trường hợp của Mđều có thể yêu cầu cùng một lượng công việc, đối thủ có thể nghiền những hạt giống cho phép họ tăng tốc độ tính toán M so với một người khai thác trung thực, do đó đạt được một lợi thế trong việc tạo ra các khối nhanh hơn và làm giảm tính bảo mật của hệ thống. Chúng tôi giảm thiểu việc lặp lại như vậy bằng cách yêu cầu hash ban đầu thấp hơn T1 mục tiêu. Ví dụ: trước khi thực hiện bước tính toán M, người khai thác phải tìm giá trị hash thấp bằng cách thay đổi bộ đếm khối dọc theo các dòng của PoW thuần túy. Xem Hình 3. Cụ thể, T1 được chọn sao cho công việc mong đợi để tìm một giá trị hash dưới mục tiêu T1 chi phí ít nhất bằng mức độ phức tạp về thời gian trong trường hợp xấu nhất của việc tính toán M - việc thực thi lặp lại cho một trường hợp dễ dàng cũng tốn kém như tính toán một trường hợp 'bất tiện' của M. Một bộ ba (Bctr, s best, sT ) thỏa mãn các điều kiện trên do đó tạo thành PoUW.

Hình 3: Bảo vệ chống mài bằng cách hash trước đối với mục tiêu T1

4. Trái ngược với PoW thuần túy, chúng ta không thể có khả năng để các node xác minh các PoUW bằng cách lặp lại phép tính Mcủa người khai thác, vì điều này có nghĩa là một lượng lớn tính toán được sao chép và do đó giảm đáng kể phần tính toán thực sự hữu ích đó trong hệ thống. Để tránh điều này, khi 'tìm thấy' một khối có thể xuất bản, người khai thác được yêu cầu tạo một đối số không tương tác ngắn gọn (SNARG) để chứng minh thành công như vậy - với lợi ích là độ phức tạp xác minh trở nên độc lập với độ phức tạp để tính M. Ngoài ra, tính toán đúng của giải pháp tốt nhất tốt nhất đã được chứng minh. Xem Hình 4.

Hình 4: Giảm thiểu xác minh phân tán bằng cách thêm bằng chứng không tương tác

5. Để tận dụng lợi thế của việc khai thác đồng thời phân tán, cá thể SLS được song song hóa (ví dụ: bằng cách duy trì nhiều đường tính toán) vì, nếu không, tất cả các thợ đào sẽ đồng thời sử dụng cùng một trạng thái, tạo ra rất nhiều (về cơ bản) các bước tính toán dư thừa. Lưu ý rằng, vì lý do bảo mật, quá trình sản xuất khối trong PoW 'Nakamoto' tiêu chuẩn diễn ra chậm và các bản cập nhật trạng thái gắn liền với các khối. Mặt khác, các bản cập nhật trạng thái phải tiến hành nhanh chóng để tránh các thợ mỏ sử dụng các trạng thái 'lỗi thời'. Do đó, chúng tôi giới thiệu hai loại khối, khối xếp hạng (ranking block) 'khó tìm' có cùng chức năng như trong sự đồng thuận của Nakamoto và khối đầu vào (input block) 'dễ tìm' có chức năng giống như các giao dịch được các khối xếp hạng tham chiếu cuối cùng. Bằng cách này, giải pháp tốt nhất của người khai thác có thể được phổ biến tương đối nhanh, do đó giữ cho tất cả người khai thác được cập nhật. Đặc biệt, điều này đạt được bằng cách đánh giá lần đầu tiên hash cuối cùng với mục tiêu ‘dễ dàng’ T3 . Nếu nó ở bên dưới, nó đủ điều kiện là một khối có thể xuất bản, nhưng chỉ khi mục tiêu nằm dưới mục tiêu 'khó hơn' T2 , thì khối đủ điều kiện là khối xếp hạng 'có liên quan đến đồng thuận' - nếu không, nó được định nghĩa là khối đầu vào. Xem Hình 5.

Hình 5: Một hậu hash bên dưới T2 đủ điều kiện cho khối đó là khối xếp hạng. Một Hậu hashing giữa T2 và T3 đủ điều kiện cho khối này là khối đầu vào

Thuộc tính giao thức

Việc đưa ra một phân tích kỹ lưỡng về tính bảo mật và tính hữu dụng của giao thức nằm ngoài phạm vi của bài viết này. Vẫn có thể hữu ích khi nhắc lại một số trực giác tại sao giao thức lại an toàn và sau đó kết luận bằng cách kiểm tra tính hiệu quả của giao thức.

Bảo mật chuỗi khối:

• Lặp lại : đối thủ không có lợi thế bằng cách Lặp lại các phiên bản dễ tính toán của M. Điều này đạt được bằng cách điều chỉnh ngưỡng tiền băm T1 sao cho việc tính toán M trên bất kỳ trường hợp nào cũng khó bằng việc tìm một tiền băm mới dưới T1 ( Trong kỳ vọng).
• Khả năng chống lại lợi thế của đối thủ : Lợi thế của đối thủ trong việc tính toán PoUW nhanh hơn so với các bên trung thực bị hạn chế. Điều này đạt được bằng cách tách khối thành công khỏi tính toán thực tế và bằng cách hash trước dưới mục tiêu T1. Đặc biệt, theo mô hình tiêu chuẩn trong [ GKL14 , PSS16], và giả định rằng đối thủ không có lợi thế trong việc tính toán Mnhanh hơn so với các bên trung thực, giao thức sẽ cho phép đối thủ kiểm soát bất kỳ thiểu số sức mạnh tính toán nào dành riêng cho mạng - Bitcoin cũng vậy. Ngược lại, ngay cả khi đối thủ có thể tính toán Mmiễn phí trong mọi trường hợp, giao thức vẫn cho phép đối thủ kiểm soát tới một phần ba tổng số tài nguyên tính toán - vì chúng vẫn hoạt động với chi phí bằng 'một nửa' do trước -bạch chống T1 .
• Độ khó thay đổi : Trong các giao thức đồng thuận PoW / PoUW, độ khó để tìm một khối phải được điều chỉnh liên tục cho phù hợp với mức sức mạnh tính toán hiện tại dành riêng cho hệ thống. Trong Ofelimos, điều này dễ dàng đạt được bằng cách điều chỉnh mục tiêu T2 cho (đơn) Hậu hashing được thực hiện sau bước tính toán - đủ điều kiện để xuất bản khối xếp hạng.

Hiệu quả :

• Cập nhật thường xuyên : Sự tách biệt giữa khối xếp hạng và khối đầu vào đảm bảo rằng các cập nhật trạng thái được phổ biến nhanh chóng.
• Tính hữu ích : Theo tính hữu ích, chúng tôi xác định tỷ lệ của công việc tính toán tổng thể được chi cho vấn đề SLS (đây là một sự đơn giản hóa - một định nghĩa cẩn thận hơn và phân tích, có thể được tìm thấy trong bài báo này). Các nguồn chính của công việc 'vô ích' trong hệ thống là tiền hash lặp đi lặp lại đối với T1 và tính toán SNARG. Lưu ý rằng:
• Hậu hashing chỉ được thực hiện một lần cho mỗi lần gọi Mvà so với độ phức tạp của M, có thể bị bỏ qua vì những lý do thực tế.
• SNARG chỉ phải được tính toán đối với hai trong số nhiều lệnh gọi M, lệnh cho kết quả T (ngụ ý khối thành công) và tốt nhất (giải pháp tốt nhất). Do đó, chi phí gây ra bởi việc tính toán SNARGs có thể được giảm thiểu bằng cách hạ thấp ngưỡng T3 quyết định sự thành công của khối - để đánh đổi với các cập nhật trạng thái chậm hơn.

Mức độ hữu dụng phụ thuộc vào các đặc tính của M. Nếu thời gian chạy của Mđược tập trung đủ, độ cứng tiền hash (pre-hash) có thể được đặt gần với độ phức tạp trường hợp trung bình của M. Xem xét các quan sát trên, độ hữu dụng của khoảng ½ đạt được là người khai thác dành khoảng một nửa thời gian của họ để tính toán M. Nhiều vấn đề SLS cổ điển dường như thuộc loại này. Tuy nhiên, nếu M không được 'cư xử tốt', tính hữu dụng có thể gần bằng không. Do đó, việc lựa chọn các thuật toán SLS cụ thể và các bước tính toán M của chúng là rất quan trọng để đạt được PoUW với mức độ hữu ích hợp lý.

Kết luận

Ofelimos chỉ là bước đầu tiên hướng tới PoUW an toàn và hữu ích. Trong khi công việc hiện tại dễ dàng cung cấp khả năng bảo mật có thể chứng minh được đối với các mức độ tham nhũng cao, thì vẫn cần nghiên cứu thêm về mặt thuật toán để cung cấp các lớp vấn đề tối ưu hóa phù hợp mà tính hữu ích cao có thể được chứng minh một cách rõ ràng.

Bài báo nghiên cứu ' Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work' được xuất bản lần đầu tiên vào tháng 10 năm 2021.

Chân thành cảm ơn Matthias Fitzi vì những ý kiến ​​đóng góp và hỗ trợ của anh ấy trong việc chuẩn bị bài đăng trên blog này.

Nguồn bài viết tại đây

---

---

Đọc thêm các bài viết liên quan tại thẻ Tags bên dưới