# 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).
8 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.

3 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].

8 Likes

@Ulysses Thanks for the comments and questions! Here is what I think:

1. The primary reason for adopting ZK rather than MPC for doing the local check was efficiency. Regarding privacy, actually MPC would be “more secure” than using ZK for local checks in the following sense: Using MPC, we can find out whether some bank has a low balance without having to reveal the identity of the bank. However, the ZK solution actually leaks the identity of honest banks having low balance. In practice, this leakage might not be a big concern though depending on the use case.

2. The Naive algorithm basically either settles all the transactions (if the positive balance constraint is satisfied) or settles none of the transactions (if the positive balance constraint is not satisfied). The FIFO (First In First Out) algorithm assumes that all transactions have a pre-defined priority ordering and it settles them in that order. This means that lower priority transactions will not be considered for settlement before higher priority transactions. Both these algorithms offer sub-optimal settlement guarantees.

Karmarkar Linear programming approach is an optimal algorithm for maximing a given criteria (here the total settlement value) subject to some linear constraints (here the positive final balance constraint). Therefore, it performs better (in terms of percentage settlement) than the other two algorithms.

1. When all the parties are dishonest, it is unclear what “privacy” even means. However, in such a scenario, it might still be worth ensuring “correctness of computation”. For e.g. suppose the current solution were to be deployed in the real world and somehow all the banks end up being dishonest during the netting procedure. Then they will be able to artificially inflate their balance without anyone noticing (because there is no honest bank to check their ZK proofs or ensure that MPC is happening correctly). This kind of scenario will be disastrous from an economic standpoint. One possible solution to this is to use Publicly Auditable MPC where an external auditor (such as the central bank) can chose to audit the MPC computations without having to participate in the MPC at all. It is a sort of “proof of correct MPC” which anyone in the public can verify, thus holding the banks accountable for any adversarial behavior.
3 Likes

@amit , thanks for your decisive responses.

The solution of using the Publicly Auditable MPC for the case of dishonest parties sits well with me.

3 Likes

Thank you @amit for the research summary. I have been battling with this research paper to understand how netting is used in the real world,
Let me give a context of my understanding, take for instance that Investor A owes $50,000 to Investor B, and Investor B owes$110,000 to Investor A. In such a case, we are assuming the settlement date of both transactions and the currency of exchange is the same. Instead of Investor A and B making two separate payments to each other, the transaction values can be netted.
As a result, Investor B would pay \$60,000 (net amount) to Investor A, whereas Investor A does not need to pay anything to Investor B. It is an example of settlement or payment netting.

Secondly, I was able to understand that Secure multi-party computation (MPC or SMPC) is a cryptographic protocol that distributes a computation process across multiple parties, where no single party can view the data of others. In other words, MPC allows the joint analysis of data without sharing them.

In addition, I think A ZK proof must fulfill two basic requirements known as completeness and soundness. Completeness refers to the ability of the prover to demonstrate knowledge of the relevant information to a high degree of probable accuracy. For the proof to be sound, the verifier must be able to reliably determine whether or not the prover is actually in possession of the information. Further more, in order to be truly zero-knowledge, the proof must achieve both completeness and soundness without the information in question ever being communicated between the prover and the verifier.

I think that a decentralized Exchange would provide an open
reduce systemic risk of centralized exchanges.

Though my thoughts and understanding of the paper but subject to learn further from you.

Lastly, do you think that Rialto would provide confidentiality to the trade rates and the account balances and unlinkability between the trades and the traders?

3 Likes

The banking industry would benefit greatly, in my opinion, from a web3 solution to netting because it would minimize the requirement for financial system to still be present in trade clearance. It may be informative to see if any additional web3 applications could be connected also with netting to make it that much more “function,” for illustration.

1 Like

Hi @Henry I’m really interested in giving some answers to your questions. However, I’m trying to reconcile the term Rialto in relation to your comment.

Is Rialto an exchange? Can you throw more light on that?

2 Likes

Hi @Yeoriton56 thanks for your question. In responding to your question, yes, Rialto is an Exchange.

Let me give a background of my understanding with the term Rialto.
Rialto (XRL) is an Ethereum based ERC20 token being developed.
It is a stage with computerized calculations for digital currency exchange, advertise making, and expectation trading.

Rialto uses the balancing system of storing majority of its funds in cold wallets and only transferring the optimal amount needed for positions. The optimal balance is constantly recalculated to signal the need before the spilling effect among the exchanges.

Furthermore, RIALTO carefully selects only reliable exchanges that pass thorough demanding background check (known owners, compliance, secure access points, audit, etc.).

infact it goes beyond just arbitrage in Bitcoin, it can easily do the same for other crypto currencies if the market conditions are right. The algorithms monitor the market order books 24/7 and only enter a trade when the parameters enable profitable execution. Their market information can be monetised further in different formats.

Ultimately they could become the go to exchange to acquire coins at their true global price. it provides a wide range of advanced tools for traders.

So as decentralized Exchange, I believe it would provide an open
reduce systemic risk of centralized exchanges.

1 Like

@Henry Since Rialto is a decentralized exchange, I do not think they will need a netting service. Trades on decentralized exchanges occur between traders and liquidty pools. There is no difference to settle.

Netting primarily is employed on centralized monetary authorities that inter transact. So if Netting should be employed on exchanges, it will most likely be cross-chain transactions, if it really is necessary.

Since Rialto is a decentralized exchange, all activities recorded on it is a public record. So anyone can actually see what is going on by virtue of public blockchain’s open nature.

2 Likes

Thanks @Yeoriton56 for your quick response and further clarification. I didn’t know that netting can be employed in centralized monetary authorities that inter transact. I was actually thinking that it could be possible in the other way round.

I must say that I learnt something from you today.

“In learning you will teach, and in teaching you will learn.”

Phil Collins

1 Like

Thanks for sharing this interesting article @amit

This was actually my first time learning about this subject, so further research was necessary from my end.

Banks settle their liabilities to each other through inter-bank payment systems generally managed by their country’s central bank. The central bank opens an account for the local banks in its jurisdiction and enforces that each account maintains a certain level of liquidity to accommodate future settlements. Upon receiving a payment instruction, say bank A transfers x home currency to bank B, and the central bank deducts x from A’s account while adding x to B’s account.

Financial institutions are embracing blockchain technology to address challenges in traditional Real Time Gross Settlement (RTGS). Given the slow settlement of inter-bank payments in practice, which takes roughly a couple of days, and the requirement that all participants be online at the time of resolving gridlock, what do you think is a solution or a better way for participants to immediately resolve gridlocks once they occur?