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

## Design goals

There are two major pathways we use when designing the circuit

- challenge generation and hash computation inside
- or outside.

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$.

$[\_, c_{8j+7}, c_{8j+6}, \cdots, c_{8j+1}, c_{8j}] = \text{Split-31bit}(\text{Poseidon–128}(CommR, j)) \\ c_i = c_i \bmod N$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)

$\phi = \text{Posedion-128}(CommD, OldCommR) \\ \rho_{c_i} = \text{Poseidon–128}(\phi, \lfloor \frac{c_iH}{N} \rfloor)$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$.

$\lfloor \frac{c_iH}{N} \rfloor = c_i \gg (\log_2N - \log_2H)$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)$
- 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$.

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.

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