src/crypto/equihash.cpp

// Copyright (c) 2016 Jack Grigg
// Copyright (c) 2016 The Zcash developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

// Implementation of the Equihash Proof-of-Work algorithm.
//
// Reference
// =========
// Alex Biryukov and Dmitry Khovratovich
// Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem
// NDSS ’16, 21-24 February 2016, San Diego, CA, USA
// https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf

#include "crypto/equihash.h"
#include "util.h"

#include <algorithm>
#include <iostream>
#include <stdexcept>

#include <boost/optional.hpp>

EhSolverCancelledException solver_cancelled;

template<unsigned int N, unsigned int K>
int Equihash<N,K>::InitialiseState(eh_HashState& base_state)
{
    uint32_t le_N = htole32(N);
    uint32_t le_K = htole32(K);
    unsigned char personalization[crypto_generichash_blake2b_PERSONALBYTES] = {};
    memcpy(personalization, "ZcashPoW", 8);
    memcpy(personalization+8,  &le_N, 4);
    memcpy(personalization+12, &le_K, 4);
    return crypto_generichash_blake2b_init_salt_personal(&base_state,
                                                         NULL, 0, // No key.
                                                         N/8,
                                                         NULL,    // No salt.
                                                         personalization);
}

// Big-endian so that lexicographic array comparison is equivalent to integer
// comparison
void EhIndexToArray(const eh_index i, unsigned char* array)
{
    assert(sizeof(eh_index) == 4);
    eh_index bei = htobe32(i);
    memcpy(array, &bei, sizeof(eh_index));
}

// Big-endian so that lexicographic array comparison is equivalent to integer
// comparison
eh_index ArrayToEhIndex(const unsigned char* array)
{
    assert(sizeof(eh_index) == 4);
    eh_index bei;
    memcpy(&bei, array, sizeof(eh_index));
    return be32toh(bei);
}

eh_trunc TruncateIndex(const eh_index i, const unsigned int ilen)
{
    // Truncate to 8 bits
    assert(sizeof(eh_trunc) == 1);
    return (i >> (ilen - 8)) & 0xff;
}

eh_index UntruncateIndex(const eh_trunc t, const eh_index r, const unsigned int ilen)
{
    eh_index i{t};
    return (i << (ilen - 8)) | r;
}

template<size_t WIDTH>
StepRow<WIDTH>::StepRow(unsigned int n, const eh_HashState& base_state, eh_index i)
{
    eh_HashState state;
    state = base_state;
    unsigned char array[sizeof(eh_index)];
    eh_index lei = htole32(i);
    memcpy(array, &lei, sizeof(eh_index));
    crypto_generichash_blake2b_update(&state, array, sizeof(eh_index));
    crypto_generichash_blake2b_final(&state, hash, n/8);
}

template<size_t WIDTH> template<size_t W>
StepRow<WIDTH>::StepRow(const StepRow<W>& a)
{
    assert(W <= WIDTH);
    std::copy(a.hash, a.hash+W, hash);
}

template<size_t WIDTH>
FullStepRow<WIDTH>::FullStepRow(unsigned int n, const eh_HashState& base_state, eh_index i) :
        StepRow<WIDTH> {n, base_state, i}
{
    EhIndexToArray(i, hash+(n/8));
}

template<size_t WIDTH> template<size_t W>
FullStepRow<WIDTH>::FullStepRow(const FullStepRow<W>& a, const FullStepRow<W>& b, size_t len, size_t lenIndices, int trim) :
        StepRow<WIDTH> {a}
{
    assert(len+lenIndices <= W);
    assert(len-trim+(2*lenIndices) <= WIDTH);
    for (int i = trim; i < len; i++)
        hash[i-trim] = a.hash[i] ^ b.hash[i];
    if (a.IndicesBefore(b, len, lenIndices)) {
        std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim);
        std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim+lenIndices);
    } else {
        std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim);
        std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim+lenIndices);
    }
}

template<size_t WIDTH>
FullStepRow<WIDTH>& FullStepRow<WIDTH>::operator=(const FullStepRow<WIDTH>& a)
{
    std::copy(a.hash, a.hash+WIDTH, hash);
    return *this;
}

template<size_t WIDTH>
bool StepRow<WIDTH>::IsZero(size_t len)
{
    // This doesn't need to be constant time.
    for (int i = 0; i < len; i++) {
        if (hash[i] != 0)
            return false;
    }
    return true;
}

template<size_t WIDTH>
std::vector<eh_index> FullStepRow<WIDTH>::GetIndices(size_t len, size_t lenIndices) const
{
    std::vector<eh_index> ret;
    for (int i = 0; i < lenIndices; i += sizeof(eh_index)) {
        ret.push_back(ArrayToEhIndex(hash+len+i));
    }
    return ret;
}

template<size_t WIDTH>
bool HasCollision(StepRow<WIDTH>& a, StepRow<WIDTH>& b, int l)
{
    // This doesn't need to be constant time.
    for (int j = 0; j < l; j++) {
        if (a.hash[j] != b.hash[j])
            return false;
    }
    return true;
}

template<size_t WIDTH>
TruncatedStepRow<WIDTH>::TruncatedStepRow(unsigned int n, const eh_HashState& base_state, eh_index i, unsigned int ilen) :
        StepRow<WIDTH> {n, base_state, i}
{
    hash[n/8] = TruncateIndex(i, ilen);
}

template<size_t WIDTH> template<size_t W>
TruncatedStepRow<WIDTH>::TruncatedStepRow(const TruncatedStepRow<W>& a, const TruncatedStepRow<W>& b, size_t len, size_t lenIndices, int trim) :
        StepRow<WIDTH> {a}
{
    assert(len+lenIndices <= W);
    assert(len-trim+(2*lenIndices) <= WIDTH);
    for (int i = trim; i < len; i++)
        hash[i-trim] = a.hash[i] ^ b.hash[i];
    if (a.IndicesBefore(b, len, lenIndices)) {
        std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim);
        std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim+lenIndices);
    } else {
        std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim);
        std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim+lenIndices);
    }
}

template<size_t WIDTH>
TruncatedStepRow<WIDTH>& TruncatedStepRow<WIDTH>::operator=(const TruncatedStepRow<WIDTH>& a)
{
    std::copy(a.hash, a.hash+WIDTH, hash);
    return *this;
}

