Define a standard hashing procedure

[gouttegd]

To allow implementations to unambiguously and consistently assess whether two mapping records are identical, the spec could/should define a standard hashing function and how the hash should be computed.

Considerations:

A. Choice of the hashing function. Not really important, we just need to pick one. Easiest option would probably be SHA-256, which is almost ubiquitously available in all programming languages. We do not really need its cryptographic properties of collision resistance and preimage resistance, but they don’t hurt.

B. What to hash? Simply put: everything. That is, all the slots that make up a mapping record. This should also probably include any non-standard slot.

C. How to hash? This is the real question. We need to define a serialisation format such that any given mapping record can have one, and only one, possible serialised form. The “canonical SSSOM/TSV” format as currently defined in the spec is not suitable, as it still leaves some room for variations across implementations.

One option would be to serialise the record into a canonical S-expression, e.g.

(7:mapping((10:subject_id44:http://purl.obolibrary.org/obo/FBbt_00001234)(12:predicate_id:46http://www.w3.org/2004/02/skos/core#exactMatch)(9:object_id45:http://purl.obolibrary.org/obo/UBERON_0005678)(21:mapping_justification51:https://w3id.org/semapv/vocab/ManualMappingCuration)(10:creator_id(37:https://orcid.org/0000-0000-1234-567837:https://orcid.org/0000-0000-5678-1234))

Regardless of the exact serialisation format, prior to serialisation and hashing: (1) all CURIEs must be expanded to their full-length form; (2) all propagatable slots must be propagated; (3) all multi-valued slots must be sorted.

[gouttegd]

⬆ @matentzn FYI, follow-up to our discussion today.

[matentzn]

Yes this captures it greatly, and S-expression is a good idea. I think this is what James Overton also used in one of his earlier tools to represent OWL expressions in a canonical form. Thanks for writing this up!

[cthoyt]

I have implemented my own hashes in SeMRA, but I would be much happier for this to be an upstream discussion in the SSSOM spec! Happy to help on this.

[gouttegd]

Another question that needs an answer: Once we have the hash, how do we represent it?

Assuming we choose SHA2-256 as the condensation function, we will have a 32-bytes (256 bits) hash. We cannot use it directly, as each byte may contain any value in the 0-255 range (including null bytes and control characters). We need to turn it into a string containing only “printable” characters.

Options include:

• hexadecimal: that’s probably the easiest and most obvious solution. The problem is that it gives a long string (each byte is encoded on two characters, so 64 characters for a 32-bytes hash, e.g. FA8B85062AB1539CB51265B9B070C7B2080C54D3B00A30F3A9384D64C74284FF).
• Base64: gives the shortest string (44 characters for a 32-bytes hash), but the resulting string may include characters that possibly we may not want if the hash is to become part of an identifier, such as /, +, or = (e.g. EpmSBp/J+BJp8vnjUE7fcce+AJkhzdHqKn+qyA9vdL0=).
• Base32: possibly a good compromise, gives a 56-characters string (e.g. DXXPB6CAV5BAG4RKRA4NVBOK3RFA44B2TWNSZOHETJBK2DJCDZ5Q====).
• Z-Base32: another possible good compromise, gives a 52-characters strings (e.g. gg5w4gbt7515yyn19s63jzsp5zeoz98cjtbpuwghjcq4uq1bmqmy).

I am personally inclined towards Z-Base32, as it

• doesn’t require padding (contrary to the original Base32), giving slightly shorter strings than Base32 and avoiding the use of = characters;
• gives more human-readable strings.

[gouttegd]

This is what the standard hashing procedure could look like if we specify it based on how hashing is currently done in SSSOM-Java:

Step 0: Propagate all condensed slots

If the mapping set contains condensed slots (slots that have the same value for all mappings in the set, and that have therefore been written as if they were set-level metadata rather than mapping-level metadata), they MUST be propagated as per the standard rules.

Step 1: Turn the mapping into a canonical S-expression

(See RFC 9804 for the complete spec about S-expressions and their canonical form.)

Assemble the S-expression as follows:

1. Start with (7:mapping(.
2. Iterate over all slots of the Mapping class, in the order in which they are listed in the LinkML model. Exclude the record_id slot and the mapping_cardinality slot. For all other slots:
   1. If the slot has no value for the current mapping, skip to the next slot.
   2. Append to the S-expression (N:SLOTNAME, where SLOTNAME is the LinkML name for the slot and N is the length of the slot name (so, for example, (10:subject_id, (9:author_id, (10:confidence, etc.).
   3. If the slot is defined as a multi-valued slot (and even if it has only one value for this particular instance):
      1. Append (.
      2. Sort the list in lexicographical order and iterate over the sorted values. For each value V, append N:V, where N is the length of V.
      3. Append ).
   4. If the slot is typed as a floating point number (e.g. confidence), convert the value to a string V by truncating the floating point number to up to 3 digits after the decimal point, rounding the last digit to the nearest neighbour (rounding up if both neighbours are equidistant). Then append N:V, where N is the length of V.
   5. If the slot is typed as an enumeration (e.g. subject_type), append N:ENUMVALUE, where ENUMVALUE is the allowed value in the enumeration as specified in the LinkML model, and N is the length of ENUMVALUE (e.g. 9:owl class for a possible value for the subject_type slot).
   6. If the slot is typed as a date, append 10:YYYY-MM-DD, where YYYY-MM-DD is the representation of the value in the ISO-8601 format.
   7. If the slot is of any other type (string, entity reference, URI), append N:V, where V is the string value of the slot and N the length of the string value. Of note, if the value is an entity reference, V is the expanded form of that reference (according to the set’s curie map), regardless of whether the entity reference had originally been written as a CURIE (e.g. if the set has been read from a SSSOM/TSV file) or as a IRI.
   8. Append ).
3. If the implementation supports extension slots and the mapping does have such slots:
   1. Append (10:extensions(.
   2. Sort extension values by their properties in lexicographical order.
   3. For each extension value:
      1. Append (N:PROP, where PROP is the property identifying the extension and N is the length of the property.
      2. Append N:V), where V is the extension value proper and N its length.
   4. Append )).
4. Append )).

Step 2: Compute the SHA2-256 hash of the S-expresssion

Encode the S-expression assembled in step 1 into UTF-8 (if it was not already assembled directly in UTF-8). Hash the array of bytes containing the UTF-8 representation of the S-expression using the standard SHA2-256 hash function (NIST FIPS 180-4).

Step 3: Encode the hash into a ZBase32 string

Encode the hash computed in step 2 into its representation in the ZBase32 encoding (RFC 6189, http://philzimmermann.com/docs/human-oriented-base-32-encoding.txt).

[gouttegd]

Illustration: Given the following mapping set:

#curie_map:
#  FBbt: http://purl.obolibrary.org/obo/FBbt_
#  UBERON: http://purl.obolibrary.org/obo/UBERON_
#  orcid: https://orcid.org/
#mapping_set_id: https://example.org/sampleset
#license: https://creativecommons.org/licenses/by/4.0/
subject_id    predicate_id     object_id       mapping_justification          creator_id
FBbt:0001234  skos:exactMatch  UBERON:0005678  semapv:ManualMappingCuration  orcid:0000-0000-5678-1234|orcid:0000-0000-1234-5678

Following the above procedure procedure for the only mapping in this set would give:

1. Canonical S-expression for the mapping (whitespaces added for clarity, they MUST NOT appear in the actual S-expression!):

(7:mapping(
           (10:subject_id44:http://purl.obolibrary.org/obo/FBbt_00001234)
           (12:predicate_id46:http://www.w3.org/2004/02/skos/core#exactMatch)
           (9:object_id45:http://purl.obolibrary.org/obo/UBERON_0005678)
           (21:mapping_justification51:https://w3id.org/semapv/vocab/ManualMappingCuration)
           (10:creator_id(
                          37:https://orcid.org/0000-0000-1234-5678
                          37:https://orcid.org/0000-0000-5678-1234
            ))
))

2. SHA2-256 hash (in hexadecimal): e3bc1b4b586c6e86d0caf369d49c161163e255c4a779821f448a8e4fbd616522

(Can be obtained by echo -n "SEXPR" | openssl dgst -sha256, where SEXPR is the S-expression above.)

3. Resulting ZBase32-encoded hash: hq6bs14aptzepwgk6pw7j8ysnft6riqrw7har84rtk8r9xmbcwty

(Can be obtained by echo -n "SEXPR" | openssl dgst -sha256 -binary | zbase32.)

[cthoyt]

@gouttegd I think this is a good proposal. I haven't used canonical S-expressions before, but given that we will have many different languages implementing SSSOM, I think this is a good idea since it has an external definition.

I think a requirement for any proposal is to have a detailed testing suite that has many different records, covering all reasonable formulations of SSSOM records, and the resulting encoded hashes so everyone can test against that. I would also like to have an additional test that checks to make sure that as we add new SSSOM fields, that all of them have corresponding tests in the test suite.

What do you think are the next steps? I guess you have a working implementation in SSSOM-Java so maybe we would also want to get an implementation working in Python, too. I can contribute this.

[cthoyt]

Also, we should pick a canonical CURIE prefix and (stub) URI prefix to go with these hashes!

[gouttegd]

I think a requirement for any proposal is to have a detailed testing suite that has many different records, covering all reasonable formulations of SSSOM records, and the resulting encoded hashes so everyone can test against that.

Fully agree.

I think the spec itself should already give at least 2 or 3 sample mappings along with the corresponding hashes, and we should have somewhere a full compliance test suite (an idea already raised in #426) with many more test cases (not only for the hashing feature, but all other aspects of the spec as well).

What do you think are the next steps?

Agreeing on the hashing procedure, I guess. :) It would be a waste of time to (1) start building up a list of mappings along with the corresponding hashes and (2) start implementing the hashing procedure in Python, if we’re not all on the same page.

@matentzn Your opinion on the proposed hashing procedure?

maybe we would also want to get an implementation working in Python, too. I can contribute this.

I think we definitely want that in Python as well, yes. :)

[matentzn]

@matentzn Your opinion on the proposed hashing procedure?

Ehhhhh. I think.. I better leave this one to the PROs. I sanity checked the general idea. This sounds fine and you have previously convinced me of this approach. The details are a little beyond my experiment horizon.

The most important sentence in the proposal for me is this one (and I fully agree with it):

If the mapping set contains condensed slots (slots that have the same value for all mappings in the set, and that have therefore been written as if they were set-level metadata rather than mapping-level metadata), they MUST be propagated as per the standard rules.

Exclude the record_id slot and the mapping_cardinality slot.

Even though the mapping_cardinality slot can be derived from the mapping set, there is nothing in the spec saying that I am not allowed to lie about the cardinality - just saying.

[gouttegd]

Exclude the record_id slot and the mapping_cardinality slot.

Even though the mapping_cardinality slot can be derived from the mapping set, there is nothing in the spec saying that I am not allowed to lie about the cardinality - just saying.

The rationale for excluding the mapping_cardinality slot is that this slot is not so much a property of a mapping record, than a property of the set in which the record appears.

Consider the following record in the FBbt-to-Uberon mapping set:

subject_id      predicate_id                    object_id        mapping_justification
FBbt:00005098   semapv:crossSpeciesExactMatch   UBERON:0000010   semapv:ManualMappingCuration

In the FBbt mapping set, there is no other mapping with the same subject and no other mapping with the same object, so the mapping cardinality of that record would be 1:1.

But let’s merge the FBbt set with the Uberon set. Now there are plenty of other mappings with the UBERON:0000010 object:

subject_id      predicate_id                    object_id        mapping_justification
FBbt:00005098   semapv:crossSpeciesExactMatch   UBERON:0000010   semapv:ManualMappingCuration
MA:0000218      semapv:crossSpeciesExactMatch   UBERON:0000010   semapv:ManualMappingCuration
TAO:0000142     semapv:crossSpeciesExactMatch   UBERON:0000010   semapv:ManualMappingCuration
EMAPA:16665     semapv:crossSpeciesExactMatch   UBERON:0000010   semapv:ManualMappingCuration
FMA:9903        semapv:crossSpeciesExactMatch   UBERON:0000010   semapv:ManualMappingCuration

So now the cardinality of the FBbt:00005098-to-UBERON:0000010 mapping would be n:1 (many subject mapped to the same object), even though the mapping record itself has not changed – only the set in which it is contained has changed.

[matentzn]

So now the cardinality of the FBbt:00005098-to-UBERON:0000010 mapping would be n:1 (many subject mapped to the same object), even though the mapping record itself has not changed – only the set in which it is contained has changed.

Your argument is a bit more compelling. So I am fine with it. I would also support the other way around, just for the record!