智能合约学习：近似算法TMDP（truffle + ganach

本文主要介绍了如何使用truffle + Atom进行拍卖环节2：报酬计算智能合约的编写，以及如何使用ganache-cli进行智能合约的交互测试。

---

1 Trueffle框架编写代码

相关细节可以查看另一篇文章以太坊公开拍卖智能合约（truffle + ganache-cli）。本文主要介绍合约实现，以及一些新的点。

1.1 建立项目

PS H:\TestContract> mkdir ReverseAuction2
PS H:\TestContract\ReverseAuction> cd contracts
PS H:\TestContract\ReverseAuction\contracts> truffle create contract ReverseAuction

• \contracts：存放智能合约源代码的地方，可以看到里面已经有一个sol文件，我们开发的ReverseAuction.sol文件就存放在这个文件夹。
• \migrations：这是Truffle用来部署智能合约的功能，待会儿我们会新建一个类似1_initial_migration.js的文件来部署ReverseAuction.sol。
• \test：测试智能合约的代码放在这里，支持js与sol测试。
• truffle-config.js和truffle.js：Truffle的配置文件,需要配置要连接的以太坊网络。

1.2 创建合约

需求：
在上一篇文章的基础上，实现一个拍卖协议，在该协议中，每个用户可以提交自己的出价。
根据边际成本排序，每次选择边际成本最低的报价，直到所有的任务被包含。
得到所有的胜利者后，对每一个胜利Bid进行critical payment，给出对应的报酬。

详细算法可以看参考文献^[1]。

pragma solidity ^0.4.22;


