gtlib/tsp/GTHashChain.php

<?php
/*
 * Copyright 2008-2010 GuardTime AS
 *
 * This file is part of the GuardTime PHP SDK.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * @package tsp
 */

/**
 * Hash chain object used to link timestamps to publication.
 *
 * Hash chain is a sequence of entries (links), each containing
 * <ul>
 * <li> hash algorithm identifier;
 * <li> a sibling hash value;
 * <li> concatenation direction indicator;
 * <li> level restriction (limiting the number of preceding steps) of this computation step.
 * </ul>
 *
 * Hash chain entries are presented as GTHashEntry objects.
 *
 * @package tsp
 */
class GTHashChain {

    private $entries = array();

    /**
     * Constructs a new GTHashChain instance.
     *
     * @throws GTException
     * @param  array $bytes hash chain bytes
     * @param  bool $checkLevel whether to check that level bytes are in increasing order
     */
    private function __construct(array $bytes, $checkLevel) {

        if (empty($bytes)) {
            throw new GTException("parameter bytes is required");
        }

        if (!is_array($bytes)) {
            throw new GTException("parameter bytes must be an array of bytes");
        }

        $previousLevel = -1;

        for ($i = 0; $i < count($bytes);) {

            $algorithm = GTHashAlgorithm::getByGtid($bytes[$i++]);

            if ($i >= count($bytes)) {
                throw new GTException("Invalid chain: not enough bytes");
            }

            $direction = $bytes[$i++];

            if ($i >= count($bytes)) {
                throw new GTException("Invalid chain: not enough bytes");
            }

            if ($direction != 0 && $direction != 1) {
                throw new GTException("invalid hash step direction: {$direction}");
            }

            $siblingAlgorithm = GTHashAlgorithm::getByGtid($bytes[$i++]);
            $siblingHash = new GTDataHash($siblingAlgorithm, array_slice($bytes, $i, $siblingAlgorithm->getLength()));

            $i += $siblingAlgorithm->getLength();

            if ($i >= count($bytes)) {
                throw new GTException("Invalid chain: not enough bytes");
            }
            $level = $bytes[$i++] & 0xFF;

            if ($checkLevel && $previousLevel >= $level) {
                throw new GTException("invalid hash step level: {$level}");
            }
            $previousLevel = $level;

            array_push($this->entries, new GTHashEntry($algorithm, $direction, $siblingHash, $level));
        }

    }

    /**
     * Computes the result of passing the given bytes through this hash chain.
     *
     * @throws GTException
     * @param  array $bytes bytes to compute chain output for
     * @return array chain output, the final hash value
     */
    public function computeOutput(array $bytes) {

        if (empty($bytes)) {
            throw new GTException("parameter bytes is required");
        }

        if (!is_array($bytes)) {
            throw new GTException("parameter bytes must be an array of bytes");
        }

        $output = $bytes;

        foreach ($this->entries as $entry) {
            $output = $entry->computeOutput($output);
        }

        return $output;

    }

    /**
     * Checks that past entries match in this history chain and the other provided history chain.
     *
     * Past history chain entries are those which have a 0 direction.
     *
     * @param  GTHashChain $hashChain history chain to compare this chain entries with
     * @return bool true if all past entries match, false otherwise
     */
    public function checkPastEntries(GTHashChain $hashChain) {

        $iter1 = new ArrayIterator($this->entries);
        $iter2 = new ArrayIterator($hashChain->entries);

        while ($iter1->valid()) {

            $entry = null;

            do {
                $entry = $iter1->current();
                $iter1->next();
            } while ($iter1->valid() && $entry->getDirection() == 1);

            if ($entry->getDirection() == 0 && !$iter2->valid()) {
                return false;
            }

            $other = null;

            do {
                $other = $iter2->current();
                $iter2->next();
            } while ($iter2->valid() && $other->getDirection() == 1);

            if ($entry->getDirection() == 1 && $other->getDirection() == 1) {
                return true;
            } else if ($entry != $other) {
                return false;
            }
        }

        return true;

    }

