Has PoS really been proven secure under comparable assumptions as Bitcoin? I am just reading this paper which claims to be a formal proof that Cardano's latest Ouroboros PoS protocol ("Genesis") gives similar security guarantees than Bitcoin's PoW protocol. Unfortunately, it is 64 pages long and presupposes a lot of earlier work that I need to get comfortable with, as well, so even though I am relatively confident in my understanding of these things, a thorough evaluation will take me quite some time. 

So I was wondering if anybody (say Andrew Poelstra, Pieter Wuille?) had already checked this out and could give their opinion. Because on one hand this is a very bold claim that would invalidate the folklore view on this topic (PoS has fundamental security issues that can't be overcome), and on the other hand the authors seem quite legit and serious in their approach.

I do realize that even if it were true, this doesn't mean that PoS is useful for bootstrapping a system like Cardano. But couldn't it be an alternative for Bitcoin, say, after another one or two halvings?
The Ouroboros line of work proves security comparable to Bitcoin's security. The proofs of security in Ouroboros are similar in style to the Backbone proofs of security, which show that Bitcoin is secure. To my knowledge, there are no alternative proofs of security for Bitcoin which are formal - these are the best results we know of that illustrate that Bitcoin is secure, beyond informal hand-wavy non-mathematical arguments (such as "but you can't find a security bug, so it must be secure").

In both of these settings, there are certain assumptions made, which are as follows:

For proof-of-work, in the first version of Backbone from 2014, Bitcoin was shown secure in a synchronous model. This model splits time into discrete portions ("rounds" in Backbone, "slots" in Ouroboros) during which the players are allowed to mine and then broadcast any blocks found throughout a round. Messages sent during a round are anonymous (i.e., unauthenticated) and can be reordered by the adversary (hence the need for a consensus protocol). The adversary is also "rushing" in that it can use its own mining power after it has observed what the honest parties have done during that same round and prior to allowing messages to travel on the network. The assumption is that no messages are lost. This is a necessary assumption to prove Bitcoin secure - if the network is split, then you can't hope for your 50/50 honest majority to continue creating the longest chain.

The synchronicity requirements were relaxed in the current version of backbone revised in 2017 in which the model is semi-synchronous. The first version of Backbone also showed that Bitcoin is secure if the difficulty is kept constant. A follow-up work on Backbone from 2016 showed that it remains secure in a variable difficulty setting. These proofs hinge on an honest majority assumption which is made precise in the papers. More precisely, it is required that the adversary has mining power which is lower than the honest mining power by a fixed constant which makes up for non-uniquely successful rounds (i.e., rounds during which multiple honest parties find a block and hence will cause a short accidental fork on the blockchain).

The assumptions in the proof-of-stake setting of Ouroboros are similar network-wise to Backbone. The model is mostly borrowed from Canetti's Universal Composability framework, in the sense that there exists an environment which can influence the execution. Proofs in the "environment-including" model are powerful in that they can speak of any execution in which the adversary is able to tell people exactly what to do beyond the requirement that the honest parties run the honest protocol. For example, the adversary can corrupt players of their choice.

In Ouroboros, the assumption which is dual to Backbone's "honest mining majority" is "honest stake majority", i.e., that at any moment in time, the majority of stake belongs to the honest parties. This is a strong assumption which may or may not hold true, so it depends on what you're willing to accept. Another assumption made in Ouroboros is that stake shifting is bounded. This seems like a reasonable assumption: It means that all money cannot change hands instantaneously. However, the construction hinges on this bound to specify the security parameters such as epoch length. In the practical system, these parameters take concrete values which allow for specific bounds to be attained.

Ouroboros Praos achieves better security guarantees than Ouroboros: It allows the adversary to corrupt any honest party instantaneously, whenever she feels she needs to. This is a strong adversary (hence the system is more secure), and is also a similar assumption to Backbone. For proof-of-stake, it's an important achievement, as the adversary could retroactively corrupt parties who were successful in staking a block so that she can create multiple competing blocks. To my knowledge, practically deployed proof-of-stake chains such as Blackcoin do not enjoy such guarantees (and really cannot make any claims, since they do not have security proofs).

Ouroboros Genesis makes the above results stronger in that the parties are dynamic (and can, e.g., go offline) and the security is proven in a stronger model.

All of these works (the proofs for both Bitcoin and Ouroboros) also use the Random Oracle assumption, which some cryptographers dislike.

All of these approaches are comparable to other lines of work such as Snow white and ALGORAND. In my opinion, Ouroboros achieves better guarantees, has good design decisions, has formal security proofs, and functions in a model that is quite similar to proof-of-work-based systems (especially Praos). It would take an extensive analysis to compare them all side-by-side.

In the end, whether you are happy with the security assumptions and threat model in these works is up to your requirements. Overall, these works achieve some good guarantees, but some results are left to be desired. For example, honest majority may hold most of the time, not all of the time, but there has been no exploration of whether security is guaranteed in these settings (neither in Bitcoin nor in Ouroboros). I do suspect that Bitcoin is more resilient to extreme conditions, but no such guarantees have been proven.

Generally, one thing to note is that these limitations/assumptions also hold for Bitcoin: The best formal proofs we have for Bitcoin work in a limited model which is close, but not exactly the same, as the real construction. To conclude, Backbone is the best analysis we have for Bitcoin, and it makes an analysis which is comparable to Ouroboros. Hence, its security guarantees do match the security guarantees we have for Bitcoin, if you equate staking honest majority with mining honest majority, at least as long as provability is required.

If you'd like to understand these papers yourself, and judge for yourself whether they achieve your desired outcomes, I recommend that you read the GKL Backbone paper first. You can read the first portion where it talks about Common Prefix, Chain Quality and Chain Growth, as well as Liveness and Persistence. Then I recommend that you read Ouroboros, maybe followed up by Ouroboros Praos. These should give you a good idea of what this line of work is about. You're right that understanding Ouroboros Genesis has a lot of prerequisites. You can get a good understanding of the results regarding the security of proof-of-stake without reading that particular paper though.

Disclaimer: I am Aggelos' PhD student (Aggelos wrote Backbone, Variable Backbone, Ouroboros, Ouroboros Praos, Ouroboros Genesis - I did not contribute to these papers); my current scientific work is used in Cardano, which is an implementation of Ouroboros. My view may be biased.