Optimize reanchor

[gavofyork]

Concerning MultiLocation::reanchor:

So I realized that what we're essentially doing here is to first find the common ancestor between self and target, then append the necessary junctions that will allow us to reach self from the common ancestor, and then we'd simplify the result, given target.

I suspect what we can do here is to write the common ancestor from the perspective of target, that way we don't have to simplify at the end of the algorithm.

Originally posted by @KiChjang in paritytech/polkadot#4470 (comment)

[shawntabrizi]

We will have a hiring candidate working on this one.

[emmaling27]

We will have a hiring candidate working on this one.

Hey! Just started looking at this. I was messing with different inputs in the tests to make sure I understand the behavior of the current implementation of reanchor correctly, and the following gave me an unexpected result

let mut id: MultiLocation = (Parent, Parachain(2000), Parachain(4000), GeneralIndex(42)).into();
let ancestry = Parachain(2000).into();
let target = (Parent, Parachain(1000), Parachain(3000)).into();
let expected = (Parent, Parent, Parachain(4000), GeneralIndex(42)).into();
id.reanchor(&target, &ancestry).unwrap();
assert_eq!(id, expected);

I got

left: `MultiLocation { parents: 2, interior: X3(Parachain(2000), Parachain(4000), GeneralIndex(42)) }`,
 right: `MultiLocation { parents: 2, interior: X2(Parachain(4000), GeneralIndex(42)) }`', xcm/src/v1/multilocation.rs:952:9

Do we want the Parachain(2000) to be repeated (it is in the ancestor and the multilocation of the reanchored id now)? I assumed not, since visiting it twice would be redundant, but maybe I'm missing some context. It also seems like there's not validation on the ancestry we pass into reanchor. How do we know that this ancestry is valid?

[KiChjang]

It looks to me that the id is not simplified, and here's why: ancestry is the path that the relay chain must take in order to get to our current consensus system, and so we can see that we're on parachain 2000. The ancestry should therefore not contain any parent junctions. We don't have any validation functions to check for a properly formed ancestry, but perhaps we can do so by making sure that the ancestry only has interior junctions and no parents, but it's not really the scope of this PR however.

What the id should say in this case is simply Parachain(4000)/GeneralIndex(42), the preceding ../Parachain(2000) should be dropped.

I would therefore expect the result after reanchoring to be ../../Parachain(2000)/Parachain(4000)/GeneralIndex(42), exactly as the test expects (up two levels to get to the common ancestor, which is the root, and then from the root, go to parachain 2000 and then parachain 4000, and finally reach for index 42).

Recall that the purpose of reanchoring is to rewrite the id from the perspective of target, and since the common ancestor between the current location and target is the root (i.e. the relay chain), it does make sense for it to go to parachain 2000 after traversing the two parent junctions.

[emmaling27]

Oh hm this is helpful, thanks @KiChjang. I have another question though: the first test case shows that the ancestry isn't necessarily the most recent common ancestor (see here). I was considering the following similar example:

let mut id: MultiLocation = (Parent, Parachain(1000), Parachain(4000), GeneralIndex(42)).into();
let ancestry = Parachain(2000).into();
let target = (Parent, Parachain(3000), Parachain(1000)).into();
let expected = (Parachain(4000), GeneralIndex(42)).into();
id.reanchor(&target, &ancestry).unwrap();
assert_eq!(id, expected);

This gave:

  left: `MultiLocation { parents: 2, interior: X3(Parachain(1000), Parachain(4000), GeneralIndex(42)) }`,
 right: `MultiLocation { parents: 0, interior: X2(Parachain(4000), GeneralIndex(42)) }`', xcm/src/v1/multilocation.rs:962:9

I am confused that reanchor returned 2 parents still, even though relative to the target at Parachain(1000) we don't have to go up any parents to get back to self so I thought it should return 0 parents. The observed behavior^ seems inconsistent with the first example (which returns 0 parents). I think I might be misunderstanding something about ancestry. Does ancestry have significance beyond being the MultiLocation self is relative to before we reanchor? Do we need to keep ancestry in the new MultiLocation even if there is a common ancestor of self and target that is deeper in junctions? Either way, shouldn't these two examples behave consistently?

