最近区块链非常火,也有人在讨论游戏和区块链的结合,就目前来看,已有的区块链游戏无非就是两种,一种就是类似于CryptoKitties这样的虚拟资产游戏,还有就是博彩类的游戏,比如中本聪筛子vDice等。

这是我当初花了300刀买的一只CryptoKitties,编号448412

        严格来说,这些都不算是真正的游戏,在我看来,区块链游戏起码要做到真正的去中心化,能够实现玩家和玩家之间的互动,并且能提供玩家最基本的游戏乐趣才行。而目前所谓的区块链游戏还远远无法满足这几点,而且现在的区块链被笼罩在非常不好的资本炒作氛围中,所谓的区块链创业大部分都是挂羊头卖狗肉而已。
        从技术上讲,游戏的去中心化并不是一件新鲜事,比如加密领域的“抛币协议”可以算是这方面的老祖宗了。早在1981年,数学家Manuel Blum就曾经发表了一篇著名的论文《Coin Flipping by Telephone: A Protocol for Solving Impossible Problems.》,在开篇就提出一个有趣的情景:

        简单的描述就是两个人想通过抛硬币来决定解决他们之间的分歧,那么如何通过电话或者互联网来实现这个行为呢?很显然让其中一个人来随机是不行的,因为他们互不信任,两个人合作呢?比如说双方各自从0和1之间随机一个值,然后把两个值异或作为最终的结果?也不行,比如说Alice随机出0或者1,她把这个数告诉Bob,那么Bob就有机会根据Alice随机到的值操纵最后结果。所以想得到真正公平的结果,抛币协议必须能够满足“抛币入井”的特性,如同把硬币扔进井中,双方只可以去观看而不能改变结果。
        一种简单的方法是利用单向函数,比如首先让Alice准备一个随机字符串,其中包含”head”或者”tail”作为抛币结果, 然后把这个字符串的hash值给Bob,让Bob猜是head还是tail,最后Alice把原始的字符串公布以验证。这个协议利用了hash函数是单向函数的特性,由于Bob只收到了hash值,他无法判断原始字符串,所以无法作弊,而Alice如果想抵赖,就需要能够操纵这个hash函数,重新构造出一个字符串使其hash值和发给Bob的那个一摸一样,这也是不可能的(或者说很困难的),在WikiPedia给出了一种这个协议的具体实现。
        但Blum给出的协议并不是这样,原因是使用hash函数并不“严肃”,因为很难对其进行严格的安全性分析,尽管Bob无法从hash值反推回原来的字符串,但他很可能发现一些蛛丝马迹,而且靠其中一方直接随机出抛币结果也不公平,因为这需要依赖很高质量且双方都信任的随机函数,Blum的抛币协议可以简单的描述为下面的过程:
        1. 首先Bob准备一个Blum整数\(n=pq\),并且把\(n\)发送给Alice
        2. Alice随机一个小于\(n\)且和\(n\)互质的数\(x\),计算\(y=x^2 \mod n\),然后把\(y\)发送给Bob
        3. Bob猜\(x\)的雅可比符号\((x\mid n)\)是1还是-1,并且把猜测的结果发送给Alice
        4. Alice向Bob出示\(x\)
        5. Bob且向Alice出示\(p,q\)
        6. 双方根据Bob是否猜对来决定硬币是正面还是反面,并且检测对方在这个过程中有没有作弊。


        这个协议利了数论中的一些基本知识,因为并不算复杂,这里先简单介绍一下:
二次剩余(Quadratic residue)

对于整数\(n\)和\(q\),如果存在整数\(x\)满足\(x^2\equiv q\pmod{n}\),那么就称\(q\)是\(n\)的二次剩余

        比如2就是7的一个二次剩余,因为\(3^2\equiv2\pmod7\),但5就不是7的二次剩余,因为找不到一个数满足\(x^2\equiv5\pmod7\),这种情况称5是7的二次非剩余。


勒让德-雅可比符号

