- How Liveness Separates CFMMs and Order Books
Authors: Tarun Chitra, Guillermo Angeris, and Alex Evans
Constant function market makers (CFMMs) are popular mechanisms for trading of digital assets. However, they have notable drawbacks relative to conventional limit order books common to equity markets. These drawbacks include economic adverse selection costs for liquidity providers and poorer latency response for active traders. But are order books really better in a decentralized setting? Empirical evidence suggests that when decentralized systems lose liveness, CFMMs are preferred to order books by liquidity providers. Liveness losses often correlate with large price changes off-chain, so that residual on-chain liquidity can dampen liquidation cascades upon regaining liveness. We provide a theoretical underpinning for when one should prefer a CFMM to an order book. Our results demonstrate that application-level liveness interacts with consensus liveness in a non-trivial manner.
Link: https://web.stanford.edu/~guillean/papers/cfmm-ob.pdf
- HPKS: High Performance Kubernetes Scheduling for Dynamic Blockchain Workloads in Cloud Computing
Authors: Zhenwu Shi, Chenming Jiang, Landu Jiang, and Xue Liu
Emerging blockchain technologies have been increasingly popular and reforming our daily lives. Fusing blockchain technology with existing cloud systems has a great benefits in both improving the functionality/performance and guaranteeing the security/privacy. However, most existing commercial systems fail to address the characteristics of PoS blockchain applications in the cloud. In real-world scenarios, jobs/pods may arrive and leave due to the workload changes. Traditionally, the selection process is based on the state of the workers, e.g., resource availability and specifications of pods. In this paper, we not only provide an optimal solution for offline workloads management which minimizes the number of used workers to reduce the total computational resource demand, but also propose a high performance Kubernetes scheduling scheme HPKS, which maximizes the utilization of workers. Specifically, extensive experiments based on real PoS blockchain applications shows that HPKS reduces the average worker nodes usage by 13.0%. Additionally, the overall increase of Makespan using HPKS is less than 3% when compared to the default scheduler available in Kubernetes.
Link: CSDL | IEEE Computer Society
- BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
Authors: Bicheng Ying, Kun Yuan, Hanbin Hu, Yiming Chen, and Wotao Yin
Decentralized algorithm is a form of computation that achieves a global goal through local dynamics that relies on low-cost communication between directly-connected agents. On large-scale optimization tasks involving distributed datasets, decentralized algorithms have shown strong, sometimes superior, performance over distributed algorithms with a central node. Recently, developing decentralized algorithms for deep learning has attracted great attention. They are considered as low-communication-overhead alternatives to those using a parameter server or the Ring-Allreduce protocol. However, the lack of an easy-to-use and efficient software package has kept most decentralized algorithms merely on paper. To fill the gap, we introduce BlueFog, a python library for straightforward, high-performance implementations of diverse decentralized algorithms. Based on a unified abstraction of various communication operations, BlueFog offers intuitive interfaces to implement a spectrum of decentralized algorithms, from those using a static, undirected graph for synchronous operations to those using dynamic and directed graphs for asynchronous operations. BlueFog also adopts several system-level acceleration techniques to further optimize the performance on the deep learning tasks. On mainstream DNN training tasks, BlueFog reaches a much higher throughput and achieves an overall 1.2Ă âŒ 1.8Ă speedup over Horovod, a state-of-the-art distributed deep learning package based on Ring-Allreduce. BlueFog is open source at GitHub - Bluefog-Lib/bluefog: Distributed and decentralized training framework for PyTorch over graph.
Link: https://arxiv.org/pdf/2111.04287.pdf
- Foundations of Transaction Fee Mechanism Design
Authors: Hao Chung and Elaine Shi
In blockchains such as Bitcoin and Ethereum, users compete in a transaction fee auction to get their transactions confirmed in the next block. A line of recent works set forth the desiderata for a âdreamâ transaction fee mechanism (TFM), and explored whether such a mechanism existed. A dream TFM should satisfy 1) user incentive compatibility (UIC), i.e., truthful bidding should be a userâs dominant strategy; 2) miner incentive compatibility (MIC), i.e., the minerâs dominant strategy is to faithfully implement the prescribed mechanism; and 3) miner-user side contract proofness (SCP), i.e., no coalition of the miner and one or more user(s) can increase their joint utility by deviating from the honest behavior. The weakest form of SCP is called 1-SCP, where we only aim to provide resilience against the collusion of the miner and a single user. Sadly, despite the various attempts, to the best of knowledge, no existing mechanism can satisfy all three properties in all situations.
Since the TFM departs from classical mechanism design in modeling and assumptions, to date, our understanding of the design space is relatively little. In this paper, we further unravel the mathematical structure of transaction fee mechanism design by proving the following results: Can we have a dream TFM? We prove a new impossibility result: assuming finite block size, no single-parameter, non-trivial, possibly randomized TFM can simultaneously satisfy UIC and 1-SCP. Consequently, no non-trivial TFM can satisfy all three desired properties simultaneously. This answers an important open question raised by Roughgarden in his recent work. Rethinking the incentive compatibility notions. We observe that the prevalently adopted incentive compatibility notions may be too draconian and somewhat flawed. We rectify the existing modeling techniques, and suggest a relaxed incentive compatibility notion that captures additional hidden costs of strategic deviation. We construct a new mechanism called the âburning second-price auctionâ, and show that it indeed satisfies the new incentive compatibility notions. We additionally prove that the use of randomness is necessary under the new incentive compatibility notions for âusefulâ mechanisms that resist the coalitions of the miner and at least 2 users. Do the new design elements make a difference? Unlike classical mechanisms, TFMs may employ a couple new design elements that are idiosyncratic to blockchains. For example, a burn rule (employed by Ethereumâs EIP-1559) allows part to all of the payment from the users to be burnt rather than paid to the miner. Some mechanisms also allow unconfirmed transactions to be included in the block, to set the price for others. Our work unveils how these new design elements actually make a difference in TFM design, allowing us to achieve incentive compatible properties that would otherwise be impossible.
Link: https://arxiv.org/pdf/2111.03151.pdf
- Themis: Fast, Strong Order-Fairness in Byzantine Consensus
Authors: Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan
We introduce Themis, a scheme for introducing fair ordering of transactions into (permissioned) Byzantine consensus protocols with at most f faulty nodes among n â„ 4f + 1. Themis is the first such scheme to achieve (optimistic) linear communication complexity. At the same time, it enforces the strongest notion of fair ordering proposed to date. Themis also achieves standard liveness, rather than the weaker notion of previous work.
We show experimentally that Themis can be integrated into state-of-the-art consensus protocols with minimal modification or performance overhead. Additionally, we introduce a suite of experiments of general interest for evaluating the practical strength of various notions of fair ordering and the resilience of fair-ordering protocols to adversarial manipulation. We use this suite of experiments to show that the notion of fair ordering enforced by Themis is significantly stronger in theory and for realistic workloads than those of competing systems.
We believe Themis offers strong practical protection against many types of transaction-ordering attacksâsuch as front-running and back-runningâthat are currently impacting commonly used smart contract systems.
Link: https://eprint.iacr.org/2021/1465.pdf
- Augmented Reality meets Non-Fungible Tokens: Insights Towards Preserving Property Rights
Authors: Mihai DuguleanÄ and Florin GĂźrbacia
Non-fungible tokens are one of the newest use-cases of blockchain technology. Ethereum Virtual Machine (EVM)-based blockchains such as Ethereum, Binance Smart Chain (BSC), or Polygon/Matic have standardized this type of tokens using interfaces such as ERC721 and ERC1155. This development fostered a connection between blockchain and Mixed Reality technologies, which can now coexist in cohesive applications. In this paper, we present the opportunities and challenges resulting from using Augmented Reality NFTs, with a particular focus on the preservation of property, whether it is physical or purely digital. We present a methodology that can ensure the protection of privacy and the preservation of intellectual property when transitioning assets from the virtual to the physical world.
Link: CSDL | IEEE Computer Society
- DevOps for Ethereum Blockchain Smart Contracts
Authors: Maximilian Wohrer and Uwe Zdun
With the evolution and proliferation of blockchain, the technology is becoming more prevalent in enterprise software development. Using the already proven DevOps approach in this setting makes sense, as it can accelerate the general pace of software development and delivery, improve software quality, and increase overall productivity. However, there is currently a lack of guidance on a structured DevOps approach and a breakdown of the specifics in the context of blockchain-based software development. Therefore, we combined gray literature and DevOps application studies from pertinent GitHub projects to systematically investigate current practices and solution approaches for an efficient blockchain-oriented DevOps procedure. In this process, we elaborated procedural steps and related activities according to the main stages of Continuous Integration and Continuous Delivery. Our research shows that core DevOps concepts and activities are similar to other areas and are entirely possible with already established CI/CD solutions that orchestrate the right tools, with the difference that more rigorous testing and differentiated deployment practices are required due to the inherent immutability of blockchain.
Link: http://eprints.cs.univie.ac.at/7141/1/document.pdf
- Smart Contracts and Solidity Code Summarization
Author: Matteo Zhang
Blockchain became a hot topic in the last decade. Blockchain is the underlying technology enabling Bitcoin transfers. In particular, this technology ensures the integrity of digital records and enables the transfer of decentralized digital currency. After the creation of bitcoin, Vitalik Buterin saw the unexpressed potential of this technology in other fields that go beyond a simple transfer of value and created Ethereum, an open-source, decentralized blockchain with smart contract functionality. Consequently, smart contracts became the centre of the Blockchain economy. Smart contracts are programs that run on the blockchain. In the Ethereum case, the most used programming language to code smart contracts is Solidity, a relatively new programming language. One of the main problems in computer science is source code documentation, and this is remarkably true for Solidity. When Solidity developers need to understand smart contracts code, the code generally lacks comments and proper documentation. In order to provide code documentation to programmers and provide a coherent summary of the source code in the Blockchain context, this thesis presents a system to automatically generate comments for Solidity smart contracts code. The created system âSoliditySummarizerâ will significantly help beginners understand the code, given that the developers spend most of their time on this task. Furthermore, the system could also be useful for people with limited coding skills, according to our final survey, since it will help them understand the source code of smart contracts with detailed summaries. In the first part of the thesis, the state of the art in solidity code summarization is analyzed. In the second part, the state of the art in general code summarization techniques are presented. Then, the developed system is described. Such system relies on transformer models to perform natural language generation from source code. The thesis also presents the dataset created to train and test the system, which was created by collecting and cleaning Solidity smart contracts. Finally, results show that the created tool provides better results than the current state of the art solidity document generation tools.
Link: https://webthesis.biblio.polito.it/20620/
- Effect of Miner Incentive on the Confirmation Time of Bitcoin Transactions
Authors: Befekadu G. Gebraselase, Bjarne E. Helvik, and Yuming Jiang
Blockchain is a technology that provides a distributed ledger that stores previous records while maintaining consistency and security. Bitcoin is the first and largest decentralized electronic cryptographic system that uses blockchain technology. It faces a challenge in making all the nodes synchronize and have the same overall view with the cost of scalability and performance. In addition, with minersâ financial interest playing a significant role in choosing transactions from the backlog, small fee or small fee per byte value transactions will exhibit more delays. To study the issues related to the systemâs performance, we developed an M(t)/MN /1 model. The backlogâs arrival follows an inhomogeneous Poison process to the system that has infinite buffer capacity, and the service time is distributed exponentially, which removes N transactions at time. Besides validating the model with measurement data, we have used the model to study the reward distribution when miners take transaction selection strategies like fee per byte, fee-based, and FIFO. The analysis shows that smaller fee transactions exhibit higher waiting times, even with increasing the block size. Moreover, the miner transaction selection strategy impacts the final gain.
Link: https://arxiv.org/pdf/2111.02725.pdf
- Asynchronous Proof-of-Stake
Authors: Jakub Sliwinski and Roger Wattenhofer
We introduce a new permissionless blockchain architecture called Cascade (Consensusless, Asynchronous, Scalable, Deterministic and Efficient). The protocol is completely asynchronous, and does rely on neither randomness nor proof-of-work. Transactions exhibit finality within one round trip of communication.
Cascade is consensusless and only satisfies a relaxed form of consensus by introducing a weaker termination property. Without full consensus, the protocol does not support certain applications, such as general smart contracts. However, many important applications do not require general smart contracts, and Cascade is an advantageous solution for these applications. In particular, the architecture can implement the functionality of a cryptocurrency such as Bitcoin, replacing Bitcoinâs energy-hungry proof-of-work with a proof-of-stake validation.
- ZKCPlus: Optimized Fair-exchange Protocol Supporting Practical and Flexible Data Exchange
Authors: Yun Li, Cun Ye, Yuguang Hu, Ivring Morpheus, Yu Guo, Chao Zhang, Yupeng Zhang, Zhipeng Sun, Yiwen Lu, and Haodi Wang
Devising a fair-exchange protocol for digital goods has been an appealing line of research in the past decades. The Zero-Knowledge Contingent Payment (ZKCP) protocol first achieves fair exchange in a trustless manner with the aid of the Bitcoin network and zeroknowledge proofs. However, it incurs setup issues and substantial proving overhead, and has difficulties handling complicated validation of large-scale data.
In this paper, we propose an improved solution ZKCPlus for practical and flexible fair exchange. ZKCPlus incorporates a new commit-and-prove non-interactive zero-knowledge (CP-NIZK) argument of knowledge under standard discrete logarithmic assumption, which is prover-efficient for data-parallel computations. With this argument we avoid the setup issues of ZKCP and reduce sellerâs proving overhead, more importantly enable the protocol to handle complicated data validations.
We have implemented a prototype of ZKCPlus and built several applications atop it. We rework a ZKCPâs classic application of trading sudoku solutions, and ZKCPlus achieves 21-67Ă improvement in seller efficiency than ZKCP, with only milliseconds of setup time and 1 MB public parameters. In particular, our CP-NIZK argument shows an order of magnitude higher proving efficiency than the zkSNARK adopted by ZKCP. We also built a realistic application of trading trained CNN models. For a 3-layer CNN containing 8,620 parameters, it takes less than 1 second to prove and verify an inference computation, and also about 1 second to deliver the parameters, which is very promising for practical use.
Link: http://netsec.ccert.edu.cn/files/papers/CCS21-ZKCPlus.pdf
- Your Smart Contracts Are Not Secure: Investigating Arbitrageurs and Oracle Manipulators in Ethereum
Authors: Kevin Tjiam, Rui Wang, Huanhuan Chen, and Kaitai Liang
Smart contracts on Ethereum enable billions of dollars to be transacted in a decentralized, transparent and trustless environment. However, adversaries lie await in the Dark Forest, waiting to exploit any and all smart contract vulnerabilities in order to extract profits from unsuspecting victims in this new financial system. As the blockchain space moves at a breakneck pace, exploits on smart contract vulnerabilities rapidly evolve, and existing research quickly becomes obsolete. It is imperative that smart contract developers stay up to date on the current most damaging vulnerabilities and countermeasures to ensure the security of usersâ funds, and to collectively ensure the future of Ethereum as a financial settlement layer. This research work focuses on two smart contract vulnerabilities: transaction-ordering dependency and oracle manipulation. Combined, these two vulnerabilities have been exploited to extract hundreds of millions of dollars from smart contracts in the past year (2020-2021). For each of them, this paper presents: (1) a literary survey from recent (as of 2021) formal and informal sources; (2) a reproducible experiment as code demonstrating the vulnerability and, where applicable, countermeasures to mitigate the vulnerability; and (3) analysis and discussion on proposed countermeasures. To conclude, strengths, weaknesses and trade-offs of these countermeasures are summarised, inspiring directions for future research.