Schnorr NIZK 非交互式零知识证明

Schnorr Identification Scheme

Schnorr Identification Scheme 是一种基于离散对数问题的身份验证协议。它是一个交互式协议，通常包括以下三个步骤：

1. 承诺阶段（Commitment Phase）：

   • 证明者选择一个随机数 $r$。
   • 计算承诺值 $R = rG$ 并发送给验证者。

2. 挑战阶段（Challenge Phase）：

   • 验证者选择一个随机挑战值 $c$ 并发送给证明者。

3. 响应阶段（Response Phase）：

   • 证明者计算响应值 $s = r + cx$ 并发送给验证者。
   • 验证者检查等式 $sG = R + cX$ 是否成立。如果成立，则验证通过。

Fiat-Shamir 变换

Fiat-Shamir 变换是一种将交互式证明系统转换为非交互式证明系统的技术。它通过将挑战值的选择过程替换为哈希函数的计算，从而消除了交互的需要。具体来说，Fiat-Shamir 变换的步骤如下：

1. 承诺阶段（Commitment Phase）：

   • 证明者选择一个随机数 $r$。
   • 计算承诺值 $R = rG$。

2. 挑战生成（Challenge Generation）：

   • 证明者计算挑战值 $c = H(R, X)$，其中 $H$ 是一个安全的哈希函数。

3. 响应阶段（Response Phase）：

   • 证明者计算响应值 $s = r + cx$。
   • 证明者生成非交互式证明 $(R, s)$。

4. 验证阶段（Verification Phase）：

   • 验证者收到 $(R, s)$ 和公钥 $X$。
   • 验证者重新计算挑战值 $c = H(R, X)$。
   • 验证者检查等式 $sG = R + cX$ 是否成立。

Schnorr Identification Scheme 与 Fiat-Shamir 变换的关系

Schnorr Identification Scheme 和 Fiat-Shamir 变换的关系可以概括为：Fiat-Shamir 变换将 Schnorr Identification Scheme 转化为 Schnorr NIZK 证明。具体来说，Fiat-Shamir 变换通过使用哈希函数生成挑战值，将 Schnorr 的交互式身份验证协议转换为非交互式零知识证明。

具体关系

1. 交互式到非交互式：

   • Schnorr Identification Scheme 是交互式的，需要证明者和验证者之间的多次通信。
   • Fiat-Shamir 变换将其转换为非交互式的，证明者可以独立生成证明，验证者可以独立验证。

2. 挑战值生成：

   • 在 Schnorr Identification Scheme 中，挑战值由验证者生成。
   • 在 Fiat-Shamir 变换中，挑战值由哈希函数生成，消除了验证者的参与。

3. 等式验证：

   • 两者的核心验证等式都是 $sG = R + cX$，只是挑战值生成方式不同。

总结

Schnorr Identification Scheme 和 Fiat-Shamir 变换密切相关。Fiat-Shamir 变换通过使用哈希函数生成挑战值，将 Schnorr 的交互式身份验证协议转换为非交互式零知识证明。这种转换使得证明过程更加高效和便捷，适用于需要零知识证明的各种场景。

Schnorr 非交互零知识（NIZK）证明

Schnorr 非交互零知识（NIZK）证明的核心等式是用来验证证明的正确性。具体来说，这个等式在验证过程中检查了证明者提供的响应值是否正确。以下是 Schnorr NIZK 证明的核心等式：

$sG = R + hX$

其中：

• $G$ 是椭圆曲线的生成元。
• $s$ 是证明者提供的响应值。
• $R$ 是证明者提供的承诺值。
• $h$ 是通过哈希函数计算得到的挑战值。
• $X$ 是公钥（即 $X = xG$，其中 $x$ 是证明者的私钥）。

详细解释 ⚡️

生成证明：

• 证明者选择一个随机数 $r$。
• 计算承诺值 $R = rG$。
• 计算挑战值 $h = H(R, X)$，其中 $H$ 是一个安全的哈希函数。
• 计算响应值 $s = r + hx$。
• 证明由 $(R, s)$ 组成。

验证证明：

• 验证者收到 $(R, s)$ 和公钥 $X$。
• 验证者重新计算挑战值 $h = H(R, X)$。
• 验证者检查等式 $sG = R + hX$ 是否成立。

