2026-07-23T04:50:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8238 2024-03-06T10:41:48Z ddc:004 open_access

Smart Contract Execution - the (+-)-Biased Ballot Problem Chen, Lin Xu, Lei Gao, Zhimin Shah, Nolan Lu, Yang Shi, Weidong Blockchain Probability Random Walk Smart Contract 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lin Chen and Lei Xu and Zhimin Gao and Nolan Shah and Yang Lu and Weidong Shi 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.21 urn:nbn:de:0030-drops-82388 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.21 eng https://creativecommons.org/licenses/by/3.0/legalcode