Feldman's VSS proof 推导 🔥

在 Feldman 分布式密钥生成（DKG）方案中，推导公式涉及多项式生成、密钥份额计算和验证者生成。以下是详细的推导过程：

1. 多项式生成

每个参与方 $P_i$ 生成一个随机的多项式 $f_i(x)$，其度数为 $t-1$，其中 $t$ 是阈值。多项式的形式为：

$$f_i(x) = a_{i,0} + a_{i,1}x + a_{i,2}x^2 + \cdots + a_{i,t-1}x^{t-1}$$

• $a_{i,0}$ 是常数项，通常是秘密共享的值。
• $a_{i,1}, a_{i,2}, \ldots, a_{i,t-1}$ 是随机系数。

2. 密钥份额计算

每个参与方 $P_i$ 使用其生成的多项式 $f_i(x)$ 计算密钥份额 $s_{i,j}$，其中 $j$ 是其他参与方的编号：

$$s_{i,j} = f_i(j)$$

即：

$$s_{i,j} = a_{i,0} + a_{i,1}j + a_{i,2}j^2 + \cdots + a_{i,t-1}j^{t-1}$$

这些密钥份额是分发给其他参与方的。例如，参与方 $P_1$ 会计算 $s_{1,2} = f_1(2)$、$s_{1,3} = f_1(3)$ 等，并分别发送给 $P_2$ 和 $P_3$。

3. 验证者生成

为了验证密钥份额的正确性，每个参与方 $P_i$ 生成一组验证者 $V_{i,k}$，这些验证者是多项式系数的公开值。通常使用一个生成元 $g$ 来生成验证者：

$$V_{i,k} = g^{a_{i,k}}$$

其中 $k$ 是多项式的项数索引（从 0 到 $t-1$）。这些验证者是公开的，可以被所有参与方用来验证密钥份额。

4. 验证密钥份额

每个参与方在接收到其他参与方的密钥份额后，可以使用验证者来验证这些密钥份额的正确性。验证步骤通常是检查如下等式是否成立：

$$g^{s_{i,j}} \stackrel{?}{=} \prod_{k=0}^{t-1} (V_{i,k})^{j^k}$$

其中，左边是密钥份额 $s_{i,j}$ 的生成元表示，右边是验证者的组合。

推导验证公式

我们需要验证密钥份额 $s_{i,j}$ 是否正确，即验证：

$$g^{s_{i,j}} \stackrel{?}{=} \prod_{k=0}^{t-1} (V_{i,k})^{j^k}$$

首先，考虑密钥份额 $s_{i,j}$ 的定义：

$$s_{i,j} = a_{i,0} + a_{i,1}j + a_{i,2}j^2 + \cdots + a_{i,t-1}j^{t-1}$$

将其代入左边的生成元表示：

$$g^{s_{i,j}} = g^{a_{i,0} + a_{i,1}j + a_{i,2}j^2 + \cdots + a_{i,t-1}j^{t-1}}$$

根据指数的加法性质，我们可以将其分解：

$$g^{s_{i,j}} = g^{a_{i,0}} \cdot g^{a_{i,1}j} \cdot g^{a_{i,2}j^2} \cdots g^{a_{i,t-1}j^{t-1}}$$

再考虑验证者 $V_{i,k} = g^{a_{i,k}}$，我们可以得到：

$$(V_{i,0})^{j^0} = (g^{a_{i,0}})^{1} = g^{a_{i,0}}$$ $$(V_{i,1})^{j^1} = (g^{a_{i,1}})^{j} = g^{a_{i,1}j}$$ $$(V_{i,2})^{j^2} = (g^{a_{i,2}})^{j^2} = g^{a_{i,2}j^2}$$ $$\cdots$$ $$(V_{i,t-1})^{j^{t-1}} = (g^{a_{i,t-1}})^{j^{t-1}} = g^{a_{i,t-1}j^{t-1}}$$

将这些验证者的组合相乘：

$$\prod_{k=0}^{t-1} (V_{i,k})^{j^k} = g^{a_{i,0}} \cdot g^{a_{i,1}j} \cdot g^{a_{i,2}j^2} \cdots g^{a_{i,t-1}j^{t-1}}$$

