⚡Lazarus⚡

0. setup

• relation R
  • constraints
    • $f^{(k)}(\overrightarrow{s_1},...,\overrightarrow{s_r})$ $={\sum }_{i,j=1}^{r^{\prime }}{a}_{i,j}^{(k)}<{\vec{s}}_i,{\vec{s}}_j>+{\sum }_{i=1}^r<{\phi }_i^{(k)},{\vec{s}}_i>-b^{(k)}=0$
    • $ct(f^{\prime (l)}(\overrightarrow{s_1},...,\overrightarrow{s_l}))$ $=ct({\sum }_{i,j=1}^L{a}_{i,j}^{(k)}<{\vec{s}}_i,{\vec{s}}_j>+{\sum }_{i=1}^L<{\phi }_i^{(l)},{\vec{s}}_i>-b^{(l)})\mathrm{mod}{q}^{\prime }$
    • norm check
      • $\vec{s}$ is witness
      • ${\sum }_{i=1}^r||\overrightarrow{s_i}|{|}_2^2\le {\beta }^2$
  • data structure
    • $\overrightarrow{s_i}$, $\overrightarrow{s_j}$ $\in R_q^n$
    • ${\vec{\phi }}_i^{(k)}$ $\in R_q^n$
    • $a_{ij}^{(k)}$ $\in R_q$
    • $b^{(k)}$ $\in R_q$
    • ${\vec{\phi }}_i^{{}^{\prime }(l)}$ $\in R_q^n$
    • $a_{ij}^{{}^{\prime }(l)}$ $\in R_q$
    • $b^{{}^{\prime }(l)}$ $\in R_q$
    • $b_0^{{}^{\prime }(l)}$ is the constant term of $b^{{}^{\prime }(l)}$
    • $<\overrightarrow{s_i},\overrightarrow{s_j}>$ $\in R_q$
    • $<\overrightarrow{{\phi }_i},\overrightarrow{s_i}>$ $\in R_q$
    • $k\in [K]$
    • $l\in [L]$
  • params
    • ${\vec{\phi }}_i^{(k)}$, $a_{ij}^{(k)}$, $b^{(k)}$, ${\vec{\phi }}_i^{{}^{\prime }(l)}$, $a_{ij}^{{}^{\prime }(l)}$, $b^{{}^{\prime }(l)}$ are public inputs of dot product constraint system(DPCS)
      • each iteration they are the same?
    • $d=64$ (page 26)
    • $q\approx 2^{32}$ (page 26)
    • $\beta =\sqrt{128/30}\sqrt{(n+(3+l)k)d/2}$ (page 26)
      • use K and L??
• sample A, B, C, D in challenge space
  • they are common reference string(CRS)
  • challenge space
    • sample ring element from ring $R=Z_q[X]/(X^{64}+1)$
    • sampled ring element should meet below requirements
      • 23 zero coefficients
      • 31 coefficient that are ±1
      • 10 coefficients that are ±2
    • coefficients are total 64
  • data structure
    • $A\in R_q^{\kappa \times n}$
    • $B_{ik}\in R_q^{{\kappa }_1\times \kappa }$
      • $1\le i\le r$
      • $0\le k\le t_1-1$
      • $t_1$ see below decomposition section
    • $C_{ijk}\in R_q^{{\kappa }_2\times 1}$
      • $1\le i\le j\le r$
      • $0\le k\le t_2-1$
      • $t_2$ see below decomposition section
      • ${\kappa }_2$ ??
    • $D_{ijk}\in R_q^{{\kappa }_2\times 1}$
      • $1\le i\le j\le r$
      • $0\le k\le t_1-1$
• questions
  • use K and L to compute $\beta$??
  • how to get the values of ${\kappa }_i$??

1. commit

• commit $s_i,i\in \mathrm{1..}r$
  • $\overrightarrow{t_i}=A\overrightarrow{s_i}\in R_q^{\kappa }$, this is Ajtai commitment
