DEEP-FRI: Sampling Outside the Box Improves Soundness论文学习笔记

1. 引言

前序博客有:

  • DEEP FRI协议
  • A summary on the FRI low degree test前2页导读
  • RISC Zero的手撕STARK
  • Reed-Solomon Codes——RS纠错码
  • Reed-Solomon Codes及其与RISC Zero zkVM的关系

Eli Ben-Sasson等人2019年论文《DEEP-FRI: Sampling Outside the Box Improves Soundness》。

为追求scalable and succinct zero knowledge arguments,重新审视了linear spaces中的worst-case-to-average-case reductions。

2018年《Worst-case to average case reductions for the distance to a code》论文中指出:

  • worst-case是指:affine space U U U某些元素,与linear code V V V的relative Hamming distance为 δ \delta δ-far
  • average-case是指:affine space U U U大多数元素,与linear code V V V的relative Hamming distance为 almost- δ \delta δ-far

不过以上结论仅当 δ < 1 − ( 1 − δ V ) 1 / 4 \delta<1-(1-\delta_V)^{1/4} δ<1(1δV)1/4时成立,其中:

  • δ V \delta_V δV:为code V V V的relative distance。
  • δ < 1 − ( 1 − δ V ) 1 / 4 \delta<1-(1-\delta_V)^{1/4} δ<1(1δV)1/4 δ V \delta_V δV的“double Johnson”函数。

本文:

  • 1)将以上soundness-bound增加为 δ V \delta_V δV的“one-and-a-half Johnson”函数。并展示了:
    • 对于任意的worst-case distance δ < 1 − ( 1 − δ V ) 1 / 3 \delta<1-(1-\delta_V)^{1/3} δ<1(1δV)1/3 U U U V V V的average distance几乎为 δ \delta δ
    • 该bound是tight紧凑的,一定程度来说令人吃惊,因为one-and-a-half Johnson函数在error correcting codes文献中并不常见。
  • 2)为进一步改进Reed Solomon codes,所采取的措施为:在该box之外进行采样。为此:
    • 引入了一种新技术——DEEP:
      • Verifier在box D D D之外采样单个点 z z z,基于该点 z z z来evaluate codewords。
      • Verifier要求Prover提供, U U U中某随机元素的插值多项式在点 z z z的evaluation值。
      • 直接来说,这会“force” Prover在一组close to U U U的“pretenders”中选择一个codeword。
      • 称该技术为Domain Extending for Eliminating Pretenders(DEEP)。
    • DEEP方法将,对RS codes的worst-case-to-average-case reduction的soundness,改进到为其list decoding radius。该半径的边界由Johnson bound限定,即意味着对于所有 δ < 1 − ( 1 − δ V ) 1 / 2 \delta<1-(1-\delta_V)^{1/2} δ<1(1δV)1/2,average distance接近于 δ \delta δ。在某个关于Reed-Solomon codes的list decoding radius的plausible conjecture下,对于所有的 δ \delta δ,与 V V V的 average distance 为 δ \delta δ
    • 该DEEP技术可推广用于所有的linear code,giving improved reductions for capacity-achieving list-decodable codes。
  • 3)基于DEEP技术设计了2种新的协议:
    • DEEP-FRI协议:为Interactive Oracle Proof of Proximity (IOPP) for RS codes。DEEP-FRI协议 改进了FRI协议的soundness,同时保持了其线性化算术证明复杂度和对数化verifier算术复杂度。
    • DEEP-ALI协议:Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) 。用于构建ZK-STARKs(zero knowledge scalable transparent arguments of knowledge)。将STARK中ALI的soundness,由small constant < 1 / 8 <1/8 <1/8,改进为了任意接近 1 1 1的constant。

算术化是一项了不起的技术,可用来reduce问题的计算复杂性,如,将,在不确定语言中验证membership,的问题,reduce为,Reed-Solomon(RS)codes 和Reed-Mull(RM)codes等代数码中向量的membership问题。
这种reduction最终对应的是RS Proximity Testing(RPT)问题。RPT问题既是固有的理论兴趣问题,也具有重要的实际意义,因为其最近被用于构建succinct zero knowledge arguments,包括但不限于:

  • Ligero
  • Aurora
  • ZK-STARKs

在RPT问题中:

  • 1)Verifier对函数 f : D → F f:D\rightarrow \mathbb{F} f:DF具有oracle access。称 D ⊂ F D\subset \mathbb{F} DF为evaluation domain。
  • 2)RPT问题的任务在于:区分:
    • “good” case: f f f为degree最多为 d d d的多项式
    • 和 “bad” case: f f f与所有degree- d d d多项式的relative Hamming distance为 δ \delta δ-far。
  • 3)为实现“poly-logarithmic in d d d”的succinct verification time,必须支持Verifier以某种形式与Prover交互。所谓Prover,是声称 deg ⁡ ( f ) ≤ d \deg(f)\leq d deg(f)d的一方。
    • 3.1)早期,这种交互形式为:Prover提供的,除 f f f之外的,对probabilistically checkable proof of proximity(PCPP)的oracle access。这种模式下,RPT问题,可由PCPPs “solved”,对应有:
      • quasilinear size ∣ D ∣ p o l y log ⁡ ∣ D ∣ |D|poly\log |D| DpolylogD
      • constant query complexity
      • constant soundness
      • 但是,即使考虑实际用到的适度小的实例size,相应的Prover time、Verifier time和communication复杂度都很大。
    • 3.2)为改进Prover time、Verifier time和communication,采用Interactive Oracle Proofs of Proximity (IOPP)模式更适合。IOPP可看成是multi-round PCPP。IOPP中,Prover无需像PCPP那样写下单个proof π \pi π。在IOPP设置中:
      • 可通过多轮交互来生成proof oracle,在交互期间,Verifier发送random bits,Prover响应额外的(long)messages,这些(long)messages支持Verifier进行oracle access。
      • 这些额外的交互轮,可大幅改进 “解决RPT问题”的近似复杂度和实际复杂度。
      • 特别地,Fast RS IOPP (FRI) 协议具有线性化Prover算术复杂度、对数化Verifier算术复杂度和constant soudness。

本文的目的是:

  • 改进FRI协议的soundness,
  • 在high-error机制(也称为“list decoding”机制)中,推荐在soundness方面更好的协议。

FRI soundness分析,reduce为,遵循关于linear space的自然“worst-case-to-average-case”问题,该问题在通用(non-RS)codes领域也非常有趣。

1.1 距离某linear code的maximum distance vs average distance

令:

  • U ⊂ F D U\subset \mathbb{F}^D UFD为“line”(即一维) affine space over F \mathbb{F} F
  • u ∗ ∈ F D u^*\in \mathbb{F}^D uFD来表示该line的起始点, u u u表示其斜率,从而有 U = { u x = u ∗ + x u ∣ x ∈ F } U=\{u_x=u^*+xu|x\in\mathbb{F}\} U={ux=u+xuxF}

本文的worst-case assumption为:

  • 对于某固定的linear space V ⊂ F D V\subset \mathbb{F}^D VFD,从 U U U中选择离 V V V最远的一个元素 u ∗ u^* u u ∗ u^* u V V V的relative Hamming distance表示为 δ m a x \delta_{max} δmax

令:

  • δ x = Δ ( u x , V ) \delta_x=\Delta(u_x,V) δx=Δ(ux,V),其中 Δ \Delta Δ表示relative Hamming distance。
  • E x ∈ F [ δ x ] E_{x\in \mathbb{F}}[\delta_x] ExF[δx]表示 u x u_x ux V V Vexpected distance。其演变历史为:
    • 2013年,[RVW13]展示对所有的 U , V U,V U,V space,有 E x [ δ x ] ≥ δ m a x 2 − o ( 1 ) E_x[\delta_x]\geq \frac{\delta_{max}}{2}-o(1) Ex[δx]2δmaxo(1),其中 o ( 1 ) o(1) o(1)表示可忽略项,因随着 ∣ F ∣ → ∞ |\mathbb{F}|\rightarrow \infty F,该项值趋近于0。【严格限定了expected distance小于 δ m a x \delta_{max} δmax。】
    • 2018年,[BKS18a]中发现该average distance scales roughly like 关于 δ m a x \delta_{max} δmax的Johnson list-decoding函数,改进为 E x [ δ x ] ≥ 1 − 1 − δ m a x − o ( 1 ) E_x[\delta_x]\geq 1-\sqrt{1-\delta_{max}}-o(1) Ex[δx]11δmax o(1)。其中Johnson list-decoding函数表示为 J ( x ) : = 1 − 1 − x J(x):=1-\sqrt{1-x} J(x):=11x 。【严格限定了expected distance小于 δ m a x \delta_{max} δmax。】
      • [BKS18a]中还发现,当 V V V是具有large relative distance δ V \delta_V δV的(linear)error correcting code,若 δ m a x \delta_{max} δmax小于 关于 δ V \delta_V δV的“double Johnson”函数,则其average distance几乎不恶化,有:【其中“double Johnson”函数表示为 J ( 2 ) ( x ) : = J ( J ( x ) ) J^{(2)}(x):=J(J(x)) J(2)(x):=J(J(x))。】
        E [ δ x ] ≥ min ⁡ ( δ m a x , J ( 2 ) ( δ V ) ) − o ( 1 ) = min ⁡ ( δ m a x , 1 − 1 − δ V 4 ) − o ( 1 ) \begin{equation} E[\delta_x]\geq \min(\delta_{max}, J^{(2)}(\delta_V))-o(1)=\min(\delta_{max}, 1-\sqrt[4]{1-\delta_{V}})-o(1) \end{equation} E[δx]min(δmax,J(2)(δV))o(1)=min(δmax,141δV )o(1)