template<size_t WIDTH>
eh_trunc* TruncatedStepRow<WIDTH>::GetTruncatedIndices(size_t len, size_t lenIndices) const
{
    eh_trunc* p = new eh_trunc[lenIndices];
    std::copy(hash+len, hash+len+lenIndices, p);
    return p;
}

template<unsigned int N, unsigned int K>
std::set<std::vector<eh_index>> Equihash<N,K>::BasicSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled)
{
    eh_index init_size { 1 << (CollisionBitLength + 1) };

    // 1) Generate first list
    LogPrint("pow", "Generating first list\n");
    size_t hashLen = N/8;
    size_t lenIndices = sizeof(eh_index);
    std::vector<FullStepRow<FullWidth>> X;
    X.reserve(init_size);
    for (eh_index i = 0; i < init_size; i++) {
        X.emplace_back(N, base_state, i);
        // Slow down checking to prevent segfaults (??)
        if (i % 10000 == 0 && cancelled(ListGeneration)) throw solver_cancelled;
    }

    // 3) Repeat step 2 until 2n/(k+1) bits remain
    for (int r = 1; r < K && X.size() > 0; r++) {
        LogPrint("pow", "Round %d:\n", r);
        // 2a) Sort the list
        LogPrint("pow", "- Sorting list\n");
        std::sort(X.begin(), X.end(), CompareSR(CollisionByteLength));
        if (cancelled(ListSorting)) throw solver_cancelled;

        LogPrint("pow", "- Finding collisions\n");
        int i = 0;
        int posFree = 0;
        std::vector<FullStepRow<FullWidth>> Xc;
        while (i < X.size() - 1) {
            // 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
            int j = 1;
            while (i+j < X.size() &&
                    HasCollision(X[i], X[i+j], CollisionByteLength)) {
                j++;
            }

            // 2c) Calculate tuples (X_i ^ X_j, (i, j))
            for (int l = 0; l < j - 1; l++) {
                for (int m = l + 1; m < j; m++) {
                    if (DistinctIndices(X[i+l], X[i+m], hashLen, lenIndices)) {
                        Xc.emplace_back(X[i+l], X[i+m], hashLen, lenIndices, CollisionByteLength);
                    }
                }
            }

            // 2d) Store tuples on the table in-place if possible
            while (posFree < i+j && Xc.size() > 0) {
                X[posFree++] = Xc.back();
                Xc.pop_back();
            }

            i += j;
            if (cancelled(ListColliding)) throw solver_cancelled;
        }

        // 2e) Handle edge case where final table entry has no collision
        while (posFree < X.size() && Xc.size() > 0) {
            X[posFree++] = Xc.back();
            Xc.pop_back();
        }

        if (Xc.size() > 0) {
            // 2f) Add overflow to end of table
            X.insert(X.end(), Xc.begin(), Xc.end());
        } else if (posFree < X.size()) {
            // 2g) Remove empty space at the end
            X.erase(X.begin()+posFree, X.end());
            X.shrink_to_fit();
        }

        hashLen -= CollisionByteLength;
        lenIndices *= 2;
        if (cancelled(RoundEnd)) throw solver_cancelled;
    }

    // k+1) Find a collision on last 2n(k+1) bits
    LogPrint("pow", "Final round:\n");
    std::set<std::vector<eh_index>> solns;
    if (X.size() > 1) {
        LogPrint("pow", "- Sorting list\n");
        std::sort(X.begin(), X.end(), CompareSR(hashLen));
        if (cancelled(FinalSorting)) throw solver_cancelled;
        LogPrint("pow", "- Finding collisions\n");
        int i = 0;
        while (i < X.size() - 1) {
            int j = 1;
            while (i+j < X.size() &&
                    HasCollision(X[i], X[i+j], hashLen)) {
                j++;
            }

            for (int l = 0; l < j - 1; l++) {
                for (int m = l + 1; m < j; m++) {
                    FullStepRow<FinalFullWidth> res(X[i+l], X[i+m], hashLen, lenIndices, 0);
                    if (DistinctIndices(X[i+l], X[i+m], hashLen, lenIndices)) {
                        solns.insert(res.GetIndices(hashLen, 2*lenIndices));
                    }
                }
            }

            i += j;
            if (cancelled(FinalColliding)) throw solver_cancelled;
        }
    } else
        LogPrint("pow", "- List is empty\n");

    return solns;
}

template<size_t WIDTH>
void CollideBranches(std::vector<FullStepRow<WIDTH>>& X, const size_t hlen, const size_t lenIndices, const unsigned int clen, const unsigned int ilen, const eh_trunc lt, const eh_trunc rt)
{
    int i = 0;
    int posFree = 0;
    std::vector<FullStepRow<WIDTH>> Xc;
    while (i < X.size() - 1) {
        // 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
        int j = 1;
        while (i+j < X.size() &&
                HasCollision(X[i], X[i+j], clen)) {
            j++;
        }

        // 2c) Calculate tuples (X_i ^ X_j, (i, j))
        for (int l = 0; l < j - 1; l++) {
            for (int m = l + 1; m < j; m++) {
                if (DistinctIndices(X[i+l], X[i+m], hlen, lenIndices)) {
                    if (IsValidBranch(X[i+l], hlen, ilen, lt) && IsValidBranch(X[i+m], hlen, ilen, rt)) {
                        Xc.emplace_back(X[i+l], X[i+m], hlen, lenIndices, clen);
                    } else if (IsValidBranch(X[i+m], hlen, ilen, lt) && IsValidBranch(X[i+l], hlen, ilen, rt)) {
                        Xc.emplace_back(X[i+m], X[i+l], hlen, lenIndices, clen);
                    }
                }
            }
        }

        // 2d) Store tuples on the table in-place if possible
        while (posFree < i+j && Xc.size() > 0) {
            X[posFree++] = Xc.back();
            Xc.pop_back();
        }

        i += j;
    }

    // 2e) Handle edge case where final table entry has no collision
    while (posFree < X.size() && Xc.size() > 0) {
        X[posFree++] = Xc.back();
        Xc.pop_back();
    }

    if (Xc.size() > 0) {
        // 2f) Add overflow to end of table
        X.insert(X.end(), Xc.begin(), Xc.end());
    } else if (posFree < X.size()) {
        // 2g) Remove empty space at the end
        X.erase(X.begin()+posFree, X.end());
        X.shrink_to_fit();
    }
}

