When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.21
URN: urn:nbn:de:0030-drops-82388
Go to the corresponding LIPIcs Volume Portal

Chen, Lin ; Xu, Lei ; Gao, Zhimin ; Shah, Nolan ; Lu, Yang ; Shi, Weidong

Smart Contract Execution - the (+-)-Biased Ballot Problem

LIPIcs-ISAAC-2017-21.pdf (0.5 MB)


Transaction system build on top of blockchain, especially smart contract, is becoming an important part of world economy. However, there is a lack of formal study on the behavior of users in these systems, which leaves the correctness and security of such system without a solid foundation. Unlike mining, in which the reward for mining a block is fixed, different execution results of a smart contract may lead to significantly different payoffs of users, which gives more incentives for some user to follow a branch that contains a wrong result, even if the branch is shorter. It is thus important to understand the exact probability that a branch is being selected by the system. We formulate this problem as the (+-)-Biased Ballot Problem as follows: there are n voters one by one voting for either of the two candidates A and B. The probability of a user voting for A or B depends on whether the difference between the current votes of A and B is positive or negative. Our model takes into account the behavior of three different kinds of users when a branch occurs in the system -- users having preference over a certain branch based on the history of their transactions, and users being indifferent and simply follow the longest chain. We study two important probabilities that are closely related with a blockchain based system - the probability that A wins at last, and the probability that A receives d votes first. We show how to recursively calculate the two probabilities for any fixed n and d, and also discuss their asymptotic values when n and d are sufficiently large.

BibTeX - Entry

  author =	{Lin Chen and Lei Xu and Zhimin Gao and Nolan Shah and Yang Lu and Weidong Shi},
  title =	{{Smart Contract Execution - the (+-)-Biased Ballot Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-82388},
  doi =		{10.4230/LIPIcs.ISAAC.2017.21},
  annote =	{Keywords: Blockchain, Probability, Random Walk, Smart Contract}

Keywords: Blockchain, Probability, Random Walk, Smart Contract
Seminar: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 04.12.2017

DROPS-Home | Fulltext Search | Imprint Published by LZI