Fungibility is a good question for inductive reasoning.  After all, what is
a claim without some rigger?

There exists some set of wallets 'w' which contain a balance of satoshi too
small to recover because it doesn't meet the minimum transaction fee
required to confirm the transaction.  These wallets are un-spendable by
their very nature - and quantifying un-spendable wallets is one way to
measure the fungibility of Bitcoin.  The number of un-spendable wallets can
be quantified as follows:

   Let 'p' equal the current price/per-bit for a transaction
   Let 'n' equal the number of bits in the transaction
   Let '[a]' be the set of all wallets with a balance
   Let '[w]' be the set of un-spendable wallets
   [w0] = [a] > b*n

Now, let's introduce a savings measure 'k' which is a constant flat savings
per transaction.

   [w1] = [a] > b*(n - k0)

As the savings 'k' increase, the set of 'w' also increases in size.
   len([w0]) < len([w1]) ... < len([wk])

In this case 'k0' could be the savings from a P2PKH transaction to a 233
byte SegWit transaction, and 'k1' could be 148 byte SegWit+PubRef
transaction, and the same model can be used for some future transaction
type that is even smaller.   As the savings 'k' approaches infinity the set
of un-spendable wallets approaches zero.

If a user is privacy-aware, and chooses to use single-use p2sh for all
transactions, then these users can still gain from PubRef because
block-weight should be decreased for everyone. There are cases where a user
or merchant might want to reuse their p2sh hash - and PubRef can provide
savings.  Additionally, the resulting p2sh script could be a multi-sig
transaction which could still benefit from PubRef compression.  PubRef
improves fungibility of Bitcoin in two different ways - both reduced cost
of transaction and increasing the max number of transactions that are able
to be confirmed by a block. Which is pretty hot - QED.

On Fri, Jul 19, 2019 at 3:48 PM Yuval Kogman <nothingmuch@woobling.org>
wrote:

> Hi,
>
> On Fri, 19 Jul 2019 at 17:49, Mike Brooks <m@ib.tc> wrote:
>
>> Users will adopt whatever the client accepts - this feature would be
>> transparent.
>>
>
> My skepticism was based in an assumption on my part that most such data is
> produced by actors with a track record of neglecting transaction
> efficiency. I'd be happy to be proven wrong, but considering say usage
> rates of native witness outputs, or the fraction of transactions with more
> than 2 outputs so far I see little evidence in support of widespread
> adoption of cost saving measures. Assuming this is intended as a new script
> version, all fully validating nodes need to commit to keeping all data
> indefinitely before they can enforce the rules that make transactions
> benefiting from this opcode safe to broadcast.
>
> That said, if successful, the main concern is still that of address reuse
> - currently there is no incentive in the protocol to do that, and with
> BIP32 wallets fewer reasons to do it as well, but this proposal introduces
> such an incentive for users which would otherwise generate new addresses
> (disregarding the ones that already reuse addresses anyway), and this is
> problematic for privacy and fungibility.
>
> Since address reuse has privacy concerns, I think it's important to draw a
> distinction between clients accepting and producing such transactions, if
> the latter were done transparently that would be very concerning IMO, and
> even the former would not be transparent for users who run currently
> pruning nodes.
>
> I'm not sure how an O(1) time complexity leads to DoS, that seems like a
>> very creative jump.
>>
>
> For what it's worth, that was in reference to hypothetical deduplication
> only at the p2p layer, similar to compact blocks, but on further reflection
> I'd like to retract that, as since both scenarios which I had in mind seem
> easily mitigated.
>
>   Based on this response, it makes me want to calculate the savings, what
>> if it was a staggering reduction in the tree size?
>>
>
> Assuming past address reuse rates are predictive this only places an upper
> bound on the potential size savings, so personally I would not find that
> very compelling. Even if the realized size savings would be substantial,
> I'm not convinced the benefits outweigh the downsides (increased validation
> costs, monotonically growing unprunable data, and direct incentive for
> address reuse), especially when compared to other methods/proposals that
> can reduce on chain footprint generally improve privacy while reducing
> validation costs for others (e.g. batching, lightning, MAST for
> sufficiently large scripts, Schnorr signatures (musig, adaptor signatures),
> {tap,graft}root, ).
>
> Regards,
> Yuval
>