Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of two workshops held at the 23rd International Conference on Financial Cryptography and Data Security, FC 2019, in St. Kitts, St. Kitts and Nevis, in February 2019.The 20 full papers and 4 short papers presented in this book were carefully reviewed and selected from 34 submissions.The papers feature the outcome of the 4th Workshop on Advances in Secure Electronic Voting, VOTING 2019 and the Third Workshop on Trusted Smart Contracts, WTSC 2019. VOTING covered topics like election auditing, voting system efficiency, voting system usability, and new technical designs for cryptographic protocols for voting systems.WTSC focuses on smart contracts, i.e., self-enforcing agreements in the form of executable programs, and other decentralized applications that are deployed to and run on top of (specialized) blockchains.

Inhaltsverzeichnis

Frontmatter

Trusted Smart Contracts

Frontmatter

Two-Party State Channels with Assertions

Abstract
An empirical case study to evaluate state channels as a scaling solution for cryptocurrencies demonstrated that providing an application’s full state during the dispute process for a state channel is financially costly (i.e. $0.24 to $8.83 for a battleship game) which can hamper their real-world use. To overcome this issue, we present State Assertion Channels, the first state channel to guarantee an honest party is always refunded the cost if it becomes necessary to send an application’s full state during the dispute process. Furthermore it ensures an honest party will pay an approximate fixed cost to continue an application’s execution via the dispute process. We provide a proof of concept implementation in Ethereum which demonstrates it costs approximately $0.02 to submit evidence regardless of the smart contract’s application.
Chris Buckland, Patrick McCorry

Short Paper: Secure Offline Payments in Bitcoin

Abstract
Double-spending attacks on fast payments are one of the fatal architectural problems in Cryptocurrencies. Dmitrienko et al. proposed an offline fast payment scheme that relies on tamper-proof wallets produced by trustworthy manufacturers. With the wallets, the payee can immediately trust the transactions generated by the wallets without waiting for their registration to the blockchain. Secure coin-preloading to the wallet is important, while illegal coin-preloading can cause over/double-spending by the trusted wallets. For this, they proposed an interesting protocol that makes use of a fragment of the main blockchain to prove to the wallets the legitimacy of preloaded coins. One drawback is that, in proving that the fragment are from honest miners, their protocol requires a trusted online time-stamp server so that the wallets can verify the timestamps to see if the blocks in the fragment is mined with sufficiently large amount of computing resources. Otherwise, it sacrifices usability. In order to eliminate such an online trustee, in this paper we took the opposite approach that the payee (not the wallets) verifies the legitimacy of preloaded coins at the time of offline payment. As a consequence, our result shows that, with light-weight tamper-proof wallets, completely decentralized offline payment is possible without any modification to the existing Bitcoin network.
Taisei Takahashi, Akira Otsuka

Proof-of-Work Sidechains

Abstract
During the last decade, the blockchain space has exploded with a plethora of new cryptocurrencies, covering a wide array of different features, performance and security characteristics. Nevertheless, each of these coins functions in a stand-alone manner, independently. Sidechains have been envisioned as a mechanism to allow blockchains to communicate with one another and, among other applications, allow the transfer of value from one chain to another, but so far there have been no decentralized constructions. In this paper, we put forth the first side chains construction that allows communication between proof-of-work blockchains without trusted intermediaries. Our construction is generic in that it allows the passing of any information between blockchains. Using this construction, two blockchains can be connected in a “two-way peg” in which an asset can be transferred from one chain to another and back. We pinpoint the features needed for two chains to communicate: On the source side, a proof-of-work blockchain that has been interlinked, potentially with a velvet fork; on the destination side, a blockchain with smart contract support. We put forth the smart contracts needed to implement these sidechains and explain them in detail. In the heart of our construction, we use a recently introduced cryptographic primitive, Non-Interactive Proofs of Proof-of-Work (NIPoPoWs).
Aggelos Kiayias, Dionysis Zindros

You Sank My Battleship! A Case Study to Evaluate State Channels as a Scaling Solution for Cryptocurrencies

Abstract
Off-chain protocols (or so-called Layer 2) are heralded as a scaling solution for cryptocurrencies. One prominent approach, state channels, allows a group of parties to transact amongst themselves and the global blockchain is only used as a last resort to self-enforce any disputed transactions. To evaluate state channels as a scaling solution, we provide a proof of concept implementation for a two-player battleship game. It fits a category of applications that are not considered reasonable to execute on the blockchain, but it is widely perceived as an ideal application for off-chain protocols. We explore the minimal modifications required to deploy the battleship game as a state channel and propose a new state channel construction, Kitsune, which combines features from existing constructions. While in the optimistic case we demonstrate the battleship game can be played efficiently in a state channel, the requirement for unanimous off-chain agreement introduces new economic and time-based attacks that can render the game as unreasonable to play.
Patrick McCorry, Chris Buckland, Surya Bakshi, Karl Wüst, Andrew Miller

