Abstract
We explore a decentralized proving architecture for Curvy, a privacy-preserving protocol based on stealth-address UTXOs and ZK aggregation. We identify a problem arising from concurrent state updates to a shared Sparse Merkle Tree (SMT) root, and propose an on-chain slot-based sequencing mechanism for provers. We analyze denial-of-service risks introduced by this approach and propose collateral-backed participation and request throttling as mitigations.
Background
Curvy protocol allows private transfers using stealth address transfers and ZK proofs. As each received transfer ends on a different stealth address, Curvy enables aggregation of funds using a ZK aggregator without revealing the funds’ origin to the public. However, a single centralized prover would be able to gather information on all transaction graph sections, thus reconstructing the origins of all funds. To prevent this kind of privacy leak, we are investigating decentralized provers that can individually create their own aggregation proofs or submit batch proofs from multiple users.
The funds from stealth transfers are represented in a UTXO manner as notes. Each note is stored in an SMT, and the current SMT root is kept in the aggregator smart contract. Note IDs (tree leaves) are emitted through events. Each client can listen to events and reconstruct the tree. Aggregation is a process in which existing notes are destroyed, and new notes are created, having the balance of the output notes equal to the sum of all input note balances. Each aggregation creates new notes and updates the notes tree, backed by the ZK proof testifying to the correctness of the update.
Problem Statement
Computing the aggregation proof requires providing both the old and new SMT root, computed after all new notes are correctly inserted. Due to the sequential nature of the on-chain root updates, if multiple provers try to modify the SMT based on the same old root, only the first prover would be able to successfully do the operation, while transactions of all other provers would be reverted. Even if a prover is indeed the first to submit the transaction, non-deterministic transaction ordering may cause the prover’s transaction to not be the first in a block, and the transaction may revert. Reverted transaction with only two (old and new) root values and Groth16 proof data in calldata cost ~33000 gas. Even though the cost is not significantly high, repeated transaction does not guarantee success even with the updated roots and corresponding proof.
Slot-Based Prover Sequencing
To mitigate the collisions resulting in multiple provers referring to the same old state, we propose the introduction of an on-chain request queue, where provers would first apply for a time slot in which they can submit their state updates. A time slot refers to an interval [fromBlockNumber, toBlockNumber] associated with a given message sender. Provers can submit their proofs only when the current block number is within the range of their time slot.
This way, the natural sequence of updates is maintained on-chain, and provers can determine their proving slot. Waiting time is also known in advance, meaning that provers can save time on constant state polling and event listening. The “sign-up” operation is a low-cost operation compared to reverting transactions carrying the ZK proof and public data. This solution prevents collisions but allows DOS attacks on the smart contract, having malicious users occupying a large number of slots using relatively small funds.
Skipped time slots are not reusable. If a prover misses the given slot, a new slot needs to be requested. The timeframe of a slot needs to be properly estimated. Slot start time needs to be delayed for at least the time required for generating Groth16 proof, while end time needs to provide a proper buffer, taking into account network latency. Exact values are yet to be determined. Slot overlaps are not allowed.
If a prover, for some reason, submits an invalid proof, the slot is still active until the slot deadline, allowing the prover to submit the corrected proof.
Collateral-backed provers
The source of the DOS attack possibility lies in the low cost of slot requests. Adding an extra cost to all requests may be a theoretical solution, but the user experience and cumulative proving costs undermine the overall benefits of decentralized proving. We consider requiring each prover to provide one-time collateral before requesting a time slot. The collateral would not be lost but locked until the provers decide to stop proving and withdraw their collateral. This way, the entry barrier has higher on-time costs but eliminates a portion of malicious provers that can cross the barrier. Additionally, each honest prover would receive a fee from all aggregated funds in their submitted proofs, making honest behavior additionally incentivized.
Request throttling
The collateral acts as a joining token to the proving service, but once joined, a prover may still spam the request queue. To mitigate this, the requests are throttled so provers may submit only a certain number of requests in a given time frame (i.e., once in 10 minutes). To be able to request slots more frequently, the required collateral would need to be higher. If one request time slot per a given time frame costs X, k slots would have a linearly higher cost of kX. Throttling would be implemented on a smart contract level, tracking the last request submission time from each prover with deposited collateral.
Data visibility
In the described protocol, each prover will require knowledge of private inputs for the construction of ZK proofs. If a prover is providing proving services to other users, it will be able to see certain disclosed information. In general, it will be aware of a segment of the transaction graph. Without knowledge of all transactions in the chain from deposits to withdrawals, the origin and destination of funds will remain untraceable for the prover.