source: flexoentity/org/FlexoEntity.org@ 33be5a0

* Tech-Talk - Hashes / IDs / Lebenszyklen / FlexoEntity
:PROPERTIES:
:CUSTOM_ID: hashes-ids-lifecycle
:END:

** Was ist ein Hash?

Ein Hash ist wie eine Art eindeutige Kennnummer oder ein "Fingerabdruck" für Daten, der
sich aus eben diesen Daten über den Algorithmus einer Hash-Funktion errechnet.

** Was ist kein Hash?

Die ISBN identifiziert ein Buch eindeutig. Sie ist nicht das Buch selbst, sondern eher ein
Identifier (eine geordnete Nummer mit Prüfziffer). Sie ist aber kein Hash, weil sie nicht
aus dem Inhalt des Buches berechnet wird. Ähnliches gilt für die IBAN

|-------------------------+---------------------------+-------------------------------------|
| Merkmal                 | Hash                      | Identifier (z. B. ISBN, IBAN, UUID) |
|-------------------------+---------------------------+-------------------------------------|
| Abhängig vom Inhalt     | ja                        | nein                                |
| Ziel                    | Integrität / Vergleich    | Identität / Referenz                |
| Länge                   | fix z. B. 32 Hex-Zeichen  | frei definierbar                    |
| Zufällig oder berechnet | deterministisch berechnet | oft generiert oder vergeben         |
|-------------------------+---------------------------+-------------------------------------|

** Warum verwenden wir Hashes?

Hashes sind super praktisch, weil sie uns eine Menge Zeit und Rechenleistung sparen.
Anstatt zwei große Dateien oder ganze Bücher direkt miteinander zu vergleichen,
vergleichen wir einfach ihre Hashes. Wenn die Hashes gleich sind, wissen wir,
dass die Daten sehr wahrscheinlich identisch sind. Wenn sie unterschiedlich sind,
hat sich etwas geändert. Das spart enorm viel Aufwand.

** Ein wichtiger Punkt

Wichtig ist auch zu verstehen, dass Hashes sogenannte "One-Way-Funktionen" sind.
Das heißt, man kann das Hashing nicht einfach umkehren, um das ursprüngliche Objekt wiederherzustellen.
Ein Hash ist also eine Einbahnstraße: Er dient nur dazu, die Daten zu repräsentieren,
aber man kann nicht vom Hash auf die originalen Daten zurückrechnen.

** Beispiele für den Einsatz von Hashes

- **Passwort-Hashes**: Wenn du ein Passwort eingibst, wird oft nur der Hash gespeichert, nicht das
   eigentliche Passwort. So bleibt es sicher, selbst wenn jemand die Datenbank stiehlt.

   Beispiel aus der /etc/shadow-Datei

root:$6$tsicHaoV3Q$YtAbiIvrHGXFtAJYz9tcEYWHXiGVQ40sJAgzPAbc57lIq9jH8eYjWXwctSW6YQnrMznRFcm6yXLnnY9mHhso20
enno:$6$sdygzfEgx0$YpaZJMQdkZgxGPclphz6RojqNG.PSNEq1oIHRP4kvZRN2iuS5MQrxt0nCkrYQIcpDGyohrb1o0S/GkWrFriWL1

- **Git-Commits**: In Versionskontrollsystemen wie Git werden Hashes benutzt, um jeden Schwung an
  Änderungen mit einer eindeutigen Kennung zu versehen

- **URL-Shortener: hash("https://example.com") → 8a3f12
  
** FlexOID

Die FlexOID ist eine Mischform. Sie selbst ist ein Identifier, der als Bestandteil aber einen Hash
enthält, um möglichst eindeutig, aber nicht zu lang zu sein.

AF-Q251022-70F759@001D
│  │ │       │     │ │
│  │ │       │     │ └── State (Draft, Approved, Signed, Published, Obsolete)
│  │ │       │     └──── Version
│  │ │       └────────── Hash (3 bytes, 6 Stellen)
│  │ └────────────────── Date (YYMMDD)
│  └──────────────────── Entity type (Question)
└─────────────────────── Domain (e.g. Air force)

In der ersten Variante der FlexOID habe ich mich mit einem 6-stelligen Hash zufrieden gegeben,
weil das einfach lesbarer ist. Warum reicht das nicht?

** Das Geburtstags-Paradoxon

Der obige 3-Byte Hash liefert mir etwas über 16 Millionen unterschiedlich Varianten.
Das klingt viel. Ist es aber nicht. Wieviele Schüler müssen nacheinander die Klasse
betreten bis sich zwei finden, die mit mehr als 50 Prozent Wahrscheinlichkeit am gleichen
Tag Geburtstag (also ein identisches Merkmal) haben?

** Lösung

Ab 23 Schülern beträgt die Wahrscheinlichkeit 50 % (näherungsweise Wurzel 365 Tagen)

Bei 47 Schülern beträgt die Wahrscheinlichkeit bereits 95 Prozent

Unsere 3 Bytes ergeben zwar 16.000.000 mögliche Varianten - im Gegenzug zu den 365 Tagen im Jahr
aus dem Geburtstagsbeispiel - aber da die Wahrscheinlichkeit zur Kollision hier bei
etwa Wurzel 16 Mio. liegt, bekommt man bereits bei 4000 Neuzugängen die ersten
Übereinstimmungen im Hash.