• decompose and combine
  • problems
    • problem 1:
      • costly to send $t_i$ directly to verifier
      • solution: combine all inner commitments $\overrightarrow{t_i}$ into a shorter outer commitment
    • problem 2:
      • ring elements ${\vec{t}}_{i,j},g_{i,j}\in R_q$ have arbitrary length of coefficients, not good for commitment
      • solution: decompose and concatenate
        • each coefficient of ring element need to be decomposed to same length with a proper basis, then concatenate them together
  • decompose
    • decompose ${\vec{t}}_{i,j}$
      • ${\vec{t}}_{i,j}\in R_q,i\in [r],j\in [\kappa ]$
      • in total there are $r\times \kappa$ $R_q$ in $\vec{t}$, means $\vec{t}\in R_q^{r\kappa }$
      • choose length $t_1$, basis $b_1$
      • decompose ${\vec{t}}_{i,j}$, output decomposed ${\vec{t}}_{i,j}={\vec{t}}_{i,j}^{(0)}+...+{\vec{t}}_{i,j}^{(t_1-1)}{b}_1^{t_1-1}\in R_q^{t_1}$
      • concatenate all decomposed ${\vec{t}}_{i,j}$, get decomposed $\vec{t}\in R_q^{t_1\kappa r}$
    • decompose ${\vec{g}}_{i,j}$
      • $g_{i,j}=<\overrightarrow{s_i},\overrightarrow{s_j}>$ $\in R_q,i\in [r],j\in [i,r]$
      • since $g_{i,j}=<\overrightarrow{s_i},\overrightarrow{s_j}>$, means choose any 2 items from r items, this a classical combination problem, the result is $r(r+1)/2=(r^2+r)/2$
      • in total there are $(r^2+r)/2$ $R_q$ in $\vec{g}$ , means $\vec{g}\in R_q^{(r^2+r)/2}$
      • choose length $t_2$, basis $b_2$
      • decompose ${\vec{g}}_k$, which $k\in [(r^2+r)/2]$, output decomposed ${\vec{g}}_k={\vec{g}}_k^{(0)}+...+{\vec{g}}_g^{(t_2-1)}{b}_2^{t_2-1}\in R_q^{t_2}$
      • concatenate all decomposed ${\vec{g}}_k$, get decomposed $\vec{g}\in R_q^{t_2(r^2+r)/2}$
    • decomposition params(page 16, 19)
      • $\tau$: variance for the sum of the coefficients of a challenge polynomial
      • $\mathfrak{s}=\beta /\sqrt{rnd}$ : standard deviation for the $Z_q$ coefficients of the vectors ${\vec{s}}_i$
      • $b\approx b_1\approx b_2=\sqrt{\sqrt{12r\tau \mathfrak{s}}}$ , b is used in recurse section
      • $t_1=\lfloor \frac{\log q}{\log b}\rceil$
      • $t_2=\lfloor \frac{\log (\sqrt{24nd{\mathfrak{s}}^2})}{\log b}\rceil$
  • combine
    • combine all inner commitments $\overrightarrow{t_i}$ with random matrix B to get a shooter outer commitment $\overrightarrow{u_1}=B\vec{t}\in R_q^{{\kappa }_1}$
    • also put $g_{ij}\in R_q$ combination here, because $g_{ij}$ is dependent of all the challenges, so compute it in the very beginning of the protocol
    • finally get: $\overrightarrow{u_1}=B\vec{t}+C\vec{g}\in R_q^{{\kappa }_1}$
  • prover sends $\overrightarrow{u_1}$ to verifier
