Named Data Networking (NDN) improves the transfer efficiency by caching the contents in routers. To prevent polluted content from being spread in NDN, NDN routers should verify every content that is published in NDN. Since the verification scheme in NDN applies the asymmetric encryption algorithm to sign the content, the verification speed is too slow to satisfy the high speed requirement. This paper proposes a Staining-based verification scheme to improve the verification speed by reducing the computation complexity of the content verification. Staining-based verification scheme stains the content that is sent to the network for the first time; then when the stained content is sent to the network again, the router can utilize the staining information to verify this content. By replacing the asymmetric encryption algorithm with symmetric encryption algorithm, Staining-based scheme can improve the verification speed effectively.