[BUG] - Token bundle in raw tx not ordered canonically

[refi93]

Internal/External External otherwise.

Area Native Tokens Related to Native Tokens (Mary).

Summary Not a bug per se, but at least complication/blocker when it comes to interoperability with HW wallets.

The asset names within the serialized asset group are apparently ordered alphabetically, but this isn't fully compliant with the canonical serialization CBOR specs, namely:

  The keys in every map must be sorted lowest value to highest.
  Sorting is performed on the bytes of the representation of the key
  data items without paying attention to the 3/5 bit splitting for
  major types.  (Note that this rule allows maps that have keys of
  different types, even though that is probably a bad practice that
  could lead to errors in some canonicalization implementations.)
  The sorting rules are:

  *  If two keys have different lengths, the shorter one sorts
     earlier;

Example command:

cardano-cli transaction build-raw --mary-era \
--tx-in 0000000000000000000000000000000000000000000000000000000000000000#0 \
--tx-out addr1q88w8sft932ckyuw0xtqvhw3y9ssygkn5ty2mrxy3s0m3y9hrpl88wzzxde89584pysyuhrmdypggxylltksmf6qqrms055em6+0\
+'1 1131301ad4b3cb7deaddbc8f03f77189082a5738c0167e1772233097.CardanoBits2278'\
+'1 1131301ad4b3cb7deaddbc8f03f77189082a5738c0167e1772233097.CardanoBits3838'\
+'1 1131301ad4b3cb7deaddbc8f03f77189082a5738c0167e1772233097.CardanoBits6932'\
+'1 3e07d877c7115f8b402de4a1c00ad9c1f0f00a9a1c25bec36c4cb634.LOVE'\
+'1 62233242a696c5eb394ee392df49727b61bfc797329108fccf3450f0.spacecoinsBud005'\
+'1 62233242a696c5eb394ee392df49727b61bfc797329108fccf3450f0.spacecoinsBud077'\
+'1 920102f4353f24c817e38b45f5282b4d7ccf9f64f445cc852e01c475.BUFFYBot196'\
+'1 923c31f3790f6a6c858971d6b1241390ed0e0dab5965652782ab12dc.AdaCard14494'\
+'1 923c31f3790f6a6c858971d6b1241390ed0e0dab5965652782ab12dc.AdaCard14552'\
+'1 923c31f3790f6a6c858971d6b1241390ed0e0dab5965652782ab12dc.AdaCard14553'\
+'1 9bee44c5c494dee38622e6da0b3b312820f9f75dd6cc256c769db788.CryptoKnittie04869'\
+'1 d5e6bf0500378d4f0da4e8dde6becec7621cd8cbf5cbb9b87013d4cc.SpaceBud312'\
+'1 d5e6bf0500378d4f0da4e8dde6becec7621cd8cbf5cbb9b87013d4cc.SpaceBud2934'\
+'1 d5e6bf0500378d4f0da4e8dde6becec7621cd8cbf5cbb9b87013d4cc.SpaceBud3843'\
  --fee 0 --out-file xxx.out

The resulting tx is:

83a30081825820000000000000000000000000000000000000000000000000000000000000000000018182583901cee3c12b2c558b138e7996065dd121610222d3a2c8ad8cc48c1fb890b7187e73b842337272d0f509204e5c7b690284189ffaed0da74000f78200a7581c1131301ad4b3cb7deaddbc8f03f77189082a5738c0167e1772233097a34f43617264616e6f4269747332323738014f43617264616e6f4269747333383338014f43617264616e6f426974733639333201581c3e07d877c7115f8b402de4a1c00ad9c1f0f00a9a1c25bec36c4cb634a1444c4f564501581c62233242a696c5eb394ee392df49727b61bfc797329108fccf3450f0a2507370616365636f696e7342756430303501507370616365636f696e7342756430373701581c920102f4353f24c817e38b45f5282b4d7ccf9f64f445cc852e01c475a14b4255464659426f7431393601581c923c31f3790f6a6c858971d6b1241390ed0e0dab5965652782ab12dca34c416461436172643134343934014c416461436172643134353532014c41646143617264313435353301581c9bee44c5c494dee38622e6da0b3b312820f9f75dd6cc256c769db788a15243727970746f4b6e6974746965303438363901581cd5e6bf0500378d4f0da4e8dde6becec7621cd8cbf5cbb9b87013d4cca34c537061636542756432393334014b5370616365427564333132014c5370616365427564333834330102009ffff6

