Recursive proof aggregation

[kike]

Here there is a bit more of detail. Hope it helps.

Aggregating proofs inside actions

Let n_c be the number of compliance units in the action. Let n_r be the total number of resources (consumed and created) in the action.

There are n_c compliance proofs, and n_r logic proofs in the action.

Aggregate compliance and logic proofs:

• Inputs:

  • cvk: The verifying key of the compliance circuit.
  • (cst_{j},\pi_{c,j})_{j\in \leq n_c}: The n_c instances and (valid) proofs of the compliance circuit.
  • (lvk_j,lst_{j},\pi_{l,j})_{j\leq n_r}: The n_r verifying keys, instances, and proofs, of the resource logic circuits.

• Output:

  • The action proof \pi_a. // An aggregated proof.

Steps:

1. Set the initial aggregated instance to two zero-bytes arrays h_0,d_0, and the initial aggregated proof to a dummy value \pi_{a,0}.

2. Let avk the verifying key of the universal aggregator program/circuit \mathsf{P}_{ua}. (See first post.)

3. For j \in 1,\ldots n_c: // First aggregate the compliance proofs

   1. Compute h_j = Hash(cst_j,h_{j-1})
   2. Compute d_j = Hash(cvk,d_{j-1})
   3. Set ast_j = (avk,h_j,d_j) // The j-th aggregated action instance
   4. Set aw_j = (cvk,h_{j-1},d_{j-1},\pi_{a,j-1},\pi_{c,j}) // The j-th aggregated action witness
   5. Compute \pi_{a,j} = prove(\mathsf{P}_{ua},ast_j,aw_j) // The j-th aggregated action proof.

4. Reset h_0 = h_{n_{c}}, d_0 = d_{n_{c}}, \pi_{a,0}= \pi_{a,n_c}

5. For j \in 1,\ldots, n_r: // Now aggregate the logic proofs

   1. Compute h_j = Hash(lst_j,h_{j-1})
   2. Compute d_j = Hash(lvk_j,d_{j-1})
   3. Set ast_j = (avk,h_j,d_j) // The (n_c+j)-th aggregated action instance
   4. Set aw_j = (lvk_j,h_{j-1},d_{j-1},\pi_{a,j-1},\pi_{l,j}) // The (n_c+j)-th aggregated action witness
   5. Compute \pi_{a,j} = prove(\mathsf{P}_{ua},ast_j,aw_j) // The j-th aggregated action proof.

6. Output \pi_{a,{n_c+n_r}}

Verify aggregation of compliance and logic proofs:

• Inputs:
  • cvk: The verifying key of the compliance circuit.
  • (cst_{j})_{j\in \leq n_c}: The n_c instances of the compliance circuit.
  • (lvk_j,lst_{j})_{j\leq n_r}: The n_r verifying keys and instances of the resource logic circuits.
  • \pi_a: The aggregated proof for the action.
• Output: b\in\{true,false\}

Steps

1. Derive the action instance from compliance and logic instances of the action:

   1. Set h_0,d_0,\pi_{a,0} to the same values as when aggregating.

   2. For j \in 1,\ldots n_c+n_r: // Compute same chained hashes as when aggregating

      • If j \leq n_c

        • Compute h_j = Hash(cst_j,h_{j-1})
        • Compute d_j = Hash(cvk,d_{j-1})

      • If j> n_c:

        • Compute h_j = Hash(lst_j,h_{j-1})
        • Compute d_j = Hash(lvk_j,d_{j-1})

   3. Set ast = (avk,h_{n_c+n_r},d_{n_c+n_r}) // The action instance

2. Output verify(avk,ast,\pi_a)

Aggregate proofs in transactions (aggregate all compliance and logic proofs)

The same way as aggregating/verifying them within actions (see above). One first collects compliance and logic instances and proofs from all the actions in the transaction.

Aggregate proofs in transactions (aggregate action proofs)

This assumes actions come with their compliance and logic proofs already aggregated. Let n_a be the number of actions in transaction T. There are n_a action proofs generated as explained above.

Aggregate actions proofs:

• Inputs:

  • avk: The verifying key of the universal aggregator program/circuit \mathsf{P}_{ua}. (See first post.) .
  • (ast_{j},\pi_{a,j})_{j\in \leq n_c}: The n_a instances and (valid) proofs of the actions of the transaction. Each action instance is generated from the compliance and logic instances of the corresponding action as explained in step 1 of ‘verify aggregation of compliance and logic proofs’

• Output:

  • The transaction proof \pi_t. // An aggregated proof.

Steps:

1. Set the initial aggregated instance to two zero-bytes arrays h_0,d_0, and the initial aggregated proof to a dummy value \pi_{t,0}.

2. Let avk the verifying key of the universal aggregator program/circuit \mathsf{P}_{ua}. (See first post.)

3. For j \in 1,\ldots n_a:

   1. Compute h_j = Hash(ast_j,h_{j-1})
   2. Compute d_j = Hash(avk,d_{j-1})
   3. Set tst_j = (avk,h_j,d_j) // The j-th aggregated transaction instance
   4. Set tw_j = (avk,h_{j-1},d_{j-1},\pi_{t,j-1},\pi_{a,j}) // The j-th aggregated transaction witness
   5. Compute \pi_{t,j} = prove(\mathsf{P}_{ua},tst_j,tw_j) // The j-th aggregated transaction proof.

4. Output \pi_{t,{n_a}}

Verify aggregation of action proofs

• Inputs:
  • avk: The verifying key of the compliance circuit.
  • (ast_{j})_{j\in \leq n_a}: The n_a action instances of the transaction.
  • \pi_t: The aggregated proof for the action.
• Output: b\in\{true,false\}

Steps

1. Derive the transaction instance:

   1. Set h_0,d_0,\pi_{a,0} to the same values as when aggregating.

   2. For j \in 1,\ldots n_a: // Compute same chained hashes as when aggregating

      1. Compute h_j = Hash(ast_j,h_{j-1})
      2. Compute d_j = Hash(avk,d_{j-1})

   3. Set tst = (avk,h_{n_a},d_{n_a}) // The transaction instance

2. Output verify(avk,tst,\pi_t)

Parallelizing provers

The universal aggregator program \mathsf{P}_{ua} can be modified so it accepts as input 2 aggregated instances and proofs (instead of one).
To aggregate a total of N = \sum_{l=0}^d n/{2^l} proofs, the N incremental proofs produced by the prover can be arranged into d layers. In the l-th layer, n/{2^l} proofs are generated in parallel and fed as input to the next layer.

Instance generation. The chained hashes h_j,d_j are computed accordingly: use the two input pair of hashes at each incremental step.

Mixing aggregation strategies

Sequential and parallel provers via binary tree transcripts are two examples of aggregation strategies. Most likely the ones we will want to use the most (sequential for few aggregations, parallel for many aggregations).

Each transaction (or each action within a transaction) can aggregate with their own strategy. Aggregating two proofs resulting from different strategies is possible.