验证过程中的等式推导

为了验证等式 $sG = R + hX$，我们可以将 $s$ 的表达式代入：

$$s = r + hx$$

将其代入等式左边：

$$sG = (r + hx)G = rG + hxG$$

因为 $X = xG$，所以：

$$sG = rG + hX$$

这与验证等式 $sG = R + hX$ 一致，因此验证通过。

带有会话 ID 的变体

当使用会话 ID 来防止重放攻击时，挑战值的计算方式会有所不同，但核心验证等式保持不变：

$$sG = R + hX$$

其中挑战值 $h$ 现在是基于会话 ID 计算的：

$$h = H(\text{sessionId}, R, X)$$

总结

Schnorr NIZK 证明的核心等式 $sG = R + hX$ 是验证过程中最关键的一步。通过这个等式，验证者可以确认证明者确实知道某个秘密值 $x$，而不需要泄露该值。

code

package schnorr

import (
	"fmt"
	"math/big"

	"github.com/okx/threshold-lib/crypto"
	"github.com/okx/threshold-lib/crypto/curves"
)

type Proof struct {
	R *curves.ECPoint
	S *big.Int
}

// Prove schnorr s = r + hx
func Prove(x *big.Int, X *curves.ECPoint) (*Proof, error) {
	if x == nil || X == nil {
		return nil, fmt.Errorf("schnorr prove parameters error")
	}
	q := X.Curve.Params().N

	r := crypto.RandomNum(q)
	R := curves.ScalarToPoint(X.Curve, r)

	h := crypto.SHA256Int(X.X, X.Y, R.X, R.Y)
	h = new(big.Int).Mod(h, q)

	s := new(big.Int).Mul(h, x)
	s = new(big.Int).Mod(new(big.Int).Add(r, s), q)
	return &Proof{R: R, S: s}, nil
}

// Verify s*G = R + h*X
func Verify(pf *Proof, X *curves.ECPoint) bool {
	if pf == nil || pf.R == nil || pf.S == nil {
		return false
	}
	if !pf.R.IsOnCurve() || !X.IsOnCurve() {
		return false
	}
	q := X.Curve.Params().N
	h := crypto.SHA256Int(X.X, X.Y, pf.R.X, pf.R.Y)
	h = new(big.Int).Mod(h, q)

	SG := curves.ScalarToPoint(X.Curve, pf.S)
	Xh := X.ScalarMult(h)
	RXh, err := pf.R.Add(Xh)
	if err != nil {
		return false
	}
	return RXh.X.Cmp(SG.X) == 0 && RXh.Y.Cmp(SG.Y) == 0
}

// ProveWithId schnorr s = r + hx
func ProveWithId(sessionId, x *big.Int, X *curves.ECPoint) (*Proof, error) {
	if x == nil || X == nil {
		return nil, fmt.Errorf("schnorr prove parameters error")
	}
	q := X.Curve.Params().N

	r := crypto.RandomNum(q)
	R := curves.ScalarToPoint(X.Curve, r)
	G := curves.ScalarToPoint(X.Curve, big.NewInt(1))

	h := crypto.SHA256Int(sessionId, G.X, G.Y, X.X, X.Y, R.X, R.Y)
	h = new(big.Int).Mod(h, q)

	s := new(big.Int).Mul(h, x)
	s = new(big.Int).Mod(new(big.Int).Add(r, s), q)
	return &Proof{R: R, S: s}, nil
}

// VerifyWithId s*G = R + h*X
func VerifyWithId(sessionId *big.Int, pf *Proof, X *curves.ECPoint) bool {
	if pf == nil || pf.R == nil || pf.S == nil {
		return false
	}
	if !pf.R.IsOnCurve() || !X.IsOnCurve() {
		return false
	}
	q := X.Curve.Params().N
	G := curves.ScalarToPoint(X.Curve, big.NewInt(1))

	h := crypto.SHA256Int(sessionId, G.X, G.Y, X.X, X.Y, pf.R.X, pf.R.Y)
	h = new(big.Int).Mod(h, q)

	SG := curves.ScalarToPoint(X.Curve, pf.S)
	Xh := X.ScalarMult(h)
	RXh, err := pf.R.Add(Xh)
	if err != nil {
		return false
	}
	return RXh.X.Cmp(SG.X) == 0 && RXh.Y.Cmp(SG.Y) == 0
}

