Store truncated indices in the same char* as the hash (H/T tromp for the idea!)

[VerusCoin.git] / 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>

void validate_params(int n, int k)
{
    if (k>=n) {
        std::cerr << "n must be larger than k\n";
        throw invalid_params();
    }
    if (n % 8 != 0) {
        std::cerr << "Parameters must satisfy n = 0 mod 8\n";
        throw invalid_params();
    }
    if ((n/(k+1)) % 8 != 0) {
        std::cerr << "Parameters must satisfy n/(k+1) = 0 mod 8\n";
        throw invalid_params();
    }
}

int Equihash::InitialiseState(eh_HashState& base_state)
{
    unsigned char personalization[crypto_generichash_blake2b_PERSONALBYTES] = {};
    memcpy(personalization, "ZcashPOW", 8);
    memcpy(personalization+8,  &n, 4);
    memcpy(personalization+12, &k, 4);
    return crypto_generichash_blake2b_init_salt_personal(&base_state,
                                                         NULL, 0, // No key.
                                                         n/8,
                                                         NULL,    // No salt.
                                                         personalization);
}

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

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

StepRow::StepRow(unsigned int n, const eh_HashState& base_state, eh_index i) :
        hash {new unsigned char[n/8]},
        len {n/8}
{
    eh_HashState state;
    state = base_state;
    crypto_generichash_blake2b_update(&state, (unsigned char*) &i, sizeof(eh_index));
    crypto_generichash_blake2b_final(&state, hash, n/8);
}

StepRow::~StepRow()
{
    delete[] hash;
}

StepRow::StepRow(const StepRow& a) :
        hash {new unsigned char[a.len]},
        len {a.len}
{
    std::copy(a.hash, a.hash+a.len, hash);
}

FullStepRow::FullStepRow(unsigned int n, const eh_HashState& base_state, eh_index i) :
        StepRow {n, base_state, i},
        indices {i}
{
    assert(indices.size() == 1);
}

FullStepRow& FullStepRow::operator=(const FullStepRow& a)
{
    unsigned char* p = new unsigned char[a.len];
    std::copy(a.hash, a.hash+a.len, p);
    delete[] hash;
    hash = p;
    len = a.len;
    indices = a.indices;
    return *this;
}

FullStepRow& FullStepRow::operator^=(const FullStepRow& a)
{
    if (a.len != len) {
        throw std::invalid_argument("Hash length differs");
    }
    if (a.indices.size() != indices.size()) {
        throw std::invalid_argument("Number of indices differs");
    }
    unsigned char* p = new unsigned char[len];
    for (int i = 0; i < len; i++)
        p[i] = hash[i] ^ a.hash[i];
    delete[] hash;
    hash = p;
    indices.reserve(indices.size() + a.indices.size());
    indices.insert(indices.end(), a.indices.begin(), a.indices.end());
    return *this;
}

void FullStepRow::TrimHash(int l)
{
    unsigned char* p = new unsigned char[len-l];
    std::copy(hash+l, hash+len, p);
    delete[] hash;
    hash = p;
    len -= l;
}

bool StepRow::IsZero()
{
    char res = 0;
    for (int i = 0; i < len; i++)
        res |= hash[i];
    return res == 0;
}

bool HasCollision(StepRow& a, StepRow& b, int l)
{
    bool res = true;
    for (int j = 0; j < l; j++)
        res &= a.hash[j] == b.hash[j];
    return res;
}

// Checks if the intersection of a.indices and b.indices is empty
bool DistinctIndices(const FullStepRow& a, const FullStepRow& b)
{
    std::vector<eh_index> aSrt(a.indices);
    std::vector<eh_index> bSrt(b.indices);

    std::sort(aSrt.begin(), aSrt.end());
    std::sort(bSrt.begin(), bSrt.end());

    unsigned int i = 0;
    for (unsigned int j = 0; j < bSrt.size(); j++) {
        while (aSrt[i] < bSrt[j]) {
            i++;
            if (i == aSrt.size()) { return true; }
        }
        assert(aSrt[i] >= bSrt[j]);
        if (aSrt[i] == bSrt[j]) { return false; }
    }
    return true;
}

bool IsValidBranch(const FullStepRow& a, const unsigned int ilen, const eh_trunc t)
{
    return TruncateIndex(a.indices[0], ilen) == t;
}

