Scope
Blockchain research touches on several different areas of computer science, inluding: distributed computation, algorithmic game theory, cryptography and network theory.
The Israel Blockchain Research day is meant to be a periodic meeting place for students and researchers interested in blockchain research within computer science.
Location
Room SL201, Law School / Sustainability School joint building (Locations 34/35 on the IDC campus map). Parking: Western IDC Parking lot.
Organizers
Eli Ben-Sasson (StarkWare), Ittay Eyal (Technion), Tal Moran (IDC)
Tentative Program
9:00 - 9:30: Reception
9:30-9:40: Opening Remarks
9:40- 10:00: Gilad Stern, HUJI: Reaching Consensus for Asynchronous Distributed Key Generation
10:00-10:20: Shir Cohen, Technion: Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
10:20-10:40: Shahar Papini, StarkWare: Cairo - A Turing complete CPU AIR for efficient ZK-STARKs
10:40 - 11:10: Coffee break
11:10 - 11:30: Aviv Yaish, HUJI: Correct Cryptocurrency ASIC Pricing: Are Miners Overpaying?
11:30 - 11:50: Maya Dotan, HUJI: Efficient multi dimensional approximate consensus
11:50-12:10: Roi Bar Zur,Technion: Efficient MDP Analysis for Selfish-Mining in Blockchains
12:10 - 14:00: Lunch
14:00-14:20: Yaron Kaner, IDC Herzliya: Bitcoin+: Cheap Support for Complex Spending Conditions in a UTXO Ledger
14:20-14:40: Itay Tsabary, Technion: MAD-HTLC: Because HTLC is Crazy-Cheap to Attack
14:40-15:00: Saar Tochner, HUJI: Differentially-Private Payment Channels with Twilight
15:00-15:30: Coffee Break
15:30-16:15: Rump Session, Open discussion
Abstracts
Gilad Stern, HUJI: Reaching Consensus for Asynchronous Distributed Key Generation
We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand n/3 faulty parties), has a constant expected number of rounds, has quasi-O(n^3) expected communication complexity, and assumes only the existence of a PKI. Prior to our work, the best A-DKG protocols required Omega(n) expected number of rounds, and Omega(n^4) expected communication.
Our A-DKG protocol relies on several building blocks that are of independent interest. We define and design a Proposal Election (PE) protocol that allows parties to retrospectively agree on a valid proposal after enough proposals have been sent from different parties. With constant probability the elected proposal was proposed by a nonfaulty party. In building our PE protocol, we design a Verifiable Gather protocol which allows parties to communicate which proposals they have and have not seen in a verifiable manner. The final building block to our A-DKG is a Validated Asynchronous Byzantine Agreement (VABA) protocol. We use our PE protocol to construct a VABA protocol that does not require leaders or an asynchronous DKG setup. Our VABA protocol can be used more generally when it is not possible to use threshold signatures.
Shir Cohen, Technion: Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
King and Saia were the first to break the quadratic word complexity bound for Byzantine Agreement in synchronous systems against an adaptive adversary, and Algorand broke this bound with near-optimal resilience (first in the synchronous model and then with eventual-synchrony). Yet the question of asynchronous sub-quadratic Byzantine Agreement remained open. To the best of our knowledge, we are the first to answer this question in the affirmative. A key component of our solution is a shared coin algorithm based on a VRF. A second essential ingredient is VRF-based committee sampling, which we formalize and utilize in the asynchronous model for the first time. Our algorithms work against a delayed-adaptive adversary, which cannot perform after-the-fact removals but has full control of Byzantine processes and full information about communication in earlier rounds. Using committee sampling and our shared coin, we solve Byzantine Agreement with high probability, with a word complexity of Õ(n) and O(1) expected time, breaking the O(n²) bit barrier for asynchronous Byzantine Agreement.
Shahar Papini, StarkWare: Cairo - A Turing complete CPU AIR for efficient ZK-STARKs
Proof systems allow one party to prove to another party that a certain statement is true. Most existing practical proof systems require that the statement will be represented in terms of polynomial equations over a finite-field. This makes the process of proving a statement rather complicated, and requires a new set of equations for each statement.
We present Cairo, a Turing-complete STARK-friendly CPU architecture. We describe a single set of polynomial equations for the statement that the execution of a program on this architecture is valid. Given a statement one wishes to prove, Cairo allows writing a program describing that statement, instead of writing a set of polynomial equations.
Aviv Yaish, HUJI: Correct Cryptocurrency ASIC Pricing: Are Miners Overpaying?
Cryptocurrencies that are based on Proof-of-Work often rely on special purpose hardware (ASICs) to perform mining operations that secure the system.
We argue that ASICs have been mispriced by miners and sellers that only consider their expected returns, and that in fact mining hardware should be treated as a bundle of financial options that, when exercised, convert electricity to virtual coins. We provide a method of pricing ASICs based on this insight, and compare the prices we derive to actual market prices.
Contrary to the widespread belief that ASICs are worth less if the cryptocurrency is highly volatile, we show the opposite effect: volatility significantly increases value. Thus, if a coin’s volatility decreases, some miners may leave, affecting security. To prevent this, we suggest a new reward mechanism.
Finally we construct a portfolio of coins and bonds that provides returns imitating an ASIC, and evaluate its behavior: historically, realized revenues of such portfolios have significantly outperformed ASICs, showing that indeed there is a mispricing of hardware, and offering an alternative investment route for would-be miners.
Maya Dotan, HUJI: Efficient multi dimensional approximate consensus
Consider an asynchronous system where each node begins with some point in $\mathbb{R}^m$. Given some fixed $\epsilon > 0$, we wish to have every nonfaulty node eventually output a point in $\mathbb{R}^m$, where all outputs are within distance $\epsilon$ of each other, and are within the convex hull of the original nonfaulty inputs. This problem, when some of the nodes are adversarial, is known as the ``Byzantine Asynchronous Multidimensional Approximate Agreement'' problem.
Previous landmark work by Mendes et al. and Vaidya et al. presented two solutions to the problem. Both of these solutions require exponential computation by each node in each round. Furthermore, the work provides a lower bound showing that it is impossible to solve the task of approximate agreement if $n\leq (m+2)t$, and thus the protocols assume that $n>(m+2)t$.
We present a Byzantine Asynchronous Multidimensional Approximate Agreement protocol in the validated setting of Cachin et al. Our protocol terminates after a logarithmic number of rounds, and requires only polynomial computation in each round. Furthermore, it is resilient to $t<\frac{n}{3}$ Byzantine nodes, which we prove to be optimal in the validated setting. In other words, working on the task in the validated setting allows us to significantly improve on previous works in several significant metrics. In addition, the techniques presented in this paper can easily yield a protocol in the original non-validated setting which requires exponential computation only in the first round, and polynomial computation in every subsequent round.
Lastly we discuss how this technique can be used to build a Blockchain-style DAG protocol.
Roi Bar Zur,Technion: Efficient MDP Analysis for Selfish-Mining in Blockchains
Roi Bar-Zur, Ittay Eyal, Aviv Tamar
A proof of work (PoW) blockchain protocol distributes rewards to its participants, called miners, according to their share of the total computational power. Sufficiently large miners can perform selfish mining - deviate from the protocol to gain more than their fair share. Such systems are thus secure if all miners are smaller than a threshold size so their best response is following the protocol.
To find the threshold, one has to identify the optimal strategy for miners of different sizes, i.e., solve a Markov Decision Process (MDP). However, because of the PoW difficulty adjustment mechanism, the miners' utility is a non-linear ratio function. We therefore call this an Average Reward Ratio (ARR) MDP. Sapirshtein et al. were the first to solve ARR MDPs by solving a series of standard MDPs that converge to the ARR MDP solution.
W e present a novel technique for solving an ARR MDP by solving a single standard MDP. The crux of our approach is to augment the MDP such that it terminates randomly, within an expected number of rounds. We call this Probabilistic Termination Optimization (PTO), and the technique applies to any MDP whose utility is a ratio function. We bound the approximation error of PTO - it is inversely proportional to the expected number of rounds before termination, a parameter that we control. Empirically, PTO's complexity is an order of magnitude lower than the state of the art.
PTO can be easily applied to different blockchains. For example, we use it to tighten the bound on the threshold for selfish mining in Ethereum. PTO can also be used for solving more complex protocols with intractable state spaces by combining it with deep RL.
Yaron Kaner, IDC Herzliya: Bitcoin+: Cheap Support for Complex Spending Conditions in a UTXO Ledger
Cryptocurrencies can be used merely to transfer value between identities, but many of the more interesting uses of cryptocurrencies require contracts, e.g, “a transfer of X coins from party S to party R should occur only if conditions A and B hold”. Bitcoin (and related cryptocurrencies) place strict limits on the language in which these conditions can be phrased. In particular, they have limited length and don’t allow loops.
In this talk I will discuss my thesis which I wrote with the guidance of Dr. Tal Moran from the Interdisciplinary Center Herzliya.
In the work, we show how to augment the Bitcoin scripting language with a single “innocuous” operation to that allows us to create “meta conditions” with much more expressive power (e.g., as defined by arbitrarily-sized circuits).
We construct a protocol to compile such meta-conditions into a set of (augmented) Bitcoin transactions. We then show how to use this compiler to realize a full “meta-ledger” functionality, which we show is secure in the universal composability framework.
Itay Tsabary, Technion: MAD-HTLC: Because HTLC is Crazy-Cheap to Attack
Smart Contracts and transactions allow users to implement elaborate constructions on cryptocurrency blockchains like Bitcoin and Ethereum. Many of these constructions, including operational payment channels and atomic swaps, use a building block called Hashed Time-Locked Contract (HTLC).
In this work, we distill from HTLC a specification (HTLC-Spec), and present an implementation called Mutual-Assured-Destruction Hashed Time-Locked Contract (MAD-HTLC). MAD-HTLC employs a novel approach of utilizing the existing blockchain operators, called miners, as part of the design. If a user misbehaves, MAD-HTLC incentivizes the miners to confiscate all her funds. We prove MAD-HTLC's security using the UC framework and game-theoretic analysis.
We demonstrate MAD-HTLC's efficacy and analyze its overhead by instantiating it on Bitcoin's and Ethereum's operational blockchains.
Notably, current miner software makes only little effort to optimize revenue, since the advantage is relatively small. However, as the demand grows and other revenue components shrink, miners are more motivated to fully optimize their fund intake. By patching the standard Bitcoin client, we demonstrate such optimization is easy to implement, making the miners natural enforcers of MAD-HTLC.
Finally, we extend previous results regarding HTLC vulnerability to bribery attacks. An attacker can incentivize miners to prefer her transactions by offering high transaction fees. We demonstrate this attack can be easily implemented by patching the Bitcoin client, and use game-theoretic tools to qualitatively tighten the known cost bound of such bribery attacks in presence of rational miners. We identify bribe opportunities occurring on the Bitcoin and Ethereum main networks where a few dollars bribe could yield tens of thousands of dollars in reward (e.g., $2 for over $25K).
Saar Tochner, HUJI: Differentially-Private Payment Channels with Twilight
Payment channel networks (PCNs) provide a faster and cheaper alternative to transactions recorded on the blockchain. Clients can trustlessly establish payment channels with relays by locking coins and then send signed payments that shift coin balances over the network's channels without recording their payment history on the blockchain. Although payments are never published, anyone can track a client's payment by monitoring changes in coin-balances over the network's channels.
We present Twilight, the first PCN that provides a rigorous differential privacy guarantee to its users.
Relays in Twilight run a noisy payment processing mechanism that hides the payments they carry. This mechanism increases the relay's cost, so Twilight combats selfish relays, that wish to avoid it, using a trusted execution environment (TEE) that ensures they follow its protocol.
The logic inside the TEE does not keep a mutable state which excludes corruption attacks by the hosting relay and simplifies the security analysis, and Twilight ensures that even if a relay breaks the TEE's security, it cannot break the integrity of the PCN.
We analyze Twilight in terms of privacy and cost and study the trade-off between them. We provide a prototype implementation of this system using Intel's SGX framework and evaluate its performance.