Tìm hiểu Cây cú pháp trừu tượng Bitcoin Merkelized là gì?
Tiêu đề gốc: "Hàng khô | Cây cú pháp trừu tượng Bitcoin Merkelization là gì? ", của David A. Harding
Merklized Abstract Syntax Trees (MAST) là một bản nâng cấp được đề xuất cho Bitcoin cho phép quy mô giao dịch nhỏ hơn, quyền riêng tư tốt hơn và hợp đồng thông minh lớn hơn. Trong bài viết này, chúng tôi giải thích cơ sở lý luận cho MAST, giải thích các lợi ích tiềm năng của nó và tóm tắt một số đề xuất hiện tại kết hợp công nghệ này.
Sự cố: Dữ liệu tập lệnh không được sử dụng
Satoshi Nakamoto đã mang đến cho Bitcoin một tính năng thú vị mà ông không viết trong sách trắng Bitcoin. Ngoài việc nhận bitcoin thông qua khóa công khai và tiêu bitcoin bằng chữ ký số khóa riêng, người dùng cũng có thể viết chương trình (được gọi là "tập lệnh") có thể được sử dụng làm chữ ký và khóa công khai động.
Khi bạn chỉ định một tập lệnh -- vốn là hoạt động cơ bản trong mọi ví Bitcoin -- giao thức Bitcoin, được thực thi bởi mạng Bitcoin, sẽ không cho phép bất kỳ ai chi tiêu Bitcoin do tập lệnh kiểm soát trừ khi tập lệnh Trả về Đúng. Điều này cho phép bạn chỉ định các điều kiện theo đó tiền có thể được chi tiêu, được gọi là "điều kiện ràng buộc" (điều kiện tài sản), chẳng hạn như yêu cầu các giao dịch được chi tiêu phải được ký bằng khóa riêng của bạn.
Các điều kiện tài sản phức tạp hơn cũng có thể xảy ra, chẳng hạn như ví dụ sau, mà chúng tôi sẽ sử dụng trong suốt bài viết này: Alice muốn có thể chi tiêu bitcoin của mình bất cứ lúc nào, nhưng nếu cô ấy không chi tiêu bitcoin của mình trong ba tháng liên tiếp (có thể chết hoặc mất năng lực), cô ấy muốn anh chị em của mình, Bob và Charlie, sở hữu bitcoin của họ và sử dụng chúng ở bất cứ nơi nào họ có thể đồng ý.
Kịch bản điều kiện sau đây đạt được mục tiêu trên, nó không chỉ bao gồm khóa chung của Alice (cần xác minh chữ ký từ khóa riêng của cô ấy) mà còn thêm logic điều kiện sau: điều kiện hết thời gian chờ và khóa chung của Bob và Charlie.
Trong giao thức Bitcoin hiện tại, tất cả dữ liệu nêu trên phải được thêm vào chuỗi khối và khi Bitcoin của Alice được chi tiêu, nó cũng bao gồm các phần của tập lệnh hoàn toàn không liên quan đến hành vi chi tiêu cụ thể, cũng phải được tiết lộ. Ví dụ: khi Alice tiêu số bitcoin của mình, khóa công khai của Bob và Charlie cũng sẽ bị lộ.
Dữ liệu có điều kiện không được sử dụng làm tăng quy mô giao dịch và khiến người dùng có nhiều quyền riêng tư hơn mức cần thiết. MAST nhằm mục đích cải thiện những tình huống này bằng cách loại bỏ nhu cầu bao gồm các phần không sử dụng của tập lệnh trực tiếp trên chuỗi khối.
MAST ý tưởng ban đầu
Ý tưởng đằng sau MAST 1 đến từ hai khái niệm lâu đời, cây ngữ nghĩa trừu tượng và cây Merkle. Cây ngữ nghĩa trừu tượng (AST) là một cách để mô tả chương trình bằng cách chia chương trình thành các phần nhỏ độc lập, giúp chương trình dễ phân tích và tối ưu hóa hơn. Để tạo AST, bạn cần kết nối tất cả các phương trình với các tiền đề của chúng bằng mũi tên cho đến khi tìm thấy tất cả các tiền đề. Hình bên dưới là AST của tập lệnh mẫu ở trên.
Mặt khác, cây Merkle có thể được sử dụng để xác minh xem một phần tử có thuộc tập hợp hay không mà không cần biết bức tranh đầy đủ về tập hợp đó. Ví dụ: Ví xác minh thanh toán đơn giản của Bitcoin (ví SPV) sử dụng cây Merkle để xác minh xem một giao dịch nhất định có tồn tại trong một khối nhất định hay không, do đó không cần tải xuống toàn bộ khối, điều này có thể tiết kiệm băng thông.
Để tạo cây Merkle, trước tiên hãy băm mỗi phần tử một lần để tạo mã định danh duy nhất của riêng nó; sau đó các mã định danh này được ghép nối và băm lại để tạo mã định danh của cặp mã định danh; và cứ thế Lặp lại cho đến khi chỉ còn một mã định danh duy nhất, được gọi là "Merkel root", là một mã định danh ngắn đánh dấu toàn bộ bộ sưu tập.
Khi xác minh rằng một phần tử thuộc về một tập hợp, người nào đó sở hữu toàn bộ tập hợp có thể cung cấp cho bạn tất cả các mã định danh trên đường dẫn từ phần tử đó đến gốc Merkle. Điều này chứng tỏ rằng phần tử thực sự nằm trong tập hợp.
Nói tóm lại, công nghệ đằng sau AST cho phép bạn chia chương trình thành các phần nhỏ và cây Merkle cho phép chúng tôi xác minh rằng các phần nhỏ này thực sự là một phần của chương trình hoàn chỉnh mà không để lộ toàn bộ chương trình. Đây là nguyên tắc cơ bản của MAST, cho phép người tiêu dùng thay thế các điều kiện không được sử dụng trong một giao dịch đơn lẻ bằng bằng chứng Merkle - giảm quy mô giao dịch, cải thiện quyền riêng tư và hỗ trợ các hợp đồng lớn hơn.
Một ví dụ về MAST
Hãy lấy điều kiện thuộc tính ở trên làm ví dụ và chia nó thành hai chỉ số con cho hai tình huống có thể xảy ra mà chúng ta muốn:
Alice có thể tiêu bitcoin của mình bất cứ lúc nào (chỉ số bên trái)
Hoặc, nếu chữ ký của Alice được sử dụng để chi tiêu trong ba tháng liên tiếp, chữ ký của Bob và Charlie được yêu cầu để chi tiêu bitcoin (chỉ số bên phải trong hình bên dưới)
Tạo cây Merkle dựa trên hai chỉ số riêng biệt sau:
Gốc của cây Merkle này cuối cùng xác định các điều kiện thuộc tính đầy đủ của Alice và nó chỉ có kích thước 32 byte. Sau đó, Alice có thể sử dụng một tập lệnh có điều kiện thay thế, nói rằng một giao dịch chi tiêu chỉ hợp lệ nếu một trong các chỉ số con được cung cấp bằng chứng rằng nó được kết nối với gốc Merkle và chương trình con trả về True.
Bằng chứng Merkle của chỉ số dưới sẽ được vẽ trực quan như hình dưới đây, tùy thuộc vào chỉ số nào được sử dụng:
Lợi ích #1 - Giao dịch nhỏ hơn
Trước tiên, hãy xem cách MAST cho phép người dùng có điều kiện tài sản phức tạp tạo các giao dịch nhỏ hơn. Đây là lợi ích đầu tiên mà MAST mang lại cho chúng tôi.
Trong ví dụ trên, chúng tôi đã sử dụng một thanh thuộc tính có hai chỉ số phụ: Alice tiêu tiền của chính mình hoặc Bob và Charlie tiêu tiền của cô ấy cùng nhau sau ba tháng chờ đợi. Hãy tưởng tượng một phiên bản kéo dài vô tận trong đó chỉ số thứ ba xác định rằng sau ba tháng và một ngày, Dan và Edith có thể tiêu tiền; chỉ số thứ tư chỉ định rằng sau ba tháng và hai ngày, Fred và George có thể sử dụng số tiền này; v.v., v.v. .
Thử nghiệm suy nghĩ này dẫn chúng ta đến biểu đồ bên dưới, biểu thị mối quan hệ giữa số lượng chỉ số và lượng dữ liệu có điều kiện cần được thêm vào một khối, có và không có MAST.
Đây là một biểu đồ logarit, có nghĩa giống nhau:
Mặc dù kích thước của giao dịch MAST sẽ lớn hơn giao dịch có cùng điều kiện mà không có MAST ngay từ đầu, chẳng hạn như điều kiện của hai tập lệnh con của chúng tôi, nhưng kích thước giao dịch không phải MAST sẽ tăng tuyến tính (với số lượng tập lệnh phụ) , trong khi khối lượng giao dịch MAST sẽ chỉ tăng theo logarit.
Nếu tiết kiệm khối lượng dữ liệu là mục tiêu chính, chúng tôi có thể tối ưu hóa hơn nữa. Đối với nhiều điều kiện tài sản, người tiêu dùng có thể sử dụng một trong số chúng thường xuyên hơn. Ví dụ, Alice muốn sống lâu, vì vậy cây Merkle mà cô ấy xây dựng sẽ đặt các điều kiện chi tiêu của cô ấy gần đỉnh hơn và tất cả các điều kiện khác được đặt ở dưới cùng của cây:
Có thể thấy rằng khi Alice sử dụng tiền, lượng dữ liệu giao dịch luôn là tình huống tối ưu, bất kể có bao nhiêu người thụ hưởng trong điều kiện tài sản của cô ấy; và khi người thụ hưởng của cô ấy sử dụng tiền, lượng dữ liệu giao dịch cũng là giống nhau Chỉ nhiều hơn một vài byte so với cây Merkle được xây dựng tiêu chuẩn đã nói ở trên.
Bất kể Alice chọn cách sắp xếp nào, có thể thấy rằng MAST có thể làm cho các giao dịch có điều kiện thuộc tính nhiều đăng ký trở nên nhỏ hơn, do đó người dùng có thể trả ít phí hơn và các giao dịch nâng cao hơn có thể được tải vào các khối.
Lợi ích #2 - Quyền riêng tư cao hơn
Trong phần giải thích ở trên, chúng tôi đã tiết lộ tất cả các tập lệnh thuộc tính của Alice, nhưng bạn có thể tưởng tượng rằng nếu Alice sử dụng bitcoin của chính mình, bạn chỉ thấy dữ liệu ở phía bên trái của hình bên dưới trên chuỗi khối:
Chỉ với thông tin này, bạn không có cách nào để biết liệu có ai khác ngoài Alice có thể chi tiêu tiền ở đây hay không và họ phải đối mặt với những hạn chế nào khi chi tiêu. Bạn có thể đoán từ MAST rằng có thể có một số điều kiện khác, nhưng đó chỉ là phỏng đoán - Alice có thể chỉ giả vờ rằng cây Merkle của cô ấy có các bộ phận khác có thể sử dụng được.
Tương ứng, nếu bạn thấy một nhánh khác (nghĩa là tập lệnh phụ bên phải trong hình trên), bạn sẽ không biết liệu có thể chi tiêu tiền trước khi hết thời gian hay không và bạn sẽ không biết liệu có thể chi tiêu với chỉ có một khóa cá nhân. có thể chi tiêu nó. Bạn cũng có thể đoán rằng có các điều kiện chi tiêu khác, nhưng bạn không thể xác nhận điều này trên blockchain.
Ví dụ: một số thương nhân có thể muốn hợp đồng thông minh của họ được bảo mật nhất có thể và không bị các đối thủ tiềm năng nhìn thấy. Điều này trái ngược với một số altcoin tuyên bố được thiết kế cho các hợp đồng thông minh, nhưng thực tế không thể cung cấp quyền riêng tư cho các hợp đồng này.
Quyền riêng tư cũng có thể mang lại lợi ích bổ sung cho tất cả người dùng Bitcoin, ngay cả khi một số người dùng chỉ đơn giản là không quan tâm đến quyền riêng tư về mặt tài sản. Giả sử rằng từ đầu bài viết này, Alice là người duy nhất sử dụng mẫu có điều kiện không phải MAST. Bởi vì tất cả các điều kiện đều được công khai, bất kỳ ai cũng có thể theo dõi hành vi chi tiêu của Alice, chỉ cần quan sát việc sử dụng mẫu này trên chuỗi khối, vì vậy quyền riêng tư của Alice không còn nữa.
Bất kỳ thiết kế nào giúp xác định một người dùng cụ thể dễ dàng hơn cũng sẽ giúp mọi người dễ dàng đối xử khác biệt với bitcoin của họ với bitcoin của người khác, điều này được gọi là "thiếu đồng nhất". Nếu ai đó biết điều kiện tài sản của Alice trông như thế nào, họ có thể hối lộ hoặc buộc những người khai thác không đóng gói các giao dịch của những người này, để ngăn Alice sử dụng bitcoin của chính cô ấy.
MAST không thể giải quyết hoàn toàn vấn đề này, bởi vì Alice (hoặc Bob và Charlie) vẫn cần tiết lộ một số cản trở, nhưng nhiều điều kiện thuộc tính phức tạp khác có thể được giải quyết thành một số lượng nhỏ các điều kiện kiểu MAST đơn giản.
Ví dụ: hành vi chi tiêu mặc định của Alice trông giống như bất kỳ hành vi thanh toán thông thường nào khác chỉ cần cung cấp một chữ ký duy nhất, vì vậy giao dịch dựa trên MAST của Alice không khác với các giao dịch dựa trên chữ ký duy nhất dựa trên MAST khác. Điều này lần lượt cải thiện quyền riêng tư của Alice, cũng như tính đồng nhất của tiền của cô ấy và tính đồng nhất về tiền tệ cho tất cả người dùng sử dụng các điều kiện chữ ký đơn dựa trên MAST.
Lợi ích này của MAST cũng có khả năng được kết hợp với các đề xuất khác để cải thiện tính riêng tư và tính đồng nhất của Bitcoin. Có những đề xuất để cung cấp một số điều kiện thuộc tính phức tạp nhất định với một chữ ký duy nhất, chẳng hạn như "Cây ngưỡng phổ quát" của Pieter Wuille và Gregory Maxwell, "Tập lệnh không có chữ viết" của Andrew Poelstra và "Hợp đồng logarit rời rạc" của Thaddeus Dryja; MAST có thể được kết hợp với những điều kiện này đề án.
Nhưng ngay cả khi không có giải pháp nào trong số này có thể được triển khai trên Bitcoin, bản thân MAST có thể cung cấp nhiều quyền riêng tư hơn và khả năng hoán đổi cho người dùng với các điều kiện tài sản phức tạp, cho dù nó được so sánh với giải pháp hiện tại hay với sự hỗ trợ cho các Altcoin hợp đồng thông minh do người dùng xác định so với.
Lợi ích #3 - Hợp đồng thông minh lớn hơn
Bitcoin hiện đặt ba giới hạn kích thước khác nhau cho các tập lệnh riêng lẻ: tập lệnh trần không thể vượt quá kích thước 10.000 byte, được giới thiệu vào tháng 7 năm 2010; tập lệnh P2SH không thể vượt quá 520 byte; và tập lệnh segwit không thể vượt quá 10.000 byte. Chúng tôi hiển thị các kích thước này trong hình trên:
Có thể thấy rằng ngay cả đối với trường hợp mở rộng vô hạn cực đoan, MAST hỗ trợ nhiều nhánh có điều kiện hơn tất cả các cơ chế hiện tại. Trên thực tế, MAST chia tỷ lệ tốt đến mức ngay cả khi bạn có tất cả năng lượng trong vũ trụ có thể quan sát được, nếu bạn chỉ sử dụng nó để tạo một cây Merkle tiêu chuẩn (cân bằng), bằng chứng Merkle của nó chỉ là 8448 byte. Ngay cả đối với bằng chứng Merkle lớn như vậy, bất kỳ máy tính xách tay hiện đại nào cũng có thể xác minh nó trong vòng chưa đầy 1 phần nghìn giây.
MAST cũng có thể giúp Bitcoin Script bỏ qua một số hạn chế cứng khác bằng cách giải phóng các nút đầy đủ khỏi nhiệm vụ xử lý các đăng ký không sử dụng. Về vấn đề này, MAST đã bảo tồn tốt và mở rộng mục tiêu thiết kế dài hạn của hợp đồng thông minh Bitcoin, nghĩa là gánh nặng của hợp đồng sẽ do những người tham gia hợp đồng gánh chịu càng nhiều càng tốt, trong khi các nút trả tiền cho băng thông, bộ nhớ và sức mạnh xử lý, nhưng không thể được đền bù và do đó phải chịu trách nhiệm càng ít càng tốt.
Vì vậy, thành tựu thực sự của MAST không phải là cho phép người dùng Bitcoin tạo ra (hơn bao giờ hết) các hợp đồng nâng cao hơn, mà nó mở ra khả năng này mà không tạo thêm gánh nặng mới cho các nút Bitcoin.
Triển khai MAST: Nhiều đề xuất hiện có
Cho đến nay, hai phương pháp kích hoạt MAST trong giao thức Bitcoin đã được đề xuất trong danh sách gửi thư của nhà phát triển bitcoin, cả hai phương pháp này vẫn đang trong giai đoạn dự thảo và có thể thay đổi.
Đề xuất đầu tiên là BIP114 do Johnson Lau (bút danh "jl2012") đề xuất, sử dụng tính năng mở rộng dựa trên nhân chứng tách biệt, để địa chỉ ban đầu của nhân chứng tách biệt (bech32) có thể trở thành cam kết gốc Merkle đối với các điều kiện tài sản MAST. Do đó, một giao dịch chi tiêu có thể chọn một tập lệnh con từ cây.
Đề xuất thứ hai, hai BIP không tên (1, 2) của Mark Friedenbach (bí danh "maaku"), làm tăng tính linh hoạt của ngôn ngữ kịch bản, cho phép các lập trình viên viết các tập lệnh để xác minh các điều kiện thuộc tính dựa trên MAST. Đã triển khai theo cách mà Friedenbach ưa thích, điều đó sẽ cung cấp bằng chứng Merkle cho cả ba loại tập lệnh mà Bitcoin hiện đang hỗ trợ (tập lệnh trần trụi, P2SH và tập lệnh Segregated Witness).
Một số đề xuất này có những ưu điểm và nhược điểm riêng, nhưng tất cả đều mang lại lợi ích của MAST đã đề cập ở trên (số lượng byte có thể tăng hoặc giảm). Mỗi cái có thể được kích hoạt bằng một soft fork.
Kết luận: Khi nào chúng ta có thể sử dụng MAST?
Ở trên, chúng tôi đã giải thích các lợi ích của MAST và đề cập ngắn gọn hai đề xuất để triển khai MAST trên Bitcoin. Bạn cũng có thể tò mò về thời điểm chúng tôi có thể sử dụng MAST. Đáng buồn thay, tôi cũng không biết.
Từ ý tưởng, đề xuất, hoàn thành triển khai, đề xuất ngã ba mềm, đến kích hoạt ngã ba mềm, con đường dài và khó khăn. Điều này đã được thể hiện rõ ràng qua bộ phim truyền hình kéo dài hai năm xung quanh việc nâng cấp Segregated Witness.
Nhưng theo quan điểm của tôi, ý tưởng cơ bản đằng sau MAST đã nhận được sự ủng hộ rộng rãi trong cộng đồng công nghệ Bitcoin và các nhà phát triển quan tâm nhất đến MAST sẽ tiếp tục phát triển nó trừ khi ai đó có thể chứng minh rằng công nghệ này hoàn toàn không đáng tin cậy. Khi các nhà phát triển này đề xuất thành công một mã soft fork có thể đánh giá ngang hàng, độc giả của bạn và những người dùng Bitcoin khác sẽ quyết định liệu MAST có thể trở thành một phần của giao thức Bitcoin hay không.
Cảm ơn
BIP114: Merklized Abstract Syntax Tree by Johnson Lau
Tail Call Sematics by Mark Friedenbach
MerkleBranchVerify opcode by Mark Friedenbach
Discussion at core.tech meetup by Mark Friedenbach (transcribed by Bryan Bishop)
Merklized Abstract Syntax Trees by Jeremy Rubin, Manali Naik, Nitya Subramanian
An explanation and justification of the tail-call and MBV approach to MAST by Mark Friedenbach
Making MAST Meaningful by Brian Deery
The next step to improve Bitcoin by Aaron van Wirdum
Cảm ơn
chú thích cuối trang
chú thích cuối trang
Russell O'Connor được ghi nhận là người đầu tiên mô tả nguyên mẫu của MAST, và một số nguồn bổ sung thêm Pieter Wuille. Nguồn: Peter Todd, Gregory Maxwell (được trích dẫn trong Jeremy Rubin và cộng sự), và Mark Friedenbach (trong giao tiếp cá nhân).
Cảm ơn John Newbery.
Liên kết gốc:
(qua)
(Có nhiều siêu liên kết trong bài viết này, bạn có thể nhấp vào "Đọc văn bản gốc" ở phía dưới bên trái để lấy từ trang web EthFans)
Liên kết gốc:
https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f
Bản dịch: A Jian
Bản dịch: A Jian
