We describe and expand upon the scalable randomized benchmarking protocol proposed in Phys. Rev. Lett.PRLTAO0031-900710.1103/PhysRevLett.106.180504 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. © 2012 American Physical Society.