Zhuang's Diary

​ 造成网页近重复的可能原因主要包括：镜像网站；内容复制；嵌入广告；计数改变；少量修改
​ 传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的缺点就是，无法将其扩展到海量数据。例如，试想像Google那种收录了数以几十亿互联网信息的大型搜索引擎，每天都会通过爬虫的方式为自己的索引库新增的数百万网页，如果待收录每一条数据都去和网页库里面的每条记录算一下余弦角度，其计算量是相当恐怖的。
​ 考虑采用为每一个web文档通过hash的方式生成一个指纹（fingerprint）。但是，传统的加密式hash，比如md5，其设计的目的是为了让整个分布尽可能地均匀，输入内容哪怕只有轻微变化，hash就会发生很大地变化。我们理想当中的哈希函数，需要对几乎相同的输入内容，产生相同或者相近的hashcode，换句话说，hashcode的相似程度要能直接反映输入内容的相似程度。很明显，前面所说的md5等传统hash无法满足我们的需求。
​ simhash是locality sensitive hash（局部敏感哈希）的一种，它产生的hash签名在一定程度上可以表征原内容的相似度。最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。Google就是基于此算法实现网页文件查重的。假设有以下三段文本：
​ the cat sat on the mat
​ the cat sat on a mat
​ we all scream for ice cream
使用传统hash可能会产生如下的结果：

1
2
3
4
5
6
7
8
9

irb(main):006:0> p1 = ‘the cat sat on the mat’
irb(main):005:0> p2 = ‘the cat sat on a mat’
irb(main):007:0> p3 = ‘we all scream for ice cream’
irb(main):007:0> p1.hash
=> 415542861
irb(main):007:0> p2.hash
=> 668720516
irb(main):007:0> p3.hash
=> 767429688

使用simhash会应该产生类似如下的结果：

1
2
3
4
5
6
7
8
9

irb(main):003:0> p1.simhash
=> 851459198
00110010110000000011110001111110
irb(main):004:0> p2.simhash
=> 847263864
00110010100000000011100001111000
irb(main):002:0> p3.simhash
=> 984968088
00111010101101010110101110011000

​ 海明距离的定义，为两个二进制串中不同位的数量。上述三个文本的simhash结果，其两两之间的海明距离为(p1,p2)=4，(p1,p3)=16以及(p2,p3)=12。事实上，这正好符合文本之间的相似度，p1和p2间的相似度要远大于与p3的。距离越小，则相似度越大。一般大文本去重，大小<=3的即可判断为重复。
​ 如何实现这种hash算法呢？simhash算法分为5个步骤：1、分词、2、hash、3、加权、4、合并、5、降维

1. 分词：

选择适合自己的分词库进行分词即可。
如“欢迎来到随迹”->（分词后）“欢迎”、“来到”、“随迹”

2. hash：

对每个词计算其hash值，hash值为二进制数01组成的n-bit签名。
设“欢迎“（100101）、“来到”（101011）、“随迹”（101011）

3. 加权：

对于给定的文本，权值即为分词后对应词出现的数量。给所有特征向量进行加权，即W = Hash * weight；这里我们假设三个词权值分别为4、5、9；
根据计算规则遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘
例如给“欢迎”的hash值“100101”加权得 到：W(欢迎) = 1001014 = 4 -4 -4 4 -4 4，给“来到”的hash值“101011”加权得到：W(来到)=1010115 = 5 -5 5 -5 5 5，剩下的按此规则计算

4. 合并：

将上述各个特征向量的加权结果累加，变成只有一个序列串。拿前两个特征向量举例，例如“欢迎”的“4 -4 -4 4 -4 4”和“来到”的“5 -5 5 -5 5 5”进行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。

5. 降维：

对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海 明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于0记为1，小于0记为0），得到的01串为：“1 0 1 0 1 1”，从而形成它们的simhash签名。

Markdown ==> 一文了解最热门的zkSNARK方案-Groth16.pdf

web ==> 一文了解最热门的zkSNARK方案-Groth16.pdf

参考链接 ==> https://docs.circom.io/ ， 一套完整的 ZKP 的工具链。

安装

1
2

npm install -g circom
npm install -g snarkjs

构建电路

