随机数

本文主要讨论区块链系统中随机数的常见方案，AElf中对于可提供随机数的智能合约提供的标准接口，以及AEDPoS合约对ACS6的实现。 关于ACS的说明可见这篇文章的开头。 区块链和随机数区块链系统中，与合约相关的随机数应用大致有几种场景：抽奖、验证码、密码相关等。 而由于区块链本质上是一个分布式系统，他要求各个节点的运算结果是可验证的，传统的随机数生成结果在不同机器上基本不会一致，让所有的节点产生同样的随机数又不造成过多的延时是不可能的。 好在区块链系统中生成一个可用的随机数，我们已知有几种方案。 中心化生成随机数。随机数由可信的第三方提供，如RANDOM.ORG。Commitment方案，或者hash-commit-reveal方案。如果读者有读过AElf白皮书会发现AElf主链共识用于确定每一轮区块生产者确定生产顺序的in_value和out_value便采用了这种方案：区块生产者在本地生成一个随机的哈希值in_value后，先公布承诺（即out_value），其中out_value = hash(in_value)，到了合适的时机再公布随机哈希值in_value，其他节点只需要验证out_value == hash(in_value)就可以了。这里的in_value可以认为是一个随机数。采集区块链状态信息作为种子，在合约中生成随机数。万一被人知道了随机数的生成算法（智能合约的代码是公开的），再获取到正确的种子，这个方案生成的随机数就可以成功预测的。不敢相信还真有人用这种方式。 显然，站在去中心化的角度上考量，Commitment方案至少是一个可用的方案，只需要保证作出承诺（commitment）的人不会自己偷偷提前公开随机数，或者自己利用随机数作弊即可。 然而很不幸，其实在区块链系统中，这是无法保证的：我们无法保证生成随机数的人不会利用信息不对等来做出不公平的事情，比如当这个随机数被作为某次赌局开奖的依据时，随机数的生成者哪怕在赌局开始之前就做出了承诺，依然可以选择性地中止公开这个随机数——这样相当于他得到了“再玩一次”的机会，因为如果他不公开这个随机数，要么赌局会选择其他人公开的随机数，要么这个赌局会作废。 如果预防随机数生产者的选择中止攻击呢？有一系列成熟的方案，参看Secret Sharing。 简单解释一下：现在有五个人A~E，每人掌握一个公私钥对，此时A产生了一个随机数Random，生成对应的承诺Commitment，同时将随机数Random与B、C、D、E的公钥进行加密得到四个SharingPart，加密SharingPart时便保证只需要凑够B~E中两个人就可以恢复Random，将SharingPart和Commitment一起公开。这样哪怕他自己因故没有公开Random的值，B~E中任意两个人用自己的私钥分别对自己收到的SharingPart解密，凑齐两个解密后的数值（要按A加密出SharingPart的顺序），便可以恢复出Random。而万一两个SharingPart没能恢复出Random，只能认为A从一开始就决定作恶——这时候只需要在区块链经济系统的设计中，让A付出代价就行了。比如直接扣除A申请称为随机数生产者缴纳的保证金。（TODO: 画图） 此外，我们还可以选择不依赖某一个个体产生的随机数，而是选择多个个体的随机数进一步计算哈希值作为应用场景中的可用随机数。如此我们可以比较稳定、安全地在区块链系统中得到随机数。 ACS6 - Random Number Provider Contract Standard我在之前的一篇文章中解释了AElf区块链关于共识的合约标准，实际上是作为AElf主链开发者对合约开发者实现共识机制时推荐实现的接口。而关于随机数生成，我们制定了ACS6，作为对任何提供随机数的合约推荐要实现的接口。 不出意外地，ACS6是选择对Commitment方案进行抽象，得到的合约标准。 支持使用ACS6的场景如下： 用户对实现了ACS6的合约申请一个随机数，类似于发送了一个定单；实现了ACS6的合约给用户返回一些信息，这些信息包括用户可以在哪个区块高度（H）获取得到一个随机数，以及用户获取随机数可用的凭据T（也是一个哈希值）；等待区块链高度到达指定高度H后，用户发送交易尝试获取随机数，凭据T需要作为该交易的参数；实现了ACS6的合约根据凭据T返回一个随机数。如果用户尝试在高度H之前获取随机数，本次获取随机数的交易会执行失败并抛出一个AssertionException，提示高度还没到。 基于以上场景，我们设计的ACS6如下： service RandomNumberProviderContract { rpc RequestRandomNumber (google.protobuf.Empty) returns (RandomNumberOrder) {}rpc GetRandomNumber (aelf.Hash) returns (aelf.Hash) {}} message RandomNumberOrder { sint64 block_height = 1;// Orderer can get a random number after this height.aelf.Hash token_hash = 2;}用户发送RequestRandomNumber交易来申请一个随机数，合约需要为本次请求生成一个凭据（token_hash），然后把该凭据和用户能够获取该随机数的区块高度一起返回给用户。高度达到以后，用户利用收到的凭据（token_hash）发送GetRandomNumber交易即可得到一个可用的随机数。作为合约，在实现该方法的时候应该缓存为用户生成的凭据，作为一个Map的key，这个Map的value则应该根据合约自己对随机数的实现自行定义数据结构。 比如，AEDPoS合约在实现ACS6的时候，可以将该Map的value定义为： message RandomNumberRequestInformation { sint64 round_number = 1;sint64 order = 2;sint64 expected_block_height = 3;}其中round_number指示为了生成该用户申请的随机数，应该使用哪一轮（及之后）各个CDC公布的previous_in_value值；order为这个用户申请随机数的RandomNumberProviderContract交易被该轮第几个CDC打包（所以需要使用该轮该次序以后公布的previous_in_value作为随机数生成的“原材料”）；expected_block_height则是要告知给用户的需要等待到的区块高度。 ...

前言事情起源于一位网友分享了一个有趣的面试题：生成由六位数字组成的ID，要求随机数字，不排重，不可自增，且数字不重复。ID总数为几十万。初次解答我一开始想到的办法是生成一个足够大的ID池（其实就是需要多少就生成多少）对ID池中的数字进行随机排序依次消费ID池中的数字可惜这个方法十分浪费空间，且性能很差。初遇梅森旋转算法后面咨询了网友后得知了一个高效的随机数算法：梅森旋转（Mersenne Twister/MT）。通过搜索资料得知：梅森旋转算法（Mersenne twister）是一个伪随机数发生算法。由松本真和西村拓士在1997年开发，基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数，修正了古典随机数发生算法的很多缺陷。最为广泛使用Mersenne Twister的一种变体是MT19937，可以产生32位整数序列。PS：此算法依然无法完美解决面试题，但是也算学到了新知识MT19937算法实现后面通过Google，找到了一个高效的MT19937的Java版本代码。原代码链接为http://www.math.sci.hiroshima…import java.util.Random;/** * MT19937的Java实现 /public class MTRandom extends Random { // Constants used in the original C implementation private final static int UPPER_MASK = 0x80000000; private final static int LOWER_MASK = 0x7fffffff; private final static int N = 624; private final static int M = 397; private final static int MAGIC[] = { 0x0, 0x9908b0df }; private final static int MAGIC_FACTOR1 = 1812433253; private final static int MAGIC_FACTOR2 = 1664525; private final static int MAGIC_FACTOR3 = 1566083941; private final static int MAGIC_MASK1 = 0x9d2c5680; private final static int MAGIC_MASK2 = 0xefc60000; private final static int MAGIC_SEED = 19650218; private final static long DEFAULT_SEED = 5489L; // Internal state private transient int[] mt; private transient int mti; private transient boolean compat = false; // Temporary buffer used during setSeed(long) private transient int[] ibuf; /* * The default constructor for an instance of MTRandom. This invokes * the no-argument constructor for java.util.Random which will result * in the class being initialised with a seed value obtained by calling * System.currentTimeMillis(). / public MTRandom() { } /* * This version of the constructor can be used to implement identical * behaviour to the original C code version of this algorithm including * exactly replicating the case where the seed value had not been set * prior to calling genrand_int32. * <p> * If the compatibility flag is set to true, then the algorithm will be * seeded with the same default value as was used in the original C * code. Furthermore the setSeed() method, which must take a 64 bit * long value, will be limited to using only the lower 32 bits of the * seed to facilitate seamless migration of existing C code into Java * where identical behaviour is required. * <p> * Whilst useful for ensuring backwards compatibility, it is advised * that this feature not be used unless specifically required, due to * the reduction in strength of the seed value. * * @param compatible Compatibility flag for replicating original * behaviour. / public MTRandom(boolean compatible) { super(0L); compat = compatible; setSeed(compat?DEFAULT_SEED:System.currentTimeMillis()); } /* * This version of the constructor simply initialises the class with * the given 64 bit seed value. For a better random number sequence * this seed value should contain as much entropy as possible. * * @param seed The seed value with which to initialise this class. / public MTRandom(long seed) { super(seed); } /* * This version of the constructor initialises the class with the * given byte array. All the data will be used to initialise this * instance. * * @param buf The non-empty byte array of seed information. * @throws NullPointerException if the buffer is null. * @throws IllegalArgumentException if the buffer has zero length. / public MTRandom(byte[] buf) { super(0L); setSeed(buf); } /* * This version of the constructor initialises the class with the * given integer array. All the data will be used to initialise * this instance. * * @param buf The non-empty integer array of seed information. * @throws NullPointerException if the buffer is null. * @throws IllegalArgumentException if the buffer has zero length. / public MTRandom(int[] buf) { super(0L); setSeed(buf); } // Initializes mt[N] with a simple integer seed. This method is // required as part of the Mersenne Twister algorithm but need // not be made public. private final void setSeed(int seed) { // Annoying runtime check for initialisation of internal data // caused by java.util.Random invoking setSeed() during init. // This is unavoidable because no fields in our instance will // have been initialised at this point, not even if the code // were placed at the declaration of the member variable. if (mt == null) mt = new int[N]; // —- Begin Mersenne Twister Algorithm —- mt[0] = seed; for (mti = 1; mti < N; mti++) { mt[mti] = (MAGIC_FACTOR1 * (mt[mti-1] ^ (mt[mti-1] >>> 30)) + mti); } // —- End Mersenne Twister Algorithm —- } /* * This method resets the state of this instance using the 64 * bits of seed data provided. Note that if the same seed data * is passed to two different instances of MTRandom (both of * which share the same compatibility state) then the sequence * of numbers generated by both instances will be identical. * <p> * If this instance was initialised in ‘compatibility’ mode then * this method will only use the lower 32 bits of any seed value * passed in and will match the behaviour of the original C code * exactly with respect to state initialisation. * * @param seed The 64 bit value used to initialise the random * number generator state. / public final synchronized void setSeed(long seed) { if (compat) { setSeed((int)seed); } else { // Annoying runtime check for initialisation of internal data // caused by java.util.Random invoking setSeed() during init. // This is unavoidable because no fields in our instance will // have been initialised at this point, not even if the code // were placed at the declaration of the member variable. if (ibuf == null) ibuf = new int[2]; ibuf[0] = (int)seed; ibuf[1] = (int)(seed >>> 32); setSeed(ibuf); } } /* * This method resets the state of this instance using the byte * array of seed data provided. Note that calling this method * is equivalent to calling “setSeed(pack(buf))” and in particular * will result in a new integer array being generated during the * call. If you wish to retain this seed data to allow the pseudo * random sequence to be restarted then it would be more efficient * to use the “pack()” method to convert it into an integer array * first and then use that to re-seed the instance. The behaviour * of the class will be the same in both cases but it will be more * efficient. * * @param buf The non-empty byte array of seed information. * @throws NullPointerException if the buffer is null. * @throws IllegalArgumentException if the buffer has zero length. / public final void setSeed(byte[] buf) { setSeed(pack(buf)); } /* * This method resets the state of this instance using the integer * array of seed data provided. This is the canonical way of * resetting the pseudo random number sequence. * * @param buf The non-empty integer array of seed information. * @throws NullPointerException if the buffer is null. * @throws IllegalArgumentException if the buffer has zero length. / public final synchronized void setSeed(int[] buf) { int length = buf.length; if (length == 0) throw new IllegalArgumentException(“Seed buffer may not be empty”); // —- Begin Mersenne Twister Algorithm —- int i = 1, j = 0, k = (N > length ? N : length); setSeed(MAGIC_SEED); for (; k > 0; k–) { mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * MAGIC_FACTOR2)) + buf[j] + j; i++; j++; if (i >= N) { mt[0] = mt[N-1]; i = 1; } if (j >= length) j = 0; } for (k = N-1; k > 0; k–) { mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * MAGIC_FACTOR3)) - i; i++; if (i >= N) { mt[0] = mt[N-1]; i = 1; } } mt[0] = UPPER_MASK; // MSB is 1; assuring non-zero initial array // —- End Mersenne Twister Algorithm —- } /* * This method forms the basis for generating a pseudo random number * sequence from this class. If given a value of 32, this method * behaves identically to the genrand_int32 function in the original * C code and ensures that using the standard nextInt() function * (inherited from Random) we are able to replicate behaviour exactly. * <p> * Note that where the number of bits requested is not equal to 32 * then bits will simply be masked out from the top of the returned * integer value. That is to say that: * <pre> * mt.setSeed(12345); * int foo = mt.nextInt(16) + (mt.nextInt(16) << 16);</pre> * will not give the same result as * <pre> * mt.setSeed(12345); * int foo = mt.nextInt(32);</pre> * * @param bits The number of significant bits desired in the output. * @return The next value in the pseudo random sequence with the * specified number of bits in the lower part of the integer. / protected final synchronized int next(int bits) { // —- Begin Mersenne Twister Algorithm —- int y, kk; if (mti >= N) { // generate N words at one time // In the original C implementation, mti is checked here // to determine if initialisation has occurred; if not // it initialises this instance with DEFAULT_SEED (5489). // This is no longer necessary as initialisation of the // Java instance must result in initialisation occurring // Use the constructor MTRandom(true) to enable backwards // compatible behaviour. for (kk = 0; kk < N-M; kk++) { y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK); mt[kk] = mt[kk+M] ^ (y >>> 1) ^ MAGIC[y & 0x1]; } for (;kk < N-1; kk++) { y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK); mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ MAGIC[y & 0x1]; } y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK); mt[N-1] = mt[M-1] ^ (y >>> 1) ^ MAGIC[y & 0x1]; mti = 0; } y = mt[mti++]; // Tempering y ^= (y >>> 11); y ^= (y << 7) & MAGIC_MASK1; y ^= (y << 15) & MAGIC_MASK2; y ^= (y >>> 18); // —- End Mersenne Twister Algorithm —- return (y >>> (32-bits)); } // This is a fairly obscure little code section to pack a // byte[] into an int[] in little endian ordering. /* * This simply utility method can be used in cases where a byte * array of seed data is to be used to repeatedly re-seed the * random number sequence. By packing the byte array into an * integer array first, using this method, and then invoking * setSeed() with that; it removes the need to re-pack the byte * array each time setSeed() is called. * <p> * If the length of the byte array is not a multiple of 4 then * it is implicitly padded with zeros as necessary. For example: * <pre> byte[] { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06 }</pre> * becomes * <pre> int[] { 0x04030201, 0x00000605 }</pre> * <p> * Note that this method will not complain if the given byte array * is empty and will produce an empty integer array, but the * setSeed() method will throw an exception if the empty integer * array is passed to it. * * @param buf The non-null byte array to be packed. * @return A non-null integer array of the packed bytes. * @throws NullPointerException if the given byte array is null. */ public static int[] pack(byte[] buf) { int k, blen = buf.length, ilen = ((buf.length+3) >>> 2); int[] ibuf = new int[ilen]; for (int n = 0; n < ilen; n++) { int m = (n+1) << 2; if (m > blen) m = blen; for (k = buf[–m]&0xff; (m & 0x3) != 0; k = (k << 8) | buf[–m]&0xff); ibuf[n] = k; } return ibuf; }}测试测试代码 // MT19937的Java实现 MTRandom mtRandom=new MTRandom(); Map<Integer,Integer> map=new HashMap<>(); //循环次数 int times=1000000; long startTime=System.currentTimeMillis(); for(int i=0;i<times;i++){ //使用Map去重 map.put(mtRandom.next(32),0); } //打印循环次数 System.out.println(“times:"+times); //打印Map的个数 System.out.println(“num:"+map.size()); //打印非重复比率 System.out.println(“proportion:"+map.size()/(double)times); //花费的时间(单位为毫秒) System.out.println(“time:"+(System.currentTimeMillis()-startTime));测试结果times:1000000num:999886proportion:0.999886time:374 ...

需求总是很紧急，昨天正在开会收到人力需求，有时间做个抽奖吗?（now 下午四点12，年会五点开始。）还没能等我拒绝，人事又补了一句做不出来我们就不抽奖了，我擦瞬间感觉要是搞不出来会被兄弟们捅死的节奏，默默的删除了没时间做的消息，重新写了四个字名单给我。还好去年前年都是我搞得很庆幸没被当场打脸，重启去年程序（需要收集全员头像并ps）时间显然不够，庆幸的是还有点经验，会议结束时间已经四点半了。好了不扯淡了开始干活吧！先屡一下思路1、好看是好看不了了，别指望没设计没时间程序员搞出来的效果。2、样式开始按钮、停止按钮、人员名单别列表、抽中名单列表。3、点击开始，首先乱序名单列表保证每次抽奖列表顺序不一样，防止他们怀疑我作弊搞权重（就TM半小时哪有时间搞权重）时间紧任务重，直接用的lodash shuffle方法来乱序视图4、随机数是肯定要有的，每隔200ms随机一个从0到人员个数（数组长度随机整数）5、抽中人员和没抽中人员分两个数组存入localStorage，防止抽奖过程中刷新页面，纯静态不存本地那场面就尴尬了每次刷新完如果本次存储了从本地获取人员列表和中奖名单6、点击end选中当前随机数在页面上高亮显示。接下来看整体实现代码//依赖js<script src=“https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script><script src=“https://lib.baomitu.com/lodash.js/4.14.1/lodash.min.js"></script><body> <div id=“list-complete-demo” class=“demo”> <button v-on:click=“start”>start</button> <button v-on:click=“end”>end</button> <div class=“draw-list”> <span v-for=“item in target”>{{item}}</span> </div> <transition-group name=“list-complete” tag=“p”> <span v-for=“item in arrList” v-bind:key=“item” class=“list-complete-item” :class=”{‘draw-bg’: item == value}"> {{ item }} </span> </transition-group> </div> <script> new Vue({ el: ‘#list-complete-demo’, data: { arrList: [ “张三”, “李四”, “王五”, “赵六”, “陈七”, “张扒”, “李十四”, “王十五”, “赵十六”, “陈十七”, “张二三”, “李二四”, “王二五”, “赵二六”, “陈二七”, “张二扒”, “李三四”, “王三五”, “赵三六”, “陈三七” ], target: [],//中奖名单 index: -1,//当前随机索引 timer: null,//定义一个定时器 value: ‘’,//当前人员名 status: true//当前抽奖状态 }, mounted() { if (!localStorage.getItem(‘initData’)) { localStorage.setItem(‘initData’, JSON.stringify(this.arrList)) } else { this.arrList = JSON.parse(localStorage.getItem(‘initData’)) } if (localStorage.getItem(‘drawList’)) { this.target = JSON.parse(localStorage.getItem(‘drawList’)) } }, methods: { start() { if (this.status) { if (this.index != -1) { this.arrList.splice(this.index, 1) localStorage.setItem(‘initData’, JSON.stringify(this.arrList)) } this.shuffle() setTimeout(() => { this.recursive() }, 800) this.status = !this.status } }, randomIndex: function() { this.index = Math.floor(Math.random() * this.arrList.length) return this.index }, remove: function() { this.arrList.splice(this.randomIndex(), 1) }, shuffle: function() { this.arrList = _.shuffle(this.arrList) }, recursive() { clearInterval(this.timer) this.timer = setTimeout(() => { this.value = this.arrList[this.randomIndex()] this.recursive() }, 200) }, end() { clearInterval(this.timer) this.index = this.randomIndex() this.value = this.arrList[this.index] this.target.push(this.value) localStorage.setItem(‘drawList’, JSON.stringify(this.target)) this.status = !this.status } } }) </script></body>体验下效果需求搞定，经现场测试目前没发现什么问题！如有疑问随时回复留言！ ...