[KiChjang]

I think there was a miscommunication -- the ancestry is not the common ancestor nor the most recent common ancestor, but the path in which the root (i.e. the relay chain) takes in order to reach the current MultiLocation. So if you see a single Parachain(2000) as your ancestry, it means that you are now located at parachain 2000.

Therefore the two examples you gave are already consistent. In both examples, self is parachain 2000, but with your latest one, it must first traverse back to the root (i.e. up one level) in order to then traverse down to parachain 1000. No such procedure is required for your previous example because the id is already located at parachain 2000.

[KiChjang]

Perhaps the part that you were stuck in is understanding that the target MultiLocation is already being written from the perspective of self, i.e. the junctions that you need to take from self in order to reach target?

[emmaling27]

Ok thanks! I now think I understand that ancestry is where self is and that target and id are relative to ancestry/self. I'm still confused about how these examples are different. I'm not seeing how the following is true:

id is already located at parachain 2000

Isn't id located at GeneralIndex(42) for both examples? Since target is at Parachain(1000) for both of them, can't you just walk down the junctions in id to get the relative path to id from target? I actually think my question is really, is there anything different about the two Parachain(1000)s? Why can't we go through them instead of these extra junctions in between (in this case, the Parent and Parachain(3000)? (This is also the first question I asked at the top of the thread; I still don't understand why we would go through the Parachain(2000) twice there).

[KiChjang]

Look closer at your target, you have two Parachain junctions. This means that parachain 3000 itself supports parachains connecting to it, and so what you actually have when you say ../Parachain(3000)/Parachain(1000) is parachain 1000 connected to parachain 3000. I suspect you thought parachain 1000 is connected to the relay chain? Because your MultiLocation suggests that it is not.

[emmaling27]

Oh I thought that all the MultiLocations in this fns are relative to the self/ancestry? Aren't they all connected by jumping up the graph with the parents and going down via the junctions? I think I conceptualized each parachain as being an absolute location, but looking at the definition of Junction it looks like these are actually relative, so these Parachain(1000)s could be different, just indexed the same way in their consensus system. Is that accurate?

[KiChjang]

That's correct. You can think of each junction as the next hop that you need to reach from the previous junction, so ../Parachain(3000)/Parachain(1000) means "go up one level, then go to the parachain indexed at 3000, and then from there, go to the parachain indexed at 1000". As you can see, this is wildly different from ../Parachain(1000), which is "go up one level, and then from there go to the parachain indexed at 1000".

[emmaling27]

This might be silly question - how do I get println! or dbg! macros to work in multilocation.rs? I see println! used in other parts of the repo but can't seem to find what I'm missing in Cargo.toml. The error I'm getting is:

error: cannot find macro `println` in this scope

This isn't blocking since I can always assert but I'm curious about why println! isn't accessible

[shawntabrizi]

@emmaling27 println! will be available when compiling with the std library. By default, all of the code used inside the Substrate runtime is made for no_std, but you can still drop in println! statements and just run cargo test ....

You can also try SKIP_WASM_BUILD=1 cargo build ... which should also skip the no_std compilation.

Finally, you can also try a special macro we have, which places code to only be compiled when compiling with std:

sp_std::if_std!{ println!("hi") }

This will be compiled out when compiling no_std, but show up with std.

However, most of the time I am doing print statements, I am just running local tests, which should support std anyway.

If this is not enough info, provide a sample of where you want to println! and how you want to trigger it, and we can try to help.

[emmaling27]

@shawntabrizi thanks I will try that next time! I opened a PR here paritytech/polkadot#4697 let me know your thoughts!

[shawntabrizi]

I think this can be closed. cc @KiChjang

[KiChjang]

Probably not actually; the algorithm for reanchoring hasn't changed at all and so we'd still like to optimize it.