zkPlasmaFold Construction

# zkPlasmaFold Construction ## Questions - Do we need to hash the nullifier tree in the block? ## Data structures $$ \def\U{\mathbb{U}} \def\u{\mathbb{u}} \def\W{\mathbb{W}} \def\w{\mathbb{w}} \def\F{\mathcal{F}} \newcommand{\noop}[1]{} \def\tx{\mathtt{tx}} \def\sender{\mathtt{sender}} \def\owner{\mathtt{owner}} \def\amount{\mathtt{amount}} \def\index{\mathtt{index}} \def\sk{\mathtt{sk}} \def\height{\mathtt{height}} \def\nullifier{\mathtt{nullifier}} \def\utxo{\mathtt{utxo}} $$ ### Transactions An $m$-to-$n$ transaction $\tx$ consists of: - Nullifiers $\{\nullifier_i\}_{i = 0}^{m - 1}$ for input UTXOs - Committed output UTXOs $\{cm(\utxo^O_j)\}_{j = 0}^{n - 1}$ - A UTXO is $\utxo := (\owner, \amount, \index)$ where owner is the UTXO owner, amount is the UTXO amount and index is the UTXO $j$-index in the transaction $\tx$ Each nullifier $\nullifier_i$ corresponds to a "poured UTXO" (in zcash linguo) which the sender has received previously. Nullifiers avoid double spends, while removing L2 observers the ability to create users' transaction history graph. We detail the computation of each UTXO's nullifier below. Consider Alice received a UTXO $\utxo$, which is the $j$-th output of $\tx$, which is the $i$-th leaf of the transaction tree $r^\tx$, which is included at block $\mathcal{B}_t$ at height $t$. Now to spend this UTXO, Alice generates the corresponding nullifier as: $$ \nullifier = H(\sk, i, j, t) $$ where $\sk$ is a secret held and committed to by a user initially. The intuition for the nullifier computation is: - the secret $\sk$ prevents the transaction sender from computing the nullifier for the corresponding UTXO (since the intial transaction sender does not have access to the receiver's secret) - the $i$ input prevents collisions between two same UTXOs in two different transactions (since they have different positions in the transaction tree) - the $j$ input prevents collisions between two same UTXOs in the same transaction (since they have different indexes in the transaction) - the height prevents collisions between the two same transactions in different blocks. And the transaction validity proof generated by Alice will show that $i$, $j$, and $t$ are correct. To summarize, a transaction is the tuple: $$ \tx = (\sender, in=\{\nullifier_i\}_{i = 0}^{m - 1}, out=\{cm(\utxo^O_j)\}_{j = 0}^{n - 1}) $$ A commitment to this transaction $cm(\tx)$ is sent to the aggregator, along with the nullifiers composing that committed transaction inputs. The aggregator will receive a randomized witness satisfying an arithmetic circuit which attests to the correctness of those public values - $cm(\tx)$ and the list of nullifiers, all coming from previously existing transactions (we detail below this circuit). The aggregator builds a transaction tree $\mathcal{T}^{\tx}$ with root $r^{\tx}$. Its leaves are composed of all the senders' transactions. Each sender can only send a single transaction per block - note that each transaction can have multiple recipients. ### Blocks A block $\mathcal{B}_t$ consists in a tree whose leaves corresponds to the root $r^{tx}_t$ of the aggregator's built transaction tree, the latest nullifier tree root $r^{null}_{t}$ (updated with the latest input nullifiers and storing all nullifiers used up to now) and the root of a signer tree (storing senders who have signed the corresponding $r^{tx}_t$). An onchain block tree stores all the aggregator produced blocks. It has root $r^{tip}_{t}$ to indicate the root for the chain's tip at time $t$. The idea for this setup is to make it straightforward for a sender to "pour" input transactions he received into a new one or for a receiver to prove he received a transaction of a given amount in a previously produced block. ![image](https://hackmd.io/_uploads/r1opOcZ2ll.png) ## High-Level Protocol ### Setup #### Aggregator Nullifier tree $\mathcal{T}^{null}$ stores a tree whose leaves consists in nullifier values $\mathtt{nullifier}_{i}$, sent by users and corresponding to poured-in transactions. The nullifier tree isn't updated when user does not provide signature of his transaction. Builds a transaction tree $\mathcal{T}^{TX}$, whose leaves consist in transactions sent by users (which are themselves trees). Builds a signer tree. #### Contract (L1) Stores blocks $\mathcal{B}_{t-1}, \mathcal{B}_{t}, \dots$ Stores the block tree with root $r^{tip}_{t}$ indicating the root for the chain tip at time $t$. Stores user nonces. #### User Stores balance ### Join L2 (Analogous to PlasmaFold) ### Transact 1. Sender generates instance-witness pair for transaction validity and randomizes it. 2. Sender sends the transaction $\tx$ and the randomization proof to the aggregator. 3. Aggregator builds transaction tree for all transactions whose randomized instance and witness are satisfying. 4. Aggregator returns Merkle path to each transaction to its sender 5. Sender forwards Merkle path to receiver and sends the signature for $\tx$ to the aggregator 6. Aggregator builds signer tree and updates nullifier tree 7. Aggregator aggregates satisfying randomized instance-witness pairs and generates a proof ensuring correct aggregation and Merkle tree updates. 8. Aggregator proposes block. 9. Sender & receiver update local balance proof. ### Exit L2 (Analogous to PlasmaFold) ## Details ### Folding setup #### User - $(\U^b, \W^b), (\u^b, \w^b)$: Running and incoming instance-witness pairs. Associated with balance circuit $\F^b$. - $(\U^t, \W^t), (\u^t, \w^t)$: Running and incoming instance-witness pairs. Associated with tx validity circuit $\F^t$.  #### Aggregator - $(\U^a, \W^a), (\u^a, \w^a)$: Running and incoming instance-witness pairs. Associated with local state validity & user instance aggregation circuit $\F^a$. - $(\overline{\U}^t, \overline{\W}^t)$: Running instance-witness pair for aggregated $(\U^t, \W^t)$.  ### Randomization Plain instance-witness pair: $(\u^t, \w^t)$ Randomized instance-witness pair: $(\widehat{\U}^t, \widehat{\W}^t) \gets FS.P((\widetilde{\U}^t, \widetilde{\W}^t), (\u^t, \w^t))$, where $(\widetilde{\U}^t, \widetilde{\W}^t)$ is a randomly sampled running instance-witness pair that satisfies $\F^t$. Randomization proof: $(\u^t, \widetilde{\U}^t, \widehat{\W}^t)$ ### Proof aggregation Naive approach: accumulate $(\U^a, \W^a)$ and $\{(\widehat{\U}^t_i, \widehat{\W}^t_i)\}$ with non-uniform PCD - Why non-uniform: $\F^a$ and $\F^t$ are different - Why PCD: $\U^a$ is folded with multiple instances ($\u^a$ and $\widehat{\U}^t_i$) Improved approach with **uniform IVC** via separate accumulation: 1. Initialization: $\U^a_0 = \W^a_0 = \overline{\U}^t_0 = \overline{\W}^t_0 = \bot$ 2. For each committed tx $\overline{tx}_i$ and randomization proof $(\u^t_i, \widetilde{\U}^t_i, \widehat{\W}^t_i)$ from user $i$: 1. $\widehat{\U}^t_i \gets FS.V(\widetilde{\U}^t_i, \u^t_i)$ 2. $(\overline{\U}^t_{i + 1}, \overline{\W}^t_{i + 1}) \gets FS.P\left((\overline{\U}^t_{i}, \overline{\W}^t_{i}), (\widehat{\U}^t_i, \widehat{\W}^t_i)\right)$ 3. $(\U^a_{i + 1}, \W^a_{i + 1}) \gets FS.P\left((\U^a_{i}, \W^a_{i}), (\u^a_{i}, \w^a_{i})\right)$ 4. Evaluate $\F^{aug(a)}$ on input $z_i = (\overline{\U}^t_i, ...)$ 5. Construct $(\u^a_{i + 1}, \w^a_{i + 1})$ from the execution trace of $\F^{aug(a)}$ (as defined below) 3. Compress $\U^a_n, \W^a_n, \overline{\U}^t_n, \overline{\W}^t_n$ with the decider SNARK #### Aggregator circuit $\F^a(z_i = (\overline{\U}^t_i, ...))$ 1. $\overline{\U}^t_{i + 1} \gets FS.V(\overline{\U}^t_i, FS.V(\widetilde{\U}^t_i, \u^t_i))$ 2. Check merkle tree updates 3. Return $z_{i + 1} = (\overline{\U}^t_{i + 1}, ...)$ #### Augmented aggregator circuit $\F^{aug(a)}(z_i = (\overline{\U}^t_i, ...))$ (Done in the same fashion as folding-based IVC circuits) 1. $\overline{\U}^t_{i + 1} \gets FS.V(\overline{\U}^t_i, FS.V(\widetilde{\U}^t_i, \u^t_i))$ 2. Check merkle tree updates 3. Check $\u^a_{i}.x = H(\U^a_{i}, i, z_0, z_i)$ 4. $\U^a_{i + 1} \gets FS.V(\U^a_{i}, \u^a_{i})$ 5. Mark $x = H(\U^a_{i + 1}, i + 1, z_0, z_{i + 1})$ as public input 6. Return $z_{i + 1} = (\overline{\U}^b_{i + 1}, ...)$ ### Sending Say that Bob is doing a transaction that spends $\{\utxo^I_i\}_{i = 0}^{m - 1}$ and creates $\{\utxo^O_j\}_{j = 0}^{n - 1}$. To this end, he needs to send the shielded transaction with input $\{\nullifier_i\}_{i = 0}^{m - 1}$ and output $\{cm(\utxo^O_j)\}_{j = 0}^{n - 1}$ to the aggregator. Furthermore, he needs to show that the shielded transaction is valid, i.e., all nullifiers nullify input UTXOs that have been received by the sender previously, and the total amount of input UTXOs equals the total amount of output UTXOs This is done by building an instance-witness pair for $\F^t$, and proof randomization is then used to ensure privacy.  #### Transaction validity circuit $\F^t$ 1. There exist input UTXOs $\{\utxo^I_i\}_{i = 0}^{m - 1}$ corresponding to nullifiers $\{\nullifier_i\}_{i = 0}^{m - 1}$ 2. There exist output UTXOs $\{\utxo^O_j\}_{j = 0}^{n - 1}$ corresponding to commitments $\{cm(\utxo^O_j)\}_{j = 0}^{n - 1}$ 3. Sum of input UTXO amounts equals that of output UTXO amounts 4. The committed input UTXOs $\{cm(\utxo^I_i)\}_{i = 0}^{m - 1}$ are contained in some transactions $\{\tx_i\}_{i = 0}^{m - 1}$ 5. $\{\tx_i\}_{i = 0}^{m - 1}$ are included in some transaction tree, and the corresponding leave of signer tree is 1 6. The transaction tree and the signer tree are included in the block tree (Augmented circuit is unnecessary) ### Updating balance After a block is validated on L1, all involved senders and receivers update their balance and balance proof. The balance proof is an IVC proof for (the augmented version of) balance circuit $\F^b$, which shows that the balance is updated according to transactions sent or received by the user in the current block. Intuition 1. Can the user *not* process the sent transaction? No, since users' nonces are stored onchain (same arg. as in intmax/plasmafold) 2. Can the recipient process the same transaction twice? No, the user's circuit specifies that the processed transaction index in the transaction tree should be strictly increasing. 3. Can the recipient process a transaction which does not exist? This could be done by: a. The sender generates a transaction with inputs not existing within $r^{tip}_{t}$ --> aggregator wouldn't be able to include it since L1 contract expects $r^{tip}_{t}$ b. The receiver processes a transaction which does not exist --> the exit proof will fail since receiver will have to accumulate a non-existing block #### Balance circuit $\F^b$ and augmented balance circuit $\F^{aug(b)}$ (Analogous to PlasmaFold)  ## Random ideas ### Replace (pending) transaction tree with (pending) utxo tree? The motivation is to simplify step 4 & step 5 of tx validity circuit. Leaf of the committed utxo tree is now $(i, cm(utxo))$, where $i$ is the index of the transaction that contains $cm(utxo)$. $i$ allows for checking the signer bit in the signer tree. With committed utxo tree, we can now simply check the membership of $cm(utxo)$ in the committed utxo tree for step 4 and step 5. This also makes the computation of nullifier clearer. We can use the index of utxo in committed utxo tree to replace both the index of utxo in transaction and the index of transaction in transaction tree. ### Replace signer tree with (settled) utxo tree? Again we want to simplify step 5 of tx validity circuit, which checks membership in both (pendind) tx/utxo tree and signer tree. If we replace signer tree with (settled) utxo tree whose leaf is $(cm(utxo), bit)$, then we only need to prove one membership for step 5. ### Replace signature with W-U pair for user acknowledgement Signature is now redundant because tx validity circuit already shows: 1. I know my sk (for nullifier computation) 2. My sk corresponds to my pk ### Replace EC-based keys with hash-based keys If we no longer depend on signatures, then we can use hash-based keys, i.e., $pk = H(sk, r)$, in order to reduce the size of tx validity circuit which checks relation between sk and pk.