In his autobiography, The Life of Flavius Josephus, Josephus provides a concrete example of the criminality of the state. St. Augustine's comment in The City of God regarding states without justice being great robber bands might have been prompted by reading Josephus.
Josephus describes an incident where he was trying to disarm a band of robbers that were too powerful to be disarmed, so he devised an expedient that sounds quite a bit like a government or protection racket:
"... and when I had sent for the most hardy among the robbers, I saw that it was not in my power to take their arms from them; but I persuaded the multitude to allow them money as pay, and told them it was better for them to give them a little willingly rather than to [be forced to] overlook them when they plundered their goods from them. And when I had obliged them to take an oath not to come into that country, unless they were invited to come, or else when they had not their pay given them, I dismissed them, and charged them neither to make an expedition against the Romans, nor against their neighbors that lay round about them; for my first care was to keep Galilee in peace....Accordingly, I made them my friends and companions as I journeyed, and set them to judge causes; and with their approbation it was that I gave my sentences, while I endeavored not to mistake what justice required, and to keep my hands clear of all bribery in those determinations."
This sounds a lot like an early example of "If you can't beat 'em, join 'em" or at least make it appear that you have forced them to join you. It doesn't look like he had many or any options, but it also illustrates how the difference between extortion and government is in the name.
It isn't clear why the oath of a robber would be of much value, but oaths are used in government all the time without any effect. Politicians swear an oath to uphold the constitution when most of them have probably never read it and have no intention of allowing words to interfere with their reelection. Perjury is the American way among public officials. The group called Oath Keepers is viewed with alarm among many - the Southern Poverty Law Center, for example - because they actually place a higher value on their oaths than orders from their superiors. The conclusion to be drawn here would be that integrity is an obstacle to good government.
Albert Jay Nock believed that when society was ruled by a strictly negative entity - one that prevented injustice - you had "government", but when the entity engaged in wealth transfer and coercion, you had the "State." The history of the world seems to be The State if Nock's definition is accurate.