Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
206 lines (117 sloc) 19.3 KB

最近考虑一个基于以太坊的去中心化赌场的实现, 赌场如果需要实现,那么随机数是必须的。 然后研究了一下以太坊里面的随机数生成,发现并不容易。

以太坊里面生成随机数的几种方式。

oraclize

Oraclize定位为去中心化应用的数据搬运工,它作为Web APIs和DApp的可靠链接。有了Oraclize,就不需要建立额外的信任链,因为我们的行为已经被强制加密验证。Oraclize是一个可证明的诚实的预言机服务,可以让智能合约访问互联网。Oraclize是平台无关的,为所有主流的智能合约平台提供一种虚拟的接口。可以想像,通过Oraclize投入大量有意义的数据到区块链中,可以使得智能合约产业更加繁荣,让更多有价值的应用呈现更大的生命力。

Oraclize的使用方式可以参考下面的代码

在update方法里面调用oraclize_newRandomDSQuery方法来调用Oracle的智能合约的代码, Oracle根据请求来生成对应的数据, 然后把结果通过回调__callback来传入。

/*
   Oraclize random-datasource example

   This contract uses the random-datasource to securely generate off-chain N random bytes
*/

pragma solidity ^0.4.11;

import "github.com/oraclize/ethereum-api/oraclizeAPI.sol";

contract RandomExample is usingOraclize {
    
    event newRandomNumber_bytes(bytes);
    event newRandomNumber_uint(uint);

    function RandomExample() {
        oraclize_setProof(proofType_Ledger); // sets the Ledger authenticity proof in the constructor
        update(); // let's ask for N random bytes immediately when the contract is created!
    }
    
    // the callback function is called by Oraclize when the result is ready
    // the oraclize_randomDS_proofVerify modifier prevents an invalid proof to execute this function code:
    // the proof validity is fully verified on-chain
    function __callback(bytes32 _queryId, string _result, bytes _proof)
    { 
        // if we reach this point successfully, it means that the attached authenticity proof has passed!
        if (msg.sender != oraclize_cbAddress()) throw;
        
        if (oraclize_randomDS_proofVerify__returnCode(_queryId, _result, _proof) != 0) {
            // the proof verification has failed, do we need to take any action here? (depends on the use case)
        } else {
            // the proof verification has passed
            // now that we know that the random number was safely generated, let's use it..
            
            newRandomNumber_bytes(bytes(_result)); // this is the resulting random number (bytes)
            
            // for simplicity of use, let's also convert the random bytes to uint if we need
            uint maxRange = 2**(8* 7); // this is the highest uint we want to get. It should never be greater than 2^(8*N), where N is the number of random bytes we had asked the datasource to return
            uint randomNumber = uint(sha3(_result)) % maxRange; // this is an efficient way to get the uint out in the [0, maxRange] range
            
            newRandomNumber_uint(randomNumber); // this is the resulting random number (uint)
        }
    }
    
    function update() payable { 
        uint N = 7; // number of random bytes we want the datasource to return
        uint delay = 0; // number of seconds to wait before the execution takes place
        uint callbackGas = 200000; // amount of gas we want Oraclize to set for the callback function
        bytes32 queryId = oraclize_newRandomDSQuery(delay, N, callbackGas); // this function internally generates the correct oraclize_query and returns its queryId
    }
    
}

考虑一个提供打赌的智能合约。 用户调用打赌的接口,这个接口会把用户的请求存储起来,然后调用Oracle随机数生成服务。 然后通过Oracle回调服务,判断随机数是否大于某个值,如果成立,那么用户成功,否则用户失败。

这就是典型的Oracle的使用案例。

RANDAO: A DAO working as RNG of Ethereum

randao是一个生成以太坊随机数的去中心化组织,

Random number in programming is very important!

RNG in a deterministic system is very difficult

Miners can't be trusted!

随机数在编程中是非常重要的。 RNG 在一个确定性的系统中是非常难的。 不能相信矿工

解决方案

Solutions

A DAO (decentralised autonomous organisation) that anyone can participate in, and the random number is generated by all participants together! First of all, we need to create a RANDAO contract in the blockchain, which defines the participation rules. Then the basic process of generating a random number can be divided into three phases:

