智能合约学习：近似算法WBDP（truffle + ganache-cli）

本文主要介绍了如何使用truffle + Atom进行拍卖环节1：胜利者选择智能合约的编写，以及如何使用ganache-cli进行智能合约的交互测试。

1 Trueffle框架编写代码

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

1.1 建立项目

PS H:\TestContract> mkdir ReverseAuction
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 创建合约

需求：
请实现一个拍卖协议，在该协议中，每个用户可以提交自己的出价。
根据边际成本排序，每次选择边际成本最低的报价，直到所有的任务被包含。

详细算法可以看参考文献^[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;
  }

  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
  Bid[] public bids;
//  mapping (address => Bid[]) public selected_bids;  // winning 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

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

  event LogBid(address, uint, uint[], uint, uint);
  function log(address id, uint k, uint[] Q, uint bid, uint r) internal {
    emit LogBid(id, k, Q, bid, r);
  }

  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 {
      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 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);

          // 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);
          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;
  }

  // print all bid
  function printAllBids() public {
      require(bids.length > 0);
      for (uint i = 0; i < bids.length; i++) {
        emit LogBid(bids[i].id, bids[i].k, bids[i].Q, bids[i].bid, bids[i].increaseR);
      }
  }

  function testCopy(uint[] _Q) public returns (address, uint, uint[], uint, uint){
      bid1 = Bid({id: msg.sender, k: 0, Q:_Q, bid: 6, increaseR:0});
      bid2 = bid1;
    //  copyBid(bid2, bid1);
      return (bid2.id, bid2.k, bid2.Q, bid2.bid, bid2.increaseR);
  }

  // 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;
      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];
          /*
          _bids[i].id = _bids[i+1].id;
          _bids[i].k = _bids[i+1].k;
          _bids[i].Q = _bids[i+1].Q;
          _bids[i].bid = _bids[i+1].bid;
          _bids[i].increaseR = _bids[i+1].increaseR;
          */
      }
      delete _bids[length - 1];
      _bids.length--;
  }

  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;
  }

}

常见错误

ufixed 和 uint
最开始，我是定义ufixed increaseR; 虽然Solidity从0.4.20开始支持浮点数，然而这些编译器并不支持，会报错UnimplementedFeatureError: Not yet implemented - FixedPointType.。所以只好改成了uint无符号整型。即使会影响精度，但这也是没有办法的事，只能等待EVM的更新了。

memory 和 storage
变量类型，可以在网上找到一些关于他们的介绍，如：Solidity的数据位置特性深入详解。简单的理解，智能合约中的状态变量，也可以说是全局变量吧，都是storage的，而函数中声明的大多数变量都是memory类型的。

看源代码function backupAllBids() {}函数中被注释掉的一句话backup_bids = new Bid[] (length);

最开始我写了一个函数，函数中会调用很多子函数，通过truffle编译后，只会报出UnimplementedFeatureError: Copying of type struct ReverseAuction.Bid memory[] memory to storage not yet supported.错误。

backup_bids是storage类型的，这里的new Bid[] (length)却是memory的。不过我这里有一个疑惑是，在function setTasks() {}函数中，我同样使用了tasks = new uint[] (_amount);，这句话却是正确的，我也不理解是为什么。可能是因为Bid是我自定义的比较复杂的结构体吧。不过不需要自己分配空间，智能合约也依然可以使用，所以目前比较好的方法就是直接删掉这句话。

EVM无法进行debug，我也尝试了利用event事件函数来打印log，不过没有成功，所以很难找出错误在哪儿。只好一个个写测试函数，在cmd中不断重新构造对象，进行单元测试。虽然这一次能找到，但是下一次依然很麻烦，希望赶紧出一个简单方便的以太坊调试工具。

uint 和 int
在我将上面的问题都解决后，我还是决定先把所有调用的子函数都测试完再将它们整合起来，这时候，function deleteConflictBids() {} 函数就报错了，EVM的特性，不会告诉你错在哪儿的，🙂，只给出一句话Error: VM Exception while processing transaction: invalid opcode，就只能自己找了。

我大概记得之前曾经看到过智能合约中进行排序或者类似i--这种类型的语句，很有可能会越界，因为定义的是uint 类型的虽然我们并不会用到i = -1这种，但是当i == 0时，有时候还会进行一次i--操作才会跳出函数，因此这种情况下会报错。

然而在智能合约中，所有的数组取值操作，下标data[i]这里的i必须是uint类型的，不然会报错。所以就需要自己多次进行类型转换。如：定义int i; 使用时bids[uint(i)]。

如上方的源代码那样修改之后，函数调用成功。

单元测试 & 集成测试
我发现单独测试将winner加入selected_bids，以及将selected_bids_num++这几句代码仿佛直接被编译器跳过了，无论重新编译几次，也不会执行。这也导致了后面函数的调用失败。

我想可能是编译器自己的原因，就直接将函数整合了，重新编译，进行整体的集成测试，然后函数完全运行成功。

