Feldman's VSS

Feldman's VSS 私钥份额计算，公钥份额计算，验证

当然，以下是使用 LaTeX 来详细描述 Feldman's Verifiable Secret Sharing (VSS) 的私钥份额计算、公钥份额计算和验证过程。

私钥份额计算

1. 秘密选择：

   • 秘密分享者选择一个秘密值 $s$，通常是一个大整数。

2. 多项式生成：

   • 选择一个度为 $t-1$ 的随机多项式 $f(x) = a*0 + a_1x + a_2x^2 + \cdots + a*{t-1}x^{t-1}$，其中 $a*0 = s$，$a_1, \ldots, a*{t-1}$ 是随机系数。

3. 计算份额：

   • 对于每个参与者 $i$，计算私钥份额 $s_i = f(i)$。

公钥份额计算

1. 生成验证者：

   • 对于多项式 $f(x)$ 的每个系数 $a_j$，计算 $A_j = g^{a_j}$，其中 $g$ 是生成元。
   • 这些 $A_j$ 值称为验证者，它们用于验证私钥份额的正确性。

2. 计算公钥份额：

   • 对于每个参与者 $i$，计算公钥份额 $P*i$，其计算方式为： $$P_i = g^{s_i} = g^{f(i)} = A_0 \cdot A_1^i \cdot A_2^{i^2} \cdots A*{t-1}^{i^{t-1}}$$

验证

验证过程确保每个参与者收到的私钥份额是正确的，即它们确实是由秘密分享者生成的多项式 $f(x)$ 计算得到的。

1. 接收私钥份额：

   • 每个参与者接收到他们的私钥份额 $s_i$ 和验证者 $A_j$。

2. 计算公钥份额：

   • 参与者使用验证者 $A*j$ 计算公钥份额 $P_i$： $$P_i = A_0 \cdot A_1^i \cdot A_2^{i^2} \cdots A*{t-1}^{i^{t-1}}$$

3. 验证私钥份额：

   • 验证者验证私钥份额 $s_i$ 的正确性，通过检查： $$g^{s_i} \stackrel{?}{=} P_i$$
   • 如果等式成立，说明私钥份额 $s_i$ 是正确的。

Feldman's Verifiable Secret Sharing (VSS) 是一种密码学协议，用于将一个秘密分割成多个部分（称为“份额”），并分发给一组参与者，同时允许这些参与者验证他们收到的份额的有效性。VSS 的主要目的是确保秘密的安全性和完整性，即使某些参与者可能是恶意的。

基本概念

1. 秘密分享：

   • 秘密分享是一种将秘密分割成多个份额的方法，这些份额被分发给一组参与者。只有当足够多的份额被收集时，秘密才能被重构。

2. 门限方案：

   • 在一个门限方案中，只有当至少 t 个参与者（其中 t 是阈值）协同工作时，才能重构秘密。Feldman's VSS 通常基于 Shamir 的秘密分享方案。

3. 可验证性：

   • 可验证性是指参与者可以验证他们收到的份额是否有效，这样可以防止恶意的秘密分发者发送无效的份额。

Feldman's VSS 协议

Feldman's VSS 协议基于 Shamir 的秘密分享方案，并通过使用同态加密（如椭圆曲线加密）来实现份额的可验证性。

1. 初始化

• 选择参数：

  • 选择一个大素数 $p$ 和一个生成元 $g$。
  • 秘密 $s$ 是一个在 $Z_p$ 中的元素。

• 生成多项式：

  • 选择一个随机的 $t-1$ 次多项式 $f(x) = s + a*1 x + a_2 x^2 + \cdots + a*{t-1} x^{t-1}$，其中 $s$ 是常数项，$a*1, a_2, \ldots, a*{t-1}$ 是随机系数。

2. 分发份额

• 计算份额：

  • 计算每个参与者 $i$ 的份额 $s_i = f(i)$。

• 计算承诺：

  • 计算并公布承诺 $C_j = g^{a_j}$ 对于 $j = 0, 1, \ldots, t-1$，其中 $a_0 = s$。

• 分发份额：

  • 将份额 $s_i$ 发送给每个参与者 $i$。

3. 验证份额

• 验证：
  • 每个参与者 $i$ 验证其份额 $s*i$ 是否满足 $g^{s_i} \stackrel{?}{=} \prod*{j=0}^{t-1} C_j^{i^j}$。
  • 如果等式成立，份额是有效的；否则，份额是无效的。

