  We address the problem of online payments, where users can transfer funds
among themselves. We introduce Astro, a system solving this problem efficiently
in a decentralized, deterministic, and completely asynchronous manner. Astro
builds on the insight that consensus is unnecessary to prevent double-spending.
Instead of consensus, Astro relies on a weaker primitive---Byzantine reliable
broadcast---enabling a simpler and more efficient implementation than
consensus-based payment systems.
  In terms of efficiency, Astro executes a payment by merely broadcasting a
message. The distinguishing feature of Astro is that it can maintain
performance robustly, i.e., remain unaffected by a fraction of replicas being
compromised or slowed down by an adversary. Our experiments on a public cloud
network show that Astro can achieve near-linear scalability in a sharded setup,
going from $10K$ payments/sec (2 shards) to $20K$ payments/sec (4 shards). In a
nutshell, Astro can match VISA-level average payment throughput, and achieves a
$5\times$ improvement over a state-of-the-art consensus-based solution, while
exhibiting sub-second $95^{th}$ percentile latency.
