# Private Liquidity Matching using MPC
[Paper](https://eprint.iacr.org/2021/475)
[Video Presentation](https://youtu.be/hRnAi_vds2Y?si=KUM1jD329DII7UeD)
**Interbank Payments**
- Banks need to transfer money between each other. If customer Alice of bank A transfers $500$ dollars to Bob, customer of bank B, now Bank A owes $500$ dollars to Bank B.
- Each commercial bank has a balance. The central bank keeps track of the balances of commercial banks.
- If Bank A has enough liquidity in their balance, the money transfer is settled right away. This is done by the central bank that decreases Bank A balance by $500$ and increases Bank B balance by $500$.
<figure align="center">
<img src="https://hackmd.io/_uploads/SywMhQxHA.png" width="400">
</figure>
- If Bank A doesn't have enough liquidity in their balance, the payment is added to a payment queue and there's gonna be an attempt to settle it at the end of the day
<figure align="center">
<img src="https://hackmd.io/_uploads/BJdS2XlS0.png" width="400">
</figure>
- At the end of the day, there might be a gridlock situation in which a set of transactions cannot be settled as each transaction is waiting for another one to be settled. A bank might only have the required liquidity to perform such payment only if some other transaction is settled.
<figure align="center">
<img src="https://hackmd.io/_uploads/H1OIn7lBC.png" width="400">
</figure>
Two solutions to gridlock problem:
1. Bank A to ask for extra liquidity and return it at the end. But liquidity is expensive!
2. A central bank, that collects all the payments in the queue, performs the netting process and detects that all the transactions can be settled. They are able to do so because they have a global picture of the state of the payment network and the balances
<figure align="center">
<img src="https://hackmd.io/_uploads/SJmwaXerR.png" width="400">
</figure>
All the payments in the queue are settled without any liquidity injection!
## Problem
- Entity is trusted to preserve the confidentiality of these information. **Can we do it without this central entity?**
Requirements are:
- *correctness* of the execution (see the rules later)
- *privacy*, account balances should only be known to the respective bank, transaction amount, sender and receiver should only be known to the 2 banks involved in the transaction.
- *fairness*, the queue order of the payments should be respected.
## Gridlock Resolution Problem
Goal: maximize the number of transaction settled (note: one tx can either be settled in full or not settled at all, partial settlement doesn't exist)
Constraints:
- After the resolution, the balances of the banks should not be negative
- The payment priority order should be maintained (First in First out - FIFO)
-> Poly-time algorithm
1. Initiate a solution $U$ with all the payments in the queue $Q$
2. Calculate the balances $B_i$ of each bank, assuming that all the payments in the solution are executed
- If there's a least a negative balance, go to step 3
- Else, all the payments in the solution $U$ can be executed
3. For each bank with negative balance, remove from $U$ the transactions with the least priority until their balance is positive. Then go to step 2.
```
Initial State
Q [(v4, v1, 1), (v1, v3, 2), (v1, v2, 1), (v3, v4, 4)]
// better to interpret it as a queue of outgoing txs for each bank
// where last tx is the one with least priority
Q_v1 = [(v1, v3, 2), (v1, v2, 1)]
Q_v2 = []
Q_v3 = [(v3, v4, 4)]
Q_v4 = [(v4, v1, 1)]
balances
v1 1
v2 1
v3 3
v4 0
// note: payment (v1, v2, 1) cannot be executed by v1 even if they have liquidity to do so
// because it has lower prio than (v1, v3, 2)
Step 1
U [(v4, v1, 1), (v1, v3, 2), (v1, v2, 1), (v3, v4, 4)]
Step 2 - 1st iteration
B_v1 = 1 + 1 - 2 - 1 = -1 >= 0 X
B_v2 = 1 + 1 = 0 >= 0 V
B_v3 = 3 + 2 - 4 = 1 >= 0 V
B_v4 = 0 - 1 + 4 = 3 >= 0 V
Step 3 - 1st iteration
U [(v4, v1, 1), (v1, v3, 2), (v3, v4, 4)]
Step 2 - 2nd iteration
B_v1 = 1 + 1 - 2 = 0 >= 0 V
B_v2 = 1 = 1 >= 0 V
B_v3 = 3 + 2 - 4 = 1 >= 0 V
B_v4 = 0 - 1 + 4 = 3 >= 0 V
Final State
- payments in U are executed
updated balances
v1 0
v2 1
v3 1
v4 3
updated Q
Q [(v1, v2, 1)]
```
Now we need to turn this algorithm into MPC
## MPC Setting
- Shamir secret sharing over three parties and active security with abort
- malicious adversaries that try to deviate from the protocol are detected and the honest parties can abort
- $p$ = 3 and $t=1$ (honest majority, t+1 can collude and learn the inputs).
- The functions to be performed are expressed through a circuit made of addition and multiplication gates over a field $F_q$, where $q$ is a large prime
- Uses the Scale Mamba framework -> https://github.com/KULeuven-COSIC/SCALE-MAMBA
| | Balances | payment amount | payment source | payment destination |
| ---- | -------- | -------------- | -------------- | ------------------- |
| SODO | 🔴 | 🔴 | 🟢 | 🟢 |
| SODS | 🔴 | 🔴 | 🟢 | 🔴 |
| SSDS | 🔴 | 🔴 | 🔴 | 🔴 |
## MPC Components
- Addition between secrets - can be executed locally
- Multiplication between secrets - require some interaction. Still pretty efficient in honest majority setting.
- Comparison between secrets - doesn't specify how to perform that. They just claim that this is more expensive than multiplication.
- Naive ORAM - necessary to read and write on a secret index of an array of secret values. Core to build that is a `Demux` function that takes:
- INPUTS: a public bound $L$ and a secret index $x$
- OUTPUTS: secret bit vector $b_1, ..., b_L$, such that
$$b_i =
\begin{cases}
1 & \text{if } i=x\\
0 & \text{o/w}
\end{cases}$$
## Algorithms
- Each transaction is a triple $t =[s, a, r]$.
- Input balances (before the settlement) are $B^i$ (balance of $i$-th bank) for $i$ in $[1, ..., n]$
- $x_t$ is a bit that indicates whether the transaction $t$ belongs to the set of transactions to be settled
### Demux
<figure align="center">
<img src="https://hackmd.io/_uploads/HkJegweBR.png" width="400">
</figure>
<figure align="center">
<img src="https://hackmd.io/_uploads/rywZfPxSR.png" width="400">
</figure>
### Calculate Balances
- Goal is to take a set of initial balances, a set of transaction with their settlement bit and output the updated balance after the trasanctions
**SODO**
- In SODO source and receiver are public while the amount is private. Therefore a transaction is equal to $t =[s, \langle a \rangle, r]$
For all $i$ in $[1, ..., n]$
$\langle S^i \rangle = \sum_t \langle a \rangle * \langle x_t \rangle$ where $t$ is any tx with $s = i$ `//calculate outgoing balance`
$\langle R^i \rangle = \sum_t \langle a \rangle * \langle x_t \rangle$ where $t$ is any tx with $r = i$ `//calculate incoming balance`
$\langle B{_U}^{i} \rangle = \langle B^i \rangle + \langle R^i \rangle - \langle S^i \rangle$ `//calculate final balance`
Note that in the first iteration the $\langle x_t \rangle$ for each transaction are set to 1 (ideal solution $U$)
**SODS**
- In SODS source is public while receiver and the amount are private. Therefore a transaction is equal to $t =[s, \langle a \rangle, \langle r \rangle]$
For all $i$ in $[1, ..., n]$
$\langle S^i \rangle = \sum_t \langle a \rangle * \langle x_t \rangle$ where $t$ is any tx with $s = i$
$\langle R^i \rangle = \sum_t \langle a \rangle * \langle x_t \rangle * \langle \mathbf{c}^t_{i} \rangle$ where:
- $t$ is any tx in the set
- $\mathbf{c}^t$ is the demux vector related to transaction $t$
- $\mathbf{c}^t_{i}$ is the $i$-th bit in that vector. It indicates whether $i$ is the receiver (1) or not (0) of $t$
$\langle B{_U}^{i} \rangle = \langle B^i \rangle + \langle R^i \rangle - \langle S^i \rangle$
Overhead:
- No difference to compute outgoing balance
- Longer sum to perform to compute incoming balance because you need to **loop over all the transactions**
- One extra multiplication for each sum
- Demux to be done at the beginning
**SSDS**
- In SSDS receiver, source and the amount are private. Therefore a transaction is equal to $t =[\langle s \rangle, \langle a \rangle, \langle r \rangle]$
For all $i$ in $[1, ..., n]$
$\langle S^i \rangle = \sum_t \langle a \rangle * \langle x_t \rangle * \langle \mathbf{w}^i_{t} \rangle$ where $t$ is any tx in the set
$\langle R^i \rangle = \sum_t \langle a \rangle * \langle x_t \rangle * \langle \mathbf{c}^i_{t} \rangle$ where $t$ is any tx in the set
$\langle B{_U}^{i} \rangle = \langle B^i \rangle + \langle R^i \rangle - \langle S^i \rangle$
Overhead -> Twice as before
### Check if balances are negative
- Define an empty array $h$ with size $n$
- For each bank $i$, calculate if the balance is negative and set the resulting bit as the $i$-th index of the array $\langle h^i \rangle = \langle B{_U}^{i} \rangle \lt 0$
- Then we have to determine whether there is at least one bank with negative balance $\langle z \rangle = \prod 1 - \langle h^{i} \rangle$ (sort of AND gate)
- Open $\langle z \rangle$
- If $z=1$, it means that all the balances are positive and we found a solution.
- If $z=0$, it means that there is at least one negative balance, therefore we need to remove the lowest priority tx from the banks with negative balance
### Remove last transaction for banks whose balance is negative
This would set the indicator bit to 0 only to the transaction part of the solution with the least priority *only for the banks with negative balance*, which is defined by the bit $\langle h^i \rangle$
After updating the indicators, recalculate the balances and do the whole process again. The process stops only when $z=1$.
### Protocol
- The servers have as inputs:
- The secret shared balances of the banks
- A set of transactions of which information are more or less private according to the `type`. The transactions are orded and have to be processed in FIFO.
- The servers perform the Gridlock Resolution algorithm as described above
- If $z=1$, all the bits of the vector $\mathbf{x}$ are opened internally. The servers get to know which transaction is settled or not.
- For any settled transaction, each party involved is notified about this. Namely, the servers open the transaction to that party by sending them the shares.
- In the case of SSDS the opening to parties is more complex. The servers don't know who are the sender and the receiver of that tx. This basically require to open every transaction for every party and the opened value will be equal to 0 when the party is not the legitimate receiver or source of that transaction. This is still based on the ORAM logic.
### Benchmarks
- Finite field 128 bits
- The machines used are 128GB of RAM, with an Intel i-9900 CPU, with a ping time of 0.098 ms between them
- $m$ transactions were chosen such that a solution will be found after m/4 iterations
### Conclusions
- Calculating the balances involve a whole set of multiplications which is already pretty expensive
- To hide the destination (and the source, if needed) require to leverage the ORAM logic which increase the complexity of the operation to compute the balances. In particular, we now need to loop over all the transactions and multiply them with a ORAM bit.
- You can move the needle on the tradeoff between privacy and computation runtime
- On the application side, the settlement is binary. No partial settlement is admitted here. This helps achieving fairness. But you could save more liquidity by admitting partial settlement.
Sign in with Wallet
Connect another wallet