What does the term "asymptotic security" mean? The Stellar cryptocurrency whitepaper lists "asymptotic security" as a key advantage over other consensus protocols (for example, proof-of-work in Bitcoin). What do they mean by this? As I understood it, it refers to guaranteed safety, as in: results valid and identical at all nodes. However, this can't be guaranteed for a decentralized system, as any node can join the system and refuse to accept the state presented by other nodes. So they must mean something else…

What does the term "asymptotic security" mean?

Here is an excerpt from the whitepaper where they vaguely characterize asymptotic security:


  Safety rests on digital signatures and hash families whose parameters can realistically be tuned to protect against adversaries with unimaginably vast computing power.
One of the key ideas of cryptography is to provide security by means of operations that are (relatively) affordable to honest parties but prohibitively costly to adversaries.  So one thing you see over and over in cryptographic literature is efforts to quantify the cost to adversaries to break some proposed cryptographic scheme.

Asymptotic security is one paradigm for so doing.  In such an analysis, one states the adversary's cost as a function of a designated security parameter (e.g., key length).  The scheme is then said to be secure if an only if the adversary's advantage is a negligible function of the security parameter.  Very informally, an asymptotically secure scheme is one that's been conditionally proven to be harder than any polynomial for the attacker to break.

What the author seems to be highlighting is that alternatives to their proposal don't enjoy this "harder than polynomial" property (pp. 2-3):


  Finally, in contrast to traditional cryptographic protocols, proof of work offers no asymptotic security. Given non-rational attackers—or ones with extrinsic incentives to sabotage consensus—small computational advantages can invalidate the security assumption, allowing history to be re-written in so-called “51% attacks.”


This seems to mean that the computational effort to an adversary who wishes to defeat the proof-of-work system is a linear function ("51%") of the total amount of computing power in the network.  That amount of computing power definitely exists, so it is theoretically possible for some combination of actors to collude and assemble that much.  Whereas an asymptotically secure scheme—like cryptographic ones are—can in principle be tuned so that the universe might not be big enough to crack them.