Chen, Lin ;
Xu, Lei ;
Gao, Zhimin ;
Shah, Nolan ;
Lu, Yang ;
Shi, Weidong
Smart Contract Execution  the (+)Biased Ballot Problem
Abstract
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
@InProceedings{chen_et_al:LIPIcs:2017:8238,
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:121:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8238},
URN = {urn:nbn:de:0030drops82388},
doi = {10.4230/LIPIcs.ISAAC.2017.21},
annote = {Keywords: Blockchain, Probability, Random Walk, Smart Contract}
}
07.12.2017
Keywords: 

Blockchain, Probability, Random Walk, Smart Contract 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

07.12.2017 