Circuit Design - SnapDeals (Lightweight CC Sector Updates)

• Design goals
• Challenge Generation
• Randomness Generation
• Outcome
• The Circuit
• Parameters
• Public inputs
• Private inputs
• Circuit

Design goals

We investigate feasibility of doing both challenge generation as well as computing hashes used as randomness during LSU, inside the circuit.

Challenge Generation

Challenge generation is a process in which we are aiming to generate a number of challenges $C = 2200$.

The $j \in [0,C/8)$ and $N$ is sector size nodes. The Result of Poseidon-128 is split into 31 bit chunks (discarding 7 high bits) forming eight challenges, which then are taken $\bmod N$.

Based on input from ZCash team, Poseidon can be used as PRG for challenge generation. Using it in this manner would mean using Poseidon-128 in 2-ary variant, costing ~311 constraints, plus additional 256 constrains for binary decomposition (binary decomposition constraints may already be included in the cost of inclusion proofs).

This results in 0.85M additional constraints.

One Poseidon, Multiple challenges

The Poseidon-128 outputs Fr field element which after decomposition results in 254.x bits of randomness. Our biggest $N$ requires 31 bits of randomness. This means that we could use one Poseidon-128 evaluation to generate 8 challenges. It would reduce cost of challenge generation by factor of 8 as the binary decomposition can be shared as well.

Randomness Generation

We are settling on number of $\rho$ per sector $H = 2^9 = 512$ (but want to keep some flexibility in final circuit), this gives us two options, we can either compute all H ρ values and use lookup to access ρ from these computed values; or we can compute ρ for each challenge and not use the fact that only H ρ computations need to be done.

The latter option is promising as 512-ary lookup of dynamic values will cost at least 512 constraints. (please verify)

As both $H$ and $N$ are powers of two the $\lfloor \frac{c_iH}{N} \rfloor$ computation can be easily performed using bit shift by selecting bits from decomposed $c_i$.

This results in ~312 constraints for $\rho_i$ generation (no decomposition, it is used as Fr).

This results in additional 0.6M constraints when compared with accepting $\rho_{c_i}$as public input.

Outcome

Overall in circuit challenge and randomness generation increases circuit size by ~1.4M constraints which is 14% of estimated size of the circuit. Given that it decreases the number of public inputs by 4400, or 99.9%, the 14% increased proving cost will be well worth the reduction of verification cost.

Poseidon-128

The ~311 constraints for Poseidon is taken from here.

Domain separation to be applied for both uses of Poseidon by means of Poseidon DST in Capacity field.

The Circuit

Single sector per circuit.

Circuit needs to fulfill following roles:

• Challenge Generation
• Verifying Inclusion Proofs:
• NewCommR
• OldCommR
• Data Commitment
• Verifying Encoding
• Generating $\rho_i$
• $R^{*}_i = R_i + D_i*\rho_i$

Parameters

$N \in \{2^{5}, 2^{18}, 2^{24}, 2^{30}, 2^{31}\}$ - sector size in nodes

$Hs(N) = \begin{cases}\{2, 2, 2,2,2,2\} & \text{if } N=2^5 \\ \{2^7, 2^8, 2^9, 2^{10}, 2^{11}, 2^{12}\} & \text{otherwise} \end{cases}$ - number of encoding hashes

$C(N) = \begin{cases}2200 & \text{for } N \in \{2^{24}, 2^{30}, 2^{31}\}\\ 10 & \text{otherwise} \end{cases}$ - number of challenges

Public inputs

• OldCommR - CommR of existing CC sector
• NewCommR - CommR of the sector after being updated with deals
• CommD - Data commitment for data which is being updated into the sector
• SectorID - not sure it needs to be a public input, on the actors side we have clear mapping of SectorID to OldCommR.
• hSelect - one-hot encoding (bit-vector of 6 values, with only one bit set) of $hSelect$

Private inputs

• CommC
• CommRLast
• SectorID
• for each $c_i$
• vanilla proofs
• $R_{c_i}$, $D_{c_i}$, $R^{*}_{c_i}$ - old replica at ${c_i}$, data at ${c_i}$, new replica at ${c_i}$

Circuit

The circuit consists of 2200 independent challenges to be verified.

One part of circuit that may be shared is proving the openings of NewCommR and OldCommR to arrive at NewCommRLast and OldCommRLast.

For $j \in [0, C/8)$:

• Challenge Generation: $[c_{8*j+7},\cdots ,c_{8*j}] = \text{Poseidon–128}(\text{NewCommR}, ParitionID*86+j) \bmod N$
$$\text{digest\_index} = ParitionID*86+j \\ c_{8*j+7},\cdots ,c_{8*j} = \text{Poseidon–128}(\text{NewCommR}, \text{digest\_index}) \bmod N$$

Consists of one 2-ary Poseidon Hash and binary decomposition, binary decomposition allows to take the $\text{mod}\ N$ .

For each $i \in [0, C)$ following sub-circuit is created:

• $\rho$ Generation: $\rho_{c_i} = \text{Poseidon–128}(\phi, \lfloor \frac{c_i*H}{N} \rfloor)$

The $\lfloor \frac{c_iH}{N} \rfloor$ can be constructed from binary decomposition of $c_i$.

To increase flexibility of the circuit at minimal cost we are suggesting ability to adjust $H$ value based on public input.

This can be easily done in circuit by having 5 computations of $\lfloor \frac{c_i*Hs[i]}{N} \rfloor$ (one for each $hSelect$ value), which are just linear combinations of decomposed $c_i$ bits, and then selecting them based on the one-hot encoding of hSelect public input.

$$\lfloor \frac{c_iH}{N} \rfloor = \sum_{k=0}^{5}hSelect[k] \cdot \lfloor \frac{c_i \cdot Hs[k]}{N} \rfloor = \\ \sum_{k=0}^{5}hSelect[k]\cdot \big( c_i \gg (\log_2N - \log_2{Hs[k]}) \big)$$

If we do shared circuit for 32GB and 64GB, the condition or flag will need to feed into this circuit.

• Inclusion proofs:
• $R_{c_i}$ is opening of OldCommR at position $c_i$
• $R^{*}_{c_i}$ is opening of NewCommR at position $c_i$
• $D_{c_i}$is opening of CommD at position $c_i$
• Encoding Check: $R^{*}_{c_i} = R_{c_i} + D_{c_i} * \rho_{c_i}$ computed in $\text{F}r$.