TY - GEN

T1 - Smart contract execution -The (+-)-biased ballot problem

AU - Chen, Lin

AU - Xu, Lei

AU - Gao, Zhimin

AU - Shah, Nolan

AU - Lu, Yang

AU - Shi, Weidong

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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.

AB - 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.

KW - Blockchain

KW - Probability

KW - Random walk

KW - Smart contract

UR - http://www.scopus.com/inward/record.url?scp=85038583450&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2017.21

DO - 10.4230/LIPIcs.ISAAC.2017.21

M3 - Conference contribution

AN - SCOPUS:85038583450

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 28th International Symposium on Algorithms and Computation, ISAAC 2017

A2 - Tokuyama, Takeshi

A2 - Okamoto, Yoshio

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 9 December 2017 through 22 December 2017

ER -