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

blocksight
更新于 2020-10-13 21:21
阅读 4033

本文主要介绍了VRF基于ECC公钥体制的证明验证过程，基于前一文的基础，本篇顺理成章地说明了验证的内在逻辑，别的地方很难有这样的内在分析！

## 写在前面

上一节说了[基于椭圆曲线的VRF证明生成](https://learnblockchain.cn/article/1545)，利用了椭圆曲线的性质。

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

本文中用到的符号含义同上篇，不再解释。

## ECVRF验证

验证方法如下：

**方法**：  ECVRF_verify(Y, pi_string, alpha_string)

参数：
Y - 公钥

pi_string - VRF 生成的证明, 长度 ptLen + n + qLen

alpha_string - 原始输入消息

返回值:

valid - 是否验证通过

执行主要过程:

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

2. 检验 D 合法性，如非法则停止

3. 解构D内容， (Gamma, c, s) = D

4. 映射曲线上的点H = ECVRF_hash_to_curve(suite_string, Y, alpha_string)

5. 计算U = s * B - c * Y

6. 计算 V = s * H - c * Gamma

7. 令c' = ECVRF_hash_points(H, Gamma, U, V)，对若干点做散列

8. 检验c == c' 则合法, 否则返回非法
    （Optional：如果合法同时计算出proof散列：ECVRF_proof_to_hash(pi_string)）

过程总体比较清晰，涉及到的方法在上一文中进行了简要说明，不懂的可以回头看。

事出必有因，为什么这样验证是正确的做法？得从原理上分析。

## 原理说明

由于c' = ECVRF_hash_points(H, Gamma, U, V)， 只要参数H, Gamma, U, V与证明生成过程是一样的值，自然就能满足c == c'。

首先， 容易得到H，Gamma在证明生成和验证期间值是相同的，因为计算方式和参数完全一致。
再次，需要证明U = k * B, V = k * H。

验证过程中:

U = s * B - c * Y = s * B - c * x * B = (s - c * x)* B

由生成过程知 s = (k + c * x ) --> s - c * x = k

代入得 U = k * B 得证。

V = s * H - c * Gamma = s * H - c * x * H = (s - c * x)* H = k * H

全部得证。

## 小结

本文主要介绍了[VRF基于ECC公钥体制的证明验证过程](https://learnblockchain.cn/article/1582)， 基于前一文的基础，本篇顺理成章地说明了验证的内在逻辑，别的地方很难有这样的内在分析！还是那句话：

**知其然知其所以然，是我们一贯坚持的原则！**

具体实现中还会有不少细节， 如如何将任意字符串映射到曲线上的point等。
好在已有成熟的实现库了，例如libsodium中的ECVRF-EDWARDS25519-SHA512-Elligator2, Google实现的ECVRF-P256-SHA256-TAI等，可自行查阅。

到此我们已经介绍了椭圆曲线基本性质，原理和两种实例：SM2&secp256k1具体算法，但是远未结束。

[下一篇](https://learnblockchain.cn/article/1598)继续说椭圆曲线类别中的爱德华曲线（Edwards curve），这在一些区块链项目中已经被采用！

欢迎关注公众号：blocksight

### 相关阅读：

[区块链中的数学-基于椭圆曲线的VRF证明生成](https://learnblockchain.cn/article/1545)

[区块链中的数学-基于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)

[区块链中的数学-射影平面与椭圆曲线方程](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)

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

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

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

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

写在前面

上一节说了基于椭圆曲线的VRF证明生成，利用了椭圆曲线的性质。

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

本文中用到的符号含义同上篇，不再解释。

ECVRF验证

验证方法如下：

方法： ECVRF_verify(Y, pi_string, alpha_string)

参数： Y - 公钥

pi_string - VRF 生成的证明, 长度 ptLen + n + qLen

alpha_string - 原始输入消息

返回值:

valid - 是否验证通过

执行主要过程:

还原证明结构，D = ECVRF_decode_proof(pi_string)
检验 D 合法性，如非法则停止
解构D内容， (Gamma, c, s) = D
映射曲线上的点H = ECVRF_hash_to_curve(suite_string, Y, alpha_string)
计算U = s B - c Y
计算 V = s H - c Gamma
令c' = ECVRF_hash_points(H, Gamma, U, V)，对若干点做散列
检验c == c' 则合法, 否则返回非法（Optional：如果合法同时计算出proof散列：ECVRF_proof_to_hash(pi_string)）

过程总体比较清晰，涉及到的方法在上一文中进行了简要说明，不懂的可以回头看。

事出必有因，为什么这样验证是正确的做法？得从原理上分析。

原理说明

由于c' = ECVRF_hash_points(H, Gamma, U, V)，只要参数H, Gamma, U, V与证明生成过程是一样的值，自然就能满足c == c'。

首先，容易得到H，Gamma在证明生成和验证期间值是相同的，因为计算方式和参数完全一致。再次，需要证明U = k B, V = k H。

验证过程中:

U = s B - c Y = s B - c x B = (s - c x)* B

由生成过程知 s = (k + c x ) --> s - c x = k

代入得 U = k * B 得证。

V = s H - c Gamma = s H - c x H = (s - c x) H = k H

全部得证。

小结

本文主要介绍了VRF基于ECC公钥体制的证明验证过程，基于前一文的基础，本篇顺理成章地说明了验证的内在逻辑，别的地方很难有这样的内在分析！还是那句话：

知其然知其所以然，是我们一贯坚持的原则！

具体实现中还会有不少细节，如如何将任意字符串映射到曲线上的point等。好在已有成熟的实现库了，例如libsodium中的ECVRF-EDWARDS25519-SHA512-Elligator2, Google实现的ECVRF-P256-SHA256-TAI等，可自行查阅。

到此我们已经介绍了椭圆曲线基本性质，原理和两种实例：SM2&secp256k1具体算法，但是远未结束。

下一篇继续说椭圆曲线类别中的爱德华曲线（Edwards curve），这在一些区块链项目中已经被采用！

欢迎关注公众号：blocksight