template<unsigned int N, unsigned int K>
std::set<std::vector<eh_index>> Equihash<N,K>::OptimisedSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled)
{
    eh_index init_size { 1 << (CollisionBitLength + 1) };

    // First run the algorithm with truncated indices

    eh_index soln_size { 1 << K };
    // Each element of partialSolns is dynamically allocated in a call to
    // GetTruncatedIndices(), and freed at the end of this function.
    std::vector<eh_trunc*> partialSolns;
    {

        // 1) Generate first list
        LogPrint("pow", "Generating first list\n");
        size_t hashLen = N/8;
        size_t lenIndices = sizeof(eh_trunc);
        std::vector<TruncatedStepRow<TruncatedWidth>> Xt;
        Xt.reserve(init_size);
        for (eh_index i = 0; i < init_size; i++) {
            Xt.emplace_back(N, base_state, i, CollisionBitLength + 1);
            // Slow down checking to prevent segfaults (??)
            if (i % 10000 == 0 && cancelled(ListGeneration)) throw solver_cancelled;
        }

        // 3) Repeat step 2 until 2n/(k+1) bits remain
        for (int r = 1; r < K && Xt.size() > 0; r++) {
            LogPrint("pow", "Round %d:\n", r);
            // 2a) Sort the list
            LogPrint("pow", "- Sorting list\n");
            std::sort(Xt.begin(), Xt.end(), CompareSR(CollisionByteLength));
            if (cancelled(ListSorting)) throw solver_cancelled;

            LogPrint("pow", "- Finding collisions\n");
            int i = 0;
            int posFree = 0;
            std::vector<TruncatedStepRow<TruncatedWidth>> Xc;
            while (i < Xt.size() - 1) {
                // 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
                int j = 1;
                while (i+j < Xt.size() &&
                        HasCollision(Xt[i], Xt[i+j], CollisionByteLength)) {
                    j++;
                }

                // 2c) Calculate tuples (X_i ^ X_j, (i, j))
                for (int l = 0; l < j - 1; l++) {
                    for (int m = l + 1; m < j; m++) {
                        // We truncated, so don't check for distinct indices here
                        Xc.emplace_back(Xt[i+l], Xt[i+m], hashLen, lenIndices, CollisionByteLength);
                    }
                }

                // 2d) Store tuples on the table in-place if possible
                while (posFree < i+j && Xc.size() > 0) {
                    Xt[posFree++] = Xc.back();
                    Xc.pop_back();
                }

                i += j;
                if (cancelled(ListColliding)) throw solver_cancelled;
            }

            // 2e) Handle edge case where final table entry has no collision
            while (posFree < Xt.size() && Xc.size() > 0) {
                Xt[posFree++] = Xc.back();
                Xc.pop_back();
            }

            if (Xc.size() > 0) {
                // 2f) Add overflow to end of table
                Xt.insert(Xt.end(), Xc.begin(), Xc.end());
            } else if (posFree < Xt.size()) {
                // 2g) Remove empty space at the end
                Xt.erase(Xt.begin()+posFree, Xt.end());
                Xt.shrink_to_fit();
            }

            hashLen -= CollisionByteLength;
            lenIndices *= 2;
            if (cancelled(RoundEnd)) throw solver_cancelled;
        }

        // k+1) Find a collision on last 2n(k+1) bits
        LogPrint("pow", "Final round:\n");
        if (Xt.size() > 1) {
            LogPrint("pow", "- Sorting list\n");
            std::sort(Xt.begin(), Xt.end(), CompareSR(hashLen));
            if (cancelled(FinalSorting)) throw solver_cancelled;
            LogPrint("pow", "- Finding collisions\n");
            int i = 0;
            while (i < Xt.size() - 1) {
                int j = 1;
                while (i+j < Xt.size() &&
                        HasCollision(Xt[i], Xt[i+j], hashLen)) {
                    j++;
                }

                for (int l = 0; l < j - 1; l++) {
                    for (int m = l + 1; m < j; m++) {
                        TruncatedStepRow<FinalTruncatedWidth> res(Xt[i+l], Xt[i+m], hashLen, lenIndices, 0);
                        partialSolns.push_back(res.GetTruncatedIndices(hashLen, 2*lenIndices));
                    }
                }

                i += j;
                if (cancelled(FinalColliding)) break;
            }
        } else
            LogPrint("pow", "- List is empty\n");

    } // Ensure Xt goes out of scope and is destroyed

    LogPrint("pow", "Found %d partial solutions\n", partialSolns.size());

    // Now for each solution run the algorithm again to recreate the indices
    LogPrint("pow", "Culling solutions\n");
    std::set<std::vector<eh_index>> solns;
    eh_index recreate_size { UntruncateIndex(1, 0, CollisionBitLength + 1) };
    int invalidCount = 0;
    if (cancelled(StartCulling)) goto cancelsolver;
    for (eh_trunc* partialSoln : partialSolns) {
        size_t hashLen;
        size_t lenIndices;
        std::vector<boost::optional<std::vector<FullStepRow<FinalFullWidth>>>> X;
        X.reserve(K+1);

        // 3) Repeat steps 1 and 2 for each partial index
        for (eh_index i = 0; i < soln_size; i++) {
            // 1) Generate first list of possibilities
            std::vector<FullStepRow<FinalFullWidth>> icv;
            icv.reserve(recreate_size);
            for (eh_index j = 0; j < recreate_size; j++) {
                eh_index newIndex { UntruncateIndex(partialSoln[i], j, CollisionBitLength + 1) };
                icv.emplace_back(N, base_state, newIndex);
                if (cancelled(PartialGeneration)) goto cancelsolver;
            }
            boost::optional<std::vector<FullStepRow<FinalFullWidth>>> ic = icv;

            // 2a) For each pair of lists:
            hashLen = N/8;
            lenIndices = sizeof(eh_index);
            size_t rti = i;
            for (size_t r = 0; r <= K; r++) {
                // 2b) Until we are at the top of a subtree:
                if (r < X.size()) {
                    if (X[r]) {
                        // 2c) Merge the lists
                        ic->reserve(ic->size() + X[r]->size());
                        ic->insert(ic->end(), X[r]->begin(), X[r]->end());
                        std::sort(ic->begin(), ic->end(), CompareSR(hashLen));
                        if (cancelled(PartialSorting)) goto cancelsolver;
                        size_t lti = rti-(1<<r);
                        CollideBranches(*ic, hashLen, lenIndices,
                                        CollisionByteLength,
                                        CollisionBitLength + 1,
                                        partialSoln[lti], partialSoln[rti]);

                        // 2d) Check if this has become an invalid solution
                        if (ic->size() == 0)
                            goto invalidsolution;

                        X[r] = boost::none;
                        hashLen -= CollisionByteLength;
                        lenIndices *= 2;
                        rti = lti;
                    } else {
                        X[r] = *ic;
                        break;
                    }
                } else {
                    X.push_back(ic);
                    break;
                }
                if (cancelled(PartialSubtreeEnd)) goto cancelsolver;
            }
            if (cancelled(PartialIndexEnd)) goto cancelsolver;
        }

        // We are at the top of the tree
        assert(X.size() == K+1);
        for (FullStepRow<FinalFullWidth> row : *X[K]) {
            solns.insert(row.GetIndices(hashLen, lenIndices));
        }
        if (cancelled(PartialEnd)) goto cancelsolver;
        continue;

invalidsolution:
        invalidCount++;
    }
    LogPrint("pow", "- Number of invalid solutions found: %d\n", invalidCount);

    for (eh_trunc* partialSoln : partialSolns) {
        delete[] partialSoln;
    }
    return solns;

cancelsolver:
    for (eh_trunc* partialSoln : partialSolns) {
        delete[] partialSoln;
    }
    throw solver_cancelled;
}

