The integrity of cloud-based convolutional neural network (CNN) prediction services can be jeopardized by a malicious cloud server. Although zero-knowledge proof approaches can be used to verify integrity, they are difficult to use for larger CNN models like LeNet-5 and VGG16, due to the large cost (in terms of time and storage) of generating a proof. This paper proposes ValidCNN, which can efficiently generate integrity proofs based zk-SNARK. At the heart of ValidCNN, it is a novel usage of Freivald's concepts for circuit construction, and a more efficient way for verifying matrix multiplication. Our experimental results demonstrate that VaildCNN significantly outperforms the state-of-the-art approaches that are based on zk-SNARK. For example, compared with ZEN, VaildCNN achieves a 12-fold improvement in time and a 31-fold improvement in storage. Compared with vCNN, VaildCNN achieves a 195-fold and 279-fold improvement in time and storage respectively.