您当前的位置： 首页 >  ar

mutourend

暂无认证

  • 1浏览

    0关注

    661博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

Polygon zkEVM的pil-stark Fibonacci状态机代码解析

mutourend 发布时间：2022-08-23 17:21:09 ，浏览量：1

1. 引言

前序博客有：

  • Polygon zkEVM的pil-stark Fibonacci状态机初体验
  • STARKs and STARK VM: Proofs of Computational Integrity

开源代码见：

  • https://github.com/0xPolygonHermez/pil-stark（Javascript）

中的test/sm_fibonacci/Fibonacci状态机，对应的序列为： 1 , 2 , 5 , 29 , ⋯ 1,2,5,29,\cdots 1,2,5,29,⋯ 对应的逻辑为： a i + 2 = a i 2 + a i + 1 2 a_{i+2}=a_{i}^2+a_{i+1}^2 ai+2​=ai2​+ai+12​。需要判定第 2 10 = 1024 2^{10}=1024 210=1024个元素是否为 74469561660084004 74469561660084004 74469561660084004。 将其execution trace表示为：具有寄存器 A = ( A 0 , A 1 , A 2 , … , A 1023 ) \mathbf{A} = ( A_0, A_1, A_2, \dots , A_{1023} ) A=(A0​,A1​,A2​,…,A1023​)和 B = ( B 0 , B 1 , B 2 , … , B 1023 ) \mathbf{B} = ( B_0, B_1, B_ 2, \dots , B_{1023} ) B=(B0​,B1​,B2​,…,B1023​)的状态机，第 i i i个状态为 ( A i , B i ) (A_i,B_i) (Ai​,Bi​)，初始状态为 A 0 = i n 1 = 1 , B 0 = i n 2 = 2 A_0=in_1=1,B_0=in_2=2 A0​=in1​=1,B0​=in2​=2。相应的约束为：

  • 1）Transition constraints： A i + 1 = B i , B i + 1 = A i 2 + B i 2 A_{i+1}=B_i,B_{i+1}=A_{i}^2+B_{i}^2 Ai+1​=Bi​,Bi+1​=Ai2​+Bi2​（ i = { 0 , ⋯   , 1022 } i=\{0,\cdots,1022\} i={0,⋯,1022}）
  • 2）Boundary constraints： A 0 = 1 , B 0 = 2 , B 1023 = o u t = 74469561660084004 A_0=1,B_0=2,B_{1023}=out=74469561660084004 A0​=1,B0​=2,B1023​=out=74469561660084004

为了便于设置STARK的polynomial identities，需额外再引入2个常量寄存器 i s I n i t i a l = ( 1 , 0 , 0 , ⋯   , 0 ) , i s L a s t = ( 0 , 0 , 0 , ⋯   , 1 ) \mathbf{isInitial}=(1,0,0,\cdots,0), \mathbf{isLast}=(0,0,0,\cdots,1) isInitial=(1,0,0,⋯,0),isLast=(0,0,0,⋯,1)，将以上transition和boundary约束表示为：（ i = { 0 , ⋯   , 1023 } i=\{0,\cdots,1023\} i={0,⋯,1023}） ( A i + 1 − B i ) ∗ ( 1 − isLast i ) = 0 (A_{i+1}-B_i)*(1-\text{isLast}_i)=0 (Ai+1​−Bi​)∗(1−isLasti​)=0 ( B i + 1 − ( A i 2 + B i 2 ) ) ∗ ( 1 − isLast i ) = 0 (B_{i+1}-(A_i^2+B_i^2))*(1-\text{isLast}_i)=0 (Bi+1​−(Ai2​+Bi2​))∗(1−isLasti​)=0 isInitial i ∗ ( A i − i n 1 ) = 0 \text{isInitial}_i*(A_i-in_1)=0 isInitiali​∗(Ai​−in1​)=0 isInitial i ∗ ( B i − i n 2 ) = 0 \text{isInitial}_i*(B_i-in_2)=0 isInitiali​∗(Bi​−in2​)=0 isLast i ∗ ( B i − o u t ) = 0 \text{isLast}_i*(B_i-out)=0 isLasti​∗(Bi​−out)=0

将寄存器 A , B , i s I n i t i a l , i s L a s t \mathbf{A}, \mathbf{B}, \mathbf{isInitial}, \mathbf{isLast} A,B,isInitial,isLast 分别插值为多项式 l 2 ( x ) , l 1 ( x ) , L 1 ( x ) , L L A S T l_2(x),l_1(x),L_1(x),LLAST l2​(x),l1​(x),L1​(x),LLAST表示。【其中 ω \omega ω为 1024 1024 1024-th root of unity。】

