Chia sẻ công nghệ: Phân loại dag khối an toàn và công bằng

lời tựa

lời tựa

Trong bài viết trước, chúng ta đã thấy rằng vấn đề có thể phát sinh trong cấu trúc liên kết DAG là xác định thứ tự của các khối và chuyển giao. Trong bài đăng này, chúng tôi mô tả cơ chế của Taraxa không chỉ đảm bảo đặt hàng trong Block DAG mà còn đảm bảo rằng quy trình đặt hàng diễn ra an toàn và công bằng.

Tại sao sắp xếp là thách thức?

Việc sắp xếp trong Block DAG có gì khó khăn?

Nếu chỉ nhìn vào bất kỳ cấu trúc dữ liệu DAG nào, chúng ta chỉ có thể thiết lập thứ tự từng phần, nghĩa là chúng ta chỉ có thể xác định mối quan hệ thứ tự giữa một số khối chứ không phải tất cả các khối. Đây là một ví dụ.

Trong hình trên, chúng ta có thể khẳng định chắc chắn 100% rằng khối màu xanh lam chắc chắn xuất hiện trước khối màu xanh lá cây và màu cam. Tại sao? Vì các khối màu xanh lá cây và màu cam trỏ đến khối màu xanh lam, nghĩa là khi các khối màu cam và xanh lá cây được tạo ra thì khối màu xanh lam đã tồn tại, nếu không thì các khối màu cam và xanh lá cây không biết chúng sẽ trỏ đến nó.

Nhưng, làm thế nào chúng ta có thể biết mối quan hệ thứ tự giữa các khối màu xanh lá cây và màu cam? Không có câu trả lời dứt khoát cho câu hỏi này, câu trả lời phụ thuộc vào loại thuật toán sắp xếp được sử dụng và thứ tự có thể hoàn toàn khác đối với các thuật toán khác nhau.

Trong quá trình xếp hạng, chúng tôi không chỉ phải giữ lại một bậc tự do mà còn phải đưa ra nhiều lựa chọn để đảm bảo rằng thuật toán xếp hạng vừa công bằng vừa an toàn, bởi vì cần đảm bảo rằng những người tham gia không trung thực không thiên vị đa số của những người tham gia mạng trung thực hoặc tấn công.

Bây giờ chúng ta hãy xem thuật toán sắp xếp của Block DAG do Taraxa thiết kế để xem chúng ta có thể giải quyết những vấn đề này như thế nào.

cuộc thi phổ biến

Trong cấu trúc liên kết DAG khối của Taraxa, mỗi khối bao gồm các con trỏ lùi không chỉ trỏ đến một khối chính duy nhất (như trong cấu trúc liên kết chuỗi đơn), mà còn trỏ đến những gì người đề xuất khối đã thấy và tin tưởng Tất cả các khối trên ranh giới DAG (cạnh) . Có rất nhiều khái niệm ở đây, hãy giải nén từng cái một.

ranh giới là gì? Trong một Khối DAG (hoặc bất kỳ cấu trúc dữ liệu DAG nào), một đường biên đề cập đến tập hợp các khối mới nhất mà không có khối nào khác trỏ đến.

Trong hình trên, khối màu xanh lam là khối "ranh giới", trong khi các khối còn lại thì không. Các chuỗi khối biên giới rất thú vị vì các khối này là cơ sở của tất cả các khối và các khối khác được tạo bởi những người đề xuất khối (tương tự như những người tạo khối) được sắp xếp theo sau chúng. Từ một quan điểm nhất định, khối mới tiếp theo chắc chắn sẽ đề cập đến các khối này. Tuy nhiên, không phải mọi nút sẽ nhìn thấy cùng một ranh giới (hoặc cùng một Khối DAG) vì mỗi nút trải qua độ trễ lan truyền mạng khác nhau và thấy một tình huống hoàn toàn khác khi gặp bất kỳ khối cụ thể nào. Do đó, những người đề xuất khối có thể đặt khối của họ dựa trên các ranh giới khác nhau tại bất kỳ thời điểm nào.