本文:

  • 1)改进了上面的方程式(1)为 “one-and-a-half-Johnson”函数—— J ( 1.5 ) ( x ) = 1 − ( 1 − x ) 1 / 3 J^{(1.5)}(x)=1-(1-x)^{1/3} J(1.5)(x)=1(1x)1/3。即对于relative Hamming distance δ V \delta_V δV的codes V V V,其expected distance为:
    E [ δ x ] ≥ min ⁡ ( δ m a x , J ( 1.5 ) ( δ V ) ) − o ( 1 ) = min ⁡ ( δ m a x , 1 − 1 − δ V 3 ) − o ( 1 ) \begin{equation} E[\delta_x]\geq \min(\delta_{max}, J^{(1.5)}(\delta_V))-o(1)=\min(\delta_{max}, 1-\sqrt[3]{1-\delta_{V}})-o(1) \end{equation} E[δx]min(δmax,J(1.5)(δV))o(1)=min(δmax,131δV )o(1)

  • 2)发现上面的方程式(2)是tight的——即使对 V V V为RS code时也是tight的。同时发现, J ( 1.5 ) ( x ) J^{(1.5)}(x) J(1.5)(x)在现有任何coding理论中都是未知的。
    以下反例展示了对非常特殊的情况下,上面方程式(2)的tightness会增加:

    • 2.1) F \mathbb{F} F为(characteristic为 2 2 2的)binary field
    • 2.2)rate ρ \rho ρ 1 / 8 = 2 − 3 1/8=2^{-3} 1/8=23
    • 2.3)evaluation domain D D D等于所有 F \mathbb{F} F【最重要的一点】

    粗略来说,该反例使用函数 u ∗ , u : F 2 n → F 2 n u^*,u:\mathbb{F}_{2^n}\rightarrow \mathbb{F}_{2^n} u,u:F2nF2n,与伪装为low-degree但实际degree为 ρ 2 n \rho 2^n ρ2n的多项式距离为 3 / 4 = 1 − ρ 2 / 3 3/4=1-\rho^{2/3} 3/4=1ρ2/3-far,因为对于所有的 x ∈ F 2 n ∖ { 0 } x\in\mathbb{F}_{2n}\setminus \{0\} xF2n{0},函数 u ∗ + x u u^*+xu u+xu与degree为 ρ 2 n \rho 2^n ρ2n的多项式为 1 / 2 = ρ 3 1/2=\sqrt[3]{\rho} 1/2=3ρ -close。

1.2 Domain Extension for Eliminating Pretenders(DEEP)

本文重点关注的是, V V V为RS code的场景。

rate为 ρ \rho ρ、基于 D D D evaluate的RS code表示为:
R S [ F , D , ρ ] : = { f : D → F ∣ deg ⁡ ( f ) < ρ ∣ D ∣ } RS[\mathbb{F}, D,\rho]:=\{f: D\rightarrow \mathbb{F} | \deg(f)<\rho |D|\} RS[F,D,ρ]:={f:DFdeg(f)<ρD}

RS codes为maximum distance separable(MDS),即意味着 δ V = 1 − ρ \delta_V=1-\rho δV=1ρ,因此上面的方程式(2)可简化为:
E [ δ x ] ≥ min ⁡ ( δ m a x , 1 − ρ 3 ) − o ( 1 ) \begin{equation} E[\delta_x]\geq \min(\delta_{max}, 1-\sqrt[3]{\rho})-o(1) \end{equation} E[δx]min(δmax,13ρ )o(1)

做一些额外工作,可将该improved bound转换为具有类似保证的FRI soundness分析。以上方程式(3)意味着:

  • 对,距离 R S [ F , D , ρ ] RS[\mathbb{F}, D,\rho] RS[F,D,ρ] δ \delta δ-far的 f : D → F f:D\rightarrow \mathbb{F} f:DF,触发单次FRI QUERY test的soundness error最多为 max ⁡ { 1 − δ , ρ 3 } \max\{1-\delta,\sqrt[3]{\rho}\} max{1δ,3ρ }。其中"单次FRI QUERY test"中,包含了 log ⁡ ∣ D ∣ \log |D| logD次query。
    • 并可将其插入到ZK-STARKs和ZK-SNARGs(如Aurora)中。

粗略来说,若 δ \delta δ-far words的拒绝概率为 max ⁡ ( δ , δ 0 ) \max (\delta,\delta_0) max(δ,δ0),则对于blocklength为 n n n的codes:

  • 其可达到的soundness error < 2 − λ <2^{-\lambda} <2λ
  • communication复杂度(和verifier复杂度)scale roughly like λ log ⁡ δ 0 ⋅ c ⋅ log ⁡ n \frac{\lambda}{\log \delta_0}\cdot c\cdot \log n logδ0λclogn for some constant c c c

因此,从方程式(1)到方程式(2),verifier复杂度降低了 25 % 25\% 25%——由 4 λ log ⁡ ρ ⋅ c ⋅ log ⁡ n \frac{4\lambda}{\log \rho}\cdot c\cdot \log n logρ4λclogn降低为 3 λ log ⁡ ρ ⋅ c ⋅ log ⁡ n \frac{3\lambda}{\log \rho}\cdot c\cdot \log n logρ3λclogn

为打破方程式(2)中的soundness bound,进一步降低verifier复杂度,引入了一种新方法:

  • u ∗ , u : D → F u^*,u:D\rightarrow\mathbb{F} u,u:DF确实为2个degree d d d多项式( P ∗ P^* P P P P)的evaluation,则verifier可:
    • 将domain D D D 扩展到更大的 D ˉ \bar{D} Dˉ
    • 随机取样 z ∈ D ˉ z\in\bar{D} zDˉ,然后请求evaluation值 P ∗ ( z ) P^*(z) P(z) P ( z ) P(z) P(z)
    • 根据prover回复的 P ∗ ( z ) P^*(z) P(z) P ( z ) P(z) P(z),以local方式,修改每个 u ∗ , u u^*,u u,u,以反映该new knowledge,且与此同时,可削减 u ∗ u^* u u u u可能伪装的多项式large list。
    • 若诚实的prover返回的是正确的 α ∗ = P ∗ ( z ) , α z = P ( z ) \alpha^*=P^*(z),\alpha_z=P(z) α=P(z),αz=P(z)值,则有 ( X − z ) ∣ P ∗ ( X ) − α z ∗ (X-z)|P^*(X)-\alpha_z^* (Xz)P(X)αz ( X − z ) ∣ P ( X ) − α z (X-z)|P(X)-\alpha_z (Xz)P(X)αz
      • α x = α ∗ + x α \alpha_x=\alpha^*+x\alpha αx=α+ P x ( X ) = P ∗ ( X ) + x P ( X ) P_x(X)=P^*(X)+xP(X) Px(X)=P(X)+xP(X),有 ( X − z ) ∣ P x ( X ) − α x (X-z)|P_x(X)-\alpha_x (Xz)Px(X)αx
      • 极端情况下, u ∗ u^* u具有以小组多项式,这小组多项式中的每一个,大概率在 z z z点都有相同的值,即prover所提供的任意答案,都将与该小组中最多一个多项式 一致。【相应证明见Therorem 4.1。】

对于半径 δ \delta δ,令 L δ ∗ = max ⁡ u ∗ ∈ F D ∣ { v ∈ V ∣ Δ ( u ∗ , v ) < δ } ∣ L_{\delta}^*=\max_{u^*\in\mathbb{F}^D}|\{v\in V| \Delta(u^*,v)<\delta\}| Lδ=maxuFD{vV∣Δ(u,v)<δ},其中 Δ \Delta Δ表示relative Hamming distance。令 V ∣ u x ( z ) = α x V|_{u_x(z)=\alpha_x} Vux(z)=αx限制 V V V中codewords 为degree最多为 d d d的多项式的evaluations——在 z z z点的evaluation值为 α x \alpha_x αx

本文Theorem 4.1中展示了,若 Δ ( u ∗ , V ) = δ m a x \Delta(u^*,V)=\delta_{max} Δ(u,V)=δmax,则对应query点 z z z所回复的 α z ∗ , α z \alpha_z^*,\alpha_z αz,αz,有:
E z , x [ Δ ( u x , V ∣ u x ( z ) = α x ) ] ≥ δ m a x − L δ ∗ ⋅ ( ρ ∣ D ∣ ∣ D ˉ ∣ ) 1 / 3 − o ( 1 ) \begin{equation} E_{z,x}[\Delta(u_x,V|_{u_x(z)=\alpha_x})]\geq \delta_{max} - L_{\delta}^*\cdot (\frac{\rho |D|}{|\bar{D}|})^{1/3}-o(1) \end{equation} Ez,x[Δ(ux,Vux(z)=αx)]δmaxLδ(DˉρD)1/3o(1)

Theorem 2.2中的Johnson bound中指出,当 δ < J ( 1 − ρ ) = 1 − ρ \delta<J(1-\rho)=1-\sqrt{\rho} δ<J(1ρ)=1ρ ,有 L δ ∗ = O ( 1 ) L_{\delta}^*=O(1) Lδ=O(1),并将方程式(2)中的worst-case-to-average-case bound,改进为匹配Johnson bound:
E z , x [ Δ ( u x , V ∣ u x ( z ) = α x ) ] ≥ min ⁡ ( δ m a x , J ( δ V ) ) − o ( 1 ) = min ⁡ ( δ m a x , ρ ) − o ( 1 ) \begin{equation} E_{z,x}[\Delta(u_x,V|_{u_x(z)=\alpha_x})]\geq \min (\delta_{max}, J(\delta_V))-o(1)=\min (\delta_{max},\sqrt{\rho})-o(1) \end{equation} Ez,x[Δ(ux,Vux(z)=αx)]min(δmax,J(δV))o(1)=min(δmax,ρ )o(1)

超过Johnson bound之外的Reed-Solomon codes的list size的准确行为,是著名的开放难题。对于半径远大于Johnson bound的情况,其list size可能是small的——事实上,对大多数domain D D D其都是成立的[RW14]。若其成立,即意味着即使半径等于 δ V = 1 − ρ \delta_V=1-\rho δV=1ρ(即,若Reed-Solomon codes meet list-decoding capacity),其list size也是small的,则说明几乎对所有的distance参数,方程式(5)都有优化soundness。