一个DAO(去中心化的匿名组织)允许任何人加入,随机数是被所有的参与者一起合作生成的。首先,我们需要在区块链上创建一个RANDAO的智能合约,合约定义了参与规则。然后生成随机数的基本过程可以分为下面三个步骤:

The first phase: collecting valid sha3(s)

Anyone who want to participate in the random number generation needs to send a transaction to the contract C with m ETH as pledge in a specified time period (e.g, 6 block period, approximately 72s), accompanied by the result of sha3(s), s is the secret number respective picked by participant.

第一步:收集有效的sha3(s) 参与随机数生成的参与者首先需要在一个指定的时间区间(比如,6个区块的区间,大约72秒)发送m ETH作为抵押到智能合约 C,同时发送一个sha3(s)的值到智能合约C ,s是一个只有参与者自己知道的数字.

The second phase: collecting valid s

After the first phase, anyone who submitted sha3(s) successfully needs to send a transaction with the secret number s in the first stage to contract C within a specified time period. Contract C will check if s is valid by running sha3 against s and comparing the result with previous committed data. Valid s will be saved to the collection of seeds to finally generate the random number.

第二步:收集有效的s

在第一步结束后,那些提交了sha3(s)的参与者需要在指定的时间区间内发送s到智能合约C. 智能合约C会检查sha3(s)和之前提交的值是否相同。 相同的s会被保存到种子集合用来最终生成随机数。

The third phase: calculating a random number, refund pledged ETH and bonus

  • After all secret numbers have been successfully collected, contract C will calculate the random number from the function f(s1,s2,...,sn), the result will be written to the storage of C, and the result will be sent to all other contracts that requested the random number before.
  • Contract C will send back the pledge to the participants in the first phase, and the profit is divided into equal parts and sent to all participants as an additional bonus. The profit comes from the fees that is paid by other contracts that consume the random number.

第三步:计算随机数,退回抵押和奖金

  • 在所有的秘密数字s被成功收集后,智能合约C会使用函数f(s1,s2,...,sn)来计算随机数,随机数的结果会写入智能合约的存储,而且结果会被发送到所有之前请求随机数的其他智能合约上面。
  • 智能合约C会把第一阶段的抵押返回给参与者,然后奖金会被分成同等分发送给所有的参与者。奖金来源于请求随机值的其他智能合约。

Additional rules

In order to ensure the RNG can't be manipulated, as well as for safety and efficiency, the contract C has the following additional rules:

  • The first phase, if two or more of the same sha3(s) are submitted in sequence, only the first one is accepted.

  • The first phase, there is a requirement for minimum number of participants, if it fails to collect enough sha3(s) within the time period, then RNG at this block height will fail.

  • If a participant submits the sha3(s) and it is accepted by contract C, he must reveal the s in the second phase.

    • If the participant fails to reveal s in the second phase, then the m ETH sent in the first phase will be confiscated without providing a return.

    • If one or more s isn't revealed in the second phase, RNG at this block height will fail. Confiscated ETHs will be divided equally and send to other participants who revealed s at the second phase. The fees paid by other contracts will be refunded.

补充规则

为了确保RNG不能被操控,以及为了安全和效率,智能合约C有以下的补充规则:

  • 在第一步中,如果有两个或更多个的同样的sha3(s)被提交上来,那么只有第一个会被接受。
  • 在第一步中,对于参与者有最低要求,如果在指定的时间区间内没有收集到足够多的sha3(s)的值,那么RNG在这个区块高度会失败。
  • 如果参与者提交了sha3(s),那么他必须在第二步提交s
    • 如果参与者在第二步没有提交s,那么第一阶段提供的m ETH会被没收而且没有奖励。
    • 如果一个或者多个s没有在第二步被提交,RNG在这个区块高度会失败。没收的ETH会被分成同等分发送给提交了s的其他参与者。其他申请随机数的其他合约的费用会被退回。

Incentive

The RNG cycle is very short, and could be for example 20 cycles in one hour, if one cycle's profit is 0.001% , the monthly rate of return is up to 0.00001 * 20 * 24 * 30 = 0.144. Targeting to 14.4% monthly rate of return, and RNG has n participants on average, the running costs of contract is n * 3 * 500 * gasPrice + Ccost. (Ccost is gas consumed by contract internally, including computing and storage, etc. ) Assuming each random numbers has r time requests on average, the call price is p ETH, the income is r * p. So each participant will get (rp - 1500n * gasPrice - Ccost) / n from one time participation. The current gasPrice is 10 szabo, and estimate of contract consumption is 1500n gas, so estimate of net income is (rp / n - 0.03) ETH. Assuming each RNG has 10 participation, and the pledge is 1000ETH, the minimum required income is 0.4 ETH, which over 0.001% profit in this case. So if the RNG is requested only once, the service price is 0.4 ETH, and if it is requested 10 times, the price is just 0.04 ETH for each request.

