区块链中的数学 - VRF基于ECC公钥体制的证明生成过程 | 登链社区

区块链中的数学 - VRF基于ECC公钥体制的证明生成过程

blocksight
更新于 2020-10-07 11:55
阅读 3683

本文主要介绍了VRF基于ECC公钥体制的证明生成过程，其中涉及多个辅助方法，这些方法只是做了简要的介绍，因为详细说明每个方法会有很多内容，先搞清楚主要过程，后续有时间再细说。

## 写在前面

上一节说了[基于RSA的VRF实现](https://learnblockchain.cn/article/1544)，继承了RSA算法的简洁性。

本文讲基于椭圆曲线秘钥体制的VRF实现，关于椭圆曲线算法的知识如果不熟悉，可先参考文末“**相关阅读**”部分。

## ECVRF

基于椭圆曲线实现的VRF记为ECVRF，满足可信唯一性，可信抗碰撞性和全伪随机性（trusted uniqueness", "trusted collision resistance", "full pseudorandomness"），关于些安全性要求，在VRF概述章节中均有所介绍。

### 符号约定

F - 有限域

2n - 域元素字节长度，向上取整

E -  F上的椭圆曲线

ptLen - 椭圆曲线点编码成字符串长度

G -  E上大素数子群

q -  群G的素数阶

qLen - q的字节长度

cofactor - E曲线点数除q 即谐因子

B - G生成元

suite_string - 标识 ECVRF套件（ciphersuite），包含上述选项参数

SK - VRF私钥

x - VRF秘密整数标量（根据不同的曲线类型，有可能等于SK，也有可能从SK派生）

Y = x*B - VRF 公钥

## 证明生成过程

**方法1**：  ECVRF_prove(SK, alpha_string)

参数：
SK - VRF 私钥
alpha_string - 原始消息

返回值:
pi_string - 长度为k的证明字符串

执行主要过程:

1. 使用 SK 派生出 VRF 密钥x， 计算VRF公钥 Y = x * B（依赖具体曲线实例或有不同）

2. 计算H = ECVRF_hash_to_curve(suite_string, Y, alpha_string)

3. 将H转化为string，g = point_to_string(H)

4. 令Gamma = x * H

5. 计算k = ECVRF_nonce_generation(SK, h_string)

6. 计算c = ECVRF_hash_points(H, Gamma, kB, kH)

7. 计算s = (k + c*x) mod q

8. 拼接证明：pi_string = point_to_string(Gamma) || int_to_string(c, n) || int_to_string(s, qLen)

9. 返回 pi_string

**方法2**：   ECVRF_proof_to_hash(pi_string)

参数：
pi_string -- VRF 证明结果

返回值:
beta_string - VRF Proof 哈希值

执行主要过程:

1. 还原proof结构，D = ECVRF_decode_proof(pi_string)

2. 验证D正确性，若非法则停止

3. 解构D: (Gamma, c, s) = D

4. 令 three_string = 0x03 = int_to_string(3, 1)

5. 计算哈希：beta_string = Hash(suite_string || three_string || point_to_string(cofactor * Gamma))

6. 返回结果 beta_string

可以看到，其实核心步骤是5，来计算最终hash

下面重点说下，证明生成过程中用到的辅助方法。

### 重要方法说明

1. ECVRF_hash_to_curve
    该方法将传入的原始信息结合曲线suite参数计算哈希，并将结果哈希映射到曲线上的点， 不同的椭圆曲线有不同的实现方法。

2. ECVRF_nonce_generation
    从SK和其他输入中派生出一个伪随机数

3. ECVRF_hash_points
    对传入的椭圆曲线的若干点做哈希运算

4. point_to_string
    椭圆曲线的点转成字符串，与之对应的还有下面方法。

5. string_to_point
    字符串转成椭圆曲线的点

## 小结

本文主要介绍了VRF基于ECC公钥体制的证明生成过程， 其中涉及多个辅助方法，这些方法只是做了简要的介绍，因为详细说明每个方法会有很多内容，先搞清楚主要过程，后续有时间再细说。

好了，证明有了，如何验证是否合法呢？
下一篇继续说[基于椭圆曲线公钥体制的VRF证明验证过程](https://learnblockchain.cn/article/1582)！

欢迎关注公众号：blocksight

### 相关阅读：

[区块链中的数学-基于RSA的VRF实现](https://learnblockchain.cn/article/1544)

[区块链中的数学-RSA签名过程！](https://learnblockchain.cn/article/1546)

[区块链中的数学-RSA加解密原理](https://learnblockchain.cn/article/1548)

[区块链中的数学-VRF（随机可验证函数）概述](https://learnblockchain.cn/article/1543)

[区块链中的数学-Uniwap核心算法解析-完结篇](https://learnblockchain.cn/article/1522)

[区块链中的数学-Uniwap核心算法解析（下）](https://learnblockchain.cn/article/1521)

[区块链中的数学-Uniwap核心算法解析（中）](https://learnblockchain.cn/article/1492)

[区块链中的数学-Uniwap自动化做市商核心算法解析（上）](https://learnblockchain.cn/article/1494)

[区块链中的数学-射影平面与椭圆曲线方程](https://learnblockchain.cn/article/1529)

[区块链中的数学-椭圆曲线上的群及代数运算](https://learnblockchain.cn/article/1530)

[区块链中的数学-离散域模素数上的加法&椭圆曲线中离散对数问题](https://learnblockchain.cn/article/1549)

[区块链中的数学-椭圆曲线加密原理和实例演练](https://learnblockchain.cn/article/1550)

[区块链中的数学-椭圆曲线进行签名和验证过程](https://learnblockchain.cn/article/1551)

写在前面

上一节说了基于RSA的VRF实现，继承了RSA算法的简洁性。

本文讲基于椭圆曲线秘钥体制的VRF实现，关于椭圆曲线算法的知识如果不熟悉，可先参考文末“相关阅读”部分。

ECVRF

符号约定

F - 有限域

2n - 域元素字节长度，向上取整

E - F上的椭圆曲线

ptLen - 椭圆曲线点编码成字符串长度

G - E上大素数子群

q - 群G的素数阶

qLen - q的字节长度

cofactor - E曲线点数除q 即谐因子

B - G生成元

suite_string - 标识 ECVRF套件（ciphersuite），包含上述选项参数

SK - VRF私钥

x - VRF秘密整数标量（根据不同的曲线类型，有可能等于SK，也有可能从SK派生）

Y = x*B - VRF 公钥

证明生成过程

方法1： ECVRF_prove(SK, alpha_string)

参数： SK - VRF 私钥 alpha_string - 原始消息

返回值: pi_string - 长度为k的证明字符串

执行主要过程:

使用 SK 派生出 VRF 密钥x，计算VRF公钥 Y = x * B（依赖具体曲线实例或有不同）
计算H = ECVRF_hash_to_curve(suite_string, Y, alpha_string)
将H转化为string，g = point_to_string(H)
令Gamma = x * H
计算k = ECVRF_nonce_generation(SK, h_string)
计算c = ECVRF_hash_points(H, Gamma, kB, kH)
计算s = (k + c*x) mod q
拼接证明：pi_string = point_to_string(Gamma) || int_to_string(c, n) || int_to_string(s, qLen)
返回 pi_string

方法2： ECVRF_proof_to_hash(pi_string)

参数： pi_string -- VRF 证明结果

返回值: beta_string - VRF Proof 哈希值

执行主要过程:

还原proof结构，D = ECVRF_decode_proof(pi_string)
验证D正确性，若非法则停止
解构D: (Gamma, c, s) = D
令 three_string = 0x03 = int_to_string(3, 1)
计算哈希：beta_string = Hash(suite_string || three_string || point_to_string(cofactor * Gamma))
返回结果 beta_string

可以看到，其实核心步骤是5，来计算最终hash

下面重点说下，证明生成过程中用到的辅助方法。

重要方法说明

ECVRF_hash_to_curve 该方法将传入的原始信息结合曲线suite参数计算哈希，并将结果哈希映射到曲线上的点，不同的椭圆曲线有不同的实现方法。
ECVRF_nonce_generation 从SK和其他输入中派生出一个伪随机数
ECVRF_hash_points 对传入的椭圆曲线的若干点做哈希运算
point_to_string 椭圆曲线的点转成字符串，与之对应的还有下面方法。
string_to_point 字符串转成椭圆曲线的点

小结

好了，证明有了，如何验证是否合法呢？下一篇继续说基于椭圆曲线公钥体制的VRF证明验证过程！

欢迎关注公众号：blocksight