Zero-Knowledge Proofs for Asset Verification

Introduction

Many cryptocurrency users rely on centralized exchanges for trading and conversion operations. These platforms offer significant convenience and speed, leading to their proliferation since Bitcoin's inception. However, this growth has been accompanied by frequent incidents of fraud and malicious exit scams. Netflix even produced a documentary highlighting one such case: a sudden exchange collapse and the mysterious death of its founder¹. The 2022 bankruptcy of FTX due to insolvency further shocked the world, causing massive losses for users and investment firms.

Financial fraud is not unique to cryptocurrencies. Traditional sectors have also seen numerous accounting scandals, such as the Enron collapse in the early 2000s. Despite being celebrated for innovation, Enron's rapid bankruptcy revealed systemic deception. Similarly, companies like Evergrande have misappropriated funds intended for specific projects, leaving stakeholders with significant losses.

A common thread in these frauds is the lack of transparency in auditing and accounting processes, which creates opportunities for corruption and manipulation. However, complete disclosure of financial data is often impractical due to privacy and competitive concerns. While increased regulation is one approach, zero-knowledge proof (ZK-proof) technology offers a promising alternative solution.

If individual users could verify their own asset holdings without exposing private details, widespread participation would make financial fraud exceedingly difficult. Since the verification process is zero-knowledge, intercepted data reveals nothing about actual assets, allowing public verification over networks. This technology democratizes auditing, moving it from exclusive, private firms like the "Big Four" to a participatory process involving all stakeholders.

Summa² is a research project by Privacy Scaling Explorations (PSE) that explores ZK-proofs for user asset verification. This article outlines the project and its underlying technical principles.

Smart Contract Architecture

Summa's data flow involves smart contracts that store and verify public data. While the current implementation uses Ethereum, it could be deployed on other blockchains like Solana, provided Halo2 proof generation is supported³.

The custodian (e.g., a centralized exchange) deploys the contract, which it owns. The contract stores two types of public data submitted by the exchange:

1. Address Ownership Proofs: These demonstrate the exchange's control over specific blockchain addresses.

   struct AddressOwnershipProof {
       string cexAddress;
       string chain;
       bytes signature;
       bytes message;
   }

2. On-Chain Asset Information: This includes the Merkle sum tree's root hash and root balances (e.g., total BTC holdings). These serve as public inputs for ZK-proof verification.

   function submitCommitment(
       uint256 mstRoot,
       uint256[] memory rootBalances,
       Cryptocurrency[] memory cryptocurrencies,
       uint256 timestamp
   ) public onlyOwner {
       // ...
   }

Both datasets are publicly verifiable on-chain, making it difficult for exchanges to manipulate them. Users can compare contract-stored data with actual blockchain records.

Proof generation is currently handled by the exchange. Users submit verification requests, and the exchange returns a proof. Users then submit this proof to the smart contract for verification. The verification contract is compiled from Halo2 circuits into Solidity code and deployed separately.

fn main() {
    let circuit = MstInclusionCircuit::<LEVELS, N_CURRENCIES, N_BYTES>::init_empty();
    let (params, pk, _) = generate_setup_artifacts(11, Some("../backend/ptau/hermez-raw-11"), circuit.clone()).unwrap();
    // ... Solidity code generation and compilation
}

During verification, the contract checks the proof against public inputs:

try inclusionVerifier.verifyProof(proof, publicInputs) returns (bool result) {
    return result;
} catch (bytes memory /*lowLevelData*/) {
    require(false, "Invalid inclusion proof");
    return false;
}

Merkle Sum Tree Construction

Summa's core component is a Merkle sum tree composed of user assets. The tree's root node is stored on-chain for verification.

Each leaf node represents a user's assets at a specific timestamp, including their username or exchange address. Leaf data is stored by the exchange and can be retained by users (e.g., via screenshots), making manipulation difficult.

Poseidon Hash⁴ is used instead of traditional hash functions due to its efficiency in ZK-proof systems. Unlike bit-operation-heavy hashes, Poseidon relies on addition and multiplication, which are better suited to Plonk-based systems like Halo2.

