The area of trustworthy charging in self-organized environments has been developed quite recently. This paper introduces a new secure charging-protocol, the polynomial-assisted charging protocol, for these environments. The protocol relies on polynomial composition for speeding the identification process in small groups. This protocol is able to provide strict guarantees of cooperative behavior in traffic forwarding, with minimal network overhead. Protocol performance is evaluated in multiple ad-hoc environments and results are compared with previously proposed work. The performance results show the merits of this protocol in multiple types of environments.