# Gridlock

*Multilateral Obligation Netting in MPC*

[EDCON 29/7/2024 - Slides](https://drive.google.com/file/d/1Lo6ls_2friG6HvNDs3foVSw4HyLnpoHD/view?usp=drive_link)

#### Preliminary Notions

*Obligation*: when a business sells goods or services to another, it issues an invoice to the buyer. This invoice represents a financial obligation: the buyer (debtor) owes money to the seller (creditor). Equal to *I owe you* (IOU)

*Liquidity*: refers to the availability of cash for a business. A business requires liquidity to meet their short-term obligations (pay their bills and employees on time), take advantage of business opportunities or weather unexpected financial challenges.

## Introduction

<figure align="center">
<img src="https://hackmd.io/_uploads/r1WRrzXt0.png" width="450">
</figure>

The figure illustrates a minimal payment network between three businesses. In such scenario, participants are not able to meet their obligations due to insufficient liquidity. Firm#1 is waiting for Firm#3 to pay his bill in order to pay Firm#2, Similarly, Firm#2 is waiting for Firm#1 and Firm#3 is waiting for Firm#2. Lack of liquidity brings the system to a halt known as *gridlock*.

To solve this stall, one participant must source liquidity externally, e.g., via a loan.

Alternatively, businesses can rely on [Multilateral Obligation Netting](https://www.mutualcredit.services/multilateral-obligation-set-off). This is a process run by a service provider who collects obligations from a network of businesses and, by having a complete view of the state of the network, can detect *cycles*. A cycle is a circular pattern of due payments that connects businesses. A cycle is an opportunity to clear, at least partially, debt for the participants involved.

<figure align="center">
<img src="https://hackmd.io/_uploads/HJudIzXt0.png" width="700">
</figure>

If you were to perform Multilateral Obligation Netting within such a network, all the obligations would be deleted without requiring any (costly) injection of external liquidity. When it is not possible to settle all the obligations, even if a partial set-off is admitted.

Starting from 1991, Slovenia implemented Multilateral Obligation Netting on a country-wide level. Results [AJPES 2002–2019] have shown that in 2019, the mechanism cleared over 209 million euros, which represents 0.5% of GDP, with 2,700 companies participating or 1.2% of the total.

The **direct benefit** for any participant in the system is liquidity saving: less cash tied up in pending payments means more financial flexibility and reduces reliance on external funding sources (like loans) for day-to-day operations. The **indirect benefit** is a decreased systemic risk for the whole network and the wider economy [FDL20].

One of the main findings of [FDL20] is that obligation set-off, if applied at a national level, can save liquidity for an amount equal to or greater than 10% of the national GDP, under the condition that at least 40% of the businesses in the country submit their outstanding invoices. Simply put, **the higher the participation, the greater the benefits for the participants**.

[FD21] argues that the one the firms might lack trust towards the state or the agency performing the clearing and this might disregard their partecipation. In addition to performing the set-off correctly, the agency is trusted to perserve the confidentiality of the obligations coming from the participants.

**Gridlock research hypotesis**: the low business participation to the network, 1.2% of the total of the companies in Slovenia recorded in 2019, is due to the requirement, for a business, of giving up the view to their invoices to a governement agency. A system that allows businesses to perform Multilateral Obligation Netting while guaranteeing confidentiality over their obligations would encourage more participation, yielding higher liquidity savings for the participants and systemic risk reduction at a macroeconomic level. In particular, *Gridlock* achieves confidentiality by using multiparty computation (MPC).

## Technical Overview

The technical section is split into two parts: first, we define Multilateral Obligation Netting as an optimization problem. Second, we analyse its secure version, namely the corresponding MPC implementation.

#### Optimization Problem

The *optimization problem* that describes the Multilateral Obligation Netting procedure is provided by [FD21]. This is also the one applied in production in Slovenia. The algorithm is proven to provide the optimal percentage of obligation settlement ($\frac{\sum \text{amount settled}}{\sum \text{amount input}}$) in an obligation network.

In a obligation network involving $v$ firms beloning to the set $V = \set{1, 2, ..., v}$:
- $L$ is a liability matrix of size $v \times v$ where the non-negative entries represent the outstanding obligations between two firms (e.g., $L_{ij}$ is what $i$ owes to $j$). Note that the obligations are filtered such that if $L_{ij}$ is positive, $L_{ji}$ must be zero. Assume that each obligation is expressed as an integer
- $E$ is the set of existing obligations of size $e$ such that $E = {(i, j) \mid L_{ij} > 0, i, j \in V}$.
- $b$ is the net balance vector of size $v$ given by the difference between the total credit of each firm and the total debt of each firm (e.g., $b_i$ is the net balance of firm $i$). Note that the sum of the vector elements must be equal to 0 since a credit of a firm equals to a debt of another firm. $$\sum_{i=1}^v b_i=0$$

The **optimization problem** is to find the liability matrix $M$ of the obligation network such that its Grandsum function $\mu$ is minimum:

\begin{equation}
\min \mu(M) = \min \sum_{(i,j)\in E} M_{ij}
\end{equation}

Subject to the constraints:

\begin{equation}
\sum_{j:(j,i)\in E} M_{ji} - \sum_{j:(i,j)\in E} M_{ij} = b_i \quad \forall i \in V
\end{equation}

\begin{equation}
0 \leq M_{ij} \leq L_{ij} \quad \forall (i,j) \in E
\end{equation}

[FD21] proposes to map this problem to the standard Minimum Cost Flow problem where each firm is a node in the network and the edge $(i, j)$ has a capacity equal to $L_{ij}$. The cost of each edge is, by default, assigned to 1.

The first constraint is the flow conservation constraint while the second is the balance conservation constraint. The MCF flow is a flow through the network that avoids all the cycles.

The remaining outstanding obligations after the set-off are represented by the solution $M$.

#### MPC Algorithm

Existing research focused on achieving confidentiality in the context of interbank payments netting. The solutions proposed by [CYD+20] and [ASA22] only achieve binary settlement (one obligation is either settled in full or not settled at all).

[ADM22] allows for partial settlement therefore achieving optimal liquidity saving. This is achieved by performing a linear programming based algorithm inside a general-purpose MPC protocol. Despite its optimality in terms of obligation set-off, this solution wouldn't be efficient enough if applied to a nation-wide payment network of businesses, which is several orders of magnitude larger than an interbank network.

To allow confidential Multilateral Obligation Netting on the scale, improvements have to be made around the secure implementation of the core algorithm. Defining the optimization program in graph theory might be more efficient than expressing it via linear programming. In particular, [AV15] describes how to solve the MCF problem in MPC, leveraging the Minimum Mean Cycle as a subroutine. Nevertheless, the applicability of the algorithm seems to be limited by the high degree ($|V|^{10}$) of the complexity-bound polynomial when considering a full graph ($|V|$ is the number of nodes in the graph).

The MPC implementation is based on a setting in which the participants submit their inputs to a set of servers that perform the computation securely (client-to-server model). The privacy is guaranteed as long as a majority of the servers is honest.

In its basic implementation, the participants are assumed to be honest and provide correct inputs to the server. The servers are assumed to perform the computation correctly (passive security). An additional dispute resolution mechanism can be attached to the system to detect any incorrectness.

#### Targets

The Secure MPC implementation should be able to perform a close-to-optimal set-off for 90k firms in less than 8 hours.

Slovenia performs Multilateral Obligation Netting on a monthly basis. Considering the participation target of 40% suggested by [FDL20] and the data registered in 2019, this would correspond to 90k firms. Furthermore, 8 hours is chosen as an arbitrary target, considering that firms should submit their invoice by the end of a working day and receive the updated state the next morning.

The secure MPC should hide both the amount of each obligation and the fact that there is an obligation outstanding between the two firms. Practically, this requires hiding the capacity of each edge and the shape of the obligation network to the computing parties.

Given the high complexity of such algorithms when performed in a secure environment, we are interested in a solution that approximates fast to an optimal solution, such that, when the stopping rule comes, a close-to-optimal solution can be provided to the parties.

## Roadmap

### Month 5/6 - 2024

**Goal**:

Survey the space. Understand if there's any opportunity (and demand) to improve the state of the art. Understand the mathematical foundation of the core algorithm.

**Deliverables**:

- [x] Literature review
- [x] Python implementation of the core TCT algorithm, including different graph theory algorithms to solve the MCF problem

### Month 7/8 - 2024

**Goal**:

Definition of the best algorithm to perform Multilateral Obligation Netting in MPC.

**Deliverables**:
- [x] Short note about efficient Minimum Mean Cycle Detection performed in MPC -> https://ethresear.ch/t/a-note-on-securely-finding-minimum-mean-cycle/20073
- [x] Prototype implementation of the TCT algorithm based on Minimum Mean Cycle in [MP-SPDZ](https://github.com/data61/MP-SPDZ)
- [x] Implementation of efficient TCT algorithm in MP-SDPZ
- [x] Benchmark at scale

### Month 9 - 2024

**Goal**:

Consolidate the findings and share them with the public.

**Deliverables**:

- [ ] Paper (to be published first on eprint then find appropriate conference)

### Future

The core component of *Gridlock*, the efficient MCF algorithm in MPC, is abstracted such that other network-based applications can leverage that. An example is [Grapevine](https://github.com/Mach-34/Grapevine), which aims to compute the degree of separation between two parties confidentially in a social graph. Further confidential graph-theory-based primitives can be implemented to support practitioners. Another idea worth exploring is to apply Gridlock in the context of payment networks.

## Team

**Collaborators**

| Name | Int/Ext | Role | FTE |
| --------- | -------------- |:-------------------------------------------------------------- | ---- |
| Nam | Int(MPC team) | Co-author of the Paper, supports MPC and research direction | 1/5 |
| Masato | Int(grantee) | Research Gridlock in FHE | 3/5 |

**Integrators**

| Name | Int/Ext | Role |
| ----- | -------------- | ---------------------------------------------------------------------- |
| Onur | Int(Halo2) | Extension of PCD Cash using Gridlock |
| Vivek | Int(Cursive) | Build IRL social experiments of Gridlock |

### Resources

- [AJPES 2002–2019](https://www.ajpes.si/Bonitetne_storitve/Vecstranski_pobot/Porocila#b671)
- [FDL20](https://www.mdpi.com/1911-8074/13/12/295)
- [FD21](https://www.mdpi.com/1911-8074/14/9/452)
- [ADM22](https://link.springer.com/chapter/10.1007/978-3-031-32415-4_19)
- [ASA22](https://link.springer.com/chapter/10.1007/978-3-030-95312-6_5)
- [CYD+20](https://link.springer.com/chapter/10.1007/978-3-030-51280-4_9)
- [AV15](https://core.ac.uk/download/pdf/34101344.pdf)