Skip to content

Latest commit

 

History

History
2174 lines (1355 loc) · 62.1 KB

Huowuge.md

File metadata and controls

2174 lines (1355 loc) · 62.1 KB
Raw
timezone
Asia/Shanghai
  1. 我是Zemmer，后端转合约，专注defi和nft。
  2. 能完成本次残酷学习。
  3. 目前阶段对ZK了解了一些，没有系统学习，正好遇到，拿下。

Notes

2024.07.29

zk的概念

1、允许作为证明者的一方在不透露其他信息的情况下让作为验证者的另一方相信某个事实或声明。

2、ZKP的目的是：证明我有这个事实。

3、ZKP并不是“零”知识，而是不透露除了这个事实之外的其他任何信息。

关于Knowledge和information的区别举例

我觉得在合约的角度，知识聚焦于交易相关概念的判断，而信息不仅包含知识，而且聚焦于单个变量的数值。

知识 信息
1、某个地址拥有大于100的ETH 1、地址0x99拥有121.3ETH
2、某个交易的交易方属于某个DAO 2、区块的生成时间是12828382938
3、某个mint后但未reveal的NFT属于某个地址
4、交易0x88的交易双方都是EOA

NP问题

P和NP的概念

1、P问题：可以在多项式时间（而不是指数时间）内求解的问题

2、NP问题：可以在多项式时间内验证解的正确性的问题。

NP问题特点

1、难以求解，但易于验证。

2、P问题是NP问题的子集：即P问题易于求解，也易于验证。

NP完全问题NP Complete

1、如果能在多项式时间内解决任何一个NP完全问题,就能解决所有NP问题

2、所有NP问题都可以归约到某个NP完全问题

常见NP问题

1、图着色问题Graph Coloring：给定一个图和k种颜色，是否可以用这k种颜色给图的顶点着色，使得相邻顶点颜色不同？

2、汉密尔顿回路问题Hamiltonian Cycle：在给定的图中，是否存在一条经过每个顶点恰好一次的回路

3、子集和问题Subset Sum：给定一组数字和一个目标值，这组数字是否存在一个子集，其和等于目标值？

4、布尔可满足性问题Boolean Satisfiability Problem, SAT：给定一个布尔表达式，是否存在一组变量赋值使表达式为真？

5、整数分解问题Integer Factorization：给定一个大整数，找出它的质因数。

关于三色图

1、三色图的游戏规则

1、需要地图上n块地图，一共三种颜色国家，相邻的两块颜色都不同。

2、地图遮住颜色。

3、验证者每次只能要求揭露相邻的两块地图颜色。

4、如果验证的结果是颜色不同，则验证通过，说明证明者正确。

5、验证者可以多次验证。

2、三色图的刷新机制

三色图规则有一个非常巧妙的地方，就是每次验证者验证之后，整体的答案进行了刷新，证明者仍保证当前答案符合游戏规则。

3、分析

1、刷新规则代表了证明者可以证明给验证者一个事实：我这次是对的，也就是这个局部是对的。

2、但不能证明一个事实：我这次的其他地方也是对的，也就是整体是对的。

3、对于验证者来说，他清楚每次有1/2的概率证明者可能出错。

4、然而，如果证明者确实有三色图的答案，那么就不可能出现验证错误的情况。

5、这就像抛硬币，虽然每次有1/2的可能性抛出头像那一面，但是如果你每次都抛出头像面，那么我可以认为你这个硬币只有一面。

6、感觉这是一种无限逼近的证明，不是完备的证明。

2024.07.30

ZK的两种技术：ZK-snarks和ZK-starks的区别

特性 zk-SNARKs zk-STARKs
扩展性 需要可信设置，扩展性较差 不需要可信设置，扩展性更强
安全性 依赖复杂数学假设（如椭圆曲线和Pairing-based加密） 基于哈希函数，依赖较少的假设，更加简单和可靠
证明尺寸 证明尺寸较小，验证时间较短，适合在区块链上使用 证明尺寸较大，生成和验证的资源消耗较大
应用率 已有较成熟的开发生态，应用较广泛 技术更先进，但应用较少，开发生态还不够成熟
可信验证 需要可信设置来生成公共参数 不需要可信设置，证明是完全透明的，任何人都可以验证

layer2的zk技术

optimistic：假设所有交易都有效，如果出问题再检测。

zk-rollup：需要每个交易都附带证明

数据存储方式三种

rollup：

validadium：数据存在链下，有点像预制菜，菜单是有效性证明！预制菜本身代表线下储存。

volition：数据存储方式：结合了zk-rollup和validadium结合。

rollup的项目

lookpring

zksync

starknet

今天学习结果很差，非常松散，需要系统的针对某一些基础进行深挖。

2024.07.31

今天只学了一个zk游戏，和三色图的有点类似，具体如下

抛硬币猜测色彩游戏

要求

verifier在不看页面的前提下，通过交互式来判断页面只有一个颜色还是两个颜色。

前提条件

1、页面上有一个矩形图形，矩形对称轴将其分成两部分。

2、每个部分可能有两个颜色，分别是绿色和紫色。也有可能都是一个颜色，比如全绿色或全紫色。

3、硬币有两面head和tail。

4、verifier是色盲，无法分辨页面颜色，但可以分辨硬币是哪一面。

5、prover不是色盲，可以分辨页面颜色。

6、prover知道verifier会投掷硬币，且会根据投掷硬币结果去决定是否翻转页面。

7、prover和verifier都诚实。

交互验证流程

1、prover将页面给verifier。

2、verifier抛硬币，并自己设定规则来根据硬币是哪一面来决定是否给页面翻面。假设当前游戏规则是抛出heads，则翻转页面。

3、verifier将操作完的页面给prover，prover收到该页面。

当前交互总结

掌握的知识 prover verifier
页面是一个颜色还是两个 是 否
verifier投掷硬币的是head还是tail 否 是
verifier是否翻转了页面 如果页面两色则是，单色则否 是

1、截止当前步骤，verifier掌握的信息只有他投掷的硬币是哪一面。

2、prover知道verifier抛了硬币，但不确定verifier是哪一面，因为prover和verifier并没有在游戏之前商量好是抛哪一面才翻转。

3、prover掌握的信息是页面的初始原色，以及页面是否被翻转这两个信息。而如果页面初始是两个颜色，他是可以100%掌握页面是否被翻转这个信息的。但如果页面初始是一个颜色，他无法掌握页面是否被翻转这个信息。

继续交互流程

4、prover需要猜测verifier设定的翻转规则，有两种：第一种是抛head翻转，而tail不翻转。第二种是抛tail翻转而head不翻转。

5、prover根据猜测的结果和页面的情况来回复verifier说：“你的coin抛了head”或“你的coin抛了tail"

6、verifier得到这个消息，和自己实际抛售的结果进行比较。

当前交互总结

掌握的知识 prover verifier
页面是一个颜色还是两个 是 否
verifier投掷硬币的是head还是tail 否 是
verifier是否翻转了页面 如果页面两色则是，单色则否 是
prover猜测的硬币面是否和verifier实际抛的硬币面一样 否 是

