As far as I'm aware stone doesn't erode in space, so we could always just laser in bumps on a stone and read it like a CD. The primary concern then becomes avoiding getting hit by micro debris.