Hashfuncties zijn alomtegenwoordig in de hedendaagse cryptografie. De Amerikaanse crytografiedeskundige Bruce Schneier¹ noemt ze niet voor niets de "werkpaarden van de moderne cryptografie". Ze worden onder andere gebruikt in digitale handtekeningen, bij het versleutelen van berichten, als vingerafdrukken om dubbels te detecteren en als controlemechanisme om foutieve gegevens te detecteren.

Peter Pearson ontwikkelde een snelle en eenvoudige hashfunctie die werkt met een permutatietabel $T$ van de natuurlijke getallen tussen 0 (inbegrepen) en 256 (niet inbegrepen). We noteren het $i$ -de getal in de tabel als $T_{i}$ ( $i = 0, 1, \dots, 255$ ). Bij Pearson hashing wordt de hashwaarde van een string $s$ als volgt berekend:

initiële hashwaarde: $h \leftarrow 0$
voor elk karakter $s_{i}$ van de string $s$ ( $i = 0, 1, \dots, | s | - 1$ )

$v \leftarrow ord (s_{i})$
$h \leftarrow (h + v) mod 256$
$h \leftarrow T_{h}$

In stap (2a) wordt de functie ord gebruikt om de integerwaarde van een karakter te bepalen (zie String.prototype.charCodeAt). In sommige implementaties — waaronder de originele implementatie van Pearson zelf — worden de twee waarden in stap (2b) gecombineerd met XOR ( $h \leftarrow (h XOR v) mod 256$ ) in plaats ze op te tellen. Het resultaat blijft altijd een hashwaarde tussen 0 (inbegrepen) en 256 (niet inbegrepen).

Pearson hashing is niet geschikt voor het versleutelen van berichten, maar wordt wel gebruikt voor niet-cryptografische doeleinden zoals het opbouwen van een blockchain — het algoritme achter Bitcoin² en andere cryptovaluta³.

Een blockchain is een voor het publiek leesbare databank waarin gegevens in blokken opgeslagen worden in een onveranderlijke en controleerbare keten. Er kunnen slechts twee bewerkingen uitgevoerd worden op de databank:

toevoegen (adjoin): toevoegen van een nieuw datum (gegevensitem) aan de databank
valideren (validate): controleren of de databank volledig en ongeschonden is

Er is geen bewerking om gegevens te wissen. Van zodra een datum aan de databank wordt toegevoegd, kan deze nooit meer verwijderd worden. Er is geen bewerking om gegevens te wijzigen. Er is geen bewerking om gegevens te sorteren. Van zodra een datum aan de databank wordt toegevoegd, kan deze nooit binnen de keten verplaatst worden.

Voorbeeld van blokken in een blockchain.

Elk blok in de keten heeft vier eigenschappen:

index (integer): start bij nul en wordt telkens met één verhoogd als er een nieuw blok aan de keten toegevoegd wordt
datum (string): willekeurige string met gegevens
hash (integer): hashwaarde van het blok (zie verder)
vorigeHash (integer): hashwaarde van het vorige blok in de keten

Het eerste blok van een blockchain wordt het genesisblok genoemd. Per definitie heeft dit blok index 0, datum Genesis Block en vorige hashwaarde 0. Het genesisblok bepaalt ook welke hashfunctie gebruikt wordt voor het opbouwen van de blockchain (bijvoorbeeld Pearson hashing). De hashwaarde van een blok wordt berekend als de hashwaarde van de string die bestaat uit de opeenvolging van de index, de datum en de hashwaarde van het vorige blok in de keten. Voor het genesisblok is dit dus de string 0Genesis Block0.

De blockchain zelf is een gelinkte lijst van blokken die kan uitgebreid worden door een nieuw blok met een gegeven datum toe te voegen (adjoin) aan een bestaand blok. Het valideren (validate) van een blok bestaat erin om de hashwaarde van het blok opnieuw te berekenen en te vergelijken met de ingestelde hashwaarde. Als dat het geval is, dan wordt de bewerking herhaald voor de voorgaande blokken in de keten, totdat het genesisblok bereikt wordt. De blockchain is corrupt van zodra een berekende hashwaarde verschilt van een ingestelde hashwaarde. Als het genesisblok bereikt wordt zonder een fout te vinden, dan is de blockchain geldig.

Opgave

Definieer een klasse Pearson waarmee de Pearson hashwaarde van strings kan berekend worden. Zorg ervoor dat de klasse minstens de volgende methoden ondersteunt:

Een constructor met twee parameters tabel en combineer. Aan de parameter tabel kan een permutatietabel $T$ (array) van de natuurlijke getallen tussen 0 (inbegrepen) en 256 (niet inbegrepen) doorgegeven worden. Als de waarde undefined wordt doorgegeven aan de parameter tabel dan wordt als permutatietabel $T$ de reeks 0, 1, …, 255 gebruikt. Als de waarde die wordt doorgegeven aan de parameter tabel geen permutatie is van de natuurlijke getallen tussen 0 (inbegrepen) en 256 (niet inbegrepen) dan moet een AssertionError opgeworpen worden met de boodschap ongeldige tabel. Aan de parameter combineer kan een functie met twee parameters $h$ en $v$ doorgegeven worden. Deze functie wordt gebruikt om de twee waarden te combineren in stap (2b) van de procedure voor Pearson hashing. Als de waarde undefined wordt doorgegeven aan de parameter combineer dan worden de twee waarden gecombineerd als $(h + v) mod 256$ .
Een methode hash waaraan een string moet doorgegeven worden. De functie moet de Pearson hashwaarde voor de gegeven string teruggeven.