序号 x x x A \mathbf{A} A（ l 2 ( x ) l_2(x) l2​(x)多项式） B \mathbf{B} B（ l 1 ( x ) l_1(x) l1​(x)多项式） i s I n i t i a l \mathbf{isInitial} isInitial（ L 1 ( x ) L_1(x) L1​(x)多项式） i s L a s t \mathbf{isLast} isLast（ L L A S T ( x ) LLAST(x) LLAST(x)多项式）0 ω 0 \omega^0 ω012101 ω 1 \omega^1 ω125002 ω 2 \omega^2 ω252900 ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮1023 ω 1023 \omega^{1023} ω1023…7446956166008400401

该状态机核心代码见fibonacci.pil文件：

	constant %N = 2**10;
	
	namespace Fibonacci(%N);

    pol constant L1, LLAST;
    pol commit l1,l2;
    
    pol l2c = l2;

    public in1 = l2c(0);
    public in2 = l1(0);
    public out = l1(%N-1);

    (l2' - l1)*(1-LLAST) = 0;

    pol next = l1*l1 + l2*l2;

    (l1' - next)*(1-LLAST) = 0;

    L1 * (l2 - :in1) = 0;
    L1 * (l1 - :in2) = 0;
    LLAST * (l1 - :out) = 0;

初始状态见fibonacci.input.json文件：

[1, 2]

STARK待证明的场景为：

  • 公开信息：常量多项式 L 1 ( x ) L_1(x) L1​(x)和 L L A S T ( x ) LLAST(x) LLAST(x)，commitment值 c o m ( l 1 ( x ) ) com(l_1(x)) com(l1​(x))和 c o m ( l 2 ( x ) ) com(l_2(x)) com(l2​(x))，Fibonacci数列第一二项为 i n 1 = 1 , i n 2 = 2 in_1=1,in_2=2 in1​=1,in2​=2，第1024项输出为 o u t = 74469561660084004 out=74469561660084004 out=74469561660084004
  • witness：多项式 l 1 ( x ) , l 2 ( x ) l_1(x),l_2(x) l1​(x),l2​(x)
  • 待证明relation：对于 x = { ω 0 , ω 1 , ⋯   , ω 1023 } x=\{\omega^0,\omega^1,\cdots, \omega^{1023}\} x={ω0,ω1,⋯,ω1023}，有：
    • ( l 2 ( ω ⋅ x ) − l 1 ( x ) ) ⋅ ( 1 − L L A S T ( x ) ) = 0 (l_2(\omega\cdot x)-l_1(x))\cdot (1-LLAST(x))=0 (l2​(ω⋅x)−l1​(x))⋅(1−LLAST(x))=0
    • ( l 1 ( ω ⋅ x ) − ( ( l 2 ( x ) ) 2 + ( l 1 ( x ) ) 2 ) ) ⋅ ( 1 − L L A S T ( x ) ) = 0 (l_1(\omega\cdot x)-((l_2(x))^2+(l_1(x))^2))\cdot (1-LLAST(x))=0 (l1​(ω⋅x)−((l2​(x))2+(l1​(x))2))⋅(1−LLAST(x))=0
    • L 1 ( x ) ⋅ ( l 2 ( x ) − i n 1 ) = 0 L_1(x)\cdot (l_2(x)-in_1)=0 L1​(x)⋅(l2​(x)−in1​)=0
    • L 1 ( x ) ⋅ ( l 1 ( x ) − i n 2 ) L_1(x)\cdot (l_1(x)-in_2) L1​(x)⋅(l1​(x)−in2​)
    • L L A S T ( x ) ⋅ ( l 1 ( x ) − o u t ) = 0 LLAST(x)\cdot (l_1(x)-out)=0 LLAST(x)⋅(l1​(x)−out)=0

基于的域const F = new F1Field();即为Goldilocks域 p = 2 64 − 2 32 + 1 p=2^{64}-2^{32}+1 p=264−232+1，详细参见：

  • Goldilocks域

代码中根据 f ( x ) f(x) f(x)表达 f ( ω ⋅ x ) f(\omega \cdot x) f(ω⋅x)多项式为：

r = pols.cm[exp.id].v_n;
if (exp.next) r = getPrime(r);

function getPrime(p) {
	const r = p.slice(1);
	r[p.length-1] = p[0];
	return r;
}
2. 编译pil生成constant多项式

debug运行fibonacci buildconst：运行状态机中main_buildconst_fibonacci.js，输出为fibonacci.const：

/usr/local/bin/node --max-old-space-size=32000 test/sm_fibonacci/main_buildconst_fibonacci.js -o tmp/fibonacci.const
file Generated Correctly

main_buildconst_fibonacci.js核心代码为：

async function run() {

    const outputFile = typeof(argv.output) === "string" ?  argv.output.trim() : "fibonacci.const";

    const F = new F1Field();
    const pil = await compile(F, path.join(__dirname, "fibonacci_main.pil"));

    const constPols = newConstantPolsArray(pil);

    await smFibonacci.buildConstants(constPols.Fibonacci);

    await constPols.saveToFile(outputFile);

    console.log("file Generated Correctly");
}
2.1 编译pil文件 
const pil = await compile(F, path.join(__dirname, "fibonacci_main.pil"));

compile是对.pil文件进行编译：

# $ cd pilcom
pilcom lanyu$ node src/pil.js ../pil-stark/test/sm_fibonacci/fibonacci_main.pil -o fibonacci.compile.json
Input Pol Commitmets: 2
Q Pol Commitmets: 1
Constant Pols: 2
Im Pols: 2
plookupIdentities: 0
permutationIdentities: 0
connectionIdentities: 0
polIdentities: 5

编译后的结果为：

{
 "nCommitments": 2, # 即pil中，以`poly commit`标记的多项式数量。
 "nQ": 1, # 即pil中以多项式为粒度，degree为2的多项式总数。如`pol next = l1*l1 + l2*l2;`，会 nQ++。
 "nIm": 2, # 非`poly constant`或`poly commit`标记的多项式数量。即pil中，仅以`poly`标记的中间多项式总数。
 "nConstants": 2, # 即pil中，以`poly constant`标记的多项式数量。
 "publics": [ # 对应pil中的`public`关键字
  { # 对应`public in1 = l2c(0);`
   "polType": "imP",
   "polId": 0,
   "idx": 0,
   "id": 0,
   "name": "in1"
  },
  { # 对应`public in2 = l1(0);`
   "polType": "cmP",
   "polId": 0,
   "idx": 0,
   "id": 1,
   "name": "in2"
  },
  { # 对应`public out = l1(%N-1);`
   "polType": "cmP",
   "polId": 0,
   "idx": 1023,
   "id": 2,
   "name": "out"
  }
 ],
 "references": {
  "Fibonacci.L1": {
   "type": "constP",
   "id": 0,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.LLAST": {
   "type": "constP",
   "id": 1,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.l1": {
   "type": "cmP",
   "id": 0,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.l2": {
   "type": "cmP",
   "id": 1,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.l2c": {
   "type": "imP",
   "id": 0,
   "polDeg": 1024,
   "isArray": false
  },
  "Fibonacci.next": {
   "type": "imP",
   "id": 2,
   "polDeg": 1024,
   "isArray": false
  }
 },
 "expressions": [
  { # 0. l2，对应中间赋值 `pol l2c = l2;`？？？
   "op": "cm",
   "deg": 1,
   "id": 1,
   "next": false
  },
  { # 1. 对应约束 `(l2' - l1)*(1-LLAST) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    {
     "op": "mul",
     "deg": 2,
     "values": [
      { # l2'-l1
       "op": "sub",
       "deg": 1,
       "values": [
        { # l2'
         "op": "cm",
         "deg": 1,
         "id": 1,
         "next": true
        },
        { # l1
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": false
        }
       ]
      },
      {
       "op": "sub",
       "deg": 1,
       "values": [
        { # 1-LLAST
         "op": "number",
         "deg": 0,
         "value": "1"
        },
        { # LLAST
         "op": "const",
         "deg": 1,
         "id": 1,
         "next": false
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  },
  { # 2. 对应中间赋值 `pol next = l1*l1 + l2*l2;`
   "op": "add",
   "deg": 1,
   "idQ": 0,
   "values": [
    { # l1*l1
     "op": "mul",
     "deg": 2,
     "values": [
      { # l1
       "op": "cm",
       "deg": 1,
       "id": 0,
       "next": false
      },
      { # l1
       "op": "cm",
       "deg": 1,
       "id": 0,
       "next": false
      }
     ]
    },
    { # l2*l2
     "op": "mul",
     "deg": 2,
     "values": [
      { # l2
       "op": "cm",
       "deg": 1,
       "id": 1,
       "next": false
      },
      { # l2
       "op": "cm",
       "deg": 1,
       "id": 1,
       "next": false
      }
     ]
    }
   ]
  },
  { # 3. 对应约束`(l1' - next)*(1-LLAST) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    { # 对应 `(l1' - next)*(1-LLAST)`
     "op": "mul",
     "deg": 2,
     "values": [
      { # l1'-next
       "op": "sub",
       "deg": 1,
       "values": [
        { # l1'
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": true
        },
        { # next
         "op": "exp", 
         "deg": 1,
         "id": 2,
         "next": false
        }
       ]
      },
      {
       "op": "sub",
       "deg": 1,
       "values": [
        { # 1
         "op": "number",
         "deg": 0,
         "value": "1"
        },
        { # LLAST
         "op": "const",
         "deg": 1,
         "id": 1,
         "next": false
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ],
   "deps": [ # 表示依赖的中间多项式id，此处对应为next。
    2
   ]
  },
  { # 4. 对应约束为`L1 * (l2 - :in1) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    { # 对应 `L1*(l2-in1)`
     "op": "mul",
     "deg": 2,
     "values": [
      { # L1
       "op": "const",
       "deg": 1,
       "id": 0,
       "next": false
      },
      { # 对应`l2-in1`
       "op": "sub",
       "deg": 1,
       "values": [
        { # l2
         "op": "cm",
         "deg": 1,
         "id": 1,
         "next": false
        },
        { # in1
         "op": "public",
         "deg": 0,
         "id": 0
        }
       ]
      }
     ]
    },
    { # 0
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  },
  { # 5. 对应约束`L1 * (l1 - :in2) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    { # L1*(l1-in2)
     "op": "mul",
     "deg": 2,
     "values": [
      { # L1
       "op": "const",
       "deg": 1,
       "id": 0,
       "next": false
      },
      { # l1-in2
       "op": "sub",
       "deg": 1,
       "values": [
        { # l1
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": false
        },
        { # in2
         "op": "public",
         "deg": 0,
         "id": 1
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  },
  { # 6. 对应约束`LLAST * (l1 - :out) - 0 = 0`
   "op": "sub",
   "deg": 2,
   "values": [
    { # LLAST*(l2-out)
     "op": "mul",
     "deg": 2,
     "values": [
      { # LLAST
       "op": "const",
       "deg": 1,
       "id": 1,
       "next": false
      },
      { # l2-out
       "op": "sub",
       "deg": 1,
       "values": [
        { # l2
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": false
        },
        { # out
         "op": "public",
         "deg": 0,
         "id": 2
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  }
 ],
 "polIdentities": [
  {
   "e": 1, # 对应”expressions“中的序号。即`(l2' - l1)*(1-LLAST) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 13 # 代码所在行号。即`(l2' - l1)*(1-LLAST) = 0;`
  },
  {
   "e": 3, # 对应”expressions“中的序号。即` (l1' - next)*(1-LLAST) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 17 # 代码所在行号。即` (l1' - next)*(1-LLAST) = 0;`
  },
  {
   "e": 4, # 对应”expressions“中的序号。即`L1 * (l2 - :in1) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 19 # 代码所在行号。即`L1 * (l2 - :in1) = 0;`
  },
  {
   "e": 5, # 对应”expressions“中的序号。即`L1 * (l1 - :in2) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 20 # 代码所在行号。即`L1 * (l1 - :in2) = 0;`
  },
  {
   "e": 6, # 对应”expressions“中的序号。即`LLAST * (l1 - :out) - 0 = 0;`
   "fileName": "fibonacci.pil",
   "line": 21 # 代码所在行号。即`LLAST * (l1 - :out) = 0;`
  }
 ],
 "plookupIdentities": [],
 "permutationIdentities": [],
 "connectionIdentities": []
}
2.2 从编译结果中获取常量多项式 
const constPols = newConstantPolsArray(pil);

本质为从编译的json文件中，取“references”中标记为“constP”的多项式。

2.3 对常量多项式赋值 
await smFibonacci.buildConstants(constPols.Fibonacci);

对各常量多项式赋值：

module.exports.buildConstants = async function (pols) {

    const N = pols.L1.length;


    for ( let i=0; i
关注
打赏
1664532908
查看更多评论

最近更新

热门博客

[ 申请 ]友情链接：

ClashX教程 绘画宝宝 配音宝宝
0.0794s