Compressed Multiaddr Combinations

[jbenet]

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.

[ghost]

Found this digging through IRC: these multiaddr combinations could be used as a language for expressing e.g. dial restrictions.

<lgierth> jbenet-on-plane: coming up with compressed multiaddr combinations as a language for expressing dialing restrictions? e.g. for tor
<jbenet-on-plane> lgierth: oh wow yeah good idea
<jbenet-on-plane> lgierth: hm seems to be a pretty useful primitive
<jbenet-on-plane> MultiaddrSet or something?

[jbenet]

Yeah i still think this would be super useful.

[dignifiedquire]

I think this would be great in terms of reducing the overhead in the various scenarios.