I once proposed this SlateStore Protocol and @tromp found a cool way to pay for storage using tx excess.