The miniaturization of electronic and mechanical components has allowed for an unprecedented downscaling of spacecraft size and mass. Today, spacecraft with a mass between 1 to 10 grams, AttoSats, have been developed and operated in space. Due to their small size, they introduce a new paradigm in spacecraft design, relying on agile development, rapid iterations, and massive redundancy. However, no systematic survey of the potential advantages and unique mission concepts based on AttoSats exists. This paper explores the potential of AttoSats for future space missions. First, we present the state of the art of AttoSats. Next, we identify unique AttoSat characteristics and map them to future mission capabilities. Finally, we go beyond AttoSats and explore how smart dust and nano-scale spacecraft could allow for even smaller spacecraft in the milligram range: zepto- and yocto spacecraft.