TLDR
- Netting refers to the problem of having multiple local banks (e.g. Bank of America, Chase, PNC etc) trying to settle pending transactions while maintaining a positive final balance.
- In this work, we present a privacy preserving and decentralized solution to this problem by using cryptographic tools like commitments, zero knowledge proofs (ZKs) and secure multiparty computation (MPC).
Core Research Question
Is there an efficient way to solve the privacy preserving decentralized netting problem ?
Citation
My talk at FC 2022 on Privacy Preserving Decentralized Netting: Privacy Preserving Decentralized Netting - YouTube
Background
-
Commitments: A cryptographic scheme which allows a designated party (called the Sender) to “commit” to a private value m by generating a string c. During a later phase, the sender can “reveal” the string c to its corresponding message m. Such a scheme has 2 basic properties: i) Hiding: The commitment string c hides the message m, ii) Binding: Sender cannot reveal a different value m'.
-
Zero Knowledge Proof (ZK): A cryptographic protocol which allows a designated party (called the Prover), having a private witness w, to generate a proof \pi asserting that w satisfies some property P i.e. P(w) = 1. Such a scheme has 3 basic properties: i) Soundness, ii) Completeness, iii) Zero Knowledge.
If the protocol involves a single message from the Prover to the Verifier, then it is called Non-Interactive Zero Knowledge (NIZK) proof. -
Secure Multiparty Computation (MPC): A cryptographic protocol which allows multiple parties P_1, \ldots, P_n, holding private inputs x_1, \ldots, x_n respectively, to interact and compute a function y = f(x_1, \ldots, x_n) in a distributed manner. The privacy property ensures that each party only learns the output y in the end and nothing else.
Summary
- In a trusted setup phase, possibly conducted by a central bank, commitments and secret shares of each bank’s balance are generated. The shares are distributed and commitments posted publicly on a bulletin board (e.g. blockchain).
- When it’s time to settle pending transactions, each bank generates secret shares and commitments to all its outgoing pending transactions. The secret shares are distributed across and commitments are posted publicly on the bulletin board.
- The protocol then runs in two phases: the Optimistic phase and the Fallback phase
- In the optimistic phase, each bank locally checks whether it has sufficient balance to net all its incoming and outgoing transactions. If so, it publicly posts a ZK range proof asserting this fact on the bulletin board.
- If all banks post such a proof, and all the proofs pass the verification check, then the optimistic phase succeeds. Now banks can locally update their own balance and also the secret shares corresponding to other banks’ balances.
- If the optimistic phase fails, banks run a fault-tolerant MPC protocol to compute the “optimal” set of partial transaction values to be netted.
Method
- Formally, we have a scenario where there are n banks. Each bank P_i has an initial balance b_i and a set of n outgoing transactions \{t_{i, j}\}_{j \in [n]}, where t_{i, j} represents the pending outgoing transaction value from bank P_i to bank P_j. You can imagine this as a directed graph as depicted below:
- Given such a transaction graph, we want to come up with a set of settled outgoing transaction values \{t'_{i, j}\}_{j \in [n]} for each bank P_i, where t'_{i, j} \in [0, t_{i, j}]. These settled transaction values should be selected in a way so that each bank satisfies a positive final balance constraint stated as follows:
$$ b_i + \sum_{j = 1}^n t’{j, i} - \sum{j = 1}^n t’_{i, j} \ge 0$$
- Essentially, the above constraint is ensuring that the final balance of each bank (which is basically the sum of the initial balance, plus all the settled incoming transaction values, minus all the settled outgoing transaction values) should be non-negative. Ideally, we would like to select such settled transaction values so that they satisfy some notion of “optimality”. One possible “optimality” criterion is to maximize the total settlement value across all banks in the system, which can be formally stated as follows:
$$ \text{Maximize} \sum_{i, j} t’_{i, j}$$
-
Our first observation is that although netting is a global optimization procedure, i.e. the optimal solution depends on the initial balance and pending transaction values of all the banks involved, we can still get away with just local checks in the optimistic case. Specifically, if we ensure that each bank individually has sufficient balance b_i to settle all of its pending incoming and outgoing transaction values, then the optimal solution just settles all the pending transactions completely, i.e. t'_{i, j} = t_{i, j}.
-
When it comes to privacy of transaction values, this observation turns out to be very useful because it enables us to use a NIZK (Non-Interactive Zero Knowledge proof) to check these local criteria while maintaining privacy. Essentially, after having each bank P_i post Pedersen commitments to their initial balance and pending outgoing transaction values, we will require them to publicly post a NIZK proof asserting the following claim:
$$ b_i + \sum_{j = 1}^n t_{j, i} - \sum_{j = 1}^n t_{i, j} \ge 0$$
-
If all the banks indeed have sufficient balance to net all of its adjacent transactions and their NIZK proof verifies, then each bank can locally update their new balance to b'_i where b'_i = b_i + \sum_{j = 1}^n t_{j, i} - \sum_{j = 1}^n t_{i, j}. Meanwhile, their public commitments to balance values can also be updated automatically, owing to the additively homomorphic nature of Pedersen commitments.
-
If some banks do not have sufficient balance to net all their adjacent transactions, and/or the NIZK proof verification of some banks fail during the optimistic phase (due to dropouts or malicious behavior), then we proceed to a fallback phase.
-
In the fallback phase, we use a generic MPC (Secure Multi-Party Computation) to compute the optimal transaction values that can be settled. To ensure fault-tolerance, we use a MPC protocol that ensures privacy and guaranteed output delivery even if a minority of n/3 banks decide to collude and disrupt the computation by engaging in arbitrary malicious behavior.
Results
-
We implemented the global optimization process using Karmarkar Linear Programming and observed that it provides a high percentage settlement compared to other techniques such as Naive and FIFO algorithms.
-
We prototyped the MPC part of our solution in MP-SPDZ framework and ran experiments with different numbers of banks using malicious shamir backend. We observe that the total running time and communication cost increase significantly as the number of banks increases.
-
The optimistic phase of our protocol is extremely efficient and can be completed on the order of milliseconds using efficient NIZK such as Bulletproofs.
Discussion and Key Takeaways
-
Using ZK as a subroutine for local checks can greatly speed up privacy preserving netting algorithms compared to executing the entire algorithm using MPC.
-
MPC serves as a fault-tolerant graceful degradation mechanism for privacy-preserving netting when the optimistic phase fails. However, the cost of this fallback MPC is really high compared to the optimistic ZK phase.
Implications and Follow-Ups
-
A nice open question is whether the fallback MPC phase can be made more efficient by designing customized MPC algorithms for solving the optimization process.
-
Another research direction is to add an auditability feature to the netting process, where a public auditor (e.g. the central bank), who is not a participant in the netting process, can verify that netting was executed correctly. This will ensure that even if all the banks collude with each other, they cannot artificially inflate the currency supply within the system.
Applicability
- The protocol proposed here can be used by local banks to settle transactions between themselves in a decentralized privacy-preserving manner without needing help from a trusted third party (e.g. the central bank).