当然，以下是对您提供的 Schnorr 签名和验证代码的详细解释：

Prove 函数

// Prove schnorr s = r + hx
func Prove(x *big.Int, X *curves.ECPoint) (*Proof, error) {
    if x == nil || X == nil {
        return nil, fmt.Errorf("schnorr prove parameters error")
    }
    q := X.Curve.Params().N

    r := crypto.RandomNum(q)
    R := curves.ScalarToPoint(X.Curve, r)

    h := crypto.SHA256Int(X.X, X.Y, R.X, R.Y)
    h = new(big.Int).Mod(h, q)

    s := new(big.Int).Mul(h, x)
    s = new(big.Int).Mod(new(big.Int).Add(r, s), q)
    return &Proof{R: R, S: s}, nil
}

解释：

• 输入参数：

  • x：签名者的私钥。
  • X：签名者的公钥（椭圆曲线点）。

• 步骤：

  1. 检查输入参数是否为 nil。
  2. 获取椭圆曲线的阶 q。
  3. 生成一个随机数 r。
  4. 计算 R = r * G，其中 G 是椭圆曲线的基点。
  5. 计算哈希值 h = SHA256(X.X, X.Y, R.X, R.Y) 并取模 q。
  6. 计算 s = (r + h * x) mod q。
  7. 返回 Schnorr 证明 Proof{R: R, S: s}。

Verify 函数

// Verify s*G = R + h*X
func Verify(pf *Proof, X *curves.ECPoint) bool {
    if pf == nil || pf.R == nil || pf.S == nil {
        return false
    }
    if !pf.R.IsOnCurve() || !X.IsOnCurve() {
        return false
    }
    q := X.Curve.Params().N
    h := crypto.SHA256Int(X.X, X.Y, pf.R.X, pf.R.Y)
    h = new(big.Int).Mod(h, q)

    SG := curves.ScalarToPoint(X.Curve, pf.S)
    Xh := X.ScalarMult(h)
    RXh, err := pf.R.Add(Xh)
    if err != nil {
        return false
    }
    return RXh.X.Cmp(SG.X) == 0 && RXh.Y.Cmp(SG.Y) == 0
}

解释：

• 输入参数：

  • pf：Schnorr 证明（包含 R 和 S）。
  • X：签名者的公钥（椭圆曲线点）。

• 步骤：

  1. 检查输入参数是否为 nil，并且 R 和 X 是否在曲线上。
  2. 获取椭圆曲线的阶 q。
  3. 计算哈希值 h = SHA256(X.X, X.Y, pf.R.X, pf.R.Y) 并取模 q。
  4. 计算 SG = S * G。
  5. 计算 Xh = h * X。
  6. 计算 RXh = R + Xh。
  7. 比较 RXh 和 SG 是否相等，若相等则验证通过。

ProveWithId 函数

// ProveWithId schnorr s = r + hx
func ProveWithId(sessionId, x *big.Int, X *curves.ECPoint) (*Proof, error) {
    if x == nil || X == nil {
        return nil, fmt.Errorf("schnorr prove parameters error")
    }
    q := X.Curve.Params().N

    r := crypto.RandomNum(q)
    R := curves.ScalarToPoint(X.Curve, r)
    G := curves.ScalarToPoint(X.Curve, big.NewInt(1))

    h := crypto.SHA256Int(sessionId, G.X, G.Y, X.X, X.Y, R.X, R.Y)
    h = new(big.Int).Mod(h, q)

    s := new(big.Int).Mul(h, x)
    s = new(big.Int).Mod(new(big.Int).Add(r, s), q)
    return &Proof{R: R, S: s}, nil
}

解释：

• 输入参数：

  • sessionId：会话 ID。
  • x：签名者的私钥。
  • X：签名者的公钥（椭圆曲线点）。