contract ReverseAuction {
    struct Bid{
        address id;  // identity of employee
        uint k;   // k-th bid of user i
    //    bool selected;  // whether it is selected
        uint[] Q; // a subset of sensing tasks that employees are willing to sense
        uint bid;  //  corresponding bid
        uint increaseR;
    }

/*
    struct winnerPay {
        Bid winnerBid;
        Bid criticalBid;
        uint pay;
    }
*/
    uint[] public tasks;   // published tasks
    address public provider;  // task provider
    uint public amount; // amount of tasks

    //mapping (address => Bid[]) public bids;   // mapping from address to bid
    //  mapping (address => Bid[]) public selected_bids;  // winning bids

    // 1. for winner selection
    Bid[] public bids;
    Bid[] public selected_bids;
    uint public selected_bids_num;

    Bid[] public backup_bids;

    uint[] public currentQ;  // tasks set currently included in the selected bids

    uint public utility;  // social welfare

    // 2. for critical payment
  //  winnerPay[] public winnerPays;    // critical payments
    Bid[] public bids_i;    // all bids except bid i
  //  Bid criticalBid;
    uint[] public winnerPays;    // critical pays

    uint[] public Q_;  // currentQ using in Bid_i

    uint[] public diffNums;
    uint public pay;

    event AuctionEnded(uint utility); // auction end event



    constructor(address _provider) {
        provider = _provider;
        amount = 0;
        selected_bids_num = 0;
        utility = 0;
    }

    function setTasks(uint _amount, uint[] _tasks) public {
        amount = _amount;
        tasks = new uint[](_amount);
        for (uint i = 0; i < amount; i++){
            tasks[i] = _tasks[i];
        }
    }

    function getTasks() constant public returns(uint[]){
        return tasks;
    }

    function addBid(uint _k, uint[] _Q, uint _bid) public {
      //  uint length = _Q.length;
        require(_Q.length > 0 && _bid > 0);
        bids.push(Bid({id: msg.sender, k: _k, Q: _Q, bid: _bid, increaseR: 0}));
    }

    function getAllBidsNum() constant public returns (uint) {
        return bids.length;
    }

    function getAllBids(uint index) constant public returns(address, uint, uint[], uint, uint) {
        return (bids[index].id, bids[index].k, bids[index].Q, bids[index].bid, bids[index].increaseR);
    }

    function getBackupBids(uint index) constant public returns(address, uint, uint[], uint, uint) {
        return (backup_bids[index].id, backup_bids[index].k, backup_bids[index].Q, backup_bids[index].bid, backup_bids[index].increaseR);
    }

    function getSocialWelfare() constant public returns (uint) {
        return utility;
    }

    function getSelectedBidsNum() constant public returns(uint) {
        return selected_bids.length;
    }

    function getSelectedBids(uint index) constant public returns(address, uint, uint[], uint, uint) {
       return (selected_bids[index].id, selected_bids[index].k, selected_bids[index].Q, selected_bids[index].bid, selected_bids[index].increaseR);
    }

    function getCurrentQNum() constant public returns (uint) {
        return currentQ.length;
    }

    function getCriticalPay(uint index) constant public returns(uint) {
        return winnerPays[index];
    }

    function getBids_iNum() constant public returns (uint) {
        return bids_i.length;
    }

    function getBids_i(uint index) constant public returns(address, uint, uint[], uint, uint) {
        return (bids_i[index].id, bids_i[index].k, bids_i[index].Q, bids_i[index].bid, bids_i[index].increaseR);
    }

    function getBids_i_Q(uint index) constant public returns(uint[]) {
        return bids_i[index].Q;
    }

    function getQ_() constant public returns(uint[]) {
        return Q_;
    }

    function getDiffNums() constant public returns(uint[]) {
        return diffNums;
    }

    function pay_copy() public {
        copyBids(bids_i, backup_bids);
    }

    function pay_getBid_i(uint i) public {
        getBidsExceptBid_i(selected_bids[i], bids_i);
    }

    function pay_payforBid(uint i) public{
        pay = payForBid(selected_bids[i], bids_i, selected_bids);
    }

    function selectWinners() public returns (uint[]) {
        require(bids.length != 0 && currentQ.length != amount);
        backupAllBids();
        while (currentQ.length != amount) {
            // compute r(bid) for each bid
            computeIncreaseR(bids, currentQ);

            if (bids.length == 0) break;

            // sort increaseR in nondecreasing order
            //  and return the top bid
            sortBidByIncreaseR(bids, int(0), int(bids.length-1));

            // increasing order
            Bid memory bid = Bid({id: bids[0].id, k: bids[0].k, Q: bids[0].Q, bid:bids[0].bid, increaseR: bids[0].increaseR});

            selected_bids.push(bid);
            selected_bids_num++;
            utility += bid.bid;

            // find union of currentQ and bid.Q, then put into the currentQ
            setUnion(currentQ, bid.Q);

            // remove the selected bid from B
            removeBid(0, bids);

            // delete bids that conflict with the selected bid
            deleteConflictBids(bid);

        }
        return currentQ;
    }
   

    function criticalPay(uint i) public returns (uint){
        //  delete bids_i;
        //  bids_i = backup_bids;   // bids has changed in winner selection process
          copyBids(bids_i, backup_bids);
          getBidsExceptBid_i(selected_bids[i], bids_i);   // get bids excpet bid i
          
          // critical pay for bid i
          //  delete criticalBid;     
          uint _pay = payForBid(selected_bids[i], bids_i, selected_bids);

          winnerPays.push(_pay);
          /*
          if (_pay == selected_bids[i].bid) {
              criticalBid = selected_bids[i];
          }
          winnerPays.push(winnerPay({winnerBid: selected_bids[i], criticalBid: criticalBid, pay: _pay}));
          */
          return _pay;
    }

    function copyBids(Bid[] storage bids1, Bid[] storage bids2) internal {
        for (uint i = 0; i < bids2.length; i++) {
            bids1.push(bids2[i]);
        }
        bids1.length = bids2.length;
    }

    function getBidsExceptBid_i(Bid _bid, Bid[] storage _bids_i) internal {
        removeBid(_bid, _bids_i);
    }

    function payForBid(Bid _bid, Bid[] storage _bids_i, Bid[] storage winners) internal returns (uint){
        delete Q_;
        Q_.length = 0;
        uint _pay = _bid.bid;
        delete diffNums;
        while (Q_.length != amount) {
            computeIncreaseR(_bids_i, Q_);
            if (_bids_i.length == 0) break;
            sortBidByIncreaseR(_bids_i, int(0), int(_bids_i.length-1));

            // increasing order
            Bid memory bid = Bid({id: _bids_i[0].id, k: _bids_i[0].k, Q: _bids_i[0].Q, bid:_bids_i[0].bid, increaseR: _bids_i[0].increaseR});

            if (isConflictInBids(bid, winners)) {
                removeBid(0, _bids_i);
                continue;
            }

            // Q_ union bid.Q
            uint diffNum = isSubsetOfcurrentQ(_bid.Q, Q_);
            diffNums.push(diffNum);
            setUnion(Q_, bid.Q);  // Q_ has changed

            if(isSubsetOfcurrentQ(_bid.Q, Q_) == 0) {
              //  _criticalBid = bid;
                _pay = bid.increaseR * diffNum;
                return _pay;
            }

            // remove bid from _bids_i
            removeBid(0, _bids_i);
        }
        return _pay;
    }

    // backup the original bids
    function backupAllBids() internal {
        uint length = bids.length;
      //  backup_bids = new Bid[](length);
        delete backup_bids;
        for (uint i = 0; i < length; i++) {
            backup_bids.push(bids[i]);
        }
    }

    // compute r(bid) for each bid
    function computeIncreaseR(Bid[] storage _bids, uint[] _currentQ) internal{
      for (uint i = 0; i < _bids.length; i++) {
          uint diffNum = isSubsetOfcurrentQ(_bids[i].Q, _currentQ); // |Q-currentQ|
          // Q is subset of currentQ, delete the bid contains Q
          if (diffNum == 0) {
              removeBid(i, _bids);
              i--;
              continue;
          }
          _bids[i].increaseR = _bids[i].bid / diffNum;
      }
    }

    // if Q is the subset of currentQ, delete Q
    // otherwise, compute the marginal benefit of Q
    function isSubsetOfcurrentQ(uint[] _Q, uint[] _currentQ) internal returns (uint){
        uint count = _Q.length;
        if (_currentQ.length == 0) return count;
        for (uint  i = 0; i < _Q.length; i++) {
            for (uint j = 0; j < _currentQ.length; j++) {
                if(_Q[i] == _currentQ[j]) {
                    count--;
                    break;  // jump out of the loop as soon as you find the same one
                }
            }
        }
        return count;
    }

    // delete the bid at the specified location
    function removeBid(uint index, Bid[] storage _bids) internal {
        uint length = _bids.length;
        if (index < 0 || index > length) return;
        for (uint i = index; i < length - 1; i++) {
            _bids[i] = _bids[i+1];
        }
        delete _bids[length - 1];
        _bids.length--;
    }

    function removeBid(Bid _bid, Bid[] storage _bids) internal {
        if (_bids.length <= 0) return;
        address id = _bid.id;
        uint k = _bid.k;
        for (uint i = 0; i < _bids.length; i++) {
            if (_bids[i].id == id && _bids[i].k == k) {
                removeBid(i, _bids);
            }
        }
    }

    function sortBidByIncreaseR(Bid[] storage R, int i, int j) internal {
        if (R.length == 0) return;
        quickSort(R, i, j);
    }

    function quickSort(Bid[] storage R, int i, int j) internal {
        if (i < j) {
            int pivot = partition(R, i, j);
            quickSort(R, i, pivot - 1);
            quickSort(R, pivot + 1, j);
        }
    }

    function partition(Bid[] storage R, int i, int j) internal returns(int){
      //  Bid temp = R[i];
        Bid memory temp = Bid({id: R[uint(i)].id, k: R[uint(i)].k, Q: R[uint(i)].Q, bid:R[uint(i)].bid, increaseR: R[uint(i)].increaseR});
      //  copyBid(temp, R[i]);
        while (i < j) {
            while (i < j && R[uint(j)].increaseR >= temp.increaseR)
                j--;
            if (i < j) {
                R[uint(i)] = R[uint(j)];
                i++;
            }
            while (i < j && R[uint(i)].increaseR <= temp.increaseR)
                i++;
            if (i < j) {
                R[uint(j)] = R[uint(i)];
                j--;
            }
        }
      //  copyBid(R[i] , temp);
        R[uint(i)] = Bid({id: temp.id, k: temp.k, Q: temp.Q, bid: temp.bid, increaseR: temp.increaseR});
        delete temp;
        return i;
    }

    // find the union of two sets
    function setUnion(uint[] storage v1, uint[] v2) internal {
        for (uint i = 0; i < v2.length; i++) {
            if (isElementInSet(v1, v2[i]))  continue;
            v1.push(v2[i]);
        }
    }

    // check whether element is in set v
    function isElementInSet(uint[] v, uint element) internal returns(bool){
        for (uint i = 0; i < v.length; i++) {
            if (v[i] == element) return true;
        }
        return false;
    }

    // delete conflict bids conflict with the bid
    function deleteConflictBids(Bid bid) internal {
        uint length = bid.Q.length;
        int i = 0;
        while (uint(i) < bids.length) {
          //  Bid temp = bids[i];
            Bid memory temp = Bid({id: bids[uint(i)].id, k: bids[uint(i)].k, Q: bids[uint(i)].Q, bid:bids[uint(i)].bid, increaseR: bids[uint(i)].increaseR});
            //copyBid(temp, bids[i]);
            i++;
            // no conflict
            if (temp.Q.length != length) continue;
            // may have conflict
            uint flag = isConflictBid(temp, bid);
            if (flag == 0) {
                --i;
                removeBid(uint(i), bids);
            }
        }
    //    delete temp;
    }

    // check if this two bids conflict
    function isConflictBid(Bid bid, Bid baseBid) internal returns(uint) {
        uint length  = baseBid.Q.length;
        uint flag = length;
        for (uint i = 0; i < length; i++) {
            for (uint j = 0; j < length; j++) {
                if (bid.Q[i] == baseBid.Q[j]) {
                    flag--;
                    break;
                }
            }
        }
        return flag;
    }

  function isConflictInBids(Bid _bid, Bid[] storage _bids) internal returns (bool){
      uint length = _bid.Q.length;
      uint i = 0;
      while (i < _bids.length) {
          Bid memory temp = Bid({id: _bids[i].id, k: _bids[i].k, Q: _bids[i].Q, bid:_bids[i].bid, increaseR: _bids[i].increaseR});
          i++;
          // the numbers are not equal, and do not conflict
          if (temp.Q.length != length) continue;
          uint flag = isConflictBid(temp, _bid);
          if (flag == 0 && _bid.id == temp.id && _bid.k == temp.k) {
              return true;
          }
      }
      return false;
  }
}

