一个去中心化的、可验算的、难以操控的抽奖程序。
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
components
public
styles
LICENSE
README.md
gulpfile.js
package.json
server.js

README.md

Rollup

Rollup 希望提供一个去中心化的「抽奖」系统 —— 在抽奖的过程中没有人有特权,一旦有人作弊会被所有人发现。

传统的抽奖系统都是运行在单机上,那么这台设备就可能被做过手脚,抽奖的结果也不能令所有人信服。因此 Rollup 会以分布式的方式运行在所有人的设备上,会有一个后端服务器帮助客户端进行广播,但没有任何特权,每个客户端都会对抽奖过程进行验算,一旦有人作弊就会被发现。

Rollup 只保证在成功选出中奖者时无人作弊,如果有人作弊那么抽奖过程会被中断,如果有人执意捣乱的话会导致抽奖一直无法完成。同时 Rollup 也不会对参与抽奖的资格进行验证,需要在下文提到的「确认参与者」的步骤中自行进行验证。

算法

Rollup 基于两阶段提交来实现,在第一阶段:

  • 每个人本地生成一个随机数(记作 secretNumber)和一个 hashSalt(用于防范彩虹表),将 secretNumberhashSalt 散列之后(记作 numberHash)连同自己的名字一起广播给其他人。
  • 在第一阶段每个人都会收到他人发来的广播,大家需要把收到的广播记录下来,并检查是否所有人都正确地进行了广播,确认所有参与者都进行了广播(否则等待剩余参与者广播 numberHash),确认没有人用不同的名字进行多次广播、没有不应参加的名字(否则抽奖中断)。
  • 每个人在进行确认后开始广播 hashSalt(广播 hashSalt 表示参与者名单确认完成),同时也会收到其他人广播的 hashSalt

对于每个人而言,当收到所有参与者的 hashSalt 之后,进入第二阶段:

  • 每个人开始广播自己的 secretNumber,并接受了记录其他人的 secretNumber(也需要使用之前的 hashSaltnumberHash 进行验算)。
  • 在收到第一阶段所有参与者的 secretNumber 之后,将 secretNumber 排序、组合并进行散列(记作 luckyNumber)。
  • 对比每个人的 secretNumberluckyNumber 的差值,按照差值排序,即为抽奖的结果。

这个算法的要点就在于,在第一阶段中,每个人都选定了一个随机数;而在第二阶段中,大家广播这个随机数并一起生成一个 luckyNumber,决定中奖者名单。之所以需要在第一阶段广播这个随机数的散列值,就是为了保证不会有人在看到其他人的随机数之后,有意地选择自己的数字,来控制最后的 luckyNumber.

讨论

如果有人执意捣乱会怎样?

  • 如果攻击者不广播 numberHash、多次使用不同的名字广播 numberHash 则会被大家在确认参与者名单的环节发现,进而无法进入第二阶段。
  • 如果攻击者不广播 hashSalt 会导致无法进入第二阶段;不广播 secretNumber 则无法得出最后的抽奖结果。
  • 如果攻击者广播错误的 secretNumberhashSaltnumberHash 的组合,则会在第二阶段的验算中失败,进而导致最后的排名无法完成。

简而言之,有客户端故意捣乱会导致抽奖无法完成,但绝不会产生一个被操控的抽奖结果。

如果后端没有公正地进行广播会怎样?

因为目前是使用单一的后端来实现广播,如果这个后端广播错误的消息的话(或者擅自添加消息),和上述存在攻击者的情况是一样的,会导致抽奖无法完成。

如果后端有选择性地不对某个客户端广播特定的消息,会导致客户端的状态出现「分叉」,即有一部分人因为完全感知不到另外一部分人,产生了完全不同的抽奖结果。这的确是目前的实现的一个缺陷,因为在这种情况下被分叉的那一部分人无法证明是后端没有正确地广播、还是自己故意地忽略了广播。

更好的设计可能是通过真正 P2P 的方式进行广播,这样除非其他所有参与者联合起来孤立一部分人,否则其他参与者就可以从未参与攻击的人哪里得到正确的广播。然而真正的 P2P 是没办法实现的 —— 你总是需要一个用作服务发现的节点,同时也要考虑通讯信道的安全性。

这个算法能支撑多大规模的抽奖?

影响最大参与人数的规模主要有两个:

  • 客户端在进行广播时,任何的错误都会导致这一次抽奖失败,需要重新开始(例如填写名字、确认参与者)。在人数过多的情况下,这种人为失误的频率会非常高。
  • 因为每个客户端需要广播消息给其他所有客户端,所以广播的消息量和参与人数的关系是指数级增长的。

实现

该项目基于上述算法实现了一个原型,components/index.jsx 是客户端的主要逻辑,使用 React 编写,需要使用 gulp 编译后才能使用。server.js 是后端的主要逻辑,辅助客户端完成消息的广播。