TruncatedStepRow::TruncatedStepRow(unsigned int n, const eh_HashState& base_state, eh_index i, unsigned int ilen) :
        StepRow {n, base_state, i},
        lenIndices {1}
{
    unsigned char* p = new unsigned char[len+lenIndices];
    std::copy(hash, hash+len, p);
    p[len] = TruncateIndex(i, ilen);
    delete[] hash;
    hash = p;
}

TruncatedStepRow::TruncatedStepRow(const TruncatedStepRow& a) :
        StepRow {a},
        lenIndices {a.lenIndices}
{
    unsigned char* p = new unsigned char[a.len+a.lenIndices];
    std::copy(a.hash, a.hash+a.len+a.lenIndices, p);
    delete[] hash;
    hash = p;
}

TruncatedStepRow& TruncatedStepRow::operator=(const TruncatedStepRow& a)
{
    unsigned char* p = new unsigned char[a.len+a.lenIndices];
    std::copy(a.hash, a.hash+a.len+a.lenIndices, p);
    delete[] hash;
    hash = p;
    len = a.len;
    lenIndices = a.lenIndices;
    return *this;
}

TruncatedStepRow& TruncatedStepRow::operator^=(const TruncatedStepRow& a)
{
    if (a.len != len) {
        throw std::invalid_argument("Hash length differs");
    }
    if (a.lenIndices != lenIndices) {
        throw std::invalid_argument("Number of indices differs");
    }
    unsigned char* p = new unsigned char[len+lenIndices+a.lenIndices];
    for (int i = 0; i < len; i++)
        p[i] = hash[i] ^ a.hash[i];
    std::copy(hash+len, hash+len+lenIndices, p+len);
    std::copy(a.hash+a.len, a.hash+a.len+a.lenIndices, p+len+lenIndices);
    delete[] hash;
    hash = p;
    lenIndices += a.lenIndices;
    return *this;
}

void TruncatedStepRow::TrimHash(int l)
{
    unsigned char* p = new unsigned char[len-l+lenIndices];
    std::copy(hash+l, hash+len+lenIndices, p);
    delete[] hash;
    hash = p;
    len -= l;
}

eh_trunc* TruncatedStepRow::GetPartialSolution(eh_index soln_size) const
{
    assert(lenIndices == soln_size);
    eh_trunc* p = new eh_trunc[lenIndices];
    std::copy(hash+len, hash+len+lenIndices, p);
    return p;
}

Equihash::Equihash(unsigned int n, unsigned int k) :
        n(n), k(k)
{
    validate_params(n, k);
}

std::set<std::vector<eh_index>> Equihash::BasicSolve(const eh_HashState& base_state)
{
    assert(CollisionBitLength() + 1 < 8*sizeof(eh_index));
    eh_index init_size { 1 << (CollisionBitLength() + 1) };

    // 1) Generate first list
    LogPrint("pow", "Generating first list\n");
    std::vector<FullStepRow> X;
    X.reserve(init_size);
    for (eh_index i = 0; i < init_size; i++) {
        X.emplace_back(n, base_state, i);
    }

    // 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());

        LogPrint("pow", "- Finding collisions\n");
        int i = 0;
        int posFree = 0;
        std::vector<FullStepRow> 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])) {
                        Xc.push_back(X[i+l] ^ X[i+m]);
                        Xc.back().TrimHash(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;
        }

        // 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();
        }
    }

    // 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());
        LogPrint("pow", "- Finding collisions\n");
        for (int i = 0; i < X.size() - 1; i++) {
            FullStepRow res = X[i] ^ X[i+1];
            if (res.IsZero() && DistinctIndices(X[i], X[i+1])) {
                solns.insert(res.GetSolution());
            }
        }
    } else
        LogPrint("pow", "- List is empty\n");

    return solns;
}

