Đồ thị có hướng không chu trình (DAG) là gì?

Đồ thị có hướng không chu trình (DAG) là một cấu trúc dữ liệu khác biệt, có thể coi như một cơ sở dữ liệu kết nối các thông tin khác nhau. Khái niệm "đồ thị có hướng không chu trình" chứa nhiều thông tin, hãy cùng phân tích từng lớp một.

Về mặt khái niệm, DAG tương tự như hình trên, bao gồm các đỉnh (hình cầu) và cạnh (đường nối). Cả hai đều có hướng, tức là chỉ theo một chiều (như mũi tên), và không có chu trình, nghĩa là không có vòng lặp—các đỉnh không quay lại điểm xuất phát ban đầu. Nói cách khác, nếu bắt đầu từ một điểm và đi theo đồ thị, ta không thể quay lại điểm xuất phát. Chúng ta sẽ tiếp tục giải thích chi tiết sau.

Cấu trúc dữ liệu này thường được sử dụng để mô hình hóa dữ liệu. Trong lĩnh vực khoa học hoặc y tế, DAG được dùng để quan sát mối quan hệ giữa các biến và xác định tác động lẫn nhau của chúng. Ví dụ, chúng ta có thể sử dụng đồ thị này để thiết lập mối liên hệ giữa dinh dưỡng, chu kỳ giấc ngủ và các triệu chứng cơ thể, từ đó xác định ảnh hưởng của các yếu tố này lên bệnh nhân.

Chúng ta tập trung hơn vào cách sử dụng đồ thị này để đạt được sự đồng thuận trong mạng lưới tiền mã hóa phân tán.

DAG hoạt động như thế nào?

Trong tiền mã hóa dựa trên DAG, mỗi đỉnh trong cấu trúc đại diện cho một giao dịch. Không có khái niệm khối (block) hay việc đào (mining) cần thiết để mở rộng cơ sở dữ liệu. Thay vì nhóm giao dịch vào các khối, giao dịch được xây dựng trên các giao dịch khác. Khi một nút (node) gửi giao dịch, vẫn có một lượng nhỏ công việc bằng chứng (proof-of-work) được thực hiện để đảm bảo mạng không bị spam đồng thời xác minh các giao dịch trước đó.

Để thêm giao dịch mới, nó phải được xây dựng trên các giao dịch trước đó. Giả sử Alice tạo một giao dịch mới. Giao dịch này muốn được xác nhận phải tham chiếu đến các giao dịch trước đó—tương tự như một khối Bitcoin tham chiếu đến khối trước đó, nhưng ở đây phải tham chiếu nhiều giao dịch.

Trong một số hệ thống, thuật toán sẽ chọn các giao dịch (hoặc "đỉnh cuối") mà giao dịch mới phải xây dựng lên. Đỉnh cuối có trọng số tích lũy càng cao thì càng dễ được chọn. Trọng số tích lũy đo lường số lượng xác nhận trên đường dẫn đến đỉnh cuối.

Các giao dịch mà Alice sắp xây dựng lên chưa được xác nhận. Tuy nhiên, một khi Alice tham chiếu đến chúng, chúng sẽ được xác nhận. Giao dịch hiện tại của Alice chưa được xác nhận, vì vậy người khác phải xây dựng giao dịch trên đó trước khi nó được chấp nhận.

Người dùng thích xác nhận các giao dịch có trọng số "cao" hơn để hệ thống tiếp tục phát triển. Nếu không, người dùng có thể thoải mái xây dựng giao dịch trên các giao dịch cũ.

Blockchain dễ dàng ngăn chặn vấn đề chi tiêu đôi (double-spending). Cùng một khoản tiền không thể được sử dụng hai lần trong một khối, và các nút có thể dễ dàng phát hiện nỗ lực này, từ chối mọi khối chứa giao dịch xung đột. Việc đào khối rất tốn kém, nên cơ chế này khuyến khích thợ đào cạnh tranh công bằng.

DAG cũng có thể ngăn chặn chi tiêu đôi bằng cơ chế tương tự nhưng không có thợ đào. Khi xác nhận giao dịch cũ, các nút sẽ đánh giá toàn bộ đường dẫn trở lại giao dịch đầu tiên trong DAG để đảm bảo người gửi có đủ số dư. Có thể có nhiều đường dẫn, nhưng chỉ cần xác minh một đường là đủ.

Nếu người dùng xây dựng giao dịch trên đường dẫn không hợp lệ, giao dịch của họ sẽ bị bỏ qua. Dù giao dịch của họ có hợp lệ, nhưng vì giao dịch trước đó không hợp lệ, nên không ai muốn mở rộng đường dẫn này.

Thoạt nhìn có vẻ không trực quan—liệu có trường hợp các nhánh khác nhau không biết đến sự tồn tại của nhau không? Người dùng có thể chi tiêu cùng một khoản tiền trên các nhánh khác nhau không?