此轮验证结束，循环开始下一轮验证。

举例

前提1：

页面颜色 verifier的规则 prover的规则
2 head -> 翻 翻 -> head
次数 verifier 抛出真实 prover看到结果 Prove的回答 Prover回答和verifier的是否一致
1 head 翻了 head 是
2 tail 没翻 tail 是

所以结果：这种情况下，永远一致。因此：正确率100%，页面颜色是2。

前提2：

页面颜色 verifier的规则 prover的规则
2 head -> 翻 不翻 -> head
次数 verifier 抛出真实 prover看到结果 Prove的回答 Prover回答和verifier的是否一致
1 head 翻了 tail 否
2 tail 没翻 head 否

所以结果：这种情况下，永远不一致。因此：正确率0%，页面颜色是2。

前提3：

页面颜色 verifier的规则 prover的规则
2 head -> 不翻 翻 -> head
次数 verifier 抛出真实 prover看到结果 Prove的回答 Prover回答和verifier的是否一致
1 head 没翻 tail 否
2 tail 翻了 head 否

所以结果：这种情况下，永远不一致。因此：正确率0%，页面颜色是2。

前提4：

页面颜色 verifier的规则 prover的规则
2 head -> 不翻 不翻 -> head
次数 verifier 抛出真实 prover看到结果 Prove的回答 Prover回答和verifier的是否一致
1 head 没翻 head 是
2 tail 翻了 tail 是

所以结果：这种情况下，永远一致。因此：正确率100%，页面颜色是2。

前提5678：

在这种情况下，由于prover看到的结果是没变化的，因此prover不能确定是否verifier是否进行了翻转，进而prover自己设置什么规则，都不可能无因有果，最后prover的回复是随机回复，无法确定的。

页面颜色 verifier的规则 prover的规则
1 head -> 翻 翻 -> head
1 head -> 翻 不翻 -> head
1 head -> 不翻 翻 -> head
1 head -> 不翻 不翻 -> head
次数 verifier 抛出真实 prover看到结果 Prove的回答 Prover回答和verifier的是否一致
1 head 没变化 随机回答 不确定
2 tail 没变化 随机回答 不确定

所以结果：这种情况下，回答有时候正确有时候错误。因此：正确率可能会在50%附近浮动（未必，要根据prover的性格来确定），页面颜色是1。

结论

1、如果prover的回答100%正确或者100%错误，则verifier判断此页面为2色。

2、如果prover的回答不是100%正确或者100%错误，则verifier判断此页面为1色。

游戏结论

1、zk需要将一个复杂问题从数学上转化为概率问题。 2、而且这个概率问题需要通过多轮独立的挑战验证来实现统计。

2024.08.01

学不动了，直接先磕circom，从后往前捯饬吧。

Circom

相关定义

signals：

1、信号，感觉就是参数

2、每个参数是一个多项式的未知数（元）

3、不仅仅是输入的参数，包括整个电路过程中所有的变量在不同时候值都算是signal。

R1CS

1、Rank-1 constraint system，称之为：秩 1 约束系统。

2、一个电路代码的限制系统

3、要求所有的参数都符合二次、线性等式。而且可以通过公式消元。

4、所有多项式的计算都是在有限域上的运算，也就是模运算。

witness

1、一组可以满足电路的信号

2、也就是R1CS的解决方案之一

3、简单的说就是一组有效的输入参数args。

输入input和输出out put

1、都属于signals

2、输入分为私有输入private和公开输入public input

3、私有输入就是不能透露的信息，也就是零知识的那部分。比如私钥。

可信设置trusted setup

1、

安装步骤

安装rust

cd ~
curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh

安装circom

git clone https://github.com/iden3/circom.git

cd circom
cargo build --release
cargo install --path circom

circus binary将安装在$HOME/.cargo/bin下。

测试

circom --help

安装snark.js

npm install -g snarkjs

使用circom的整体步骤

1、撰写circom

得到一个.circom文件，该文件内部建立了template的实例。

2、编译circom

编译命令：circom 文件名

circom multiplier2.circom --r1cs --wasm --sym --c

参数解释

--r1cs

1、生成 fileName.r1cs文件

2、该文件是电路中R1CS的二进制

--wasm

1、生成了fileName_js文件夹

2、该文件夹内包含fileName.wasm文件，以及其它文件

3、这些文件的内容是在JavaScript环境下生成见证人witness

--sym

1、生成了fileName.sym文件

2、用于调试和以注释模式打印约束系统。

--c

1、生成了fileName_cpp文件夹

2、该文件夹包含了fileName.cpp和fileName.dat等文件

3、这些文件也是用来在C++环境下生成见证人witness的。性能更好（但每个证明的生成时间里见证人只是其中一部分）

-o

1、用于指定输出文件的目录。

2、默认是当前目录

-l

添加库搜索路径，即指定额外的目录，circom会在这些目录中查找include指令引用的电路文件。

3、计算见证人witness

1、设计一组和wasm文件对应的实参，并将参数放入自定义的json文件中，比如命名为input.json。

{"a": "3", "b": "11"}

2、将这个文件放入fileName_js文件夹中，即和fileName.wasm同一目录下。

3、在该文件目录下，运行以下文件生成证明文件.wtns。此命令使用 Node.js 运行 generate_witness.js，参数依次是输入的fileName.wasm文件、电路输入的 JSON 文件input.json，和生成的自定义的witness文件witness.wtns。

node generate_witness.js multiplier2.wasm input.json witness.wtns

4、证明电路

生成电路所需的文件

1、wtns文件：见证人文件，包含所有的信号。

2、r1cs文件：约束文件，包含电路约束

3、未完待续

2024.08.02

Circom语法

结束语法

和js一样，每一行代码结束后使用分号;

数据类型

普通数据：x

列表数据：x[N]

信号signal

信号类型

1、输入信号，类型是input

2、输出信号，类型是output

3、中间信号，没有指明类型的全部是中间信号。

信号声明

格式：signal 变量类型 变量名，如果没有变量类型则为中间变量。

signal input in;
signal output out[N];
signal inter;

公开信号和私有信号

性质

1、私有信号只有自己（证明人）可知，也就是只有电路内访问，外部不可访问。

2、公开信号证明人和验证人都可见，也就是电路外可访问。

3、所有的信号默认都是私有信号。

4、主组件中所有的输出信号都是公开信号.

标识公开信号的方式

1、只有在主组件中可以定义公开信号。

2、定义的语法是使用public语法如下。

3、注意如果不定义公开信号的话仍为私有信号。

component main {public [in1,in2]} = Multiplier2();

信号的不可更改型immutable

所有的信号都不能二次赋值，即只能赋值一次。

2024.08.03

信号的值

1、信号的值只能是数字、布尔值或者数字列表

2、circom没有字符串这个概念。

约束constrain

1、定义信号signal之间的关系。

2、这些关系在电路执行时候（以及证明过程中）必须满足。

3、一个模板之中通常有多个约束。

信号约束相关符号
符号 解释 常用度
<== 约束+赋值，常用语信号signal中，用于约束 常用
==> 和<==一样，就是方向不同 很少
=== 仅仅约束，不赋值 常用
<-- 仅赋值，不约束 很少
--> 和<--一样，就是方向不同 很少
= 变量赋值var、component等。 不用于信号
约束示例

