In order to know whether our algorithm actually works and scales, we tested it on a rather large dataset: the Sarafu dataset.

The Sarafu Dataset

The Sarafu Dataset is openly available and describes 440,000 transactions between roughly 55,000 accounts. We use it here to see if the LedgerLoops algorithm can efficiently find loops.

Definition of Loops

Consider the following small dataset:

Transaction 1: Node 1 sends node 2 a transfer of 50 units
Transaction 2: Node 2 sends node 3 a transfer of 150 units
Transaction 3: Node 3 sends node 2 a transfer of 25 units
Transaction 4: Node 3 sends node 1 a transfer of 25 units

If these transactions are administered on a single ledger, then the balances would evolve as follows:

After transaction	Node 1 balance	Node 2 balance	Node 3 balance
0	0	0	0
1	0 - 50 = -50	0 + 50 = 50	0
2	-50	50 - 150 = -100	0 + 150 = 150
3	-50	-100 + 25 = -75	150 - 25 = 125
4	-50 + 25 = -25	-75	125 - 25 = 100

Note that in this situation, each node has only a single balance against its environment, and netting happens explicitly as a part of each transaction. At each transaction, two of the balances on the central ledger are updated.

It is, however, also possible to implement a payment network using just bilateral peer-to-peer trustlines. In that case, the balances would evolve as follows:

After transaction	[1->2, 1->3] bilateral balances	[2->1, 2->3] bilateral balances	[3->1, 3->2] bilateral balances
0	[ 0, 0 ]	[ 0, 0 ]	[ 0, 0 ]
1	[-50, 0 ]	[ 50 , 0 ]	[ 0, 0 ]
2	[-50, 0 ]	[ 50, -150 ]	[ 0, 150 ]
3	[-50, 0 ]	[ 50 , -125 ]	[ 0, 125 ]
4	[-50, 25 ]	[ 50 , -125 ]	[ -25, 125 ]

Note that in this case bilateral netting between nodes 2 and 3 is still immediate, and transactions 2 and 3 partially cancel each other out.

However, whereas the central ledger ends up with a total deployed balance of 100 units, the system of bilateral ledgers ends up with total deployed balance of 50 + (150-25) + 25 = 200 units.

In order to reduce the total deployed balance in a network of bilateral ledgers, loops can be used. They consist of a set of transactions, one per ledger, that reduce the total deployed balance in a way all participants can agree with.

So in this case:

Transaction 5a: Node 2 sends node 1 a loop-transfer 25 units.
Transaction 5b: Node 3 sends node 2 a loop-transfer 25 units.
Transaction 5c: Node 1 sends node 3 a loop-transfer 25 units.

And the effect:

After transaction	[1->2, 1->3] bilateral balances	[2->1, 2->3] bilateral balances	[3->1, 3->2] bilateral balances
5a	[ -50 + 25 = -25, 25 ]	[ 50 - 25 = 25, -125 ]	[ -25, 125 ]
5b	[ -25, 25 ]	[ 25, -125 + 25 = -100 ]	[ -25, 125 - 25 = 100 ]
5c	[ -25, 25 - 25 = 0 ]	[ 25, -100 ]	[ -25 + 25 = 0, 100 ]

The total deployed balance has now been reduced by 3 times 25 units, from 50 + (150-25) + 25 = 200 units to (50-25) + (150-25-25) + (25-25) = 125 units.

Performance

Snake Game Search

Until recently, most loop detection algorithms were based on min-cost-flow (MCF) algorithms. However, a decentralised implementation of MCF would require nodes that are not part of the globally best solution to cooperate altruistically. We therefore explored the use of "Snake Game" search algorithms, in which forwarded messages between nodes cause a 'snake' to form through the network, similar to the Snake Game that was popular on feature phones.

The presence of a loop would cause the "snake" to encounter its own "tail". Our strategy pit compares such a snake-like Depth-First Search (DFS) algorithm against MCF.

Conclusion

Observations

The results are very encouraging. MCF does clear more debt, namely 67% instead of 60%, so snake-like DFS is underperforming by about 10%. But we believe this is an acceptable performance gap, and have plans for enhancements that will make this gap even smaller.

The currently tested DFS algorithm is written in 350 lines of TypeScript and finds around 1,000 loops per second in a single execution thread on a regular modern laptop.

Algorithm Open Standard

We are working on a messaging-based version of this algorithm that uses the messaging protocol specified by the Decentralized Cycle Detection Internet Draft, and this is rather straightforward when using a central orchestrator to decide which node moves next.

Tech Preview

So far, it has proven more difficult than we had anticipated to make the algorithm run not only through node-to-node messaging but also without any central coordination, but we're making good progress on this goal and hope to launch an MVP of a fully peer-to-peer obligation clearing network in 2025. We published our Jerboa prototype in October 2024 to show that peer-to-peer obligation clearing is, in principle, feasible.