Game-Theoretic Analysis of an Incentivized Verifiable Computation System

Abstract
Outsourcing computation allows a weak client to outsource its computation to a powerful server and receive the result of the computation. Verifiable outsourcing enables clients to verify the computation result of untrusted servers. Permissionless distributed outsourcing systems provide an attractive marketplace for users to participate in the system as a problem-giver who needs solution to a problem, or problem-solver who is willing to sell its computational resources. Verification of computation in these systems, that do not assume trusted computational nodes, is a challenging task. In this paper we provide a game-theoretic analysis of an incentivized outsourcing computation system, proposed by Harz and Boman [Harz et al. 2018] (HB), at WTSC 2018 (FC Workshop), and show that the system is vulnerable to collusion and Sybil attacks, that result in incorrect solutions to be accepted by the system. We also show that malicious computational node can succeed in polluting the blockchain. We propose modifications to the system that incentivizes honest behavior, and improve the system’s correctness guarantee. We provide a high-level analysis of the modified system using our game theoretic approach, and show the effectiveness of the proposed modifications.
Mahmudun Nabi, Sepideh Avizheh, Muni Venkateswarlu Kumaramangalam, Reihaneh Safavi-Naini

Sluggish Mining: Profiting from the Verifier’s Dilemma

Abstract
Miners in Ethereum need to make a choice when they receive a block: they can fully validate the block by executing every transaction in order to validate the new state, but this consumes precious time that could be used on mining the next block. Alternatively, miners could skip some of the verification stages and proceed with the mining, taking the risk of building on top of a potentially invalid block. This is referred to as the verifier’s dilemma.
Although the gas limit imposed on Ethereum blocks mitigates this attack by forcing an upper bound on the time spent during verification, the slowdown that can be achieved within a block can still be enough to have an impact on profitability.
In this paper we present a mining strategy based around sluggish contracts; these computationally intensive contracts are purposely designed to have a slow execution time in the Ethereum Virtual Machine to provide an advantage over other miners by slowing their contract verification time.
We validate our proposed mining strategy by designing and evaluating a set of candidate sluggish smart contracts. Furthermore, we provide a detailed analysis that shows under which conditions our strategy becomes profitable alongside a series of suggestions to detect this type of strategy in the future.
Beltrán Borja Fiz Pontiveros, Christof Ferreira Torres, Radu State

Short Paper: Deploying PayWord on Ethereum

Abstract
We revisit the 1997 PayWord credit-based micropayment scheme from Rivest and Shamir. We observe that smart contracts can be used to augment this system, apply to ‘claim or refund’ paradigm of cryptocurrencies to remove the counter-party risk inherent in PayWorld, and use a smart contract to ‘staple’ real value (in Ether) to payments in the system. Our implementation is more concise than any Ethereum payment channel we are aware of and the offline payments are very compact values (264 bits). It only uses hash functions and not digital signatures. EthWord becomes cheaper than standard Ethereum transfers when more than 16 payments between the same participants are made and appears to maintain its advantage for up to 1000+ transactions, at which point signature-based payments become cheapest. The main drawback of EthWord is the moderate gas price of using the system—despite dropping signatures, it is still priced out of the micropayments use-case. Like any payment channel, requires only two on-blockchain function calls to open and close the channel, while allowing the rest to be made off-blockchain.
Muhammad Elsheikh, Jeremy Clark, Amr M. Youssef

SoK: Development of Secure Smart Contracts – Lessons from a Graduate Course

Abstract
Smart contracts are programs on top of blockchains and cryptocurrencies. This new technology allows parties to exchange valuable assets without mutual trust, with smart contracts controlling the interaction between the parties. Developing smart contracts, or more generally decentralized applications, is challenging. First, they run in a concurrent environment that admits race conditions; adversaries may attack smart contracts by influencing the order of transactions. Second, the required functionality is often based on roles and states. This proves to be difficult to implement in current smart contract languages. Third, as a distinctive feature, smart contracts are immutable, hence bugs cannot be corrected easily. At the same time, bugs may cause (and have already caused) tremendous losses; they are to be avoided by all means.
This paper discusses our approach of teaching the development of secure smart contracts on the Ethereum platform at university level. This is a challenging task in many respects. The underlying technologies evolve rapidly and documentation lags behind. Available tools are in different stages of development, and even the most mature ones are still difficult to use. The development of secure smart contracts is not yet a well-established discipline. Our aim is to share our ideas, didactic concept, materials, insights, and lessons learned.
Monika di Angelo, Christian Sack, Gernot Salzer

