Flash: An Asynchronous Payment System with Good-Case Linear Communication Complexity

While the original purpose of blockchains was to realize a payment system, it has been shown that, in fact, such systems do not require consensus and can be implemented deterministically in asynchronous networks. State-of-the-art payment systems employ Reliable Broadcast to disseminate payments and prevent double spending, which entails O(n^2) communication complexity per payment even if Byzantine behavior is scarce or non-existent.
Here we present Flash, the first payment system to achieve O(n) communication complexity per payment in the good case and O(n2) complexity in the worst-case, matching the lower bound. This is made possible by sidestepping Reliable Broadcast and instead using the blocklace — a DAG-like partially-ordered generalization of the blockchain — for the tasks of recording transaction dependencies, block dissemination, and equivocation exclusion, which in turn prevents doublespending.
Flash has two variants: for high congestion when multiple blocks that contain multiple payments are issued concurrently; and for low congestion when payments are infrequent.

Flash: An Asynchronous Payment System with Good-Case Linear Communication Complexity, pdf.

This is joint work with Ehud Shapiro and Oded Naor.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s