将以上Reed-Solomon codes结论 推广到 任意linear codes:

  • DEEP方法可用于改进通用linear codes的 worst-to-average-case。将 V V V中的codewords看成是domain D D D中evaluations的线性组合,可请求对应该线性组合中的 u ∗ , u u^*,u u,u在随机点 z ∈ D ˉ z\in\bar{D} zDˉ的evaluation值,其中 ∣ D ˉ ∣ ≫ ∣ D ∣ |\bar{D}|\gg |D| DˉD。Lemma 4.6概括了Theorem 4.1:
    • V V V具有(small list size的)near-capacity list-decoding半径,且 D ˉ \bar{D} Dˉ对应(某generating矩阵各列的)good error correcting code,则有 E x [ δ x ] ≈ δ m a x E_x[\delta_x]\approx\delta_{max} Ex[δx]δmax
  • 任意linear codes和RS code情况下的区别在于:
    • RS code场景下,verifier可使用,prover所回复的 α ∗ ( x ) , α ( x ) \alpha^*(x),\alpha(x) α(x),α(x),在本地修改 u x u_x ux元素,以降低最终函数的degree。而对所有linear codes来说,其不具备该属性。

1.3 DEEP-FRI

将DEEP技术用于FRI协议,需要做相应修改。

FRI协议可描述为“随机folding” (inverse) Fast Fourier Transform(iFFT)计算的过程。在“经典”iFFT中:

  • 初始函数 f ( 0 ) : < w > → F f^{(0)}:<w>\rightarrow \mathbb{F} f(0):<w>→F,其中 w w w为generator,用于生成order为 2 k 2^k 2k的multiplicative group, k k k为整数。
  • iFFT计算函数 f f f的插值多项式 f ~ ( X ) \tilde{f}(X) f~(X),计算复杂度为 O ( k 2 k ) O(k2^k) O(k2k)
  • 以线性时间计算一组函数 f 0 , f 1 : < w 2 > → F f_0,f_1:<w^2>\rightarrow \mathbb{F} f0,f1:<w2>→F,注意有 ∣ < w 2 > ∣ = 1 2 ∣ < w > ∣ |<w^2>|=\frac{1}{2}|<w>| <w2>=21<w>。相应的插值多项式 f ~ 0 , f ~ 1 \tilde{f}_0,\tilde{f}_1 f~0,f~1可用于计算 f f f的插值多项式 f ~ \tilde{f} f~

如《Fast Reed-Solomon Interactive Oracle Proofs of Proximity》中所述,以上FRI协议中:

  • Prover首先对 f f f进行commit
  • Verifier采样随机值 x ( 0 ) ∈ F x^{(0)}\in \mathbb{F} x(0)F
  • 协议继续处理单个函数 f ( 1 ) : < w 2 > → F f^{(1)}:<w^2>\rightarrow \mathbb{F} f(1):<w2>→F,其满足 f ( 1 ) : = f 0 + x ( 0 ) f 1 f^{(1)}:=f_0+x^{(0)}f_1 f(1):=f0+x(0)f1
  • f f f的degree确实小于 ρ ∣ < w > ∣ \rho |<w>| ρ<w>,则对于所有的 x x x,有 f ( 1 ) f^{(1)} f(1)的degree小于 ρ ∣ < w 2 > ∣ \rho|<w^2>| ρ<w2>
  • 其中棘手的部分在于:当 f f f R S [ F , < w > , ρ ] RS[\mathbb{F},<w>,\rho] RS[F,<w>,ρ] δ \delta δ-far,则大概率基于 x x x f ( 1 ) f^{(1)} f(1)也是 δ ′ \delta' δ-far,其中 δ ′ \delta' δ δ \delta δ尽可能近。
  • 方程式(2)和Lemma 3.1中的worst-case-to-average-case结论,可转换为类似对FRI的改进,即对于 δ < 1 − ρ 3 \delta<1-\sqrt[3]{\rho} δ<13ρ ,有 δ ′ ≈ δ \delta'\approx \delta δδ

在这里插入图片描述
DEEP-FRI协议:

  • 为将方程式(4)和Theorem 4.1中的DEEP技术用于改进RS-IOPP soundness,而对FRI协议做了修改。
  • 与FRI协议的不同之处在于:
    • 不直接构建 f ( 1 ) f^{(1)} f(1),而是verifier先发送随机采样点 z ( 0 ) ∈ F z^{(0)}\in\mathbb{F} z(0)F,并向prover请求插值多项式 f ( 0 ) f^{(0)} f(0) z ( 0 ) z^{(0)} z(0) − z ( 0 ) -z^{(0)} z(0)点的evaluation值。
    • 在收到 α z ( i ) , α − z ( i ) \alpha_{z^{(i)}},\alpha_{-z^{(i)}} αz(i),αz(i)之后,继续采样 x ( 0 ) x^{(0)} x(0),并期待Prover所submit的 f ( 1 ) f^{(1)} f(1) f 0 ′ , f 1 ′ f_0',f_1' f0,f1的线性组合。其中 f 0 ′ , f 1 ′ f_0',f_1' f0,f1派生自 f f f f ′ f' f,而 f ′ f' f中已包含了之前回复的 α z ( i ) , α − z ( i ) \alpha_{z^{(i)}},\alpha_{-z^{(i)}} αz(i),αz(i)
    • 假设 f ~ \tilde{f} f~ f f f的插值多项式,则诚实的Prover将设置 f ′ ( X ) : = ( f ~ ( X ) − U ( X ) ) / Z ( X ) f'(X):=(\tilde{f}(X)-U(X))/Z(X) f(X):=(f~(X)U(X))/Z(X),其中:
      • U ( X ) U(X) U(X)为degree ≤ 1 \leq 1 1的多项式,其在 z ( 0 ) z^{(0)} z(0)点的evaluation值为 α z ( 0 ) \alpha_{z^{(0)}} αz(0),在 − z ( 0 ) -z^{(0)} z(0)点的evaluation值为 α − z ( 0 ) \alpha_{-z^{(0)}} αz(0)
      • Z ( X ) Z(X) Z(X)为首项系数为1且degree为2的多项式,其roots为 z ( 0 ) , z ( 0 ) z^{(0)},z^{(0)} z(0),z(0)

详情见本论文Section 5,方程式(4)和Theorem 4.1的soundness bound适用于DEEP-FRI:

  • list-size为“small”的情况下,对于任意小于最大半径的 δ \delta δ,DEEP-FRI的soundness,即拒绝 距离 R S [ F , D , ρ ] RS[\mathbb{F},D,\rho] RS[F,D,ρ] δ \delta δ-far 的words 的概率约为 δ \delta δ

1.4 DEEP Algebraic Linking IOP (DEEP-ALI)

1.3节中仅讨论了改进Reed-Solomon Proximity Testing(RPT)的结论。

本节将讨论:

  • 如何使用RPT结论来改进基于IOP的证明系统的soundness?

为利用RPT改进的soundness优势:

  • 需要某种reduction来生成RPT problem实例。当input instance是unsatisfiable时,对应所生成的RPT problem实例应 far from the relevant RS code
    • 在2018年《Scalable, transparent, and post-quantum secure computational integrity》论文中,提出了Algebraic Linking IOP (ALI)协议。
      • 该RPT problem实例派生自ALI中的某unsatisfiable instance。并证明了其是far from low-degree的,但在该论文中所证明的distance bound为 < 1 / 8 <1/8 <1/8——即使RS code中所使用的rate ρ \rho ρ可忽略。【也在Aurora论文中有类似猜想。】
    • 本文Section 6中,与DEEP-FRI修改类似,也采用了DEEP技术来改进ALI协议。
      • 修改之后的DEEP-ALI协议,适用于方程式(4)中的soundness结论。且当提供unsatisfiable instances时,借助DEEP-ALI协议所生成的received words的distance至少为 1 − ρ − o ( 1 ) 1-\sqrt{\rho}-o(1) 1ρ o(1)。【也可能更大,详情见Conjecture 2.3。】