Which when deserialized in https://cbor.me you can see

                  A3                    # map(3)
                     4C                 # bytes(12)
                        537061636542756432393334 # "SpaceBud2934"
                     01                 # unsigned(1)
                     4B                 # bytes(11)
                        5370616365427564333132 # "SpaceBud312"
                     01                 # unsigned(1)
                     4C                 # bytes(12)
                        537061636542756433383433 # "SpaceBud3843"
                     01                 # unsigned(1)

So the SpaceBud312 map key comes after SpaceBud2934 even though its shorter, violating the canonical CBOR specs.

This has interoperability implications on HW wallets which serialize the transactions canonically (Trezor in-memory and Ledger requires a deterministic ordering of the token bundle items to be able to reject duplicate keys which can otherwise lead to transactions with unclear effect which bears security implications), therefore cardano-hw-cli can't sign such a transaction with hw wallets.

Expected behavior If we agree canonical CBOR is the way to serialize transactions across tools in the Cardano ecosystem (for the sake of interoperability and security of hw wallets), the asset group keys should be in the order SpaceBud312, SpaceBud2934, SpaceBud3843 - i.e. ordered by length first and only then alphabetically (technically, by their CBOR representation length/alphabetical order but that shouldn't matter given the keys are of the same type).

System info (please complete the following information):

• CLI version 1.27.0

[gitmachtl]

This is an urgent one! For example i was not able to move out a specific NativeAsset (NFT) from a Wallet today. I had to do some special CLI "tricks" shifting Tokens around to get that one out. Thats nothing the normal user can do. So, we need a fix for the CBOR sorting via cardano-cli ASAP please, thx.

[dcoutts]

Summary from a private slack conversation:

I'm happy to discuss it further, but my current view is that it is the cardano-hw-cli that has the responsibility to pass the tx information to the hardware device in an order that is suitable for the constraints imposed by the hardware device. My view is that it should not be a universal constraint imposed on all tools (e.g. the cardano-cli). The constraint arises from the hardware, it should be local to just the hardware and the hardware's host software.

Yes for multisig this means that cooperating wallets that involve hardware may need to agree on a canonical representation, since they follow the approach of serialising the tx in multiple locations and expecting it to come to the same txid. A CIP is appropriate for that. But the cardano-cli would not be bound by that CIP.

Indeed, in any scheme where there is flexibility that is never used, things tend to ossify and assumptions creep in that everything does use the "normal" representation. So in that context a little arbitrary diversity is a good thing to stop unhelpful assumptions creeping into tools.

[AndrewWestberg]

I disagree. Cbor has specs for a reason. Tools that are following the specs should not have to work around cardano-cli which is not. The fix should happen in the tool not following the spec.

[dcoutts]

No, there's no non-compliance with specs here. Cardano Shelley (and onwards) does not use canonical CBOR. The node accepts any valid CBOR fitting the CDDL (plus some extra restrictions not desribable in the CDDL). The cardano-cli generates valid spec-compliant CBOR. There is no suggestion here that any tool is not following any spec (that it should actually be following).

The problem here is that hardware wallets have tighter constraints than that. Because hardware wallets are so constrained for memory space, they do not work by parsing the tx body CBOR. They work by being fed the intput data to make a transaction, and they produce the serialised representation as an output. Effectively this means that hardware wallets want to use a canonical representation (within all the permitted representations). This is fine, and hardware wallets can do that. It has implications for multi-sig, since it means all the wallets need to agree on that canonical form.

Furthermore, a CIP for wallets that did propose a canonical form is free to chose the details of that canonical form and still be fully compliant with the CBOR specification:

https://datatracker.ietf.org/doc/html/rfc7049#section-3.9

3.9. Canonical CBOR

Some protocols may want encoders to only emit CBOR in a particular canonical format; those protocols might also have the decoders check that their input is canonical. Those protocols are free to define what they mean by a canonical format and what encoders and decoders are expected to do. This section lists some suggestions for such protocols.

Emphasis added by me. So a CIP on this topic would be free to standardise as a canonical form the one we use now. The only difference from the suggestions in the CBOR spec is the sort order for map keys. The CBOR spec suggestion is (in my humble opinion) totally bonkers. Even Cardano Byron (which does use canonical CBOR) does not use that rule. The sane rule, which we use, is that the sort order is the natural sort order of the keys (e.g. the normal mathematical sort order for numbers, or the lexicographic order for byte strings).

[refi93]

the normal mathematical sort order for numbers, or the lexicographic order for byte strings)