Definieer ook nog een klasse Blok waarmee blokken uit een blockchain kunnen voorgesteld worden. Aan de constructor kan een hashfunctie doorgegeven worden. Deze hashfunctie wordt voorgesteld door een object met een methode hash waaraan een string $s$ kan doorgegeven worden en die de hashwaarde van de string $s$ teruggeeft. Als er geen hashfunctie wordt doorgegegeven aan de constructor dan moet de blockchain gebruikmaken van Pearson hashing met als permutatietabel $T$ de reeks 0, 1, …, 255.

Elk object van de klasse Blok moet vier eigenschappen hebben die bepaald worden zoals beschreven in de inleiding: index, datum, hash en vorig_hash. De eigenschappen index en vorigeHash zijn onveranderlijk. Als een poging wordt ondernomen om deze eigenschappen te wijzigen, dan moet een AssertionError opgeworpen worden met de boodschap can't set attribute. De eigenschappen datum en hash moeten wel gewijzigd kunnen worden, in een poging om de blockchain aan te passen.

Zorg ervoor dat de klasse Blok minstens de volgende methoden ondersteunt:

Een methode toevoegen waaraan een datum (string) moet doorgegeven worden. De methode moet een nieuw blok met gegeven datum aan de blockchain toevoegen en een verwijzing naar dit nieuw blok (een object van de klasse Blok) teruggeven.
Een methode isGeldig waaraan geen argumenten kunnen doorgegeven worden. De methode moet een Booleaanse waarde teruggeven die de geldigheid aangeeft van de keten die start bij het blok waarop de methode wordt aangeroepen.

Voorbeeld

        >>> const pearson01 = new Pearson();
>>> pearson01.hash("Hello");
244
>>> pearson01.hash("Hello,");
32
>>> pearson01.hash("Hell,o");
32
>>> pearson01.hash("Hel,lo");
32
>>> pearson01.hash("Hello, World!");
105

>>> const pearson02 = new Pearson([...Array(256).keys()].reverse());
>>> pearson02.hash("Hello");
173
>>> pearson02.hash("Hello,");
38
>>> pearson02.hash("Hell,o");
160
>>> pearson02.hash("Hel,lo");
32
>>> pearson02.hash("Hello, World!");
234

>>> const pearson03 = new Pearson([...Array(256).keys()].reverse(), (h, v) => (h ^ v) % 256);
>>> pearson03.hash("Hello");
189
>>> pearson03.hash("Hello,");
110
>>> pearson03.hash("Hell,o");
110
>>> pearson03.hash("Hel,lo");
110
>>> pearson03.hash("Hello, World!");
210

>>> new Pearson([1, 2, 3, 4]);
AssertionError: ongeldige tabel

>>> let genesis = new Blok();
>>> [genesis.index, genesis.datum, genesis.hash, genesis.vorigeHash];
[0, "Genesis Block", 57, 0]
>>> genesis.isGeldig();
true

>>> let blokA = genesis.toevoegen("A");
>>> [blokA.index, blokA.datum, blokA.hash, blokA.vorigeHash];
[1, "A", 222, 57]
>>> blokA.isGeldig();
true

>>> let blokB = blokA.toevoegen("B");
>>> [blokB.index, blokB.datum, blokB.hash, blokB.vorigeHash];
[2, "B", 10, 222]
>>> blokB.isGeldig();
true

>>> let blokC = blokB.toevoegen("C");
>>> [blokC.index, blokC.datum, blokC.hash, blokC.vorigeHash]
[3, "C", 215, 10]
>>> blokC.isGeldig();
true

>>> let blokD = blokB.toevoegen("D");
>>> [blokD.index, blokD.datum, blokD.hash, blokD.vorigeHash];
[3, "D", 216, 10]
>>> blokD.isGeldig();
true

>>> blokD.index = 100;
AssertionError: can"t set attribute
>>> blokD.vorigeHash = 200;
AssertionError: can"t set attribute

>>> blokD.hash = 666;
666
>>> blokA.isGeldig();
true
>>> blokB.isGeldig();
true
>>> blokC.isGeldig();
true
>>> blokD.isGeldig();
false
>>> blokD.hash = 216;
216
>>> blokA.isGeldig();
true
>>> blokB.isGeldig();
true
>>> blokC.isGeldig();
true
>>> blokD.isGeldig();
true

>>> blokB.datum = "XXX";
"XXX"
>>> blokA.isGeldig();
true
>>> blokB.isGeldig();
false
>>> blokC.isGeldig();
false
>>> blokD.isGeldig();
false
>>> blokB.datum = "B";
"B"
>>> blokA.isGeldig();
true
>>> blokB.isGeldig();
true
>>> blokC.isGeldig();
true
>>> blokD.isGeldig();
true

>>> let genesis = new Blok(new Pearson([...Array(256).keys()].reverse()));
>>> [genesis.index, genesis.datum, genesis.hash, genesis.vorigeHash];
[0, "Genesis Block", 52, 0]
>>> genesis.isGeldig();
true

>>> let blokA = genesis.toevoegen("A");
>>> [blokA.index, blokA.datum, blokA.hash, blokA.vorigeHash];
[1, "A", 243, 52]
>>> blokA.isGeldig();
true

Bronnen

Pearson P (1990). Fast hashing of variable-length text strings. Communications of the ACM 33(6), 677–680. ⁴