2. 预备知识

  • 1)Functions函数:对于集合 D D D,本文关注的函数 u : D → F u:D\rightarrow \mathbb{F} u:DF 空间,表示为 F D \mathbb{F}^D FD

    • 对于 u ∈ F D u\in\mathbb{F}^D uFD z ∈ D z\in D zD,使用 u ( z ) u(z) u(z)来表示 u u u的第 z z z个元素。
    • 对于 C ⊂ D C\subset D CD,使用 f ∣ C f|_C fC来表示限定 f f f C C C
    • 对于2个函数 f , g : D → F f,g:D\rightarrow \mathbb{F} f,g:DF,以 f = g f=g f=g来表示对于 F D \mathbb{F}^D FD中的元素,这两个函数相等;以 f ∣ C = g ∣ C f|_C=g|_C fC=gC来表示当限定元素为 F C \mathbb{F}^C FC时,二者是相等的。
  • 2)Distance距离:以 Δ D ( u , v ) = Pr ⁡ z ∈ D [ u ( z ) ≠ v ( z ) ] \Delta_{D}(u,v)=\Pr_{z\in D}[u(z)\neq v(z)] ΔD(u,v)=PrzD[u(z)=v(z)]来表示relative Hamming distance,并在上下文清晰的情况下,可忽略 D D D

    • 对于集合 S ⊂ F D S\subset \mathbb{F}^D SFD,使用 Δ D ( v , S ) = min ⁡ s ∈ S Δ D ( v , s ) \Delta_D(v,S)=\min_{s\in S}\Delta_D(v,s) ΔD(v,S)=minsSΔD(v,s) Δ D ( S ) = min ⁡ s ≠ s ′ ∈ S Δ D ( s , s ′ ) \Delta_D(S)=\min_{s\neq s'\in S}\Delta_D(s,s') ΔD(S)=mins=sSΔD(s,s)来表示 S S S的minimal relative distance。
    • 对于 u ∈ F D u\in \mathbb{F}^D uFD,将,以 u u u为中心,归一化 δ \delta δ为半径的 F D \mathbb{F}^D FD Hamming ball,表示为 B ( u , δ ) B(u,\delta) B(u,δ),有: B ( u , δ ) = { u ′ ∈ F D ∣ Δ D ( u , u ′ ) < δ } B(u,\delta)=\{u'\in \mathbb{F}^D|\Delta_D(u,u')<\delta\} B(u,δ)={uFDΔD(u,u)<δ}
  • 3)Linear codes: [ n , k , d ] q [n,k,d]_q [n,k,d]q-linear error correcting code为基于 F q \mathbb{F}_q Fq域的、dimension为 k k k的、最小Hamming distance为 d d d的线性空间 V ⊂ F q n V\subset \mathbb{F}_q^n VFqn

    • V V V的generating矩阵表示为具有rank k k k的矩阵 G ∈ F q n × k G\in \mathbb{F}_q^{n\times k} GFqn×k,其满足 V = { G x ∣ x ∈ F q k } V=\{Gx|x\in \mathbb{F}_q^k\} V={GxxFqk}
  • 4)Polynomials and RS codes: f : D → F f:D\rightarrow \mathbb{F} f:DF的插值多项式是唯一的,该插值多项式的degree < ∣ D ∣ <|D| <D,且其在 D D D domain的evaluation值为 f f f

    • deg ⁡ ( f ) \deg(f) deg(f)表示 f f f的degree——即为其插值多项式的degree。
    • 基于domain D ⊂ F D\subset \mathbb{F} DF所evaluate的RS码 以及 rate ρ \rho ρ 表示为 R S [ F , D , ρ ] = { f : D → F ∣ deg ⁡ ( f ) < ρ ∣ D ∣ } RS[\mathbb{F},D,\rho]=\{f:D\rightarrow \mathbb{F}|\deg(f)<\rho |D|\} RS[F,D,ρ]={f:DFdeg(f)<ρD}
    • 有时,使用degree比使用rate来表达更合适,也可表示为 R S [ F , D , d ] = { f : D → F ∣ deg ⁡ ( f ) < d } RS[\mathbb{F},D,d]=\{f:D\rightarrow \mathbb{F}|\deg(f)<d\} RS[F,D,d]={f:DFdeg(f)<d}
    • 以大写字母,如 P , Q P,Q P,Q来表示多项式。
    • P ∈ R S [ F , D , ρ ] P\in RS[\mathbb{F},D,\rho] PRS[F,D,ρ]即意味着 deg ⁡ ( P ) < ρ ∣ D ∣ \deg(P)<\rho |D| deg(P)<ρD
    • P P P与某RS codeword关联,是指其为 D D D的evaluation值。
    • f ~ \tilde{f} f~来表示对函数 f f f的插值多项式。

2.1 List Decoding

Reed-Solomon Codes的list size定义为:

  • 对于 u ∈ F D u\in\mathbb{F}^D uFD,集合 V ⊂ F D V\subset \mathbb{F}^D VFD,以及distance参数 δ ∈ [ 0 , 1 ] \delta\in [0,1] δ[0,1]
  • L i s t ( u , V , δ ) List(u,V,\delta) List(u,V,δ) V V V中某些元素的集合,这些元素离 u u u的relative Hamming distance最多为 δ \delta δ-far。
  • 使用 B ( u , δ ) B(u,\delta) B(u,δ)来表示,以 u u u为中心, δ \delta δ为相对半径的Hamming ball。
  • L i s t ( u , V , δ ) = B ( u , δ ) ∩ V List(u,V,\delta)=B(u,\delta)\cap V List(u,V,δ)=B(u,δ)V
  • 若对于所有的 u ∈ F q D u\in\mathbb{F}_q^D uFqD,有 ∣ L i s t ( u , V , δ ) ∣ ≤ L |List(u,V,\delta)|\leq L List(u,V,δ)L,则称code V V V δ , L \delta,L δ,L-list-decodable。
  • 对于 D ⊆ F q D\subseteq \mathbb{F}_q DFq V = R S [ F q , D , ρ = d / ∣ D ∣ ] V=RS[\mathbb{F}_q,D,\rho=d/|D|] V=RS[Fq,D,ρ=d/∣D],从所有的 u ∈ F q D u\in \mathbb{F}_q^D uFqD中取最大size的 L i s t ( u , V , δ ) List(u,V,\delta) List(u,V,δ),表示为 L ( F q , D , d , δ ) \mathcal{L}(\mathbb{F}_q,D,d,\delta) L(Fq,D,d,δ)

Johnson bound基础为:

  • 对于最小distance为large的集合,其具有nontrivial list-decodability。

根据[Gur07]论文的Theorem 3.3,设置 d = ( 1 − ρ ) ∣ D ∣ d=(1-\rho)|D| d=(1ρ)D e = ( 1 − ρ − ε ) ∣ D ∣ e=(1-\sqrt{\rho}-\varepsilon)|D| e=(1ρ ε)D,相应的Johnson bound具有如下定理:

  • V ⊂ F D V\subset \mathbb{F}^D VFD为最小相对距离为 1 − ρ 1-\rho 1ρ的code,其中 ρ ∈ ( 0 , 1 ) \rho\in (0,1) ρ(0,1)。则对于每个 ε ∈ ( 0 , 1 − ρ ) \varepsilon\in (0,1-\sqrt{\rho}) ε(0,1ρ ) V V V ( 1 − ρ − ε , 1 / ( 2 ε ρ ) ) (1-\sqrt{\rho}-\varepsilon,1/(2\varepsilon\sqrt{\rho})) (1ρ ε,1/(2ερ ))-list-decodable。

特别地,对于Reed-Solomon codes,其遵循如下list-decodability bound:
L ( F q , D , d = ρ ∣ D ∣ , 1 − ρ − ε ) ≤ O ( 1 ε ρ ) \mathcal{L}(\mathbb{F}_q,D,d=\rho|D|,1-\sqrt{\rho}-\varepsilon)\leq O(\frac{1}{\varepsilon \sqrt{\rho}}) L(Fq,D,d=ρD,1ρ ε)O(ερ 1)

本文非常乐观地希望对于具有中等list size的、distance最多为其Capacity的所有Reed-Solomon codes都是list-decodable的。为此,有如下勇敢地猜想——Conjecture 2.3(List decodability of Reed-Solomon Codes up to Capacity):

  • 对于每个 ρ > 0 \rho>0 ρ>0,存在某常量 C p C_p Cp,使得 每个长度为 n n n的Reed-Solomon code 和 rate ρ \rho ρ,都是list-decodable from 1 − ρ − ε 1-\rho-\varepsilon 1ρε fraction errors with list size ( n ε ) C p (\frac{n}{\varepsilon})^{C_p} (εn)Cp。即:
    L ( F q , D , d = ρ ∣ D ∣ , 1 − ρ − ε ) ≤ O ( ∣ D ∣ ε ) C p \mathcal{L}(\mathbb{F}_q,D,d=\rho|D|,1-\sqrt{\rho}-\varepsilon)\leq O(\frac{|D|}{\varepsilon})^{C_p} L(Fq,D,d=ρD,1ρ ε)O(εD)Cp

Theorem 4.1(DEEP method for RS codes)为:
在这里插入图片描述

5. DEEP-FRI

DEEP-FRI:

  • 为一种新的fast RS IOPP。

5.1 FRI

初始函数为 f ( 0 ) : L ( 0 ) → F f^{(0)}:L^{(0)}\rightarrow \mathbb{F} f(0):L(0)F,其中:

  • F \mathbb{F} F为某有限域。
  • evaluation domain L ( 0 ) ⊂ F L^{(0)}\subset \mathbb{F} L(0)F F \mathbb{F} F中某群的coset。若 F \mathbb{F} F为binary field,则该群为加法群;否则为乘法群。
  • ∣ L ( 0 ) ∣ = 2 k ( 0 ) |L^{(0)}|=2^{k^{(0)}} L(0)=2k(0)

假设目标rate为 ρ = 2 − R \rho=2^{-\mathcal{R}} ρ=2R,其中 R \mathcal{R} R为某正整数。

FRI协议用于让Verifier信服:

  • f ( 0 ) f^{(0)} f(0)接近于该Reed-Solomon code R S [ F , L ( 0 ) , ρ ] RS[\mathbb{F}, L^{(0)},\rho] RS[F,L(0),ρ]

FRI协议中有2大阶段:

  • COMMIT阶段:包含 r = k ( 0 ) − R r=k^{(0)}-\mathcal{R} r=k(0)R轮。
  • QUERY阶段

在Prover和Verifier开始做任何通讯之前,二者需对一系列sub-groups L ( i ) L^{(i)} L(i)(的cosets)达成一致,其中 ∣ L ( i ) ∣ = 2 k ( 0 ) − i |L^{(i)}|=2^{k^{(0)}-i} L(i)=2k(0)i。以 R S ( i ) RS^{(i)} RS(i)来表示Reed-Solomon code R S [ F , L ( i ) , ρ ∣ L ( i ) ∣ ] RS[\mathbb{F},L^{(i)},\rho|L^{(i)}|] RS[F,L(i),ρL(i)]

FRI协议的主要要素为:

  • 一种特殊的代数哈希函数 H x H_x Hx
    • 其输入有:seed x ∈ F x\in \mathbb{F} xF,和,函数 f : L ( i ) → F f:L^{(i)}\rightarrow \mathbb{F} f:L(i)F
    • 其输出为:长度为 f f f一半的hash。

准确来说,函数 H x [ f ] H_x[f] Hx[f]为:【详情见附录B】

  • H x [ f ] : L ( i + 1 ) → F H_x[f]:L^{(i+1)}\rightarrow \mathbb{F} Hx[f]:L(i+1)F

