A decentralized storage network (DSN) collects idle storage resources from Internet nodes for low-cost rental to users, and its scale has grown exponentially. In a DSN, most users rely on a centralized third-party service provider (SP) to process userside data and interact with decentralized storage nodes (SNs), making users suffer from a single point of failure. Additionally, since both SP and SNs may offer malicious services, enabling fault tolerance, data confidentiality, and availability guarantee with public verifiability is crucial in the presence of such threats. In this paper, we propose TolerStore, a completely decentralized service framework for DSNs with decentralized SPs and SNs, which can tolerate Byzantine SPs and malicious SNs. To the best of our knowledge, TolerStore is the first to develop a blockchain with multiple SPs for privacy-aware data processing in DSNs, which is formally proven to ensure Byzantine fault tolerance, data confidentiality, public verification, and data availability. Furthermore, we propose an optimized Byzantine Fault-Tolerant consensus with an adaptive leader rotation, incorporating homomorphic fingerprints to verify privacy-aware data processing with enhanced performance. We implement a TolerStore prototype over Hyperledger Fabric, and extensive experiments show that it tolerates [$\frac{N-1}{3}$] Byzantine SPs and 50% malicious SNs with up to 99.99% data availability.