示例代码（Go 语言）

以下是一个简单的 Feldman's VSS 协议的 Go 语言实现示例：

package main

import (
	"crypto/rand"
	"fmt"
	"math/big"
)

var p, _ = new(big.Int).SetString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16) // 大素数
var g = big.NewInt(2) // 生成元

func main() {
	// 秘密
	s := big.NewInt(12345)

	// 阈值
	t := 3

	// 参与者数量
	n := 5

	// 生成多项式系数
	coefficients := make([]*big.Int, t)
	coefficients[0] = s
	for i := 1; i < t; i++ {
		coefficients[i], _ = rand.Int(rand.Reader, p)
	}

	// 计算承诺
	commitments := make([]*big.Int, t)
	for j := 0; j < t; j++ {
		commitments[j] = new(big.Int).Exp(g, coefficients[j], p)
	}

	// 计算并分发份额
	shares := make([]*big.Int, n)
	for i := 1; i <= n; i++ {
		shares[i-1] = calculateShare(i, coefficients)
		fmt.Printf("Participant %d's share: %s\n", i, shares[i-1].String())
	}

	// 验证份额
	for i := 1; i <= n; i++ {
		if verifyShare(i, shares[i-1], commitments) {
			fmt.Printf("Participant %d's share is valid.\n", i)
		} else {
			fmt.Printf("Participant %d's share is invalid.\n", i)
		}
	}
}

func calculateShare(x int, coefficients []*big.Int) *big.Int {
	result := big.NewInt(0)
	for j := len(coefficients) - 1; j >= 0; j-- {
		result.Mul(result, big.NewInt(int64(x)))
		result.Add(result, coefficients[j])
		result.Mod(result, p)
	}
	return result
}

func verifyShare(i int, share *big.Int, commitments []*big.Int) bool {
	left := new(big.Int).Exp(g, share, p)
	right := big.NewInt(1)
	x := big.NewInt(int64(i))
	for j := 0; j < len(commitments); j++ {
		tmp := new(big.Int).Exp(commitments[j], new(big.Int).Exp(x, big.NewInt(int64(j)), p), p)
		right.Mul(right, tmp)
		right.Mod(right, p)
	}
	return left.Cmp(right) == 0
}

结论

Feldman's VSS 提供了一种安全和可验证的方法来分享秘密，确保只有在足够多的参与者协同工作时才能重构秘密，并且参与者可以验证他们收到的份额的有效性。该协议广泛应用于分布式系统和密码学应用中，如门限签名和分布式密钥生成。

code Polynomial

package vss

import (
	"crypto/elliptic"
	"crypto/rand"
	"fmt"
	"math/big"
)

type Polynomial struct {
	Coefficients []*big.Int // polynomial coefficient, eg: [a0, a1, a2 ...]
	QMod         *big.Int
}

// secret share
type Share struct {
	Id *big.Int // x-coordinate
	Y  *big.Int // y-coordinate
}

// InitPolynomial init Coefficients [a0, a1....at] t=degree
func InitPolynomial(curve elliptic.Curve, secret *big.Int, degree int) (*Polynomial, error) {
	if degree < 1 {
		return nil, fmt.Errorf("degree must be at least 1")
	}
	q := curve.Params().N
	Coefficients := make([]*big.Int, degree+1)
	Coefficients[0] = secret
	for i := 1; i <= degree; i++ {
		r, err := rand.Prime(rand.Reader, q.BitLen())
		if err != nil {
			return nil, err
		}
		Coefficients[i] = r // random generation coefficient
	}
	return &Polynomial{
		Coefficients: Coefficients,
		QMod:         q,
	}, nil
}

// EvaluatePolynomial a polynomial with coefficients such that:
// EvaluatePolynomial(x):
// 		returns a + bx + cx^2 + dx^3
func (p *Polynomial) EvaluatePolynomial(x *big.Int) *Share {
	result := new(big.Int).Set(p.Coefficients[0])
	tmp := big.NewInt(1)
	for i := 1; i <= len(p.Coefficients)-1; i++ {
		tmp = new(big.Int).Mul(tmp, x)
		aiXi := new(big.Int).Mul(p.Coefficients[i], tmp)
		result = result.Add(result, aiXi)
	}
	result = new(big.Int).Mod(result, p.QMod)
	return &Share{
		Id: x,
		Y:  result,
	}
}

