Electroweak Baryogenesis (EWBG) is a compelling scenario for explaining the matter-antimatter asymmetry in the universe. It is in principal testable, but doing so exhaustively seems difficult in practice due to the large amount of model building freedom in realizing this mechanism. I will outline our first steps in investigating a possible "no-loose" theorem for testing EWBG in future e+e- or hadron colliders. This involves focusing on a factorized picture of EWBG which separates the new physics requirements of strong phase transition and CP violation. We then construct a "nightmare scenario" that generates a strong phase transition, but is very difficult to test experimentally. We show that a 100 TeV hadron collider is both necessary and possibly sufficient for testing the parameter space of the nightmare scenario that is consistent with EWBG. I will also give a preview of some work in progress, in which we try to construct a consistent effective field theory framework for an important class of electroweak phase transitions.