Religion is a special case of the enforceable side-contract in which God is doing the enforcing. God doesn't have to exist for this to work; as long as at least one party believes He does, the threat of punishment will be credible. The advantage of being able to easily make enforceable side contracts even in the absence of social authority may be one reason religion became so popular, and if humans do turn out to have a genetic tendency toward belief, the side contracts might have provided part of the survival advantage that spread the gene.

By the way, the book, "The Evolution of God" makes a very strong case for religious beliefs as the original enabler of non-zero-sum games between non-kin, by showing the parallels in the development of religion and government as humans progress from tribes to chiefdoms to kingdoms and empires, and the ways in which religions were modified "just-in-time" to serve both intra-group co-operation and intergroup alliances. Fascinating stuff.