Logo
    📝

    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−δ)c=pc=(0.961)176<2−10≤ (1-\delta)^c = p^c= (0.961)^{176} < 2^{-10}≤(1−δ)c=pc=(0.961)176<2−10

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

    • A Synthetic Challenge set SCSCSC is generated. This is a set of NSynN_{Syn}NSyn​ positions selected at random.
    • The 176 PoRep challenges are sampled among the NSynN_{Syn}NSyn​ elements of the Synthetic Challenge set, instead of being randomly selected among the 2302^{30}230 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 NSynN_{Syn}NSyn​ needs to be.

    Technical Analysis

    Assume that a Synthetic Challenge set SCSCSC of NSynN_{Syn}NSyn​ Synthetic Challenges is generated. The expected number of challenges that can be answered is therefore C=pNSynC = pN_{Syn}C=pNSyn​.

    By grinding the adversary can try to come up with a set SC′SC^{\prime}SC′ of NSynN_{Syn}NSyn​ challenges with C′=qN>pNC^\prime = qN > pNC′=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−λ+12^{-\lambda + 1}2−λ+1.

    In that case the adversary needs C′=qNC^\prime = qNC′=qN such that qc=2−λ+1=2⋅pcq^c = 2^{-\lambda + 1} = 2\cdot p^{c}qc=2−λ+1=2⋅pc (that is q=21cpq = 2^{\frac{1}{c}} pq=2c1​p)

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

    We want to compute the probability p∗p^*p∗ that C′≥qNSyn=21c⋅p⋅NSynC^\prime ≥ qN_{Syn} = 2^{\frac{1}{c}}\cdot p \cdot N_{Syn}C′≥qNSyn​=2c1​⋅p⋅NSyn​ so that we can compute the grinding effort as 1p∗\frac{1}{p^*}p∗1​.

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

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

    P(X=C′)=(NSynC′)pC′(1−p)(NSyn−C′)\mathbb{P}(X = C^\prime) = {N_{Syn} \choose C^\prime} p^{C^\prime} (1-p)^{(N_{Syn}-C^\prime)}P(X=C′)=(C′NSyn​​)pC′(1−p)(NSyn​−C′)

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

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

    • NSyn=226000N_{Syn} = 226000NSyn​=226000
    • p=0.961p = 0.961p=0.961
    • q=0.9651q = 0.9651q=0.9651
    • C′=⌊qNSyn⌋=⌊0.9651⋅226000⌋=218112C^{\prime} = \lfloor qN_{Syn} \rfloor = \lfloor 0.9651 \cdot 226000 \rfloor = 218112C′=⌊qNSyn​⌋=⌊0.9651⋅226000⌋=218112

    We get P(X≥C′)≤2−80\mathbb{P}(X ≥ C^\prime) ≤ 2^{-80}P(X≥C′)≤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 NSyn=218=262144N_{Syn} = 2^{18} = 262144NSyn​=218=262144 resulting in P(X≥C′)≤2−92\mathbb{P}(X ≥ C^\prime) ≤ 2^{-92}P(X≥C′)≤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:

    CryptoNet is a Protocol Labs initiative.

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