Ultrain随机数服务获美国权威认证！
作者：Ultrain首席密码学家Husen王虎森
随机数的重要性
在区块链应用中，随机数服务具有重要的地位，应用领域非常广泛，所以随机数服务是否安全可靠，是需要仔细考量的。之前业内有部分公链提供了随机数的服务，但实际效果都差强人意，往往都具有很大的漏洞，频频出现被黑客攻破的情况。
Ultrain针对业内已有的问题，结合自身公链功能特点，设计了全新的随机数服务架构。那么Ultrain如何保证链上随机数的安全可靠呢？我们主要通过如下两种机制：
1.随机数的生成过程是对所有人公开透明的，并且是人人可以参与，结果是可以验证的，同时极大概率没有人能够左右随机数的结果。
2.随机数的结果通过最高级别的密码学随机性校验，即美国国家标准局测试NIST SP800-22，意味着没有任何人能够预测未来的随机数中的任何一位，随机性完全可以直接使用，不需要经过任何额外的处理比如熵增加。
关于第一点，我们通过参与者利用可验证随机函数贡献随机数的一部分，系统汇集最终结果生成公开的随机数。通过设置高额的惩罚和合理的博弈过程，我们将作恶行为限制为最低。
第二点，我们通过NIST SP800-22的随机数测试保证，这也是目前业内最高级别的测试，保障当今世界上金融和信息领域的诸多服务的安全性和随机性。
NIST SP800-22测试的具体内容
该测试一共有15项。我们这里解释几种比较重要的测试项目：
1.Frequency Test（频率测试）和 Block Frequency Test（块频率测试）
这两项测试会对一串随机的0 1进行统计，假如其中一个数目明显多余另外一个的话，那么测试就不通过。区别在于，Block测试会对整个序列的任一特定长度为M的字符串进行测试，只要有一些出现0 1一个过多，测试也会不通过。
2.Runs Test和longest Runs Test（连续0/1测试）
这两项测试会对连续出现的0或者1序列进行统计。出现过多或者过少，甚至分布不符合统计特性的连续字符串，都被认为测试不通过。longest测试会对整个序列的任一特定长度为M的字符串中的最长0或者1进行统计，分布不合理的会被视为不通过。
3.Binary Matrix Rank Test
将整个序列分为若干个不相邻的子矩阵，然后对矩阵的阶进行测试。该测试的目的是为了发现序列中是否存在相关性，即是不是通过某些序列能推测出其他序列，这会严重影响随机数的不可预测性。
4.Discrete FFT Test（离散FFT测试）
有时候序列的相关性表现在某一频率的字符串出现过多，比如01011。假如出现过多，将会让攻击者可以猜到未来的可能性，比如0101出现后，下一比特更有可能是1。这种测试会将序列进行离散FFT变换到频域，然后观测是不是有一种字符串出现了异常的峰值。
5.Non-overlapping/ overlapping Template Matching Test
（重叠或者非重叠模板测试）
该测试通过一个比特一个比特地移动窗口，找到周期或者非周期性出现的字符串。一般可以遍历所有可能出现的某种长度的字符串，比如对于宽度为4的，可以查找0000, 0001, 0010, ..., 1111共16种。假如任何一个出现频率异常了，都会认为不通过。
6.Universal Statistical Test
该测试是通过对字符串的可压缩性进行测试。假如一个字符串能压缩更短的话，那么说明该字符串本身就是冗余和自相关的，也就是可以预测的，所以也是不能被认为随机的。
7.Cumulative Sums/ Random Excursion(Variant)测试
随机游走测试，即将0看作-1，然后从0点开始，左右游走，比如010相当于走到了-1。该系列测试会研究任何一个序列游走的最大长度和游走经过的点的停留频率，任何一种不符合统计的情况，都会被认为未通过测试。
Ultrain随机数的测试结果
我们对Ultrain随机数采集了121万条数据，然后二进制化，形成了类似如下序列的二进制数据：
1000011010001010001100000010001101011000100010101110101110001000
0101000001000010111101100111111110101011001011011111010101101000
0010111010001100100111000001010111110101110110110111111101001011
0111101001001001111100110010110100011101111001100010001100100000
1111011110101110010110110000111001011110101111101001000010000100
0110110111000111111100100101010111011011110101011110010000011100
然后对所有SP800-22的测试项目进行了测试，测试结果如下（不完全列举）：
RESULTSFOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
generator is<data/sp800test.log>
------------------------------------------------------------------------------
C1 C2 C3 C4 C5 C6 C7 C8 C9C10 P-VALUE PROPORTION STATISTICAL TEST
------------------------------------------------------------------------------
3 7 6 9 8 5 6 10 4 6 0.602458 64/64 Frequency
8 7 7 6 3 4 7 5 6 11 0.568055 63/64 BlockFrequency
3 7 6 6 7 11 9 4 5 6 0.500934 64/64 CumulativeSums
4 8 10 9 4 7 5 7 7 3 0.500934 64/64 CumulativeSums
6 4 8 8 6 5 5 7 5 10 0.804337 63/64 Runs
10 4 6 10 8 1 5 6 9 5 0.178278 63/64 LongestRun
3 7 7 8 2 6 10 6 7 8 0.468595 64/64 Rank
4 9 13 4 7 5 4 11 6 1 0.015963 64/64 FFT
10 8 7 6 8 5 5 7 4 4 0.739918 63/64 NonOverlappingTemplate
9 4 5 7 9 9 6 5 7 3 0.602458 64/64 NonOverlappingTemplate
6 8 3 16 7 5 6 5 4 4 0.014216 62/64 OverlappingTemplate
8 2 5 8 9 4 9 6 6 7 0.534146 64/64 Universal
4 5 6 7 9 7 6 7 5 8 0.931952 63/64 ApproximateEntropy
6 4 5 3 8 5 3 4 3 3 0.689019 43/44 RandomExcursions
6 2 4 5 4 4 3 6 6 4 0.875539 43/44 RandomExcursions
10 4 4 5 8 7 12 5 5 4 0.213309 62/64 Serial
10 8 7 6 7 3 5 7 5 6 0.772760 63/64 LinearComplexity
对于每个测试样例，满足了60/64和41/44的通过率测试，相当于通过了所有测试。
测试用的数据集已经上传到Ultrain的Github库：
(https://github.com/wanghs09/randgen)，任何人都可以重复该测试。同时我们近期将对外开放该随机数的调用网页，任何人都可以通过该网页收集Ultrain生成的随机数数据集并重复该测试。
通过测试后的意义
Ultrain的随机数服务通过SP800-22的测试，首先表明Ultrain该服务生成的随机数是安全可靠，并且是足够随机的；同时意味着该服务生成的所有随机数可以不经过额外的处理就可以使用，可以保证足够的随机性。而且经过安全的派生，比如与特定的序列号一起hash，即可以生成同样安全级别的随机数。
Ultrain会持续稳定地提供Ultrain链上随机数服务，我们会同合作伙伴一起，将随机数在区块链中应用开来，为区块链行业的公平性和安全性做出贡献。