1、有两个约束，第一个是out <== -in * inv + 1;，第二个是in * out === 0;

2、虽然第二个约束看起来没用，但还是能增加系统鲁棒性。

/* 判断数字是否是0：输入一个数，当这个数字为0时候输出1，当这个数字不0时候输出0.*/
pragma circom 2.0.0;

template IsZero() {
    signal input in;
    signal output out;
    signal inv;
    inv <-- in != 0 ? 1/in : 0;
    out <== -in * inv + 1;
    in * out === 0;
}

component main {public [in]} = IsZero();

变量var

和信号的不同，尤其是中间信号

异同点 var signal
赋值号 = <==
使用场景 临时变量赋值，循环变量，不能做约束 约束
赋值次数 多次 1次

模版template和组件component

1、template定义了电路逻辑

template的参数

1、template可以有参数。

2、template的参数在component中赋值实参，因为component是实例化的意思。

3、不能把template的参数赋值给信号。因为信号是生成见证人阶段从外部输入的。

4、也不能把信号赋值给template参数，因为template实参是以常量形式在代码中输入的，而且是在编译阶段执行实例化的。

template tempid ( param_1, ... , param_n ) {
 signal input a;
 signal output b;

 .....

}

component c = tempid(v1,...,vn);

component

1、是实例化的模版

2、模版如果有参数，必须在这个阶段输入参数

3、可以通过.来获取实例中的信号。

主组件main component

有限域

circom的有限域的模p值为：

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617.

判断

if else判断

  if(N > 0){
     a = A(N);
  }
  else{
     a = A(0);
  }

三元表达式

布尔条件? true值: false值;

var z = x>y? x : y;

2024.08.04

函数

1、函数内无法声明信号，或者创建约束，这只能是模版template的功能。

function funid ( param1, ... , paramn ) {

 .....

 return x;
}

2、如果函数有返回值，且返回值是根据判断条件来决定的，那么需要做到每个判断条件都定义返回值，不能存在开放的条件没有返回值的情况。（即有if必须有else或者包含else的其他情况）。

// 错误，当 N < 0 时，没有返回值
function example(N){
    if (N >= 0) {
        return 1;
    } 
}


// 正确
function example(N){
    if (N >= 0) {
        return 1;
    }
    else{
        return 0;
    }
}

// 正确
function example(N){
    if (N >= 0) {
        return 1;
    }
    return 0;
}

导入电路

1、不同于import，circom用语法include来导入其它电路文件

2、文件名必须加后缀.circom

3、可以使用-l参数，具体什么意思不知道。

include "montgomery.circom";
include "mux3.circom";
include "babyjub.circom";

运算符

布尔运算符

和：&&

或：||

非：!

算数运算符

1、所有的算数运算符都是模运算，包含加减乘除幂。

2、/是乘以逆元，例如10/3 mod11的意思是10 * 8 mod 11 也就是3 mod 11。

3、\是整除，且不进行模运算，返回a/b的整数部分。

4、%取余，切不进行模运算，返回a/b的余数。

2024.08.05

断言assertion

1、语法：assert(布尔表达式);

2、注意不仅在编译阶段进行检查，而且会在运行阶段进行检查。比如编译可能正确，但是运行可能错误。这是因为断言的条件可能包含了输入信号：

// 这个电路可以编译成功，但如果在运行阶段（生成见证阶段）输入信号in > 254，则会报错
template Translate(n) {
  signal input in;  
  assert(in <= 254);
  . . .
}

调试打印log

语法：log(变量/常量/表达式/字符串)，可以用,连接

编译阶段调试命令

--sym详解

1、该命令生成了fileName.sym文件

2、该命令后面可以跟一个参数，该参数表示信号简化的程度，该参数值为默认没有， -O0 或 --O1

3、该文件表示了该电路内每个信号的详细信息，虽然不是实际传输的见证。（这里电路类似于形参，而见证类似于实参）

4、内有四个字段，分别为#s, #w, #c, name

内容 定义 解释 示例
#s 信号编号 每个信号都有一个整数编号，从1开始，顺序排列 1
#w 见证位置 信号在见证中的位置。
如果不是public signal且不出现在最终的R1CS约束中，则值为-1		 2
#c 组件编号 标注信号来自于哪个组件
从0开始的非负整数		 0
name 信号名称 信号全称，格式为：组件名.信号名 main.c.in[1]
一组.sym文件示例
1,1,1,main.out
2,2,1,main.in[0]
3,3,1,main.in[1]
4,-1,0,main.c.out
5,-1,0,main.c.in[0]
6,-1,0,main.c.in[1]

匿名组件

1、算是一种组件的语法糖，只支持circom2.1+

2、语法是：temp_name(arg1,...,argN)(input1,...,inputM)，要注意input信号的顺序。

匿名组件示例

1、示例：传统组件

// 创建一个电路A，输入信号两个，输出信号一个，约束是输出信号=输入信号相乘。
template A(n){
   signal input a, b;
   signal output c;
   c <== a*b;
}
//  创建一个电路B，输入信号是一个数组，输出信号一个，约束借助于A，也就是等于输出信号=输入信号数组内第一个元素和第二个元素相乘
template B(n){
   signal input in[n];
   signal out;
   component temp_a = A(n);
   temp_a.a <== in[0]; 
   temp_a.b <== in[1];
   out <== temp_a.c;
}
component main = B(2);

2、匿名改造

template A(n){
   signal input a, b;
   signal output c;
   c <== a*b;
}
template B(n){
   signal input in[n];
   signal out <== A(n)(in[0],in[1]);
}
component main = B(2);
总结匿名组件的语法

1、普通组件需要通过component来定义，而匿名组件不需要，直接实例化模板，比如直接A(n)

2、普通组件通过 实例.输入信号 进行电路之间的信号传递，而匿名组件通过实例(输入信号)的语法来进行信号传递，比如A(n)(x,y)

3、普通组件的输出需要通过 实例.输出信号来传递，而匿名组件直接对结果进行约束，比如signal out <== A(n)(in[0],in[1]);

匿名组件的输出信号

1、没有输出信号：直接temp_name(arg1,...,argN)(input1,...,inputM);

2、有一个输出信号：signal out1 <== temp_name(arg1,...,argN)(input1,...,inputM);

3、多个输出信号：使用元组

signal output a1, a2, a3;
(a1, a2, a3) <== temp_name(arg1,...,argN)(input1,...,inputM);

4、可以通过语法_来忽略其中部分输出信号（把对应的约束也忽略了）

template A(n){
   signal input a;
   signal output b, c, d;
   b <== a * a;
   c <== a + 2;
   d <== a * a + 2;
}
template B(n){
   signal input in;
   signal output out1;
   (_,out1,_) <== A(n)(in);  // 只留下c
}
component main = B(3);

5、扩展：元组也适合变量var

var  a1, a2, a3;
(a1, a2, a3) = temp_name(arg1,...,argN)(input1,...,inputM);

#circom基础语法学习结束，明天开始回到zk#

