Proof of Innocence
Proof of Innocence is a ZK Proof that RAILGUN users generate to prove that their withdrawals are not a part of a predefined list of addresses or transactions. For example, if law enforcement or a regulatory agency like OFAC maintains a list of addresses known to be related to illegal activity, RAILGUN users can take this input data and generate a proof that displays to the outside world their funds are legitimate.
This proof does not reveal anything else about the user like address, history, or balances and enables compliance whilst preserving privacy. It also preserves the open, permissionless nature of RAILGUN as it does not introduce any centralization gateways or transaction screening to achieve compliance.
Proof of Innocence will sit beside existing RAILGUN ZK cryptographic systems. Each RAILGUN 0zk balance is comprised of a set of encrypted UTXOs organized via a private Merkle Tree.
Each time you send a RAILGUN private transaction such as a Private Send, you generate a zk-SNARK proof through cryptographic circuits that you have sufficient UTXOs in your balance to send the transaction. If your UTXO balance is enough to fulfil the transaction, then it is valid and the Merkle Tree updates with the new change in balance and state.
The RAILGUN Merkle Tree is thus an accumulator of previous history within the transaction system. Using the Merkle Tree data structure, it is possible to commit many different assertions about balances and addresses without revealing those balances and addresses. The current RAILGUN Merkle Tree is perfect for proving that a balance is a part of a transaction set to enable valid fund transfers, but it can’t in its current form prove that a transaction is NOT a part of a transaction set. To do this, we need a sparse Merkle Tree.
A sparse Merkle Tree is like its more familiar cousin, but its underlying data is indexed. For empty values, a regular Merkle Tree will contain an empty leaf whereas a sparse Merkle Tree has a NULL value, meaning it does not exist and is not a part of a dataset. By organizing a list of addresses and transactions into a sparse Merkle Tree, we can build a proof that checks if a deposit is or isn’t part of this list.
As the underlying data is indexed, data should have an expected location. If we hash the transaction data, we can then follow the sparse Merkle Tree from the root to the node & leaf where we expect the impugned transaction to be. If the node is NULL, then the transaction is not a part of the set and is therefore not a part of a blacklist. A Merkle proof of non-interaction is then the combination of hashed sibling nodes from the root to the leaf.
zk-SNARKs are verifications that a computation has occurred correctly or that some piece of information is correct. They require the verified computation to be condensed into a circuit. Since the act of verification is itself a computation which can be expressed as a circuit, a zk-SNARK can verify other SNARK proofs. It’s a SNARK of a SNARK.
A recursive SNARK verifies that a proof below it in the chain has been computed correctly. As RAILGUN allows for intermediate 0zk balance transfers between deposit and withdrawal and each of these transactions is itself a proof, Proof of Innocence needs a recursion mechanism to assert further statements about these existing proofs.
Due to these intermediate transaction types, RAILGUN Proof of Innocence must compute proofs for all previous flow of funds leading up to a withdrawal and it also has more details to account for than a protocol with solely deposits and withdrawals. Likewise, for Private Swaps and DeFi, as funds leave the smart contract and are redeposited via the RelayAdapt module, breaking the connection between transactions, every swap must be connected to the web of transactions around it via a history accumulator.
Recursive SNARKs can prove the entire flow of funds from the initial deposit satisfies the conditions of the Merkle proof of non-inclusion. Proof of Innocence will compute proofs for every leaf in the regular Merkle Tree that apply to a balance of UTXOs and account for intermediate transactions between deposit and withdrawal. This is done through recursive SNARKs which tie the whole proof together.
As Proof of Innocence is still in early stages of development, the exact architecture may change as Chainway and RAILGUN contributors progress, however, the above concepts will form the building blocks of Proof of Innocence.
Here’s how a user flow would generally work:
- 1.Take list of addresses and transactions.
- 2.Organize this data into a sparse Merkle Tree.
- 3.Generate a recursive SNARK proof that user deposits are not a part of the sparse Merkle Tree of ‘bad’ deposits.
- 4.Take this Proof of Innocence to verify to third parties or anyone interested that your RAILGUN transactions are legitimate.
In future, Proof of Innocence could be expanded to give risk scores for a more granular viewpoint such as Low, Medium, or High Risk depending on the % of UTXOs a user has from the ‘bad’ deposit transaction set. Taking this a step further, Proof of Innocence could also help a user quarantine ‘bad’ UTXOs that they’ve received inadvertently such as from a ‘dusting’ attack where a bad actors sends small amounts of cryptocurrency to many innocent users.
Last modified 3mo ago