Saar Tochner

Publications

• Gen-T: Reduce Distributed Tracing Operational Costs Using Generative Models [pdf] (AGL @ NeurIPS 23')

  Authors: Saar Tochner^*, Giulia Fanti Vyas Sekar

  Abstract: Distributed tracing (DT) is an important aspect of modern microservice operations. It allows ▽ More Distributed tracing (DT) is an important aspect of modern microservice operations. It allows operators to troubleshoot problems by modeling the sequence of services a specific request traverses in the system. Transmitting traces incurs significant costs, often forcing operators to use coarse-grained prefiltering or sampling techniques. This creates undesirable tradeoffs between cost and fidelity.
  We propose to circumvent these issues using recent advances in deep generative modeling. We envision the use of generative models to capture the semantic structure of collected traces in a lossy-yet-succinct way. Realizing this potential in practice is challenging. Naively extending ideas from the literature on deep generative models in timeseries generation or graph generation can result in poor cost-fidelity tradeoffs.
  In designing and implementing Gen-T, we tackle key algorithmic and systems challenges to make deep generative models practical for DT. We demonstrate practical integrations with industry standard frameworks (such as OpenTelemetry) and provide empirical evidence that Gen-T significantly outperforms conventional approaches in terms of cost-fidelity tradeoff. Our results reveal that Gen-T achieves a level of fidelity comparable to that of 1:15 sampling, which is more fine-grained than the default 1:20 sampling setting in the Opentelemetry documentation, while maintaining a cost profile equivalent to that of 1:100 lossless-compressed sampling (i.e., a 7x volume reduction). △ Less

• Blockchain Stretching & Squeezing: Manipulating Time For Your Best Interest [pdf] (ACM EC 22')

  Authors: Aviv Yaish^*, Saar Tochner^*, Aviv Zohar

  Abstract: We present a novel way for cryptocurrency miners to manipulate the effective interest-rate ▽ More We present a novel way for cryptocurrency miners to manipulate the effective interest-rate on loans or deposits they make on DeFi platforms by manipulating DAAs and changing the block-rate. This presents a new class of strategic manipulations available to miners. These manipulations allow miners to stretch and squeeze the time between consecutive blocks. We analyze these manipulations both analytically and empirically, and show that a 25% miner can stretch the time between consecutive blocks by up to 54% in Ethereum and 33% in Bitcoin, and squeeze it by up to 9% in Ethereum. Ethereum is particularly vulnerable, and even relatively small miners can seriously affect the block-rate. An interesting application of these manipulations is to create an artificial interest-rate gap between loans taken from one DeFi platform which accrues interest according to block height (such as Compound) and deposited in some other platform that does so according to elapsed time (like a bank, or other DeFi platforms such as Aave). Hence, stretching and squeezing the block-rate can decrease the interest paid on DeFi loans relative to external financial platforms. The profit made from this interest-rate gap provides a large incentive for miners to deviate. For example, a 25% Ethereum miner using our manipulations can increase mining profits by up to 35%, even after taking potential losses into consideration, such as less block-rewards. Our analysis of these manipulations and their mitigations has broad implications with regards to commonly-used cryptocurrency mechanisms and paradigms, such as Ethereum's difficulty-adjustment algorithm and reward schemes, with Ethereum's handling of uncle blocks being particularly manipulable. Interestingly, Bitcoin's mechanism is more resistant Ethereum's, owing to its larger incentives and a more resilient DAA. △ Less

• Twilight: A Differentially Private Payment Channel Network [pdf] (USENIX Security 22')

  Authors: Maya Dotan^*, Saar Tochner^*, Aviv Zohar, Yossi Gilad

  Abstract: Payment channel networks (PCNs) provide a faster and cheaper alternative to transactions ▽ More 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. 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 TEE does not store the channel’s state, which minimizes the trusted computing base. Crucially, 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 implement Twilight using Intel’s SGX framework and evaluate its performance using relays deployed on two continents. We show that a route consisting of 4 relays handles 820 payments/sec. △ Less

• SOK: Cryptocurrency Networking Context, State-of-the-Art, Challenges [pdf] (ACM Computing Surveys 21'; ARES 20')

  Authors: Maya Dotan, Yvonne-Anne Pignolet, Stefan Schmid, Saar Tochner, Aviv Zohar

  Abstract: Cryptocurrencies such as Bitcoin are realized using distributed systems and hence ▽ More Cryptocurrencies such as Bitcoin are realized using distributed systems and hence critically rely on the performance and security of the interconnecting network. The requirements on these networks and their usage, however can differ significantly from traditional communication networks, with implications on all layers of the protocol stack. This paper is motivated by these differences, and in particular by the observation that many fundamental design aspects of these networks are not well-understood today. In order to support the networking community to contribute to this emerging application domain, we present a structured overview of the field, from topology and neighbor discovery to block and transaction propagation. In particular, we provide the context, highlighting differences and commonalities with traditional networks, review the state-of-the-art, and identify open research challenges. Our paper can hence also be seen as a call-to-arms to improve the foundation on top of which cryptocurrencies are built. △ Less

• On Search Friction of Route Discovery in Offchain Networks [pdf] (IEEE Blockchains 20')

  Authors: Saar Tochner, Stefan Schmid

  Abstract: Offchain networks provide a promising solution to overcome the scalability challenges ▽ More Offchain networks provide a promising solution to overcome the scalability challenges of cryptocurrencies. However, design tradeoffs of offchain networks are still not well-understood today. In particular, offchain networks typically rely on fees-based incentives and hence require mechanisms for the efficient discovery of``good routes'': routes with low fees (cost efficiency) and a high success rate of the transaction routing (effectiveness). Furthermore, the route discovery should be confidential (privacy), and eg, not reveal information about who transacts with whom or about the transaction value. This paper provides an analysis of the ``search friction'' of route discovery, ie, the costs and tradeoffs of route discovery in large-scale offchain networks in which nodes behave strategically. As a case study, we consider the Lighning network and the route discovery service provided by the trampoline nodes, evaluating the tradeoff in different scenarios also empirically. Finally, we initiate the discussion of alternative charging schemes for offchain networks. △ Less

• Proofs of Useless Work - Positive and Negative Results for Wasteless Mining Systems [pdf] (GAMES 20')

  Authors: Maya Dotan^* Saar Tochner^*,

  Abstract: Many blockchain systems today, including Bitcoin, rely on Proof of Work (PoW). Proof ▽ More Many blockchain systems today, including Bitcoin, rely on Proof of Work (PoW). Proof of work is crucial to the liveness and security of cryptocurrencies. The assumption when using PoW is that a lot of trial and error is required on average before a valid block is generated. One of the main concerns raised with regard to this kind of system is the inherent need to "waste" energy on" meaningless" problems. In fact, the Bitcoin system is believed to consume more electricity than several small countries [5]. In this work we formally define three properties that are necessary for wasteless PoW systems:(1) solve" meaningful" problems (2) solve them efficiently and (3) be secure against double-spend attacks. We analyze these properties and deduce constraints that impose on PoW systems. In particular, we conclude that under realistic assumptions, the set of allowed functions for mining must be preimage resistant functions. Finally, we propose a modification to the Bitcoin consensus rule that allows users to upload a certain subset of preimage resistant problems and let the mining process solve them. We prove security against Double-Spend attacks identical to the existing security guarantee in Bitcoin today. △ Less

• Hijacking Routes in Payment Channel Networks: A Predictability Tradeoff [pdf] (ACM AFT 20')

  Authors: Saar Tochner, Aviv Zohar, Stefan Schmid

  Abstract: Off-chain transaction networks can mitigate the scalability issues of today's trustless ▽ More Off-chain transaction networks can mitigate the scalability issues of today's trustless electronic cash systems such as Bitcoin. However, these peer-to-peer networks also introduce a new attack surface which is not well-understood today. This paper identifies and analyzes, a novel Denial-of-Service attack which is based on route hijacking, i.e., which exploits the way transactions are routed and executed along the created channels of the network. This attack is conceptually interesting as even a limited attacker that manipulates the topology through the creation of new channels can navigate tradeoffs related to the way it attacks the network. Furthermore, the attack also highlights a fundamental design tradeoff for the defender (who determines its own routes): to become less predictable and hence secure, a rational node has to pay higher fees to nodes that forward its payments. We find that the three most common implementations for payment channels in Bitcoin (lnd, C-lightning, Eclair) approach routing differently. We begin by surveying the current state of the Lightning network and explore the routes chosen by these implementations. We find that in the current network nearly 60% of all routes pass through only five nodes, while 80% go through only 10 nodes. Thus, a relatively small number of colluding nodes can deny service to a large fraction of the network. We then turn to study an external attacker who creates links to the network and draws more routes through its nodes by asking for lower fees. We find that just five new links are enough to draw the majority (65% - 75%) of the traffic regardless of the implementation being used. The cost of creating these links is very low. We discuss the differences between implementations and eventually derive our own suggested routing policy, which is based on a novel combination of existing approaches. △ Less

• How to Pick Your Friends - A Game Theoretic Approach to P2P Overlay Construction [pdf] (ACM AFT 20')

  Authors: Saar Tochner, Aviv Zohar

  Abstract: A major limitation of open P2P networks is the lack of strong identities. This allows any ▽ More A major limitation of open P2P networks is the lack of strong identities. This allows any agent to attack the system by creating multiple false personas, thereby disrupting the overlay network's connectivity and sabotaging its operation. In this paper, we explore practical ways to defend P2P networks from such attacks. To do so, we employ a game theoretic approach to the management of each peer's list of known nodes and to the overlay construction mechanisms that utilize this list. We consider the interaction between defender and attacker agents as a zero-sum game. We show that the cost of attacks can be driven up substantially if the defender utilizes available information about peers it chooses to connect to, such as their IP address. In addition to theoretical analysis of the underlying game, we apply our approach to the Bitcoin P2P network and derive effective strategies that guarantee a high safety level against attacks. △ Less