其具有如下属性:

  • 1)locality:对于任意的 s ∈ L ( i + 1 ) s\in L^{(i+1)} sL(i+1),可仅query f f f在其domain上的2个点,就可计算出 H x [ f ] H_x[f] Hx[f]。(这2个点为 ( q ( i ) ) − 1 ( s ) (q^{(i)})^{-1}(s) (q(i))1(s)
  • 2)completeness:若 f ∈ R S ( i ) f\in RS^{(i)} fRS(i),则对于所有的 x ∈ F x\in \mathbb{F} xF,有 H x [ f ] ∈ R S ( i + 1 ) H_x[f]\in RS^{(i+1)} Hx[f]RS(i+1)
  • 3)soundness:若 f f f为far from R S ( i ) RS^{(i)} RS(i),则大概率基于所选择的seed x x x H x [ f ] H_x[f] Hx[f]也会quite far from R S ( i + 1 ) RS^{(i+1)} RS(i+1)

其中completeness和soundness这两个属性,粗略说明了,基于随机 x x x H x H_x Hx将保持与Reed-Solomon codes的距离。

5.1.1 FRI COMMIT 阶段

FRI COMMIT 阶段流程为:

  • 1)对于 i = 0 i=0 i=0 i = r − 1 i=r-1 i=r1
    • 1.1)Verifier选择随机值 x ( i ) ∈ F x^{(i)}\in \mathbb{F} x(i)F,并发送给Prover。
    • 1.2)Prover写下函数 f ( i + 1 ) : L ( i + 1 ) → F f^{(i+1)}:L^{(i+1)}\rightarrow \mathbb{F} f(i+1):L(i+1)F。若Prover是诚实的,此时有 f ( i + 1 ) = H x ( i ) [ f ( i ) ] f^{(i+1)}=H_{x^{(i)}}[f^{(i)}] f(i+1)=Hx(i)[f(i)]
    • 1.3)重复以上流程,直到 i = r − 1 i=r-1 i=r1
  • 2)Prover写下value值 C ∈ F q C\in \mathbb{F}_q CFq。若Prover是诚实的, f r f^{r} fr为值为 C C C的常量函数。

5.1.2 FRI Query 阶段

FRI Query 阶段流程为:【由Verifier执行,因满足上面的属性1,Verifier可根据query值来做相应计算。】

  • 1)重复以下步骤 l l l次:【即Verifier对每一轮均做 l l l次query】
    • 1.1)选择随机值 s ( 0 ) ∈ L ( 0 ) s^{(0)}\in L^{(0)} s(0)L(0)
    • 1.2)对于 i = 0 i=0 i=0 i = r − 1 i=r-1 i=r1:【逐轮检查这些evaluation值的一致性】
      • 1.2.1)根据 s ( i + 1 ) = q ( i ) ( s ( i ) ) s^{(i+1)}=q^{(i)}(s^{(i)}) s(i+1)=q(i)(s(i))定义 s ( i + 1 ) ∈ L i + 1 s^{(i+1)}\in L^{i+1} s(i+1)Li+1
      • 1.2.2)根据对 f ( i ) f^{(i)} f(i)的2个query值,计算 H x ( i ) [ f ( i ) ] ( s ( i + 1 ) ) H_{x^{(i)}}[f^{(i)}](s^{(i+1)}) Hx(i)[f(i)](s(i+1))
      • 1.2.3)若 f ( i + 1 ) ( s ( i + 1 ) ) ≠ H x ( i ) [ f ( i ) ] ( s ( i + 1 ) ) f^{(i+1)}(s^{(i+1)})\neq H_{x^{(i)}}[f^{(i)}](s^{(i+1)}) f(i+1)(s(i+1))=Hx(i)[f(i)](s(i+1)),则REJECT。
  • 2)ACCEPT。

5.2 DEEP-FRI

DEEP-FRI为FRI的变种:

  • 具有改进的soundness
  • 代价是:增加了少量query复杂度。但不会增加proof length,也不会增加对committed proofs的query次数——实际应用中这很重要。

5.2.1 Quotienting

有集合 L ⊆ F q L\subseteq\mathbb{F}_q LFq和函数 f : L → F q f:L\rightarrow \mathbb{F}_q f:LFq。已知 point z ∈ F q z\in\mathbb{F}_q zFq 和 value b ∈ F q b\in\mathbb{F}_q bFq

Z ( Y ) ∈ F q [ Y ] Z(Y)\in\mathbb{F}_q[Y] Z(Y)Fq[Y]为多项式 Z ( Y ) = Y − z Z(Y)=Y-z Z(Y)=Yz。则定义 Q U O T I E N T ( f , z , b ) QUOTIENT(f,z,b) QUOTIENT(f,z,b)为函数 g : L → F q g:L\rightarrow \mathbb{F}_q g:LFq,有:
g ( y ) = f ( y ) − b Z ( y ) g(y)=\frac{f(y)-b}{Z(y)} g(y)=Z(y)f(y)b

也可简洁表示为: g = Q U O T I E N T ( f , z , b ) = f − b Z g=QUOTIENT(f,z,b)=\frac{f-b}{Z} g=QUOTIENT(f,z,b)=Zfb。其具有如下特性:
在这里插入图片描述

5.2.2 DEEP-FRI协议

有:

  • linear spaces: L ( 0 ) , L ( 1 ) , ⋯   , L ( r ) L^{(0)},L^{(1)},\cdots,L^{(r)} L(0),L(1),,L(r),分别具有的dimension为 k , k − 1 , ⋯   , k − r k, k-1,\cdots,k-r k,k1,,kr
  • 有subspaces: L 0 ( 0 ) , L 0 ( 1 ) , ⋯   , L 0 ( r ) L_0^{(0)},L_0^{(1)},\cdots,L_0^{(r)} L0(0),L0(1),,L0(r),dimension均为1。且有 L 0 ( i ) ⊆ L ( i ) L_0^{(i)}\subseteq L^{(i)} L0(i)L(i)
  • 注意,domain L ( 0 ) L^{(0)} L(0) 远小于 F q \mathbb{F}_q Fq域——可能有 q = ∣ L ( 0 ) ∣ Θ ( 1 ) q=|L^{(0)}|^{\Theta(1)} q=L(0)Θ(1)

DEEP-FRI协议的输入为:

  • 函数 f ( 0 ) : L ( 0 ) → F q f^{(0)}:L^{(0)}\rightarrow \mathbb{F}_q f(0):L(0)Fq,其具有的degree < d ( 0 ) <d^{(0)} <d(0)

DEEP-FRI协议的COMMIT阶段流程为:

  • 1)对于每个 i ∈ [ 0 , r − 1 ] i\in [0,r-1] i[0,r1],执行以下流程:
    • 1.1)Verifier选择随机值 z ( i ) ∈ F q z^{(i)}\in\mathbb{F}_q z(i)Fq
    • 1.2)Prover写下degree 1 1 1 多项式 B z ( i ) ( i ) ( X ) ∈ F q [ X ] B_{z^{(i)}}^{(i)}(X)\in\mathbb{F}_q[X] Bz(i)(i)(X)Fq[X],要求 B z ( i ) ( i ) ( x ) B_{z^{(i)}}^{(i)}(x) Bz(i)(i)(x)值 等于 低degree多项式 H x [ f ( i ) ] H_x[f^{(i)}] Hx[f(i)] z ( i ) z^{(i)} z(i)点的evaluation值。
    • 1.3)Verifier选择随机值 x ( i ) ∈ F q x^{(i)}\in\mathbb{F}_q x(i)Fq
    • 1.4)Prover写下函数 f ( i + 1 ) : L ( i + 1 ) → F q f^{(i+1)}:L^{(i+1)}\rightarrow \mathbb{F}_q f(i+1):L(i+1)Fq。若输入为 y y y,则其等于 Q U O T I E N T ( H x ( i ) [ f ( i ) ] , z ( i ) , B z ( i ) ( i ) ( x ) ) QUOTIENT(H_{x^{(i)}}[f^{(i)}],z^{(i)},B_{z^{(i)}}^{(i)}(x)) QUOTIENT(Hx(i)[f(i)],z(i),Bz(i)(i)(x))
    • 1.5)重复以上流程,直到 i = r − 1 i=r-1 i=r1
  • 2)Prover写下value C ∈ F q C\in\mathbb{F}_q CFq

DEEP-FRI Query 阶段流程为:【由Verifier执行,因满足上面的属性1,Verifier可根据query值来做相应计算。】

  • 1)重复以下步骤 l l l次:【即Verifier对每一轮均做 l l l次query】
    • 1.1)选择随机值 s ( 0 ) ∈ L ( 0 ) s^{(0)}\in L^{(0)} s(0)L(0)
    • 1.2)对于 i = 0 i=0 i=0 i = r − 1 i=r-1 i=r1:【逐轮检查这些evaluation值的一致性】
      • 1.2.1)根据 s ( i + 1 ) = q ( i ) ( s ( i ) ) s^{(i+1)}=q^{(i)}(s^{(i)}) s(i+1)=q(i)(s(i))定义 s ( i + 1 ) ∈ L i + 1 s^{(i+1)}\in L^{i+1} s(i+1)Li+1
      • 1.2.2)根据对 f ( i ) f^{(i)} f(i)的2个query值,计算 H x ( i ) [ f ( i ) ] ( s ( i + 1 ) ) H_{x^{(i)}}[f^{(i)}](s^{(i+1)}) Hx(i)[f(i)](s(i+1))
      • 1.2.3)若 H x ( i ) [ f ( i ) ] ( s ( i + 1 ) ) ≠ f ( i + 1 ) ( s ( i + 1 ) ) ⋅ ( s ( i + 1 ) − z ( i ) ) + B z ( i ) ( i ) ( x ( i ) ) H_{x^{(i)}}[f^{(i)}](s^{(i+1)})\neq f^{(i+1)}(s^{(i+1)})\cdot (s^{(i+1)}-z^{(i)})+B_{z^{(i)}}^{(i)}(x^{(i)}) Hx(i)[f(i)](s(i+1))=f(i+1)(s(i+1))(s(i+1)z(i))+Bz(i)(i)(x(i)),则REJECT。
  • 2)ACCEPT。

