无偏冲突终端机:一种和谐利器用于公平抽签
Smallcup@NEWSMTH

=== 概要 ===
本文介绍了一种全国范围随机抽签算法--无偏冲突终端机。本算法基于字符串散列和不可控随机数种子，使得结果的有效性可以被每一个参与抽签个体以简单方法验证，而无人可以影响其公平性。本算法解决了绝大部分随机抽签分配利益的不公平性，给和谐社会提供极大的技术保证。

=== 背景 ===
随机抽签是解决少量资源在大量潜在使用者中分配的方法。经济适用房、彩票、小学入学等等场合都是随机抽签的应用点。更多潜在的应用点包括户口分配、医疗、就业、生育控制等无数方向。但是缺乏有效的公平（特别是可验证的公平）抽签方法造成大量社会矛盾。很多情况即使抽签是公平的，也会被未入选者指摘为不公平。此时抽签组织者和抽签获益者均无法提供可信服的公平性的证明。这样的矛盾极大的影响了社会分配效率，因为不但有权者可能出卖抽签机会，而且即使抽签本身是公平的，也无法说服抽签失败者信服，从而使得抽签结果难以付诸实施。
基于这方面考虑，本文提出一个绝对公平和可验证的抽签算法，可以一举解决上述问题。本方法利用公钥体系、SHA1算法和世界股市报价系统，为每一个抽签事件生成一系列抽签结果。抽签事件规模和结果的数量均可由主办者决定，而其结果可以被任何参与者——包括受益者和败者——以极低成本验证。

=== 模型 ===
设参与者集合U={u_i}包含m个成员。抽签目的在于从中抽取n个成员，使每个成员被抽中的概率均为1/m。模型中另两个元素为抽签组织者和国家抽签局。每个抽签事件在启动前给于一个独立的随机数字N，长度至少160位。

=== 算法 ===
抽签过程分为6个不重叠步骤：预备、报名、构造集合、静默、抽签、结果发布

0，预备
抽签过程6个阶段的日期必须在抽签之前就向全体潜在报名者公式，并用主办者私钥签署。

1，报名
期间，报名人员可以随意增减。我们假设报名者的标示(id_i)是身份证号码（或学生号码、社会安全号码等等，不失一般性），报名结束时，集合U将包含m个元素。特别注意的是，报名过程的公正性不是本算法重点。组织单位可能通过不对称的信息传递使得某些潜在人群无法参与报名或者报名无效。每个参与报名者在报名时均需要提供一个较长（160位或以上）的随机数r_i。报名成功瞬间，由组织者给报名者颁发一个用自己私钥签署的收据，证明的内容为id_i和r_i以及N。

2，报名结束后构造抽签集合，采用以下公式：
   u_i = SHA_1(id_i, r_i, N)
由于u_i足够长，可以忽略冲突的情况。即使出现冲突，在报名期间可以提醒报名者更换r_i解决冲突。

3，静默期
静默期，组织者必须将抽签集合向匿名用户完全开放。所有人可以下载、保存抽签集合U。组织者必须用公钥签署集合U。因为下载是匿名的，组织者无法针对不同下载者提供不同集合，而每个下载者i可以验证SHA_1(id_i, r_i, N)是否在U中。如果不然，他可以很容易举证抽签造假（因为在报名时他拿到了主办者私钥签署的收据）

4，抽签
政府抽签局每天早晨6点30分向社会发布当天的随机数种子S。随机数种子S由8个全球主要股指最后收盘点数的字符串连接。例如香港恒生+美国道琼斯+纳斯达克+日经+法兰克福+伦敦金融等等。由于这些点数均由大量股票价格构成，任何一方均无法精确影响其结果。另一方面，这些指数的运算方法和基础数据均公开，所以不可能出现指数结果造假。实际上政府抽签局并非必要环节，任何人可以从网络直接取得各个指数并构造S。

每一个抽签组织者得到S后，计算
  R = SHA_1(S, N)
如上所述，N为本抽签的特定随机数。
然后对每个代选择成员分别计算
  x_i = SHA_1(R, u_i)
如上所述，m为本抽签的参与人数。抽签最终结果将选去x_i数值最大的n个人。由于x_i足够长，不可能出现x_i重复现象。即使出现，可以按照u_i顺序选择。

5，结果发布
抽签主办者将抽签结果(最高的m个u_i)公布，所有参与者均可验证。实际上，以上2-4步可以被任何抽签者以很低的计算成本重复进行，结果必然相同。如果有人发现结果不准确（前n个x_i中，有的没有出现在结果中），可以轻易举证造假，因为第二步中的U是用主办者私钥签署的。
报名成功者可以用在报名期间得到的签署过的回条(id_i, r_i, N)领取抽签利益。

=== 讨论 ===
1, 隐私
由于报名期间要求用户提供随机数r_i，无人可以通过u_i反推id_i。组织者甚至可以不保存id_i和r_i，而用签署的u_i作为回条，从而彻底保证参与的隐私。

2，攻击
由于抽签的任何环节均可被任何参与者轻易重复并得到相同结果，而且错误结果可以轻易举证造假，所以不存在明显的攻击方式，除了主办方用假身份稀释报名者。这种情况可以用id_i代替u_i，以牺牲隐私的代价，换来身份的真实性。
随机树种子可能是最容易被攻击的环节，但是影响它到特定值的代价极大，超过了绝大多数抽签者的获利。

3，部署方式
可以开源开发全国通用的抽签客户端，用以帮助不具备计算机能力的参与者，验证抽签的有效性。开源的代码可以被任何人检查有无漏洞。

=== 结论 ===
本文的贡献在于提出了一套行之有效而且完全安全的随机抽签算法。这种算法必将促使和谐社会早日到来。

=== 感谢 ===
感谢绿坝的原作者。你们的脸皮给了我足够的勇气把这篇文章完成并发表。