void CollideBranches(std::vector<FullStepRow>& X, 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> 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])) {
                    if (IsValidBranch(X[i+l], ilen, lt) && IsValidBranch(X[i+m], ilen, rt)) {
                        Xc.push_back(X[i+l] ^ X[i+m]);
                        Xc.back().TrimHash(clen);
                    } else if (IsValidBranch(X[i+m], ilen, lt) && IsValidBranch(X[i+l], ilen, rt)) {
                        Xc.push_back(X[i+m] ^ X[i+l]);
                        Xc.back().TrimHash(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();
    }
}

std::set<std::vector<eh_index>> Equihash::OptimisedSolve(const eh_HashState& base_state)
{
    assert(CollisionBitLength() + 1 < 8*sizeof(eh_index));
    eh_index init_size { 1 << (CollisionBitLength() + 1) };

    // First run the algorithm with truncated indices

    eh_index soln_size { 1 << k };
    std::vector<eh_trunc*> partialSolns;
    {

        // 1) Generate first list
        LogPrint("pow", "Generating first list\n");
        std::vector<TruncatedStepRow> Xt;
        Xt.reserve(init_size);
        for (eh_index i = 0; i < init_size; i++) {
            Xt.emplace_back(n, base_state, i, CollisionBitLength() + 1);
        }

        // 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());

            LogPrint("pow", "- Finding collisions\n");
            int i = 0;
            int posFree = 0;
            std::vector<TruncatedStepRow> 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.push_back(Xt[i+l] ^ Xt[i+m]);
                        Xc.back().TrimHash(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;
            }

            // 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();
            }
        }

        // 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());
            LogPrint("pow", "- Finding collisions\n");
            for (int i = 0; i < Xt.size() - 1; i++) {
                TruncatedStepRow res = Xt[i] ^ Xt[i+1];
                if (res.IsZero()) {
                    partialSolns.push_back(res.GetPartialSolution(soln_size));
                }
            }
        } 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;
    for (eh_trunc* partialSoln : partialSolns) {
        // 1) Generate first list of possibilities
        std::vector<std::vector<FullStepRow>> X;
        X.reserve(soln_size);
        for (eh_index i = 0; i < soln_size; i++) {
            std::vector<FullStepRow> ic;
            ic.reserve(recreate_size);
            for (eh_index j = 0; j < recreate_size; j++) {
                eh_index newIndex { UntruncateIndex(partialSoln[i], j, CollisionBitLength() + 1) };
                ic.emplace_back(n, base_state, newIndex);
            }
            X.push_back(ic);
        }

        // 3) Repeat step 2 for each level of the tree
        for (int r = 0; X.size() > 1; r++) {
            std::vector<std::vector<FullStepRow>> Xc;
            Xc.reserve(X.size()/2);

            // 2a) For each pair of lists:
            for (int v = 0; v < X.size(); v += 2) {
                // 2b) Merge the lists
                std::vector<FullStepRow> ic(X[v]);
                ic.reserve(X[v].size() + X[v+1].size());
                ic.insert(ic.end(), X[v+1].begin(), X[v+1].end());
                std::sort(ic.begin(), ic.end());
                CollideBranches(ic, CollisionByteLength(), CollisionBitLength() + 1, partialSoln[(1<<r)*v], partialSoln[(1<<r)*(v+1)]);

                // 2v) Check if this has become an invalid solution
                if (ic.size() == 0)
                    goto invalidsolution;

                Xc.push_back(ic);
            }

            X = Xc;
        }

        // We are at the top of the tree
        assert(X.size() == 1);
        for (FullStepRow row : X[0]) {
            solns.insert(row.GetSolution());
        }
        goto deletesolution;

invalidsolution:
        invalidCount++;

deletesolution:
        delete[] partialSoln;
    }
    LogPrint("pow", "- Number of invalid solutions found: %d\n", invalidCount);

    return solns;
}

bool Equihash::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> X;
    X.reserve(soln_size);
    for (eh_index i : soln) {
        X.emplace_back(n, base_state, i);
    }

    while (X.size() > 1) {
        std::vector<FullStepRow> 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());
                LogPrint("pow", "X[i+1] = %s\n", X[i+1].GetHex());
                return false;
            }
            if (X[i+1].IndicesBefore(X[i])) {
                return false;
                LogPrint("pow", "Invalid solution: Index tree incorrectly ordered\n");
            }
            if (!DistinctIndices(X[i], X[i+1])) {
                LogPrint("pow", "Invalid solution: duplicate indices\n");
                return false;
            }
            Xc.push_back(X[i] ^ X[i+1]);
            Xc.back().TrimHash(CollisionByteLength());
        }
        X = Xc;
    }

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