Key Translation Duplicate Check Safety Hole

[JeremyRubin]

When translating keys in a given policy/miniscript, translating:

and(pk(A), pk(B))

with F: { A -> X, B -> X }

creates

and(pk(X), pk(X))

bypassing the check that no duplicate/repeated keys are used.

Fixing this requires changing from a function to a bijective map of some kind, either by tracing the function as it's used or switching the type externally to some kind of map.

cc @apoelstra @sanket1729, creating an issue for this to track fixing it

[sanket1729]

A simpler but slightly inefficient solution might be to retraverse the tree again. I am not against doing this because we are already traversing the tree once when translating.

[JeremyRubin]

@sanket1729 I advise caching because the function could have interior mutable state and lie to you...

[sanket1729]

@JeremyRubin, We can call the translate function only once and save the output policy/miniscript which possibly contains duplicate keys. Do the checks again on the translated miniscript/policy.

Am I missing something or are you looking for an efficient way to it while creating(one traversal) while aborting at the first duplicate?

[JeremyRubin]

Ah, certainly doing full checks after translating is the safest choice, but I think given that most functions are probably just getters around a map might make sense to do something just passing a map in. I'm for whatever works and closes the safety hole.

When you said 'retraverse' I thought you meant while translating in a manner that calls the function more than once per key. (Interestingly this sort of trick could be used to translate a duplicated-key script to non duplicated if it uses e.g. sequential HD derivation per call per key)

[sanket1729]

Planning to cleanly address this after #493.

[benma]

@sanket1729 reminder now that #493 is merged. I just experimented with this library and was quite confused why there was no error with duplicate keys present.

[sanket1729]

@benma. Are you facing the no error when translating keys using TranslatePk? This is fixed in #556. All regular methods from_str, parse, compile etc should currently be fail on duplicated keys.

[benma]

@benma. Are you facing the no error when translating keys using TranslatePk?

Yes exactly. Thanks for the fix.