Abstract In recent years, network coding has received extensive attention and been applied to various computer network systems, since it has been mathematically proven to enhance the network robustness and maximize the network throughput. However, it is well-known that it is extremely vulnerable under pollution attacks. Certificatelss network coding scheme (CLNS) is a recently-proposed mechanism to defend against pollution attacks for network coding, which avoids the tedious management of certificates and the key-escrow attack. Until now, only a few constructions were presented and more ones should be given in order to enrich this field. In this paper, for the first time, we study the general construction of CLNS from certificateless public auditing protocol (CL-PAP), although the two areas seem to be quite different in their nature and are studied independently. Since there are many candidates of CL-PAPs, we naturally obtain abundant constructions of CLNSs according to our systematic way. In addition, in order to show the power of our general construction, we also present a concrete implementation given a specific CL-PAP. The performance analysis and experimental result show that the implemented CLNS is competitive in the existing network coding schemes.