Con trỏ hoặc khối cha là gì? Con trỏ, được biểu thị bằng mũi tên trong sơ đồ, là dữ liệu được nhúng trong một khối "trỏ" hoặc tham chiếu khối khác. Trong cấu trúc khối DAG của Taraxa, con trỏ sẽ trỏ đến tập hợp khối chính. Khối cha là khối được con trỏ trỏ tới nên có thể hiểu là khối cha của khối trước đó của chúng.

Trong hình trên, chúng ta thấy rằng khối màu xanh lam có hai con trỏ tới hai khối cha được đại diện bởi các khối màu xanh lá cây. Điều này có nghĩa là khi người đề xuất tạo một khối màu xanh lam, người đề xuất biết hai (2) khối trên ranh giới DAG của Khối và coi hai khối này là hợp lệ, do đó, chỉ khối màu xanh lam đã tạo cho cả hai.

Quá trình mà các con trỏ này kết nối các khối thực sự là một cuộc thi về mức độ phổ biến - chỉ đơn giản là khối nào sẽ được nhiều khối trỏ tới nhất và được coi là hợp lệ. Ngoài ra, nếu bản thân các khối trỏ đến một khối cụ thể là "phổ biến" (có nghĩa là nhiều khối khác trỏ đến chúng), thì "mức độ phổ biến" cũng sẽ chuyển sang khối cụ thể đó (khối chính).

Bây giờ, hãy đo mức độ phổ biến của từng khối.

trọng lượng - điểm phổ biến

Để đo mức độ phổ biến của từng vùng lân cận, chúng tôi áp dụng giao thức GHOST do Zohar và Sompolinsky đề xuất. GHOST giúp tính toán trọng số của mỗi khối ("độ phổ biến" của mỗi khối) dựa trên các con trỏ được nhúng trong Block DAG.

"trọng lượng" là gì? Nếu Khối DAG được xoay sang một bên, thì có thể coi mỗi khối con và khối con của nó bị cô lập khỏi khối mẹ, do đó, trọng số của bất kỳ khối nào trong GHOST là tổng trọng số của khối và tất cả các con cháu của nó.

Các trọng số đại diện cho nỗ lực tập thể của tất cả các nỗ lực nhằm dần dần xây dựng các khối khác trên khối đó, ngay cả khi nỗ lực này không được phối hợp và trải rộng trên nhiều con cháu.

>Giao thức GHOST rất đơn giản,

>Mỗi khối tự nhiên có trọng số là 1

>Mỗi khối có trọng lượng bằng trọng lượng của chính nó (1) cộng với trọng lượng của tất cả các khối trỏ tới nó

Bắt đầu từ ranh giới của khối DAG và đo ngược lại

Đây là một ví dụ.

Bắt đầu với các khối viền, chúng ta có thể gán trọng số cho từng khối. Khối màu xanh nằm ở biên của DAG, không có khối nào trỏ đến nó, vì vậy khối này có trọng số là 1. Khối màu xanh lá cây chỉ có một khối trỏ tới nó (khối màu xanh lam), vì vậy chúng tôi cộng trọng số khối của khối màu xanh lá cây (1) cộng với khối trỏ tới trọng số của nó (1) và chúng tôi nhận được 2, là trọng số mới cho màu xanh lá cây khối. Đi xa hơn, khối màu cam chỉ tới 3 khối nên trọng lượng của nó bằng tổng trọng lượng của 3 khối cộng với trọng lượng của chính nó là 1: 5+20+12+1=38.

Có vẻ tốt, tại sao chúng ta không thể sắp xếp theo trọng lượng bây giờ? Vâng, không hoàn toàn. Có một số vấn đề rất tế nhị với chiến lược đơn giản này, hãy tìm hiểu thêm về chúng.

Các cách để nhầm lẫn thứ tự

Hãy xem một ví dụ đơn giản để hiểu tại sao chỉ sử dụng giá trị trọng số làm cơ sở logic của cơ chế sắp xếp là không đủ.

Trong hình trên, chúng ta bắt đầu với kịch bản (a).

(a) Ta thấy rằng có hai khối màu cam, cả hai đều có giá trị trọng lượng là 1, vì vậy thứ tự của chúng không rõ ràng.