2024.08.06

Circom典型电路

注意这两个电路都不作为零知识证明，只是作为基础电路被引用到其它zkp电路中。

Num2Bit

功能：将十进制数字转化为二进制

pragma circom 2.0.0;

template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1=0;
    var e2=1;
    for (var i = 0; i<n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] -1 ) === 0;
        lc1 += out[i] * e2;
        e2 = e2+e2;
    }
    lc1 === in;
}

component main {public [in]}= Num2Bits(3);

isZero

功能：判断输入的是0还是1。

pragma circom 2.0.0;

template IsZero() {
    signal input in;
    signal output out;
    signal inv;
    inv <-- in!=0 ? 1/in : 0;
    out <== -in*inv +1;
    in*out === 0;
}

component main {public [in]}= IsZero();

2024.08.07

没学

2024.08.08

零知识证明系统的数学表达

以下的表都不保证对，要命

前提

1、R：一个可以高效计算的二元运算关系，即变量x和y之间的运算关系。这种关系可以是四则运算、hash运算、椭圆曲线有限域上运算等。

2、(x, w)：一个二元组，符合R运算，其中w是私有输入例如私钥，x是公开输入例如公钥。

步骤

存在五个算法阶段

算法阶段 生成 解释
sysGen 系统参数 生成椭圆曲线初始的系统参数：比如椭圆曲线的公式、有限域p等。
commitment 承诺 prover选择随机数r，发送承诺C = Com(x, w; r)
challenge 挑战 verifier从特定域中选择随机数e，发送给prover
response 响应 证明根据挑战生成响应：z = Response(x, w; e, r)
Verify 验证 verifier基于Com、验证响应 v = Verify(x, C, e, z)

zk-snarks的七个等价转化关系

等价转化的意思：将复杂问题简单化，最终转化为可以高效验证的形式。

关系 原理简述或公式 举例
计算关系 y=F(ω)，初始出入ω
R1CS（电路约束） 将算法用电路表达出来
向量s与多维向量/电路向量(um, vm, wm)的内积 多变量多项式的零点对应R1CS约束的解
向量s与电路矩阵U,V,W的内积
向量s与三组多项式U(x),V(x),W(x)的线性组合运算（系数）
目标多项式整除QAP或QSP多项式 构成NP问题
QAP多项式、目标多项式、商多项式的多指数运算 构成零知识证明
基于这三个多项式UVW的系数计算椭圆曲线离散对数点（双线性映射） 验证

非交互式零知识证明和数字签名的区别

Alice：Prover/Signer。Bob：Verifier

阶段 人 NIZKP ECDSA signature signature Schnorr signature
由私钥sk生成公钥 Alice Pk = sk.G Pk = sk.G Pk = sk.G Pk = sk.G
生成随机数r Alice r r r r
生成承诺R Alice R = r.G R= r.G，其中R^x^是R的横坐标 R = r.G R = r.G
加密消息 Alice 无 m = Hash(M) mod n m = Hash(M) m = Hash(M)
生成挑战c Alice c = Hash(Pk, R) c = Hash(R, m) c = Hash(Pk, R, m) c = Hash(R, m)
计算 Alice z = r + c.sk s = r^-1^(m+R^x^.sk) mod n z = r + c.sk z = r + c.sk
组合并传递给Bob Alice (R, z) (R^x^, s) (R, z) (R, z)
计算 Bob c' =Hash(Pk, R) c' = Hash(Pk, R, m) R' = z.G - c.Pk
验证 Bob z.G =R +c'.Pk R' = (s^-1^.m).G + (s^-1^.R^x^).Pk = R z.G = R + c'.Pk R' = R

r的作用：随机数，就是为了保密私钥sk的。作用等价于sk。

Tornado cash的原理是，通过zk证明知道Merkle Tree中的保密随机数r，就等于知道了私钥sk，就可以提资产了（也就是不必直接知道sk）

2024.08.09

请假

2024.08.10

ZK-snarks电路例子

等价转化的意思：将复杂问题简单化，最终转化为可以高效验证的形式。

zk-snark的过程：并不是将一个P问题转化为一个NP问题。而是找到了高效验证复杂问题是否满足某些条件的机制。

理论上任何只要能转化成电路约束的需求都可以最终转化为zk-snark，也就是实现零知识证明。

关系 原理简述或公式
计算关系 y=F(ω)，初始参数ω，F包含任意运算关系
R1CS（电路约束） 将算法用电路表达出来，初始参数还是ω
向量s与多维向量/电路向量(um, vm, wm)的内积 多变量多项式的零点对应R1CS约束的解
向量s与电路矩阵U,V,W的内积
向量s与三组多项式U(x),V(x),W(x)的线性组合运算（系数）
目标多项式整除QAP或QSP多项式 构成NP问题
QAP多项式、目标多项式、商多项式的多指数运算 构成零知识证明
基于这三个多项式UVW的系数计算椭圆曲线离散对数点（双线性映射） 验证

一、场景需求描述

1、需求：未知？

2、结果是x = 3 为解

二、数学公式化

$$ x^4 + x^3 + x^2 + x = 120 $$

三、电路化：变为R1CS

第一种R1CS逻辑

R1CS 逻辑 门 加法门强制转化乘法门
s1 = x * x x^2^ 乘法
s2 = s1 * x x^3^ 乘法
s3 = s2 * x x^4^ 乘法
s4 = s1 + x x^2^ + x 加法 s4 = (s1 + x) * 1
s5 = s4 + s2 x^3^ + x^2^ + x 加法 s5 = (s4 + s2) *1
120 = s5 + s3 120 = x^4^ + x^3^ + x^2^ + x 加法 120 = (s5 + s3) *1

优化的第二种R1CS逻辑

R1CS 逻辑 门
s1 = x * x x^2^ 乘法
s2 = s1 * x x^3^ 乘法
120 - (s2 + s1 +x) = s2 * x 120 - (x^3^ + x^2^ + x) = x^4^ 乘法

四、向量化（升维：将实数域转化为向量域）

前三步是最难的，之后全用snarkjs自动实现。

以优化后的第二种R1CS为例

1、构建向量s

1、解为x = 3

2、s表示为一个数组。

3、s的第一个元素是1，表示为任意常量

4、s = [1, output, input1, input2,...inputN] ，

5、其中output为公开的输出数据，即(1, output)就是statement。

6、其中input均为保密数据，即(input1,...inputN)就是witness。

7、所以zk-snark协议核心就是构造数据s = (statement; witness)

2、获取向量中的值

1、要获取向量中的某一个值，则点乘一个布尔向量c。

2、例如：获取 s = [1, out, x, s1, s2] 的s1，则s1 = s.c = [1, out, x, s1, s2] . [0, 0, 0, 1, 0]

3、构建多维向量

1、由于电路的基础是乘法门，即a*b=c，或称为U.V = W

2、对于s1 = x * x 这个乘法门，需要计算两边，用s来表达。

3、即s.w1 = s.u1 * s.v1。从实数域转化为向量域，后者包含前者。

4、s1 = s.c = [1, out, x, s1, s2] . [0, 0, 0, 1, 0] ，此时w = c = [0, 0, 0, 1, 0]

