Suggestion: Creating a unique identifier for programs: Canonical CMR and parameter slots

[stringhandler]

Project

core

Describe the feature

This concept could also be logged in rust-simplicity or even simplicity but will create it here since it deals with parameters.

Problem

Wallets will need a way of identifying simplicity programs for deterministic recovery. Something similar to miniscript fragments used for wallet descriptors.

Wallets will most likely store the SimplicityHL source code and recompile them with parameters. I am suggesting an identifier for this source code.

Canonical CMR

Since the program already has the concept of CMR's, I suggest we uniquely identify a program through this process:

1. Substitute each parameter (word in the compiled code) with an index per type. So the first u32 would be 0, second u32 would be 1, third parameter might be a u256, which would be 0. (Note: the ordering is up for debate, but I would suggest using the same post node ordering that encoding uses)
2. Generate a CMR using this code.

The program can then be encoded as <ccmr><param_type><param_type>.....

This has the added benefit of allowing parameter substitution into a compiled simplicity program.

Notes

1. Originally, I used zero for all parameter values, but this has the consequence of generating a different node structure due to node sharing. This could still be considered, but there could be multiple programs that compile to the same CCMR. Another reason is that round trip encoding of programs should remain the same. As it is, a round trip encoding/decoding of a program with duplicate parameters would result in different encodings.
2. I suggest a unique index per type, instead of unique overall, otherwise some indexes may overflow the type. Even with this adjustment, the ccmr would be limited to 2 boolean args, 4 u2 args,
3. Calculating CCMRs from onchain or pruned programs. Originally I came up with the concept of CCMRs while working on every-simplicity. I was trying to match programs from the block explorer back to their source code. However, case nodes are pruned and will differ if there are parameters stored in their branches.

I am happy to hear other solutions.

[apoelstra]

If the goal is to fit this whole identifier into one line (or one "symbol") I think we should use descriptor expressions for this.

See https://bips.dev/388/ which solves a similar problem in Bitcoin.