The catalytic nature of particulate matter is often advocated to explain its ability to generate reactive oxygen species, but quantitative data are lacking. We have performed molecular characterization of three different carbonaceous nanoparticles (NP) by 1. identifying and quantifying their surface functional groups based on probe gas-particle titration; 2. studying the kinetics of dissolved oxygen consumption in the presence of suspended NP's and dithiothreitol (DTT). We show that these NP's can reversibly change their oxidation state between oxidized and reduced functional groups present on the NP surface. By comparing the amount of O2 consumed and the number of strongly reducing sites on the NP, its average turnover ranged from 35 to 600 depending on the type of NP. The observed quadratic rate law for O2 disappearance points to a Langmuir-Hinshelwood surface-based reaction mechanism possibly involving semiquinone radical. In the proposed model, the strongly reducing surface site is assumed to be a polycyclic aromatic hydroquinone whose oxidation to the corresponding conjugated quinone is rate-limiting in the catalytic chain reaction. The presence and strength of the reducing surface functional groups are important for explaining the catalytic activity of NP in the presence of oxygen and a reducing agent like DTT.