// RecoverSecret recover secret key
func RecoverSecret(curve elliptic.Curve, pointList []*Share) *big.Int {
	q := curve.Params().N
	xList := make([]*big.Int, len(pointList))
	for i, point := range pointList {
		xList[i] = point.Id
	}
	secret := big.NewInt(0)
	for _, point := range pointList {
		wi := CalLagrangian(curve, point.Id, point.Y, xList)
		secret = secret.Add(secret, wi)
	}
	secret = new(big.Int).Mod(secret, q)
	return secret
}

// CalLagrangian lagrangian interpolation wi, x = sum(wi)
func CalLagrangian(curve elliptic.Curve, x, y *big.Int, xList []*big.Int) *big.Int {
	q := curve.Params().N
	wi := new(big.Int).SetBytes(y.Bytes())
	// wi = y*mul(xj/(xj-xi))
	for i := 0; i < len(xList); i++ {
		xj := xList[i]
		if x.Cmp(xj) == 0 {
			continue
		}
		coef := new(big.Int).Sub(xj, x)
		coef.ModInverse(coef, q)
		coef.Mul(xj, coef)
		wi.Mul(wi, coef)
	}
	wi = new(big.Int).Mod(wi, q)
	return wi
}

这段代码实现了基于椭圆曲线的秘密共享方案，使用多项式插值来分发和恢复秘密。以下是对每个部分的详细解释：

Polynomial 结构体

type Polynomial struct {
	Coefficients []*big.Int // 多项式系数，例如: [a0, a1, a2 ...]
	QMod         *big.Int    // 模数 q
}

• Coefficients：存储多项式的系数。
• QMod：用于模运算的素数 $q$，通常是椭圆曲线的阶数。

Share 结构体

type Share struct {
	Id *big.Int // x 坐标
	Y  *big.Int // y 坐标
}

• Id：分享的 x 坐标。
• Y：分享的 y 坐标。

初始化多项式

func InitPolynomial(curve elliptic.Curve, secret *big.Int, degree int) (*Polynomial, error) {
	if degree < 1 {
		return nil, fmt.Errorf("degree must be at least 1")
	}
	q := curve.Params().N
	Coefficients := make([]*big.Int, degree+1)
	Coefficients[0] = secret
	for i := 1; i <= degree; i++ {
		r, err := rand.Prime(rand.Reader, q.BitLen())
		if err != nil {
			return nil, err
		}
		Coefficients[i] = r // 随机生成系数
	}
	return &Polynomial{
		Coefficients: Coefficients,
		QMod:         q,
	}, nil
}

• curve：椭圆曲线。
• secret：秘密（多项式的常数项）。
• degree：多项式的度。

评估多项式

func (p *Polynomial) EvaluatePolynomial(x *big.Int) *Share {
	result := new(big.Int).Set(p.Coefficients[0])
	tmp := big.NewInt(1)
	for i := 1; i <= len(p.Coefficients)-1; i++ {
		tmp = new(big.Int).Mul(tmp, x)
		aiXi := new(big.Int).Mul(p.Coefficients[i], tmp)
		result = result.Add(result, aiXi)
	}
	result = new(big.Int).Mod(result, p.QMod)
	return &Share{
		Id: x,
		Y:  result,
	}
}

• EvaluatePolynomial：计算给定 $x$ 值处的多项式值。

恢复秘密

func RecoverSecret(curve elliptic.Curve, pointList []*Share) *big.Int {
	q := curve.Params().N
	xList := make([]*big.Int, len(pointList))
	for i, point := range pointList {
		xList[i] = point.Id
	}
	secret := big.NewInt(0)
	for _, point := range pointList {
		wi := CalLagrangian(curve, point.Id, point.Y, xList)
		secret = secret.Add(secret, wi)
	}
	secret = new(big.Int).Mod(secret, q)
	return secret
}

• RecoverSecret：使用拉格朗日插值法从分享中恢复秘密。

计算拉格朗日插值

func CalLagrangian(curve elliptic.Curve, x, y *big.Int, xList []*big.Int) *big.Int {
	q := curve.Params().N
	wi := new(big.Int).SetBytes(y.Bytes())
	for i := 0; i < len(xList); i++ {
		xj := xList[i]
		if x.Cmp(xj) == 0 {
			continue
		}
		coef := new(big.Int).Sub(xj, x)
		coef.ModInverse(coef, q)
		coef.Mul(xj, coef)
		wi.Mul(wi, coef)
	}
	wi = new(big.Int).Mod(wi, q)
	return wi
}