template<unsigned int N, unsigned int K>
bool Equihash<N,K>::IsValidSolution(const eh_HashState& base_state, std::vector<eh_index> soln)
{
    eh_index soln_size { 1u << K };
    if (soln.size() != soln_size) {
        LogPrint("pow", "Invalid solution size: %d\n", soln.size());
        return false;
    }

    std::vector<FullStepRow<FinalFullWidth>> X;
    X.reserve(soln_size);
    for (eh_index i : soln) {
        X.emplace_back(N, base_state, i);
    }

    size_t hashLen = N/8;
    size_t lenIndices = sizeof(eh_index);
    while (X.size() > 1) {
        std::vector<FullStepRow<FinalFullWidth>> Xc;
        for (int i = 0; i < X.size(); i += 2) {
            if (!HasCollision(X[i], X[i+1], CollisionByteLength)) {
                LogPrint("pow", "Invalid solution: invalid collision length between StepRows\n");
                LogPrint("pow", "X[i]   = %s\n", X[i].GetHex(hashLen));
                LogPrint("pow", "X[i+1] = %s\n", X[i+1].GetHex(hashLen));
                return false;
            }
            if (X[i+1].IndicesBefore(X[i], hashLen, lenIndices)) {
                return false;
                LogPrint("pow", "Invalid solution: Index tree incorrectly ordered\n");
            }
            if (!DistinctIndices(X[i], X[i+1], hashLen, lenIndices)) {
                LogPrint("pow", "Invalid solution: duplicate indices\n");
                return false;
            }
            Xc.emplace_back(X[i], X[i+1], hashLen, lenIndices, CollisionByteLength);
        }
        X = Xc;
        hashLen -= CollisionByteLength;
        lenIndices *= 2;
    }

    assert(X.size() == 1);
    return X[0].IsZero(hashLen);
}

// Explicit instantiations for Equihash<96,3>
template int Equihash<96,3>::InitialiseState(eh_HashState& base_state);
template std::set<std::vector<eh_index>> Equihash<96,3>::BasicSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
template std::set<std::vector<eh_index>> Equihash<96,3>::OptimisedSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
template bool Equihash<96,3>::IsValidSolution(const eh_HashState& base_state, std::vector<eh_index> soln);

// Explicit instantiations for Equihash<96,5>
template int Equihash<96,5>::InitialiseState(eh_HashState& base_state);
template std::set<std::vector<eh_index>> Equihash<96,5>::BasicSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
template std::set<std::vector<eh_index>> Equihash<96,5>::OptimisedSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
template bool Equihash<96,5>::IsValidSolution(const eh_HashState& base_state, std::vector<eh_index> soln);

