Flash: An Asynchronous Payment System with Good-Case Linear Communication Complexity
share
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(n^2) 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.
READ FULL TEXT
