Comment by semiel

Yep, and we pretty much know what the solution will look like: zero-knowledge proofs, such as the ones used by ZCash.