我们可以看到，这右边正好等于 $g^{s_{i,j}}$。因此，验证公式成立：

$$g^{s_{i,j}} = \prod_{k=0}^{t-1} (V_{i,k})^{j^k}$$

总结

通过以上推导，我们可以看到 Feldman DKG 方案中的验证公式是如何得出的。每个参与方生成的多项式用于计算密钥份额，而验证者是多项式系数的生成元表示。通过验证公式，可以确保密钥份额的正确性，保证密钥生成和分发的安全性和可靠性。

参与者将分享和分享的证明，一起发送到其他参与者，其他参与者，来执行计算，验证，分享和分享的证明关系成立

是的，你理解得很正确。在分布式密钥生成（DKG）协议中，每个参与者确实需要验证其他参与者发送的分享。这是通过验证分享和其伴生证明者之间的数学关系来实现的。

验证过程详细说明

在 DKG 协议中，每个参与者会生成一个秘密分享，并将该分享和相关的证明一起发送给其他参与者。其他参与者接收到这些信息后，会进行验证以确保分享的正确性和完整性。

具体来说，验证过程包括以下几个步骤：

1. 接收分享和证明：每个参与者接收其他参与者发送的秘密分享和相关的证明。
2. 验证承诺：使用哈希承诺技术验证消息的完整性，确保消息没有被篡改。
3. 反序列化验证者：将消息中的验证者反序列化为椭圆曲线上的点。
4. 验证秘密分享：使用 Feldman VSS 验证每个秘密分享的正确性。
5. 验证零知识证明：使用 Schnorr 零知识证明验证发送者的身份和分享的正确性。

代码中的关键部分

接收分享和证明

在代码中，接收分享和证明的部分是通过消息 msgs 实现的：

for _, msg := range msgs {
    // 检查消息是否发送到当前设备
    if msg.To != info.DeviceNumber {
        return nil, fmt.Errorf("message sending error")
    }
    var content tss.KeyStep2Data
    // 反序列化消息数据
    err := json.Unmarshal([]byte(msg.Data), &content)
    if err != nil {
        return nil, err
    }
    // 创建哈希承诺
    hashCommit := commitment.HashCommitment{}
    hashCommit.C = info.commitmentMap[msg.From]
    hashCommit.Msg = *content.Witness
    // 打开承诺并验证
    ok, D := hashCommit.Open()
    if !ok {
        return nil, fmt.Errorf("commitment DeCommit fail")
    }

验证承诺

    // 打开承诺并验证
    ok, D := hashCommit.Open()
    if !ok {
        return nil, fmt.Errorf("commitment DeCommit fail")
    }

这部分代码使用哈希承诺技术验证消息的完整性。承诺确保消息没有被篡改。

反序列化验证者

    // 反序列化验证者
    verifiers[msg.From], err = dkg.UnmarshalVerifiers(curve, D, info.Threshold)

这部分代码将消息中的验证者反序列化为椭圆曲线上的点。

验证秘密分享

    // 验证秘密份额
    if ok, err := feldman.Verify(content.Share, verifiers[msg.From]); !ok {
        if err != nil {
            return nil, err
        } else {
            return nil, fmt.Errorf("invalid share for participant")
        }
    }

这部分代码使用 Feldman VSS 验证消息中的秘密分享。通过验证者，可以确保秘密分享是有效的。

验证零知识证明

    // 验证 Schnorr 证明
    ujPoint := verifiers[msg.From][0]

    // 过滤 0*G
    if ujPoint.X.Cmp(big.NewInt(0)) == 0 || ujPoint.Y.Cmp(big.NewInt(0)) == 0 {
        continue
    }
    point, err := curves.NewECPoint(curve, ujPoint.X, ujPoint.Y)
    if err != nil {
        return nil, err
    }
    // 验证零知识证明
    verify := schnorr.Verify(content.Proof, point)
    if (!verify) {
        return nil, fmt.Errorf("schnorr verify fail")
    }
}