• data structure
  • $\overrightarrow{s_i}\in R_q^n$
  • $A\in R_q^{\kappa \times n}$
  • $\overrightarrow{t_i}=A\overrightarrow{s_i}\in R_q^{\kappa }$, $1\le i\le r$
  • $g_{i,j}=<\overrightarrow{s_i},\overrightarrow{s_j}>\in R_q$, $1\le i\le j\le r$
  • after decompose
    • $\overrightarrow{t_i}\in R_q^{t_1\kappa },i\in [r]$
    • $\vec{t}\in R_q^{t_1\kappa r}$
    • $g_{i,j}\in R_q^{t_2}$, $1\le i\le j\le r$
    • $\vec{g}\in R_q^{t_2(r^2+r)/2}$
    • $\overrightarrow{u_1}=B\vec{t}+C\vec{g}\in R_q^{{\kappa }_1}$

2. project

• goal: norm check can be replaced by Johnson-Lindenstrauss projection.
• why: because the JL proof is more compact than check the long vector $\vec{s}$
• need to reach a security level $\lambda (\lambda =128)$
• steps
  • verifier do a random sample get ${\prod }_i\in \{-1,0,1{\}}^{2\lambda \times nd}$ then send to prover
    • $\overrightarrow{s_i}\in R_q^n$
    • n: length of $\overrightarrow{s_i}$
    • d: degree of each element($R_q$) in $\overrightarrow{s_i}$
    • sample probability
      • -1: 1/4
      • 0: 1/2
      • 1: 1/4
  • prover calculate $p_j$
    • $p_j={\sum }_{i=1}^r<{\pi }_i^{(j)},\overrightarrow{s_i}>$ $\in Z_q$, $j=1,...,2\lambda$
  • prover sends $\vec{p}\in Z_q^{2\lambda }$
  • verifier check $||\vec{p}|{|}_2\le \sqrt{\lambda }\beta$ instead of ${\sum }_{i=1}^r||\overrightarrow{s_i}|{|}_2^2\le {\beta }^2$
  • notes: greyhound only use {1, -1} to do the sample
• new constraint added to: (1) make sure final projection is correct, (2) aggregate
  • ${\sum }_{i=1}^r<\tau ({\pi }_i^{(j)}),\tau (\overrightarrow{s_i})>-p_j=0$
  • => $ct({\sum }_{i=1}^r<{\sigma }_{-1}({\pi }_i^{(j)}),\overrightarrow{s_i}>)-p_j=0$
  • => $ct({\sum }_{i=1}^r<{\sigma }_{-1}({\pi }_i^{(j)}),\overrightarrow{s_i}>-p_j)=0$
  • ${\vec{\pi }}_i^{(j)}$ is the j-th row of ${\prod }_i$
  • ${\sigma }_{-1}(f(x))=f(x^{-1})$, just replace $x$ with $x^{-1}$
  • this defines a LaBRADOR compatible constant-term constraint($F^{\prime }$) that can be aggregated
• data structure
  • n: $Z_q$, length of $\overrightarrow{s_i}$
  • d: $Z_q$, degree of $\overrightarrow{s_i}$
  • $1\le i\le r$
  • $j=1,...,2\lambda$
  • ${\prod }_i\in \{-1,0,1{\}}^{2\lambda \times nd}$
  • ${\pi }_i^{(j)}$: $\in \{-1,0,1{\}}^{nd}$
  • $p_j\in Z_q$
  • $\vec{p}\in Z_q^{2\lambda }$

3. aggregate

• goal: aggregate all dot product constraints
  • aggregate $(F,F^{\prime })=F$ $\in R_q$