常见错误：
最开始，我设计的是通过循环得到所有胜利者的报酬，将他们存到数组中。然而这样会导致out of gas错误。我以为是程序的问题，后来通过单元测试，对每一个Bid自己手动run一遍循环中的内容，发现得出了和C++代码一样的结果。说明不是程序的问题，我就将循环去掉，这样其实正好契合了智能合约的特性，后面会陆续加上密封报价的拍卖等，竞拍成功的人自己调用合约中的criticalPayment()入口得到自己的报酬。

function criticalPay() public returns (uint[]){
        uint num = selected_bids.length;
        for (uint i = 0; i < num; i++) {
            // bids has changed in winner selection process
            copyBids(bids_i, backup_bids);
            getBidsExceptBid_i(selected_bids[i], bids_i);   // get bids excpet bid i

            // critical pay for bid i
            uint _pay = payForBid(selected_bids[i], bids_i, selected_bids);

            winnerPays.push(_pay);         
        }
        return winnerPays;
    }

1.3 编译合约

同样可以参考之前的文章，有详细说明。
在项目根目录ReverseAuction的powershell中执行truffle compile命令：

PS H:\TestContract\ReverseAuction2> truffle compile
Compiling .\contracts\Migrations.sol...
Compiling .\contracts\ReverseAuction.sol...