• CalLagrangian：计算拉格朗日插值基函数。

示例用法

假设我们想要分发一个秘密，并从分享中恢复它：

func main() {
	// 使用 P-256 椭圆曲线
	curve := elliptic.P256()

	// 初始化多项式，秘密为 42，度为 2
	secret := big.NewInt(42)
	polynomial, err := InitPolynomial(curve, secret, 2)
	if err != nil {
		fmt.Println("Error initializing polynomial:", err)
		return
	}

	// 生成 5 份分享
	shares := make([]*Share, 5)
	for i := 1; i <= 5; i++ {
		shares[i-1] = polynomial.EvaluatePolynomial(big.NewInt(int64(i)))
		fmt.Printf("Share %d: (%s, %s)\n", i, shares[i-1].Id.String(), shares[i-1].Y.String())
	}

	// 使用任意 3 份分享来恢复秘密
	recoveredSecret := RecoverSecret(curve, shares[:3])
	fmt.Printf("Recovered Secret: %s\n", recoveredSecret.String())
}

解释

1. 初始化多项式：

   • 使用 InitPolynomial 函数初始化一个多项式，秘密为 42，度为 2。

2. 生成分享：

   • 使用 EvaluatePolynomial 函数生成 5 份分享。

3. 恢复秘密：

   • 使用 RecoverSecret 函数，从任意 3 份分享中恢复秘密。

这段代码展示了如何使用拉格朗日插值法进行秘密共享和恢复，适用于基于椭圆曲线的密码学应用。

code Feldman

package vss