Verification-Led Smart Contracts

Abstract
Turing complete smart contract formalisms (e.g. Solidity) are conceptually appealing, but leave the door open to the problems of verifying completely arbitrary code, a task which can be of arbitrarily high complexity or can be undecidable. We argue that a more structured approach, in which smart contract families are designed ab initio with efficient verifiability in mind, provide a much more practical way forward. We emphasis that the boundary between on-chain and off-chain information, which must always be determined in an application specific manner, is crucial in determining the practicability of smart contract verification. We discuss the role of refinement technologies in breaking down the complexity of smart contract verification, and illustrate the argument using the Event-B formal modelling framework and Solidity as implementation vehicle.
Richard Banach

A Java Framework for Smart Contracts

Abstract
This article defines a framework for programming, in Java, smart contracts over blockchain. The framework consists of a restricted runtime and of an instrumentation procedure for classes that need to be persisted to blockchain, for payable contract methods and for gas metering. This instrumentation abstracts away any difference between storage and memory data location, which is at the origin of tricky semantical issues and bugs in Solidity. Moreover, this framework allows one to leverage, in a transparent way, existing expertise and tools from the Java world, in order to build smart contracts in a simple and comfortable way. The resulting contracts are strongly-typed and work over a shared storage, that allows simple intercontract communication. This makes it easy to install libraries or microservices in blockchain.
Fausto Spoto

Is Solidity Solid Enough?

Abstract
We introduce Featherweight Solidity, a calculus formalizing the core features of the Solidity language, thus providing a fundamental step to reason about safety properties of smart contracts’ source code. The formalization includes a static type system that represents the foundation of the Solidity compiler. We show that it prevents some errors whereas many others, such as accesses to a non existing function or state variable, are only detected at runtime and cause interruption and rolling-back of transactions. We then propose a refinement of the type system that is retro-compatible with original Solidity code, and statically captures more errors, such as unsafe casts and unsafe call-back expressions.
Silvia Crafa, Matteo Di Pirro, Elena Zucca

Building Executable Secure Design Models for Smart Contracts with Formal Methods

Abstract
Smart contracts are appealing because they are self-executing business agreements between parties with the predefined and immutable obligations and rights. However, as with all software, smart contracts may contain vulnerabilities because of design flaws, which may be exploited by one of the parties to defraud the others. In this paper, we demonstrate a systematic approach to building secure design models for smart contracts using formal methods. To build the secure models, we first model the behaviors of participating parties as state machines, and then, we model the predefined obligations and rights of contracts, which specify the interactions among state machines for achieving the business goal. After that, we illustrate executable secure model design patterns in TLA+ (Temporal Logic of Actions) to against well-known smart contract vulnerabilities in terms of state machines and obligations and rights at the design level. These vulnerabilities are found in Ethereum contracts, including Call to the unknown, Gasless send, Reentrancy, Lost in the transfer, and Unpredictable state. The resultant TLA+ specifications are called secure models. We illustrate our approach to detect the vulnerabilities using a real-estate contract example at the design level.
Weifeng Xu, Glenn A. Fink

SoK: Transparent Dishonesty: Front-Running Attacks on Blockchain

Abstract
We consider front-running to be a course of action where an entity benefits from prior access to privileged market information about upcoming transactions and trades. Front-running has been an issue in financial instrument markets since the 1970s. With the advent of the blockchain technology, front-running has resurfaced in new forms we explore here, instigated by blockchain’s decentralized and transparent nature. In this paper, we draw from a scattered body of knowledge and instances of front-running across the top 25 most active decentral applications (DApps) deployed on Ethereum blockchain. Additionally, we carry out a detailed analysis of Status.im initial coin offering (ICO) and show evidence of abnormal miner’s behavior indicative of front-running token purchases. Finally, we map the proposed solutions to front-running into useful categories.
Shayan Eskandari, Seyedehmahsa Moosavi, Jeremy Clark

Trustee: Full Privacy Preserving Vickrey Auction on Top of Ethereum

