<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Seres István András on Medium]]></title>
        <description><![CDATA[Stories by Seres István András on Medium]]></description>
        <link>https://medium.com/@istvan-a-seres?source=rss-8498e40d416------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*4q0JCw9dyth4van9.jpg</url>
            <title>Stories by Seres István András on Medium</title>
            <link>https://medium.com/@istvan-a-seres?source=rss-8498e40d416------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 12:09:22 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@istvan-a-seres/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Messi or Ronaldo? A mathematical argument to settle the football G.O.A.T. debate]]></title>
            <link>https://istvan-a-seres.medium.com/messi-or-ronaldo-a-mathematical-argument-to-settle-the-football-g-o-a-t-debate-5975b6945339?source=rss-8498e40d416------2</link>
            <guid isPermaLink="false">https://medium.com/p/5975b6945339</guid>
            <category><![CDATA[mathematics-education]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[football]]></category>
            <category><![CDATA[messi]]></category>
            <dc:creator><![CDATA[Seres István András]]></dc:creator>
            <pubDate>Wed, 31 May 2023 10:34:55 GMT</pubDate>
            <atom:updated>2023-06-01T10:15:10.045Z</atom:updated>
            <content:encoded><![CDATA[<p><em>It has been long debated passionately who is the greatest footballer of all time. In this post, we try to answer this question rigorously without bias through the lens of mathematics. In particular, we will analyze the intriguing patterns of Messi’s and Cristiano Ronaldo’s goal-scoring patterns.</em></p><h4>If you want to learn about the coupon collector’s problem or the Kolmogorov-Smirnov test in an entertaining manner, then read on!</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*gpmNnsg16-Zh2mwJ.jpg" /><figcaption>Messi and Ronaldo playing chess. But which of them is better at football?</figcaption></figure><h3>The definition of greatness</h3><p>In mathematics, we often start with axioms and/or definitions. How shall we define being a great striker in football? Well, first of all, an attacker must be unpredictable and equally dangerous for the opponent&#39;s goal at every single minute. Imagine that it would be known that an attacker solely scores between minutes 30 and 35. Then it is straightforward to defend against such a predictable striker: double-team or even triple-team them for that short 5 minutes of the game. Afterward, you can even forget about that particular striker before the 30th minute and after the 35th minute of the game since they are incapable of scoring a goal. Now, we can define more formally what makes a striker excellent.</p><blockquote><em>Definition (</em><strong><em>perfect striker</em></strong><em>): a striker is said to be </em><strong><em>perfect</em></strong><em> if they can score at every single minute of the game with equal (non-zero) probability. More precisely, the probability distribution of their scoring behavior follows a </em><a href="https://en.wikipedia.org/wiki/Discrete_uniform_distribution"><em>uniform random distribution</em></a><em>.</em></blockquote><p>The definition implies that in our particular example, a perfect striker’s probability of scoring a goal at each minute of the game is 1/90. In contrast, in our example above with the predictable striker, their scoring probability is 0 in the first half an hour of the game and after the 35th minute of the game. On the other hand, they score a goal between the 30th and 35th minute with an 18/90 probability per minute (20%).</p><p>Let’s explore how close Messi and Ronaldo are to being perfect strikers!</p><h3>Goal at every minute!</h3><p>First, we collected for Messi and Ronaldo the number of goals they scored each minute of the game throughout their careers. Interestingly, at the time of writing, Ronaldo scored at least 1 goal per each minute of the game, while Messi did not manage to score in the very first minute of the game.</p><pre>## The number of goals the players scored in each minute of the game. <br>messiGoalsPerMinute = [0,1,5,4,9,3,4,6,5,4,9,9,10,5,11,11,8,9,5,12,9,6,11,7,12,9,7,10,4,9,12,6,12,7,6,9,11,13,8,9,7,12,15,7,22,2,5,3,6,8,10,5,5,5,15,8,7,13,10,10,12,8,11,12,11,6,9,8,10,5,6,9,12,11,14,10,9,14,8,11,5,12,8,6,12,13,14,12,12,45]<br>ronaldoGoalsPerMinute = [1,6,10,8,2,6,3,5,5,8,5,5,7,11,3,3,5,7,5,6,9,5,15,7,8,11,7,11,5,9,4,6,7,6,7,7,6,7,6,3,7,4,4,11,15,1,7,4,8,11,10,5,7,7,8,4,7,9,6,8,6,6,8,10,10,2,4,13,9,9,6,3,11,5,6,7,9,7,10,9,10,11,7,7,7,5,9,10,12,35]</pre><p>The above goal-per-minute database is more updated for Messi than for Ronaldo. Hence, we observe more total goals for Messi (817 vs. 663). One can observe in the following figure that there are two outlier data points: one around the 45th minute and one around the 90th minute. This is because all the goals that were scored in the additional time after the 45th or the 90th minute are represented in a single bin corresponding to those two minutes. Interestingly, both players tend to score more goals in the second half. More precisely, the expected times of the goal distributions are 50.21 for Messi and 48.95 for Ronaldo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*FaysrrcLQIzTOvPJbOlUvw.png" /></figure><p>Let’s consider the following intriguing question: assuming that a striker scores a goal in each and every minute with equal probability, how many goals do they need to score in order to have at least one goal scored every minute? This question is closely related to the <a href="https://en.wikipedia.org/wiki/Coupon_collector%27s_problem">coupon collector’s problem</a>.</p><p>The coupon collector’s problem is as follows. One can buy items that inside them contain coupons. Altogether there are <em>n</em> different coupons one wants to collect. The coupon collector’s problem asks how many items one needs to buy on average to collect all the coupons assuming that every coupon is placed with equal probability in each item. A simple argument shows that when there are <em>n </em>elements, then we need to buy, on average<em> nlog(n) </em>items to have drawn each coupon at least once.</p><blockquote>This quantity for the expected number of goals to reach at least one goal per minute for a 90-minute football game is <a href="https://www.wolframalpha.com/input?i=90*log%2890%29">404.98</a><em>. G</em>uess what! <a href="https://www.si.com/extra-mustard/2014/02/12/throughout-his-career-cristiano-ronaldo-has-scored-a-goal-in-every-minute-of-a-game">Ronaldo’s 405th career goal</a> has accomplished the achievement of notching at least one goal at every minute. This is just exactly what the simple mathematics of the coupon collector’s problem has predicted.</blockquote><p>This simple statistic might hint that, indeed, the distribution of these footballers&#39; goals per minute might follow a uniformly random distribution. Now, let’s get back to our original question. According to our definition, how close Messi and Ronaldo are to being perfect strikers?</p><h3>How close to being perfect?</h3><p>First, we observe that in our small database, we have different total numbers of goals scored for each player. To make them comparable, we normalize these lists to obtain a probability distribution. The next figure shows Messi’s and Ronaldo’s scoring probability distributions. One can see that both of them are “pretty close” to the black horizontal line representing the perfect scoring distribution: the uniform random distribution. But which of them is closer to the uniform random distribution? Put differently, which of them is closer to being a perfectly unpredictable and dangerous striker throughout the whole game?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*HCifEhL3hLqpXjZZvGGdQA.png" /></figure><p>Since we want to settle the football G.O.A.T. debate, we need to answer the following mathematical question: how close each player’s goal distribution is to the uniformly and randomly distributed goal distribution? As shown in the figure above, we cannot hope that either of the player’s goal distributions would match perfectly the uniformly random distribution. Rather, it only makes sense to ask <em>how close their goal-scoring distribution is to the uniformly random distribution.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*PyJoXd8p6AJrB_k4tiFwSA.png" /></figure><p>A valuable statistical tool called the Kolmogorov-Smirnov test (KS test) measures just that. More precisely, the KS test measures the distance between two probability distributions. We take the cumulative distribution functions (CDF) of each of our analyzed probability distributions and measure the distance between them at each point. The KS statistic is the maximum of these distances (in our example, we have a finite, discrete probability distribution, so we can take the maximum. The usual definition would use the supremum).</p><pre>rng = np.random.default_rng()<br>print(stats.kstest(messiCDF, stats.uniform.rvs(size=sum(messiGoalsPerMinute), random_state=rng), N=sum(messiGoalsPerMinute)))<br>print(stats.kstest(ronaldoCDF, stats.uniform.rvs(size=sum(ronaldoGoalsPerMinute), random_state=rng), N=sum(ronaldoGoalsPerMinute)))<br>## The result<br>KstestResult(statistic=0.09948320413436693, pvalue=0.3718889719826961)<br>KstestResult(statistic=0.07003519356460533, pvalue=0.8030016140819126)</pre><p>The verdict of the KS test is that Ronaldo’s goal-scoring distribution is closer (KS statistic 0.070) to the uniformly random distribution than Messi’s (KS statistic 0.099), also with higher confidence (p-value). Hence, we just showed, in a rigorous way, that Ronaldo’s goal-scoring distribution is closer to being perfect than Messi’s.</p><h3>Epilogue</h3><p>Obviously, deciding who is the football G.O.A.T is much more a social construction than a mathematical debate. One would need to factor in many more aspects of greatness that are not necessarily measurable, for instance, cultural impact or impact on the game. Nevertheless, in this post, we tried to analyze Messi’s and Ronaldo’s goal-scoring distributions from a mathematical point of view and answered a few intriguing questions.</p><p>If you want to see another mathematician’s view on settling the football G.O.A.T. debate, <a href="https://www.youtube.com/watch?v=vcIrkpXKrZU">watch this video</a> by <a href="https://tomrocksmaths.com/">Tom Crawford</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5975b6945339" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Untold Story of the Bitcoin White Paper]]></title>
            <link>https://medium.com/coinmonks/the-untold-story-of-the-bitcoin-white-paper-d6524c0355ed?source=rss-8498e40d416------2</link>
            <guid isPermaLink="false">https://medium.com/p/d6524c0355ed</guid>
            <category><![CDATA[cryptocurrency-news]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[bitcoin]]></category>
            <category><![CDATA[bitcoin-news]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Seres István András]]></dc:creator>
            <pubDate>Tue, 23 Feb 2021 13:44:51 GMT</pubDate>
            <atom:updated>2021-02-25T10:41:29.582Z</atom:updated>
            <content:encoded><![CDATA[<h4>Satoshi Nakamoto and his early rejection from an academic conference in 2008. Stories from a parallel universe.</h4><p>Many of us know the <a href="https://bitcoin.org/bitcoin.pdf">Bitcoin White Paper</a> inside out. It is a landmark work and achievement. It was the very document that spearheaded the launch of the <a href="https://blockstream.info/">Bitcoin network</a> and its digital currency, the bitcoin — which has recently <a href="https://www.coindesk.com/bitcoin-1-trillion-market-value">reached $1 trillion dollar market value</a>. However, only a few have heard about the peculiar and painful story of the Bitcoin White Paper as an academic work. After completing the writing of his groundbreaking work in 2008, Satoshi Nakamoto attempted to publish his paper at <a href="https://en.wikipedia.org/wiki/Association_for_Computing_Machinery">ACM</a> CCS. The Computer and Communications Security Conference (<a href="https://dl.acm.org/conference/ccs">CCS</a>) is one of the most prestigious venues for advances in computer science.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/0*xqw1zDHodAxB-C0I.jpg" /><figcaption>The ACM CCS 2008 poster. Satoshi Nakamoto released the Bitcoin White Paper on the very last day of the conference. Would it be a coincidence?</figcaption></figure><p>Satoshi wished to validate his extraordinary ideas before the implementation and broader release of Bitcoin to the world. To that end, he submitted his work on Bitcoin to the ACM CCS’08 program committee. He firmly believed in the <em>power and justice</em> of the <a href="https://en.wikipedia.org/wiki/Scholarly_peer_review">peer-review</a> process. He eagerly wished to have more vigilant and sharp eyes on his unprecedented work. In the end, maybe he made a mistake or he might have left an unrecoverable error in his system’s design. He was languorously looking forward to learning fellow highly regarded scholars’ opinions and constructive comments on his proposal for a peer-to-peer electronic cash system.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*6AINFYljboF7RmAz.jpg" /><figcaption>Pictures from a CCS conference. A vibrant and unique professional community</figcaption></figure><p>After agonizing months of waiting for the insightful CCS reviews, Satoshi finally received 3 thorough reviews from the best minds of his field. With trembling hands, he clicked on the incoming e-mail from the CCS program committee. He started to read the reviews with flutter.</p><p>On behalf of the program committee, we regret to inform you that your submission <strong>#6102</strong> titled “<strong><em>Bitcoin: A Peer-to-Peer Electronic Cash System</em></strong>” will not be included in the ACM Conference on Computer and Communications Security (ACM CCS) 2008.</p><h4>Reviewer A.</h4><p>This decentralized electronic cash proposal might eventually work, but it completely lacks a grounded security analysis! The authors should define proper ideal functionalities, preferably in the <a href="https://en.wikipedia.org/wiki/Universal_composability">Universal composability framework</a>, and then they should subsequently prove that the proposed Bitcoin protocol achieves the claimed security properties. Without such a formal analysis, I simply can’t accept the work for this scholarly venue.</p><p>Another blazing issue is that of anonymity. The authors seem to overlook the power of transaction graph analysis. The alleged anonymity part of the paper especially needs to be revised! Physical cash would provide higher levels of financial privacy than this easily traceable digital cash. I doubt if any privacy-focused person would ever want to use this currency for any privacy-critical transaction. However, maybe, with some clever techniques, one might enhance financial privacy by obscuring transactions in the transaction graph? Sadly, this line of thinking was not pursued in the paper.</p><p>While the problem tackled by the paper is indeed interesting, the paper falls especially short when outlining its contribution when compared to other digital money proposals used in the literature.</p><p><strong><em>Overall merit: Reject and resubmit</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/945/0*Jb0csiZkDXOhw82_.png" /></figure><h4>Reviewer B.</h4><p>The scientific contribution of this paper — if there is any at all — is at best hopelessly insignificant. It seems more like a trivial extension of <a href="https://en.wikipedia.org/wiki/Hashcash">Hashcash</a>. Moreover, Hashcash is already known to be a dead end. I don’t see much science in this manuscript.</p><p>The purported one-CPU-one-vote property of the <a href="https://en.wikipedia.org/wiki/Proof_of_work">proof of work</a> mechanism looks overly idealistic. Why does not the author analyse the possibility of people amassing a tremendous amount of CPUs for the sole purpose of mining new bitcoins? Such a group of people could potentially subvert this brittle decentralized financial network.</p><p>Overall, the paper is very poorly written.</p><p><strong><em>Overall merit: Reject</em></strong></p><h4>Reviewer C.</h4><p>This paper is so badly written I could barely get through it.</p><p>For instance, a crucial blunder: the block size and other stated parameters of the system (e.g., the 10-minute block interval) are effectively left unjustified. The authors in the title promised to deliver an electronic cash system. Small blocks of transactions arriving every 10 minutes do not seem to provide sensible throughput for this “cash” system. But this is just one example. The paper abundances in such grey areas.</p><p>The analysis of the double-spend attack at the end of the paper is extremely simplistic. Indeed, by the end of the paper, the reader is left with a feeling of ‘so what now’?</p><p><strong><em>Overall merit: Reject</em></strong></p><p>Years after years, Satoshi Nakamoto maybe even up to this very day tries to publish his digital cash system in a top-tier computer science conference. He rewrote the Bitcoin white paper dozens of times. For every submission, he chooses a different pseudonym to get his ingenious digital cash paper into the most prestigious computer science conferences in the world. However, his scholarly success yet remains to be seen.</p><h4><strong>Disclaimer</strong></h4><p>Note, that this piece is purely fictional. Luckily, Satoshi Nakamoto did not even try to submit the Bitcoin White Paper to <em>any</em> conference. He just proactively implemented his ideas and released them to the world. <em>Maybe, if he had submitted his work, we would have never seen Bitcoin in the first place?</em></p><p>Btw, for an even more comprehensive list of errors in the Bitcoin White Paper, see <a href="https://gist.github.com/harding/dabea3d83c695e6b937bf090eddf2bb3">this list</a> by David A. Harding or <a href="https://www.coindesk.com/what-bitcoins-white-paper-got-right-wrong-and-what-we-still-dont-know">this one</a> by Joseph Bonneau.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d6524c0355ed" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/the-untold-story-of-the-bitcoin-white-paper-d6524c0355ed">The Untold Story of the Bitcoin White Paper</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[AZTEC vs PGC or the quest for confidential transactions]]></title>
            <link>https://istvan-a-seres.medium.com/aztec-vs-pgc-or-the-quest-for-confidential-transactions-d137a0e4f7ed?source=rss-8498e40d416------2</link>
            <guid isPermaLink="false">https://medium.com/p/d137a0e4f7ed</guid>
            <category><![CDATA[privacy]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Seres István András]]></dc:creator>
            <pubDate>Mon, 15 Jul 2019 15:00:34 GMT</pubDate>
            <atom:updated>2019-07-15T15:00:34.981Z</atom:updated>
            <content:encoded><![CDATA[<p>One of the main impeding obstacles to mass adoption for many public blockchains (apart from scalability and usability) is the total <a href="https://ethresear.ch/t/privacy-anonymity-on-ethereum-is-doomed/5430">lack of privacy</a>. Since the transaction graph is public, anyone can easily cluster blockchain addresses and possibly link them to users (social media accounts (Reddit, Twitter etc), email or IP addresses). In this article I briefly review and compare <a href="https://github.com/AztecProtocol/AZTEC/blob/develop/AZTEC.pdf">AZTEC</a> and <a href="https://eprint.iacr.org/2019/319.pdf">PGC</a>, two recent proposals to achieve confidential transactions on Ethereum.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/846/1*nqohxKqpiX2Exj-iew_GmQ.jpeg" /></figure><p><strong>Confidential transactions</strong> are transactions where the transferred amounts are “hidden”, however the validity of the transaction still remains publicly verifiable (i.e. no money is created out of thin air). Although they do not provide anonymity per se, unlike Monero and ZCash, that provides confidentiality AND anonymity, confidential transactions are an important first step in the right direction and in some use cases it is not even desired to hide the identity of the parties, rather just transacted amounts to retain them as business secrets.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*g4eJSQ7XAqyKt4rFPBL8iQ.jpeg" /></figure><p>Without doubt, the flagship of these <a href="https://github.com/ethereum/EIPs/issues/1724">proposals</a> is the <a href="https://www.aztecprotocol.com/">AZTEC</a> protocol (Anonymous Zero-Knowledge Transactions with Efficient Communication), created and invented by <a href="https://twitter.com/Zac_Aztec">Zachary Williamson</a>. First, Zac proposes a novel perfectly hiding and computationally binding commitment scheme, which is tailored to admit efficient range proofs. Afterwards he defines the Joinsplit protocol and a NIZK (non-interactive zero-knowledge) proof system to prove the correctness of Joinsplit transactions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pBoAzdFqOT_8Anm4BxOOGA.png" /></figure><p>What are Joinsplit transactions? AZTEC represents money as notes, one might think of them as UTXOs (unspent transaction outputs). In a Joinsplit transaction input notes are destroyed and output notes are created in equal amount, in a way that the values of these notes remain encrypted. More precisely, both input and output notes are <em>commitments</em> to the value these notes represent. A novel NIZK proof system is introduced in AZTEC to prove that the commitments in a Joinsplit transaction are well formed (the transaction originator can open the commitments) and the sum of input notes equal to the sum of output notes. Zac shows in the AZTEC paper that the proposed proof system achieves perfect completeness, special soundness and special honest verifier zero-knowledge in the random oracle model under the q-Strong Diffie-Hellman (SDH) assumption.</p><p>AZTEC’s efficiency comes at a price. It relies on a trusted setup, whose protocol details are not public yet, although I encourage anyone to participate in the trusted setup once the trusted setup MPC date and protocol details are known. Basically in the trusted setup, participants need to create Boneh-Boyen signatures on all the numbers in the interval [0..2³²-1] in a way, that the secret signing key is additively shared among participants and no participant knows the secret key in its entirety. The number 2³²-1 is defined in the protocol as the highest representable AZTEC note denomination.</p><p>Another remarkable proposal is <strong>Pretty Good Confidential </strong>transaction system with accountability<strong> </strong>also known as <a href="https://eprint.iacr.org/2019/319.pdf">PGC</a> by Yu Chen and Xuecheng Ma. It takes a different approach than AZTEC and therefore offer an interesting set of tradeoffs. They deliberately focus on creating a confidential transaction system which does not rely on a trusted setup and only assumes classis cryptographic assumptions, such as the Decision Diffie-Hellman (DDH) assumption. Moreover PGC clients do not need to be stateful, i.e. they do not need to necessarily track the value of their confidential notes.</p><p>Similarly to AZTEC, PGC also introduces its own Sigma-protocol ZK proof system in order to prove the validity and correctness of PGC transactions. Interestingly enough it only uses fairly standard cryptographic building blocks: ElGamal encryption, Chaum-Pedersen proofs (equality of discrete logs) and Bulletproofs (range proof). PGC only allows simple value transfers, namely there can only be a single sender and a single receiver. Unfortunately, they did not enclose an implementation of PGC, so we can only refer to the following comparison:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*hstt8_S0-xb0Ljjts8VRvQ.png" /><figcaption>For AZTEC, <strong>n</strong> is the number of total AZTEC notes in the Joinsplit transaction, while <strong>m</strong> denotes the number of input notes</figcaption></figure><p>The equivalent of a PGC transaction is a 1-to-2 Joinsplit transaction. Therefore verifier costs are (9 addition+6 multiplication+1 pairing) vs (8 addition+14 multiplication), while proof sizes are (6 group elements+6 scalars) vs (22 group elements+16 scalars). Such an AZTEC transaction costs around 620,000 gas while a back-of-the-envelope calculation for PGC indicates 285,000 gas. Note, that PGC does not need to use the pairing friendly <em>altbn128</em> curve, it can just operate on the <em>secp256k1</em> curve, where for one can have elliptic curve multiplication for 10,000 gas using <a href="https://ethresear.ch/t/you-can-kinda-abuse-ecrecover-to-do-ecmul-in-secp256k1-today/2384">Vitalik’s trick</a>.</p><p>I’m really looking forward to see evolving AZTEC and its cryptography engine, which will greatly advance the implementation and use of confidential assets on Ethereum.</p><p>I would also be happy to see other confidential/anonymity protocols to gain more attraction in order to explore better the tradeoff space around privacy-enhancing solutions. Let me know if anyone is thinking about implementing PGC or if anyone have some ideas how to create a generic, efficient, confidential assets on Ethereum without trusted setup.</p><p>I’m grateful to <a href="https://twitter.com/OmerShlomovits">Omer Shlomovits</a>, founder of <a href="https://zengo.com/">KZen</a>, for insightful comments and proofreading! You can also reach out to me, <a href="https://twitter.com/Istvan_A_Seres">here</a>!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d137a0e4f7ed" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The future of sports betting]]></title>
            <link>https://medium.com/cryptodigest/the-future-of-sports-betting-fb8f5a215c67?source=rss-8498e40d416------2</link>
            <guid isPermaLink="false">https://medium.com/p/fb8f5a215c67</guid>
            <category><![CDATA[opinion]]></category>
            <category><![CDATA[betting]]></category>
            <category><![CDATA[world-cup]]></category>
            <category><![CDATA[gambling]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Seres István András]]></dc:creator>
            <pubDate>Fri, 06 Jul 2018 12:16:25 GMT</pubDate>
            <atom:updated>2018-07-09T03:30:30.437Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Blockchains and cryptocurrencies offer a huge potential to, among others, betting and gambling. In 2018, could we bet on the FIFA world cup in a decentralized, trustless manner? Are we there yet? Let’s find out together!</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*m7y9omxYyVRrbY85eQ0gfg.jpeg" /></figure><h3>Preface</h3><p>Last weekend I participated at the <a href="https://binarydistrict.com/workshop/master-workshop-off-the-chain/">#offthechain master workshop</a> organized by <a href="https://twitter.com/BinaryDistrict">Binary District</a> in Berlin. This was an amazing two-day event focusing on state channels and second layer solutions. Although I had to skip some thrilling world cup matches, the fascinating talks about <a href="https://www.youtube.com/watch?v=sUxh6wO_Z00&amp;t=563s">Lightning Network</a>, <a href="https://www.teechain.network/">payment networks</a> and <a href="https://www.youtube.com/watch?v=oxxnrN97F2o&amp;t=40s">oracles</a> abundantly compensated me. We also had the chance to enjoy some demos such as the one about <a href="https://funfair.io/">Funfair</a>, which is a transparent and provably fair casino *using Ethereum state channels*. It’s pretty cool isn’t it!</p><p>After those two days I became confident that we already have the technology to create a decentralized trust-minimized betting platform. I also wanted to play and bet a little bit so I began to investigate what my options are. Honestly the current standing does not look bright at all. However we could easily fix this. I show you how. ;)</p><h3>State of the “art”</h3><p>I wanted to bet on some FIFA world cup games in Ether, therefore I explored some dapps on <a href="http://www.stateofthedapps.com/">www.stateofthedapps.com</a>. The cornerstone of every betting dapp is the way how they connect their smart contracts with the off-chain world. Sadly all the solutions I saw are pretty flawed.</p><h4>Parallel World Cup</h4><p>This idea of this <a href="https://www.parallelworldcup.com/">dapp</a> is quite nice actually: all the teams are represented by an ERC721 non-fungible token and these tokens can be traded among players. One can purchase a team if she is willing to pay higher amount than the current owner. In this case the current owner loses her deposit. At the end of the world cup the owner of the token representing the winner team is going to take all the money in the contract. This is a classic <a href="https://en.wikipedia.org/wiki/Ponzi_scheme">Ponzi game</a>, nothing wrong with that. Actually this could be a pretty good game and then you see how they set the winner of the tournament. Ewww.</p><pre>function awardprize(uint256 _itemId) <strong>onlyOwner()</strong> public{<br>    uint256 winneramount;</pre><pre>winneramount = this.balance;</pre><pre>if (ownerOf(_itemId) != address(this))<br>    {<br>      //winner gets the prize amount minus developer cut<br>      ownerOf(_itemId).transfer(winneramount);<br>    }<br>}</pre><p>Basically the contract owner will set on its own which team won the world cup. This implies you would need to trust in an unknown person, who could easily steal your money. This smells massive fraud. Just because this contract is deployed on the blockchain it does not mean that functionally it is not centralized. Parallel World Cup is no better than <a href="https://sports.bwin.com/hu/sports">bwin</a> or <a href="https://www.bet365.es/es/">bet365</a> by any means. Do <strong>NOT</strong> put any ether in the <a href="https://etherscan.io/address/0x7e4a4e42fca1c6527e8d373320299893e5a396e9#code">Parallel World Cup contract</a>.</p><p>There are some other live betting platforms on the Ethereum main net such as <a href="https://etherscan.io/address/0xFEF1595DA2BBa952FE13003dcE7Ad32d991c6e2F#code">CryptoCup</a>, <a href="https://www.stateofthedapps.com/dapps/cryptoworldcup">CryptoWorldCup</a> or <a href="https://www.stateofthedapps.com/dapps/ethsoccer">Ethsoccer</a>. However they suffer from exactly the same flaw as the one we’ve just seen before. So they are just as useless as Parallel World Cup.</p><p>Can we do better? Could we connect a smart contract with the outside world in order to get the result of a football match in a trust-minimized way? Do we have the technology for this. Luckily, the answer is yes.</p><h3>A potential solution</h3><p>In order to minimize the trust required for feeding data into the walled garden of our betting contract one could use an oracle service. I’ve chosen to use <a href="http://www.oraclize.it/">Oraclize</a>, since currently Oraclize is the most usable, well-tested and documented oracle service. But what are oracles at all?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CgOHUAtsfXl3GNTIhCPH-Q.jpeg" /><figcaption>Thomas Bertani, CEO of Oraclize, at the #offthechain workshop (picture from<a href="https://twitter.com/tobdea"> Tobia de Angelis</a>)</figcaption></figure><p>Oracles are data carriers for decentralized apps. They enable smart contracts to fetch external data on their own. External data could come from any web API or website. Correct behaviur of oracles are usually enforced by cryptographic proofs such authenticity proofs. These proofs guarantee that the oracle did not tamper with the requested data. Authenticity proofs can either be verified by the smart contract itself or off-chain.</p><p>Now we can connect our smart contract with the off-chain world. This is clearly not a trustless solution, since you rely on your data source for availability and trustworthiness. Here is the proof of concept smart contract code I wrote. You can grab it and play with your friends. This contract lets you bet on the Brazil vs Belgium quarter-final but you can easily generalize and adapt the contract to any other match.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1a48e1c34c6af1557cd4ba0b4fc38672/href">https://medium.com/media/1a48e1c34c6af1557cd4ba0b4fc38672/href</a></iframe><p>Teams are represented by their official FIFA id used by the FIFA API. Players can bet on both sides as much eth as they like. Gamblers who betted on the winner team are able to withdraw their betting plus some amount from the loser team’s pot proportional to their bet divided by the winner team’s total pot.</p><p>The winner team is set by calling the Oraclize smart contract which in turn calls off-chain the official FIFA API. The result of this off-chain API call is sent back to the <strong><em>_callback()</em></strong> function called by the Oraclize smart contract.</p><p>If the winning team is set, users are able to withdraw their rewards from the betting contract.</p><p>Unfortunately Oraclize smart contract is not able to return integers, therefore one need to store the FIFA ids as strings. Furthermore it is not possible to compare strings in Solidity, because they are dynamically-sized variables, therefore first one needs to hash them in order to be able to check the equality of two strings, in our case FIFA ids.</p><p>A possible extension of this contract could be to deploy more than one data sources, this way mitigating the risk if one of them is not available or faulty.</p><h3>Alternative solution: Schelling point</h3><p>Another, maybe even better solution would be to use Schelling points also known as focal points. Vitalik wrote a <a href="https://blog.ethereum.org/2014/03/28/schellingcoin-a-minimal-trust-universal-data-feed/">fascinating blog post</a> about Schelling points on Ethereum a while ago. The main idea of such an approach would be that basically gamblers themselves could be their own oracles. They should set on their own who won the pending match. People would signal to the betting contract who won the match with some ETH as deposit and the team which has the majority of the votes would be regarded as winner. All those who signalled the “wrong” team forfeits their deposit. Why does this scheme work?</p><blockquote>Everyone wants to provide the correct answer because everyone expects that everyone else will provide the correct answer and the protocol encourages everyone to provide what everyone else provides. (Vitalik)</blockquote><p>Obviously this scheme has also its own limitations and problems as Vitalik pointed out. One of these drawbacks is that, trivially, if there is an entity who controls the majority of the votes, it could unilaterally fake the signaling if the result of the match is not in its favor. This could be somewhat mitigated by requiring huge deposits for the signalling.</p><p>To analyse in depth the implications of using a Schelling scheme in such a scenario is left for another post.</p><h3>Aftermath</h3><p>IMHO currently this is close to the best what we can achieve as regards blockchain-based betting platforms. Let me know if you have any other ideas to improve this contract or any other idea on betting platforms.</p><p>If you want to know more about my upcoming blockchain-related projects, follow me on <a href="https://medium.com/@Istvan_A_Seres">Medium</a> or <a href="https://twitter.com/Istvan_A_Seres">Twitter</a>. Strive for more, keep #buidl!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fb8f5a215c67" width="1" height="1" alt=""><hr><p><a href="https://medium.com/cryptodigest/the-future-of-sports-betting-fb8f5a215c67">The future of sports betting</a> was originally published in <a href="https://medium.com/cryptodigest">CryptoDigest</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solidity at its best: an appetizer for the 1st Solidity Gas Golfing Contest]]></title>
            <link>https://medium.com/coinmonks/solidity-at-its-best-an-appetizer-for-the-1st-solidity-gas-golfing-contest-56f394a053c3?source=rss-8498e40d416------2</link>
            <guid isPermaLink="false">https://medium.com/p/56f394a053c3</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[solidity]]></category>
            <category><![CDATA[gas]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Seres István András]]></dc:creator>
            <pubDate>Thu, 14 Jun 2018 08:09:26 GMT</pubDate>
            <atom:updated>2018-06-22T15:21:04.004Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*Ppe_m8tyjBGk9KuoE96K_g.jpeg" /></figure><p><em>This article will help you to solve a classical programming exercise in Solidity and teach you a few tricks how you can save some gas while developing Solidity smart contracts</em></p><p>The most fun way to learn and improve your coding skills is to solve challenging exercises. The Ethereum community regularly organizes <a href="https://ethglobal.co/">hackathons</a> and competitions to gather smart contract developers together. Personally my favourite ones were the contests organized by Ethereum’s <a href="https://twitter.com/nicksdjohnson">Nick Johnson</a> so far.</p><p>Last year there was an amazing <a href="http://u.solidity.cc/">Underhanded Solidity Coding Contest</a>, where the goal was to put hard-to-detect vulnerabilities in ICO contracts that could be exploited to enrich the project creators. Several fascinating solutions were <a href="https://medium.com/@weka/announcing-the-winners-of-the-first-underhanded-solidity-coding-contest-282563a87079">submitted</a> presenting vulnerabilities I could possibly never thought of.</p><p>This year the goal is to solve classical programming tasks in Solidity with as little gas as possible. <a href="https://g.solidity.cc/">The contest</a> contains 5 exercises: integer sorting, creating a BrainFuck interpreter, a Hex decoder, a string search and removing duplicate elements from a list. If you want to start with the integer sorting exercise <a href="https://blog.cotten.io/thinking-in-solidity-6670c06390a9">Tim Cotten</a> already wrote a superb writeup I highly recommend. I also would like to guide you through my journey with the last exercise and show you what I’ve learnt along the way. Hopefully this will encourage you to have a look at the other exercises and get your hands dirty with some Solidity coding ;)</p><h3>Setup</h3><p>I’m a big fan of <a href="https://github.com/trufflesuite/truffle">Truffle</a>, so I use the Truffle project version of the contest, available <a href="https://github.com/Arachnid/sggc">here</a>. It is pretty convenient to jump into the contest. After writing some code you can quickly test whether your solution passes all the test vectors with the command truffle test test/Unique.js .</p><h3><strong>Challenge #5: Remove duplicate elements</strong></h3><p>The problem is pretty simple: write a smart contract in Solidity which removes all but the first occurrence of each element from a list of integers, preserving the order of original elements, and returns the list. Moreover the input list may be of any length.</p><h3>Naive solution</h3><p>I wanted to start with a simple and dumb solution just to have something as a benchmark. A straightforward idea is the following.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bb93dc7dc178966f8ac8baba0b462181/href">https://medium.com/media/bb93dc7dc178966f8ac8baba0b462181/href</a></iframe><p>Return every input array whose length is less than 2 since they are already free of duplicates. Afterwards let’s use a separate bool array to track which element is duplicate. This piece of code uses a nested loop which is highly inefficient. It gives us an <strong>O(n²) </strong>algorithm if <strong>n</strong> is the length of the input array. It may seem odd that we copy the unique[] array to a unique2[] array. The reason for this is that it is not possible in Solidity to resize arrays in memory. After testing this naive solution we see that we pass test vector 0 and 1: an empty array and a one element array… SO MUCH WIN! However for most of the test vectors it will just run out of gas. This initial failure suggests that we should aim for a <strong>O(n)</strong> algorithm. Can we find all the duplicates if we are allowed to iterate over the array only once? OFC!</p><h3>Hash tables</h3><p>The natural idea is not to compare the integers themselves rather a transformation of theirs. So let’s map all the elements into slots where different elements are mapped to different slots, while same elements obviously reside in the same slot. <a href="https://en.wikipedia.org/wiki/Hash_table">Hash tables</a> are a perfect match for this very task. When we iterate over the array we take an integer, hash it and map the integer to a key value computed from its hash. Detecting duplicates becomes easy because if there are duplicates of an integer then we would map that integer multiple times to the same slot.</p><h4>Open addressing</h4><p>Even if a cryptographically secure hash function is applied, it can easily happen that two integers are assigned to the same slot. This is called collision. In our case this is clearly unwanted since two different integers are mapped to the same slot giving us to believe that they are duplicates although they are not. All in all such collisions must be accomodated some way. One of the hash collision resolution technique is open addressing.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dd6c94d481f3bf65a3f25bdb251a2df4/href">https://medium.com/media/dd6c94d481f3bf65a3f25bdb251a2df4/href</a></iframe><p>The intuition is that whenever such a collision occurs we simply iterate in the key space as long as we find an empty slot (“key”). The integer is inserted in the first unoccupied slot. Here there is an inherent computational time/space trade-off. As the number of slots, key space, increases number of collisions decreases. Similarly if the key space gets smaller, hash collisions will be more likely. An unsophisticated and unoptimized implementation of an open addressing hash table can be found above. This passes all the test vectors and burns 1149096 gas.</p><p>How could we improve the efficiency of this solution? Let’s use a more efficient hash function. We do not need sha3 , a cryptographic hash function, for our purposes mod is also perfectly fine as it mixes numbers fairly well. So if we compute the key simply by uint hash = input[i] % lengthOfKeySpace we save 113380 gas.</p><p>Instead of the % operator we should calculate the remainder with bitwise operators seeing that bitwise operators are closer to the machine code. As one can observe in the <a href="http://yellowpaper.io/">Ethereum yellow paper</a> one mod costs 5 gas, while a bitwise and costs only 3 gas. If the modulus is a power of 2, n mod k can be also given as n &amp; (k-1) . Therefore let lengthOfKeySpacebe 256 which is a power of 2. Calculating the modulo with bitwise and yields another 46903 gas saving.</p><p>Hmmm… 989623 gas??? This is still way too much! What if we apply a different collision resolution technique?</p><h4>Separate chaining</h4><p>Another common collision resolution technique is separate chaining. The idea is that each slot is independent and at each slot there is a separate list. Whenever we encounter a collision at a certain slot, we just push the to-be-inserted integer at the end of the list. Often the list is implemented as a linked list.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/372/1*Cw6y5UATtLqEYZnUYJK7EA.gif" /><figcaption>A visual explanation for separate chaining</figcaption></figure><p>The time for hash table operations is the time to find the slot, which is constant, plus the time for the list operation. In a good hash table, each bucket has zero or one entries, and sometimes two or three, but rarely more than that. Therefore, structures that are efficient in time and space for these cases are preferred. As the load factor (in our case the number of integers in the input list per the number of slots) increases separate chaining becomes faster in comparison to open addressing. The reason for that is if the hash table is dense, then collisions are more likely, thus one needs to iterate more over the hash table to find an open address. Contrarily separate chaining does not use iteration to resolve collisions, it uses only one fast operation, namely an appending at the end of the slot’s list.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7e14b281f19b75d3f1226d3fe7d32c52/href">https://medium.com/media/7e14b281f19b75d3f1226d3fe7d32c52/href</a></iframe><p>Separate chaining indeed proves to be more efficient than open addressing. This gives us altogether 957787 gas consumption on the truffle test vectors. On the secret test vectors of the contest our separate chaining solution consumes 792960 gas. Okay, we could omit those assignments, where we assign 0 to the hashTable or index since the EVM initializes all data structures with their default values, this is 0 in case of integer arrays. We could also make the code a little faster by using prefix increments instead of postfix increments. But all in all this does not give more than 5136 gas saving. We are not there yet! One might say this is storm in a teacup: we are still far from being on the leaderboard for this task. Currently the fastest solution only burns 309063 gas. Ouch!</p><p>Can you beat it? Challenge accepted!</p><h3><strong>Notes</strong></h3><p>As you can see we are still far from being on the leader board with this version so intentionally left some space for improvement with this one. I hope you enjoyed this ride and now you have the courage and appetite to start coding some nifty smart contracts in Solidity.</p><p>I do not want to spoiler too much but I give you some hints, how you could make your entry more efficient.</p><ol><li>Keep in mind that only the uniquify() function’s gas cost is taken into account.</li><li>I just leave this here: <a href="https://gastoken.io/">https://gastoken.io/</a> If you know what I’m saying ;)</li><li>Always clean up after yourself! :)</li></ol><p>Credit goes to <a href="https://medium.com/@Csyk">Balázs Paulcsik</a> for his <a href="https://twitter.com/Csyk01">ideas</a> and support!</p><h3>Keep it up!</h3><p>Let me know how you solved this challenge or if you have other more efficient approaches to solve this task. I would like to hear about those ideas ;)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*UZLj4yUiEPOE01ZJgqLrlw.jpeg" /><figcaption>Keep going and happy gas golfing!</figcaption></figure><p>If you want to know more about my upcoming blockchain-related projects, follow me on <a href="https://medium.com/@Istvan_A_Seres">Medium</a> or <a href="https://twitter.com/Istvan_A_Seres">Twitter</a>. Strive for more, keep #buidl!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=56f394a053c3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/solidity-at-its-best-an-appetizer-for-the-1st-solidity-gas-golfing-contest-56f394a053c3">Solidity at its best: an appetizer for the 1st Solidity Gas Golfing Contest</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implementing an e-voting protocol with blind signatures on Ethereum]]></title>
            <link>https://medium.com/coinmonks/implementing-an-e-voting-protocol-with-blind-signatures-on-ethereum-411e88af044a?source=rss-8498e40d416------2</link>
            <guid isPermaLink="false">https://medium.com/p/411e88af044a</guid>
            <category><![CDATA[digital-signatures]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[e-voting]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <dc:creator><![CDATA[Seres István András]]></dc:creator>
            <pubDate>Tue, 22 May 2018 13:00:40 GMT</pubDate>
            <atom:updated>2018-12-10T09:30:41.870Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/635/0*-sOaKkBVyv8IjRii." /><figcaption><a href="https://www.brennancenter.org/blog/restore-ex-felons-voting-rights-its-right-thing">Source</a></figcaption></figure><p>Electronic voting has been a <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.295.7959&amp;rep=rep1&amp;type=pdf">vivid research field</a> for the past few decades, aiming at designing and implementing cryptographic protocols to overcome numerous shortages of traditional paper-based voting systems that is lack of verifiability, error-proneness and high expenses. (Remote) electronic voting systems have the potential to provide a trust-minimized, environmentally friendly, economical and less error-prone platform for voting.</p><p>Prior to the invention of blockchain, electronic voting protocols <a href="https://www.usenix.org/legacy/event/sec08/tech/full_papers/adida/adida.pdf">relied on a public bulletin board</a> for storing census, votes, cryptographic (Zero-knowledge, Shuffle, Schnorr, decryption etc.) proofs and other supplemental data. Public bulletin boards have been generally <a href="https://www.cs.cornell.edu/projects/civitas/papers/clarkson_civitas_tr.pdf">implemented as relational databases</a>, that do not provide data integrity and transparency. This implies that such e-voting platforms are essentially centralized systems, where in order to attain certain security properties (availability, data integrity and privacy) one needs to trust the public bulletin board. Such centralized point of failure could be amended by applying blockchain as a decentralized public bulletin board.</p><p>Blockchain-based e-voting protocols alleviate the above-mentioned security issues by deploying blockchain as the bulletin board; attaining data integrity, transparency, increased availability and fault-tolerance. However this usually comes at an <a href="https://eprint.iacr.org/2017/110.pd">unbearable computational complexity</a> and <a href="https://www.dgalindo.es/mscprojects/yifan.pdf">limited scalability</a>.</p><p><strong>Our contrbutions:</strong> We present the first practical and <a href="https://github.com/itblockchain/evoting">scalable implementation </a>of <a href="https://eprint.iacr.org/2017/1043.pdf">this protocol</a> which uses blind signatures to verify ballots. Security analysis of the implementation and computational breakdown of its execution cost are also elaborated. Our implementation is <a href="https://github.com/seresistvanandras/evoting">publicly available at github</a> and one could inspect the <a href="https://rinkeby.etherscan.io/address/0xa87cd09c77b47c8bd0ad4b6b7af0ea9ce735e36b">contract on Ethereum’s test network</a>.</p><h4><strong>Related work</strong></h4><p>Straightforward blockchain-based <a href="https://www.ethereum.org/dao">e-voting protocols</a> solely use the blockchain to record individual votes on it and calculate the tally with the aid of a smart contract’s code. Although these solutions are practical and as scalable as the underlying blockchain itself, they do not provide ballot secrecy which is a crucial, essential property, moreover declared to be a <a href="http://www.un.org/en/universal-declaration-human-rights/index.html">human right</a>.</p><p>Ballot secrecy, self-tallying and anonymous voting are achieved by the <a href="https://pdfs.semanticscholar.org/e57b/12f582b5f18c197965971fb3d4ef6946e10f.pdf">Open Vote Network (OVN) protocol</a>, which was <a href="https://eprint.iacr.org/2017/110.pdf">first implemented</a> as an Ethereum smart contract by Patrick McCorry et al. The protocol’s main disadvantage is that the computational cost of casting a vote is <strong>O(n)</strong>, where <strong>n</strong> is the number of voters. This renders the implementation essentially unsuitable for conducting elections with more than a few dozens of voters, since on the Ethereum network one can only put bounded number of computational steps in a nascent block and this limit is soon reached after cca. 40–50 voters. Another drawback of the protocol is that the last voter is able to compute the final tally before anyone else and can act (vote or abort) accordingly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/807/1*TP5nMBUOeYX-nsnaSm__iw.png" /><figcaption>Comparing various protocols by crucial (e-)voting related properties</figcaption></figure><p>Blind signatures were <a href="https://allquantor.at/blockchainbib/pdf/chaum1990untraceable.pdf">first suggested by David Chaum</a>. In subsequent papers e-voting has been one of the main use cases for where blind signatures <a href="https://people.csail.mit.edu/rivest/voting/papers/Chaum-SecretBallotReceiptsTrueVoterVerifiableElections.pdf">had been applied</a>. Blind signatures are a robust solution to attain voter authorization while maintaining anonymity. The first blockchain-based e-voting protocol which uses blind signatures <a href="https://eprint.iacr.org/2017/1043.pdf">was suggested in 2017</a>. As a result of applying blind signatures the protocol provides voter (pseudo-)anonymity (pseudo, since the nature of blockchain), while the complexity of casting a vote is <strong>O(1)</strong>. Prior to an Ethereum protocol update in October 2017, verifying blind signatures were not practical. <a href="https://blog.ethereum.org/2017/10/12/byzantium-hf-announcement/">After the update</a>, however, using elliptic curve operations are feasible, allowing efficient on-chain verification of elliptic curve digital signatures.</p><h3>An e-voting protocol with blind signatures on Ethereum</h3><p>The blind signature protocol enables a voting scheme to dissociate the vote from the voter, while still maintaining authentication. Hereby a short recap of <a href="https://eprint.iacr.org/2017/1043.pdf">the e-voting protocol</a> is presented, before discussing its smart contract implementation on Ethereum.</p><p>There are three types of actors in the protocol: <br><br><strong><em>Voters:</em></strong> the set of all eligible voters.<br><strong><em>Organizers:</em></strong> the set of election organizers, whose task is to register eligible voters and interact with them (blindly sign votes) throughout the course of the voting.<br><strong><em>Inspectors:</em></strong> the set of parties which are meant to be on the lookout for organizers’ actions in order to limit their power. They also interact with voters, potentially they could be also added to blindly sign votes.</p><p>Let Alice be a voter, Bob be an organizer, Carol be an inspector.<br>The implemented protocol has three phases:</p><p><strong><em>Pre-voting phase</em>:</strong> Alice registers herself as an eligible voter via a channel provided by Bob. After successful registration Bob puts Alice in the <strong>Voters</strong> set. At the end of this phase, the <strong>Voters</strong> set is made public for inspection.<br><strong><em>Voting phase:</em></strong> Alice requests blind signatures on her vote from organizers and inspectors. After receiving blind signatures from those parties, Alice sends her vote in clear text with the blind signatures from a freshly generated blockchain address. <br><strong><em> Post-voting phase:</em></strong> the protocol is self-tallying, ie. anyone is able to compute the tally once all ballots are cast. One needs to check whether signatures on the ballots are verified or not. If all signatures are verified, then it should be counted in the final tally, otherwise not.</p><p><strong>Design choices</strong></p><p>The Ethereum blockchain was chosen to implement the protocol, since in contrast to Bitcoin it is not only able to store data, but it is also capable of enforcing the protocol’s correct execution due to its programmable nature. An election smart contract is used to facilitate the protocol’s proceeding. Source code is available <a href="https://github.com/itblockchain/evoting">here</a>.</p><p>The issuing of blind signatures can not take place in an Ethereum smart contract, since for calculating the blind signature administrators and organizers need to provide their private keys. Due to the transparent nature of the EVM’s execution environment, those parties are unable to sign ballots without revealing their private signing keys. Therefore only the signatures’ verification can be carried out on chain.</p><h4>Blind signature verification on Ethereum</h4><p>Before including each ballot in the final tally, blind signatures are verified by the election smart contract. Ballots are included in the final tally if and only if blind signatures on the ballots are verified.</p><p>Several algorithms could have been used for implementing blind signatures. The first and most obvious choice would have been to use RSA blind signatures. Since the maximum word size of the EVM is 256-bits and currently there is not any secure, fast and cost-efficient way to use larger integers on top EVM, one would need to use 256-bit long blind signatures, which is clearly insecure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/726/1*-3aKQn6irCup6iBS8NEENQ.png" /><figcaption>Approximate gas consumption of verifying one vote for OVN and for various algorithms using blind signatures</figcaption></figure><p>Blind signatures using Elliptic Curve Cryptography (ECC) are more compact in key size, therefore they can provide sufficient level of security even in such a constrained environment like the EVM. This has been our motivation to use <a href="http://www.isecure-journal.com/article_39171_47f9ec605dd3918c2793565ec21fcd7a.pdf">an ECC blind signature scheme</a>. However, before an Ethereum network-wide protocol upgrade, verifying ECC blind signatures were not supported, meaning that one would need to use external libraries -such as <a href="https://github.com/androlo/standard-contracts">this one</a> - to use elliptic curve operations. As one can see in the figure above, before the protocol upgrade (hard-fork) verifying even one ECC blind signature would cost more than the block gas limit, meaning that such transaction would have been always thrown an out-of-gas error ie. it would have never left any state changes in the Ethereum blockchain.</p><p>As a result of the Byzantium hard fork elliptic curve point addition and scalar multiplication are supported natively in the EVM, which also means that such operations consume significantly less gas than before the hard fork. This protocol change enabled our implementation to become practical. To put things into perspective one can inspect the figure above which shows the gas cost of casting a vote using the Ethereum smart contract implementation of the Open Vote Network protocol.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/642/1*gMTOxP4YuWZY4uIzHgTzHQ.png" /><figcaption>Gas costs of different blockchain-based e-voting protocols for casting a vote for an eligible voter (numbers denote the amount of gas while registering a voter or casing a vote)</figcaption></figure><p>A simple smart contract solution developed by the Ethereum Foundation is almost the most gas cost-efficient for voting, however, it does not provide ballot secrecy, meaning anyone will know how all the others voted. All the rest of the protocols provide ballot secrecy which clearly comes at a computational cost. Open Vote Network almost skims the block gas limit if registration and vote casting would take place in the same block. RSA blind signatures are the fastest among the protocols using blind signatures, although it does not provide any meaningful level of security. The Byzantium hard fork was indeed necessary to be able to implement the protocol. The <a href="https://eprint.iacr.org/2017/1043.pdf">original protocol</a> does not guarantee fairness, but it can be achieved with additional commit and reveal rounds. As one can see these additional rounds make the e-voting scheme slightly less cost-efficient.</p><h4>Security analysis</h4><p>Hereby our implementation is analyzed from a security point of view. We assume the existence of a secure communication channel between administrator(s) and voters. Furthermore, investigating client-side issues and vulnerabilities are beyond the scope of this post.</p><p><strong>Census</strong><br>Currently the list of eligible voters is maintained by the election administrator(s). Election administrator can add and remove voters from the eligible voters list. This makes the current census mechanism entirely dependent on the benevolence of the administrator(s).<br>This design weakness could be alleviated by using some form of self-authentication. In countries like Estonia or Malta there is already given and deployed the e-Identity which could be used to let users authenticate themselves in a decentralized manner without relying on any central parties. Integrating such e-Identity solution is left for future work.<br> <br><strong>Censorship resistance</strong><br>Election administrator can refuse to sign blinded votes or she can just produce a signature which is not valid. This might be ameliorated by applying not only one entity to sign votes, rather allowing multiple parties to participate as election organizers.<br>A fully decentralized way would be to delegate this functionality to the election smart contract as well. However, this is simply not feasible since smart contracts are fully transparent therefore they can not hold private data such as private keys for signing.</p><p><strong>ECC blind signature</strong><br>The security of the blind signature scheme depends on the difficulty of solving the discrete logarithm problem in the altBN128 elliptic curve group.</p><p><strong>Fairness</strong><br>Fairness is not guaranteed by the proposed protocol, although this could be fixed by adding an additional commit-reveal phase using a commitment scheme (eg. Pedersen commitment scheme). However, this worsens the usability and computational complexity of the platform, as pointed out earlier.</p><p><strong>Verifiability</strong><br>E2E-, individual- and universal-verifiability are achieved by the nature and transparance of blockchain. Voter can verify that their vote is included in the tally by checking the transaction containing their vote is included in the blockchain and whether it was mined and executed successfully. Similarly, voters could check the validity of all other transactions, that is gaining certainty that the election as a whole was carried out in a secure and honest way.</p><p><strong>Double-voting, fake votes</strong><br>Double-voting or fake votes could be produced if one is able to compromise the election administrator and get her signing key. Once again, this weakness might be mitigated somewhat if more than one election administrator is deployed. This modification would require multiple signatures on a single vote.</p><p>If the discrete logarithm assumption is broken, then basically anyone is able to create valid signatures on any vote, no matter how many election administrators are deployed. <br> <br><strong>Timing attacks</strong><br>Voter anonymity might be harmed by timing attacks. One might connect the votes to the voter identity if between signature generation and the vote casting there are only a few or none voters casting their votes. The anonymity set of a voter is essentially the numbers of votes in the block where the vote is cast as part of an Ethereum transaction. Anonymity can be strengthened by randomly casting the vote after the blind signature issuing. Such a random delay functionality should be developed on the client side. <br> <br><strong>Ballot collision</strong><br>Ballot collision is only possible if there are two ballots with the same choice code and signature. This has a negligible probability.</p><p><strong>Network analysis</strong><br>One might analyse the network and reveal which IP address (real world physical identity) belongs to which Ethereum address. Users should be prompted to use anonymity services like proxies or TOR, which can enable users to obscure their IP addresses.</p><p><strong>Network attack</strong><br>By using a public blockchain for election purposes, one has to take into consideration the possibility of suffering from a network-wide attack such as the infamous 51% attack. Miners might also compromise the election by not including transactions targeting the election smart contract. <br> <br><strong>Consensus algorithm</strong><br>If one wishes to use a private/permissioned blockchain, has to decide which consensus algorithm she wants to use. A straightforward choice would be deploying a proof-of-authority consensus algorithm, however the trustless nature of the deployed blockchain is conceded. In this case trust is dispersed among parties who are authorized to sign blocks.</p><h4>Conclusion</h4><p>Hereby an Ethereum smart contract has been presented as an implementation of an <a href="https://eprint.iacr.org/2017/1043.pdf">e-voting protocol</a> with blind signatures. Different blind signature algorithms have been tested in order to choose the best suitable one for our e-voting platform. Security analysis and breakdown of computational costs of our implementation are conferred. Practicability and scalability of our smart contract implementation is demonstrated by simulating an election on the Ethereum Rinkeby test network.</p><p>If you want to know more about my upcoming blockchain-related projects, follow me on <a href="https://medium.com/@Istvan_A_Seres">Medium</a> or <a href="https://twitter.com/Istvan_A_Seres">Twitter</a>. Strive for more, keep #buidl!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=411e88af044a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/coinmonks/implementing-an-e-voting-protocol-with-blind-signatures-on-ethereum-411e88af044a">Implementing an e-voting protocol with blind signatures on Ethereum</a> was originally published in <a href="https://medium.com/coinmonks">Coinmonks</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Remote electronic voting: a recap from a blockchain perspective]]></title>
            <link>https://istvan-a-seres.medium.com/remote-electronic-voting-a-recap-from-a-blockchain-perspective-2d726d4fe23b?source=rss-8498e40d416------2</link>
            <guid isPermaLink="false">https://medium.com/p/2d726d4fe23b</guid>
            <category><![CDATA[electronic-voting]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[politics]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[bitcoin]]></category>
            <dc:creator><![CDATA[Seres István András]]></dc:creator>
            <pubDate>Wed, 31 Jan 2018 19:28:16 GMT</pubDate>
            <atom:updated>2018-02-03T08:50:55.708Z</atom:updated>
            <content:encoded><![CDATA[<p>Digital transformation has not yet touched the foundations of voting. We still cast our votes the same way how ancient Greeks did in Athens more than 2,400 years ago. The whole process is cumbersome, expensive, involves a lot of trust and more importantly not verifiable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*R-c9G7T8ZMs-L0tXSPLJow.jpeg" /><figcaption>Voting tokens as pottery shards</figcaption></figure><p>Furthermore traditional voting is prone to fraud. History has already shown us <a href="https://en.wikipedia.org/wiki/List_of_controversial_elections">numerous examples</a> of electoral fraud. The conclusion of these shameful events should be that we must aim to create and deploy a trustless, secure and verifiable voting system which would re-establish the good fame of democracy. In such a voting system any malevolent form of modification or distortion of election results should be impossible. But today what we see is <a href="http://www.independent.co.uk/news/uk/politics/generalelection/general-election-2015-200000-ballot-papers-stolen-by-van-thieves-10213657.html">stolen votes</a>,<a href="https://www.theguardian.com/world/2017/oct/01/violence-against-catalan-voters-what-we-know-so-far"> forced abstention attacks</a> against voters, <a href="https://en.wikipedia.org/wiki/New_Black_Panther_Party_voter_intimidation_case">voter intimidation</a>, weak voter privacy etc. Luckily this is not the end of the sad story of voting around the globe.</p><p>The promise of electronic voting is that we can do better. By means of cryptography electronic voting protocols are trying to achieve the properties of traditional voting (secret ballot, non-reusability of ballots (one voter one vote), robustness) as well as additional desired properties such as verifiability, no forced-abstention attacks and fault tolerance.</p><h3>Why blockchain?</h3><p>Seemingly there is an irreconcilable trade-off between voter privacy and verifiability. It looks like only one of these is achievable already at the protocol level. Fortunately it is not the case; this is the point where blockchain comes into the picture.</p><p>The immediate advantage of applying a public or permissioned blockchain — instead of a public bulletin board — in remote electronic voting protocols is that it provides data integrity and fault tolerance. Verifiability is provided for those who are entitled to see the blockchain, they just need to look at the chain and check whether their vote was <strong><em>casted as intended</em></strong> and <strong><em>counted as casted. </em></strong>If any voter is able to verify their own vote, that is called: <strong><em>individual verifiability</em></strong><em>, </em>while if<em> </em>they are also able to verify that the whole voting process is executed in a correct manner, it is called <strong><em>universal verifiability</em></strong>.</p><p>One of the challenges of electronic voting protocols using blockchain is how to provide voter privacy meanwhile retaining individual/universal verifiability.</p><p>A trivial way to implement a voting smart contract in Ethereum can be found <a href="https://ethereum.org/dao">here</a>. However this obvious solution does reveal who voted for what. So let’s keep voter privacy!</p><h3>An e-voting protocol based on blockchain</h3><p>Recently a simple but elegant blockchain-based e-voting protocol was <a href="https://eprint.iacr.org/2017/1043.pdf">suggested</a> by Yi Liu and Qi Wang. There are 3 actors in this protocol:</p><ol><li>Voters</li><li>Organizers</li><li>Inspectors</li></ol><p>In the pre-voting phase voters are authenticated and registered by an assumed, already existing identity management system.</p><p>In the voting phase individual encrypted votes are blindly signed by organizers and inspectors to say they do not see what they actually sign, they only able to see whether it comes from a registered voter. After the <a href="http://wwwf.imperial.ac.uk/~rbellovi/writings/chaum.pdf">blind signature</a> protocol individual voters will have signatures on the hash of the vote from all the organizers and inspectors. Casting a vote requires a freshly generated blockchain address from which the vote (in clear text) and the blindly signed hashes will be sent. The blindly signed hashes will make it possible to check whether the vote is cast from a legitimate voter. Sending the votes from a freshly generated address basically acts as a mix-net, providing voter privacy.</p><p>Afterwards the counting phase is pretty straightforward. The election result can be simply obtained by looking at the votes on the blockchain. One just need to exclude those votes whose blind signature is not valid. This design clearly fulfills universal and individual verifiability while maintains voter privacy.</p><h3>Aftermath</h3><p>This very same protocol is easily implementable and deployable (unlike <a href="https://eprint.iacr.org/2017/110.pdf">this protocol</a> which relies on Schnorr-proofs) since the Ethereum Virtual Machine (EVM) <a href="https://github.com/axic/ethereum-rsa">is capable</a> of verifying RSA signatures.</p><p>Hopefully very soon we will see local and general elections backed by blockchains in order to upgrade our democracies to a higher level of inclusion, fairness, transparency and security.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NwLTqKP5d9pqVf2U7wR25g.jpeg" /><figcaption>Catalan independence referendum protecting ballots with the “blockchain”</figcaption></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2d726d4fe23b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Ethereum: a community which does not learn from its own mistakes]]></title>
            <link>https://istvan-a-seres.medium.com/ethereum-a-community-which-does-not-learn-from-its-own-mistakes-ee70cfa7d863?source=rss-8498e40d416------2</link>
            <guid isPermaLink="false">https://medium.com/p/ee70cfa7d863</guid>
            <category><![CDATA[security]]></category>
            <category><![CDATA[ethereum-blockchain]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Seres István András]]></dc:creator>
            <pubDate>Mon, 11 Sep 2017 09:28:49 GMT</pubDate>
            <atom:updated>2017-09-11T09:33:18.622Z</atom:updated>
            <content:encoded><![CDATA[<p>Lessons learnt from the <a href="https://github.com/slockit/DAO/wiki/The-DAO-v1.0-Code">DAO v1.0</a>, right? Lessons learnt from the <a href="https://www.kingoftheether.com/thrones/kingoftheether/index.html">KingOfTheEtherThrone</a>, right? Lessons learnt from all the other <a href="https://www.reddit.com/r/ethereum/comments/4omdlf/to_kickstart_the_building_safer_smart_contracts/?st=j7fuu67j&amp;sh=0115eb49">numerous failed contracts</a>? Sure! <strong><em>Sure</em></strong>??!!</p><p>Wanna bet?</p><p>Dapps (or Decentralized Applications) is an umbrella term for applications whose backend is built (partly or fully) on some blockchain. Dapps by having a decentralized backend can function in a trustless, more transparent way. There are several appealing and promising dapps out there on the Ethereum blockchainon such as <a href="https://augur.net/">Augur</a>, a decentralized prediction market or <a href="https://swarm.city/">Swarm City</a>, which is a decentralized commerce platform. However, this is just the tip of the iceberg.</p><p>Last week I just wanted to have a look at the latest developments in the Ethereum Dapp field, so I visited one of my <a href="https://dapps.ethercasts.com/">favourite sites</a> for dapps, I have not checked for months. It is a <em>popular,</em> <strong>curated</strong> collection of dapps on Ethereum. I just skimmed over a few smart contract source code and my overall impression was quite distressing.</p><p>Let’s start with <a href="https://etherscan.io/address/0x663a5ca0295231b0d88afb1c557a8d8f4c1b6459#code">Cillionaire</a>. It is a donation game with a random beneficiary. It has a reentrant function, which allows one to potentially drain all the money from the contract. Hello DAO v1.0!</p><p>Then there is <a href="https://etherscan.io/address/0x582b2489710a4189ad558b6958641789587fcc27#code">Ponzi Unlimited</a> which is a typical one among many ponzi game (thanks Captain Obvious). Seemingly it handles the possibility that paying out rewards to investors can fail (anyway <em>.send()</em> function is not recommended to use), however this is not the case. In case <em>.send()</em> fails in the <em>payout</em> function, there is not any implemented measure to resend funds or let users withdraw it on their own. This can lead to lost investments and unrecovarable funds just like it happened once again with KingOfTheEtherThrone.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/568/1*gGhd4p4dZ1gQx318GodIyA.jpeg" /><figcaption>The struggle is real!</figcaption></figure><p>Although these are just two randomly chosen dapps deployed in the past few weeks, I don’t have illusions regarding the security of Ethereum smart contracts. My guess would be that on a large scale there are still tremendous amount of contracts which does not even follow <a href="https://github.com/ConsenSys/smart-contract-best-practices">basic security recommendations</a>. If this is indeed currently the state of Ethereum dapps, then it is quite alarming for all of us.</p><p>There can be sharding, proof of stake, Ethereum can solve the problems of scaling, timestamping or privacy, it would be still good for nothing unless smart contract security progresses significantly as well.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ee70cfa7d863" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>