完全にrandomな数字を生み出すための smart contract RANDAO

EthereumでDappを作ろうと思ったときに手数料やトランザクションの次くらいに困るのがrandamな番号の生成かと思います。
blockhashやtimestampなどの値は、ある程度マイナーに依存した数値になってしまうため、そのまま利用するとマイナーに依存する不完全なものになってしまいます。

randaoは、contractに参加する複数の人間から得られた入力値を乱数生成に利用し、さらに経済的なインセンティブを与えることによってランダム性を担保しよう、という試みです。

こちらに書いてあるので、普通に英語でこちら見ても良いと思います。

以下解説

STEP 1

乱数生成に参加したい参加者は、誓約(pledge)として、決められた期間の間に、あらかじめ決められた量のETHを、それぞれが選択した秘密の番号sのhash sha3(s) と一緒にrandao　contractに送金します。

STEP 2

参加者は、step1で送った番号sをコントラクトに送り、コントラクトはそれをsha3(s)して、step1で受け取ったhashの情報と一致することを確認し、一致した場合は有効なseedとしてsをseedの中に追加し、最終的にseedを元にrandam numberを生成する。

##STEP 3
全てのs（step1で集めた秘密の数字）を集めることに成功したら、random numberを関数f(s1,s2,s2...)によってい生成し、乱数を要求していたコントラクトに対して結果を送信します。

さらにrandaoコントラクトは、pledgeとして受け取っていたETHと、乱数を要求するための手数料として他のコントラクトがrandaoコントラクトに支払っていたETHを合わせたものを、報酬として乱数生成に協力した人たちに送金します。

以上がRANDAOの概要です。このようにして、乱数生成に対して一定のfeeを要求し、生成に協力した人間にそのfeeを支払う、という形を取っています。

以下は実際のコントラクトの解説をします。

##Counter

 contract Counter { 
   uint public counter = 0;
   function count() { 
     counter += 1;    
   } 
 } 

文字通り、数えて行くだけのコントラクト。count()が呼ばれたらstate変数のcounterに+1して行く。

##Randao

