百万富翁问题的一个简单解释

两个百万富翁都想比较到底谁更富有，但是有都不想让别人知道自己有多少钱。在没有可信的第三方的情况下如何进行？

这个问题就是著名的姚式百万富翁问题。姚式，即大名鼎鼎的姚期智，我国唯一一个图灵奖获得者，此问题开创了安全多方计算领域，在如今，以区块链为先导的一系列可信（Trustless）架构中，多方计算问题是建立机器信任的关键技术之一。

简化问题

为了简单描述问题，我们假设两个富翁的财产在一千万到一亿之间，而且他们也只想做千万级的比较，也即每个人只在乎是否在千万级别上谁更多。问题简化为：
两个富翁，分别为张三和李四。他们自己都清楚自己有几千万财产，也即，他们心里清楚 1～10中的一个数（代表自己千万级的财富）；他们想知道到底谁的数更大一些。

这里假定：

两人都值得信任，不会作假
两人都希望诚实地比较出谁更服务（即谁的数更大）
两人又都希望知道对方财产到底是多少，如果可能的话，拿到具体数字最好了

其实这里假定的是一个安全多方计算的模型 - 半诚实对手模型，即计算方存在获取其他计算方原始数据的需求，但仍然按照计算协议执行。另外有恶意敌手模型，在这种模型中，参与方可以造假，即不按照计算协议执行计算过程。这就要复杂很多。为简化期间，本文仅讨论半诚实对手模型。

一个”解决方案”

有人提出这样一个解决方案：放一个天平，两边放上封闭的盒子，让两个富翁分别在两边放入质量相同的苹果，有几千万财富就放几个，最后看哪边重就可以了。就这么简单。

真的这么简单么？这里方案的提出者忽略了一个条件，也就是不存在可信的第三方，天平谁来提供？提供天平者是可以知道一切的。

这是一个看似简单实则非常复杂的问题。

不经意传输的解决方案

这个问题在数学上，必须借助于密码学。不经意传输是解决这个问题的绝妙方案。
那么什么是不经意传输呢？拿这个例子来说，就是张三给李四提供 n 个选择，这n个选择对李四而言都是无法分辨的（即无法获知原始内容的），李四从中选择一个并告诉张三。但有趣的是，张三不能知道李四选择的是哪一个。这个有点难了吧。

回到百万富翁问题，一个简单的解决方案就是一下步骤：

张三找10个一模一样的箱子，按照1～10的顺序摆好，并按照自己的财富值分别往里面放入苹果梨和香蕉，具体放法为：如果序号小于自己的财富之，放入苹果，相等，则放入梨，大于自己的财富值，放入香蕉；
把10个盒子都叫上锁；并叫李四过来（或者寄给李四）
李四根据自己的财富值对相应的箱子再加一把锁。然后把其他所有箱子销毁。并把这个选择的箱子送给张三。
张三看到送回来的箱子，但他不知道李四选择的是第几个箱子，因为每个箱子都是一样的
张三李四分别开锁，看里面是什么水果：
-- 如果是苹果，张三比李四富有；
-- 如果是梨，两人一样有钱
-- 如果是香蕉，李四比张三富有

简单吧，可行吗？当然可行！前提是双方都是可信的，双方会遵守协议，所以这是一个半诚实对手模型。如果有一方造假，那么结果就不可信了。那是恶意敌手模型要讨论的问题。

密码学的解决方案

上文中所述的方式在算法中如何实现呢？这就要借助密码学了。觉得密码学太麻烦的同学可以略过以下部分。

无需不经意传输的解决方案

同样，对此问题进行抽象化，其实就是两个数的安全比较大小问题，以确定哪一个较大。张三知道一个整数i，李四知道一个整数j。张三和李四希望知道究竟是 i<=j 呢还是 i>j，但都不想让对方知道自己的数。为简单期间，假设 i 与 j 的范围为 [1, 10]。李四有一个公开密钥Eb与私有密钥Db。

张三选择一个大随机数 x，并用李四的公开密钥加密：
c = Eb(x)
张三计算 c-i，并传送给李四
李四计算下面的 10个数：
Yu=Db(c-i+u) , u[1, 10]
并取一个大素数 p (p 比 x 稍小，李四不知道x，但张三可以告诉李四 x 的大小范围），计算：
Zu=Yu mod p , u属于[1, 10]
这里需要验证：
对所有的 u 下式成立： 0<Zu<p-1
对所有的 uv: |Zu-Zv| >= 2
如果不成立，选择另一个p，重新计算
注意：这里有一个显然的性质： Zi=x mod p
李四将以下数列发给张三：
{Z1, Z2, ... , Zi, Zj+1+1, Zj+2+1, ... Z10+1 }
张三验证这个数列的第 i 个数是否与 x mod p 相同，如果相同，则 i<=j, 否则， i>j。
张三把这个结论告诉李四。

不经意传输

不经意传输本身是一套协议和算法。相对比较复杂。其基本原理还是基于密码学，基于大数分解的复杂性或离散对数解的复杂性。一般在一个有限群中进行。具体这里不赘述，有兴趣的自行google。
在不经意传输的支持下，上述方案可以简化为以下版本：

令 X = {1,2, … , 10}, R=Pi(X) 是 X的一个随机置换。李四计算下面的10个数，得到一个数组 Y = {Y1, Y2, … , Y10}, 其中：
- Yi = g(i, b) = 0 + Ri, 如果 i==b
- Yi = g(i, b) = 10 + Ri, 如果 i > b
- Yi = g(i, b) = 20 + Ri, 如果 i < b
利用不经意传输，张三能够选择她愿意得到的唯一的数 Ya=g(a,b)。不经意传输方案保证了张三可以决定要得到的唯一的数，而李四并不知道张三选择了哪一个数。如果Ya<10，则：a==b; 如果 10<Ya<=20, 则： a>b; 如果 Ya>20，则 a<b。
张三将结果告诉李四

看，是不是跟我们的水果解法比较类似呢？

拓展

百万富翁问题可以说是安全多方计算的最基本的问题了。无论从方案还是算法复杂度而言，都不简单。但是，这里看到了通过安全计算做比较和加法的方案。考虑到所有的算法实现都是最后眼花成计算机门电路，那么把一个算法转换成电路（与，非，异或等），那算法就是这些简单的操作的组合了。这就为复杂的安全计算推开了一扇门，尽管需要突破的技术难点还很多，实现和优化还有很长的路要走，但相信在计算能力日益强大的今天，在需求的拉动之下，会很快迎来突破。