• 步骤：

  1. 检查输入参数是否为 nil。
  2. 获取椭圆曲线的阶 q。
  3. 生成一个随机数 r。
  4. 计算 R = r * G，其中 G 是椭圆曲线的基点。
  5. 计算哈希值 h = SHA256(sessionId, G.X, G.Y, X.X, X.Y, R.X, R.Y) 并取模 q。
  6. 计算 s = (r + h * x) mod q。
  7. 返回 Schnorr 证明 Proof{R: R, S: s}。

VerifyWithId 函数

// VerifyWithId s*G = R + h*X
func VerifyWithId(sessionId *big.Int, pf *Proof, X *curves.ECPoint) bool {
    if pf == nil || pf.R == nil || pf.S == nil {
        return false
    }
    if !pf.R.IsOnCurve() || !X.IsOnCurve() {
        return false
    }
    q := X.Curve.Params().N
    G := curves.ScalarToPoint(X.Curve, big.NewInt(1))

    h := crypto.SHA256Int(sessionId, G.X, G.Y, X.X, X.Y, pf.R.X, pf.R.Y)
    h = new(big.Int).Mod(h, q)

    SG := curves.ScalarToPoint(X.Curve, pf.S)
    Xh := X.ScalarMult(h)
    RXh, err := pf.R.Add(Xh)
    if err != nil {
        return false
    }
    return RXh.X.Cmp(SG.X) == 0 && RXh.Y.Cmp(SG.Y) == 0
}

解释：

• 输入参数：

  • sessionId：会话 ID。
  • pf：Schnorr 证明（包含 R 和 S）。
  • X：签名者的公钥（椭圆曲线点）。

• 步骤：

  1. 检查输入参数是否为 nil，并且 R 和 X 是否在曲线上。
  2. 获取椭圆曲线的阶 q。
  3. 计算哈希值 h = SHA256(sessionId, G.X, G.Y, X.X, X.Y, pf.R.X, pf.R.Y) 并取模 q。
  4. 计算 SG = S * G。
  5. 计算 Xh = h * X。
  6. 计算 RXh = R + Xh。
  7. 比较 RXh 和 SG 是否相等，若相等则验证通过。

总结

这些函数实现了 Schnorr 签名方案的生成和验证。Prove 和 Verify 用于标准 Schnorr 签名，而 ProveWithId 和 VerifyWithId 则增加了会话 ID 以增强安全性。通过这些函数，您可以生成和验证 Schnorr 签名，确保数据的完整性和真实性。

R = r * G

椭圆曲线的基点 (G) 是椭圆曲线上的一个固定点，通常被称为生成点。它是用于生成椭圆曲线上的其他点的基础。在椭圆曲线密码学中，许多操作都是基于这个基点进行的。

在椭圆曲线数字签名算法 (ECDSA) 和 Schnorr 签名中，基点 $G$ 是一个公开的、固定的点。所有的公私钥对都是基于这个基点生成的。

代码解释

在您提供的代码中，curves.ScalarToPoint 函数用于将一个标量（整数）转换为椭圆曲线上的一个点。具体来说，它计算的是标量乘法的结果，即 R = r * G，其中 G 是基点，r 是一个随机数。

详细解释

Prove 函数中的基点使用

func Prove(x *big.Int, X *curves.ECPoint) (*Proof, error) {
    // ... 省略部分代码 ...

    r := crypto.RandomNum(q)
    R := curves.ScalarToPoint(X.Curve, r) // 这里的 R 是通过 r * G 计算得到的

    // ... 省略部分代码 ...
}

在这段代码中，curves.ScalarToPoint(X.Curve, r) 实际上计算的是 R = r * G，其中 G 是椭圆曲线的基点。

ProveWithId 函数中的基点使用

func ProveWithId(sessionId, x *big.Int, X *curves.ECPoint) (*Proof, error) {
    // ... 省略部分代码 ...

    r := crypto.RandomNum(q)
    R := curves.ScalarToPoint(X.Curve, r) // 这里的 R 是通过 r * G 计算得到的
    G := curves.ScalarToPoint(X.Curve, big.NewInt(1)) // 这里明确获取了基点 G

    // ... 省略部分代码 ...
}