设\(p\)是一个大于2的质数,\(a\)是一正整数,那么定义勒让德符号(Legendre Symbol)如下:
$$
\left(\frac{a}{p}\right) =\cases{
1 & \text{ }a\text{ 是 }p\text{的二次剩余} \cr
-1 & \text{ }a\text{ 是 }p\text{的二次非剩余} \cr
0 & \text{ }a\text{ 是 }p\text{的倍数}
}
$$

        勒让德符号一般用\(\left(\frac{a}{p}\right)\)或者\((a\mid p)\)表示,可以直接用欧拉准则(Euler’s criterion)计算
$$
\left(\frac{a}{p}\right)=a^{(p-1)/2}\pmod{p}
$$
        比如\((9\mid 13)=9^{(13-1)/2}\pmod{13}=1\),所以9是13的二次剩余。
        而\((10\mid 13)=10^{(13-1)/2}\pmod{13}=-1\),所以10是13的二次非剩余(在同余系统中\(p-1\equiv -1\pmod{p}\))。
        将勒让德符号扩展到合数\(n\)就是雅可比符号(Jacobi symbol),同样用\(\left(\frac{a}{n}\right)\)或者\((a\mid n)\)表示。

合数\(n\)可以表达成多个质因子的乘积,也就是\(n=p_1p_2\cdots p_k\),那么定义雅可比符号
$$
\displaystyle\left(\frac{a}{n}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots \left(\frac{a}{p_k}\right)
$$

        比如$$
\left(\frac{7}{143}\right)=\left(\frac{7}{11}\right)\left(\frac{7}{13}\right)=(-1)(-1)=1
$$        需要注意的是,对于合数,雅可比符号并不能判断二次剩余,比如上面的例子中,尽管(7|143)=1,但7并不是143的二次剩余


Blum整数(Blum Integer)

如果有质数\(p,q\),满足\(p\equiv3\pmod4,q\equiv3\pmod4\),那么称它们的乘积\(pq\)为Blum整数

        比如21(3×7),33(3×11),133(7×19)都是Blum整数,Blum整数在加密领域用途非常广泛,因为它有很多有用的特性,比如说\(a\)是Blum整数\(n\)的一个二次剩余,那么考察下面的二次剩余方程
$$
x^2\equiv a\pmod{n}
$$        首先这个方程有且只有4个解,如果知道\(n\)的两个质因子\(pq\)的情况下,可以在常数时间内计算出这四个解(一般数论书中都有求解二次剩余方程的方法,这里不再详述),但如果不知道质因子\(pq\)的话,解这个方程非常困难,难度和分解\(n\)的难度相等。
        对于Blum整数\(n\),这4个解的雅可比符号恰好有两个满足\((x\mid n)=1\),另两个解满足\((x\mid n)=-1\),比如方程\(x^2\equiv4\pmod{21}\),四个解分别是2,19,5,16,其中(2|21)=(19|21)=-1,而(5|21)=(16|21)=1


        回到Blum抛币协议,当知道Blum整数这些特性后,理解这个协议就简单了,这个协议中一共有\(p,q,n,x,y\)这几个数,在完成第3步(也就是硬币入井)的时候,Alice知道\(n,x,y\),Bob知道\(p,q,n,y\),对于Bob来说,由于他知道\(n\)的两个质因子,所以他能解出\(y\equiv x^2 \pmod{n}\)的4个解,但正如我们上面的分析,这4个解中有两个的雅可比符号是1,另两个是-1,所以他猜对的概率是50%,这也保证了这个协议产生的随机数一定是均匀的。
        那么Alice有可能作弊吗?如果她想作弊,那么她需要准备两个\(x\),满足\(x_1^2 \equiv x_2^2\pmod{n}\),并且\((x_1\mid n)\neq(x_2\mid n)\),那么根据Blum整数的其他特性,可以推导出$$
x_1^2-x_2^2=(x_1+x_2)(x_1-x_2)\equiv0\pmod{n}
$$        这相当于分解了\(n\),而大数分解又是著名难题,所以Alice也不可能作弊

发表评论

邮箱地址不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.