If a 2x savings were possible it would be a worrying sign, because it would mean that miners would have an incentive to try to run this algorithm themselves. If they can reduce the witness by this much it means they can increase the speed at which their blocks propagate, winning some extra revenue from reduced uncle rates. Because the algorithm would be so complicated, this gives larger miners (or mining pools) an additional advantage over smaller mining pools.
Here are some more radical proposals:
(12) Larger and more infrequent blocks (a 30 second block time) would provide more opportunity for witness aggregation, meaning the same number of transactions would lead to smaller witnesses.
(13) Adopting GHOST or a similar design (don’t believe the abstract, Ethereum does not implement GHOST) would not make the witness size smaller but it would alleviate much of the impact of large witness sizes. Blocks which take a while to propagate would not pose a security risk.
(14) If transactions included their own witnesses (like how ETH2 is expected to work) then nodes would already have most of the block witness in their mempool. A block propagation protocol which took advantage of that could send much less witness data during block propagation.
(15) An improved block propagation protocol (much like Bitcoin’s FIBRE) might cause blocks to propagate much faster. If blocks and witnesses propagated faster then increased witness sizes would again not be as much of a concern.
(16) If witnesses did not need to propagate alongside blocks then witness size isn’t a large concern.
(17) A better understanding of how blocks propagate might win us some witness size. Currently, miners which accept a block must first process it before attempting to build new blocks on top of it. Witnesses reduce the amount of time it takes to process blocks. However, witnesses mean that blocks take longer to get to the miners. If the first effect is larger than the second then larger witnesses would be acceptable.
(18) I’m not sure what you meant by (9), but we could encourage Dapps to lean on CALLDATA by giving it a decreased gas cost. CALLDATA is propagated along with transactions so we can expect it to already be in the mempool of receiving nodes, a witness propagation algorithm would took advantage of this would be able to send less data. If we paired this with increased costs for calls such as SLOAD we could heavily incentivize dapps to start leaning on CALLDATA. (this is a variant of 14 which we can move to without forcing dapp developers to change anything)
(19) EXTCODESIZE requires having access to the entire bytecode. The naive answer would be to make it very expensive, but a more reasonable answer would be to store the code size in the account data. This requires re-writing the entire account trie.