One possible solution is to only be able to contact someone if you have received an invitation code from them out of band. E.g. "scan this QR code to add me on signal". Such an invitation code should default to single-use but users should be allowed to generate standing invitations so that businesses and the like can print and post one in their store or whatever. Start getting spam from one of your standing invitations? Just revoke it and make a new one. Presumably the Signal folks can come up with more alternative solutions than the half baked one I came up with after thinking about it for a minute, they're clever cookies.