Synthetic PoRep Security Analysis

Definitions

$\delta$ : percentage of incorrect labels. Currently set to 0.39 (red pebbles)
Adv: any SP who is able to place more than 3.9% of incorrect labels and still pass the proof
p = probability to answer a random challenge, currently equal to 0.961
$\lambda$ = security parameter, currently set to 10 (soundness error 2ˆ{-\lambda})
c = PoRep challenges per layer, currently set to 176

Overview

An adversary passes the verification with probability $≤ (1-\delta)^c = p^c= (0.961)^{176} < 2^{-10}$

protocol introduces an additional step to the current PoRep protocol in order to reduce the buffer between PreCommit and ProveCommit .

A Synthetic Challenge set $SC$ is generated. This is a set of $N_{Syn}$ positions selected at random.
The 176 PoRep challenges are sampled among the $N_{Syn}$ elements of the Synthetic Challenge set, instead of being randomly selected among the $2^{30}$ nodes of the entire 32GiB layer of the SDR graph.

We do not want to increase the number of challenges (c) or decrease $\lambda$ . In order not to lose security we need to analyze how big $N_{Syn}$ needs to be.

Technical Analysis

Assume that a Synthetic Challenge set $SC$ of $N_{Syn}$ Synthetic Challenges is generated. The expected number of challenges that can be answered is therefore $C = pN_{Syn}$ .

By grinding the adversary can try to come up with a set $SC^{\prime}$ of $N_{Syn}$ challenges with $C^\prime = qN > pN$ challenges that can be answered.

We consider the target of the adversary being to lower down the security parameter by 1 (1 less bit of security). This means that the adversary aims to pass the verification with probability $2^{-\lambda + 1}$ .

In that case the adversary needs $C^\prime = qN$ such that $q^c = 2^{-\lambda + 1} = 2\cdot p^{c}$ (that is $q = 2^{\frac{1}{c}} p$ )

Given $c = 176$ , we take $q = 0.9651$ given that $q^{176} = 0.001926 \sim 0.001953 = 2^{-9}$ .

We want to compute the probability $p^*$ that $C^\prime ≥ qN_{Syn} = 2^{\frac{1}{c}}\cdot p \cdot N_{Syn}$ so that we can compute the grinding effort as $\frac{1}{p^*}$ .

Given we want grinding to be infeasible we need $p^*$ to be small enough (that is, $p^* ≤ 2^{-80}$ ).

If $X$ is the random variable that counts the Synthetic challenges challenges that the adversary can answer we have that the probability $\mathbb{P}(X = C^\prime)$ that exactly $C^\prime$ challenges out of $N_{Syn}$ can be answered is the binomial distribution

\mathbb{P}(X = C^\prime) = {N_{Syn} \choose C^\prime} p^{C^\prime} (1-p)^{(N_{Syn}-C^\prime)}

We want to know how big $N_{Syn}$ needs be in order to have $p^* =: \mathbb{P}(X ≥ C^\prime) ≤ 2^{-80}$

Plugging in numbers in the binomial distribution, we can see that with the inputs

$N_{Syn} = 226000$
$p = 0.961$
$q = 0.9651$
$C^{\prime} = \lfloor qN_{Syn} \rfloor = \lfloor 0.9651 \cdot 226000 \rfloor = 218112$

We get $\mathbb{P}(X ≥ C^\prime) ≤ 2^{-80}$ .

The calculation above can be checked in a binomial calculator like this.

Note

In the Synthetic PoRep implementation, in order to have the synthetic challenge number to be a power of 2, we pick $N_{Syn} = 2^{18} = 262144$ resulting in $\mathbb{P}(X ≥ C^\prime) ≤ 2^{-92}$ . Note: having the synthetic challenge be a power of 2 avoids problem with the modulo reduction when sampling PoRep challenges from the synthetic challenge set.

For the FIP:

## Security Considerations

In the current PoRep protocol if 3.9% or more of nodes in a layer are wrongly encoded by the SP, then the ProveCommit step, where 176 random nodes are checked, will fail with large probability (larger than $1-2^{10}$).
In the new protocol, the SP first samples a set of `N_syn` positions and then proceeds to sample the 176 random nodes from there. In order to be able to keep the same security as before, we need that the distribution of errors in the synthetic challenge set is as close as possible to the original distribution of errors in the layer. However the adversary can try different sets to get one where the fraction of wrongly encoded nodes is smaller than 3.9%. We consider an adversary that wants to pass with probability $2^{-9}$, who then needs a set of synthetic challenges where at least a fraction $q$ are goods (correctly encoded) with $q$ = 0.9651 ($q^{176} ≤ 2^{-9)}$).
We can show that if `N_syn` is large enough, then this is not possible in practice. More in details: the probability that the number of correctly encoded nodes in the sythetic set is larger or equal to $q$`N_syn` is given by the binomial probability:

$$
P = \sum_{i=0}^{qN_{syn}} \binom{N_{syn}}{i}p^i (1-p)^{N_{syn}-i} \text{ with } p ≤ 0.961
$$

and with `N_syn` = $2^{18}$, we have that $P < 2^{-92}$.