(b) Một khối khác được thêm vào trỏ đến hai khối trước đó, nhưng bây giờ cả hai đều có giá trị trọng số là 2 và vẫn có thứ tự không rõ ràng.

(c) Sau khi thêm một vài khối nữa, vấn đề với các khối màu cam không biến mất, chúng vẫn có cùng trọng lượng. Không chỉ vậy mà bây giờ nó còn tồi tệ hơn, vấn đề mới là các khối màu vàng cũng có thứ tự không rõ ràng.

Trong ví dụ trên, chúng tôi cho rằng mọi người đều trung thực - nhưng chúng tôi vẫn có thể gặp sự cố. Điều gì sẽ xảy ra nếu bạn giới thiệu một người chơi độc hại?Người chơi đó có thể chủ động làm xáo trộn thứ tự trên cấu trúc khối DAG. Hãy xem một ví dụ dưới đây.

Trong ví dụ này, chúng tôi bắt đầu với (b).

(b) Chúng ta có 2 khối màu cam với thứ tự không rõ ràng.

(d) Một khối khác xuất hiện và giải quyết vấn đề, bây giờ chúng ta có một thứ tự xác định. Sống lâu!

(e) Nhưng không lâu... một người chơi ác ý đang tích cực tìm cách giữ trật tự không rõ ràng và tạo một khối (màu đỏ) làm tăng khối đường viền và trọng lượng trở lại vị trí ban đầu. Sự cố, hai khối màu cam lại xuất hiện không được đặt hàng tốt.

Một hàm ý khác của cuộc tấn công này là những người chơi ác ý không chỉ có thể duy trì thứ tự mờ mà còn chuyển đổi thứ tự trước và sau khi thêm khối, khiến mạng luôn trong tình trạng hỗn loạn liên tục.

Mặc dù đây là những ví dụ rất đơn giản, nhưng những vấn đề như vậy có thể xảy ra ở quy mô lớn hơn, trong đó toàn bộ cụm khối được để ở trạng thái sắp xếp không xác định.

Vậy làm cách nào để giải quyết vấn đề này, tiếp theo chúng tôi sẽ giới thiệu các khái niệm về chuỗi neo và con trỏ ma.

Chuỗi neo - tuyến đường phổ biến nhất

Bước tiếp theo sau khi tính toán trọng số là xác định các chuỗi neo trong Block DAG. Nếu trọng số là điểm số phổ biến của mỗi khối, thì chuỗi neo là đường dẫn phổ biến nhất thông qua Block DAG. Các khối được quan sát trong khi đi qua các đường dẫn (đi bộ) cũng được quan sát rộng rãi (rất phổ biến) bởi mạng.

Làm thế nào để xây dựng một chuỗi neo? khối của , mỗi bước chọn khối có trọng số cao nhất. Đây là một ví dụ,

Ở hình trên, bắt đầu từ khối G trở đi có 3 khối có trọng số để bạn lựa chọn (381, 765, 381), khối nặng nhất là 765. Tiếp tục đi theo hướng này theo logic này, con đường từ khối G đến điểm cuối là chuỗi neo đã được xây dựng (màu xanh lá cây).

Đây là cách các chuỗi neo được tạo ra, "neo" Block DAG vào một đường dẫn mà từ đó chúng ta có thể xây dựng thuật toán sắp xếp.

Mặc dù phương pháp tính toán chuỗi neo này giải quyết vấn đề có cùng trọng lượng cho mỗi khối nhọn, nhưng nó lại đưa ra một vấn đề khác, vì kẻ tấn công vẫn có thể tiếp tục thay đổi chuỗi neo (không hội tụ rất nhanh). Vì vậy, chúng tôi giới thiệu các con trỏ ma để giúp mạng hội tụ đến một chuỗi neo cố định nhanh hơn, do đó đạt được thứ tự xác định.

Không phải tất cả các con trỏ đều được tạo bằng nhau

