Cybercrime in the past decade has experienced an all-time high due to the inclusion of so-called smart devices in our daily lives. These tiny devices with brittle security features are often dubbed as the Internet of Things (IoT). Their inclusion is not only limited to our daily lives but also in different fields, for example, healthcare, smart-industries, aviation, and smart-cities. Although IoT devices make our lives easy and perform our jobs in a smart way, their fragile security mechanisms pose a severe challenge regarding safety and privacy of its users. Attacks like Stuxnet, and Mirai-botnet are the key examples of the damages that can be caused by maliciously controlling these devices. One effective tool to identify a malicious entity at a network device is to perform Remote Attestation (RA). However, performing RA over a large, heterogeneous IoT network is difficult tasks due to resource constrain nature of these networks. To this end, we propose a novel scheme called SARP, which is an attestation-assisted secure and scalable routing protocol for IoT networks. SARP performs attestation in large scale IoT networks by using Routing Protocol for Low Power and Lossy Networks (RPL) framework and exploiting the inbuilt features of RPL. In particular, SARP uses attestation technique that not only secures the network from internal attacks, but it also provides security to RPLs data communication process, which helps to improve the overall network performance. Moreover, SARP supports network mobility, device heterogeneity, and network scalability, while it does not sacrifice the key requirements of IoT networks such as low energy and memory consumption, and low network overhead. The simulation results obtained in different IoT scenarios in presence of various types of attacks show the effectiveness of SARP, concerning energy consumption, packet delivery ratio, network overhead, data integrity, and communication security.