Punishment offers a powerful mechanism for the maintenance of cooperation in human and animal societies, but the maintenance of costly punishment itself remains problematic. Game theory has shown that corruption, where punishers can defect without being punished themselves, may sustain cooperation. However, in many human societies and some insect ones, high levels of cooperation coexist with low levels of corruption, and such societies show greater wellbeing than societies with high corruption. Here we show that small payments from cooperators to punishers can destabilize corrupt societies and lead to the spread of punishment without corruption (righteousness). Righteousness can prevail even in the face of persistent power inequalities. The resultant righteous societies are highly stable and have higher wellbeing than corrupt ones. This result may help to explain the persistence of costly punishing behavior, and indicates that corruption is a sub-optimal tool for maintaining cooperation in human societies.