DEEP-FRI协议分析:
在这里插入图片描述

6. DEEP-ALI

DEEP Algebraic Linking IOP (DEEP-ALI) 。
可将以上Theorem 4.1和第5章技术用于改进 interactive oracle proof (IOP) protocol 中其它部分的soundness。本文将这些技术用于获得,比2018年《Scalable, transparent, and post-quantum secure computational integrity》论文Theorem 3.4,具有更好soundness的Scalable
Transparent IOP of Knowledge (STIK)。

证明系统中通常会用少量步骤来,将,nondeterministic language L L L下的membership problem,reduce为,对某种algebraic code(如Reed-Solomon)的proximity函数的algebraic problem。这种reduction的目的是:

  • 获取一个大的proximity gap γ \gamma γ,即意味着:
    • L L L中的实例,诚实的Prover将提供引导到codewords的信息;
    • 对非 L L L中的实例,Prover所提供的任何oracle,经该reduction转换后的函数,大概率与相应code是 δ \delta δ-far的。
    • 有大量研究致力于增加 δ \delta δ值,因其实FRI和DEEP-FRI这些proximity协议的输入,且这些协议的soundness与 δ \delta δ有关。

STIK协议是一种特例情况。STIK协议:

  • 要求Prover提供对函数 f : D → F f:D\rightarrow\mathbb{F} f:DF的oracle access,并假定函数 f : D → F f:D\rightarrow\mathbb{F} f:DF 是对 L L L中输入实例的membership witness的RS编码。
  • f f f应用一组 t t t-local约束,以构建函数 g : D → F g:D\rightarrow\mathbb{F} g:DF,要求其具有如下gap-guarantee:
    • f f f确实为该实例某有效witness的编码,则所获得函数 g : D → F g:D\rightarrow \mathbb{F} g:DF也是某RS code成员。
  • Verifier会在 f , g f,g f,g之间做consistency test
    • 在本文之前,都是直接 f , g f,g f,g做consistency test。这将导致非常小的 γ \gamma γ—— γ ≤ 1 8 \gamma\leq \frac{1}{8} γ81。从而导致 后续对 f , g f,g f,g应用RS Proximity Testing(RPT)协议提供small soundness。
    • 本文:通过应用DEEP技术:
      • 在提供完 f , g f,g f,g之后,Verifier提供随机值 z ∈ F q z\in\mathbb{F}_q zFq,并向Prover请求,检查 所有 t t t个约束consistency test所需的 f , g f,g f,g插值多项式值。
      • Verifier,使用从Prover中获得信息,对 f , g f,g f,g做QUOTIENT操作,

本文证明了,对基于large domain D ′ ⊃ D D'\supset D DD 的单个consistency test,足以将proximity gap改进为 1 − ρ 1-\sqrt{\rho} 1ρ ,当 ρ \rho ρ越接近于0时,该proximity gap约接近于1值。

本文基于Algebraic linking IOP protocol (ALI) 协议,获得改进了proximity gap的DEEP-ALI协议。

6.1 The Algebraic Placement and Routing (APR) Relation

接下来,以 f ~ \tilde{f} f~来表示 F [ x ] \mathbb{F}[x] F[x]中的某多项式。对 D ⊆ F D\subseteq \mathbb{F} DF的operator ∣ D |_D D,将多项式转变为函数: f ~ ∣ D : D → F \tilde{f}|_D:D\rightarrow \mathbb{F} f~D:DF

本文定义了简化版的 Algebraic placement and routing relation (APR),并仅使用一个witness多项式。该APR将用作Protocol 6.4中的reduction的输入。

Definition 6.1:Instance-Witness pairs ( X , W ) (\mathbb{X},\mathbb{W}) (X,W)集合的 R A P R R_{APR} RAPR relation满足:

  • 1)Instance格式:instance X \mathbb{X} X为tuple ( F q , d , C ) (\mathbb{F}_q, d,\mathcal{C}) (Fq,d,C),其中:
    • F q \mathbb{F}_q Fq:size为 q q q的有限域。
    • d d d:整数,表示witness degree的上限。
    • C \mathcal{C} C:为表示约束的 ∣ C ∣ |C| C个tuples ( M i , P i , Q i ) (M^i,P^i,Q^i) (Mi,Pi,Qi)集合:
      • M i M^i Mi:为mask,对应为一组域元素 M i = { M j i ∈ F q } j = 1 ∣ M i ∣ M^i=\{M_j^i\in\mathbb{F}_q\}_{j=1}^{|M^i|} Mi={MjiFq}j=1Mi
      • P i P^i Pi:为约束条件,对应为具有 ∣ M i ∣ |M^i| Mi个变量的多项式。
      • Q i ∈ F q [ x ] Q^i\in\mathbb{F}_q[x] QiFq[x]:为约束的domain多项式,其应在约束成立的位置vanish。
    • 此外,引入了如下标记符:
      • M = { M j i ∣ 1 ≤ i ≤ ∣ C ∣ 且 1 ≤ j ≤ ∣ M i ∣ } ⊆ F q \mathcal{M}=\{M_j^i|1\leq i\leq |\mathcal{C}|且1\leq j\leq |M^i|\}\subseteq \mathbb{F}_q M={Mji∣1iC1jMi}Fq为full mask。
      • d C = max ⁡ i deg ⁡ ( P i ) d_{\mathcal{C}}=\max_i\deg(P^i) dC=maxideg(Pi) P i P^i Pi的maximal total degree。
      • Q l c m ∈ F q [ x ] Q_{lcm}\in\mathbb{F}_q[x] QlcmFq[x] Q i Q^i Qi的最大公倍数。
  • 2)Witness格式:witness W \mathbb{W} W 为某多项式 f ~ ∈ F q \tilde{f}\in\mathbb{F}_q f~Fq
    • P ( f ~ ( x ⋅ M 1 ) , ⋯   , f ~ ( x ⋅ M ∣ M ∣ ) ) = 0 P(\tilde{f}(x\cdot M_1),\cdots,\tilde{f}(x\cdot M_{|M|}))=0 P(f~(xM1),,f~(xMM))=0,则称约束 ( M , P , Q ) (M,P,Q) (M,P,Q)在位置 x ∈ F q x\in\mathbb{F}_q xFq处成立。
    • 若在每个 x ∈ F q x\in\mathbb{F}_q xFq成立,有 Q ( x ) = 0 Q(x)=0 Q(x)=0,则称 f ~ \tilde{f} f~满足该约束。
    • 当且仅当 deg ⁡ ( f ~ ) < d \deg(\tilde{f})<d deg(f~)<d f ~ \tilde{f} f~ 满足所有约束,则称Witness W \mathbb{W} W 满足 Instance X \mathbb{X} X

本文遵循《Scalable, transparent, and post-quantum secure computational integrity》论文中的思想,并展示了由Algebraic Intermediate Representation(AIR)到APR的reduction:

  • X = ( F q , T , w , P , C , B ) \mathbb{X}=(\mathbb{F}_q,T,\mathbf{w},\mathcal{P},C,B) X=(Fq,T,w,P,C,B) R A I R R_{AIR} RAIR instance。
  • 选择size为 T ⋅ w T\cdot\mathbf{w} Tw的乘法子群 < γ > ⊆ F q × <\gamma>\subseteq\mathbb{F}_q^{\times} <γ>⊆Fq×,选择 f ~ \tilde{f} f~,使得对于 t ∈ [ T ] 和 i ∈ [ w ] t\in[T]和i\in[w] t[T]i[w],有 f ~ ( γ t w + j ) = w j ( t ) \tilde{f}(\gamma^{tw+j})=w_j(t) f~(γtw+j)=wj(t)。此处 [ n ] = { 0 , 1 , ⋯   , n − 1 } [n]=\{0,1,\cdots,n-1\} [n]={0,1,,n1}
  • 对于 P \mathcal{P} P中所有约束:
    • 选择mask M = { 1 , γ , ⋯   , γ 2 w − 1 } M=\{1,\gamma,\cdots,\gamma^{2\mathbf{w}-1}\} M={1,γ,,γ2w1}
    • 选择domain多项式,其在 { γ t w } t ∈ [ T − 1 ] \{\gamma^{t\mathbf{w}}\}_{t\in[T-1]} {γtw}t[T1]处均为0值,即 Q ( x ) = ( x T − 1 ) / ( x − γ − w ) Q(x)=(x^T-1)/(x-\gamma^{-w}) Q(x)=(xT1)/(xγw)
    • 将每个boundary约束 ( i , j , α ) ∈ B (i,j,\alpha)\in B (i,j,α)B,替换为常规约束—— M = { 1 } , P ( x ) = x − α , Q ( x ) = x − γ i w + j M=\{1\},P(x)=x-\alpha,Q(x)=x-\gamma^{i\mathbf{w}+j} M={1},P(x)=xα,Q(x)=xγiw+j

6.2 DEEP-ALI协议