Abstract
The wide deployment of tokens for digital assets on top of Ethereum implies the need for powerful trading platforms. Vickrey auctions have been known to determine the real market price of items as bidders are motivated to submit their own monetary valuations without leaking their information to the competitors. Recent constructions have utilized various cryptographic protocols such as ZKP and MPC, however, these approaches either are partially privacy-preserving or require complex computations with several rounds. In this paper, we overcome these limits by presenting Trustee as a Vickrey auction on Ethereum which fully preserves bids’ privacy at relatively much lower fees. Trustee consists of three components: a front-end smart contract deployed on Ethereum, an Intel SGX enclave, and a relay to redirect messages between them. Initially, the enclave generates an Ethereum account and ECDH key-pair. Subsequently, the relay publishes the account’s address and ECDH public key on the smart contract. As a prerequisite, bidders are encouraged to verify the authenticity and security of Trustee by using the SGX remote attestation service. To participate in the auction, bidders utilize the ECDH public key to encrypt their bids and submit them to the smart contract. Once the bidding interval is closed, the relay retrieves the encrypted bids and feeds them to the enclave that autonomously generates a signed transaction indicating the auction winner. Finally, the relay submits the transaction to the smart contract which verifies the transaction’s authenticity and the parameters’ consistency before accepting the claimed auction winner. As part of our contributions, we have made a prototype for Trustee available on Github for the community to review and inspect it. Additionally, we analyze the security features of Trustee and report on the transactions’ gas cost incurred on Trustee smart contract.
Hisham S. Galal, Amr M. Youssef

Advances in Secure Electronic Voting Schemes

Frontmatter

Election Manipulation 100

Abstract
The true election margin for an Instant Runoff Voting (IRV) election can be hard to compute, because a small modification early in the elimination sequence can alter the outcome and result in a candidate winning the last round by a large margin. It is often assumed that the true margin is the last-round margin, that is half the difference between the two candidates who remain when everyone else is eliminated, though it is well known that this need not be the case. Perceptions of confidence in the outcome, and even formal policies about recounts, often depend on the last-round margin. There is already some prior work on how to compute the true election margin efficiently for IRV, and hence how to find the minimal manipulation. In this work we show how to manipulate an election efficiently while also producing a large last-round margin. This would allow a successful manipulation to evade detection against naive methods of assessing the confidence of the election result. This serves as further evidence for accurate computations of the exact margin, or for rigorous Risk Limiting Audits which would detect a close or wrong election result (respectively) regardless of the last-round margin.
Michelle Blom, Peter J. Stuckey, Vanessa J. Teague

Bernoulli Ballot Polling: A Manifest Improvement for Risk-Limiting Audits

Abstract
We present a method and software for ballot-polling risk-limiting audits (RLAs) based on Bernoulli sampling: ballots are included in the sample with probability p, independently. Bernoulli sampling has several advantages: (1) it does not require a ballot manifest; (2) it can be conducted independently at different locations, rather than requiring a central authority to select the sample from the whole population of cast ballots or requiring stratified sampling; (3) it can start in polling places on election night, before margins are known. If the reported margins for the 2016 U.S. Presidential election are correct, a Bernoulli ballot-polling audit with a risk limit of 5% and a sampling rate of \(p_0=1\%\) would have had at least a 99% probability of confirming the outcome in 42 states. (The other states were more likely to have needed to examine additional ballots). Logistical and security advantages that auditing in the polling place affords may outweigh the cost of examining more ballots than some other methods might require.
Kellie Ottoboni, Matthew Bernhard, J. Alex Halderman, Ronald L. Rivest, Philip B. Stark

k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits

Abstract
We present an approximate sampling framework and discuss how risk-limiting audits can compensate for these approximations, while maintaining their “risk-limiting” properties. Our framework is general and can compensate for counting mistakes made during audits.
Moreover, we present and analyze a simple approximate sampling method, “k-cut”, for picking a ballot randomly from a stack, without counting. Our method involves doing k “cuts,” each involving moving a random portion of ballots from the top to the bottom of the stack, and then picking the ballot on top. Unlike conventional methods of picking a ballot at random, k-cut does not require identification numbers on the ballots or counting many ballots per draw. We analyze how close the distribution of chosen ballots is to the uniform distribution, and design mitigation procedures. We show that \(k=6\) cuts is enough for a risk-limiting election audit, based on empirical data, which provides a significant increase in sampling efficiency. This method has been used in pilot RLAs in Indiana and is scheduled to be used in Michigan pilot audits in December 2018.
Mayuri Sridhar, Ronald L. Rivest

How to Assess the Usability Metrics of E-Voting Schemes