Compilation warnings encountered:

....

Writing artifacts to .\build\contracts

2 Ganache-cli 部署测试智能合约

2.1 启动ganache-cli

打开powershell终端，可以看到ganache-cli启动后自动建立了10个账号（Accounts），与每个账号对应的私钥（Private Key)。每个账号中都有100个测试用的以太币（Ether）。
Note. ganache-cli仅运行在内存中，因此每次重开时都会回到全新的状态。

C:\Users\aby>ganache-cli

2.2 部署合约

（1）migrations目录下创建一个名字叫做2_deploy_contracts.js的文件。文件中的内容为：

var ReverseAuction = artifacts.require('./ReverseAuction');

module.exports = function(deployer){
    deployer.deploy(ReverseAuction, '0xe81926dafe87588737d82336a93375bb7e5300d7')
}

（2）修改truffle.js文件，连接本地ganache-cli环境。参数在最开初始化ganache-cli环境的窗口可以看到。

module.exports = {
  // See <http://truffleframework.com/docs/advanced/configuration>
  // to customize your Truffle configuration!
  networks: {
        development: {
            host: '127.0.0.1',
            port: 8545,
            network_id: "*" // match any network id
        }
    }
};

（3）现在执行truffle migrate命令，我们可以将ReverseAuction.sol原始码编译成Ethereum bytecode。