Protocol 6.4:DEEP-ALI协议流程为:

  • 1)Prover发送 f : D → F f:D\rightarrow \mathbb{F} f:DF(实际应为 f ~ ∣ D \tilde{f}|_D f~D)的oracle。
  • 2)Verifier发送随机系数 α = ( α 1 , ⋯   , α C ) ∈ F q ∣ C ∣ \alpha=(\alpha_1,\cdots,\alpha_{\mathcal{C}})\in\mathbb{F}_q^{|\mathcal{C}|} α=(α1,,αC)FqC
  • 3)Prover发送 g α : D ′ → F g_{\alpha}:D'\rightarrow\mathbb{F} gα:DF(实际应为 g ~ α ∣ D ′ \tilde{g}_{\alpha}|_{D'} g~αD)的oracle,其中:
    g ~ α = ∑ i = 1 ∣ C ∣ α i ⋅ P i ( f ~ ( x ⋅ M 1 i ) , ⋯   , f ~ ( x ⋅ M ∣ M i ∣ i ) ) Q i ( x ) \begin{equation} \tilde{g}_{\alpha}=\sum_{i=1}^{|\mathcal{C}|}\alpha_i\cdot \frac{P^{i}(\tilde{f}(x\cdot M_1^i),\cdots,\tilde{f}(x\cdot M_{|M^i|}^i))}{Q^i(x)} \end{equation} g~α=i=1CαiQi(x)Pi(f~(xM1i),,f~(xMMii))
    注意: deg ⁡ ( g ~ α ) < d ⋅ d C \deg(\tilde{g}_{\alpha})<d\cdot d_{\mathcal{C}} deg(g~α)<ddC
  • 4)Verifier发送随机值 z ∈ F q z\in\mathbb{F}_q zFq
  • 5)令 M = { z ⋅ M j i ∣ 1 ≤ i ≤ ∣ C ∣ 且 1 ≤ j ≤ ∣ M i ∣ } \mathcal{M}=\{z\cdot M_j^i|1\leq i\leq |\mathcal{C}| 且 1\leq j\leq |M^i|\} M={zMji∣1iC1jMi}。Prover发送 a α , z : M z → F a_{\alpha,z}:\mathcal{M}_z\rightarrow \mathbb{F} aα,z:MzF(实际应为 f ~ ∣ M z \tilde{f}|_{\mathcal{M}_z} f~Mz)的oracle。Verifier根据上面方程式计算 b α , z = g ~ α ( z ) b_{\alpha,z}=\tilde{g}_{\alpha}(z) bα,z=g~α(z)
  • 6) U ( x ) , Z ( x ) U(x),Z(x) U(x),Z(x) 对应上面5.2.1节 Q U O T I E N T ( f , a α , z ) QUOTIENT(f,a_{\alpha,z}) QUOTIENT(f,aα,z)中定义,并令:
    h 1 ( x ) = h α , z 1 ( x ) = Q U O T I E N T ( f , a α , z ) = f ( x ) − U ( x ) Z ( x ) h^1(x)=h^1_{\alpha,z}(x)=QUOTIENT(f,a_{\alpha,z})=\frac{f(x)-U(x)}{Z(x)} h1(x)=hα,z1(x)=QUOTIENT(f,aα,z)=Z(x)f(x)U(x)
    h 2 ( x ) = h α , z 2 ( x ) = Q U O T I E N T ( g α , { z ↦ b α , z ) = g α ( x ) − b α , z x − z h^2(x)=h^2_{\alpha,z}(x)=QUOTIENT(g_{\alpha},\{z\mapsto b_{\alpha,z})=\frac{g_{\alpha}(x)-b_{\alpha,z}}{x-z} h2(x)=hα,z2(x)=QUOTIENT(gα,{zbα,z)=xzgα(x)bα,z
    • 注意,通过 f , g f,g f,g的oracle,Verifier也对 h 1 , h 2 h^1,h^2 h1,h2具有oracle access。
  • 7)Prover和Verifier使用 R P T D , R P T D ′ RPT_D,RPT_{D'} RPTD,RPTD来:
    • 7.1)证明 h 1 h^1 h1 R S [ F q , D , ( d − ∣ M ∣ ) / ∣ D ∣ ] RS[\mathbb{F}_q,D,(d-|\mathcal{M}|)/|D|] RS[Fq,D,(dM)/∣D]最多为 δ \delta δ-far。换句话说,即其接近于某degree < d − ∣ M ∣ <d-|\mathcal{M}| <dM的多项式。
    • 7.2)证明 h 2 h^2 h2 R S [ F q , D ′ , ( d ⋅ d C − ∣ M ∣ ) / ∣ D ′ ∣ ] RS[\mathbb{F}_q,D',(d\cdot d_{\mathcal{C}}-|\mathcal{M}|)/|D'|] RS[Fq,D,(ddCM)/∣D]最多为 δ \delta δ-far。

6.3 DEEP-ALI vs. ALI

DEEP-ALI协议 相比于 ALI协议的优势有:

  • 1)Soundness优势:
    • 即使 ρ \rho ρ接近于0值,ALI协议的lower bound为 1 / 8 1/8 1/8
    • DEEP-ALI协议的lower bound为 1 − ρ 1-\sqrt{\rho} 1ρ
  • 2)Query复杂度:
    • ALI中Verifier需query ∣ M ∣ ⋅ Q |\mathcal{M}|\cdot Q MQ个域元素,因需要 ∣ M ∣ |\mathcal{M}| M个元素来evaluate P i ( f ~ ( x ⋅ M 1 i ) , ⋯   , f ~ ( x ⋅ M ∣ M i ∣ i ) ) P^i(\tilde{f}(x\cdot M_1^i),\cdots,\tilde{f}(x\cdot M_{|M^i|}^i)) Pi(f~(xM1i),,f~(xMMii))
    • DEEP-ALI中Verifier需query O ( ∣ M ∣ + Q ) O(|\mathcal{M}|+Q) O(M+Q)个域元素,因为 P i P^i Pi的evaluation 之前已完成。
  • 3)Verifier复杂度:
    • ALI中Verifier复杂度为 Ω ( Q ⋅ T a r i t h ) \Omega(Q\cdot T_{arith}) Ω(QTarith),其中 T a r i t h T_{arith} Tarith为evaluate所有约束的运算复杂度。
    • DEEP-ALI中Verifier复杂度区间与 Q + T a r i t h Q+T_{arith} Q+Tarith,因仅需对约束evaluate一次。
  • 4)Prover复杂度:对于多个witness多项式 f 1 , ⋯   , f w f_1,\cdots,f_{\mathbf{w}} f1,,fw
    • ALI中 Prover复杂度为 ( w d C ρ − 1 + T a r i t h d C ) ⋅ d (\mathbf{w}d_{\mathcal{C}}\rho^{-1}+T_{arith}d_{\mathcal{C}})\cdot d (wdCρ1+TarithdC)d
    • DEEP-ALI中 Prover复杂度为 ( w ρ − 1 + d C ρ − 1 + T a r i t h d C ) ⋅ d (\mathbf{w}\rho^{-1}+d_{\mathcal{C}}\rho^{-1}+T_{arith}d_{\mathcal{C}})\cdot d (wρ1+dCρ1+TarithdC)d

附录B 代数哈希函数 H x H_x Hx

需固定特定subspaces来描述代数哈希函数 H x H_x Hx。对于每个 i ∈ [ 0 , r ] i\in [0,r] i[0,r],选择 F 2 \mathbb{F}_2 F2-subspaces L 0 ( i ) , L ( i ) L_0^{(i)},L^{(i)} L0(i),L(i)应满足如下属性:

  • 1) L 0 ( i ) ⊆ L ( i ) L_0^{(i)}\subseteq L^{(i)} L0(i)L(i),其中 dim ⁡ ( L 0 ( i ) ) = 1 \dim(L_0^{(i)})=1 dim(L0(i))=1
  • 2) L ( i + 1 ) = q ( i ) ( L ( i ) ) L^{(i+1)}=q^{(i)}(L^{(i)}) L(i+1)=q(i)(L(i)),其中 q ( i ) ( X ) q^{(i)}(X) q(i)(X) L 0 ( i ) L_0^{(i)} L0(i)的subspace多项式:
    q ( i ) ( X ) = ∏ α ∈ L 0 ( i ) ( X − α ) q^{(i)}(X)=\prod_{\alpha\in L_0^{(i)}}(X-\alpha) q(i)(X)=αL0(i)(Xα)
    • q ( i ) ( X ) q^{(i)}(X) q(i)(X)为对kernel L 0 ( i ) L_0^{(i)} L0(i) F 2 \mathbb{F}_2 F2-linear map
    • dim ⁡ ( L ( i + 1 ) ) = dim ⁡ ( L ( i ) ) − 1 \dim(L^{(i+1)})=\dim(L^{(i)})-1 dim(L(i+1))=dim(L(i))1

S i \mathcal{S}^i Si来表示包含在 L ( i ) L^{(i)} L(i)中的 L 0 ( i ) L_0^{(i)} L0(i)的cosets集合。

已知 x ∈ F x\in \mathbb{F} xF f : L ( i ) → F f:L^{(i)}\rightarrow \mathbb{F} f:L(i)F,以seed x x x f f f的哈希定义为函数 H x [ f ] : L ( i + 1 ) → F H_x[f]:L^{(i+1)}\rightarrow \mathbb{F} Hx[f]:L(i+1)F

对于 s ∈ L ( i + 1 ) s\in L^{(i+1)} sL(i+1),令 s 0 , s 1 ∈ L ( i + 1 ) s_0,s_1\in L^{(i+1)} s0,s1L(i+1) q ( i ) ( X ) − s q^{(i)}(X)-s q(i)(X)s的2个roots。
P f , s ( X ) ∈ F [ X ] P_{f,s}(X)\in\mathbb{F}[X] Pf,s(X)F[X]为唯一的degree ≤ 1 \leq 1 1多项式,其若满足:
P f , s ( s 0 ) = f ( s 0 ) P_{f,s}(s_0)=f(s_0) Pf,s(s0)=f(s0)
P f , s ( s 1 ) = f ( s 1 ) P_{f,s}(s_1)=f(s_1) Pf,s(s1)=f(s1)
则可定义:
H x [ f ] ( s ) = P f , s ( x ) \begin{equation} H_x[f](s)=P_{f,s}(x) \end{equation} Hx[f](s)=Pf,s(x)

由此可知, H x [ f ] ( s ) H_x[f](s) Hx[f](s)是对 f f f query集合 { s 0 , s 1 } \{s_0,s_1\} {s0,s1} 计算而来的。 { s 0 , s 1 } \{s_0,s_1\} {s0,s1} L 0 ( i ) L_0^{(i)} L0(i)的coset,并将其表示为 S s ( i ) \mathcal{S}_s^{(i)} Ss(i)

