Alternative approach to zkSnark design replacing user specific proof with a unique proof.

[enricobottazzi]

The actual circuit implementation is available in pyt-circuits/alt-approach.

The bigger limit of this implementation is due to the fact that it requires to build a whole Merkle tree inside the circuit making it highly inefficient. A similar approach is used by MACI and it would be interesting to know how they seek to solve this problem. @gurrpi

This new approach requires a different userflow:

The customer of the Proof of Solvency is the exchange. The atomic actions performed by the exchange are:

• Send salt to each user
• Generate a unique proof of solvency starting from the database of its users and verify that on-chain
• Publish on IPFS the list of the Users Combos (username, salt, balance) that were included in the proof of solvency

• 1. Proof of Assets

  The exchange requires to prove ownerhsip of an address with a certain amount of assets. In order to do so, the exchange needs to sign H(poSolID, address) where

  • poSolID is a sequential nonce stored inside the Verifier Smart Contract (VSC) and is unique for each Proof Of Solvency process.
  • address is the address controlled by the exchange

  The signature of the message is sent to the VSC that will check whether the message signature matches the required criteria such as:

  • poSolID matches the current nonce stored inside the VSC.
  • address matches the address of the signer.

  By signing this message, the Exchange is authenticating the following information: “I, Exchange, am attesting that I own address and this information will be used as part of the Proof Of Solvency poSolID ”.

  On signature verification, the address gets associated to the poSolID. This value is locked and cannot be changed afterwards.

  Attack Vector: At this point the exchange can bribe someone (ideally owning a large amount of assets) to sign the message on its behalf

• 2. Share Salt

  The exchange shares a salt to each of its users. The salt is a random integer between 0 and 1’000’000. It is important that the salts being distributed to the users do not leak as it will reveal sensible business information of the exchange (and its users) to the public. Communication of these salts is believed to be done through secure channels, but if a malicious party were to intercept it, they may also gain access to other sensitive information like a user's password, which would result in much larger problems not related to this document

  Attack Vector: the salt is too short and the userId and balance can be brute forced starting from the User Combo published on IPFS in step 3

• 3. Publish userCombos

  The exchange sorts its users by their username, salt and balance (of a certain assets)

  username	salt	balance
  alice	3490430	3223
  bob	3234	100234
  carl	1111023	42069

  Each entry of the table is hashed through Poseidon Hash

  userCombo = H(usernameToBigInt, salt, balance). The username is first parsed into its utf8 bytes representation and then converted to BigInt.

  The resulting list of this operation is then published to IPFS

• 4. Store IPFS CID

  The exchange stores the CID of the IPFS content storing its userCombos inside the VSC. This gets associated with the poSolID. This value is locked and cannot be changed afterwards. The immutability of the content stored on IPFS ensures that Exchange, or any other actor, do not manipulate the entries of the list.

• 5. Generate zk PoSol

  The exchange generates the Proof of Solvency inside a zkSNARK. The SNARK takes the user entries usernameToBigInt, salt and balance together with the targetSum (the total assets owned by the exchange) as inputs and perform the following operations:

  • Perform the posiedon hash on each entry to get the userCombo
  • Build a Merkle Tree starting from the userCombos and compute the userComboTreeRoot
  • Sum together all the balance to get to the aggregatedSum of users’ balances
  • Verify that targetSum is greater or equal than aggregatedSum
  • Output the userComboTreeRoot
  

  The proof, together with the public signals, is sent in Solidity Call Data format to the VSC calling the verifyPoSol function

• 6. Verify zk Posol

  The smart contract performs different types of check inside the verifyPoSol function

  • verify that the targetSum used as public input to the SNARK matched the amount of assets owned by the address associated with the current poSolID
  • verify the validity of the proof
  • associated the output of the proof, namely userComboTreeRoot to the poSolID. This value is locked and cannot be changed afterwards.

• 7. Compute Root from userCombos and verify it matches

  At this point Alice must verify that the actual list posted on IPFS is valid and these entries are actually the ones used by the exchange to generate the proof in step 5. In order to do so, Alice must compute the Tree Root from the UsersCombos available on IPFS and verify that it matches the userComboTreeRoot stored associated to the current poSolID inside the VSC. The action can be performed by everyone, even by someone who is not an user of the exchange as all the input data are publicly available, and it doesn’t need to be repeated by each user.

• 8. Verify aliceCombo is in userCombos

  This is the only action that needs to be actively and necessarily performed by a user in order to verify that the exchange is solvent. Alice needs to start from its personal information `username` , `salt` and `balance` , compute `aliceCombo = H(usernameToBigInt, salt, balance)` and verify that `aliceCombo` is included inside the `userCombos` published on IPFS. If the verification is valid, Alice is confident that the exchange she has been included inside the liabilities of the exchange.

  Its important to underline that in order to verify the Solvency of the exchange, the user only needs to verify that their combination were included in the list published on IPFS. This verification doesn’t require any interaction with the Exchange, so the exchange is not able to tell which user has verified their proof of solvency and which has not.

  This feature avoids that the exchange would be able to tell which are the “lazy” users that do not verify their inclusion in the list and, therefore, excluding them from the list the next time and understating their total liabilities.