5、第一个x = s.c = [1, out, x, s1, s2] . [0, 0, 1, 0, 0] ，此时u = c = [0, 0, 1, 0, 0]

6、第二个x = s.c = [1, out, x, s1, s2] . [0, 0, 1, 0, 0] ，此时v = c = [0, 0, 1, 0, 0]

7、总结，如果将s1 = x * x 设为第一组约束的话，那么其向量为w1 = [0, 0, 0, 1, 0]，u1 = [0, 0, 1, 0, 0] ，v1 = [0, 0, 1, 0, 0]

8、同理对于s2 = s1 * x和120 - (s2 + s1 +x) = s2 * x，分别构建一维的向量为：w2 = [0, 0, 0, 0, 1]，u2 = [0, 0, 0, 1, 0] ，v2 = [0, 0, 1, 0, 0] ，w3 = [0, 1, -1, -1, -1]，u3 = [0, 0, 0, 0, 1] ，v3 = [0, 0, 1, 0, 0]

4、构建UVW矩阵

1、将三组约束变为一个UVW矩阵，其中：

2、W = [w1, w2, w3] = [[0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 1, -1, -1, -1]]

3、U = [u1, u2, u3] = [[0, 0, 1, 0, 0], [0, 0, 0, 1, 0] , [0, 0, 0, 0, 1] ]

4、V = [v1, v2, v3] = [ [0, 0, 1, 0, 0] , [0, 0, 1, 0, 0] ,[0, 0, 1, 0, 0] ]

五、向量与矩阵内积运算

1、将向量s与向量wi、ui、vi的分别多维内积计算，转化为s与矩阵UVW的内积计算。

2、即从s.w1 = s.u1 * s.v1，及s.w2 = s.u2 * s.v2， 及 s.w3 = s.u3 * s.v3

3、转化为：s.W = s.U * s.V

4、根据Schwartz–Zippel lemma：s.W(x) - s.U(x) * s.V(x) = 0

4、计算的目的：将WUV视为多项式的值，反求多项式的系数。

5、计算的方法：可选：拉格朗日插值法、最优：快速傅里叶变换FTT的变体：基4时分的Cooley-Tukey蝶形变化。

六、多项式线性组合化

z(x)整除QAP多项式

基于电路多项式W(x),U(x), V(x)生成局部系统参数CRS2

Prover将QAP多项式、目标多项式、商多项式放置到椭圆曲线的离散对数点上，并对外暴露此公钥。

Verifier进行双线性映射，重构整除关系，验证s是否正确但不知道s。

2024.08.11

重新总结交互式和非交互式零知识证明的相同和不同点，把基础弄牢固

前提

Alice（证明者），Bob（验证者）

交互式零知识证明IZK

1、Alice知道一个秘密，Bob去挑战，Alice给出证明，Bob验证，无论验证多少次，都验证成功，因此Bob判断：Alice确实知道这个秘密。

2、Alice：不保证全对（无法证明给Bob确实掌握了真理），但保证没错（每次都对）。

3、Bob在验证的过程中无法获取这个秘密，甚至是任何其他的知识。

交互式零知识证明的步骤

1、Alice生成私钥sk，公钥Pk=sk.G。

2、Alice给Bob传递公钥Pk

3、Alice生成随机数r

4、Alice计算出R = r.G，将R给Bob

5、Bob生成随机数c，将c给Alice

6、Alice计算出z = r + c.sk，将z给Bob

7、Bob验证z.G是否等于R +c.Pk

交互式零知识证明的3次交互步骤

0、Alice发送公钥Pk给Bob，由于公钥是分发的，不是点对点的交互，因此不算在交互次数里。

1、Alice发送R（这里R是承诺commitment）给Bob。

2、Bob发送c给Alice，这里c是随机挑战Challenge。

3、Alice发送挑战的响应z给Bob。

交互式零知识证明之信息总结

掌握的信息 Alice Bob
私钥/秘密：sk 是 否
公钥：Pk 是 是
随机数：r 是 否
承诺：R 是 是
挑战：随机数c 是 是
证明/挑战响应：z 是 是

扩展：关于随机数r的说明

1、r的存在是为了混淆sk。

2、作用是生成一个与密钥sk无关的承诺R。也就是说r和sk没有任何关系。

2、因此r是真随机数，不包含有用的信息。

3、包含有用信息的也就是所谓的知识或者秘密的载体是密钥sk。

4、r每次都变化，不允许存在同一知识的两个证明r一样的情况，不然就会计算出秘密sk。

同一知识的两个证明拥有相同r 计算出sk的推导公式

z1 = r + c1.sk

z2 = r + c2.sk

如果r不变，则

z1 - z2 = r - r + c1.sk - c2.sk = c1.sk - c2.sk

z1 - z2 = (c1 - c2).sk

sk = (z1 - z2)(c1 - c2)^-1^ mod p

其中(c1-c2)^-1^是(c1 - c2)在有限域上的乘法逆元。

因此sk可解出。

非交互式零知识证明NIZK

web3的零知识证明全是NIZK，不是IZK。

非交互式零知识证明的步骤

1、Alice生成私钥sk，公钥Pk=sk.G

2、Alice给Bob传递公钥Pk

3、Alice生成随机数r

4、Alice计算出R = r.G，（注：R理解为承诺）

5、Alice计算出c = Hash(Pk, R)，这里c的作用就是生成z。

6、Alice计算出z = r + c.sk

7、Alice将(R, z)发给Bob

8、Bob计算出c' =Hash(Pk, R)，

9、Bob验证是否 z.G =R +c'.Pk

交互式和非交互式零知识证明的区别

1、交互式由验证者Bob发起挑战，证明者Alice必须针对挑战回应。

2、交互式Bob可以多次挑战Alice。

3、非交互式由证明者Alice自主生成挑战。

4、非交互式只给一次挑战和一次证明。

掌握的信息 Alice Bob
私钥/秘密：sk 是 否
公钥：Pk 是 是
随机数：r 是 否
承诺：R 是 是
挑战：随机数c 是，自生成 是，自生成
证明/挑战响应：z 是 是

关于非交互式零知识证明中c的解释

c为什么安全

1、因为c是由R和Pk通过hash生成的，hash保证了只能通过彩虹攻击来破解。

2、而R是由r通过椭圆曲线生成的。这也是一个NP问题，理论上也只能通过掌握r才能控制。

3、而r是一个代码生成的伪随机数，只要确定Dapp的生成r的代码是正常的随机而不是人为操作，那么就可以保证c是安全的。

c的代码
from py_ecc import bn128
from py_ecc.bn128.bn128_curve import G1

def pedersen_commitment_pyecc(sk: int, r: int) -> tuple:
    """生成一个Pedersen承诺"""
    # G1是基点
    H = G1
    # sk * G1 是公开值
    Pk = bn128.multiply(H, sk)
    # 计算承诺值C
    C = bn128.add(bn128.multiply(G1, sk), bn128.multiply(H, r))
    return Pk, C

为什么INZP一次验证就可以

1、因为hash等操作保证了随机性的难度，就像是大海捞针，只需捞到一次就证明是海神，而不是假的。

