Musannaf Ibn Abi Shayba 28:419

Waki' narrated to us, he said: Muhammad bin Qays narrated to us, from 'Amir, who said: The people of As-Sawad did not have a covenant. But when they (the Muslims) accepted the jizya from them, they became entitled to a covenant.