Zig语言实现的社会主义百万富翁问题

Zig 中的社会主义百万富翁问题

姚期智出生于 1946 年，目前是清华大学的院长 [ here]。他实际上获得了两个博士学位。第一个是 1972 年在哈佛大学物理学专业完成的，第二个是 1975 年在伊利诺伊大学计算机科学专业完成的。之后，他在斯坦福大学和加州大学伯克利分校工作。他的第一个主要贡献是姚氏测试 [1]，其中一系列单词如果无法与随机生成区分开来，则可以通过他的测试。

总的来说，他是一位世界级的学者，并且是一位归化的美国公民，但在 2014 年，他决定搬回中国，以加强他出生国家的研究。2000 年，他被授予 ACM 图灵奖（相当于计算机科学领域的诺贝尔奖）[ here]:

在姚 1982 年的论文 [2] 中，他概述了一个问题，即寻找一种方法让两位百万富翁找出他们中谁的钱最多，而且他们不信任任何人来确定这一点，并且他们不透露他们有多少钱：

它是多方计算 (MPC) 和零知识证明的开始。在百万富翁问题中，我们可以确定两位百万富翁中谁的钱最多，而他们无需透露自己的钱。

因此，Bob 和 Alice 在网络安全领域赚了数百万美元，但他们现在决定他们的财富要平等——他们变成了社会主义百万富翁。但是，Bob 和 Alice 在网络安全领域的时间里学到了一件事，那就是他们不能信任任何人。那么，Bob 和 Alice 如何在不实际告诉对方他们的财富是多少的情况下，检查他们是否拥有相同的钱？

嗯，这是基于姚的百万富翁问题，我们可以确定两位百万富翁中谁的钱最多，而他们实际上并没有透露他们拥有的钱数。但是，在社会主义百万富翁问题中，我们想表明他们拥有相同的财富。

社会主义百万富翁问题

对于社会主义百万富翁问题（SMP），我们需要证明两位百万富翁要么拥有相同数量的钱，要么没有。为此，我们将使用 Baudot 的方法 [3]。有了这个，两位百万富翁（Bob 和 Alice）就一个基点 H 达成一致。

Alice 的财富为 $x$，并创建三个随机值：$a$、$α$ 和 $r$。

Bob 的财富为 $y$，并创建三个随机值：$b$、$β$ 和 $s$。

Bob 和 Alice 现在必须证明 $x$ 和 $y$ 是相同的，而无需透露它们的值。

Alice 发送 Bob $a$. $H$，Bob 发送 Alice $b$. $H$。然后他们使用 Diffie-Hellman 方法创建一个共享值：

$g$ = $ab$. $H$

Alice 发送 Bob，$α$. $H$，Bob 发送 Alice，$β$. $h$。然后他们使用 Diffie-Hellman 方法创建一个共享值：

$γ$ = $αβ$. $H$

接下来，Alice 创建并发送 Bob 这些值：

$Pa$ = $r$. $γ$

和：

$Qa$ = $r$. $H$ + $x$. $G$

Bob 创建并发送 Alice 这些值：

$Pb$ = $s$. $γ$

和：

$Qb$ = $s$. $H$ + $y$. $G$

他们可以传递 Qa、Qb、Pa 和 Pb，然后使用 Diffie-Hellman 方法得出：

$c$ = $αβ$.( $Qa$ − $Qb$)

然后他们可以计算：

$c$′= $Pa$ − $Pb$

然后他们测试 $c$ = $c$′ 是否成立。如果它们相等，则 Bob 和 Alice 拥有的值是相同的。这是因为：

$Pa$ − $Pb$ = $r$. $γ$ − $s$. $γ$ =( $r$ − $s$). $γ$ = $αβ$.( $r$ − $s$). $H$

因此：

$c$ = $α$. $β$( $Qa$ − $Qb$)= $α$. $β$( $r$. $H$ + $x$. $G$ − $s$. $H$ − $y$. $G$)= $αβ$(( $r$ − $s$). $H$ +( $x$ − $y$). $G$)= $α$. $β$(( $r$ − $s$). $H$ + $ab$( $x$ − $y$). $H$)= $αβ$( $r$ − $s$). $H$ + $αβab$( $x$ − $y$). $H$ =( $Pa$ − $Pb$)+ $αβab$( $x$ − $y$). $H$

因此，如果 $x$ = $y$，我们得到：

$Pa$ − $Pb$

代码如下：

以下提供代码 [ here]：

const std = @import("std");
const crypto = @import("std").crypto;