2、究根结底还是依赖于r的随机性。

r的生成代码
import secret

def generate_csprng():
    return secrets.randbits(256)

2024.08.12

进度慢了，但只能这么快

IZP问题：哈密尔顿环路Hamiltonian Cycle

非常类似于三色图

1、哈密尔顿环路的游戏规则

1、有一个包含多个点的地图，个别点之间进行了连线，这些连线是可选路线。

2、证明人需要证明自己可以在G上提供一个没有回头路的路线（即不重复的路线），经过所有点的环路。

2、解决方案

1、证明人拥有原始地图G，注意这个G是零知识内容，验证人不知道。

2、证明人需要证明自己拥有最终路线x。

3、证明人每次证明前生成一个G的同态地图G'。

4、验证人每次挑战可以有两个挑战方式，只能二选一

5、第一种挑战方式是要求证明人提供加密全图G'，验证人验证G'是否是G的同态加密版本。注意这是在验证人不掌握G的前提下验证的，原理是利用了同态加密的证明人提供给验证人的G'生成的一些关键参数，知道这些参数和G'后，验证人可以验证G = G'，但无法获取G的信息。也无法获取到证明人是否有当前G’图上的路线。

6、第二种挑战方式是要求证明人提供基于当前G'图的1条Hamiltonian Cycle，也就是说如果证明人可以提供这个同态图上的路线，则说明他也可以提供在原图G上的路线。但这个过程中验证人既不能得出原图G上的路线，也不能获取G'图或者G图的全部信息，也不能获取是否G = G‘。

7、重复以上挑战即可证明。

关键点1：哈密尔顿环路的刷新机制

和其它IZK问题一样，当验证者挑战一次后，证明人会进行刷新，具体刷新的是下面提到的G'。

关键点2：转化为概率问题

1、由于一个完整的验证需要同时满足第一种挑战和第二种挑战。

2、而这种刻意的分割让确定的证明变成概率问题，同时保证了每次证明的零知识。

关键点3：承诺commit

1、其实有一个关键步骤没细讲，就是在3和4步之间，证明人将G'的隐藏版本交给了验证人。

2、这叫做承诺

3、这样做的目的是为了让验证者知道，我生成了G'不会随意改变。

4、概念上理解为：掩盖住的路线图。验证人如果选择挑战1则证明人揭开公开的R的所有路线G'，如果选择挑战2则揭开G‘上的答案路线x'。

5、实际上操作为：椭圆曲线私钥加密后的点：R=r.G

CRS

1、Common Reference String，公共参考串

2、证明前公开给Prover和Verifier。

3、随机的字符串。

4、存在目的：让「模拟器」与「验证者」不平等。

5、存在于非交互零知识证明NIZK中。

2024.08.13

这个课程绝对让我疯掉了。

半IZK问题：ZK-Ham2

1、同之前，已知G、G'、C、C’，G'=Perm(G)，C'=Perm(C)

2、承诺：不同于将G‘作为R，在这里以C'作为R，交给Bob

前置学习：G'和C'这两个矩阵中1和0单元的意思

0 1
G' 该点无边 该点有边
C' 有边，但该边不是回路 有边，且该边属于回路

关系：

1、C’的1 + C'的部分0 = G'的1

2、C'的1 + C'的0 = G'的1 + G'的0，也就是C'和G‘都存在补集，他们的全集一样的。

关系进一步分析：

1、C'属于G'：C′ 中的 1 只会出现在 G′ 的 1 位置。

2、也因此得出：C'中的0的位置可能是G'中的0，也可能是G'中的1。

挑战0的情况

1、不同于zk-ham的prover揭示全部G'来让verifier验证是否G'=Perm(G)。zk-ham2改为验证C' 是否合规。

2、所谓的合规并不是验证C' = Perm(C)，也不是验证是否C'是G‘的路径，而是验证C'自身是否是一个有效的环路。

3、其实就是揭示了所有 C'的1的部分。

4、所谓的揭示，可以理解为解密？可以，但通常就是展示秘密。

5、这么做的结果是：Alice似乎在对Bob说：你看，我有一条路线，这是一个答案，但Bob只能知道这是一条回路，但不知道这是否真是答案，因为它甚至不知道题目（G'）是什么。

挑战1的情况

验证内容

1、Alice需要证明的是：对于G'中所有的0，C'中对应位置也都是0。

2、即：如果该点无边，那么该点肯定不是环路上的路线。

3、即证明：Alice声称的哈密尔顿回路C'中，没有使用任何在G'中不存在的边。

验证过程

1、Alice发送置换函数Perm(.)给Bob。

2、揭示C'中的所有特定单元。这些单元对应于G'中值为0的位置。

3、Bob根据这些单元位置，在C'中进行验证，如果也都为0则正确，如果有1则证明无效。

4、这么做的结果是：Alice似乎在对Bob说：我能告诉你一部分不是环路的部分，但不能告诉你其它信息，你去验证下这部分是否不是环路，如果是环路，则我错了。

我的疑问

1、Bob为什么需要置换函数Perm(.)？Bob不知道G、G'、C、C’，在这四个都不知道的前提下，知道Perm(.)有什么用。

2、虽然Bob知道了G'中对应为0的元素，但难道Perm(.)可以逆向运算吗，难道可以推导G的0部分 = Perm(G'的0的部分)？

3、关键点：为什么挑战0和挑战1加起来就是一个完整验证了？这个验证严谨性逻辑我没懂，反正不如zk-ham好理解。

疑问回答

1、虽然Bob不知道G、G'、C、C’，但挑战1的时候，Bob知道了G'的0的部分和C'中0的部分。

2、Perm(.)分享给Bob是因为确实Perm(.)可逆（双射函数），也就是说Bob可以推导G的0部分 = Perm(G'的0的部分)。虽然这么做没必要。但可以验证：C的0的部分 = Perm(C'的0的部分)。

3、是的，综合挑战0验证C'是一个有效的环路以及挑战1验证C'不包含G'中不存在的边。这两个信息，就可以构成完整验证。

4、也就是说：zk-Ham2的Bob永远不会获得完整的G'或C'，这显得更加零知识了（连同态的知识都没有）。

5、这两个条件就像是要证明一个人是好人，只需要证明： 挑战0：这是一个人。 挑战1：这个人没做过坏事。

掌握的信息 zk-Ham的Alice zk-Ham的Bob zk-Ham2的Alice zk-Ham2的Bob
G 是 否 是 否
G'的0的部分，即!G 是 0挑战获取 是 1挑战获取
G'的1的部分 是 0挑战获取 是 否
C 是 否 是 否
C'的0的部分，即!C 是 1挑战获取 是 0挑战获取，1挑战获取
C'的1的部分 是 1挑战获取 是 0挑战获取
承诺 G' 加密的G'，包含0和1部分 C' 加密的C'，包含0和1部分
随机同态加密函数Perm(.) 是 否 是 1挑战获取

称为半IZK的原因

1、可以省略掉挑战0的情况，只保留一个挑战1即可。

2、也不需要承诺C'了。

3、直接使用可信第三方提供一个字符串代替所有。