激励

RNG的周期非常短,例如一个小时20个生成周期,如果没有周期的利润是0.001%,一个月的盈利会达到0.00001 * 20 * 24 * 30 = 0.144。 为了达到14.4%每个月的盈利,并且RNG平均有n个参与者,运行智能合约C的费用为 n * 3 * 500 * gasPrice + Ccost.(CCost是合约内部的gas消费,包括计算和存储)假设每个随机值平均有r个请求,每个请求的费用是 p ETH, 那么收入是 r*p. 所以每个参与者每一次参与会收到rp - 1500n * gasPrice - Ccost) / n。当前的gasPrice是10 szabo, 合约的消费大概是1500n gas, 所以大概的净收入是(rp/n-0.03)ETH. 假设每个RNG有10个参与者,并且抵押是1000ETH,所以如果RNG如果只请求一次,那么一次的费用是0.4 ETH, 如果请求是10次,那么一次请求的价格会被降到0.04ETH

The RANDAO acts as an infrastructure in the Ethereum system. It is called by other contracts. Contracts for different purposes require different random numbers: some need high security, such as lottery; some need steady responses and the request should be responded immediately, these contracts are normally low-value; some need a callback, they want to receive a notification with random numbers when numbers are ready.

Obviously it's impossible to meet different requirements in various scenarios with only one RNG contract, so a lot of contracts will be created with different initial parameters, but the basic rules are the same.

RANDAO作为以太坊系统的基础设施。被其他的合约调用。不同的合约因为有不同的目的所以需要不同的随机值:有些需要高度加密的,比如说抽奖;有些需要稳定的回应,并且要求立即作出回应,这些合约本身的价值不高;有些需要回调函数,当随机值已经生成的时候需要接收到通知。

很明显通过单一的RNG合约不可能满足所有的不同的请求,所以使用了不同的初始值创建了很多智能合约,不过他们基本的规则是相同的。

For example, if we need high security, we can substantially increase the pledge of the first phase. Thus, the cost of leading to failure of RNG process by not revealing s is greatly increased. And for the contracts without much interest involved, the minimum number of participants and the pledge can be lower.

Let's look at an example of a dApp betting on odd or even numbers, we'll show how to adjust the contract's parameters to meet the desired security level, by making the cost of cheating higher than expected earnings. Assuming the bet is 1000 ETH, the betting contract calls a RNG contract C1, if C1 failed to generate a random number at requested block height, then betting contract waits for the next random number of C1, until there is one generated.

比如,如果你需要高度安全,我们可以大大的增加第一阶段的抵押。这样不提供s的导致失败的概率会大大降低。对于那么资金不是很充足的合约,那么参与者的最小个数和抵押都可以降低。

让我们看一个dapp的例子,这个例子用来赌数的奇数和偶数,我们会显示如何调整合约的参数来匹配适合的安全程度,通过让造假的成本大大高于收益。假设打赌是1000ETH,这个打赌的合约调用了RNG的合约C1, 如果C1在请求的区块高度生成随机数失败了,打赌的合约会等待C1的下一个随机数,直到有一个生成成功。

Let's build the RNG contract C1, and set the pledged ETH of C1 to 2000. The gambler G plays the betting dApp but also participates in the contract. When he finds himself in a disadvantageous position before he reveals his secret number, he can choose not to reveal s, so that the RNG failed and he got another chance. But he will lose the 2000 pledged ETH, so although he can get 1000 ETH expected return, it is still a bad deal. However, G can reduce his losses on C1 by some means, such as participating in C1 using two accounts, sending two sha3(s). if in a disadvantageous position, G will keep only one account's secret, and if only one participant expect G participate to in C1, G will only lose 1000 ETH in C1, but G will get 1000 ETH as expected return, which is a worthy try.