// Explicit instantiations for Equihash<48,5>
template int Equihash<48,5>::InitialiseState(eh_HashState& base_state);
template std::set<std::vector<eh_index>> Equihash<48,5>::BasicSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
template std::set<std::vector<eh_index>> Equihash<48,5>::OptimisedSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
template bool Equihash<48,5>::IsValidSolution(const eh_HashState& base_state, std::vector<eh_index> soln);
Commit	Line	Data
	1	// Copyright (c) 2016 Jack Grigg
	2	// Copyright (c) 2016 The Zcash developers
	3	// Distributed under the MIT software license, see the accompanying
	4	// file COPYING or http://www.opensource.org/licenses/mit-license.php.
	5
	6	// Implementation of the Equihash Proof-of-Work algorithm.
	7	//
	8	// Reference
	9	// =========
	10	// Alex Biryukov and Dmitry Khovratovich
	11	// Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem
	12	// NDSS ’16, 21-24 February 2016, San Diego, CA, USA
	13	// https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf
	14
	15	#include "crypto/equihash.h"
	16	#include "util.h"
	17
	18	#include <algorithm>
	19	#include <iostream>
	20	#include <stdexcept>
	21
	22	#include <boost/optional.hpp>
	23
	24	EhSolverCancelledException solver_cancelled;
	25
	26	template<unsigned int N, unsigned int K>
	27	int Equihash<N,K>::InitialiseState(eh_HashState& base_state)
	28	{
	29	uint32_t le_N = htole32(N);
	30	uint32_t le_K = htole32(K);
	31	unsigned char personalization[crypto_generichash_blake2b_PERSONALBYTES] = {};
	32	memcpy(personalization, "ZcashPoW", 8);
	33	memcpy(personalization+8, &le_N, 4);
	34	memcpy(personalization+12, &le_K, 4);
	35	return crypto_generichash_blake2b_init_salt_personal(&base_state,
	36	NULL, 0, // No key.
	37	N/8,
	38	NULL, // No salt.
	39	personalization);
	40	}
	41
	42	// Big-endian so that lexicographic array comparison is equivalent to integer
	43	// comparison
	44	void EhIndexToArray(const eh_index i, unsigned char* array)
	45	{
	46	assert(sizeof(eh_index) == 4);
	47	eh_index bei = htobe32(i);
	48	memcpy(array, &bei, sizeof(eh_index));
	49	}
	50
	51	// Big-endian so that lexicographic array comparison is equivalent to integer
	52	// comparison
	53	eh_index ArrayToEhIndex(const unsigned char* array)
	54	{
	55	assert(sizeof(eh_index) == 4);
	56	eh_index bei;
	57	memcpy(&bei, array, sizeof(eh_index));
	58	return be32toh(bei);
	59	}
	60
	61	eh_trunc TruncateIndex(const eh_index i, const unsigned int ilen)
	62	{
	63	// Truncate to 8 bits
	64	assert(sizeof(eh_trunc) == 1);
	65	return (i >> (ilen - 8)) & 0xff;
	66	}
	67
	68	eh_index UntruncateIndex(const eh_trunc t, const eh_index r, const unsigned int ilen)
	69	{
	70	eh_index i{t};
	71	return (i << (ilen - 8)) \| r;
	72	}
	73
	74	template<size_t WIDTH>
	75	StepRow<WIDTH>::StepRow(unsigned int n, const eh_HashState& base_state, eh_index i)
	76	{
	77	eh_HashState state;
	78	state = base_state;
	79	unsigned char array[sizeof(eh_index)];
	80	eh_index lei = htole32(i);
	81	memcpy(array, &lei, sizeof(eh_index));
	82	crypto_generichash_blake2b_update(&state, array, sizeof(eh_index));
	83	crypto_generichash_blake2b_final(&state, hash, n/8);
	84	}
	85
	86	template<size_t WIDTH> template<size_t W>
	87	StepRow<WIDTH>::StepRow(const StepRow<W>& a)
	88	{
	89	assert(W <= WIDTH);
	90	std::copy(a.hash, a.hash+W, hash);
	91	}
	92
	93	template<size_t WIDTH>
	94	FullStepRow<WIDTH>::FullStepRow(unsigned int n, const eh_HashState& base_state, eh_index i) :
	95	StepRow<WIDTH> {n, base_state, i}
	96	{
	97	EhIndexToArray(i, hash+(n/8));
	98	}
	99
	100	template<size_t WIDTH> template<size_t W>
	101	FullStepRow<WIDTH>::FullStepRow(const FullStepRow<W>& a, const FullStepRow<W>& b, size_t len, size_t lenIndices, int trim) :
	102	StepRow<WIDTH> {a}
	103	{
	104	assert(len+lenIndices <= W);
	105	assert(len-trim+(2*lenIndices) <= WIDTH);
	106	for (int i = trim; i < len; i++)
	107	hash[i-trim] = a.hash[i] ^ b.hash[i];
	108	if (a.IndicesBefore(b, len, lenIndices)) {
	109	std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim);
	110	std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim+lenIndices);
	111	} else {
	112	std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim);
	113	std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim+lenIndices);
	114	}
	115	}
	116
	117	template<size_t WIDTH>
	118	FullStepRow<WIDTH>& FullStepRow<WIDTH>::operator=(const FullStepRow<WIDTH>& a)
	119	{
	120	std::copy(a.hash, a.hash+WIDTH, hash);
	121	return *this;
	122	}
	123
	124	template<size_t WIDTH>
	125	bool StepRow<WIDTH>::IsZero(size_t len)
	126	{
	127	// This doesn't need to be constant time.
	128	for (int i = 0; i < len; i++) {
	129	if (hash[i] != 0)
	130	return false;
	131	}
	132	return true;
	133	}
	134
	135	template<size_t WIDTH>
	136	std::vector<eh_index> FullStepRow<WIDTH>::GetIndices(size_t len, size_t lenIndices) const
	137	{
	138	std::vector<eh_index> ret;
	139	for (int i = 0; i < lenIndices; i += sizeof(eh_index)) {
	140	ret.push_back(ArrayToEhIndex(hash+len+i));
	141	}
	142	return ret;
	143	}
	144
	145	template<size_t WIDTH>
	146	bool HasCollision(StepRow<WIDTH>& a, StepRow<WIDTH>& b, int l)
	147	{
	148	// This doesn't need to be constant time.
	149	for (int j = 0; j < l; j++) {
	150	if (a.hash[j] != b.hash[j])
	151	return false;
	152	}
	153	return true;
	154	}
	155
	156	template<size_t WIDTH>
	157	TruncatedStepRow<WIDTH>::TruncatedStepRow(unsigned int n, const eh_HashState& base_state, eh_index i, unsigned int ilen) :
	158	StepRow<WIDTH> {n, base_state, i}
	159	{
	160	hash[n/8] = TruncateIndex(i, ilen);
	161	}
	162
	163	template<size_t WIDTH> template<size_t W>
	164	TruncatedStepRow<WIDTH>::TruncatedStepRow(const TruncatedStepRow<W>& a, const TruncatedStepRow<W>& b, size_t len, size_t lenIndices, int trim) :
	165	StepRow<WIDTH> {a}
	166	{
	167	assert(len+lenIndices <= W);
	168	assert(len-trim+(2*lenIndices) <= WIDTH);
	169	for (int i = trim; i < len; i++)
	170	hash[i-trim] = a.hash[i] ^ b.hash[i];
	171	if (a.IndicesBefore(b, len, lenIndices)) {
	172	std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim);
	173	std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim+lenIndices);
	174	} else {
	175	std::copy(b.hash+len, b.hash+len+lenIndices, hash+len-trim);
	176	std::copy(a.hash+len, a.hash+len+lenIndices, hash+len-trim+lenIndices);
	177	}
	178	}
	179
	180	template<size_t WIDTH>
	181	TruncatedStepRow<WIDTH>& TruncatedStepRow<WIDTH>::operator=(const TruncatedStepRow<WIDTH>& a)
	182	{
	183	std::copy(a.hash, a.hash+WIDTH, hash);
	184	return *this;
	185	}
	186
	187	template<size_t WIDTH>
	188	eh_trunc* TruncatedStepRow<WIDTH>::GetTruncatedIndices(size_t len, size_t lenIndices) const
	189	{
	190	eh_trunc* p = new eh_trunc[lenIndices];
	191	std::copy(hash+len, hash+len+lenIndices, p);
	192	return p;
	193	}
	194
	195	template<unsigned int N, unsigned int K>
	196	std::set<std::vector<eh_index>> Equihash<N,K>::BasicSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled)
	197	{
	198	eh_index init_size { 1 << (CollisionBitLength + 1) };
	199
	200	// 1) Generate first list
	201	LogPrint("pow", "Generating first list\n");
	202	size_t hashLen = N/8;
	203	size_t lenIndices = sizeof(eh_index);
	204	std::vector<FullStepRow<FullWidth>> X;
	205	X.reserve(init_size);
	206	for (eh_index i = 0; i < init_size; i++) {
	207	X.emplace_back(N, base_state, i);
	208	// Slow down checking to prevent segfaults (??)
	209	if (i % 10000 == 0 && cancelled(ListGeneration)) throw solver_cancelled;
	210	}
	211
	212	// 3) Repeat step 2 until 2n/(k+1) bits remain
	213	for (int r = 1; r < K && X.size() > 0; r++) {
	214	LogPrint("pow", "Round %d:\n", r);
	215	// 2a) Sort the list
	216	LogPrint("pow", "- Sorting list\n");
	217	std::sort(X.begin(), X.end(), CompareSR(CollisionByteLength));
	218	if (cancelled(ListSorting)) throw solver_cancelled;
	219
	220	LogPrint("pow", "- Finding collisions\n");
	221	int i = 0;
	222	int posFree = 0;
	223	std::vector<FullStepRow<FullWidth>> Xc;
	224	while (i < X.size() - 1) {
	225	// 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
	226	int j = 1;
	227	while (i+j < X.size() &&
	228	HasCollision(X[i], X[i+j], CollisionByteLength)) {
	229	j++;
	230	}
	231
	232	// 2c) Calculate tuples (X_i ^ X_j, (i, j))
	233	for (int l = 0; l < j - 1; l++) {
	234	for (int m = l + 1; m < j; m++) {
	235	if (DistinctIndices(X[i+l], X[i+m], hashLen, lenIndices)) {
	236	Xc.emplace_back(X[i+l], X[i+m], hashLen, lenIndices, CollisionByteLength);
	237	}
	238	}
	239	}
	240
	241	// 2d) Store tuples on the table in-place if possible
	242	while (posFree < i+j && Xc.size() > 0) {
	243	X[posFree++] = Xc.back();
	244	Xc.pop_back();
	245	}
	246
	247	i += j;
	248	if (cancelled(ListColliding)) throw solver_cancelled;
	249	}
	250
	251	// 2e) Handle edge case where final table entry has no collision
	252	while (posFree < X.size() && Xc.size() > 0) {
	253	X[posFree++] = Xc.back();
	254	Xc.pop_back();
	255	}
	256
	257	if (Xc.size() > 0) {
	258	// 2f) Add overflow to end of table
	259	X.insert(X.end(), Xc.begin(), Xc.end());
	260	} else if (posFree < X.size()) {
	261	// 2g) Remove empty space at the end
	262	X.erase(X.begin()+posFree, X.end());
	263	X.shrink_to_fit();
	264	}
	265
	266	hashLen -= CollisionByteLength;
	267	lenIndices *= 2;
	268	if (cancelled(RoundEnd)) throw solver_cancelled;
	269	}
	270
	271	// k+1) Find a collision on last 2n(k+1) bits
	272	LogPrint("pow", "Final round:\n");
	273	std::set<std::vector<eh_index>> solns;
	274	if (X.size() > 1) {
	275	LogPrint("pow", "- Sorting list\n");
	276	std::sort(X.begin(), X.end(), CompareSR(hashLen));
	277	if (cancelled(FinalSorting)) throw solver_cancelled;
	278	LogPrint("pow", "- Finding collisions\n");
	279	int i = 0;
	280	while (i < X.size() - 1) {
	281	int j = 1;
	282	while (i+j < X.size() &&
	283	HasCollision(X[i], X[i+j], hashLen)) {
	284	j++;
	285	}
	286
	287	for (int l = 0; l < j - 1; l++) {
	288	for (int m = l + 1; m < j; m++) {
	289	FullStepRow<FinalFullWidth> res(X[i+l], X[i+m], hashLen, lenIndices, 0);
	290	if (DistinctIndices(X[i+l], X[i+m], hashLen, lenIndices)) {
	291	solns.insert(res.GetIndices(hashLen, 2*lenIndices));
	292	}
	293	}
	294	}
	295
	296	i += j;
	297	if (cancelled(FinalColliding)) throw solver_cancelled;
	298	}
	299	} else
	300	LogPrint("pow", "- List is empty\n");
	301
	302	return solns;
	303	}
	304
	305	template<size_t WIDTH>
	306	void CollideBranches(std::vector<FullStepRow<WIDTH>>& X, const size_t hlen, const size_t lenIndices, const unsigned int clen, const unsigned int ilen, const eh_trunc lt, const eh_trunc rt)
	307	{
	308	int i = 0;
	309	int posFree = 0;
	310	std::vector<FullStepRow<WIDTH>> Xc;
	311	while (i < X.size() - 1) {
	312	// 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
	313	int j = 1;
	314	while (i+j < X.size() &&
	315	HasCollision(X[i], X[i+j], clen)) {
	316	j++;
	317	}
	318
	319	// 2c) Calculate tuples (X_i ^ X_j, (i, j))
	320	for (int l = 0; l < j - 1; l++) {
	321	for (int m = l + 1; m < j; m++) {
	322	if (DistinctIndices(X[i+l], X[i+m], hlen, lenIndices)) {
	323	if (IsValidBranch(X[i+l], hlen, ilen, lt) && IsValidBranch(X[i+m], hlen, ilen, rt)) {
	324	Xc.emplace_back(X[i+l], X[i+m], hlen, lenIndices, clen);
	325	} else if (IsValidBranch(X[i+m], hlen, ilen, lt) && IsValidBranch(X[i+l], hlen, ilen, rt)) {
	326	Xc.emplace_back(X[i+m], X[i+l], hlen, lenIndices, clen);
	327	}
	328	}
	329	}
	330	}
	331
	332	// 2d) Store tuples on the table in-place if possible
	333	while (posFree < i+j && Xc.size() > 0) {
	334	X[posFree++] = Xc.back();
	335	Xc.pop_back();
	336	}
	337
	338	i += j;
	339	}
	340
	341	// 2e) Handle edge case where final table entry has no collision
	342	while (posFree < X.size() && Xc.size() > 0) {
	343	X[posFree++] = Xc.back();
	344	Xc.pop_back();
	345	}
	346
	347	if (Xc.size() > 0) {
	348	// 2f) Add overflow to end of table
	349	X.insert(X.end(), Xc.begin(), Xc.end());
	350	} else if (posFree < X.size()) {
	351	// 2g) Remove empty space at the end
	352	X.erase(X.begin()+posFree, X.end());
	353	X.shrink_to_fit();
	354	}
	355	}
	356
	357	template<unsigned int N, unsigned int K>
	358	std::set<std::vector<eh_index>> Equihash<N,K>::OptimisedSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled)
	359	{
	360	eh_index init_size { 1 << (CollisionBitLength + 1) };
	361
	362	// First run the algorithm with truncated indices
	363
	364	eh_index soln_size { 1 << K };
	365	// Each element of partialSolns is dynamically allocated in a call to
	366	// GetTruncatedIndices(), and freed at the end of this function.
	367	std::vector<eh_trunc*> partialSolns;
	368	{
	369
	370	// 1) Generate first list
	371	LogPrint("pow", "Generating first list\n");
	372	size_t hashLen = N/8;
	373	size_t lenIndices = sizeof(eh_trunc);
	374	std::vector<TruncatedStepRow<TruncatedWidth>> Xt;
	375	Xt.reserve(init_size);
	376	for (eh_index i = 0; i < init_size; i++) {
	377	Xt.emplace_back(N, base_state, i, CollisionBitLength + 1);
	378	// Slow down checking to prevent segfaults (??)
	379	if (i % 10000 == 0 && cancelled(ListGeneration)) throw solver_cancelled;
	380	}
	381
	382	// 3) Repeat step 2 until 2n/(k+1) bits remain
	383	for (int r = 1; r < K && Xt.size() > 0; r++) {
	384	LogPrint("pow", "Round %d:\n", r);
	385	// 2a) Sort the list
	386	LogPrint("pow", "- Sorting list\n");
	387	std::sort(Xt.begin(), Xt.end(), CompareSR(CollisionByteLength));
	388	if (cancelled(ListSorting)) throw solver_cancelled;
	389
	390	LogPrint("pow", "- Finding collisions\n");
	391	int i = 0;
	392	int posFree = 0;
	393	std::vector<TruncatedStepRow<TruncatedWidth>> Xc;
	394	while (i < Xt.size() - 1) {
	395	// 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits
	396	int j = 1;
	397	while (i+j < Xt.size() &&
	398	HasCollision(Xt[i], Xt[i+j], CollisionByteLength)) {
	399	j++;
	400	}
	401
	402	// 2c) Calculate tuples (X_i ^ X_j, (i, j))
	403	for (int l = 0; l < j - 1; l++) {
	404	for (int m = l + 1; m < j; m++) {
	405	// We truncated, so don't check for distinct indices here
	406	Xc.emplace_back(Xt[i+l], Xt[i+m], hashLen, lenIndices, CollisionByteLength);
	407	}
	408	}
	409
	410	// 2d) Store tuples on the table in-place if possible
	411	while (posFree < i+j && Xc.size() > 0) {
	412	Xt[posFree++] = Xc.back();
	413	Xc.pop_back();
	414	}
	415
	416	i += j;
	417	if (cancelled(ListColliding)) throw solver_cancelled;
	418	}
	419
	420	// 2e) Handle edge case where final table entry has no collision
	421	while (posFree < Xt.size() && Xc.size() > 0) {
	422	Xt[posFree++] = Xc.back();
	423	Xc.pop_back();
	424	}
	425
	426	if (Xc.size() > 0) {
	427	// 2f) Add overflow to end of table
	428	Xt.insert(Xt.end(), Xc.begin(), Xc.end());
	429	} else if (posFree < Xt.size()) {
	430	// 2g) Remove empty space at the end
	431	Xt.erase(Xt.begin()+posFree, Xt.end());
	432	Xt.shrink_to_fit();
	433	}
	434
	435	hashLen -= CollisionByteLength;
	436	lenIndices *= 2;
	437	if (cancelled(RoundEnd)) throw solver_cancelled;
	438	}
	439
	440	// k+1) Find a collision on last 2n(k+1) bits
	441	LogPrint("pow", "Final round:\n");
	442	if (Xt.size() > 1) {
	443	LogPrint("pow", "- Sorting list\n");
	444	std::sort(Xt.begin(), Xt.end(), CompareSR(hashLen));
	445	if (cancelled(FinalSorting)) throw solver_cancelled;
	446	LogPrint("pow", "- Finding collisions\n");
	447	int i = 0;
	448	while (i < Xt.size() - 1) {
	449	int j = 1;
	450	while (i+j < Xt.size() &&
	451	HasCollision(Xt[i], Xt[i+j], hashLen)) {
	452	j++;
	453	}
	454
	455	for (int l = 0; l < j - 1; l++) {
	456	for (int m = l + 1; m < j; m++) {
	457	TruncatedStepRow<FinalTruncatedWidth> res(Xt[i+l], Xt[i+m], hashLen, lenIndices, 0);
	458	partialSolns.push_back(res.GetTruncatedIndices(hashLen, 2*lenIndices));
	459	}
	460	}
	461
	462	i += j;
	463	if (cancelled(FinalColliding)) break;
	464	}
	465	} else
	466	LogPrint("pow", "- List is empty\n");
	467
	468	} // Ensure Xt goes out of scope and is destroyed
	469
	470	LogPrint("pow", "Found %d partial solutions\n", partialSolns.size());
	471
	472	// Now for each solution run the algorithm again to recreate the indices
	473	LogPrint("pow", "Culling solutions\n");
	474	std::set<std::vector<eh_index>> solns;
	475	eh_index recreate_size { UntruncateIndex(1, 0, CollisionBitLength + 1) };
	476	int invalidCount = 0;
	477	if (cancelled(StartCulling)) goto cancelsolver;
	478	for (eh_trunc* partialSoln : partialSolns) {
	479	size_t hashLen;
	480	size_t lenIndices;
	481	std::vector<boost::optional<std::vector<FullStepRow<FinalFullWidth>>>> X;
	482	X.reserve(K+1);
	483
	484	// 3) Repeat steps 1 and 2 for each partial index
	485	for (eh_index i = 0; i < soln_size; i++) {
	486	// 1) Generate first list of possibilities
	487	std::vector<FullStepRow<FinalFullWidth>> icv;
	488	icv.reserve(recreate_size);
	489	for (eh_index j = 0; j < recreate_size; j++) {
	490	eh_index newIndex { UntruncateIndex(partialSoln[i], j, CollisionBitLength + 1) };
	491	icv.emplace_back(N, base_state, newIndex);
	492	if (cancelled(PartialGeneration)) goto cancelsolver;
	493	}
	494	boost::optional<std::vector<FullStepRow<FinalFullWidth>>> ic = icv;
	495
	496	// 2a) For each pair of lists:
	497	hashLen = N/8;
	498	lenIndices = sizeof(eh_index);
	499	size_t rti = i;
	500	for (size_t r = 0; r <= K; r++) {
	501	// 2b) Until we are at the top of a subtree:
	502	if (r < X.size()) {
	503	if (X[r]) {
	504	// 2c) Merge the lists
	505	ic->reserve(ic->size() + X[r]->size());
	506	ic->insert(ic->end(), X[r]->begin(), X[r]->end());
	507	std::sort(ic->begin(), ic->end(), CompareSR(hashLen));
	508	if (cancelled(PartialSorting)) goto cancelsolver;
	509	size_t lti = rti-(1<<r);
	510	CollideBranches(*ic, hashLen, lenIndices,
	511	CollisionByteLength,
	512	CollisionBitLength + 1,
	513	partialSoln[lti], partialSoln[rti]);
	514
	515	// 2d) Check if this has become an invalid solution
	516	if (ic->size() == 0)
	517	goto invalidsolution;
	518
	519	X[r] = boost::none;
	520	hashLen -= CollisionByteLength;
	521	lenIndices *= 2;
	522	rti = lti;
	523	} else {
	524	X[r] = *ic;
	525	break;
	526	}
	527	} else {
	528	X.push_back(ic);
	529	break;
	530	}
	531	if (cancelled(PartialSubtreeEnd)) goto cancelsolver;
	532	}
	533	if (cancelled(PartialIndexEnd)) goto cancelsolver;
	534	}
	535
	536	// We are at the top of the tree
	537	assert(X.size() == K+1);
	538	for (FullStepRow<FinalFullWidth> row : *X[K]) {
	539	solns.insert(row.GetIndices(hashLen, lenIndices));
	540	}
	541	if (cancelled(PartialEnd)) goto cancelsolver;
	542	continue;
	543
	544	invalidsolution:
	545	invalidCount++;
	546	}
	547	LogPrint("pow", "- Number of invalid solutions found: %d\n", invalidCount);
	548
	549	for (eh_trunc* partialSoln : partialSolns) {
	550	delete[] partialSoln;
	551	}
	552	return solns;
	553
	554	cancelsolver:
	555	for (eh_trunc* partialSoln : partialSolns) {
	556	delete[] partialSoln;
	557	}
	558	throw solver_cancelled;
	559	}
	560
	561	template<unsigned int N, unsigned int K>
	562	bool Equihash<N,K>::IsValidSolution(const eh_HashState& base_state, std::vector<eh_index> soln)
	563	{
	564	eh_index soln_size { 1u << K };
	565	if (soln.size() != soln_size) {
	566	LogPrint("pow", "Invalid solution size: %d\n", soln.size());
	567	return false;
	568	}
	569
	570	std::vector<FullStepRow<FinalFullWidth>> X;
	571	X.reserve(soln_size);
	572	for (eh_index i : soln) {
	573	X.emplace_back(N, base_state, i);
	574	}
	575
	576	size_t hashLen = N/8;
	577	size_t lenIndices = sizeof(eh_index);
	578	while (X.size() > 1) {
	579	std::vector<FullStepRow<FinalFullWidth>> Xc;
	580	for (int i = 0; i < X.size(); i += 2) {
	581	if (!HasCollision(X[i], X[i+1], CollisionByteLength)) {
	582	LogPrint("pow", "Invalid solution: invalid collision length between StepRows\n");
	583	LogPrint("pow", "X[i] = %s\n", X[i].GetHex(hashLen));
	584	LogPrint("pow", "X[i+1] = %s\n", X[i+1].GetHex(hashLen));
	585	return false;
	586	}
	587	if (X[i+1].IndicesBefore(X[i], hashLen, lenIndices)) {
	588	return false;
	589	LogPrint("pow", "Invalid solution: Index tree incorrectly ordered\n");
	590	}
	591	if (!DistinctIndices(X[i], X[i+1], hashLen, lenIndices)) {
	592	LogPrint("pow", "Invalid solution: duplicate indices\n");
	593	return false;
	594	}
	595	Xc.emplace_back(X[i], X[i+1], hashLen, lenIndices, CollisionByteLength);
	596	}
	597	X = Xc;
	598	hashLen -= CollisionByteLength;
	599	lenIndices *= 2;
	600	}
	601
	602	assert(X.size() == 1);
	603	return X[0].IsZero(hashLen);
	604	}
	605
	606	// Explicit instantiations for Equihash<96,3>
	607	template int Equihash<96,3>::InitialiseState(eh_HashState& base_state);
	608	template std::set<std::vector<eh_index>> Equihash<96,3>::BasicSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
	609	template std::set<std::vector<eh_index>> Equihash<96,3>::OptimisedSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
	610	template bool Equihash<96,3>::IsValidSolution(const eh_HashState& base_state, std::vector<eh_index> soln);
	611
	612	// Explicit instantiations for Equihash<96,5>
	613	template int Equihash<96,5>::InitialiseState(eh_HashState& base_state);
	614	template std::set<std::vector<eh_index>> Equihash<96,5>::BasicSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
	615	template std::set<std::vector<eh_index>> Equihash<96,5>::OptimisedSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
	616	template bool Equihash<96,5>::IsValidSolution(const eh_HashState& base_state, std::vector<eh_index> soln);
	617
	618	// Explicit instantiations for Equihash<48,5>
	619	template int Equihash<48,5>::InitialiseState(eh_HashState& base_state);
	620	template std::set<std::vector<eh_index>> Equihash<48,5>::BasicSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
	621	template std::set<std::vector<eh_index>> Equihash<48,5>::OptimisedSolve(const eh_HashState& base_state, const std::function<bool(EhSolverCancelCheck)> cancelled);
	622	template bool Equihash<48,5>::IsValidSolution(const eh_HashState& base_state, std::vector<eh_index> soln);