Compressed Multiaddr Combinations

When handling many multiaddrs that have common prefixes, or sections, it has been discussed that it may be useful to have a format for expressing these as combinations, or DAGs. This is to allow much more compressed transmissions, and even in-memory representations.

For example, the list:

/ip4/1.2.3.4/tcp/4001/ipfs/Qmf8SVETTnpzzCJyurQa2ekxFwKnUNNYycLHsNfVjiq19B
/ip4/1.2.3.4/udp/4002/utp/ipfs/Qmf8SVETTnpzzCJyurQa2ekxFwKnUNNYycLHsNfVjiq19B
/ip4/127.0.01/tcp/4001/ipfs/Qmf8SVETTnpzzCJyurQa2ekxFwKnUNNYycLHsNfVjiq19B
/ip4/127.0.0.1/udp/4002/utp/ipfs/Qmf8SVETTnpzzCJyurQa2ekxFwKnUNNYycLHsNfVjiq19B
/ip6/::1/tcp/4001/ipfs/Qmf8SVETTnpzzCJyurQa2ekxFwKnUNNYycLHsNfVjiq19B
/ip6/::1/udp/4002/utp/ipfs/Qmf8SVETTnpzzCJyurQa2ekxFwKnUNNYycLHsNfVjiq19B

OR-Lists

It is an expansion of the combinations

/ip4/1.2.3.4 OR /ip4/127.0.0.1 OR /ip6/::1
/tcp/4001 OR /udp/4002/udt
/ipfs/Qmf8SVETTnpzzCJyurQa2ekxFwKnUNNYycLHsNfVjiq19B

This notation could be much more compressed way to represent these than the full list.

DAGs

Another such representation could treat it like a dag:

n0 := /ip4/1.2.3.4
n1 := /ip4/127.0.0.1
n2 := /ip6/::1
n3 := /tcp/4001
n4 := /udp/4002/udt
n5 := /ipfs/Qmf8SVETTnpzzCJyurQa2ekxFwKnUNNYycLHsNfVjiq19B
n6 := n0 OR n1 OR n2
n7 := n3 OR n4
n8 := n6 AND n7 AND n5

This one could also be very compressed, and allow representing much more versatile lists.

Some open problems with this:

• Transforming lists of addrs into these reprs.
• Dealing with changes efficiently (one node added or dropped) -- this may turn out pretty easy
• Use it for the wire format transmission of a big multiaddr set
• Use it for the in-memory representation of a big multiaddr set! (this could be very cool)
• Making all this super efficient.

• I'm not convinced how useful vs complex this would be.
• Opening to gather thoughts.
• Wonder if there's already some generic way of doing this over any set of strings that we can just use.

Start by reviewing the existing multiaddr representation and wire-format handling, then compare the proposed OR-lists and DAGs against the open problems listed. Done would require an agreed scope and an implemented representation with transformation, change handling, and transmission or in-memory use addressed.