在这段代码中，curves.ScalarToPoint(X.Curve, r) 同样计算的是 R = r * G。此外，G := curves.ScalarToPoint(X.Curve, big.NewInt(1)) 明确地获取了基点 $G$（通常情况下，基点 $G$ 是曲线参数的一部分，您可以通过曲线参数直接获取它）。

椭圆曲线的基点

在椭圆曲线密码学中，基点 $G$ 是一个预先定义的、固定的点，通常由标准化组织（如 NIST）选择和发布。基点 $G$ 的选择非常重要，因为它是整个椭圆曲线系统的基础。

例子

假设我们使用的是 secp256k1 椭圆曲线，基点 $G$ 的坐标为：

Gx = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

这些坐标是固定的，并且在椭圆曲线的定义中给出。

总结

• 基点 $G$：椭圆曲线上的一个固定点，通常由标准化组织定义。
• R = r * G：通过随机数 $r$ 和基点 $G$ 计算得到的点 $R$。
• 代码中的基点使用：curves.ScalarToPoint 函数用于将一个标量转换为椭圆曲线上的点，实际上是执行了标量乘法，即 r * G。

希望这些解释能帮助您更好地理解椭圆曲线基点的概念及其在代码中的使用。

椭圆 G 点

curve.Params().N 并不是基点 $G$。为了澄清这一点，让我们详细解释一下 ScalarToPoint 函数以及椭圆曲线参数中的各个部分。

ScalarToPoint 函数

// ScalarToPoint returns the point k*G on the elliptic curve
func ScalarToPoint(curve elliptic.Curve, k *big.Int) *ECPoint {
    k = new(big.Int).Mod(k, curve.Params().N)

    point := new(ECPoint)
    point.Curve = curve
    point.X, point.Y = curve.ScalarBaseMult(k.Bytes())
    return point
}

解释：

• 输入参数：

  • curve：椭圆曲线对象。
  • k：标量（整数）。

• 步骤：

  1. 将标量 k 取模曲线的阶 N。
  2. 创建一个新的 ECPoint 对象。
  3. 使用 curve.ScalarBaseMult(k.Bytes()) 计算点 k * G，其中 G 是椭圆曲线的基点。

椭圆曲线参数

椭圆曲线参数通常包含以下几个部分：

• P：素数，定义了有限域的大小。
• N：椭圆曲线的阶，即基点 $G$ 的阶。
• B：曲线的常数项。
• G：基点，曲线上的一个固定点。
• A：椭圆曲线的系数。

在 Go 的 elliptic.Curve 接口中，这些参数可以通过 curve.Params() 获取。

curve.Params().N 是什么？

• curve.Params().N 是椭圆曲线的阶，即基点 $G$ 的阶。它表示基点 $G$ 在被加上自身 $N$ 次之后会回到原点（曲线上的零点）。

基点 $G$ 是什么？

• 基点 $G$ 是椭圆曲线上的一个固定点，它是所有密钥对生成的基础。基点 $G$ 通常在椭圆曲线的定义中明确给出。

curve.ScalarBaseMult 是什么？

• curve.ScalarBaseMult(k.Bytes()) 是一个用于计算标量乘法的函数，即计算 k * G，其中 G 是基点，k 是标量。

例子

假设我们使用的是 secp256k1 椭圆曲线，以下是曲线参数的一个例子：

curve := elliptic.P256()
params := curve.Params()

fmt.Println("P:", params.P)
fmt.Println("N:", params.N)
fmt.Println("B:", params.B)
fmt.Println("Gx:", params.Gx)
fmt.Println("Gy:", params.Gy)
fmt.Println("A:", params.A)

其中：

• params.P 是素数 P。
• params.N 是椭圆曲线的阶 N。
• params.B 是曲线的常数项 B。
• params.Gx 和 params.Gy 是基点 G 的坐标。
• params.A 是椭圆曲线的系数 A。

总结

• curve.Params().N：是椭圆曲线的阶，不是基点 $G$。
• 基点 $G$：是一个固定的椭圆曲线点，通常在曲线参数中定义。
• ScalarToPoint 函数：通过 curve.ScalarBaseMult(k.Bytes()) 计算点 k * G，其中 G 是基点。

希望这些解释能帮助您更好地理解 ScalarToPoint 函数以及椭圆曲线参数中的各个部分。