The importance of random numbers

It is well known how random number generators play an important role in the blockchain ecosystem, requiring random number services that are safe, unpredicable and reliable. Exisisting public chains such as EOS have provided random number services in the past, but often attacked by hackers due to unproperly design.

Ultrain designed a new random number generator architecture to solve this problem, providing service to both consensus and Dapps. So how does Ultrain guarantee the security and randomness of the random numbers on the chain? The answer lies in the following two mechanisms:

The process of generating random numbers is fully decentralized and open to all, so that everyone can participate in generation and verification, while ensuring the minimum probability of manipulation by carefully designing the incentive mechanism.
The result of the random number passes the highest level of cryptographic randomness check: The National Institute of Standards and Technology SP800-22 test. This result indicates that no one can predict any of the future random numbers, with the random result able to be used directly. No additional processing is required, such as increasing entropy.
To further explain point one: verifiable random function is used to compute a random number, which the blockchain verifies and aggregates to generate the final result. This mechanism is enhanced with high penalties and a reasonable incentive model to prevent malicious behavior.

Secondly, Ultrain’s random number process passes the NIST SP800-22 random number test. This certification is the most strict random test in the industry, used to be a requirement for traditional financial transactions and information communication, guaranteeing the security and randomness of the many services built on top of Ultrain.

Lets explore the specific content of the NIST SP800-22 test:

This test includes 15 different sections as follows:

Frequency Test and Block Frequency Test

  1. These two tests count a random number of binary digits. If one of the numbers is obviously more than the other, then the test will not pass. The test checks any sequence of length M for the sequence. If there are any discrepancies the test will not pass.

  2. Run test and Longest Run test (continuous 0/1 test)

These two tests will count consecutive sequences of binary. Strings that do not conform to statistical characteristics are considered to fail the test. The Longest Run test counts the longest 0 or 1 in any specific sequence of arbitrary length. Demonstrating results outside of the standard distribution will fail.

  1. Binary Matrix Rank Test

The entire sequence is divided into several non-adjacent sub-matrices, and then the order of the matrix is ​​tested. The purpose of this test is to find out if there is a correlation in the sequence. That is, whether other sequences can be inferred by another sequence, which would seriously affect the predictability of random numbers.

  1. Discrete FFT Test

Certain sequences can sometimes appear too often, such as 01011. If there are too many instances of this sequence, it will allow attackers to predict future outcomes. For example, after 0101 appears, the next bit is more likely to be 1. This test performs a discrete FFT transformation of the sequence into the frequency domain and then observes if there is a specific number will appear with an abnormal peak.

  1. Non-overlapping/overlapping Template Matching Test (overlap or non-overlapping template test)

The test moves the window one bit at a time to find a periodic or non-periodic sequence. Generally, it is possible to traverse all possible length of sequence at a certain length. For example, for a width of 4, a total of 16 types of 0000, 0001, 0010, …, 1111 can be found. If any one of the frequencies is abnormal, it will fail.

  1. Universal Statistical Test

The test is made by compressing a specific sequence. If a specific sequence can be compressed to a shorter extent, then the sequence itself is redundant and autocorrelated, which is predictable, so it cannot be considered random.

  1. Cumulative Sums/ Random Excursion (Variant) test

If 0 is regarded as -1, then starting from 0 o’clock, left and right, such as 010 is equivalent to walking to -1. This series of tests will study the maximum length of any sequence walked, and the frequency of staying at the point where the walk passes. Any situation that does not match the statistics will fail.

Ultrain random number testing results

1.21 million data points were collected from the Ultrain random number generator, and then binarized to form binary data such as the following sequence:

1000011010001010001100000010001101011000100010101110101110001000

0101000001000010111101100111111110101011001011011111010101101000

0010111010001100100111000001010111110101110110110111111101001011

0111101001001001111100110010110100011101111001100010001100100000

1111011110101110010110110000111001011110101111101001000010000100

0110110111000111111100100101010111011011110101011110010000011100

RESULTS FOR 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

For each test case, a pass rate of 60/64 and 41/44 was achieved, which means that it passed all tests.

All test data has been uploaded to Ultrain’s Github library(https://github.com/wanghs09/randgen), so anyone can repeat the test. In addition, Ultrain will display the random number in the near future via Ultrain.io. Anyone will be able to generate their own random number data set from Ultrain through this webpage and repeat the test.

Conclusions

Passing the NIST SP800–22 test demonstrates that Ultrain’s random number generator is safe, reliable, and sufficiently random. This also implies that all random numbers generated by the service can be used without additional processing, since they already guarantee enough randomness. Soon, everyone will be able to generate random numbers of the same security level, thanks to Ultrain.

Ultrain continues its work with partners to apply random numbers in the blockchain industry, contributing to fairness and security for all.