pub fn uintTo32Bytes(comptime T: type, value: T) [32]u8 {
    var out: [32]u8 = [_]u8{0} ** 32;
    var v = value;
    var i: usize = 0;
    while (v != 0 and i < 32) : (i += 1) {
        out[31 - i] = @intCast(v & 0xff);
        v >>= 8;
    }
    return out;
}
pub fn main() !void {
    var stdout_buffer: [4096]u8 = undefined;
    var stdout_writer = std.fs.File.stdout().writer(&stdout_buffer);
    const stdout = &stdout_writer.interface;
    const args = try std.process.argsAlloc(std.heap.page_allocator);
    defer std.process.argsFree(std.heap.page_allocator, args);
    var xval: u32 = 5;
    var yval: u32 = 5;
    // Check if there are any arguments // 检查是否有任何参数
    if (args.len > 1) {
        xval = try std.fmt.parseInt(u32, args[1], 10);
    }
    if (args.len > 2) {
        yval = try std.fmt.parseInt(u32, args[2], 10);
    }

    // x := curve.Scalar.New(xval)
    // y := curve.Scalar.New(yval)

    const x = try crypto.ecc.P256.scalar.Scalar.fromBytes(uintTo32Bytes(u32, xval), std.builtin.Endian.big);
    const y = try crypto.ecc.P256.scalar.Scalar.fromBytes(uintTo32Bytes(u32, yval), std.builtin.Endian.big);

    const r = crypto.ecc.P256.scalar.Scalar.random();
    const s = crypto.ecc.P256.scalar.Scalar.random();
    const a = crypto.ecc.P256.scalar.Scalar.random();
    const b = crypto.ecc.P256.scalar.Scalar.random();
    const alpha = crypto.ecc.P256.scalar.Scalar.random();
    const beta = crypto.ecc.P256.scalar.Scalar.random();

    // G := H.Mul(a.Mul(b))
    // Gamma := H.Mul(alpha.Mul(beta))
    const G = try crypto.ecc.P256.basePoint.mul(a.mul(b).toBytes(std.builtin.Endian.big), std.builtin.Endian.big);
    const Gamma = try crypto.ecc.P256.basePoint.mul(alpha.mul(beta).toBytes(std.builtin.Endian.big), std.builtin.Endian.big);

    // Pa := Gamma.Mul(r)
    // Pb := Gamma.Mul(s)
    const Pa = try crypto.ecc.P256.mul(Gamma, r.toBytes(std.builtin.Endian.big), std.builtin.Endian.big);
    const Pb = try crypto.ecc.P256.mul(Gamma, s.toBytes(std.builtin.Endian.big), std.builtin.Endian.big);

    // Qa := H.Mul(r).Add(G.Mul(x))
    // Qb := H.Mul(s).Add(G.Mul(y))
    const rH = try crypto.ecc.P256.basePoint.mul(r.toBytes(std.builtin.Endian.big), std.builtin.Endian.big);
    const Gx = try crypto.ecc.P256.mul(G, x.toBytes(std.builtin.Endian.big), std.builtin.Endian.big);
    const Qa = crypto.ecc.P256.add(rH, Gx);
    const sH = try crypto.ecc.P256.basePoint.mul(s.toBytes(std.builtin.Endian.big), std.builtin.Endian.big);
    const Gy = try crypto.ecc.P256.mul(G, y.toBytes(std.builtin.Endian.big), std.builtin.Endian.big);
    const Qb = crypto.ecc.P256.add(sH, Gy);

    // Qa := H.Mul(r).Add(G.Mul(x))
    // Qb := H.Mul(s).Add(G.Mul(y))
    const Qa_Qb = crypto.ecc.P256.sub(Qa, Qb);

    // c := Qa.Sub(Qb).Mul(alpha.Mul(beta))
    // c_ := Pa.Sub(Pb)
    const c = try crypto.ecc.P256.mul(Qa_Qb, alpha.mul(beta).toBytes(std.builtin.Endian.big), std.builtin.Endian.big);
    const c_ = crypto.ecc.P256.sub(Pa, Pb);

    try stdout.writeAll("Socialist Millionaire Problem\n");
    try stdout.print("\n Bob x= {x}\n", .{x.toBytes(std.builtin.Endian.big)});
    try stdout.print("\n Alice y= {x}\n", .{y.toBytes(std.builtin.Endian.big)});
    try stdout.print("\nc= {x}\n", .{c.toCompressedSec1()});
    try stdout.print("\nc_= {x}\n", .{c_.toCompressedSec1()});
    if (c.equivalent(c_)) {
        try stdout.writeAll("\nBob and Alice have the same money\n");
    } else {
        try stdout.writeAll("\nBob and Alice do NOT have the same money\n");
    }
    try stdout.flush();
}

这是一个示例运行，其中 Bob 和 Alice 都有 $5 [ here]：

Socialist Millionaire Problem

Bob x= 0000000000000000000000000000000000000000000000000000000000000005

Alice y= 0000000000000000000000000000000000000000000000000000000000000005

c= 02ec9bea8ac1335aa4ae192c3267f277771fe7ce973ad69ef0ea56c1a99f1482f0

c_= 02ec9bea8ac1335aa4ae192c3267f277771fe7ce973ad69ef0ea56c1a99f1482f0

Bob and Alice have the same money

其中 Bob 拥有 $5，Alice 拥有 $6 [ here]：

Socialist Millionaire Problem

Bob x= 0000000000000000000000000000000000000000000000000000000000000005
Alice y= 0000000000000000000000000000000000000000000000000000000000000006

c= 02975d291461c123286ab88ceddb97744ae97a1e306287148dd7f696324e05097e

c_= 0361a4840fa4c605abd648ea08685504815b1afe5aa16666b704c5fa3a5092c59c

Bob and Alice do NOT have the same money

这是演示:

https://asecuritysite.com/zig/zig_zkp_ver

参考文献

[1] Yao, A. C. (1982, November). Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) (pp. 80–91). IEEE.

[2] Yao, A. C. (1982, November). Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfcs 1982) (pp. 160–164). IEEE.

[3] Boudot, Fabrice, Berry Schoenmakers, and Jacques Traore. “A fair and efficient solution to the socialist millionaires’ problem.” Discrete Applied Mathematics 111.1–2 (2001): 23–36 [ here].

• 原文链接： medium.com/asecuritysite...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～