这部分代码使用 Schnorr 零知识证明验证发送者的身份和分享的正确性。这进一步确保了消息的安全性和完整性。

总结

在 DKG 协议中，每个参与者确实需要验证其他参与者发送的分享。这是通过验证分享和其伴生证明者之间的数学关系来实现的。具体步骤包括接收分享和证明、验证承诺、反序列化验证者、验证秘密分享和验证零知识证明。这些步骤共同确保了分布式密钥生成协议的安全性和正确性。

示例

好的，我们通过一个具体的例子来解释 Feldman 可验证秘密共享（VSS）方案。假设我们有一个秘密$s = 2$，并且我们希望生成 3 个共享，其中任意 2 个共享可以恢复秘密。

1. 生成共享

首先，我们使用 Shamir 秘密共享方案生成共享。

1. 选择参数：

   • 秘密：$s = 2$
   • 阈值：$t = 2$（需要至少 2 个共享来恢复秘密）
   • 生成一个随机的一次多项式：$f(x) = a_0 + a_1 x$
   • 其中，$a_0 = s = 2$，$a_1$是一个随机选择的系数。

2. 生成多项式：

   • 假设我们选择$a_1 = 3$，那么多项式为： $$f(x) = 2 + 3x$$

3. 生成共享：

   • 选择 3 个不同的$x$值，通常可以简单选择 1, 2, 3。
   • 计算每个$x$对应的$y$值： $$f(1) = 2 + 3 \times 1 = 5$$ $$f(2) = 2 + 3 \times 2 = 8$$ $$f(3) = 2 + 3 \times 3 = 11$$
   • 因此，生成的共享为： $$(1, 5), (2, 8), (3, 11)$$

2. 生成公开验证者

在 Feldman VSS 中，我们还需要生成公开验证者以便验证每个共享的有效性。

1. 选择生成元和素数：

   • 选择一个生成元$g$和一个大素数$q$。
   • 假设选择$g = 2$和$q = 17$（这些值在实际应用中会更大）。

2. 计算验证者：

   • 计算多项式系数的承诺： $$g^{a_0} = g^2 \mod q = 2^2 \mod 17 = 4$$ $$g^{a_1} = g^3 \mod q = 2^3 \mod 17 = 8$$
   • 验证者为： $$V_0 = g^{a_0} = 4$$ $$V_1 = g^{a_1} = 8$$

3. 验证共享

现在，每个接收者可以使用这些验证者来验证共享的有效性。

1. 验证共享 (1, 5)：

   • 计算左侧（LHS）： $$LHS = g^{y_1} \mod q = 2^5 \mod 17 = 32 \mod 17 = 15$$
   • 计算右侧（RHS）： $$RHS = V_0 \cdot V_1^1 \mod q = 4 \cdot 8^1 \mod 17 = 4 \cdot 8 \mod 17 = 32 \mod 17 = 15$$
   • 因为 $LHS = RHS$，共享 (1, 5) 是有效的。

2. 验证共享 (2, 8)：

   • 计算左侧（LHS）： $$LHS = g^{y_2} \mod q = 2^8 \mod 17 = 256 \mod 17 = 1$$
   • 计算右侧（RHS）： $$RHS = V_0 \cdot V_1^2 \mod q = 4 \cdot 8^2 \mod 17 = 4 \cdot 64 \mod 17 = 256 \mod 17 = 1$$
   • 因为 $LHS = RHS$，共享 (2, 8) 是有效的。

3. 验证共享 (3, 11)：

   • 计算左侧（LHS）： $$LHS = g^{y_3} \mod q = 2^{11} \mod 17 = 2048 \mod 17 = 14$$
   • 计算右侧（RHS）： $$RHS = V_0 \cdot V_1^3 \mod q = 4 \cdot 8^3 \mod 17 = 4 \cdot 512 \mod 17 = 2048 \mod 17 = 14$$
   • 因为 $LHS = RHS$，共享 (3, 11) 是有效的。

通过这些步骤，Feldman VSS 方案确保每个接收者可以独立验证其共享的有效性，而无需信任分享者。这提高了整个秘密共享方案的安全性和可靠性。