PS H:\TestContract\ReverseAuction> truffle migrate --reset
Using network 'development'.

Running migration: 1_initial_migration.js
  Deploying Migrations...
  ... 
Saving artifacts...

2.3 与合约交互

truffle提供命令行工具，执行truffle console命令后，可用Javascript来和刚刚部署的合约互动。

PS H:\TestContract\SimpleAuction> truffle console
truffle(development)>

2.3.1 参与拍卖的账户

我们需要准备一些测试账户。
它会把第一个帐户的地址分配给变量account0，第二个帐户分配给变量account1。Web3是一个JavaScript API，它将RPC调用包装起来以方便我们与区块链进行交互。
我在这里将第9个账户作为部署合约初始化的拍卖发起人。
其余7个账户会进行报价。

PS H:\TestContract\ReverseAuction> truffle console
truffle(development)> address = web3.eth.accounts[9];
'0x9c13d1858c1b6d11cc191df368f973b6166945ef'
truffle(development)> a1 = web3.eth.accounts[1];
'0x68e8a5c2041d181b83b45e6d43bd6632c2fbd4c1'
truffle(development)> a2 = web3.eth.accounts[2];
'0x14636416fafe3c5f04f40a5ab2561d92c5919cad'
truffle(development)> a3 = web3.eth.accounts[3];
'0x86d411018845c6b66147f9f65aafe28be5a7b452'
truffle(development)> a4 = web3.eth.accounts[4];
'0xf8dc81cc6eed17c8a8aafe41f1259264c895e22b'
truffle(development)> a5 = web3.eth.accounts[5];
'0x5e97507ce9fa74b7e4f057e3def717e43e525ba3'
truffle(development)> a5 = web3.eth.accounts[6];
'0x55545b5fade70457a19e81644068cce8ed75017a'
truffle(development)> a5 = web3.eth.accounts[7];
'0x8e9aa9b81a87e58355541a81444e12848a98b388'

