Context. The TRAPPIST-1 system hosts seven Earth-sized, temperate exoplanets orbiting an ultra-cool dwarf star. As such, it represents a remarkable setting to study the formation and evolution of terrestrial planets that formed in the same protoplanetary disk. While the sizes of the TRAPPIST-1 planets are all known to better than 5% precision, their densities have significant uncertainties (between 28% and 95%) because of poor constraints on the planets masses. Aims.The goal of this paper is to improve our knowledge of the TRAPPIST-1 planetary masses and densities using transit-timing variations (TTV). The complexity of the TTV inversion problem is known to be particularly acute in multi-planetary systems (convergence issues, degeneracies and size of the parameter space), especially for resonant chain systems such as TRAPPIST-1. Methods. To overcome these challenges, we have used a novel method that employs a genetic algorithm coupled to a full N-body integrator that we applied to a set of 284 individual transit timings. This approach enables us to efficiently explore the parameter space and to derive reliable masses and densities from TTVs for all seven planets. Results. Our new masses result in a five- to eight-fold improvement on the planetary density uncertainties, with precisions ranging from 5% to 12%. These updated values provide new insights into the bulk structure of the TRAPPIST-1 planets. We find that TRAPPIST-1,c and e likely have largely rocky interiors, while planets b, d, f, g, and h require envelopes of volatiles in the form of thick atmospheres, oceans, or ice, in most cases with water mass fractions less than 5%.