contract Randao {
  struct Participant {
    uint256   secret;
    bytes32   commitment;
    uint256   reward;
    bool      revealed;
    bool      rewarded;
  }

  struct Consumer {
    address caddr;
    uint256 bountypot;
  }

  struct Campaign {
    uint32    bnum;
    uint96    deposit;
    uint16    commitBalkline;
    uint16    commitDeadline;

    uint256   random;
    bool      settled;
    uint256   bountypot;
    uint32    commitNum;
    uint32    revealsNum;

    mapping (address => Consumer) consumers;
    mapping (address => Participant) participants;
  }

  uint256 public numCampaigns;
  Campaign[] public campaigns;
  address public founder;

  modifier blankAddress(address _n) { if (_n != 0) throw; _; }

  modifier moreThanZero(uint256 _deposit) { if (_deposit <= 0) throw; _; }

  modifier notBeBlank(bytes32 _s) { if (_s == "") throw; _; }

  modifier beBlank(bytes32 _s) { if (_s != "") throw; _; }

  modifier beFalse(bool _t) { if (_t) throw; _; }

  function Randao() {
    founder = msg.sender;
  }

  event LogCampaignAdded(uint256 indexed campaignID,
    address indexed from,
    uint32 indexed bnum,
    uint96 deposit,
    uint16 commitBalkline,
    uint16 commitDeadline,
    uint256 bountypot);

  modifier timeLineCheck(uint32 _bnum, uint16 _commitBalkline, uint16 _commitDeadline) {
    if (block.number >= _bnum) throw;
    if (_commitBalkline <= 0) throw;
    if (_commitDeadline <= 0) throw;
    if (_commitDeadline >= _commitBalkline) throw;
    if (block.number >= _bnum - _commitBalkline) throw;
    _;
  }

  function newCampaign(
    uint32 _bnum,
    uint96 _deposit,
    uint16 _commitBalkline,
    uint16 _commitDeadline
  ) payable
  timeLineCheck(_bnum, _commitBalkline, _commitDeadline)
  moreThanZero(_deposit) external returns (uint256 _campaignID) {
    _campaignID = campaigns.length++;
    Campaign c = campaigns[_campaignID];
    numCampaigns++;
    c.bnum = _bnum;
    c.deposit = _deposit;
    c.commitBalkline = _commitBalkline;
    c.commitDeadline = _commitDeadline;
    c.bountypot = msg.value;
    c.consumers[msg.sender] = Consumer(msg.sender, msg.value);
    LogCampaignAdded(_campaignID, msg.sender, _bnum, _deposit, _commitBalkline, _commitDeadline, msg.value);
  }

  event LogFollow(uint256 indexed CampaignId, address indexed from, uint256 bountypot);

  function follow(uint256 _campaignID)
  external payable returns (bool) {
    Campaign c = campaigns[_campaignID];
    Consumer consumer = c.consumers[msg.sender];
    return followCampaign(_campaignID, c, consumer);
  }

  modifier checkFollowPhase(uint256 _bnum, uint16 _commitDeadline) {
    if (block.number > _bnum - _commitDeadline) throw;
    _;
  }

  function followCampaign(
    uint256 _campaignID,
    Campaign storage c,
    Consumer storage consumer
  ) checkFollowPhase(c.bnum, c.commitDeadline)
  blankAddress(consumer.caddr) internal returns (bool) {
    c.bountypot += msg.value;
    c.consumers[msg.sender] = Consumer(msg.sender, msg.value);
    LogFollow(_campaignID, msg.sender, msg.value);
    return true;
  }

  event LogCommit(uint256 indexed CampaignId, address indexed from, bytes32 commitment);

  function commit(uint256 _campaignID, bytes32 _hs) notBeBlank(_hs) external payable {
    Campaign c = campaigns[_campaignID];
    commitmentCampaign(_campaignID, _hs, c);
  }

  modifier checkDeposit(uint256 _deposit) { if (msg.value != _deposit) throw; _; }

  modifier checkCommitPhase(uint256 _bnum, uint16 _commitBalkline, uint16 _commitDeadline) {
    if (block.number < _bnum - _commitBalkline) throw;
    if (block.number > _bnum - _commitDeadline) throw;
    _;
  }

  function commitmentCampaign(
    uint256 _campaignID,
    bytes32 _hs,
    Campaign storage c
  ) checkDeposit(c.deposit)
  checkCommitPhase(c.bnum, c.commitBalkline, c.commitDeadline)
  beBlank(c.participants[msg.sender].commitment) internal {
    c.participants[msg.sender] = Participant(0, _hs, 0, false, false);
    c.commitNum++;
    LogCommit(_campaignID, msg.sender, _hs);
  }

  // For test
  function getCommitment(uint256 _campaignID) external constant returns (bytes32) {
    Campaign c = campaigns[_campaignID];
    Participant p = c.participants[msg.sender];
    return p.commitment;
  }

  function shaCommit(uint256 _s) returns (bytes32) {
    return sha3(_s);
  }

  event LogReveal(uint256 indexed CampaignId, address indexed from, uint256 secret);

  function reveal(uint256 _campaignID, uint256 _s) external {
    Campaign c = campaigns[_campaignID];
    Participant p = c.participants[msg.sender];
    revealCampaign(_campaignID, _s, c, p);
  }

  modifier checkRevealPhase(uint256 _bnum, uint16 _commitDeadline) {
    if (block.number <= _bnum - _commitDeadline) throw;
    if (block.number >= _bnum) throw;
    _;
  }

  modifier checkSecret(uint256 _s, bytes32 _commitment) {
    if (sha3(_s) != _commitment) throw;
    _;
  }

  function revealCampaign(
    uint256 _campaignID,
    uint256 _s,
    Campaign storage c,
    Participant storage p
  ) checkRevealPhase(c.bnum, c.commitDeadline)
  checkSecret(_s, p.commitment)
  beFalse(p.revealed) internal {
    p.secret = _s;
    p.revealed = true;
    c.revealsNum++;
    c.random ^= p.secret;
    LogReveal(_campaignID, msg.sender, _s);
  }

  modifier bountyPhase(uint256 _bnum){ if (block.number < _bnum) throw; _; }

  function getRandom(uint256 _campaignID) external returns (uint256) {
    Campaign c = campaigns[_campaignID];
    return returnRandom(c);
  }

  function returnRandom(Campaign storage c) bountyPhase(c.bnum) internal returns (uint256) {
    if (c.revealsNum == c.commitNum) {
      c.settled = true;
      return c.random;
    }
  }

  // The commiter get his bounty and deposit, there are three situations
  // 1. Campaign succeeds.Every revealer gets his deposit and the bounty.
  // 2. Someone revels, but some does not,Campaign fails.
  // The revealer can get the deposit and the fines are distributed.
  // 3. Nobody reveals, Campaign fails.Every commiter can get his deposit.
  function getMyBounty(uint256 _campaignID) external {
    Campaign c = campaigns[_campaignID];
    Participant p = c.participants[msg.sender];
    transferBounty(c, p);
  }

  function transferBounty(
    Campaign storage c,
    Participant storage p
  ) bountyPhase(c.bnum)
  beFalse(p.rewarded) internal {
    if (c.revealsNum > 0) {
      if (p.revealed) {
        uint256 share = calculateShare(c);
        returnReward(share, c, p);
      }
      // Nobody reveals
    } else {
      returnReward(0, c, p);
    }
  }

  function calculateShare(Campaign c) internal returns (uint256 _share) {
    // Someone does not reveal. Campaign fails.
    if (c.commitNum > c.revealsNum) {
      _share = fines(c) / c.revealsNum;
      // Campaign succeeds.
    } else {
      _share = c.bountypot / c.revealsNum;
    }
  }

  function returnReward(
    uint256 _share,
    Campaign storage c,
    Participant storage p
  ) internal {
    p.reward = _share;
    p.rewarded = true;
    if (!msg.sender.send(_share + c.deposit)) {
      p.reward = 0;
      p.rewarded = false;
    }
  }

  function fines(Campaign c) internal returns (uint256) {
    return (c.commitNum - c.revealsNum) * c.deposit;
  }

  // If the campaign fails, the consumers can get back the bounty.
  function refundBounty(uint256 _campaignID) external {
    Campaign c = campaigns[_campaignID];
    returnBounty(_campaignID, c);
  }

  modifier campaignFailed(uint32 _commitNum, uint32 _revealsNum) {
    if (_commitNum == _revealsNum && _commitNum != 0) throw;
    _;
  }

  modifier beConsumer(address _caddr) {
    if (_caddr != msg.sender) throw;
    _;
  }

  function returnBounty(uint256 _campaignID, Campaign storage c)
  bountyPhase(c.bnum)
  campaignFailed(c.commitNum, c.revealsNum)
  beConsumer(c.consumers[msg.sender].caddr) internal {
    uint256 bountypot = c.consumers[msg.sender].bountypot;
    c.consumers[msg.sender].bountypot = 0;
    if (!msg.sender.send(bountypot)) {
      c.consumers[msg.sender].bountypot = bountypot;
    }
  }
}