Để tiếp tục ngăn mạng rơi vào tình trạng hỗn loạn, chúng tôi giới thiệu một con trỏ đặc biệt được gọi là con trỏ ma. Ý tưởng cơ bản là khi mỗi khối được tạo, nó trỏ đến tất cả các khối trên ranh giới mà nó đã thấy và xác minh là hợp pháp, nhưng những khối như vậy là đặc biệt.

Khối đặc biệt là khối kết thúc của chuỗi neo, ngoài việc thừa nhận sự tồn tại của các khối hợp pháp khác trên ranh giới của Khối DAG, mỗi khối mới được thêm vào cũng sẽ trỏ đến con trỏ ma của khối kết thúc. Một thay đổi quan trọng ở đây là chỉ khối được trỏ tới bởi con trỏ ma mới được xem xét trong phép tính trọng lượng khối và các khối được trỏ tới bởi con trỏ khác không được xem xét.

Khối mẹ trở thành khối chỉ có con trỏ ma đặc biệt trỏ tới nó. Trong cấu trúc DAG của Khối Taraxa, mỗi khối sẽ chỉ trỏ đến một khối chính. Các khối khác chỉ đơn giản là quan sát các khối khác của cây khối (nguyên văn là lá có thể hiểu là khối), hoặc "tổ tiên" - trong Ethereum, chúng được gọi là "chú" hoặc "ommers". Điều này có thể được đề cập trước đó, hoặc có thể rất rõ ràng về số phụ huynh mà một khối có thể có.

Điều này giải quyết một vấn đề cơ bản về cách đảm bảo rằng tất cả các khối trên ranh giới không được trình bày ở dạng mơ hồ trong quá trình bỏ phiếu ngầm được biểu thị bằng biểu đồ DAG.

>Hãy xem nhanh một ví dụ,

>Mũi tên dày là con trỏ ma (trọng số được tính toán)

Mũi tên mỏng là con trỏ xác nhận (không có trọng lượng)

(a) Hai khối (1.1 và 1.2) trỏ đến khối gốc đầu tiên (0), đường đậm là con trỏ ma vì chỉ tồn tại một khối cha và cả hai khối đều trỏ đến khối đó. Thứ tự hiện không rõ ràng, nhưng chúng ta có thể sử dụng hàm băm thấp nhất để so sánh, giả sử (1.1) thắng và được coi là một ứng cử viên cho con trỏ ma của các khối trong tương lai.

(b) 3 khối được thêm vào, nhưng do sự chậm trễ của mạng, không phải tất cả các khối này đều nhìn thấy mọi khối mới cùng một lúc, điều đó có nghĩa là một số nút có thể nhìn thấy một số khối mảnh nhanh hơn. Ví dụ: ít bước nhảy mạng hơn do khoảng cách vật lý gần hơn sẽ tăng tốc độ mà các nút nhìn thấy các khối. Cả khối (2.1) và khối (2.2) đều nhìn thấy hai khối trước đó (1.1 và 1.2), vì vậy cả hai đều trỏ con trỏ ma đến hai khối này và xác định trung thực (1.1) là nằm trên chuỗi neo của khối kết thúc. Tuy nhiên (2.3) không nhìn thấy (1.1) nên chỉ có thể dùng ghost pointer để trỏ đến (1.2) chứ không thể làm gì khác. Lưu ý rằng theo quy tắc của chúng tôi, trọng số của khối đã được cập nhật, nhưng chỉ một phần của khối con trỏ tới nó bằng con trỏ ma mới được tính.

(c) Khối của lớp tiếp theo xuất hiện, khối (3.1) nhìn thấy khối (2.1) và (2.2) đồng thời và khối (3.2) nhìn thấy khối (2.1) và (2.3) đồng thời thời gian, Khối (3.3) cưa các khối (2.1, 2.2 và 2.3) cùng một lúc. Khi khởi chạy, mỗi khối chọn khối kết thúc trên chuỗi neo mà chúng nhìn thấy, trỏ con trỏ ma của nó vào khối đó và tiếp tục.

Cùng với chuỗi neo, con trỏ ma giúp buộc mạng hội tụ về chuỗi neo, ổn định thứ tự tổng thể. Tiếp theo, chúng tôi mô tả cách các khối cuối cùng được sắp xếp dựa trên chuỗi neo.