所以有网友说直接用自带remix编译成abi，然后自己部署，不要用类似truffle之类的工具，毕竟也是其他开发者自己编写的，会有很多bug。remix会实时编译，也挺方便。但是使用框架毕竟要容易一点，目前还能忍受一些小小的错误。

如何用remix编译部署的方法，我另一篇文章也有简单介绍Windows搭建私有链，创建部署Hello world智能合约，自己可以自由组合用什么工具写编译智能合约（atom+truffle, remix, wallet...) ，再用什么方法部署智能合约(truffle, 自己创建的私有链，wallet...)。网上的方法也挺多的。

1.3 编译合约

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

PS H:\TestContract\ReverseAuction> 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, '0x540dcc00853f82dcba9d5871e1013d55d3bd9461')
}

（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个账户作为部署合约初始化的拍卖发起人。
其余5个账户会进行报价。

PS H:\TestContract\ReverseAuction> truffle console
truffle(development)> address = web3.eth.accounts[9];
'0x540dcc00853f82dcba9d5871e1013d55d3bd9461'
truffle(development)> a1 = web3.eth.accounts[1];
'0x68e8a5c2041d181b83b45e6d43bd6632c2fbd4c1'
truffle(development)> a2 = web3.eth.accounts[2];
'0x05f5daeb06b8c9d4e158b9fa0ce3c36805a2542a'
truffle(development)> a3 = web3.eth.accounts[3];
'0x1e78baa740a7241fc92f5d47ae13d6a5f304b516'
truffle(development)> a4 = web3.eth.accounts[4];
'0x489fbcee812f313596ed7fdc816b588383b9c3f7'
truffle(development)> a5 = web3.eth.accounts[5];
'0x6125b3b7e1bf338696eae491df24710ae13258eb'

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],16,{from:a4});
truffle(development)> contract.addBid(0,[2,4,6],9,{from:a5});

并且查看此时a1报价（注释是我写文章的时候加的，为了方便查看，命令行中并没有）。

truffle(development)> contract.getAllBids.call(0)
[ '0x68e8a5c2041d181b83b45e6d43bd6632c2fbd4c1',   // id
  BigNumber { s: 1, e: 0, c: [ 0 ] },             // k
  [ BigNumber { s: 1, e: 0, c: [Array] },         // Q
    BigNumber { s: 1, e: 0, c: [Array] },
    BigNumber { s: 1, e: 0, c: [Array] } ],
  BigNumber { s: 1, e: 1, c: [ 12 ] },            // bid
  BigNumber { s: 1, e: 0, c: [ 0 ] } ]            // increaseR

2.3.4 启动winner selection算法

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

truffle(development)> contract.selectWinners({from:address})
{ tx: '0x376316e4346743675be052b07323b5ebac115d92a80e9cf0571203d5f0207b72',
  receipt:
   { transactionHash: '0x376316e4346743675be052b07323b5ebac115d92a80e9cf0571203d5f0207b72',
     transactionIndex: 0,
     blockHash: '0x8e71731c25b51e8561483cbdeabaaaf8f7eefe7a3a9496f5990bc65043b951c3',
     blockNumber: 11,
     gasUsed: 2515856,
     cumulativeGasUsed: 2515856,
     contractAddress: null,
     logs: [],
     status: '0x1',
     logsBloom: '0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000' },
  logs: [] }

然后查看当前原始Bidsbids中没被选中的报价数。

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

再看看selected_bids中被选中的报价数。

truffle(development)> contract.getSelectedBidsNum.call()
BigNumber { s: 1, e: 0, c: [ 3 ] }

最后分别查看selected_bids中每个被选中报价的详情。

truffle(development)> contract.getSelectedBids.call(0)
[ '0x6125b3b7e1bf338696eae491df24710ae13258eb',
  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: [ 9 ] },
  BigNumber { s: 1, e: 0, c: [ 3 ] } ]
truffle(development)> contract.getSelectedBids.call(1)
[ '0x05f5daeb06b8c9d4e158b9fa0ce3c36805a2542a',
  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: [ 6 ] },
  BigNumber { s: 1, e: 0, c: [ 3 ] } ]
truffle(development)> contract.getSelectedBids.call(2)
[ '0x68e8a5c2041d181b83b45e6d43bd6632c2fbd4c1',
  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: 1, c: [ 12 ] },
  BigNumber { s: 1, e: 1, c: [ 12 ] } ]

最后看一看是否已经覆盖了全部的任务，同时打印social welfare。

truffle(development)> contract.getCurrentQNum.call()
BigNumber { s: 1, e: 0, c: [ 6 ] }
truffle(development)> contract.getSocialWelfare.call()
BigNumber { s: 1, e: 1, c: [ 27 ] }

可以看出所有任务都被覆盖到。

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

下一篇文章，将会用智能合约实现参考文献^[1]的第二部分critical payment算法。

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

2018年7月26日

Reference

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