乙太坊上的圖遍歷，大規模

我閱讀了定向加權圖執行緒的 Efficient Solidity 儲存模式，但它涉及儲存圖。我對如何在 Solidity 中大規模遍歷圖形的技術感興趣。

考慮以下數據模式，它使用 Rob Hitchens 的UnorderedKeySet庫來建構一個包含行和鍵的類似表的數據庫：

contract GraphTraversal {
   using HitchensUnorderedAddressSetLib for HitchensUnorderedAddressSetLib.Set;
   using HitchensUnorderedKeySetLib for HitchensUnorderedKeySetLib.Set;

   struct User {
       uint256 balance;
       uint256[] incomingStreamIds;
       mapping(uint256 => uint256) incomingStreamIdPointers; /* left is stream is row in table */
       uint256[] outgoingStreamIds;
       mapping(uint256 => uint256) outgoingStreamIdPointers; /* left is stream id, right is row in table */
   }

   mapping(address => User) public users;
   HitchensUnorderedAddressSetLib.Set userSet;

   struct Stream {
       uint256 interval;
       uint256 paymentRate;
       address sender; /* key for a User struct */
       address recipient; /* key for a User struct */
       uint256 startTime;
       uint256 stopTime;
   }

   mapping(bytes32 => Stream) public streams;
   HitchensUnorderedKeySetLib.Set streamSet;
}

---

強調：

• 每個使用者引用兩個集合，傳入和傳出流，它們的長度都有上限 - 合約對可以創建多少傳入和傳出流實施上限
• 每個流引用兩個使用者，一個發送者和一個接收者

以上是使用者和流之間的二對多數據關係。我們將流定義為金融協議，其中發送者每隔一段時間向接收者支付特定金額的錢。

---

現在，我想要實現的目標：

• 有一個rebalance函式可以遍歷所有引用使用者的傳入和傳出流
• 遞歸呼叫rebalance傳入流的每個發送者和傳出流的每個接收者 - 本質上是深度優先搜尋 (DFS)
• 如果在函式呼叫期間的任何階段，使用者抵押不足（流所需的付款金額超過其目前餘額），則刪除目前流和所有後續流
• 在函式結束時，通過將傳入流提供的所有收入相加並減去對傳出流的所有支付來rebalance更新每個使用者的屬性balance

---

顯然，這在乙太坊主網上（大規模）是不可行的。我會在使用者和流相對較少的情況下達到塊氣體限制。

這樣的事情怎麼可能實現？也許是 SNARK 或樂觀匯總，它們在鏈外進行圖遍歷並隨後在主網上發布簡潔的證明？

有關該rebalance函式的虛擬碼實現，請參閱 GitHub 上的此要點。

你可以要求主播進行超額抵押，而那些未能保持超額抵押的主播將被清算。有了它，您可以採取惰性更新方法，其中自利的參與者以拼湊模式更新智能合約。

因此，例如，假設所有流都需要發布至少 3 小時的流媒體的附屬品。當流被合法關閉時，例如作為流媒體和流媒體之間的協議，流媒體將獲得 3 小時的附帶費用。

任何人都可以對任何擁有少於 3 小時抵押品來覆蓋他們的資金流的人啟動清算過程。如果成功，清算人會獲得抵押品，但也會獲得資金流。獲取整個帳戶。

清算人現在需要充值抵押池，並可能關閉流出的流。將其視為對公司的強制收購。如果處理得當，它將為清算人帶來淨利潤。

任何流媒體的狀態都可以在智能合約未完全更新的情況下在鏈下計算。但是，要進行清算，智能合約需要處於可以驗證抵押不足的狀態。因此，清算人可以維護自己的鏈下狀態副本，尋找清算機會。當他們找到一個時，他們可以更新最低限度以證明清算是有效的。

除此之外，為了盡可能保持智能合約的更新，​​流媒體更新可以捆綁到其他交易中，就像Pot.sol強制任何知道的人將chi其更新到目前的一樣now。

您真的需要每次都遍歷所有流嗎？

您可以有一個時間函式來告訴您每秒的傳出總數和傳入總數，它將僅基於每個使用者的一個變數，該變數在每次修改流時都會更新。您可以通過簡單的操作知道使用者是否抵押不足。

看看Pot.solMakerDAO 和ERC20DividendableEth.solHQ20 是如何工作的。

引用自：https://ethereum.stackexchange.com/questions/84226