Research Summary: Privacy Preserving Decentralized Netting

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).
4 Likes

@amit how big of an impact would a web3 solution to netting have on the banking industry? It sounds like an enormous use case for web3.

@jmcgirk That’s a good question! Currently, the netting protocol makes use of both ZK proofs and MPC. While it is relatively straightforward to deploy the ZK specific step on the blockchain (as has been done in prior work), it is unclear how to perform MPC in a blockchain ecosystem. Current fault-tolerant MPC protocols require an honest majority assumption among the MPC servers. Maybe this is possible if you are in a permissioned setting where you can dedicate some specific nodes to perform MPC computation (under the assumption that only a minority of those nodes will be corrupt).

Also, there are some papers (see this and references therein) which study the possibility of MPC in a blockchain-like setting but I am not familiar with any real-world deployment of such a system. So I guess the next step for the community would be to figure out how to integrate MPC into the blockchain world in a secure and scalable way. This seems like a precursor to deploying the netting protocol using a web3 solution.

Having said that, I think a web3 solution to netting would be immensely useful for the banking industry as it would remove the need for a central bank to be involved (except maybe for the setup phase) for doing transaction settlement. It might also be interesting to see if other applications on web3 can be integrated with the netting part to make it more “feature-rich”, for example, integrating a web3 decentralized “reputation system” with the netting protocol to assign priorities to the transactions e.g. a transaction originating from a bank with higher reputation will be assigned a higher priority during the netting process compared to a transaction originating from a lower reputation bank.

2 Likes

@amit This is an intriguing practical application of blockchain and cryptography in solving real life problems. Thanks for this wonderful research.

I recall that in @Tony_Siu’s Summary on “Do You Need a Blockchain?”, he distilled three criteria laid out by the researchers on when to use blockchain technology for solving a problem.

This research by @amit validates the criteria and provides some hints on @jmcgirk’s question on when not to use blockchain. This is how this paper follows the criteria:

1.The first criterion was that there has to be multiple parties involved for blockchain to be used in solving a problem. In this case, there were multiple local banks involved in solving the netting problem.

2.The parties should not mutually trust each other. The local banks, in this case, did not mutually trust each other.

3.The parties do not want the services of a trusted third party due to trust issues. In this case, due to trust issues, the local banks did not want the mediation of the central bank in solving this problem.

For further practical insights on the application of blockchain to solving the netting problem, I will reference a practical solution of netting using blockchain by IBM. Although this case is not exactly like the one in the paper, it provides a reasonable insight on how blockchain is already solving the netting problem in the financial sector.

@amit In Addition, I have a few questions:

1.Apart from the low-cost and better-speed advantages of Zero Knowledge Proof, are there other reasons for which it was chosen over Secure Multiparty Computation for local checks? Could there have been security or privacy reasons, or some other considerations?

2.What is special about the Karmarkar Linear Programming that gives it a high percentage settlement over the Naive and FIFO algorithms for the optimization process?

3.For further research, I have an idea. From the present research, there were two methods suggested for solving this netting problem, the Optimistic Phase and the Fallback Phase. The Optimistic Phase is to be applied when all parties are honest, while the Fallback Phase is to be employed when some parties are dishonest. In a situation where all parties are dishonest, what would be the possible method of solving the netting problem?

If no answer comes to mind, I suggest that the option could be considered for further research.

References
Dickson, A. (2020) Streamlining Financial Netting with Blockchain. IBM Supply Chain and Blockchain Blog[online]. Available at: https://www.ibm.com/blogs/blockchain/2020/12/streamlining-financial-netting-with-blockchain/ [Accessed 2nd August 2022].

2 Likes