Poseidon Hash involves parameter preparation and hashing phases⁵. Parameter preparation uses a linear-feedback shift register (LFSR)⁶, which involves bit operations but is a one-time process. The actual hashing uses only addition and multiplication:

def s_box(self, element):
    return element ** self.alpha

def full_rounds(self):
    for r in range(0, self.half_full_round):
        for i in range(0, self.t):
            self.state[i] = self.state[i] + self.rc_field[self.rc_counter]
            self.rc_counter += 1
            self.state[i] = self.s_box(self.state[i])
        self.state = np.matmul(self.mds_matrix, self.state)

To prevent overflow in finite field arithmetic, data undergoes range checks before tree construction. The range check circuit decomposes values into 8-bit chunks, enabling efficient lookup tables without excessive resource consumption.

Each user's data is an Entry:

pub struct Entry<const N_CURRENCIES: usize> {
    username_as_big_uint: BigUint,
    balances: [BigUint; N_CURRENCIES],
    username: String,
}

Entries are converted into nodes for tree construction. Leaf node hashing combines the username and all balances:

pub struct Node<const N_CURRENCIES: usize> {
    pub hash: Fp,
    pub balances: [Fp; N_CURRENCIES],
}

pub fn leaf_node_from_preimage(preimage: &[Fp; N_CURRENCIES + 1]) -> Node<N_CURRENCIES> {
    Node {
        hash: Self::poseidon_hash_leaf(preimage[0], preimage[1..].try_into().unwrap()),
        balances: preimage[1..].try_into().unwrap(),
    }
}

Intermediate node hashing combines left and child balances and hashes:

fn build_middle_level<const N_CURRENCIES: usize>(level: usize, tree: &mut [Vec<Node<N_CURRENCIES>>]) {
    let results: Vec<Node<N_CURRENCIES>> = (0..tree[level - 1].len())
        .into_par_iter()
        .step_by(2)
        .map(|index| {
            let mut hash_preimage = [Fp::zero(); N_CURRENCIES + 2];
            for (i, balance) in hash_preimage.iter_mut().enumerate().take(N_CURRENCIES) {
                *balance = tree[level - 1][index].balances[i] + tree[level - 1][index + 1].balances[i];
            }
            hash_preimage[N_CURRENCIES] = tree[level - 1][index].hash;
            hash_preimage[N_CURRENCIES + 1] = tree[level - 1][index + 1].hash;
            Node::middle_node_from_preimage(&hash_preimage)
        })
        .collect();
    // ...
}

The complete tree structure is:

pub struct MerkleSumTree<const N_CURRENCIES: usize, const N_BYTES: usize> {
    root: Node<N_CURRENCIES>,
    nodes: Vec<Vec<Node<N_CURRENCIES>>>,
    depth: usize,
    entries: Vec<Entry<N_CURRENCIES>>,
    cryptocurrencies: Vec<Cryptocurrency>,
    is_sorted: bool,
}

Zero-Knowledge Proof Generation

The ZK-proof verifies that a user's entry exists in the Merkle tree. For a given entry index, the proof generation constructs necessary data:

fn generate_proof(&self, index: usize) -> Result<MerkleProof<N_CURRENCIES, N_BYTES>, Box<dyn std::error::Error>> {
    let nodes = self.nodes();
    let depth = *self.depth();
    let root = self.root();
    if index >= nodes[0].len() {
        return Err(Box::from("Index out of bounds"));
    }

    let mut sibling_middle_node_hash_preimages = Vec::with_capacity(depth - 1);
    let sibling_leaf_index = if index % 2 == 0 { index + 1 } else { index - 1 };
    let sibling_leaf_node_hash_preimage: [Fp; N_CURRENCIES + 1] = self.get_leaf_node_hash_preimage(sibling_leaf_index)?;
    let mut path_indices = vec![Fp::zero(); depth];
    let mut current_index = index;
    for level in 0..depth {
        let position = current_index % 2;
        let sibling_index = current_index - position + (1 - position);
        if sibling_index < nodes[level].len() && level != 0 {
            let sibling_node_preimage = self.get_middle_node_hash_preimage(level, sibling_index)?;
            sibling_middle_node_hash_preimages.push(sibling_node_preimage);
        }
        path_indices[level] = Fp::from(position as u64);
        current_index /= 2;
    }
    let entry = self.get_entry(index).clone();
    Ok(MerkleProof { entry, root: root.clone(), sibling_leaf_node_hash_preimage, sibling_middle_node_hash_preimages, path_indices })
}

