  Research on deductive verification of probabilistic programs has considered
expectation-based logics, where pre- and post-conditions are real-valued
functions on states, and assertion-based logics, where pre- and post-conditions
are boolean predicates on state distributions. Both approaches have developed
over nearly four decades, but they have different standings today.
Expectation-based systems have managed to formalize many sophisticated case
studies, while assertion-based systems today have more limited expressivity and
have targeted simpler examples.
  We present Ellora, a sound and relatively complete assertion-based program
logic, and demonstrate its expressivity by verifying several classical examples
of randomized algorithms using an implementation in the EasyCrypt proof
assistant. Ellora features new proof rules for loops and adversarial code, and
supports richer assertions than existing program logics. We also show that
Ellora allows convenient reasoning about complex probabilistic concepts by
developing a new program logic for probabilistic independence and distribution
law, and then smoothly embedding it into Ellora. Our work demonstrates that the
assertion-based approach is not fundamentally limited and suggests that some
notions are potentially easier to reason about in assertion-based systems.
