Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.21.pdf
  • Filesize: 484 kB
  • 12 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Lin Chen, Lei Xu, Zhimin Gao, Nolan Shah, Yang Lu, and Weidong Shi. Smart Contract Execution - the (+-)-Biased Ballot Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.21

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.

Subject Classification

Keywords
  • Blockchain
  • Probability
  • Random Walk
  • Smart Contract

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. L Addario-Berry and BA Reed. Ballot theorems, old and new. In Horizons of combinatorics, pages 9-35. Springer, 2008. Google Scholar
  2. DF Bailey. Counting arrangements of 1’s and-1’s. Mathematics Magazine, 69(2):128-131, 1996. Google Scholar
  3. Shagun Bali and Terry Roche. Blockchain technology: Pushing the envelope in fintech. In Industry report TABB Forum, 2015. Google Scholar
  4. Vitalik Buterin. What proof of stake is and why it matters. Bitcoin Magazine, August, 26, 2013. Google Scholar
  5. Vitalik Buterin. A next-generation smart contract and decentralized application platform. white paper, 2014. Google Scholar
  6. Lin Chen, Lei Xu, Zhimin Gao, Nolan Shah, Yang Lu, and Weidong Shi. Smart contract execution - the (+-)-biased ballot problem. URL: http://i2c.cs.uh.edu/tiki-download_wiki_attachment.php?attId=71&download=y.
  7. Lin Chen, Lei Xu, Zhimin Gao, Nolan Shah, Yang Lu, and Weidong Shi. Decentralized execution of smart contracts: Agent model perspective and its implications. In 1st Workshop on Trusted Smart Contracts, 2017. Google Scholar
  8. Lin Chen, Lei Xu, Nolan Shah, Zhimin Gao, Yang Lu, and Weidong Shi. On security analysis of proof-of-elapsed-time (poet). In 19th Annual International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2017. Google Scholar
  9. Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gün Sirer, et al. On scaling decentralized blockchains. In International Conference on Financial Cryptography and Data Security, pages 106-125. Springer, 2016. Google Scholar
  10. Anthony Cuthbertson. Bitcoin now accepted by 100,000 merchants worldwide, 2015. Google Scholar
  11. Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse. Bitcoin-ng: A scalable blockchain protocol. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), pages 45-59, 2016. Google Scholar
  12. Ittay Eyal and Emin Gün Sirer. Majority is not enough: Bitcoin mining is vulnerable. In International Conference on Financial Cryptography and Data Security, pages 436-454. Springer, 2014. Google Scholar
  13. William Feller. An introduction to probability theory and its applications: volume I, volume 3. John Wiley &Sons New York, 1968. Google Scholar
  14. Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. Inclusive block chain protocols. In International Conference on Financial Cryptography and Data Security, pages 528-547. Springer, 2015. Google Scholar
  15. Debin Liu and L Jean Camp. Proof of work can work. In WEIS, 2006. Google Scholar
  16. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. Google Scholar
  17. Marc Renault. Lost (and found) in translation: Andre’s actual method and its application to the generalized ballot problem. The American Mathematical Monthly, 115(4):358-363, 2008. Google Scholar
  18. Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar. Optimal selfish mining strategies in bitcoin. arXiv preprint arXiv:1507.06183, 2015. Google Scholar
  19. Melanie Swan. Blockchain: Blueprint for a new economy. " O'Reilly Media, Inc.", 2015. Google Scholar
  20. Lajos Takács. A generalization of the ballot problem and its application in the theory of queues. Journal of the American Statistical Association, 57(298):327-337, 1962. Google Scholar
  21. Lajos Takács. The distribution of the majority in a ballot. journal for probability theory and related fields, 2(2):118-121, 1963. Google Scholar
  22. Lajos Takács. Fluctuations in the ratio of scores in counting a ballot. Journal of Applied Probability, 1(02):393-396, 1964. Google Scholar
  23. Santosh Vempala. Geometric random walks: a survey. Combinatorial and computational geometry, 52(573-612):2, 2005. Google Scholar
  24. Marko Vukolić. The quest for scalable blockchain fabric: Proof-of-work vs. bft replication. In International Workshop on Open Problems in Network Security, pages 112-125. Springer, 2015. Google Scholar
  25. Gavin Wood. Ethereum: A secure decentralised generalised transaction ledger. Ethereum Project Yellow Paper, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact