Data security has become a major subject in the cloud computing. Data integrity verification allows clients know whether the data storing in the cloud is secure or not. And data recovery also provides a reliable guarantee for the clients. However, the pre-processing for the files such as the works of hash, blocks' signature, and redundancy generation and data recovery causes a great challenge to the clients' performance. To solve this problem, this paper proposes a data integrity verification and fault-tolerant scheme based on the third party (TP), and it supports public audit ability. Finally, the analysis shows that the scheme is efficient and secure.