Necroposting here but since there’s already some recent activity, it’s worth noting this problem was posed at an SBC workshop and a group (including myself) realised we can in fact solve the underlying problem instead by creating a signature aggregation scheme which can handle unions of joint sets (not just disjoint set unions, as is assumed by the BLS aggregation scheme in this post). In particular, to create such a scheme we show a simple modification of the original BLS scheme by attaching a SNARK (bulletproof or other succinct proof in practice) that keeps track of the multiplicity of each aggregated signature. The use of this modified BLS scheme is described in the new Horn proposal and in much more detail in this HackMD note.
4 Likes