Điều này hoàn toàn có thể xảy ra. Nhưng bằng cách sử dụng thuật toán chọn đỉnh cuối dựa trên trọng số tích lũy, vấn đề này được giải quyết. Theo thời gian, một nhánh sẽ phát triển mạnh hơn các nhánh khác. Các nhánh yếu hơn bị bỏ rơi, và mạng tiếp tục phát triển trên nhánh có trọng số cao nhất.

Giống như blockchain, mạng này không có xác nhận tuyệt đối—chúng ta không bao giờ hoàn toàn chắc chắn rằng giao dịch sẽ không bị đảo ngược. Dù khả năng cực thấp, nhưng về lý thuyết, các khối Bitcoin hoặc Ethereum có thể bị "hoàn tác", dẫn đến đảo ngược tất cả giao dịch trong đó. Càng nhiều khối được thêm sau giao dịch, giao dịch đó càng an toàn. Đó là lý do người dùng được khuyên đợi sáu lần xác nhận trước khi cam kết tiền.

Trong các DAG như IOTA Tangle, có một khái niệm gọi là "độ tin cậy xác nhận". Thuật toán chọn chạy 100 lần, tính toán số lần giao dịch được phê duyệt trực tiếp hoặc gián tiếp bởi các đỉnh cuối được chọn. Tỷ lệ phần trăm càng cao, độ tin cậy rằng giao dịch vẫn ở trạng thái "đã thanh toán" càng lớn.

Điều này có vẻ làm trải nghiệm người dùng kém đi. Nhưng thực tế không phải vậy. Nếu Alice gửi cho Bob 10 MagicDAGToken, cô ấy không cần lo lắng về việc chọn đúng đỉnh cuối trong đồ thị vì ví của cô ấy sẽ tự động thực hiện các bước sau:

1. Chọn các đỉnh cuối có trọng số cao (nhớ rằng, đó là những đỉnh có nhiều xác nhận tích lũy nhất).

2. Truy ngược đường dẫn về các giao dịch trước đó để đảm bảo đỉnh cuối có đủ số dư để thanh toán.

3. Khi đạt các yêu cầu trên, giao dịch sẽ được thêm vào DAG và được xác nhận.
   Đối với Alice, đây chỉ là quy trình hoạt động thông thường của tiền mã hóa. Cô ấy nhập địa chỉ của Bob và số tiền muốn gửi, sau đó nhấn "Gửi". Danh sách trên là công việc bằng chứng mà mỗi người tham gia thực hiện khi tạo giao dịch.
   Ưu và nhược điểm của DAG
   Ưu điểm của DAG
   Tốc độ
   Không có giới hạn thời gian tạo khối—bất kỳ ai cũng có thể công bố và xử lý giao dịch bất cứ lúc nào. Miễn là các giao dịch trước đó được xác nhận trước, người dùng không bị giới hạn số lần gửi giao dịch.

Không cần đào

DAG không sử dụng thuật toán đồng thuận bằng chứng công việc (proof-of-work) truyền thống. So với tiền mã hóa dựa vào đào để duy trì mạng blockchain, DAG có lượng khí thải carbon chỉ bằng một phần nhỏ.

Không phí giao dịch

Vì không có thợ đào, người dùng không phải trả phí để công bố giao dịch, mặc dù một số hệ thống có thể tính phí nhỏ cho một số loại nút. Phí thấp (hoặc miễn phí) rất hấp dẫn đối với giao dịch vi mô, nơi phí mạng cao sẽ làm mất giá trị.

Không có vấn đề mở rộng

Không giống như blockchain truyền thống, DAG không bị giới hạn bởi thời gian tạo khối, cho phép xử lý nhiều giao dịch hơn mỗi giây. Nhiều người ủng hộ tin rằng điều này làm cho DAG có giá trị cao trong các trường hợp sử dụng IoT liên quan đến tương tác máy-máy.

Nhược điểm của DAG

Không hoàn toàn phi tập trung

Các giao thức dựa trên DAG thường có tính năng tập trung. Một số cho rằng đây là giải pháp ngắn hạn để khởi động mạng, nhưng vẫn cần xem liệu DAG có thể phát triển mạnh mà không cần can thiệp của bên thứ ba hay không. Nếu không, mạng có thể dễ bị tấn công và tổn thất nghiêm trọng.

Chưa được kiểm tra quy mô lớn

Mặc dù tiền mã hóa dựa trên DAG đã xuất hiện vài năm, nhưng việc áp dụng rộng rãi sẽ cần thêm thời gian. Do đó, rất khó để dự đoán động lực nào sẽ thúc đẩy người dùng sử dụng hệ thống này trong tương lai.

Kết luận

Không nghi ngờ gì, DAG là một công nghệ thú vị để xây dựng mạng tiền mã hóa. Cho đến nay, rất ít dự án sử dụng cấu trúc dữ liệu này, và nó vẫn chưa phát triển đầy đủ.

Tuy nhiên, nếu DAG phát huy tiềm năng, chúng chắc chắn có thể cung cấp năng lượng cho nhiều hệ sinh thái mở rộng. Với thông lượng cao và miễn phí, DAG có vô số trường hợp sử dụng, chẳng hạn như IoT và giao dịch vi mô.