@dcoutts sorry to circle back on this. This rule is clear to me as long as the keys in the map are of the same type, but I noticed in the CDDL the metadata (in case it is a map) can indeed have keys of different types (numbers/bytes/text) -

transaction_metadatum =
            { * transaction_metadatum => transaction_metadatum }
          / [ * transaction_metadatum ]
          / int
          / bytes .size (0..64)
          / text .size (0..64)

https://github.com/input-output-hk/cardano-ledger-specs/blob/d99dcda8c06a1bad301ebd4cad56cf51ab03852d/shelley-ma/shelley-ma-test/cddl-files/shelley-ma.cddl#L206

It's not clear to me yet how these keys of different types should be consistently sorted within a map following the rule above. Canonical CBOR addresses that by taking the cbor serialized representations of the keys and comparing these (but that would result in definite-length bytestrings of the same type being ordered by length as the length is being prepended in their CBOR representation) - could you clarify how to handle keys of different types? Or is the CDDL just too rigid to specify that keys of different types within the same map is an invalid case in Cardano?

[dcoutts]

Note that the cardano-cli has no defined order for tx metadata. It allows user supplied metadata, and uses whatever order is given by the user input.

You might not need any defined order for these in the hw case either: just use the exact order in which the user chooses to present it. You don't even need to exclude duplicates.

If one needs a canonical order for these, the obvious thing to do is to define a specific order of the types. For example that might be the order they appear here in the CDDL, or it could be the order of the 3bits of the CBOR major type (which is what the spec's canonical CBOR suggestion amounts to).

[gitmachtl]

@dcoutts i have to bring this topic up again, because the current implementation of the asset ordering within the cardano-cli generated txbody is again causing issues with hw-wallets. would it be possible to add an optional flag to the cli to generate the maps with the length before lexicographically order for the assetnames? Or a flag that would allow to add the assets in the order they are provided via the --tx-out parameters without reordering them internally? So they can be presorted externally.

Doing a reordering just for the hw-wallet-signing is not a good solution, because when you have multiple signers, the TxID would differ from the original TxBody. So we would need a presorted TxBody before starting the multiple signers process when it is a mixed setup of hw-keys and cli-keys.

[mark-stopka]

@disassembler I wonder if properly dusting the IOG UTxOs with right native assets would make @dcoutts change his mind... by the time it is time to rotate the community delegations... aren't you guys using ledger devices?

[gitmachtl]

@disassembler I wonder if properly dusting the IOG UTxOs with right native assets would make @dcoutts change his mind... by the time it is time to rotate the community delegations... aren't you guys using ledger devices?

hmm... 😄

[gitmachtl]

Note that the cardano-cli has no defined order for tx metadata. It allows user supplied metadata, and uses whatever order is given by the user input.

You might not need any defined order for these in the hw case either: just use the exact order in which the user chooses to present it. You don't even need to exclude duplicates.

If one needs a canonical order for these, the obvious thing to do is to define a specific order of the types. For example that might be the order they appear here in the CDDL, or it could be the order of the 3bits of the CBOR major type (which is what the spec's canonical CBOR suggestion amounts to).

@dcoutts can we please change the cardano-cli to not sort the given assets by its own strange order, just use the order that is provided via the given parameters on the call? also possible would be a flag as a parameter like --sort-assets if you wanna keep your current order. because currently even if you provide the assets in the order the hw wallets need them, cardano-cli reorders it in an own way.

also please read: https://github.com/Emurgo/cardano-serialization-lib/issues/240 and https://github.com/vacuumlabs/cardano-hw-cli/issues/104

thx!