The search functionality is under construction.

Author Search Result

[Author] Yulong ZENG(1hit)

1-1hit
  • A Fast Algorithm for Liquid Voting on Blockchain

    Xiaoping ZHOU  Peng LI  Yulong ZENG  Xuepeng FAN  Peng LIU  Toshiaki MIYAZAKI  

     
    PAPER

      Pubricized:
    2021/05/17
      Vol:
    E104-D No:8
      Page(s):
    1163-1171

    Blockchain-based voting, including liquid voting, has been extensively studied in recent years. However, it remains challenging to implement liquid voting on blockchain using Ethereum smart contract. The challenge comes from the gas limit, which is that the number of instructions for processing a ballot cannot exceed a certain amount. This restricts the application scenario with respect to algorithms whose time complexity is linear to the number of voters, i.e., O(n). As the blockchain technology can well share and reuse the resources, we study a model of liquid voting on blockchain and propose a fast algorithm, named Flash, to eliminate the restriction. The key idea behind our algorithm is to shift some on-chain process to off-chain. In detail, we first construct a Merkle tree off-chain which contains all voters' properties. Second, we use Merkle proof and interval tree to process each ballot with O(log n) on-chain time complexity. Theoretically, the algorithm can support up to 21000 voters with respect to the current gas limit on Ethereum. Experimentally, the result implies that the consumed gas fee remains at a very low level when the number of voters increases. This means our algorithm makes liquid voting on blockchain practical even for massive voters.