We describe and expand upon the scalable randomized benchmarking protocol proposed in Phys. Rev. Lett. 106, 180504 (2011) which provides a method for benchmarking quantum gates and estimating the gate-dependence of the noise. The protocol allows the noise to have weak time and gate-dependence, and we provide a sufficient condition for the applicability of the protocol in terms of the average variation of the noise. We discuss how state preparation and measurement errors are taken into account and provide a complete proof of the scalability of the protocol. We establish a connection in special cases between the error rate provided by this protocol and the error strength measured using the diamond norm distance.