1.创建circuit.circom文件

1
2
3
4
5
6
7
8

template Multiplier() {
   signal private input a;
   signal private input b;
   signal output c;
   c <== a*b;
}

component main = Multiplier();

​ 此电路的目的是让我们向某人证明我们能够因式分解整数c。具体来说，使用此电路，我们将能够证明我们知道两个数字（a和b）相乘得到c，而不会显示a和b。这个电路有2个 private 输入信号，名为 a 和 b ，还有一个输出 c。输入和输出使用<==运算符进行关联。在circom中，<==运算符做两件事。 首先是连接信号。 第二个是施加约束。在本例中，我们使用<==将c连接到a和b，同时将c约束为a * b的值，即电路做的事情是让强制信号 c 为 a*b 的值。在声明 Multiplier 模板之后, 我们使用名为main的组件实例化它。注意：编译电路时，必须始终有一个名为main的组件。

2.编译电路

1

circom circuit.circom --r1cs --wasm --sym

• --r1cs: 生成 circuit.r1cs ( r1cs 电路的二进制格式约束系统)
• --wasm: 生成 circuit.wasm ( wasm 代码用来生成见证 witness 稍后再介绍)
• --sym: 生成 circuit.sym (以注释方式调试和打印约束系统所需的符号文件）

r1cs是将代数电路转换为zk-snark的第一步。

构建零知识证明

​ 使用snarkjs 来生成和验证 zk-SNARK 证明。我们将证明能够分解数字33。也就是说，将证明我们知道两个整数a和b，以便将它们相乘时得出33。

1.查看电路有关的信息

​ 使用 snarkJS，您可以获得电路的一般统计数据并打印约束。

1
2
3
4
5
6
7
8

➜  circom snarkjs info -r circuit.r1cs 
[INFO]  snarkJS: Curve: bn-128
[INFO]  snarkJS: # of Wires: 4
[INFO]  snarkJS: # of Constraints: 1
[INFO]  snarkJS: # of Private Inputs: 2
[INFO]  snarkJS: # of Public Inputs: 0
[INFO]  snarkJS: # of Labels: 4
[INFO]  snarkJS: # of Outputs: 1

1
2

➜  circom snarkjs print -r circuit.r1cs -s circuit.sym
[INFO]  snarkJS: [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.a ] * [ main.b ] - [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.c ] = 0

2.setup

2.1 设置的生成分为两个阶段：第一步是创建一些称为tau的幂的值。此处，我们将保留一个“ powers of tau”文件。 运行以下命令：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

➜  circom snarkjs powersoftau new bn128 12 pot12_0000.ptau -v
[DEBUG] snarkJS: Calculating First Challenge Hash
[DEBUG] snarkJS: Calculate Initial Hash: tauG1
[DEBUG] snarkJS: Calculate Initial Hash: tauG2
[DEBUG] snarkJS: Calculate Initial Hash: alphaTauG1
[DEBUG] snarkJS: Calculate Initial Hash: betaTauG1
[DEBUG] snarkJS: Blank Contribution Hash:
		786a02f7 42015903 c6c6fd85 2552d272
		912f4740 e1584761 8a86e217 f71f5419
		d25e1031 afee5853 13896444 934eb04b
		903a685b 1448b755 d56f701a fe9be2ce
[INFO]  snarkJS: First Contribution Hash:
		9e63a5f6 2b96538d aaed2372 481920d1
		a40b9195 9ea38ef9 f5f6a303 3b886516
		0710d067 c09d0961 5f928ea5 17bcdf49
		ad75abd2 c8340b40 0e3b18e9 68b4ffef
➜  circom snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="First contribution" -v
Enter a random text. (Entropy): zhuangweiming
[DEBUG] snarkJS: Calculating First Challenge Hash
[DEBUG] snarkJS: Calculate Initial Hash: tauG1
[DEBUG] snarkJS: Calculate Initial Hash: tauG2
[DEBUG] snarkJS: Calculate Initial Hash: alphaTauG1
[DEBUG] snarkJS: Calculate Initial Hash: betaTauG1
[DEBUG] snarkJS: processing: tauG1: 0/8191
[DEBUG] snarkJS: processing: tauG2: 0/4096
[DEBUG] snarkJS: processing: alphaTauG1: 0/4096
[DEBUG] snarkJS: processing: betaTauG1: 0/4096
[DEBUG] snarkJS: processing: betaTauG2: 0/1
[INFO]  snarkJS: Contribution Response Hash imported: 
		e15fa0f4 126ae14d 0e724ffa ee1adaba
		1f9f44fb a963db61 e0eda605 4a172efa
		124d177b 3a565656 1f1a3a23 6dea3366
		3b21ec32 8a26d7b2 ac98ff89 2b1962ae
[INFO]  snarkJS: Next Challenge Hash: 
		b77a3861 ad4a4cbb abe3e870 69787d8c
		85ab1372 c15bff14 352c15fb 3116c3c8
		81791ae6 3258fbcb 898cad52 c9863e00
		c336b311 f8bfb38e 3cefc2cd 917c86eb

​ 系统将提示您输入一些随机文本，这些文本将用作熵的来源。输入文本后，命令将输出一个名为pot12_001.ptau的脚本。设置的第一部分是通用的，对任何电路都有用，因此您可以将其保存以在以后的项目中重复使用。

​ 要获得zk-SNARK证明的证明和验证密钥，必须生成设置。此步骤需要生成一些需要消除的随机值。 消除过程至关重要：如果暴露了这些价值，则整个方案的安全性将受到损害。想要构建设置，我们使用多方计算（MPC）仪式，该仪式允许多个独立方共同构建参数。使用MPC，一个参与者删除其贡献的秘密副本就足够了，以确保整个方案的安全。
​ 可信设置的构建分为两个阶段：对任何电路均有效的常规MPC仪式（称为powers of tau ceremony），以及为每个特定电路构造的第二阶段（阶段2）。任何人都可以通过其随机性参与MPC仪式，通常，在获取最终参数之前，将应用一个随机信标。

2.2 下一步，称为设置的阶段2，运行命令如下：

1

snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v

​ 以上命令运行完成后，pot12_final.ptau文件被生成。该计算在笔记本电脑上大概花费了3分钟时间。

​ 第二阶段的产生与我们使用tau的能力相似。将生成一个.zkey文件，其中将包含证明和验证密钥以及所有第二阶段贡献。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// Start a new zkey and make a contribution
➜  circom snarkjs zkey new circuit.r1cs pot12_final.ptau circuit_0000.zkey
[INFO]  snarkJS: Reading r1cs
[INFO]  snarkJS: Reading tauG1
[INFO]  snarkJS: Reading tauG2
[INFO]  snarkJS: Reading alphatauG1
[INFO]  snarkJS: Reading betatauG1
[INFO]  snarkJS: Circuit hash: 
		965f5c51 98906eb7 8fc597d1 d7b31bdf
		ad7f0491 d1cc081d 8d236685 489f05be
		b621e87a 1ba57a28 25071ac3 a69a4df1
		1ec4b2c6 aa36b8f2 94e37d17 270ce6bf

➜  circom snarkjs zkey contribute circuit_0000.zkey circuit_final.zkey --name="1st Contributor Name" -v
Enter a random text. (Entropy): zhuangweiming
[DEBUG] snarkJS: Applying key: L Section: 0/2
[DEBUG] snarkJS: Applying key: H Section: 0/4
[INFO]  snarkJS: Circuit Hash: 
		965f5c51 98906eb7 8fc597d1 d7b31bdf
		ad7f0491 d1cc081d 8d236685 489f05be
		b621e87a 1ba57a28 25071ac3 a69a4df1
		1ec4b2c6 aa36b8f2 94e37d17 270ce6bf
[INFO]  snarkJS: Contribution Hash: 
		7987d679 5c914cb3 4138e57a ceee7ae4
		8974b323 585bb48f 056fdd8f ea858cd3
		a625d63e d8394b9c 974912e4 801aff06
		0064f25a 677e727a a289252d 397b8d04

​ 和上述步骤一样，系统将提示您输入一些随机文本以提供熵的来源。输出将是一个名为circuit_final.zkey的文件，我们将使用该文件导出验证密钥(verification key)。

​ 现在，来自circuit_final.zkey的验证密钥导出到文件Verification_key.json中。verification key:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

{
 "protocol": "groth16",
 "curve": "bn128",
 "nPublic": 1,
 "vk_alpha_1": [
  "15175462370442750548879662426586324604498073737772476635702014058846911119264",
  "11126336670194938919608091368599342163660484801811140235738809534621680589277",
  "1"
 ],
 "vk_beta_2": [
  [
   "5251596196706483766793357074374737595900200707659808196530067991530054260554",
   "2264756861473257353315497004278362201201416308719887395373581359048933031269"
  ],[
   "10552939216865106848464515813683167112323139053174380454808956637789377680967",
   "2701413932452289802745906093844601151278714195849736706988417564960748034273"
  ],[
   "1",
   "0"
  ]
 ],
 "vk_gamma_2": [
  [
   "10857046999023057135944570762232829481370756359578518086990519993285655852781",
   "11559732032986387107991004021392285783925812861821192530917403151452391805634"
  ],[
   "8495653923123431417604973247489272438418190587263600148770280649306958101930",
   "4082367875863433681332203403145435568316851327593401208105741076214120093531"
  ],[
   "1",
   "0"
  ]
 ],
 "vk_delta_2": [
  [
   "8590425680399084984710617722188581478119753421410764960451677916514215428082",
   "15713152249579034550437632242139020796726126371657275384984401462748083625785"
  ],[
   "4862154669589263828958978916321240414342527577427918353789686327852433696883",
   "9569117504828540945921139710836305890297695048604628362102771433345477012098"
  ],[
   "1",
   "0"
  ]
 ],
 "vk_alphabeta_12": [
  [
   [
    "1121360319902761693820363426996646168569211552394580075970634177898785008311",
    "14249756278025620543130105348741511241747839379662316431830590326729096142975"
   ],[
    "16423439174084021024919681708878615489972548829583206833909869670703901853110",
    "9329143387573491748526724433415355164900218750592620992570237269470665264202"
   ],[
    "19623272010929083665872244835381945771016147820964222485760645671773298080071",
    "9896773903597386179712166971836923631098313509393860803813715414524549373292"
   ]
  ],[
   [
    "18313799470766842592075662760908626166323669476646669856687182611043590126171",
    "7532895603020793142335129648471958187885524608608576812436682807569433790546"
   ],[
    "20059629119556696413695556916087392540474931269939016250934117162067722623426",
    "11285185652573117971807135387812020477130047554451136821582438888864777467010"
   ],[
    "18429091017205122590573696082242994893262627891230351210235517202888391625680",
    "7734180768772801433386131669021273948517355047659921136453462913759461451288"
   ]
  ]
 ],
 "IC": [
  [
   "17305572679177982597803616153716539127293296363987765110136569516232291230411",
   "7425872175786571904106950706682618227429476545503095908552111445555350791878",
   "1"
  ],[
   "16125521217907931491019162042616560858833563034453402251972608389495277275869",
   "20962607216912168718282504555696865046978428189883507401556888923455626427056",
   "1"
  ]
 ]
}

​ 可以验证.ptau或.zkey文件的计算是否正确：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

➜  circom snarkjs powersoftau verify pot12_final.ptau
[INFO]  snarkJS: Powers Of tau file OK!
[INFO]  snarkJS: Next challenge hash: 
		b77a3861 ad4a4cbb abe3e870 69787d8c
		85ab1372 c15bff14 352c15fb 3116c3c8
		81791ae6 3258fbcb 898cad52 c9863e00
		c336b311 f8bfb38e 3cefc2cd 917c86eb
[INFO]  snarkJS: -----------------------------------------------------
[INFO]  snarkJS: Contribution #1: First contribution
[INFO]  snarkJS: Next Challenge: 
		b77a3861 ad4a4cbb abe3e870 69787d8c
		85ab1372 c15bff14 352c15fb 3116c3c8
		81791ae6 3258fbcb 898cad52 c9863e00
		c336b311 f8bfb38e 3cefc2cd 917c86eb
[INFO]  snarkJS: Response Hash:
		e15fa0f4 126ae14d 0e724ffa ee1adaba
		1f9f44fb a963db61 e0eda605 4a172efa
		124d177b 3a565656 1f1a3a23 6dea3366
		3b21ec32 8a26d7b2 ac98ff89 2b1962ae
[INFO]  snarkJS: Response Hash:
		9e63a5f6 2b96538d aaed2372 481920d1
		a40b9195 9ea38ef9 f5f6a303 3b886516
		0710d067 c09d0961 5f928ea5 17bcdf49
		ad75abd2 c8340b40 0e3b18e9 68b4ffef
[INFO]  snarkJS: -----------------------------------------------------
[INFO]  snarkJS: Powers of Tau Ok!
➜  circom snarkjs zkey verify circuit.r1cs pot12_final.ptau circuit_final.zkey
[INFO]  snarkJS: Reading r1cs
[INFO]  snarkJS: Reading tauG1
[INFO]  snarkJS: Reading tauG2
[INFO]  snarkJS: Reading alphatauG1
[INFO]  snarkJS: Reading betatauG1
[INFO]  snarkJS: Circuit hash: 
		965f5c51 98906eb7 8fc597d1 d7b31bdf
		ad7f0491 d1cc081d 8d236685 489f05be
		b621e87a 1ba57a28 25071ac3 a69a4df1
		1ec4b2c6 aa36b8f2 94e37d17 270ce6bf
[INFO]  snarkJS: Circuit Hash: 
		965f5c51 98906eb7 8fc597d1 d7b31bdf
		ad7f0491 d1cc081d 8d236685 489f05be
		b621e87a 1ba57a28 25071ac3 a69a4df1
		1ec4b2c6 aa36b8f2 94e37d17 270ce6bf
[INFO]  snarkJS: -------------------------
[INFO]  snarkJS: contribution #1 1st Contributor Name:
		7987d679 5c914cb3 4138e57a ceee7ae4
		8974b323 585bb48f 056fdd8f ea858cd3
		a625d63e d8394b9c 974912e4 801aff06
		0064f25a 677e727a a289252d 397b8d04
[INFO]  snarkJS: -------------------------
[INFO]  snarkJS: ZKey Ok!

3.计算witness

​ 在创建任何证明之前，我们需要计算与电路的所有约束匹配的电路的所有信号。为此，我们将使用由circom生成的Wasm模块来帮助完成此工作。我们只需要提供一个包含输入的文件，模块将执行电路并计算所有中间信号和输出。输入，中间信号和输出的集合称为见证人(witness)。

​ 本次的范例中，我们想证明我们能够分解数字33。因此，指定a=3, b=11。创建一个文件，命名为 input.json

1

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

​ 下面开始就算 witness，生成 witness 文件， 命令如下：

1

snarkjs wtns calculate circuit.wasm input.json witness.wtns

4.创建证明

​ 这个命令默认会使用 prooving_key.json 和 witness.json 文件去生成 proof.json 和 public.json。

1

snarkjs groth16 prove circuit_final.zkey witness.wtns proof.json public.json

proof.json 文件包含了实际的证明。而 public.json 文件将仅包含公共的输入（当前的例子没有）和输出（当前的例子是 33）。

5.验证证明

1
2

➜  circom snarkjs groth16 verify verification_key.json public.json proof.json
[INFO]  snarkJS: OK!

​ 此命令使用我们之前导出的verify_key.json文件，proof.json和public.json来检查证明是否有效。如果证明有效，则命令输出OK。一个有效的证明不仅证明我们知道满足电路要求的一组信号，而且证明我们使用的公共输入和输出与public.json文件中描述的匹配。

​ **实际上，在此阶段，将把proof.json和public.json文件都交给验证者。**但是，出于教程的目的，我们还将扮演验证者的角色。借助证明以及公共输入和输出，我们现在可以向验证者证明我们知道一个或多个满足电路约束的私有信号，而无需透露有关那些私有信号的任何信息。从验证者的角度来看，她可以验证我们是否知道见证中包含的一组私有信号，而无需访问它。这是zk-proof背后魔术的核心！

6.智能合约验证证明

1

snarkjs zkey export solidityverifier circuit_final.zkey verifier.sol

​ 上述命令使用验证密钥circuit_final.zkey并在名为verifier.sol的文件中输出合约代码。可以看到该代码包含两个协定：Pairing和Verifier。只需要部署Verifier合约。

​ 生成智能合约调用的参数，命令如下：

1
2

➜  circom snarkjs zkesc public.json proof.json
["0x29b83d63472e4f47b092fd4ced43a566697f0575186964c7cc3deec2c5c1b0bd", "0x2eb116882d2bacdbeece8a2adf2ab6d0f4420b60e82b4b66ddb18cc26ab2bae2"],[["0x170d208ad3a8bf4358c207706bce9e87cbad11037f642d1ab06f65a5ebf10eb4", "0x0dc07edd498cc16c5174c2a5a2aeed86c2f5689ed25486e8981768d7c7ceae13"],["0x1c52e6144e980ae72e5c5679c979c70e0da4a519fc087dda3b96bbea09179b20", "0x2849fdea744fa924ae19eb15917dac4543c0fa3b888293dfcd365c6251f25223"]],["0x01918c12515eb00b823f0e2a63ef53e15792b4b4fd331b595ffc670e929d6b99", "0x2246e9bb88119c6f8f1c04735beeee038ddc6e66572cb44f1c926575db80be9a"],["0x0000000000000000000000000000000000000000000000000000000000000021"]

​ 验证者具有一个称为verifyProof的函数，当且仅当证明和输入有效时，该函数才返回TRUE。

​ 如果仅更改参数中的任何位，则可以检查结果返回 false 。

漏洞修复

​ 我们已经表明可以生成证明我们知道两个因子a和b使得a*b=33的证明。但这不能证明我们知道如何分解数字33，因为我们可以选择a = 1和b = 33，通常对于任何整数n，选择输入a=1，b=n。在此，我们需要修改电路，以便不可能将数字1分配给任何输入。为此，我们将使用0是唯一没有反数的事实。

​ 这里的技巧是使用0不可求倒数的属性，约束不接受 1 作为任何一个输入，即(a-1) 不可求倒数的方式来约束电路。

​ 如果 a 是 1 则 (a-1)*inv = 1 是不可能成立的，通过 1/(a-1) 来计算 inv 。

修正电路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

template Multiplier() {
   signal private input a;
   signal private input b;
   signal output c;
   signal inva;
   signal invb;

   inva <-- 1/(a-1);
   (a-1)*inva === 1;
   invb <-- 1/(b-1);
   (b-1)*invb === 1;

   c <== a*b;
}

component main = Multiplier();

​ 您可能已经注意到，我们引入了两个新的运算符 : <-- 和 === 。<-- 和 --> 操作符运算符只为信号分配一个值，而不创建任何约束。=== 操作符添加约束而不分配值。如前所述，<== 为信号分配一个值并添加一个约束。这意味着它只是 <--和 === 的组合。但是，由于并非总是希望在同一步骤中同时完成这两个步骤，因此circom 的灵活性使我们可以将这一步分为两步。

​ 事实证明，电路仍然存在一个细微的问题：由于运算是在有限域（Z_r）上进行的，因此我们需要确保乘法不会溢出。

最后

​ circomlib 写好了一些基本的电路，如：binaritzations、comparators, eddsa, hashes, merkle trees 等等。

定义

​ 椭圆曲线和很多学习完基础代数之后见过的方程差不多。y在等号的左边，而x在等号的右边。椭圆曲线有如下的形式：
$$
y^2 = x^3+ax+b
$$
​ 你肯定接触过其他类似的方程。比如，在基础代数课上就学过线性函数：
$$
y=mx+b
$$
​ 你可能还记得m叫作斜率，b叫作截距。你也能画出线性函数图像。类似地，你可能也熟悉二次函数和它的图像：
$$
y=ax^2+bx+c
$$
​ 在学习代数时，你还接触过更高阶的函数比如三次函数及其图像。
$$
y=ax^3+bx^2+cx+d
$$
​ 椭圆曲线和他们没有太大的区别。椭圆曲线和三次函数不同的地方在于等号左边是y的平方，这使得函数图像沿x轴对称：
$$
y^2 = x^3 + ax + b
$$

​ 因为椭圆曲线的等号左边是y的平方，所以它也不像三次函数那样陡峭。此外，椭圆曲线可能是不想接的，如下图：

​ 比如，比特币使用的椭圆曲线被称为secp256k1，使用下面的方程：
$$
y^2=x^3+7
$$

椭圆曲线的加法

过曲线上的两点A、B画一条直线，找到直线与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A+B，即为加法。如下图所示：A + B = C

​ 椭圆曲线因其点加法运算(point addition)而被广泛使用。

椭圆曲线的二倍运算

​ 上述方法无法解释A + A，即两点重合的情况，因此在这种情况下，将椭圆曲线在A点的切线，与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A + A，即2A，即为二倍运算。

同余运算

​ 同余就是有相同的余数，两个整数 a、 b，若它们除以正整数 m所得的余数相等，则称 a，b对于模m同余。
$$
a≡b (mod m)
$$

有限域

​ 椭圆曲线是连续的，并不适合用于加密，所以必须把椭圆曲线变成离散的点，要把椭圆曲线定义在有限域上。而椭圆曲线密码所使用的椭圆曲线是定义在有限域内，有限域最常见的例子是有限域GF(p)，指给定某质数p，由0,1,2…,p-1共p个元素组成的整数集合中加法、二倍运算。例如GF(233)就是：
$$
y^2=(x^3+7) (mod 223)
$$
详见上一篇帖子。

乘法逆元

在模7乘法中：

• 1的逆元为1 (1*1)%7=1
• 2的逆元为4 (2*4)%7=1
• 3的逆元为5 (3*5)%7=1
• 4的逆元为2 (4*2)%7=1
• 5的逆元为3 (5*3)%7=1
• 6的逆元为6 (6*6)%7=1

数学解释

​ 并不是所有的椭圆曲线都适合加密，上述是一类可以用来加密的椭圆曲线，也是最为简单的一类。

针对曲线Ep(a,b)表示为：
$$
y^2=x^3+ax+b(mod p), x,y \in [0,p],p为质数
$$
​ 该曲线关于x轴对称。选择两个满足下列条件的小于p(p为素数)的非负整数a、b，要求满足以下条件：
$$
4a^3+27b^2≠0(mod p),a和b是小于p的非负整数
$$
1、有限域的负元

​ P(x,y)的负元是(x,-ymodp)=(x,p-y)

2、有限域的加法，P+Q

​ P(x1,y1)，Q(x2,y2)和R(x3,y3)三点，其中R是PQ直线与曲线的交点的关于x轴的对称点，即 R=P+Q，有如下关系：
$$
x_3≡k^2-x_1-x_2(modp),y_3≡k(x_1-x_3)-y_1(modp)
$$
3、斜率计算

​ 若P=Q，即计算P点切线，则
$$
k=(3x_2+a) \div (2y_1)
$$
​ 若P≠Q，则
$$
k=(y_2-y_1) \div (x_2-x_1)
$$

椭圆曲线加解密算法原理

​ 设私钥、公钥分别为d、Q，即Q = dG，其中G为基点，椭圆曲线上的已知G和dG，求d是非常困难的，也就是说已知公钥和基点，想要算出私钥是非常困难的。其中基点是椭圆曲线上选择的一个点，这个点能够保证满足dG=∞的最小正整数n足够大，也就是阶足够大。1<私钥<n，大于n的私钥必能在[1,n)中找到对应的私钥b使得aG=bG，换句话说也就是有足够多的私钥。
**公钥加密：**选择随机数r，将消息M生成密文C，该密文是一个点对，C = {rG, M+rQ}，其中Q为公钥。
私钥解密：M + rQ - d(rG) = M + r(dG) - d(rG) = M，其中d、Q分别为私钥、公钥。

椭圆曲线签名算法原理

​ 椭圆曲线签名算法(ECDSA)。设私钥、公钥分别为d、Q，即Q = dG，其中G为基点。

私钥签名：

• 选择随机数r，计算点rG(x, y)。
• 根据随机数r、消息M的哈希h、私钥d，计算s = (h + dx)/r。　　
• 将消息M、和签名{rG, s}发给接收方。

公钥验证签名：　　

• 接收方收到消息M、以及签名{rG=(x,y), s}。　　
• 根据消息求哈希h。　　
• 使用发送方公钥Q计算：hG/s + xQ/s，并与rG比较，如相等即验签成功。
  原理：hG/s + xQ/s = hG/s + x(dG)/s = (h+xd)G/s = r(h+xd)G / (h+dx) = rG

签名过程

​ 假设要签名的消息是一个字符串：“Hello World!”。DSA签名的第一个步骤是对待签名的消息生成一个消息摘要，不同的签名算法使用不同的消息摘要算法，而ECDSA256使用SHA256生成256比特的摘要。

​ 摘要生成结束后，应用签名算法对摘要进行签名：

• 产生一个随机数k
• 利用随机数k，计算出两个大数r和s。将r和s拼在一起就构成了对消息摘要的签名。
  这里需要注意的是，因为随机数k的存在，对于同一条消息，使用同一个算法，产生的签名是不一样的。从函数的角度来理解，签名函数对同样的输入会产生不同的输出。因为函数内部会将随机值混入签名的过程。

验证过程

​ 关于验证过程，这里不讨论它的算法细节。从宏观上看，消息的接收方从签名中分离出r和s，然后利用公开的密钥信息和s计算出r。如果计算出的r和接收到的r值相同，则表示验证成功，否则，表示验证失败。

有限域的定义

​ 有限域的数学定义是一个有限的数字集以及两个运算+(加法）和·(乘法）,并且满足下面的性质：

1.如果a和b属于集合，则a+b和a·b也属于集合。我们称此性质为封闭性。

2.存在0使得a+0=a。我们称此性质为加法恒等。

3.存在1使得a·1=a,我们称此性质为乘法恒等。

4.如果a属于集合，则-a属于集合；满足a+(-a)=0。我们称此性质为加法逆。

5.如果a属于集合，
$$
则 a^{-1}属于集合，满足 a \cdot a^{-1}=1。我们称此性质为乘法逆。
$$
​ 我们来进一步分析这些准则。

​ 有一个有限的数的集合，因为集合是有限的，所以可以把集合大小定义为p，我们称之为集合的阶。

​ 性质1要求对加法和乘法封闭。这意味着定义加法和乘法时要使其运算结果仍然属于集合。比如集合{0,1,2}并不对加法封闭，因为1+2=3，3不在集合内；同理2+2=4也不符合定义。当然，可以对加法定义做一些修改来使其满足有限域的性质，但是“常见”的加法并不能使这个集合组成有限域。另外，集合{-1,0,1}对正常的乘法是封闭的。任意两个集合内的元素（共有9种组合）其乘积仍然属于集合。

​ 另一个选项是对乘法重新定义以满足有限域的封闭性。但是其核心概念是这里定义的加法和减法不同于我们熟悉的加法和减法。

​ 性质2和性质3意味着必须要有加法和乘法恒等元，也就是0和1必须在集合内。

​ 性质4意味着有加法逆。如果a在集合内，-a也在集合内，通过使用加法逆运算，我们可以定义减法。

​ 性质5意味着乘法有着相同的性质，如果a在集合内，则a-t也在集合内，即a·a’=1,通过乘法逆，我们可以定义除法。这是定义一个有限域最难的部分。

定义有限集合

​ 如果集合的阶（大小）是p，我们可以说该集合的元素有0,1,2,3,…,p-1。把这些数称为集合的元素，而不必称其为传统的数字0,1,2,3等。这些集合的元素在很多方面和传统数字一致，但是在如加法、减法和乘法等运算上仍有一些地方不太一样。有限域的数学表示如下：
​ Fp={0,1,2,…,p-1}构成有限域的是集合的元素。Fp是一个特定的有限域，读作“阶数为p的域”（field of p)、“阶数为29的有限域”或者其他阶数（重申：数学家把集合大小称为阶）。{}之间的数字代表域中的元素。我们将这些元素命名为0,1,2等，因为这些名字便于使用。

一个阶数为11的域如下：
F11={0,1,2,3,4,5,6,7,8,9,10}

一个阶数为17的域如下：
F17={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

一个阶数为983的域如下：
F983={0,1,2,…，982}

​ 注意，域的阶数总是比最大元素大1。你可能注意到了每次我们给出的域的阶数都是质数。出于很多之后才能解释清楚的原因，域的阶数必须为质数的整数次幕，其中阶数为质数的有限域是我们特别关心的。