Abstract
Voters play an important role in end-to-end verifiable e-voting schemes because the schemes encourage them to carry out several security-critical tasks by themselves. If the voters cannot complete the tasks by themselves or experience bad usability while executing them, vote manipulations by either a faulty software or deliberate attacks cannot be detected which renders verification useless. Therefore, the scheme’s usability is of crucial importance and demands an early investigation of human factors when implementing e-voting systems. In this paper, we give an overview of user study design challenges when investigating end-to-end verifiable e-voting schemes. We provide guidelines that address these challenges and support researchers in the design of user studies. The guidelines are based on the literature and the authors’ experiences.
Karola Marky, Marie-Laure Zollinger, Markus Funk, Peter Y. A. Ryan, Max Mühlhäuser

Improving the Performance of Cryptographic Voting Protocols

Abstract
Cryptographic voting protocols often rely on methods that require a large number of modular exponentiations. Corresponding performance bottlenecks may appear both on the server and the client side. Applying existing optimization techniques is often mentioned and recommended in the literature, but their potential has never been analyzed in depth. In this paper, we investigate existing algorithms for computing fixed-base exponentiations and product exponentiations. Both of them appear frequently in voting protocols. We also explore the potential of applying small-exponent techniques. It turns out that using these techniques in combination, the overall computation time can be reduced by two or more orders of magnitude.
Rolf Haenni, Philipp Locher, Nicolas Gailly

Short Paper: Coercion-Resistant Voting in Linear Time via Fully Homomorphic Encryption

Towards a Quantum-Safe Scheme
Abstract
We present an approach for performing the tallying work in the coercion-resistant JCJ voting protocol, introduced by Juels, Catalano, and Jakobsson, in linear time using fully homomorphic encryption (FHE). The suggested enhancement also paves the path towards making JCJ quantum-resistant, while leaving the underlying structure of JCJ intact. The pairwise comparison-based approach of JCJ using plaintext equivalence tests leads to a quadratic blow-up in the number of votes, which makes the tallying process rather impractical in realistic settings with a large number of voters. We show how the removal of invalid votes can be done in linear time via a solution based on recent advances in various FHE primitives such as hashing, zero-knowledge proofs of correct decryption, verifiable shuffles and threshold FHE. We conclude by discussing some of the advantages and challenges resulting from our proposal, followed by an outline of future work and possible lines of attack.
Peter B. Rønne, Arash Atashpendar, Kristian Gjøsteen, Peter Y. A. Ryan

PrivApollo – Secret Ballot E2E-V Internet Voting

Abstract
The Apollo voting protocol improves on the integrity properties of Helios by enabling voters to communicate to the public the failure of the cast-as-intended check, in the event that the voting terminal changes the vote on receiving the credential. It also enables the voter to detect a dishonest registrar and to prove misbehaviour. It provides an explicit description of the role of one or more computational voting assistants which help the voter perform the checks without obtaining information on the vote. Unfortunately, neither Helios nor Apollo provides ballot secrecy, because the voting terminal knows the vote. We present PrivApollo, a protocol that improves Apollo by providing ballot secrecy from the voting terminal.
Hua Wu, Poorvi L. Vora, Filip Zagórski

End-to-End Verifiable Quadratic Voting with Everlasting Privacy

Abstract
Quadratic voting is an intriguing new method for public choice suggested by Lalley and Weyl, which they showed to be utilitarian efficient. Voters are given a budget of credits and can assign each of the candidates a (perhaps negative) value, where the price paid for their voting choice is the sum of the squared values. From a security viewpoint, we generally request elections to be private and have integrity, and even further (end-to-end) verifiability which entails public bulletin boards. Such public data might be troublesome when considering future adversaries capable of breaking current cryptographic primitives, either due to computational power advances, broken primitives or scientific breakthroughs. This calls for election schemes with everlasting privacy and perfectly private audit trails. In the case of quadratic voting this is even more crucial since budget balances have to be linked between elections in a verifiable way, and revealing old budget values partially break privacy in later elections. In this paper, we suggest an efficient construction of electronic quadratic voting with end-to-end verifiability and a perfectly private audit trail inspired by the methods of Cuvelier, Pereira and Peters, but adapted to include the quadratic relations and keeping budget balances everlasting private.
Olivier Pereira, Peter B. Rønne

Lattice-Based Proof of a Shuffle

Abstract
In this paper we present the first fully post-quantum proof of a shuffle for RLWE encryption schemes. Shuffles are commonly used to construct mixing networks (mix-nets), a key element to ensure anonymity in many applications such as electronic voting systems. They should preserve anonymity even against an attack using quantum computers in order to guarantee long-term privacy. The proof presented in this paper is built over RLWE commitments which are perfectly binding and computationally hiding under the RLWE assumption, thus achieving security in a post-quantum scenario. Furthermore we provide a new definition for a secure mixing node (mix-node) and prove that our construction satisfies this definition.
Nuria Costa, Ramiro Martínez, Paz Morillo

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise