# Circuit-Efficient Labeling

During sealing, we perform a labeling function for each node in each layer (sha256 of a 20-block preimage).

let label = sha256([
    replica_id,      // 0.5 blocks
    layer_index,     // 0.25 blocks
    node,            // 0.25 blocks
    parent_1_label,  // 0.5 blocks
    ...,
    parent_37_label, // 0.5 blocks
]);

This labeling function enforces a minimum sealing runtime and its preimage length functions as a *delay* parameter.

In-circuit, these labeling functions ($176 * 11 * 20$ sha256 compressions per proof) are very inefficient and are a predominating factor in PoRep circuit size and prover runtime.

It would be useful to replace the current labeling function with one that is both circuit-efficient and enforces a similar sealing runtime. Field arithmetic is very circuit-efficient; a labeling function using those operations would maximize circuit efficiency.

Performing $n$ sequential squarings of a random field element could be utilized as a delay function (as it is non-parallelizable); the value of $n$ could be chosen such that the runtime of the squarings is effectively that of the labeling function.

Once sequential powers are computed for a node, we can compute a linear combination of those powers with the node's parent labels, thus mapping a vector of parent labels to a child node's label.

Both repeated squarings and linear combinations are circuit-efficient as they utilize only field operations.

[On my computer] a single (non-circuit) labeling function runs in $1.5 * 10^{-5}\ \text{sec}$ which is equivalent to that of 400 pasta field multiplications.

Given a random on-chain field element $\alpha$ we could label each node in each layer by computing $400$ sequential squarings of $\alpha$ ($\text{sector_nodes} * 11 * 400$ field multiplications in total for a sector) and take the node's label to be a linear combination of those powers with the node's parent labels.

// Configure the number of squarings performed per node labeling.
let n = 400;

let mut alpha = get_randomness_from_chain();
for layer in 0..11 {
    // First node's label should depend only on replica-id and layer index.
    let mut layer_labels = vec![replica_id + layer];
    for node in 1..sector_nodes {
        // Repeated squaring of alpha.
        let mut alpha_pows = vec![alpha.square()];
        for i in 0..n - 1 {
            alpha_pows.push(alpha_pows[i].square());
        }
        // Random linear combination of the parent labels with the largest powers of alpha.
        let node_label = parent_labels(node)
            .rev()
            .zip(alpha_pows.iter().rev())
            .map(Mul::mul)
            .sum();
        layer_labels.push(node_label);
        // The next node's starting alpha should be the largest power of alpha computed thus far.
        alpha = alpha_pows[n - 1];
    }
}

The number of squarings performed per node can be modified to target new sealing runtimes and to account for improving sha256 and field arithmetic runtimes of sealing miners; because Halo2 does not require trusted setups, this parameter can be easily updated in production.

Additionally, Halo2 (unlike Groth16) does not limit our use of public inputs; because $\alpha$ is public, the prover and verifier can compute the powers of $\alpha$ out of circuit and expose the powers used during labeling as public inputs, thus further improving circuit size and prover runtime. If it's undesirable for the verifier to compute large powers of $\alpha$, the circuit size could still be reduced by having the verifier compute some of the first powers of alpha.

**Problem:** sequentiality of $\alpha$ powers results in too many multiplcation gates in-circuit
**Solution:** don't use sequential powers of $\alpha$ across node labels, instead change the base from $\alpha$ to a sum of values unique to a node `label = (replica_id + parent_1_label + ...)^(2^400)`