Paper review. Service-oriented sharding with Aspen

This week in our seminar, we discussed this linked whitepaper/shortpaper from Adem Efe Gencer, Robbert van Renesse, Emin Gün Sirer.

The problem

Blockchains provide trustless auditability, tamper-resistance, and transparency due to the face of Byzantine participants.  As such there is a community of users that would like to use blockchains to record in an authoritative manner transactions/provenance for many assets (in addition to the prevalent use of cryptocurrencies), such as gold, silver, diamonds, gems, land records, deeds, mortgages, boat titles, fine art, health records, and domain names.

The simplest approach address this demand is to layer these additional blockchains on top of an existing secure blockchain such as Bitcoin. The OP_RETURN opcode is adopted for this purpose, and its use has been increasing rapidly. However, this is not scalable, as it leads to a stream of costly and burdensome transactions. And Bitcoin blockchain is already overburdened and crawling.

The other approach is to create a dedicated, specialized, standalone blockchain for each asset. But that approach suffers from the lack of mining power. How do you bootstrap each blockchain? (That is not very easy problem, especially initially when the number of miners is low, how do you know Byzantine miners are in the minority? At least when piggybacking on BitCoin we are assured that the blockchain had sufficient mining power to withstand attacks.) Moreover, even if it is possible to create a separate thriving blockchain ecosystem for each asset, that would be very wasteful. Given that Bitcoin mining consumes more electricity than many countries in the world does, what would be the cost of having so many different chains? Pretty please, let's not burn down the planet.

The main idea

The proposed protocol, Aspen, securely shards the blockchain (say a popular blockchain like Bitcoin) to provide high scalability to the service users.

Sharding is a well-established technique to improve scalability by distributing contents of a database across nodes in a network. But sharding blockchains is non-trivial. The main challenge is to preserve the trustless nature while hiding transactions in other services of a blockchain from users participating in one service.

"Aspen employs a sharding approach that comes with the following benefits: (1) preserves the total computational power of miners to secure the whole blockchain, (2) prevents users from double-spending their funds while maintaining the same trustless setup assumptions as Bitcoin, (3) improves scalability by absolving non-miner participants --i.e. service users-- from the responsibility of storing, processing, and propagating irrelevant data to confirm the validity of services they are interested in."

The paper would benefit a lot from clarifying this point further. There are two different entities in the blockchain: the service users and the miners. The sharding in Aspen helps reduce the workload on the users, because the users can just focus the transactions on the service they are using. On the other hand, the miners need to know about the history of all the services/channels as well as their service and integration rules. The miners are the nodes that generate the keyblocks and publish service transactions as microblocks as described below.

The architecture

Aspen is an instantiation of service-oriented sharding on Bitcoin-NG. Please go read my short summary of the Bitcoin-NG paper, if you are unfamiliar with it. It is a great paper that prescribes a way to scale the throughput of a PoW blockchain.

Each channel corresponds to a service. Each channel contains 1) the global genesis block (the exact same special block for each channel) 2) all key blocks (the exact same set of blocks for all channels) and 3) the set of microblocks containing custom transactions exclusive to that service.

In other words, Aspen distributes transactions to microblocks with respect to services. The key blocks keep microblock chains together; the key blocks are not per-service, they are the same (i.e. common, shared) for all services.

If you like to look at this from a service-oriented perspective, there are two protocols for each channel/service:
1) A service protocol defines the validity of transactions in a given channel, including the syntax for each transaction type, the relationship between transactions within a channel, the size, frequency, and format constraints for blocks that keep transactions.
2) An integration protocol specifies the security, incentive mechanism, valid service numbers, the genesis block, and the inter-channel communication process between the payment channel and the other channels.

Each channel maintains key blocks to enforce the integration protocol. And each channel maintains the microblocks only to contain the service-specific transactions. Two special channels, payment (to exchange funds) and registration (to add/update services), are defined by Aspen to help bootstrap the blockchain. We discuss these two next.

Flow of funds

To prevent double spending, Aspen uses the payment channel to make each fund spendable only in a specific channel. A special payment channel transaction, funding pore, enables users to lock funds to other channels. Transfers across channels are allowed only in one way, from the payment channel to others.

Alternatively, users can directly buy locked funds at the target channel to pay for the service running on the corresponding channel. Aspen enforces a high minimum fee for serializing funding pores to (1) discourage users from bloating the payment channel and (2) improve the fungibility of funds in nonpayment channels.

As shown in Figure 3.b, a coinbase transaction in a key block provides separate outputs to compensate the current and the previous miner for each service they provision.

Service integration

Users propose protocols to introduce or update services by generating transactions for the registration channel. A service protocol is specified in a platform independent language such as WebAssembly or Lua. The miners conduct an election to choose a registration channel transaction and indicate their choice using ballots. If a particular transaction is referred by more than a certain fraction of ballots, its protocols become active.

The voting process works similar to that in Bitcoin.

MAD questions

1. It may be too much of a burden to require that the miners store/process the entire history of all services/channels, and could create a scalability barrier for the blockchain. Checkpoints (a.k.a. snapshots) can help for this as they make the state more compact: you don't need to go all the way to the origin block, instead you can refer to a recent checkpoint to validate transactions. The paper mentions that the key blocks include checkpoints, but it is unclear if these checkpoints are snapshots at all.

What could go wrong if we included checkpoints as snapshots? An obvious strawman attack is where the leader is proposing an incorrect checkpoint to misrepresent information. I guess the other miners can notice this and add a poison transaction.

I don't know if there are other measures need to be taken to incorporate checkpoints. On a philosophical point, does using checkpoints violate the transparency of blockchain? When the whole log history is available, the nodes have more information to go with. Starting from a recent checkpoint adds some obscurity to the history.

2. It may not be necessary to link all the services together with each key block. So it may be possible to relax Aspen to have specialized miners that only track certain services; when those miners mine a keyblock they would only link the corresponding tracked services together. Statistically, each service will get a miner that tracks it soon and get a key block that integrates it to other services.

I am not sure if this relaxation would lead to security problems. I guess one problem could be incompatibilities between to consequent miners; the rewarding/incentive mechanism may need to be rethought for miners of different kinds trailing each other. Another problem could be that some less popular services may attract less number of miners and high latency transactions. On the other hand, if there is way to make this work, this relaxation can help alleviate the scalability problem for the miners as the number of services grow.


Popular posts from this blog

Graviton2 and Graviton3

Foundational distributed systems papers

Learning a technical subject

SQLite: Past, Present, and Future

Learning about distributed systems: where to start?

Strict-serializability, but at what cost, for what purpose?

CockroachDB: The Resilient Geo-Distributed SQL Database

The Seattle Report on Database Research (2022)

Amazon Aurora: Design Considerations + On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes

Warp: Lightweight Multi-Key Transactions for Key-Value Stores