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'sbalance
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.