Sắp xếp theo Neo

Sử dụng con trỏ ma, hãy tính toán lại các trọng số trong ví dụ Block DAG trước đó. Một lần nữa lưu ý rằng chỉ khối được trỏ tới bởi con trỏ ma mới có trọng số được tính vào khối chính.

Khi chuỗi neo được vẽ, chúng tôi xây dựng các kỷ nguyên xung quanh mỗi khối (khối neo) trên chuỗi neo. Kỷ nguyên là số khối mà khối neo có thể quan sát hoặc khối mà khối neo trực tiếp hoặc gián tiếp trỏ tới. Hãy nghĩ về họ như những người bạn của các khối neo siêu phổ biến.

Trong hình trên, chúng tôi vẽ từng kỷ nguyên khối neo bằng đường chấm màu đỏ. Thật không may, khối neo đầu tiên có trọng lượng 25 chỉ là epoch. Khối neo tiếp theo có trọng lượng 21 có epoc, bao gồm chính nó và hai khối trọng lượng 1 khác mà nó có thể quan sát. Khối neo thứ ba có trọng lượng là 18 và chỉ có thể quan sát thấy một khối neo. Khối tiếp theo có trọng số là 17 và kỷ nguyên của nó là 3, bao gồm một khối có trọng số là 1 mà nó có thể quan sát trực tiếp và một khối khác có trọng số là 2 mà nó có thể quan sát gián tiếp. Bằng cách này, chúng tôi tiếp tục phân biệt cho đến khi kỷ nguyên của mỗi khối neo được rút ra.

Bây giờ chúng ta đã sẵn sàng để sắp xếp các khối! Đầu tiên, các khối được sắp xếp theo kỷ nguyên từ cũ nhất đến mới nhất (từ trái sang phải). Trong mỗi kỷ nguyên, giá trị trọng số được sử dụng để xác định khối nào đến trước bằng cách xem khối nào trỏ đến khối nào. Hoặc nếu phương pháp này không thành công, hãy sử dụng hàm băm khối làm phương pháp phán đoán khối có cùng khoảng cách với khối neo.

Nhìn vào biểu đồ kỷ nguyên, G là (1) đầu tiên. Sẽ chỉ có một khối trong kỷ nguyên tiếp theo, vì vậy khối này có trọng số 25 là khối thứ hai (2). Chuyển sang epoch tiếp theo, hai khối có giá trị trọng số là 1 nằm trước khối neo có trọng số là 21 (vì chúng trỏ đến khối có trọng số là 21), cách so sánh hai khối này là so sánh hàm băm của ai. giá trị thấp hơn Xác định (3) và (4), sau đó, khối thứ năm (5) là khối có giá trị trọng số là 21. Chúng tôi tiếp tục cho đến khi tất cả các khối trong tất cả các kỷ nguyên được sắp xếp.

Như được hiển thị bên dưới, các số trong mỗi khối biểu thị thứ tự chứ không phải trọng lượng.

Chúng tôi cuối cùng đã hoàn thành!

Nhưng chúng ta đã thực sự hoàn thành chưa Còn những khối chưa được sắp xếp thì sao?epochLuôn có một số khối gần ranh giới của cấu trúc Block DAG không thuộc chuỗi neo

một phần của. Nhưng đừng lo lắng, vì nhiều khối được thêm vào ranh giới, cuối cùng chúng sẽ được đưa vào.

Không phải các chuỗi neo (và do đó thứ tự kết quả) thay đổi theo thời gian?Vâng, có nguy cơ sắp xếp lại thứ tự trong cấu trúc Block DAG. Rủi ro này giảm theo cấp số nhân theo thời gian, nhưng không bao giờ thực sự bị loại bỏ, đó là lý do tại sao Taraxa cần triển khai quy trình hoàn thiện theo thời gian thực (bài viết sắp xuất bản).

Tính hữu hạn thời gian thực thực sự được giới thiệu trong cấu trúc Block DAG mà không có nguy cơ sắp xếp lại thứ tự, đây là cơ sở để xây dựng DApps trong mạng.