• steps
  • 1. aggregate $F^{\prime }$
    • for security $\lambda$, F' is aggregated to $\lceil \lambda /lo{g}_2(q)\rceil$ constant-term constraints(why??)
    • F' includes constant-term constraints related to $f^{\prime }$ and $p_j$
    • steps
      • verifier sends random samples: ${\vec{\psi }}^{(k)}\stackrel{\$}{\leftarrow }{Z}_q^{|L|}$, ${\vec{\omega }}^{(k)}\stackrel{\$}{\leftarrow }{Z}_q^{2\lambda }$
      • aggregate:
        • $k=1,...,\lceil \lambda /lo{g}_2(q)\rceil$, $j=1,...,2\lambda$
        • $f^{{}^{\prime \prime }(k)}(\overrightarrow{s_1},...,\overrightarrow{s_r})$
          • $={\sum }_{l=1}^{|L|}{\vec{\psi }}_l^{(k)}{f}^{{}^{\prime }(l)}(\overrightarrow{s_1},...,\overrightarrow{s_r})$
          • $+{\sum }_{j=1}^{2\lambda }{\vec{\omega }}_j^{(k)}({\sum }_{i=1}^r<{\sigma }_{-1}({\overrightarrow{{\pi }_i}}^{(j)}),{\vec{s}}_i>-p_j)$
          • $={\sum }_{i,j=1}^r{a}_{i,j}^{{}^{\prime \prime }(k)}<{\vec{s}}_i,{\vec{s}}_j>+{\sum }_{i=1}^r<{\phi }_i^{{}^{\prime \prime }(k)},{\vec{s}}_i>-b_0^{{}^{\prime \prime }(k)}$
        • so prover gets:
          • $a_{i,j}^{{}^{\prime \prime }(k)}={\sum }_{l=1}^{|L|}{\vec{\psi }}_l^{(k)}{a}_{i,j}^{{}^{\prime }(l)}$
          • ${\phi }_i^{{}^{\prime \prime }(k)}={\sum }_{l=1}^{|L|}{\vec{\psi }}_l^{(k)}{\phi }_i^{{}^{\prime }(l)}+{\sum }_{j=1}^{2\lambda }{\vec{\omega }}_j^{(k)}{\sigma }_{-1}({\overrightarrow{{\pi }_i}}^{(j)})$
          • $b^{{}^{\prime \prime }(k)}={\sum }_{i,j=1}^r{a}_{i,j}^{{}^{\prime \prime }(k)}<{\vec{s}}_i,{\vec{s}}_j>+{\sum }_{i=1}^r<{\phi }_i^{{}^{\prime \prime }(k)},{\vec{s}}_i>$
      • extends integers $b_0^{{}^{\prime \prime }(k)}$ to full polynomials such that $f^{{}^{\prime \prime }(k)}(\overrightarrow{s_1},...,\overrightarrow{s_r})=0$
      • prover sends $b_0^{{}^{\prime \prime }(k)}$ to verifier
      • verifier checks the constant term
        • $b_0^{{}^{\prime \prime }(k)}={\sum }_{l=1}^{|L|}{\vec{\psi }}_l^{(k)}{b}_0^{(l)}+<{\vec{\omega }}^{(k)},\vec{p}>$
  • 2. aggregate linear constraints $f^{(k)}(k=1,...,|F|)$ and $f^{{}^{\prime \prime }(k)}(k=1,...,\lceil \lambda /lo{g}_2(q)\rceil )$
    • verifier sends random samples from challenge space: $\vec{\alpha }\stackrel{\$}{\leftarrow }{R}_q^{|F|}$, $\vec{\beta }\stackrel{\$}{\leftarrow }{R}_q^{\lceil \lambda /lo{g}_2(q)\rceil },K=|F|$
    • $F=<\vec{\alpha },f>+<\vec{\beta },f^{\prime \prime }>$
    • $F(\overrightarrow{s_1},...,\overrightarrow{s_r})$
      • $={\sum }_{k=1}^K{\vec{\alpha }}_k{f}^{(k)}+{\sum }_{k=1}^{\lceil \lambda /lo{g}_2(q)\rceil }{\vec{\beta }}_k{f}^{{}^{\prime \prime }(k)}$
      • $={\sum }_{i,j=1}^r{a}_{i,j}<{\vec{s}}_i,{\vec{s}}_j>+{\sum }_{i=1}^r<{\phi }_i,{\vec{s}}_i>-b$
    • compute outer commitment ${\vec{u}}_2$
      • ${\vec{\phi }}_i={\sum }_{k=1}^K{\vec{\alpha }}_k{\phi }_i^{(k)}+{\sum }_{k=1}^{\lceil \lambda /lo{g}_2(q)\rceil }{\vec{\beta }}_k{\phi }_i^{{}^{\prime \prime }(k)}$
      • $h_{ij}=\frac{1}{2}(<{\phi }_i,{\vec{s}}_j>+<{\phi }_j,{\vec{s}}_i>)$
      • decompose ${\vec{h}}_{i,j}$
        • ${\vec{h}}_{i,j}\in R_q,i\in [r],j\in [r]$
        • in total there are $(r^2+r)/2$ $R_q$ in $\vec{h}$ , means $\vec{h}\in R_q^{(r^2+r)/2}$
        • choose length $t_1$, basis $b_1$
        • decompose ${\vec{h}}_{i,j}$, output decomposed ${\vec{h}}_{i,j}={\vec{h}}_{i,j}^{(0)}+...+{\vec{h}}_{i,j}^{(t_1-1)}{b}_1^{t_1-1}\in R_q^{t_1}$
        • concatenate all decomposed ${\vec{h}}_{i,j}$, get decomposed $\vec{h}\in R_q^{t_1(r^2+r)/2}$
      • ${\vec{u}}_2=D\vec{h}$ $\in R_q^{{\kappa }_2}$