import (
	"crypto/elliptic"
	"fmt"
	"math/big"

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

//  verifiable secret sharing scheme
type Feldman struct {
	threshold int // power of polynomial add one
	limit     int //
	curve     elliptic.Curve
}

// NewFeldman
func NewFeldman(threshold, limit int, curve elliptic.Curve) (*Feldman, error) {
	if threshold < 2 {
		return nil, fmt.Errorf("threshold least than 2")
	}
	if limit < threshold {
		return nil, fmt.Errorf("NewFeldman error, limit less than threshold")
	}
	return &Feldman{threshold, limit, curve}, nil
}

// Evaluate return verifiers and shares
func (fm *Feldman) Evaluate(secret *big.Int) ([]*curves.ECPoint, []*Share, error) {
	poly, err := InitPolynomial(fm.curve, secret, fm.threshold-1)
	if err != nil {
		return nil, nil, err
	}
	shares := make([]*Share, fm.limit)
	for i := 1; i <= fm.limit; i++ {
		shares[i-1] = poly.EvaluatePolynomial(big.NewInt(int64(i)))
	}
	verifiers := make([]*curves.ECPoint, len(poly.Coefficients))
	for i, c := range poly.Coefficients {
		verifiers[i] = curves.ScalarToPoint(fm.curve, c)
	}
	return verifiers, shares, nil
}

// Verify check feldman verifiable secret sharing
func (fm *Feldman) Verify(share *Share, verifiers []*curves.ECPoint) (bool, error) {
	if len(verifiers) < fm.threshold {
		return false, fmt.Errorf("feldman verify number error")
	}
	lhs := curves.ScalarToPoint(fm.curve, share.Y)

	var err error
	x := big.NewInt(1)
	rhs := verifiers[0]
	for j := 1; j < len(verifiers); j++ {
		x = new(big.Int).Mul(x, share.Id)
		c := verifiers[j].ScalarMult(x)
		rhs, err = rhs.Add(c)
		if err != nil {
			return false, err
		}
	}
	return lhs.Equals(rhs), nil
}

这段代码实现了基于 Feldman 可验证秘密共享方案（Verifiable Secret Sharing, VSS）。Feldman VSS 是一种在秘密共享中添加验证机制的方法，允许参与者验证每个分享的正确性。

Feldman 结构体

type Feldman struct {
	threshold int           // 多项式的度加一
	limit     int           // 分享的数量
	curve     elliptic.Curve // 使用的椭圆曲线
}

• threshold：秘密共享的门限值，即需要多少份分享才能恢复秘密。
• limit：生成的分享数量。
• curve：使用的椭圆曲线。

初始化 Feldman 结构体

func NewFeldman(threshold, limit int, curve elliptic.Curve) (*Feldman, error) {
	if threshold < 2 {
		return nil, fmt.Errorf("threshold least than 2")
	}
	if limit < threshold {
		return nil, fmt.Errorf("NewFeldman error, limit less than threshold")
	}
	return &Feldman{threshold, limit, curve}, nil
}

• threshold：门限值，至少为 2。
• limit：分享的数量，必须大于或等于门限值。
• curve：使用的椭圆曲线。

生成分享和验证信息

func (fm *Feldman) Evaluate(secret *big.Int) ([]*curves.ECPoint, []*Share, error) {
	poly, err := InitPolynomial(fm.curve, secret, fm.threshold-1)
	if err != nil {
		return nil, nil, err
	}
	shares := make([]*Share, fm.limit)
	for i := 1; i <= fm.limit; i++ {
		shares[i-1] = poly.EvaluatePolynomial(big.NewInt(int64(i)))
	}
	verifiers := make([]*curves.ECPoint, len(poly.Coefficients))
	for i, c := range poly.Coefficients {
		verifiers[i] = curves.ScalarToPoint(fm.curve, c)
	}
	return verifiers, shares, nil
}

• Evaluate：生成分享和验证信息。
  • secret：秘密。
  • 返回值：验证信息（verifiers）和分享（shares）。

验证分享的有效性

func (fm *Feldman) Verify(share *Share, verifiers []*curves.ECPoint) (bool, error) {
	if len(verifiers) < fm.threshold {
		return false, fmt.Errorf("feldman verify number error")
	}
	lhs := curves.ScalarToPoint(fm.curve, share.Y)

	var err error
	x := big.NewInt(1)
	rhs := verifiers[0]
	for j := 1; j < len(verifiers); j++ {
		x = new(big.Int).Mul(x, share.Id)
		c := verifiers[j].ScalarMult(x)
		rhs, err = rhs.Add(c)
		if err != nil {
			return false, err
		}
	}
	return lhs.Equals(rhs), nil
}

• Verify：验证某个分享的有效性。
  • share：需要验证的分享。
  • verifiers：用于验证的验证信息。
  • 返回值：布尔值表示验证是否通过。

解释

1. 初始化 Feldman 结构体：

   • NewFeldman 函数用于初始化一个 Feldman 结构体，确保门限值和分享数量的合理性。

2. 生成分享和验证信息：

   • Evaluate 函数生成分享和验证信息。
   • 使用 InitPolynomial 初始化多项式，并计算多项式在不同点的值生成分享。
   • 使用 curves.ScalarToPoint 将多项式的系数转换为椭圆曲线上的点，生成验证信息。

3. 验证分享的有效性：

   • Verify 函数验证某个分享的有效性。
   • 将分享的 y 值转换为椭圆曲线上的点 lhs。
   • 计算验证信息的线性组合 rhs，检查 lhs 和 rhs 是否相等。

示例用法

假设我们想要生成秘密的分享并验证它们：

func main() {
	// 使用 P-256 椭圆曲线
	curve := elliptic.P256()

	// 初始化 Feldman 结构体，门限值为 3，分享数量为 5
	feldman, err := NewFeldman(3, 5, curve)
	if err != nil {
		fmt.Println("Error initializing Feldman:", err)
		return
	}

	// 秘密为 42
	secret := big.NewInt(42)

	// 生成分享和验证信息
	verifiers, shares, err := feldman.Evaluate(secret)
	if err != nil {
		fmt.Println("Error generating shares:", err)
		return
	}

	// 打印分享和验证信息
	for i, share := range shares {
		fmt.Printf("Share %d: (%s, %s)\n", i+1, share.Id.String(), share.Y.String())
	}

	for i, verifier := range verifiers {
		fmt.Printf("Verifier %d: (%s, %s)\n", i, verifier.X.String(), verifier.Y.String())
	}

	// 验证分享的有效性
	for i, share := range shares {
		valid, err := feldman.Verify(share, verifiers)
		if err != nil {
			fmt.Printf("Error verifying share %d: %s\n", i+1, err)
			continue
		}
		fmt.Printf("Share %d valid: %t\n", i+1, valid)
	}
}

解释

1. 初始化 Feldman 结构体：

   • 使用 NewFeldman 函数初始化一个 Feldman 结构体，门限值为 3，分享数量为 5。

2. 生成分享和验证信息：

   • 使用 Evaluate 函数生成秘密的分享和验证信息。

3. 验证分享的有效性：

   • 使用 Verify 函数验证每个分享的有效性。

通过这种方式，我们可以确保每个分享的正确性，并且只有在达到门限值时才能恢复秘密。