The circuit structure for inclusion proof is:

pub struct MstInclusionCircuit<const LEVELS: usize, const N_CURRENCIES: usize, const N_BYTES: usize> {
    pub entry: Entry<N_CURRENCIES>,
    pub path_indices: Vec<Fp>,
    pub sibling_leaf_node_hash_preimage: [Fp; N_CURRENCIES + 1],
    pub sibling_middle_node_hash_preimages: Vec<[Fp; N_CURRENCIES + 2]>,
    pub root: Node<N_CURRENCIES>,
}

Key constraints include swap constraints (ensuring correct sibling ordering) and balance constraints (parent balances equal the sum of child balances). Swap constraints use path indices to determine left/right positioning:

meta.create_gate("swap constraint", |meta| {
    let s = meta.query_selector(bool_and_swap_selector);
    let swap_bit = meta.query_advice(col_c, Rotation::cur());
    let element_l_cur = meta.query_advice(col_a, Rotation::cur());
    let element_r_cur = meta.query_advice(col_b, Rotation::cur());
    let element_l_next = meta.query_advice(col_a, Rotation::next());
    let element_r_next = meta.query_advice(col_b, Rotation::next());
    let swap_constraint_1 = s.clone() * ((element_r_cur.clone() - element_l_cur.clone()) * swap_bit.clone() + element_l_cur.clone() - element_l_next);
    let swap_constraint_2 = s * ((element_l_cur - element_r_cur.clone()) * swap_bit + element_r_cur - element_r_next);
    vec![swap_constraint_1, swap_constraint_2]
});

The entire proof process involves layer-by-layer data processing, with circuit constraints ensuring correct tree construction. The output root hash and total balances must match on-chain data.

Solvency Verification

Currently, proof generation is exchange-mediated: users request proofs, which exchanges generate and return. Future developments might enable user-side proof generation without exchange involvement. The Halo2 circuit could be compiled to WebAssembly, with APIs via ethers-rs⁷. Since Merkle tree root verification is O(log n), user devices could handle it efficiently, enhancing decentralization and security.

👉 Explore advanced verification methods

Frequently Asked Questions

What is a zero-knowledge proof?
A zero-knowledge proof allows one party to prove to another that a statement is true without revealing any information beyond the validity of the statement itself. In asset verification, it enables users to confirm their holdings are included in a reserve without exposing sensitive data.

How does Summa improve audit transparency?
Summa uses Merkle sum trees and ZK-proofs to let users independently verify their assets are backed by exchange reserves. This collective verification reduces the risk of undetected fraud, as many participants can validate the system without relying on centralized auditors.

Can exchanges cheat the system?
Exchanges cannot alter on-chain data without detection, as the smart contract stores verifiable commitments. Any discrepancy between reported reserves and actual assets would be caught during user verification processes, making manipulation highly difficult.

What blockchains support this technology?
While initially designed for Ethereum, Summa's architecture is blockchain-agnostic. It can be deployed on any chain supporting Halo2 proof verification, including Solana and other EVM-compatible networks.

Is user data exposed during verification?
No. Zero-knowledge proofs ensure that verification reveals no information about individual user balances or identities. Only the proof's validity is checked against public inputs.

What are the computational requirements?
Proof generation is resource-intensive and currently handled by exchanges. Verification is lightweight and can be performed on-chain or by user devices, making it accessible for widespread use.

References