• data structure
  • $1\le i,j\le r$
  • ${\phi }_i$ $\in R_q^n$
  • $h_{ij}=\frac{1}{2}(<{\phi }_i,{\vec{s}}_j>+<{\phi }_j,{\vec{s}}_i>)\in R_q$
  • after decompose
    • $h_{i,j}\in R_q^{t_1}$
    • $\vec{h}\in R_q^{t_1(r^2+r)/2}$
    • ${\vec{u}}_2=D\vec{h}$ $\in R_q^{{\kappa }_2}$
• questions

4. amortize

• purpose: achieve small proof size
• method: instead of checking $F$ is satisfied by the witness, verifier will check 3 dot product constraints hold
• steps
  • verifier sends challenge $c_i$ $\in R_q$ from challenge space
  • prover calculates $\vec{z},\vec{h}$
    • $\vec{z}={\sum }_{i=1}^r{c}_i{\vec{s}}_i$
  • provers sends $\vec{z},\vec{t},\vec{g},\vec{h}$
• data structure
  • $c_i$ $\in R_q$
  • $\vec{z}$ $\in R_q^n$

5. verifier checks(without recursion)

• $\kappa +{\kappa }_1+{\kappa }_2+3$ dot product constraints
  • 3 dot product constraints check
    • (1) $<\vec{z},\vec{z}>={\sum }_{i,j=1}^r{g}_{i,j}{c}_i{c}_j$
    • (2) ${\sum }_{i=1}^r<{\vec{\phi }}_i,\vec{z}>c_i={\sum }_{i,j=1}^r{h}_{i,j}{c}_i{c}_j$
    • (3) ${\sum }_{i,j=1}^r{a}_{i,j}{g}_{i,j}+{\sum }_{i=1}^r{h}_{i,i}-b=0$
  • $\kappa +{\kappa }_1+{\kappa }_2$ dot product constraints check
    • $A\vec{z}={\sum }_{i=1}^r{c}_i{\vec{t}}_i$ $\in R_q^{\kappa }$
    • $\overrightarrow{u_1}=B\vec{t}+C\vec{g}$ $\in R_q^{{\kappa }_1}$
    • ${\vec{u}}_2=D\vec{h}$ $\in R_q^{{\kappa }_2}$
• norm check for $\vec{z},\vec{t},\vec{g},\vec{h}$
  • $||\vec{z}||\le \gamma$
  • $||\vec{t}||\le {\gamma }_1$
  • $\sqrt{||\vec{g}|{|}^2+||\vec{h}|{|}^2}\le {\gamma }_2$
