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.

• Maybe this is nitpicking, and you found the expression in the quote, but: safety and security do not have the same meaning and no security expert should ever use one tearm while meaning the other. Safety protects from randomness (hit by lightning, power spikes, etc.), or from the aftereffects of events (accidents). Security protects from malicious intend of a driven, adaptable and malicious adversary, who knows exactly what you're doing, how you're doing it and maybe knows more about cryptography than yourself. – tylo Apr 28 '17 at 18:44

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.

When he says:

in contrast to traditional cryptographic protocols, proof of work offers no asymptotic security.

I think he means that it is vulnerable to > 50% hash power attacks.

With "asymptotic" I think he means a miner growing hash power and reaching the limit, in this case 51%.

• Funny that this answer comes shortly after Antbleed's popularity hits. Something about a 51% attack seems much more plausible when there seems to be a way for a major party to DoS competitors. – Nat Apr 29 '17 at 11:35