By the way, there is no excuse for the cost to be quadratic. That is one of the many crocks in the BitcoinCore implementation, that will take more crocks to work around. Like the Segregated Witnesses proposal, malleability and its partial patches, blockchain voting to increase the limit, etc..
Jorge, do you have a link to how this issue arises and, ideally, how it might be solved?
This is what I found; maybe you can follow those leads.