• params
  • $\gamma ,{\gamma }_1,{\gamma }_2,{\beta }^{\prime }$ see page 19

6. recurse

• goal: prove the last message ($\vec{z},\vec{t},\vec{g},\vec{h}$) of each iteration with base protocol recursively until get shooter witness and proof, then output the last message ($\vec{z},\vec{t},\vec{g},\vec{h}$)
• steps:
  • 1. convert last message to new witness vector ${\vec{s}}_i^{\prime }$ , $i\in [r^{\prime }]$
    • decompose $\vec{z}$
      • $\vec{z}={\vec{z}}^{(0)}+b{\vec{z}}^{(1)}$ , ${\vec{z}}^{(0)},{\vec{z}}^{(1)}\in R_q^n$
    • combine $\vec{t},\vec{g},\vec{h}$
      • $\vec{v}=\vec{t}||\vec{g}||\vec{h}$ $\in R_q^m$
      • $m=r{t}_1\kappa +(t_1+t_2)(r^2+r)/2$
    • compose ${\vec{s}}_i^{\prime }$
      • choose $\nu ,\mu$ how to choose??
      • ${\vec{s}}_i^{\prime }$ part 1:
        • ${\vec{z}}^{(0)}={\vec{s}}_1^{\prime }||...||{\vec{s}}_{\nu }^{\prime }$
        • ${\vec{s}}_i^{\prime }$ $\in R_q^{\lceil n/\nu \rceil }$
      • ${\vec{s}}_i^{\prime }$ part 2:
        • ${\vec{z}}^{(1)}={\vec{s}}_{\nu +1}^{\prime }||...||{\vec{s}}_{2\nu }^{\prime }$
        • ${\vec{s}}_i^{\prime }$ $\in R_q^{\lceil n/\nu \rceil }$
      • ${\vec{s}}_i^{\prime }$ part 3:
        • $\vec{v}={\vec{s}}_{2\nu +1}^{\prime }||...||{\vec{s}}_{2\nu +\mu }^{\prime }$
        • ${\vec{s}}_i^{\prime }$ $\in R_q^{\lceil m/\mu \rceil }$
  • 2. use base protocol to prove the new witness
    • get new relation $g^{(k)}(\overrightarrow{s_1},...,\overrightarrow{s_{r^{\prime }}})$ $={\sum }_{i,j=1}^{r^{\prime }}{a}_{i,j}^{(k)}<{\vec{s}}_i,{\vec{s}}_j>+{\sum }_{i=1}^{r^{\prime }}<{\phi }_i^{(k)},{\vec{s}}_i>-b^{(k)}=0$
    • $k=1,...,\kappa +{\kappa }_1+{\kappa }_2+3$
    • $a_{ij}$ value refer page 15
  • 3. keep recursing, until proof is small enough
    • need O(log log n) iterations
    • in practice , 6-7 iterations gives the best results
  • 4. norm check
    • $||{\vec{z}}^{(0)}|{|}^2+||{\vec{z}}^{(1)}|{|}^2+||\vec{v}|{|}^2\le \frac{2}{b^2}{\gamma }^2+{\gamma }_1^2+{\gamma }_2^2$
    • verifier checks(without recursion)
• data structure
  • ${\vec{z}}^{(0)},{\vec{z}}^{(1)}\in R_q^n$
  • ${\vec{z}}^{(0)}||{\vec{z}}^{(1)}\in R_q^{2n}$
  • $\vec{v}$ $\in R_q^m$
• params
  • $2n\approx m$
  • $\gamma ,{\gamma }_1,{\gamma }_2,{\beta }^{\prime }$ (page 19)
  • $\frac{n}{\nu }\approx \frac{m}{\mu }$
  • $r^{\prime }=2\nu +\mu =O(r^{1/3})$ is optimal(page 5)