让我们构建RNG智能合约C1, 并且设置抵押的值是2000。 赌徒G参与了dApp的赌注,同时参与了RNG的智能合约。在他提交s之前,发现自己处在不利的状态。他可以选择不提交自己的s,这样RNG会失败,他会得到下一个机会。 但是他会损失2000ETH的抵押,尽管他可以得到1000ETH的赌注,所以这样并不是一个好的交易。然而赌徒G可以使用其他的方式来减少损失,比如G可以使用两个账号参与RNG,发送两个sha3(s).如果在不利的状态,G会让一个账号不提交s,这样如果除了G之外只有另外一个其他的账号,G只会在G1上面损失1000ETH,但是G如果赌赢了可以得到1000ETH,所以也值得一试。

This issue can be fixed by confiscating the pledged ETH, and not return them to participants as bonus. so a contract with 1000 pledged ETH will meet the requirement of the betting dApp.

这种情况可以通过没收所有抵押来修复,不会把他们作为奖励返回。所以一个1000抵押的合约会符合赌博的要求。

Besides confiscation, another scheme can prevent such attacks by introducing an additional system: RANDAO membership. To become a member you must pay dues, anyone paid their dues is a member. Members have different levels according to the dues they paid. Membership does not belong to a contract, but instead functions like a passport to participate in some RANDAO contracts. If a breach of any contract happens, that person's membership will be ended and the dues will be confiscated. Now we can add an additional agreement to C1, C1 will only accept numbers committed by members whose level of investment is high enough (membership dues over 1000 ETH). This will ensure that nobody has a financial motive to try an attack.

除了没收,还有一个方案可以阻止这种攻击,那就是 RANDAO membership。 为了成为成员,你必须缴纳成员费用。根据成员缴纳的费用的多少把成员分成不同的等级, 成员系统不属于智能合约,而是作为一种类似护照的形式来参与一些RANDAO合约。 如果发生违约情况,这个成员的会员资格会被终止,成员会用会被没收。现在我们可以给智能合约C1增加一个额外的协议,C1只接受会员会用大于一定值的成员来参与。 这样来保证没有任何人会有财务动机来发动攻击。

QA: Quest and Answer

Q: Why not let the miners participate in RNG? Why not use tx hash, nonce and other blockchain data? A: Miners have the ability to manipulate these blockchain data, and thus can indirectly affect RNG. If RNG contains blockchain data, it will give the miners capacity to construct random numbers in their favor.

Q: 为什么不让矿工来参与到RNG中? 为什么不使用txhash,nonce或者其他区块链数据? A:矿工有能力才操纵这些区块链数据,而这些会对RNG产生影响。如果RNG包含了区块链数据,会给予矿工按照自己的行为构造随机数的能力。

Q: the miners can ignore certain transactions that contain random number they dislike, how to deal with that? A: That's why we need a time window period. A reasonable period should be greater than 6 blocks, we believe that nobody can produce 6 blocks in succession. So if the participant is honest, and he send numbers immediately as long as each time window open, he doesn't need to worry about being excluded.

Q: 矿工有能力忽略特定的包含了随机数的交易,如何处理这种情况? A: 这就是为什么我们需要时间间隔。 一个合理的时间间隔会大于6个区块,我们任务没有人能连续生成6个区块。 所以如果参与者是忠诚的,而且在时间窗口内发送了那个数字, 那么他不同担心会被矿工排除在外。

Q: Why use all numbers of all participants, rather than a subset? A: The rule to pick a subset is deterministic, so participants will try to take specified position of the collection by various means, if they succeed, they will know in advance what the random number is generating from subsets. If the rule to pick a subset is randomised, then we still have the problem of true randomisation.

Q: 为什么使用所有的参与者的所有的值,而不是其子集? A: 选择一个子集的规则是确定性的,所以参与者将尝试通过各种方式来采集指定的集合位置,如果它们成功,他们将事先知道从子集中产生的随机数。 如果选择一个子集的规则是随机的,那么我们仍然存在真正的随机化问题。

Q: Where does pledged dues go? A: It will be donated to a charity, or RANDAO to maintain funding. Q: 没收的费用去哪了。 会捐献给慈善机构,或者是RANDAO会维护一个基金。

Note: f(s1, s2, ..., sn) is a function with multiple inputs, for example r = s1 xor s2 xor s3 ... xor sn, or r = sha3(sn + sha3(sn-1 + ... (sha3(s2 + s1))))