4、这个可信第三方提供的内容：正确的环路C'。所以不需要挑战0了。也不需要对其进行承诺了。

5、这个可信的共享字符串不能让Bob知道。

6、而且这个可信第三方需要同时得到Alice和Bob的信任。

2024.08.14

总结了代码、算数、电路

常用电路

判断相等

等于0 isZero

分别用python和circom写出电路，判断输入的数字为0

1、理论基础

第一种方式是直接判断

第二种方式是费马小定理

费马小定理：

1、费马小定理提出，对于任意整数 a 和质数 p，如果 a 不被 p 整除，那么：a^(p-1)^ ≡ 1 (mod p)

2、由于p是质数，因此能整除p的只能是0或者p本身或p的倍数

3、而有限域定义在整数域{0, p-1}上，因此该整数域上只有0能被p整除。

4、利用这个定理，我们可以构造一个方法来证明一个数是否等于0：

  • 如果 a ≠ 0 (mod p)，那么 a^(p-1)^ - 1 ≡ 0 (mod p)
  • 如果 a ≡ 0 (mod p)，那么 a^(p-1)^ - 1 ≢ 0 (mod p)

2、python解答判断0

1、直接判断
def is_zero(a):
    return (f"{a} is {'zero' if a == 0 else 'non-zero'}")

p = 17  # A prime number
for i in range(p):
    print(is_zero(i))
2、费马小定律
def is_zero_fermat(a, p):
    """
    Check if a number is zero using Fermat's Little Theorem.
    
    :param a: The number to check
    :param p: A prime number (modulus)
    :return: True if a is zero, False otherwise
    """
    return pow(pow(a, p-1, p) - 1, p-1, p) == 0

# Example usage
p = 17  # A prime number
for a in range(p):
    print(f"{a} is {'non-zero' if is_zero_fermat(a, p) else 'zero'}")

3、circom电路判断0

用一个预先计算的提示值作为中间信号inv，来实现简单的0判断电路

pragma circom 2.0.0;

template IsZero() {
    signal input in;
    signal output out;
    signal inv;
    inv <-- in!=0 ? 1/in : 0;
    out <== -in*inv +1;
    in*out === 0;
}

component main {public [in]}= IsZero();

两数相等 isEqual

判断两个整数是否相等，如果相等返回1，否则为0

？

二进制Num2Bits

功能：将十进制数字转化为二进制

pragma circom 2.0.0;

template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1=0;
    var e2=1;
    for (var i = 0; i<n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] -1 ) === 0;
        lc1 += out[i] * e2;
        e2 = e2+e2;
    }
    lc1 === in;
}

component main {public [in]}= Num2Bits(3);

比较大小

GreaterThan

判断：整数s1是否大于s2？

逻辑

let y = s1 > s2 ? 1 : 0
y = 1 if s1 > s2 else 0

电路

要求

1、输入：s1和s2两个整数

2、输出：判断结果如果大于则为1，如果小于则为0

原理

1、无法在电路中直接比较十进制的整数大小

2、而需要转化为二进制。

3、因为二进制的加减法等算数运算都通过比较简单的门可以实现。

4、这里利用了二进制数的一个重要特性：较高位的 1 比任何较低位的组合都"更大"

步骤

1、先将十进制整数都转化为二进制。

2、比较依次从右向左，比较二进制的同一最高位。

3、如果该位一样都为1或者0，则比较下一位。

4、列出公式：y = s1 + 2^n^ - s2

代码略

LessThan

功能：输入两个整数的数组，判断数组中第一个数是否小于第二个数

include "Num2bits.circom"

// 参数n的解释：n为二进制的位数。手动限制二进制的位数的目的是减少计算量。
template LessThan(n){
    assert(n <= 252);
    signal input in[2];
    signal output out;
    component n2b = Num2Bits(n+1);
    
    n2b.in <== in[0] + (1 << n) - in[1];
    
    out <== 1-n2b.out[n];
}

其它函数包括：LessEqThan、GreaterEqThan

选择器Selecter

选择器的概念

二选一，if else，或三元判断 s ? a : b

选择器的实现

1、制造一个开关s，

2、s输入为二进制0或者1，表示两种选择的一种。

3、该s符合s *(s -1) = 0，其中s和s-1分别为开关两种状态。

4、每一种情况与其中一种状态相乘，即 y = s * a + (s-1) * b

5、这样当s输入不同的数时候，得到y = a 或者y = b。

问1：

交换

将两个输入a和b进行交换，输出为b和a

逻辑运算

1、逻辑自身是二进制，表示布尔值。

2、下面a和b理解为是条件的判断结果，比如a = 6 > 7，此时a = false。

3、值为1表示为真，值为0表示为假。

4、逻辑运算基于选择器

反门

两个值选任意一个都成立

代码
let y = !a
算数

当a = 0时候y = 1，反之当a = 1时候y = 0

y = 1 - a
电路
pragma circom 2.1.6;

template Reverse() {
    signal input a;
    signal output y;

    0 === a * (a - 1);
    y <== 1 - a;
}

component main  = Reverse();

/* INPUT = {
    "a": 1
} */

与门

a和b同时为1时候，y才能为1。

代码
let y = a & b
算数

y = a * b

电路
pragma circom 2.1.6;

template AND() {
    signal input a;
    signal input b;
    signal output y;

    0 === a * (a - 1);
    0 === b * (b - 1);
    y <== a * b;
}

component main  = AND();

/* INPUT = {
    "a": 1,
    "b": 1
} */

或门

两个值选任意一个都成立

代码
let y = a | b
算数

y=1 − (1−a)*(1−b)

电路
pragma circom 2.1.6;

template OR() {
    signal input a;
    signal input b;
    signal output y;
    
    0 === a * (a - 1);
    0 === b * (b - 1);
    y <== 1 - (1 - a) * (1 - b);
}

component main  = OR();

/* INPUT = {
    "a": 1,
    "b": 0
} */

异或

代码
let y = a ^ b
算数

y = a + b - 2 * (a * b)

电路
pragma circom 2.1.6;

template XOR() {
    signal input a;
    signal input b;
    signal output y;
    
    0 === a * (a - 1);
    0 === b * (b - 1);
    y <== a + b - 2 * (a * b) ;
}

component main  = XOR();

/* INPUT = {
    "a": 1,
    "b": 0
} */

2024.08.15

强制控制相等ForceEqualIfEnabled

1、enabled为输入参数，当1为强制两个输入的整数必须相等，即返回1。否则电路出错。

2、为0时候只是判断两个整数是否相等，和isEqual一样，不做控制。

3、使用场景是有点类似于将输入控制为0或1的x * (1 - x) === 0; 一样，就是控制输入。

pragma circom 2.0.0;

include "IsZero.circom";

template ForceEqualIfEnabled() {
    signal input enabled;
    signal input in[2];

    component isz = IsZero();

    in[1] - in[0] ==> isz.in;

    (1 - isz.out)*enabled === 0;
}

交换

将两个输入a和b进行交换，输出为b和a

算数

a, b = b, a

电路

设置了一个开关s

pragma circom 2.1.6;