一组验证者，可以验证多个共享

是的，一组验证者可以验证多个共享。这是因为验证者是基于秘密生成的多项式的系数计算出来的，而这些系数在所有共享中都是一致的。因此，所有共享都可以使用同一组验证者来验证其有效性。

让我们更详细地解释这个过程。

1. 生成共享

假设我们有一个秘密 $s = 2$，并且我们希望生成 3 个共享，其中任意 2 个共享可以恢复秘密。

1. 选择参数：

   • 秘密：$s = 2$
   • 阈值：$t = 2$（需要至少 2 个共享来恢复秘密）
   • 生成一个随机的一次多项式：$f(x) = a_0 + a_1 x$
   • 其中，$a_0 = s = 2$，$a_1$是一个随机选择的系数。

2. 生成多项式：

   • 假设我们选择 $a_1 = 3$，那么多项式为： $$f(x) = 2 + 3x$$

3. 生成共享：

   • 选择 3 个不同的 $x$ 值，通常可以简单选择 1, 2, 3。
   • 计算每个 $x$ 对应的 $y$ 值： $$f(1) = 2 + 3 \times 1 = 5$$ $$f(2) = 2 + 3 \times 2 = 8$$ $$f(3) = 2 + 3 \times 3 = 11$$
   • 因此，生成的共享为： $$(1, 5), (2, 8), (3, 11)$$

2. 生成公开验证者

在 Feldman VSS 中，我们还需要生成公开验证者以便验证每个共享的有效性。

1. 选择生成元和素数：

   • 选择一个生成元 $g$ 和一个大素数 $q$。
   • 假设选择 $g = 2$ 和 $q = 17$（这些值在实际应用中会更大）。

2. 计算验证者：

   • 计算多项式系数的承诺： $$g^{a_0} = g^2 \mod q = 2^2 \mod 17 = 4$$ $$g^{a_1} = g^3 \mod q = 2^3 \mod 17 = 8$$
   • 验证者为： $$V_0 = g^{a_0} = 4$$ $$V_1 = g^{a_1} = 8$$

3. 验证共享

现在，每个接收者可以使用这些验证者来验证共享的有效性。

1. 验证共享 (1, 5)：

   • 计算左侧（LHS）： $$LHS = g^{y_1} \mod q = 2^5 \mod 17 = 32 \mod 17 = 15$$
   • 计算右侧（RHS）： $$RHS = V_0 \cdot V_1^1 \mod q = 4 \cdot 8^1 \mod 17 = 4 \cdot 8 \mod 17 = 32 \mod 17 = 15$$
   • 因为 $LHS = RHS$，共享 (1, 5) 是有效的。

2. 验证共享 (2, 8)：

   • 计算左侧（LHS）： $$LHS = g^{y_2} \mod q = 2^8 \mod 17 = 256 \mod 17 = 1$$
   • 计算右侧（RHS）： $$RHS = V_0 \cdot V_1^2 \mod q = 4 \cdot 8^2 \mod 17 = 4 \cdot 64 \mod 17 = 256 \mod 17 = 1$$
   • 因为 $LHS = RHS$，共享 (2, 8) 是有效的。

3. 验证共享 (3, 11)：

   • 计算左侧（LHS）： $$LHS = g^{y_3} \mod q = 2^{11} \mod 17 = 2048 \mod 17 = 14$$
   • 计算右侧（RHS）： $$RHS = V_0 \cdot V_1^3 \mod q = 4 \cdot 8^3 \mod 17 = 4 \cdot 512 \mod 17 = 2048 \mod 17 = 14$$
   • 因为 $LHS = RHS$，共享 (3, 11) 是有效的。

结论

通过这些步骤，我们可以看到，尽管每个共享的 $x$ 和 $y$ 值不同，但它们都可以使用同一组验证者 $V_0$ 和 $V_1$ 来验证其有效性。这是因为这些验证者是基于生成共享的多项式的系数计算出来的，而这些系数在所有共享中都是一致的。因此，一组验证者可以验证多个共享。