結構長いコントラクトでした。順番に

変数

struct Participant　乱数生成に参加する人
secret → 秘密の数字
commitment → 秘密の数字のhash sha3(secret)
reward → 報酬
revealed → 有効と証明されたか
rewarded → 報酬を受け取ったか

Consumer　乱数を要求するコントラクト
caddr　→ 乱数を要求するコントラクトのアドレス
bountypot → comsumerが支払った手数料

Campaign
bnum → randam numberを生成するblock number
deposit → 参加者に求めるdeposit
commitBalkline → follow phaseの締め切り。(randam numberをrequestする締め切り)
commitDeadline → 生成に参加する締め切り。commit phaseの締め切り
random → randam numberを格納
settled → 生成が終わったかどうか
bountypot　→ 集めた手数料の合計
commitNum　→ 乱数生成に参加する人の数
revealsNum → hashを証明した人の数
comsumers → 乱数を要求したコントラクトの数
participants　→乱数生成参加者の情報

numCampaigns

campaigns

founder

###修飾子（modifier）

blankAddress

moreThanZero

notBeBlank

beBlank

beFalse

timeLineCheck

checkFollowPhase

checkRevealPhase

bountyPhase

campaignFailed

beConsumer

phaseは
follow phase → commit phase → reveal phase → bounty phase　と移行して行く。

checkSecret
revealで渡された数字とhashが正しいかどうか確認する

###Event

LogCampaignAdded

LogFollow

###関数(functions)
関数だけサクッと説明します

Randao constructor
コンストラクタ。コントラクトをdeployした人間を決定する。

newCampaign(external)
新しい乱数を生成するキャンペーンを生成する。
関数を実行した人はそのcampaignのconsumerに追加される

commit(external)
hashと参加するcampaignを選択して、campaignに参加する

follow (external)
乱数を要求する。（consumerとして登録する）

commitmentCampaign
新しい参加者をcommitmentに追加する

getCommitment (external)
参加者のhashを取得する

getRandom (external)
campaignによって生成されたrandam numberを返す。

shaCommit
数字を受けて、sha3　hashを返す

reveal (external)
参加者が送信した値とcampaiginのidを指定して、自分がcommitしていることを証明する

revealCampaign
campaign参加者の状態変数を更新しておく

returnRandom
commitした人が全員証明されていることを確認して、random変数を返す

getMyBounty (external)
自分の報酬をgetする

transferBounty
乱数生成の報酬をを参加者に送金する

fines
誰かがrevealに失敗していた場合に、懲罰金として他のcommiterに配分される金額を計算する。→revealに失敗した人の分のdepositが他の人に配分される。

calculateShare
campaignが終わった時に、commitした人間に配分される量を計算する。

returnReward
報酬を配分する

refundBounty (external)
campaignが失敗した時に、comsumerに手数料を返金する

returnBounty
campaignが失敗した時に、comsumerに手数料を返金する

色々問題はありそうですが、大規模に人数集めてやったら上手いこと実現できそうな気はします。。
Ethereumでの乱数生成、悩ましいですね。