template Swap() {
    signal input input1;
    signal input input2;
    signal input s;  // 交换标识，0 或 1
    signal output output1;
    signal output output2;

    0 === s * (s - 1);
    output1 <== (input2 - input1) * s + input1;
    output2 <== (input1 - input2) * s + input2;
}

component main = Swap();

/* INPUT = {
    "input1": 15,
    "input2": 8,
    "s": 1
} */

场景

排序

排序

从大到小排序

代码

a = [ 1, 5, 6, 3]
print( sorted(a, reverse=True))

# 冒泡排序
for i in range(len(a)):
    for j in range(0, len(a)-i-1):
        if a[j] < a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]  

print(a)  # Output: [6, 5, 3, 1]

算法

1、依次比较元素，如果a < b则交换位置

2、比较一轮后开始第二轮，执行元素多的轮次。

电路

1、排序必须导入交换swap、两个数比较大小GreaterThan和数字转化二进制Num2Bits、

2、电路的排序需要明确被比较的元素数量，不能未知数量。

// 以下只能三个非负整数按照从小到大排列。
pragma circom 2.1.6;

include "GreaterThan.circom";
include "Swap.circom";

// BubbleSort3 模板，用于对3个数字进行冒泡排序（从大到小）
template BubbleSort3(n) {
    signal input in[3];
    signal output out[3];

    // 第一次比较和交换
    component gt1 = GreaterThan(n);
    gt1.in[0] <== in[0];
    gt1.in[1] <== in[1];

    component swap1 = Swap();
    swap1.input1 <== in[0];
    swap1.input2 <== in[1];
    swap1.s <== gt1.out;

    // 交换后的中间结果
    signal temp0;
    signal temp1;
    temp0 <== swap1.output1;
    temp1 <== swap1.output2;

    // 第二次比较和交换
    component gt2 = GreaterThan(n);
    gt2.in[0] <== temp0;
    gt2.in[1] <== in[2];

    component swap2 = Swap();
    swap2.input1 <== temp0;
    swap2.input2 <== in[2];
    swap2.s <== gt2.out;

    // 交换后的中间结果
    signal temp2;
    temp2 <== swap2.output2;

    // 第三次比较和交换
    component gt3 = GreaterThan(n);
    gt3.in[0] <== temp1;
    gt3.in[1] <== temp2;

    component swap3 = Swap();
    swap3.input1 <== temp1;
    swap3.input2 <== temp2;
    swap3.s <== gt3.out;

    // 输出最终结果
    out[0] <== swap2.output1;
    out[1] <== swap3.output1;
    out[2] <== swap3.output2;
}

component main= BubbleSort3(10);

/* INPUT = {
    "in": [2,4,2]
} */

2024.08.16

了解了什么是semaphore，以及它和tornado cash实现匿名交易的不同原理。 复习了merkle tree相关的操作。 circom的进度太慢了，又没有勇气把每个电路复现一遍，很痛苦。

2024.08.17

Circom的简单数字签名

需求

证明内容

我（证明者）拥有能够生成这个数字签名的私钥，但我不会向你（验证者）展示这个私钥本身。

电路过程

1、证明者：公钥密码生成器：输入私钥sk，输出公钥pk

2、证明者：签名sign：s = Sign(m, sk)

3、验证者：验证verify：bool = Verify(m, s, pk)，从而验证陈述。

代码

公钥生成模块

1、调用circomlib的posidon组件，该组件用来生成哈希。

2、利用该组件来从私钥生成公钥

pragma circom 2.1.6;

include "circomlib/poseidon.circom";

template sk2pk() {
    signal input sk;
    signal output pk;

    component poseidon = Poseidon(1);

    poseidon.inputs[0] <== sk;

    pk <== poseidon.out;
}

component main = sk2pk();

/* 
INPUT = { "sk": 5 }
*/

/* pk = 19065150524771031435284970883882288895168425523179566388456001105768498065277 */

posidon详解

加密哈希函数，专为电路设计，相比SHA256等传统加密函数在电路方面更加快且节省资源。

将一个或多个输入的整数转化为哈希值。

输出为BN254即254位的大整数。（254位二进制转为十进制）

2024.08.18

circomlib/poseidon详解

见zk-练习。

签名模块

模块特点

1、输入了m却没有对m进行约束，这意味着m可以是任何数。

2、没有输出一个签名signature，意味着sign的过程没有真实的一个签名生成。

对m不约束的原因

1、m本身对于零知识证明没有影响，也就是无论任何消息被签名，都不影响生成签名这个过程。

2、但同时还是需要m，因为这是签名必要的一个输入。

没有输出签名signature的原因

？

pragma circom 2.1.6;

include "sk2pk.circom";


template sign () {
    signal input sk;
    signal input pk;
    signal input m;
    // signal output signature; 注意没有这个输出，具体为什么不清楚。
    component s2p = sk2pk();
    s2p.sk <== sk;
    s2p.pk === pk;  // 只能约束不能赋值，因为是判断两个pk是否相等。其中s2p.pk就是sk算出来的pk'。
}

component main { public [ m, pk ] } = sign();

/* INPUT = {
"sk": "5", 
"pk":"19065150524771031435284970883882288895168425523179566388456001105768498065277", 
"m":"123"
} */

没有验证模块电路的原因

Circom的群签名（固定群大小）

需求分阶段剖析

1、我能进行群签名。

2、证明一组签名中，有一个是我的有效签名。

3、证明人拥有群签名的其中至少一个签名的私钥。

4、证明人可以创建群签名暴露的公钥串里至少其中一个公钥。

分析

1、和数字签名的不同点是有多个pk被暴露。

2、需要通过减后相乘==0来进行判断是否拥有其中之一。

3、也就是利用了一个数学定理：对于一个连乘的数，只有其中至少一个乘数=0时候，结果才=0。

代码

生成公钥部分一样

签名部分

pragma circom 2.1.6;

include "sk2pk.circom";

template Sign (n) {
    signal input sk;
    signal input pk[n];
    signal input m;
    // 设计一个连乘判断0项
    signal ZeroCheck[n+1];
    // 初始元素仅在第一次判断使用，设为常量1或者任意不等于0的数字。
    ZeroCheck[0] <== 1;
    
    component s2p = sk2pk();
    s2p.sk <== sk;
    
    // 连乘逻辑
    for (var i = 0; i < n; i ++){
        ZeroCheck[i+1] <== ZeroCheck[i] * (s2p.pk - pk[i]);
    }
    // 对连乘结果进行判断
    ZeroCheck[n] === 0;
}

component main { public [ m, pk ] } = Sign(3);


/* INPUT = {
"sk": "5", 
"pk":["19065150524771031435284970883882288895168425523179566388456001105768498065277","1","2"], 
"m":"123"
} */

Circom的群签名（不固定群大小）

需求分析

和固定群大小的需求一样

只不过特点是群人数不确定。

固定的原因是电路必须是确定的，编译后不能改变了。

分析

使用merkle tree 告一段落吧，再来30天左右应该可以达到求职水平了。

接下来的任务：

1、完成0xparc练习10天。 2、看三个源码，每个一星期。 3、简单构建个人项目相关的电路。

Bye