2.3.2 启动拍卖

现在我们需要先启动一个拍卖，才能进行接下来的操作。

truffle(development)> let contract
undefined
truffle(development)>  ReverseAuction.deployed().then(instance => contract = instance);

任务提供者设置任务。

truffle(development)> tasks = [1,2,3,4,5,6];
[ 1, 2, 3, 4, 5, 6 ]
truffle(development)> contract.setTasks(6,tasks,{from:address});

truffle(development)> contract.getTasks.call();
[ BigNumber { s: 1, e: 0, c: [ 1 ] },
  BigNumber { s: 1, e: 0, c: [ 2 ] },
  BigNumber { s: 1, e: 0, c: [ 3 ] },
  BigNumber { s: 1, e: 0, c: [ 4 ] },
  BigNumber { s: 1, e: 0, c: [ 5 ] },
  BigNumber { s: 1, e: 0, c: [ 6 ] } ]

2.3.3 开始报价

此时我们用5个账号分别调用addBid()进行报价。

truffle(development)> contract.addBid(0,[1,3,4],12,{from:a1});
truffle(development)> contract.addBid(0,[1,5],6,{from:a2});
truffle(development)> contract.addBid(0,[2,3,4],15,{from:a3});
truffle(development)> contract.addBid(0,[3,4,5,6],20,{from:a4});
truffle(development)> contract.addBid(0,[2,4,6],9,{from:a5});
truffle(development)> contract.addBid(0,[1,2,3],6,{from:a6});
truffle(development)> contract.addBid(0,[3,5],10,{from:a7});

2.3.4 启动winner selection算法

调用function selectWinners() {}函数进行winner selection。

truffle(development)> contract.selectWinners({from:address})

查看selected_bids中被选中的报价数，以及被选中的第一个Bid详情，和当前的social welfare。

truffle(development)> contract.getSelectedBidsNum.call()
BigNumber { s: 1, e: 0, c: [ 3 ] }
truffle(development)> contract.getSelectedBids.call(0)
[ '0x55545b5fade70457a19e81644068cce8ed75017a',
  BigNumber { s: 1, e: 0, c: [ 0 ] },
  [ BigNumber { s: 1, e: 0, c: [Array] },
    BigNumber { s: 1, e: 0, c: [Array] },
    BigNumber { s: 1, e: 0, c: [Array] } ],
  BigNumber { s: 1, e: 0, c: [ 6 ] },
  BigNumber { s: 1, e: 0, c: [ 2 ] } ]
truffle(development)> contract.getSocialWelfare.call()
BigNumber { s: 1, e: 1, c: [ 21 ] }

2.3.5 启动Critical Payment算法

对于每一个胜者，分别调用pay。

truffle(development)> contract.criticalPay(0,{from:address})
truffle(development)> contract.criticalPay(1,{from:address})
truffle(development)> contract.criticalPay(2,{from:address})

查看具体的payment数值。

truffle(development)> contract.getCriticalPay.call(0)
BigNumber { s: 1, e: 1, c: [ 15 ] }
truffle(development)> contract.getCriticalPay.call(1)
BigNumber { s: 1, e: 1, c: [ 15 ] }
truffle(development)> contract.getCriticalPay.call(2)
BigNumber { s: 1, e: 1, c: [ 10 ] }

不过因为设置的bid太少，所以结果不能很好地反映算法。
算法可能也理解有些误差，不过主要目的是学习用智能合约实现一个拍卖算法。

结果与我用c++跑出来的结果一样。

下一篇文章，尝试在这篇文章的基础上，对报价进行保护。

本文作者：Joyce
文章来源：https://www.jianshu.com/p/dc932929a88c
版权声明：转载请注明出处！

2018年8月1日

---

Reference

---

1. TRAC: Truthful Auction for Location-Aware Collaborative Sensing in Mobile Crowdsourcing ↩