Document (and test) sources of non-determinism in fulfillments

[justmoon]

• Order of subfulfillments and subconditions in threshold-sha-256 fulfillment is undetermined
• DER
  • Unused bits in a BIT ARRAY (e.g. subtypes) are ignored

[ssadler]

Hm, this first one seems to be important. Some ledgers derive the transaction ID from the body of a transaction including the signatures / fulfillments.

I noticed that my implementations, and also the Python implementation, are susceptible to this malleability; they don't check the order of conditions when deserialising, and they sort the conditions before producing a threshold fingerprint, which means that you can trivially rearrange the fulfillment binary (producing a different transaction) but when you derive the condition binary you'll still get a match:

# threshold with two preimages
b'\xa2\x13\xa0\x0f\xa0\x05\x80\x03abc\xa0\x06\x80\x04abcd\xa1\x00'
# here they are swapped
b'\xa2\x13\xa0\x0f\xa0\x06\x80\x04abcd\xa0\x05\x80\x03abc\xa1\x00'

@sbellem @sappenin

Edit: I guess the easiest thing to do for now in order to handle both the above issues is just to encode the fulfillment binary again and compare it with the given one.

Edit2: Actually that doesn't solve the issue, since if the subfulfillments are sorted by cost prior to encoding the fulfillment payload, and there are 2 of equal cost, the indeterminism remains.