Der Hash ist also nicht gut genug, weil man sehr schnell und sehr häufig, diese
Übereinstimmungen feststellen und behandeln müsste, wenn man weiterhin eindeutige
Zuordnungen treffen will.

Wenn man die Ausgabe der Hashfunktion auf 6 Bytes erweitert, kommen die ersten Kollisionen
erst bei etwa 20 Mio erzeugten Hashes (Fingerabdrücken) und die kann man dann ohne
Einbußen gesondert behandeln (Salzen), weil es so selten passiert.

Übrigens, wenn man beim Menschen den Daumenabdruck nimmt und sich dabei auf 12 Merkmale
beschränkt und sehr lockere Toleranzen ansetzt (was man in der Praxis nicht macht),
hat man bereits nach 14000 Menschen eine Übereinstimmung. Bei 24 Merkmalen und sehr
lockeren Toleranzen, hat man bei etwa nach 9 Mio. Menschen eine ungefähre Übereinstimmung.
Da muss die Polizei schon sehr schlampig arbeiten, damit man fälschlicherweise beschuldigt wird.
Die Zahlen in der Realität sind sogar noch deutlich höher.

** FlexoEntity

Nun haben wir gesehen, dass wir mit der FlexOID (mit 6-Byte Hash) sehr viele unterschiedliche
Dinge eindeutig bestimmen können. Da unsere FlexOID erstmal nur eine Zeichenfolge ist,
brauchen wir etwas das damit umgehen kann und was dafür verantwortlich ist. Das ist die FlexoEntity.

Sie beinhaltet zusätzlich eine Signatur und ein Origin-Feld, wo festgehalten wird, woher diese
Entität stammt (beispielsweise aus einer Hashkollision oder einer Änderung an den weiteren Daten)

Jede Klasse, die von FlexoEntity erbt, muss zwingend die Method "text_seed" implementieren, mit der
der Algorithmus einer Hash-Funktion gefüttert wird, aus der dann der 6-Byte Hash herauspurzelt.
Hashfunktionen sind z.B. MD5, SHA1, SHA256 oder wie von mir genutzt Blake2s.
Die Mathematik dahinter ist recht aufwändig, aber wer sich mal einlesen möchte

- Hashing in Smalltalk: Theory and Practice von Andres Valloud

Damit die Hash-Funktion genug Eingabedaten pro Entity hat, muss man sich überlegen, welche Merkmale
einer Entität man durch "text_seed" übermittelt.

** text_seed

Man kann beliebige Klassen von FlexoEntity ableiten und erhält ohne Aufwand die Funktionalität
zur eindeutigen Identifizierung und zur Lebenszyklus-Verwaltung


Das ist das Beispiel einer OptionQuestion, also einer Testfrage, wo mögliche Antworten enthalten sind

    @property
    def text_seed(self) -> str:
        """Include answer options (and points) for deterministic ID generation."""
        base = super().text_seed
        if not self.options:
            return base

        joined = "|".join(
            f"{opt.text.strip()}:{opt.points}"
            for opt in sorted(self.options, key=lambda o: o.text.strip().lower())
        )
        return f"{base}::{joined}"

** Lebenszyklus

Der Lebenszyklus einer Entität folgt dieser Reihenfolge und ist nicht umkehrbar

- Entwurf (DRAFT)
- Genehmigt (APPROVED)
- Unterschrieben (SIGNED)
- Veröffentlicht (PUBLISHED)
- Veraltet (OBSOLETE)

Eine Entität, die bereits die Stufe Veröffentlicht erreicht hat, kann nicht in die Stufe
(nur) Unterschrieben zurückkehren. Daher ist auch die Lebenszyklusstufe in der ID kodiert
(letztes Symbol der FlexOID)

Beispiele für Entitäten:

- Testfrage
- Fragenkatalog
- Einstufungstest
- Zertifikat

Ein veröffentlichter Einstufungstest kann nur Fragen beinhalten, die ihrerseits die Stufe Veröffentlicht
erreicht haben. Ein Zertifikat kann nur ausgestellt werden, wenn der passende Einstufungstest die Stufe
Veröffentlicht hat. Das origin-Feld des Zertifikats sollte sinnvollerweise die ID des Tests enthalten.
        
** Erhöhung der Versionsnummer oder neue ID

Sobald - aus Gründen - eine neue ID vergeben werden muss, wird ggf. die Ursprungs-ID
im Feld origin der neuen FlexoEntity gespeichert. So ist immer ein Suchen im Stammbaum möglich.

Eine einfache Erhöhung der Versionsnummer (am Ende der ID) ist unter Umständen auch ausreichend,
damit nicht zu häufig komplett neue IDs erzeugt werden müssen. Der Entscheidungsbaum dazu ist
für das Projekt FlexoGrader recht umfangreich und soll hier nicht weiter besprochen werden.
Da es aber im Hintergrund passiert und vom Endanwender nicht bemerkt wird, behindert der
Mechanismus die Nutzung des FlexoGrader (TM) nicht. 

** Lizenz

Da ich die FlexoEntity-Bibliothek in meiner Freizeit entworfen und programmiert habe,
bin ich alleiniger Urheber. Als Lizenz habe ich MIT gewählt, somit kann - unter Nennung
des Urhebers - jeder damit machen, was er möchte

Der FlexoGrader ist ein Bundeswehrprojekt, welches ich im Dienst programmiere und somit
gehen die Nutzungsrechte uneingeschränkt auf den Dienstherren über.

Das betrifft auch etwaige Folgeprojekte wie FlexoVault und FlexoDrill