We were at al-Mirbad when a man with disheveled hair came along, holding a piece of red leather in his hand.We said to him, "You look like one of the desert people."He replied, "Indeed I am."We said, "Hand us that piece of leather you have."He gave it to us, and we read it. It contained the following, "From Muhammad the Messenger of Allah to the tribe of Zuhayr bin Uqaysh. If you bear witness that there is no god but Allah and that Muhammad is the Messenger of Allah, establish the prayer, pay the zakat, hand over a fifth of the spoils of war along with the Prophet's ﷺ chosen share, then you are granted security under the protection of Allah and His Messenger."We asked him, "Who wrote this letter for you?"He answered, "The Messenger of Allah ﷺ."
حدثنا مسلم بن إبراهيم حدثنا قرة قال سمعت
كنا بالمربد فجاء رجل أشعث الرأس بيده قطعة أديم أحمر فقلنا كأنك من أهل البادية فقال أجل قلنا ناولنا هذه القطعة الأديم التي في يدك فناولناها فقرأناها فإذا فيها من محمد رسول الله إلى بني زهير بن أقيش إنكم إن شهدتم أن لا إله إلا الله وأن محمدا رسول الله وأقمتم الصلاة وآتيتم الزكاة وأديتم الخمس من المغنم وسهم النبي ﷺ الصفي أنتم آمنون بأمان الله ورسوله فقلنا من كتب لك هذا الكتاب قال رسول الله ﷺ
[Its isnad is sahih] Nasai narrated it in the section on Fay, chapter 1, no. 4151, from the hadith of Yazid bin Abdullah bin Shikhir, through this route, and Ibn Jarud graded it sahih, no. 1099, as did Ibn Hibban, no. 949.The companion is Numar bin Tawlab, the poet.