By Hanxi Ma
Cornell Tech
In traditional way, a third-party auditor takes the responsibility to examine the bank' s balance sheet and verifies whether it misbehaves. With emerging new technology of block chain, it is possible to let the customers participate in the decentralized auditing. But how the decentralized auditing works? What is cryptographic proof of liabilities? On March 25th, Yan Ji gave us a fantastic presentation on the proof of liabilities.
Why?
Yan Ji started her presentation from solvency and insolvency of commercial banks. A commercial bank being solvent, meaning that a bank has enough assets to pay customers off. When a bank becomes insolvent as the bank makes bad investments or the bank's borrowers are not able to repay their loans, the bank's assets are worth less than the total liabilities. Even if the bank is running in the healthy state, insolvency could still occur due to a panic of customers.
Without proper regulation and protection, customers have no way to get their money back in full. Yan Ji illustrated this with the example of the Great Depression. What' s more, in a system with deposits insurance, the incentive of monitoring the bank' s behaviors is removed, which is called moral hazard. Since deposit insurance doesn't solve all the problem, it is still necessary to audit the solvency in a proper way.
Traditionally, a third-party auditor undertakes the role bears finding the total liabilities by cross checking transaction records and the company books. However, such audit provides no privacy and auditors are taking excessive work in centralized auditing. Moreover, there's a potential that the audited bank is close with the auditor like Enron case.
Here, Yan Ji introduced an alternative as decentralized auditing, which requires customers to participate in the auditing process. This enables distributed workload and distributed trust in contrast to a centralized auditing where all the work and trust rely upon the auditor. In decentralized auditing, each customer verifies if their own balance is included in the total liabilities. If some customer finds the total liabilities not equal to the sum of the individual balances; he alarms the auditor. Receiving an alarm, the auditor starts a closing investigation into the bank. However, decentralized auditing still lack privacy, including legal balanced distribution and the banks business size. Moreover, the bank could cheat on the total balances.
What?
To modify the problems above, Yan Ji illustrated by assuming there are three entities: a bank, its customers, and an auditor. When the bank claims its total liabilities, each customer can verify with proofs generated by the bank. If some proof doesn't pass verification by the customer, and he or she reports to the auditor with evidence such as the proof received from the bank, then the auditor starts a close investigation into the bank. In this problem statement, the bank is the prover. In general, the prover is the subject liable to a set of entities for certain obligations while the customers are the verifiers who are the entities the prover is liable to. The goal here is to guarantee that the reported total liabilities equal to the sum of individual liabilities so that the prover is reporting correctly.
Then Yan Ji introduced the public bulletin board to modify the problem statement. A public bulletin board is the standard assumption in cryptography. It is a piece of storage, publicly readable, and append only writable. It guarantees that people have consistent view of the data element. A blockchain is viewed as a practical implementation of a public bulletin board because of its decentralization, accessibility and reliability. Therefore, in this way, customers can simply send a transaction to a blockchain and the transaction contains the data. However, sending transactions or putting data on the blockchain is not free. In fact, it requires a significant amount of transaction fees today. This is because blockchains are decentralized systems, it requires all participants to store the same piece of data for customers. Yan Ji had a single calculation on the cost of money. It costs roughly $200 for storing one kilobytes of data.
Apart from solvency, Yan Ji explained other applications where may need proofs of liabilities like charitable donation, tax auditing, syndicated loans and disapproval voting. What's more, during the COVID 19, there's always an urgent need to monitor and check the number of infections and deaths, which helps scientists learn more about the disease and stop the spread and find a cure. So here a hospital may collect the data, announced the total confirmed cases, and allow participants to verify if the number is correct. The common characteristic of these applications is there's no incentive for the prover to overstate the number. This feature affects the problem statement significantly. Originally, we will want to guarantee that the reported total liabilities exactly equal to the sum of individual liabilities. However, given a feature that the prover has no incentive to increase the total liabilities, the requirement can be relaxed. Instead of requiring the reported total liabilities equal to the sum of individual liabilities, the proof it only needs to prove that the claim to the liabilities is worth no less than a sum of individual liabilities. This is a weaker requirement than the equivalence relation, which opens up the possibility of simpler solutions to this problem.
How?
Yan Ji started this part by introducing a strawman solution, which lets the prover or the bank to simply publish the whole de-identified balance book on the blockchain or the public bulletin board. Thus, customers can check the data on the blockchain and see if their balances aren't included in the total liabilities. However, this scam cannot provide privacy of individual liabilities, since everyone can learn the balanced distribution of the bank. A scheme called provisions is proposed to provide better privacy guarantee. In this scheme, the bank commits to each user's balance and publishes the commitments. Crypto commitments provide two properties: binding and hiding. Binding means that the prover cannot open a commitment to a different value. Hiding means that the verifier cannot guess the value before the prover opens commitments. Provisions utilizes the cryptographic commitments to provide privacy of individual liabilities. Since the commitments provide hiding property, individual balances are not revealed to anyone. Therefore, provisions achieve privacy of liabilities. However, since the number of commitments is public, the number of customers, which is sensitive information should be avoid of the bank's business size is public. And the cost on public bulletin board is too high too.
Here, Yan Ji introduced her team' s work DAPOL+, which is the refined construction based on the basic idea to commit to each user' s balance first, then construct a sparse Merkle tree and publish the tree root only. Merkle tree is the data structure efficiently proves inclusion of a set member. It is a binary tree. Each node contains a value which is a hash of the values of its child nodes. Note that a hash function is collision resistant. Meaning that it's hard to find x and y such that their hash results are the same. To make a proof more efficient, the prover generates a Merkle tree. Each bottom layer leaf node of the Merkle tree contains the hash of a set's elements. Instead of sending the whole set, the prover only needs to set logarithmic size of data to prove setting inclusion. In ordinary Merkle trees, values are mapped to bottom-layer leaf nodes from left to right to the trace compact. Hence, if a value is mapped to the rightmost leaf node, then people can infer the size of the set. However, in a sparse Merkle tree, values are matched to bottom layer leaf nodes randomly. No one can learn anything about the actual population.
Having knowledge of both cryptography commitments and sparse Merkle Trees. Yan Ji explained DAPOL+ in details. Similar as a Provisions the bank commits to each user's balance, then maps each user to a bottom layer leaf node of the binary tree and generates sparse Merkle tree. The root node now contains the sum of the individual commitments, which is also commitment to the total liabilities. Now the bank publishes the Merkle root or says it to a blockchain. A commitment to its total liabilities with proof on the public bulletin board. Each verifier can acquire Merkle proofs with auxiliary data on the blockchain. Verifiers can verify the inclusion of their balances in the bank's total liabilities. So same as probations, DAPOL+ guaranteed privacy of liabilities with cryptographic commitments. It also achieves privacy of number of users with sparse Merkle trees. Meanwhile, only the Merkle root needs to be committed on the public bulletin board. This game is also practical, not only on the cost of public bulletin board, but also in terms of resource consumption for each verifier. For a bank with a million users and using a tree of height three cubed, the data to be put on a bulletin board is of 64 bytes, and each user receives a proof of a few kilobytes, which is tolerable on a mobile device.
In the end, Yan Ji extended a concept of failure probability. The intuitive idea here is that the failure probability is the probability that a cheat doesn't get caught. If the prover manipulates the liability of five accounts, then only like 50 percent of the verifies needs to actually do the verification to guarantee a very low probability of failure.
Summary
First of all, proof of liabilities is a common problem in auditing for a wide range of applications, not limited to solvency. Secondly, decentralist auditing is actually proven possible and the protocol at least foolproof liabilities. And from the pass of during this project, Yan ji advised that research goals actually evolved with the development of new technologies. Originally, proof or liabilities is proposed for auditing solvency of cryptocurrency exchanges. But then people realized that there are common features in many different applications. Therefore, the goal is to generalize this crypto primitive as much as possible applications. Secondly, as block chain becomes a new protocol implementation of public bulletin board, the goal of Proof of liabilities also includes the goal to minimize costs on the public bulletin board.