    /**
     * Computes location ID of this chain.
     *
     * This computation is only sensible for location chains.
     *
     * @return GTBigInteger location ID computed on this location chain
     */
    public function computeLocationId() {

        // Skip: machine bits + slot bits
        $topSkip = 3 + 3;
        $nationalSkip = 3 + 2;
        $stateSkip = 2 + 2;

        // Level: depth + machine bits + slot bits - 2
        $topLevel = 60 + $topSkip - 2;
        $nationalLevel = 39 + $nationalSkip - 2;
        $stateLevel = 19 + $stateSkip - 2;

        $locationId = new GTBigInteger(0);

        $i = count($this->entries) - 1;
        $i--; // skip hasher bit

        // calculate national id
        $idNational = 0;

        while (true) {
            $entry = $this->entries[$i--];

            if ($entry->getLevel() > $topLevel) {
                $idNational = 2 * $idNational + (1 - $entry->getDirection());

            } else {
                break;

            }
        }

        $locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idNational));

        // Skip machine and slot bits of top-level aggregator
        $i -= $topSkip;

        // Calculate state ID
        $idState = 0;

        while (true) {
            $entry = $this->entries[$i--];

            if ($entry->getLevel() > $nationalLevel) {
                $idState = 2 * $idState + (1 - $entry->getDirection());

            } else {
                break;
            }
        }

        $locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idState));

        // Skip machine and slot bits of national-level aggregator
        $i -= $nationalSkip;

        // Calculate local ID
        $idLocal = 0;

        while (true) {
            $entry = $this->entries[$i--];

            if ($entry->getLevel() > $stateLevel) {
                $idLocal = 2 * $idLocal + (1 - $entry->getDirection());

            } else {
                break;
            }

        }

        $locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idLocal));

        // Skip machine and slot bits of state-level aggregator
        $i -= $stateSkip;

        // Calculate client ID
        $idClient = 0;

        while ($i > 0) {
            $entry = $this->entries[$i--];
            $idClient = 2 * $idClient + (1 - $entry->getDirection());
        }

        $locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idClient));

        return $locationId;
    }

    /**
     * Computes history ID of this hash chain.
     *
     * History ID is the number of seconds from 1970-01-01 00:00:00 UTC to
     * the time corresponding  to the starting position of this hash chain
     * in the GuardTime calendar tree.
     *
     * This computation is only sensible for history chains.
     *
     * @param  string $publicationId history ID corresponding to the root of the
     * calendar tree from which the history chain was extracted.
     *
     * @return GTBigInteger history ID computed on this history chain
     */
    public function computeHistoryId($publicationId) {

        $N = $publicationId->add(new GTBigInteger(1));
        $m = 0; // number of 1 bits in N

        $bits = $N->toBits();

        for ($i = 0; $i < strlen($bits); $i++) {
            if ($bits{$i} == '1') {
                $m++;
            }
        }

        $hashChainLength = count($this->entries);
        $hashChainDirs = new GTBigInteger(0);

        $i = $hashChainLength;

        while ($i > 0) {
            $i--;
            $hashChainDirs = $hashChainDirs->shiftLeft(1);

            $entry = $this->entries[$i];

            if ($entry->getDirection() == 1) {
                $hashChainDirs = $hashChainDirs->bitOr(new GTBigInteger(1));
            }
        }

        // number of leading zeroes in $hashChainDirs
        $bits = $hashChainDirs->toBits();

        // pad to 64 bit
        while (strlen($bits) % 64 != 0) {
            $bits = '0' . $bits;
        }

        $z = 0;

        for ($i = 0; $i < strlen($bits); $i++) {
            if ($bits{$i} == '0') {
                $z++;
            } else {
                break;
            }
        }

        // Get leading zeros within `hashChainLen` number of last bits
        $z = $z - (64 - $hashChainLength);

        $count = 0;

        if ($z + 1 > $m) {
            $hashChainLength -= $m - 1;
            $count = 1;
        } else {
            $hashChainLength -= $z + 1;
            $count = $m - $z;
        }

        $mask = new GTBigInteger(0x1);
        $zero = new GTBigInteger(0x0);

        $i = 0;

        while ($i < $count && $N->comp($zero) > 0) {

            if ($N->bitAnd($mask)->comp($mask) == 0) {
                $N = $N->bitXOr($mask);
                $i++;
            }

            $mask = $mask->shiftLeft(1);
        }

        $hashChainDirs = $hashChainDirs->bitNot();

        $mask = new GTBigInteger(0x1);
        $n = new GTBigInteger(0);

        $i = 0;

        while ($i < $hashChainLength) {

            if ($hashChainDirs->bitAnd($mask)->comp($mask) == 0) {
                $n = $n->add($mask);
            }

            $mask = $mask->shiftLeft(1);
            $i++;
        }

        $result = new GTBigInteger($n);
        $result = $result->add($N);

        return $result;

    }

    /**
     * Builds a new location hash chain out of the specified hash chain bytes.
     *
     * Hash chain bytes is a binary representation of a hash chain extracted
     * from the timestamp.
     *
     * @static
     * @param  array $bytes byte array containing the hash chain bytes
     * @return GTHashChain hash chain object
     */
    public static function getLocationInstance(array $bytes) {
        return new GTHashChain($bytes, true);
    }

    /**
     * Builds a new history hash chain out of the specified hash chain bytes.
     *
     * Hash chain bytes is a binary representation of a hash chain extracted
     * from the timestamp.
     *
     * @static
     * @param  array $bytes byte array containing the hash chain bytes
     * @return GTHashChain hash chain object
     */
    public static function getHistoryInstance(array $bytes) {
        return new GTHashChain($bytes, false);
    }
}

?>