接下来,看 H x H_x Hx R S ( i ) RS^{(i)} RS(i)的用途。
f ∈ R S ( i ) f\in RS^{(i)} fRS(i),则底层的 f ( X ) f(X) f(X)的degree最多为 ρ ∣ L ( i ) ∣ \rho |L^{(i)}| ρL(i)。可将 f ( X ) f(X) f(X)基于base q ( i ) ( X ) q^{(i)}(X) q(i)(X)表示为:
f ( X ) = a 0 ( X ) + a 1 ( X ) ⋅ q ( i ) ( X ) + ⋯ + a t ( X ) ⋅ ( q ( i ) ( X ) ) t \begin{equation} f(X)=a_0(X)+a_1(X)\cdot q^{(i)}(X)+\cdots + a_t(X)\cdot (q^{(i)}(X))^t \end{equation} f(X)=a0(X)+a1(X)q(i)(X)++at(X)(q(i)(X))t

其中:

  • 每个 a i ( X ) a_i(X) ai(X)的degree最多为1。
  • t ≤ ρ ∣ L ( i ) ∣ / 2 t\leq \rho |L^{(i)}|/2 tρL(i)∣/2

由于多项式 f ( X ) f(X) f(X) P f , s ( X ) P_{f,s}(X) Pf,s(X) q ( X ) − s q(X)-s q(X)s的roots处相交,从而有 f ( X ) ≡ P f , s ( X ) m o d    ( q ( i ) ( X ) − s ) f(X)\equiv P_{f,s}(X)\mod (q^{(i)}(X)-s) f(X)Pf,s(X)mod(q(i)(X)s)。根据上面方程式有:
P f , s = a 0 ( x ) + a 1 ( X ) ⋅ s + ⋯ + a t ( X ) ⋅ s t P_{f,s}=a_0(x)+a_1(X)\cdot s+\cdots +a_t(X)\cdot s^t Pf,s=a0(x)+a1(X)s++at(X)st

对于所有的 x ∈ F x\in \mathbb{F} xF:【以 s s s为变量】
H x [ f ] ( s ) = P f , s ( x ) = a 0 ( x ) + a 1 ( x ) ⋅ s + ⋯ + a t ( x ) ⋅ s t H_x[f](s)=P_{f,s}(x)=a_0(x)+a_1(x)\cdot s+\cdots +a_t(x)\cdot s^t Hx[f](s)=Pf,s(x)=a0(x)+a1(x)s++at(x)st
从而有:
H x [ f ] ∈ R S ( i + 1 ) H_x[f]\in RS^{(i+1)} Hx[f]RS(i+1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/162428.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

解决:微软在登录时总是弹出需要家长或监护人同意才能使用该账户并且不断循环?

目录 问题来源&#xff1a; 解决办法&#xff1a; 问题来源&#xff1a; 我的edge浏览器账号登录&#xff0c;一直弹出来需要家长或监护人同意才能使用&#xff0c;然后按照提示操作&#xff0c;会一直循环&#xff0c;是个无穷循环。 解决办法&#xff1a; 参考&#xff1…

【Java 进阶篇】唤醒好运:JQuery 抽奖案例详解

在现代社交网络和电商平台中&#xff0c;抽奖活动成为吸引用户、提升用户参与度的一种常见手段。通过精心设计的抽奖页面&#xff0c;不仅可以增加用户的互动体验&#xff0c;还能在一定程度上提高品牌的知名度。本篇博客将通过详细解析 JQuery 抽奖案例&#xff0c;带领你走进…

Linux:firewalled服务常规操作汇总

一、firewalled防火墙工作原理 firewalled的内部结构&#xff0c;可以简单的看做下图&#xff0c;有两个集合&#xff0c;一个集合管理关闭的端口&#xff0c;另一个集合管理放开的端口。 二、常用操作 1、开启和关闭防火墙 临时性配置&#xff1a; systemctl [start | stop …

【Java 进阶篇】插上翅膀:JQuery 插件机制详解

在前端开发中&#xff0c;JQuery 作为一个广泛应用的 JavaScript 库&#xff0c;为开发者提供了丰富的工具和方法&#xff0c;简化了 DOM 操作、事件处理等繁琐的任务。而在这个庞大的生态系统中&#xff0c;插件机制是 JQuery 的一项重要特性&#xff0c;使得开发者能够轻松地…

电磁场与电磁波part4--时变电磁场

1、采用洛伦兹条件使得矢量位 与标量位 分离在两个独立的方程中&#xff0c;且矢量位 仅与电流密度 有关&#xff0c;而标量位 仅与电荷密度 有关。 2、电磁能量守恒定理&#xff08;坡印廷定理&#xff09; 即减少的电磁能量电磁场所做的功流出的电磁能量 3、设u(r,t)是…

【双指针】复写0

复写0 1089. 复写零 - 力扣&#xff08;LeetCode&#xff09; 给你一个长度固定的整数数组 arr &#xff0c;请你将该数组中出现的每个零都复写一遍&#xff0c;并将其余的元素向右平移。 注意&#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上…

Git命令总结-常用-后续使用频繁的再添加~

Git命令总结-常用 久了不用&#xff0c;有些时候老是会忘记一些命令&#xff0c;多的都记录一下&#xff0c;方便查找 git init 初始化一个Git仓库&#xff0c;执行完git init命令后&#xff0c;会生成一个**.git**目录&#xff0c;该目录包含了资源数据&#xff0c;且只会在…

新增文章分类

pojo.Category package com.lin.springboot01.pojo;import jakarta.validation.constraints.NotEmpty; import lombok.Data;import java.time.LocalDateTime;Data public class Category {private Integer id;//主键NotEmptyprivate String categoryName;//分类名称NotEmptypr…

redis cluster搭建

k8s部署 Redis Insight k8s部署redis集群_mob6454cc6c6291的技术博客_51CTO博客 占用的内存竟然这么小&#xff0c;才200M左右 随便选个节点进去&#xff0c;看能否连接上其他节点 redis-cli -h redis-cluster-v1-0.redis-cluster.project-gulimall.svc.cluster.local 再创建个…

【总结】I/O接口中的数据线,地址线,控制线,状态线传输什么信息?

数据线 方向&#xff1a;双向功能&#xff1a;在内存、寄存器和数据缓冲寄存器进行数据交换&#xff1b;接口和设备的状态信息也通过数据线传给CPU&#xff08;这里的状态指的是设备独有的&#xff0c;和状态线中的忙碌、空闲相区别&#xff09;&#xff1b;CPU对外设的控制命…

tomcat8.5处理get请求时,控制台输出中文乱码问题的解决

问题描述 控制台输出中文乱码 版本信息 我使用的是tomcat8.5 问题解决 配置web.xml 注&#xff1a;SpringMVC中处理编码的过滤器一定要配置到其他过滤器之前&#xff0c;否则无效 <!--配置springMVC的编码过滤器--> <filter><filter-name>CharacterEn…

Lstm+transformer的刀具磨损预测

视频讲解: 基于Lstm+transformer的刀具磨损预测实战_哔哩哔哩_bilibili 结果展示: 数据展示: 主要代码: # pip install openpyxl -i https://pypi.tuna.tsinghua.edu.cn/simple/ # pip install optuna -i https://pypi.tuna.tsinghua.edu.cn/simple/ import numpy as np…

Java之线程的概念及方法的学习

线程创建 方法一 直接使用Thread public class demo {public static void main(String[] args) {new Thread(){Overridepublic void run() {System.out.println(Thread.currentThread().getName());}}.start();System.out.println(Thread.currentThread().getName());} } main…

The ultimate UI kit and design system for Figma 组件库下载

Untitled UI 是世界上最大的 Figma UI 套件和设计系统。可以启动任何项目&#xff0c;为您节省数千小时&#xff0c;并祝您升级为专业设计师。 采用 100% 自动布局 5.0、变量、智能变体和 WCAG 可访问性精心制作。 900全局样式、变量&#xff1a;超级智能的全局颜色、排版和效…

JDBC,Java连接数据库

下载 JDBC https://mvnrepository.com/ 创建项目&#xff0c;然后创建一个目录并将下载好的 jar 包拷贝进去 选择 Add as Library&#xff0c;让这个目录能被项目识别 连接数据库服务器 在 JDBC 里面&#xff0c;使用 DataSource 类来描述数据库的位置 import com.mysql.cj.…

openGauss学习笔记-126 openGauss 数据库管理-设置账本数据库-归档账本数据库

文章目录 openGauss学习笔记-126 openGauss 数据库管理-设置账本数据库-归档账本数据库126.1 前提条件126.2 背景信息126.3 操作步骤 openGauss学习笔记-126 openGauss 数据库管理-设置账本数据库-归档账本数据库 126.1 前提条件 系统中需要有审计管理员或者具有审计管理员权…

CTF-虚拟机——【前置知识三】

文章目录 内存虚拟化常见缩写虚拟机内存访问原理影子页表扩展页表VPID&#xff08;Virtual Processor Identifier&#xff09;&#xff1a;TLB&#xff08;Translation Lookaside Buffer&#xff09;资源优化 内存虚拟化 能够提供在Guest机制中识别为从零开始的连续的物理地址…

C++之set/multise容器

C之set/multise容器 set基本概念 set构造和赋值 #include <iostream> #include<set> using namespace std;void PrintfSet(set<int>&s) {for(set<int>::iterator it s.begin();it ! s.end();it){cout<<*it<<" ";}cout&l…

链表题(4)

本章内容 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 今天继续给大家带来链表的相关练习题。 相交链表 这道题来自力扣网&#xff0c;链接…

央企太卷.....来自央企的7个面试题,一个一个生产难题

说在前面 在40岁老架构师尼恩的&#xff08;50&#xff09;读者社群中&#xff0c;最近小伙伴&#xff0c;面试央企、美团、京东、阿里、 百度、头条等大厂。 下面是一个小伙伴成功拿到通过了一个央企设计研究院一面面试&#xff0c;现在把面试真题和参考答案收入咱们的宝典。…