Search

Automated Market Makers (AMMs) are a cornerstone of decentralized finance. They are smart contracts (stateful programs) running on blockchains. They enable virtual token exchange: traders swap tokens with the AMM for a fee, while liquidity providers supply liquidity and receive these fees. Demand for AMMs is growing rapidly, but our experiment-based estimates show that current architectures cannot meet the projected demand by 2029. This is because the execution of existing AMMs is non-parallelizable. We present SAMM, an AMM comprising multiple shards. All shards are AMMs running on the same chain, but their independence enables parallel execution. Unlike classical sharding solutions, here security relies on incentive compatibility. Therefore, SAMM introduces a novel fee design. Through analysis of Subgame-Perfect Nash Equilibria (SPNE), we show that SAMM incentivizes the desired behavior: liquidity providers balance liquidity among all shards, overcoming destabilization attacks, and trades are evenly distributed. We validate our game-theoretic analysis with a simulation using real-world data. We evaluate SAMM by implementing and deploying it on local testnets of the Sui and Solana blockchains. To our knowledge, this is the first quantification of high-demand-contract performance. SAMM improves throughput by 5x and 16x, respectively, potentially more with better parallelization of the underlying blockchains. It is directly deployable, mitigating the upcoming scaling bottleneck.

A diffusion auction is a market to sell commodities over a social network, where the challenge is to incentivize existing buyers to invite their neighbors in the network to join the market. Existing mechanisms have been designed to solve the challenge in various settings, aiming at desirable properties such as non-deficiency, incentive compatibility and social welfare maximization. Since the mechanisms are employed in dynamic networks with ever-changing structures, buyers could easily generate fake nodes in the network to manipulate the mechanisms for their own benefits, which is commonly known as the Sybil attack. We observe that strategic agents may gain an unfair advantage in existing mechanisms through such attacks. To resist this potential attack, we propose two diffusion auction mechanisms, the Sybil tax mechanism (STM) and the Sybil cluster mechanism (SCM), to achieve both Sybil-proofness and incentive compatibility in the single-item setting. Our proposal provides the first mechanisms to protect the interests of buyers against Sybil attacks with a mild sacrifice of social welfare and revenue.

With the development of blockchain applications, the requirements for file storage in blockchain are increasing rapidly. Many protocols, including Filecoin, Arweave, and Sia, have been proposed to provide scalable decentralized file storage for blockchain applications. However, the reliability is not well promised by existing protocols. Inspired by the idea of insurance, we innovatively propose a decentralized file storage protocol in blockchain, named as FileInsurer, to achieve both scalability and reliability. While ensuring scalability by distributed storage, FileInsurer guarantees reliability by enhancing robustness and fully compensating for the file loss. Specifically, under mild conditions, we prove that no more than 0.1\% value of all files should be compensated even if half of the storage collapses. Therefore, only a relatively small deposit needs to be pledged by storage providers to cover the potential file loss. Because of lower burdens of deposit, storage providers have more incentives to participate in the storage network. FileInsurer can run in the top layer of the InterPlanetary File System (IPFS), and thus it can be directly applied in Web 3.0, Non-Fungible Tokens, and Metaverse.

The Non-Fungible Token (NFT) is viewed as one of the important applications of blockchain technology. Although NFT has a large market scale and multiple practical standards, several limitations of the existing mechanism in NFT markets exist. This work proposes a novel securitization and repurchase scheme for NFT to overcome these limitations. We first provide an Asset-Backed Securities (ABS) solution to settle the limitations of non-fungibility of NFT. Our securitization design aims to enhance the liquidity of NFTs and enable Oracles and Automatic Market Makers (AMMs) for NFTs. Then we propose a novel repurchase protocol for a participant owing a portion of NFT to repurchase other shares to obtain the complete ownership. As participants may strategically bid during the acquisition process, our repurchase process is formulated as a Stackelberg game to explore the equilibrium prices. We also provide solutions to handle difficulties at market such as budget constraints and lazy bidders., Comment: To appear in Financial Cryptography and Data Security 2022

Nowadays, sharding is deemed as a promising way to save traditional blockchain protocols from their low scalability. However, such technique also brings several potential risks and huge communication overheads. An improper design may give rise to the inconsistent state among different committees. Further, the communication overheads arising from cross-shard transactions unfortunately reduce the system's performance. In this paper, we first summarize five essential issues that all sharding blockchain designers face. For each issue, we discuss its key challenge and propose our suggested solutions. In order to break the performance bottlenecks, we propose a reputation mechanism for selecting leaders. The term of reputation in our design reflects each node's honest computation resources. In addition, we introduce a referee committee and partial sets in each committee, and design a recovery procedure in case the leader is malicious. Under the design, we prove that malicious leaders will not hurt the system and will be evicted. Furthermore, we conduct a series of simulations to evaluate our design. The results show that selecting leaders by the reputation can dramatically improve the system performance.

The design of permissioned blockchains places an access control requirement for members to read, access, and write information over the blockchains. In this paper, we study a hierarchical scenario to include three types of participants: providers, collectors, and governors. To be specific, providers forward transactions, collected from terminals, to collectors; collectors upload received transactions to governors after verifying and labeling them; and governors validate a part of received labeled transactions, pack valid ones into a block, and append a new block on the ledger. Collectors in the hierarchical model play a crucial role in the design: they have connections with both providers and governors, and are responsible for collecting, verifying, and uploading transactions. However, collectors are rational and some of them may behave maliciously (not necessarily for their own benefits). In this paper, we introduce a reputation protocol as a measure of the reliability of collectors in the permissioned blockchain environment. Its objective is to encourage collectors to behave truthfully and, in addition, to reduce the verification cost. The verification cost on provider $p$ is defined as the total number of invalid transactions provided by $p$ and checked by governors. Through theoretical analysis, our protocol with the reputation mechanism has a significant improvement in efficiency. Specifically, the verification loss that governors suffer is proved to be asymptotically $O(\sqrt{T_{total}})$ ($T_{total}$, representing the number of transactions verified by governors and provided by $p$), as long as there exists at least one collector who behaves well. At last, two typical cases where our model can be well applied are also demonstrated.

Traditional public distributed ledgers have not been able to scale-out well and work efficiently. Sharding is deemed as a promising way to solve this problem. By partitioning all nodes into small committees and letting them work in parallel, we can significantly lower the amount of communication and computation, reduce the overhead on each node's storage, as well as enhance the throughput of the distributed ledger. Existing sharding-based protocols still suffer from several serious drawbacks. The first thing is that all non-faulty nodes must connect well with each other, which demands a huge number of communication channels in the network. Moreover, previous protocols have faced great loss in efficiency in the case where the honesty of each committee's leader is in question. At the same time, no explicit incentive is provided for nodes to actively participate in the protocol. We present CycLedger, a scalable and secure parallel protocol for distributed ledger via sharding. Our protocol selects a leader and a partial set for each committee, who are in charge of maintaining intra-shard consensus and communicating with other committees, to reduce the amortized complexity of communication, computation, and storage on all nodes. We introduce a novel semi-commitment scheme between committees and a recovery procedure to prevent the system from crashing even when leaders of committees are malicious. To add incentive for the network, we use the concept of reputation, which measures each node's trusty computing power. As nodes with a higher reputation receive more rewards, there is an encouragement for nodes with strong computing ability to work honestly to gain reputation. In this way, we strike out a new path to establish scalability, security, and incentive for the sharding-based distributed ledger., Comment: Full version of the paper in IPDPS2020