Graph traversals on Ethereum, at scale

Question

I read the Efficient Solidity storage pattern for a directional weighted graph thread, but that deals with storing graphs. I'm interested in techniques for how to traverse graphs in Solidity, at scale.

Consider the following data pattern, which uses Rob Hitchens' UnorderedKeySet library to build a table-like database with rows and keys:

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;
}

---

Highlights:

• Each user references two sets, incoming and outgoing streams, which are both capped in length - the contract enforces an upper limit on how many incoming and outgoing streams can be created
• Each stream references two users, a sender and a recipient

The above is a two-to-many data relationship between users and streams. We define streams as financial agreements whereby the sender pays the recipient a specific amount of money once every so often.

---

Now, what I want to achieve:

• Have a rebalance function that iterates over all incoming and outgoing streams that refer to a user
• Recursively call rebalance for every sender of an incoming stream and every recipient of an outgoing stream - essentially a depth-first search (DFS)
• If at any stage during the function call, a user is under-collateralised (the payment amount required by the the streams exceeds his current balance), delete the current stream and all streams that succeed it
• At the end of the rebalance function, update each user's balance property by adding up all the income provided by the incoming streams and subtracting all payments made to outgoing streams

---

Obviously, this is not feasible on Ethereum mainnet (at scale). I'd hit the block gas limit with relatively few users and streams.

How could something like this be implemented? Maybe SNARKs or optimistic rollups that do the graph traversal off-chain and post a succinct proof on mainnet afterward?

For a pseudocode implementation of the rebalance function, see this gist on GitHub.

Answer 1

You could require streamers to overcollateralize, with those that fail to stay overcollateralized being liquidated. With that you can take a lazy update approach, where self-interested actors update the smart contracts in a patchwork pattern.

So imagine for example that all streams are required to post collateral for at least 3 hours of streaming. When a stream is lawfully closed, for example as an agreement between streamer and streamed, the streamer gets the 3 hours of collateral back.

A liquidation process could be started by anyone on anyone that has less than 3 hours of collateral to cover their streams. If successful the liquidator gets the collateral, but also the streams. Gets the whole account.

The liquidator now needs to top up the collateral pool, and possibly close the outgoing streams. Think of it as a forced acquisition of a company. If done properly, it will result in a net profit for the liquidator.

The state of any streamer can be calculated off-chain with the smart contracts not fully updated. For a liquidation to happen, the smart contracts need to be in a state where the undercollateralization can be verified, though. Therefore, the liquidators can maintain their own off-chain copy of the state, looking for liquidation opportunities. When they find one, they can update the bare minimum to prove that the liquidation is valid.

Apart from that, to keep the smart contracts as updated as possible, streamer updating can be bundled into other transactions, same as Pot.sol forces anyone whating to know the chi to update it to the current now.

Answer 2

Do you really need to iterate over all streams each time?

You could have a time function that tells you the outgoing total and incoming totals per second, it would be based on just one variable per user which gets updated each time the streams are modified. You could know if an user is undercolaterallized with a simple operation.

Have a look at how Pot.sol from MakerDAO and ERC20DividendableEth.sol from HQ20 work.