PRSONA/prsona/src/server.cpp

#include <iostream>

#include "server.hpp"

/********************
 * PUBLIC FUNCTIONS *
 ********************/

/*
 * CONSTRUCTORS
 */

// Used to generate the first server; instantiates BGN for the first time
PrsonaServer::PrsonaServer(size_t numServers)
: numServers(numServers)
{
    currentSeed.set_random();
}

// Used for all other servers, so they have the same BGN parameters
PrsonaServer::PrsonaServer(size_t numServers, const BGN& otherBgn)
: numServers(numServers), bgnSystem(otherBgn)
{
    currentSeed.set_random();
}

/*
 * BASIC PUBLIC SYSTEM INFO GETTERS
 */

BGNPublicKey PrsonaServer::get_bgn_public_key() const
{
    return bgnSystem.get_public_key();
}

size_t PrsonaServer::get_num_clients() const
{
    return currentPseudonyms.size();
}

size_t PrsonaServer::get_num_servers() const
{
    return numServers;
}

/*
 * FRESH GENERATOR CALCULATION
 */

// To calculate the current epoch's generator, start from the base generator,
// then have every server call this function on it iteratively (in any order).
Curvepoint PrsonaServer::add_curr_seed_to_generator(
    std::vector<Proof>& pi,
    const Curvepoint& currGenerator) const
{
    pi.push_back(add_to_generator_proof(currGenerator, currentSeed));

    return currGenerator * currentSeed;
}

// To calculate the next epoch's generator, start from the base generator,
// then have every server call this function on it iteratively (in any order).
Curvepoint PrsonaServer::add_next_seed_to_generator(
    std::vector<Proof>& pi,
    const Curvepoint& currGenerator) const
{
    pi.push_back(add_to_generator_proof(currGenerator, nextSeed));

    return currGenerator * nextSeed;
}

/*
 * ENCRYPTED DATA GETTERS
 */

/* Call this in order to get the current encrypted votes cast by a given user
 * (who is identified by their short term public key).
 * In practice, this is intended for clients,
 * who need to know their current votes in order to rerandomize them. */
std::vector<CurveBipoint> PrsonaServer::get_current_votes_by(
    Proof& pi, const Curvepoint& shortTermPublicKey) const
{
    std::vector<CurveBipoint> retval;
    size_t voteSubmitter = binary_search(shortTermPublicKey);
    retval = voteMatrix[voteSubmitter];

    pi = generate_valid_vote_row_proof(retval);
    return retval;
}

std::vector<std::vector<CurveBipoint>> PrsonaServer::get_all_current_votes(
    Proof& pi) const
{
    pi = generate_valid_vote_matrix_proof(voteMatrix);
    return voteMatrix;
}

/* Call this in order to get the current encrypted tally of a given user
 * (who is identified by their short term public key).
 * In practice, this is intended for clients, so that the servers vouch
 * for their ciphertexts being valid as part of their reputation proofs. */
EGCiphertext PrsonaServer::get_current_user_encrypted_tally(
    Proof& pi, const Curvepoint& shortTermPublicKey) const
{
    EGCiphertext retval;
    size_t tallyOwner = binary_search(shortTermPublicKey);
    retval = currentUserEncryptedTallies[tallyOwner];
    
    pi = generate_valid_user_tally_proof(retval);
    return retval;
}

TwistBipoint PrsonaServer::get_current_server_encrypted_tally(
    Proof& pi, const Curvepoint& shortTermPublicKey) const
{
    TwistBipoint retval;
    size_t tallyOwner = binary_search(shortTermPublicKey);
    retval = previousVoteTallies[tallyOwner];
    
    pi = generate_valid_server_tally_proof(retval);
    return retval;
}

std::vector<Curvepoint> PrsonaServer::get_current_pseudonyms(Proof& pi) const
{    
    pi = generate_valid_pseudonyms_proof(currentPseudonyms);
    return currentPseudonyms;
}

/*
 * PROOF COMMITMENT GETTERS
 */

Proof PrsonaServer::get_vote_row_commitment(const Curvepoint& request) const
{
    size_t requestID = binary_search(request);
    return generate_valid_vote_row_proof(voteMatrix[requestID]);
}

Proof PrsonaServer::get_vote_matrix_commitment() const
{
    return generate_valid_vote_matrix_proof(voteMatrix);
}

Proof PrsonaServer::get_user_tally_commitment(const Curvepoint& request) const
{
    size_t requestID = binary_search(request);
    return generate_valid_user_tally_proof(currentUserEncryptedTallies[requestID]);
}

Proof PrsonaServer::get_server_tally_commitment(const Curvepoint& request) const
{
    size_t requestID = binary_search(request);
    return generate_valid_server_tally_proof(previousVoteTallies[requestID]);
}

Proof PrsonaServer::get_pseudonyms_commitment() const
{
    return generate_valid_pseudonyms_proof(currentPseudonyms);
}

/*
 * CLIENT INTERACTIONS
 */

/* Add a new client (who is identified only by their short term public key)
 * One server will do this, then ask all other servers to import their
 * (proven) exported data. */
void PrsonaServer::add_new_client(
    std::vector<Proof>& proofOfValidAddition,
    const Proof& proofOfValidKey,
    const Curvepoint& shortTermPublicKey)
{
    if (!verify_ownership_proof(
            proofOfValidKey, currentFreshGenerator, shortTermPublicKey))
    {
        std::cerr << "Could not verify proof of valid key." << std::endl;
        return;
    }

    currentPseudonyms.push_back(shortTermPublicKey);

    // The first epoch's score for a new user will be low,
    // but will typically converge on an average score quickly
    Scalar tallySeed;
    TwistBipoint encryptedDefaultTally =
        bgnSystem.get_public_key().twistEncrypt(tallySeed, DEFAULT_TALLY);
    previousVoteTallies.push_back(encryptedDefaultTally);

    Scalar seedForUserTally;
    seedForUserTally.set_random();
    EGCiphertext newUserEncryptedTally;
    newUserEncryptedTally.mask = shortTermPublicKey * seedForUserTally;
    newUserEncryptedTally.encryptedMessage =
        currentFreshGenerator * seedForUserTally +
        elGamalBlindGenerator * DEFAULT_TALLY;
    currentUserEncryptedTallies.push_back(newUserEncryptedTally);

    // Users are defaulted to casting a neutral vote for others.
    CurveBipoint encryptedDefaultVote, encryptedSelfVote;
    Scalar currDefaultSeed, currSelfSeed;
    encryptedDefaultVote = 
        bgnSystem.get_public_key().curveEncrypt(currDefaultSeed, DEFAULT_VOTE);
    encryptedSelfVote =
        bgnSystem.get_public_key().curveEncrypt(currSelfSeed, Scalar(MAX_ALLOWED_VOTE));

    std::vector<CurveBipoint> newRow;
    std::vector<Scalar> userVoteSeeds;
    std::vector<Scalar> otherVoteSeeds;
    for (size_t i = 0; i < voteMatrix.size(); i++)
    {
        Scalar addedSeed;

        encryptedDefaultVote = bgnSystem.get_public_key().rerandomize(addedSeed, encryptedDefaultVote);
        currDefaultSeed = currDefaultSeed + addedSeed;

        otherVoteSeeds.push_back(Scalar());
        otherVoteSeeds[i] = currDefaultSeed;
        
        voteMatrix[i].push_back(encryptedDefaultVote);

        encryptedDefaultVote = bgnSystem.get_public_key().rerandomize(addedSeed, encryptedDefaultVote);
        currDefaultSeed = currDefaultSeed + addedSeed;

        userVoteSeeds.push_back(Scalar());
        userVoteSeeds[i] = currDefaultSeed;

        newRow.push_back(encryptedDefaultVote);
    }
    
    // Because we are adding the new user to the end (and then sorting it),
    // this last element (bottom right corner) is always the self vote.
    userVoteSeeds.push_back(Scalar());
    userVoteSeeds[newRow.size()] = currSelfSeed;
    
    otherVoteSeeds.push_back(Scalar());
    otherVoteSeeds[newRow.size()] = currSelfSeed;

    newRow.push_back(encryptedSelfVote);
    voteMatrix.push_back(newRow);

    std::vector<size_t> sortOrder = order_data();
    std::vector<Scalar> newUserVoteSeeds;
    std::vector<Scalar> newOtherVoteSeeds;
    for (size_t i = 0; i < sortOrder.size(); i++)
    {
        newUserVoteSeeds.push_back(userVoteSeeds[sortOrder[i]]);
        newOtherVoteSeeds.push_back(otherVoteSeeds[sortOrder[i]]);
    }

    proofOfValidAddition = generate_proof_of_added_user(
        tallySeed,
        seedForUserTally,
        newUserVoteSeeds,
        newOtherVoteSeeds);
}

// Receive a new vote row from a user (identified by short term public key).
bool PrsonaServer::receive_vote(
    const std::vector<Proof>& pi,
    const std::vector<CurveBipoint>& newVotes,
    const Curvepoint& shortTermPublicKey)
{
    size_t voteSubmitter = binary_search(shortTermPublicKey);
    std::vector<CurveBipoint> oldVotes = voteMatrix[voteSubmitter];

    if (!verify_vote_proof(pi, oldVotes, newVotes, shortTermPublicKey))
        return false;

    voteMatrix[voteSubmitter] = newVotes;
    return true;
}

/*********************
 * PRIVATE FUNCTIONS *
 *********************/

/*
 * CONSTRUCTOR HELPERS
 */

const BGN& PrsonaServer::get_bgn_details() const
{
    return bgnSystem;
}

bool PrsonaServer::initialize_fresh_generator(
    const std::vector<Proof>& pi,
    const Curvepoint& firstGenerator)
{
    if (!verify_generator_proof(pi, firstGenerator, numServers))
    {
        std::cerr << "Could not verify generator proof, aborting." << std::endl;
        return false;
    }

    currentFreshGenerator = firstGenerator;
    return true;
}

// To calculate the blind generator for ElGamal, start from the base generator,
// then have every server call this function on it iteratively (in any order).
Curvepoint PrsonaServer::add_rand_seed_to_generator(
    std::vector<Proof>& pi,
    const Curvepoint& currGenerator) const
{
    Scalar lambda;
    lambda.set_random();

    pi.push_back(add_to_generator_proof(currGenerator, lambda));

    return currGenerator * lambda;
}

bool PrsonaServer::set_EG_blind_generator(
    const std::vector<Proof>& pi,
    const Curvepoint& currGenerator)
{
    return PrsonaBase::set_EG_blind_generator(pi, currGenerator, numServers);
}

/*
 * SCORE TALLYING
 */

/* Calculate scores homomorphically (as an individual server would normally)
 * and then decrypt them (which the servers would normally work together to do).
 *
 * Note that since these calculations are just for us, we don't need to do any
 * expensive rerandomizations of intermediate values. */
std::vector<Scalar> PrsonaServer::tally_scores()
{
    std::vector<Quadripoint> BGNEncryptedTallies;
    std::vector<Scalar> decryptedTallies;
    for (size_t i = 0; i < voteMatrix.size(); i++)
    {
        std::vector<Quadripoint> weightedVotes;

        // ZIP
        for (size_t j = 0; j < previousVoteTallies.size(); j++)
        {
            Quadripoint curr =
                bgnSystem.homomorphic_multiplication_no_rerandomize(
                    voteMatrix[j][i], previousVoteTallies[j]);

            weightedVotes.push_back(curr);
        }

        // FOLDL
        Quadripoint currEncryptedTally = weightedVotes[0];
        for (size_t j = 1; j < weightedVotes.size(); j++)
        {
            currEncryptedTally =
                bgnSystem.homomorphic_addition_no_rerandomize(
                    currEncryptedTally, weightedVotes[j]);
        }

        // DECRYPT
        decryptedTallies.push_back(bgnSystem.decrypt(currEncryptedTally));
    }

    return decryptedTallies;
}

/* Calculate what the maximum possible score this round was (that is,
 * given the current user weights, what was the highest possible score?).
 *
 * As with individual scores, this also does the decryption that servers
 * would ordinarily work together to form. */
Scalar PrsonaServer::get_max_possible_score()
{
    // FOLDL
    TwistBipoint currEncryptedVal = previousVoteTallies[0];
    for (size_t i = 1; i < previousVoteTallies.size(); i++)
    {
        currEncryptedVal =
            bgnSystem.homomorphic_addition_no_rerandomize(
                currEncryptedVal, previousVoteTallies[i]);
    }

    // DECRYPT
    Scalar retval = bgnSystem.decrypt(currEncryptedVal);

    return retval;
}

/*
 * EPOCH ROUNDS
 */

// The first round, going from A_0 to A_0.5
void PrsonaServer::build_up_midway_pseudonyms(
    std::vector<std::vector<std::vector<Proof>>>& pi,
    std::vector<std::vector<std::vector<Curvepoint>>>& permutationCommits,
    std::vector<std::vector<std::vector<Curvepoint>>>& freshPseudonymCommits,
    std::vector<std::vector<std::vector<Curvepoint>>>& freshPseudonymSeedCommits,
    std::vector<std::vector<std::vector<TwistBipoint>>>& serverTallyCommits,
    std::vector<std::vector<std::vector<std::vector<std::vector<CurveBipoint>>>>>& voteMatrixCommits,
    Curvepoint& nextGenerator)
{
    nextSeed.set_random();

    std::vector<std::vector<Curvepoint>> currPermutationCommits;
    std::vector<std::vector<Curvepoint>> currFreshPseudonymCommits;
    std::vector<std::vector<Curvepoint>> currFreshPseudonymSeedCommits;
    std::vector<std::vector<TwistBipoint>> currServerTallyCommits;
    std::vector<std::vector<std::vector<std::vector<CurveBipoint>>>> currVoteMatrixCommits;
    std::vector<std::vector<std::vector<Curvepoint>>> currUserTallyCommits;
    std::vector<std::vector<Curvepoint>> currUserTallyMaskSeedCommits;
    pi.push_back(epoch_calculations(
        currPermutationCommits,
        currFreshPseudonymCommits,
        currFreshPseudonymSeedCommits,
        currServerTallyCommits,
        currVoteMatrixCommits,
        currUserTallyCommits,
        currUserTallyMaskSeedCommits,
        nextSeed,
        false));

    permutationCommits.push_back(currPermutationCommits);
    freshPseudonymCommits.push_back(currFreshPseudonymCommits);
    freshPseudonymSeedCommits.push_back(currFreshPseudonymSeedCommits);
    serverTallyCommits.push_back(currServerTallyCommits);
    voteMatrixCommits.push_back(currVoteMatrixCommits);

    pi[0][0].push_back(
        add_to_generator_proof(nextGenerator, nextSeed));
    nextGenerator = nextGenerator * nextSeed;
}

// In between these rounds, scores are tallied, decrypted,
// and encrypted to fresh user pseudonyms (possible through weird math)

// The second round, going from A_0.5 to A_1
void PrsonaServer::break_down_midway_pseudonyms(
    std::vector<Proof>& generatorProof,
    std::vector<std::vector<std::vector<Proof>>>& pi,
    std::vector<std::vector<std::vector<Curvepoint>>>& permutationCommits,
    std::vector<std::vector<std::vector<Curvepoint>>>& freshPseudonymCommits,
    std::vector<std::vector<std::vector<Curvepoint>>>& freshPseudonymSeedCommits,
    std::vector<std::vector<std::vector<TwistBipoint>>>& serverTallyCommits,
    std::vector<std::vector<std::vector<std::vector<std::vector<CurveBipoint>>>>>& voteMatrixCommits,
    std::vector<std::vector<std::vector<std::vector<Curvepoint>>>>& userTallyCommits,
    std::vector<std::vector<std::vector<Curvepoint>>>& userTallyMaskSeedCommits,
    const Curvepoint& nextGenerator)
{
    if (!initialize_fresh_generator(generatorProof, nextGenerator))
    {
        std::cerr << "New fresh generator could not be verified." << std::endl;
        return;
    }

    Scalar inverseSeed = currentSeed.curveMultInverse();

    std::vector<std::vector<Curvepoint>> currPermutationCommits;
    std::vector<std::vector<Curvepoint>> currFreshPseudonymCommits;
    std::vector<std::vector<Curvepoint>> currFreshPseudonymSeedCommits;
    std::vector<std::vector<TwistBipoint>> currServerTallyCommits;
    std::vector<std::vector<std::vector<std::vector<CurveBipoint>>>> currVoteMatrixCommits;
    std::vector<std::vector<std::vector<Curvepoint>>> currUserTallyCommits;
    std::vector<std::vector<Curvepoint>> currUserTallyMaskSeedCommits;
    pi.push_back(epoch_calculations(
        currPermutationCommits,
        currFreshPseudonymCommits,
        currFreshPseudonymSeedCommits,
        currServerTallyCommits,
        currVoteMatrixCommits,
        currUserTallyCommits,
        currUserTallyMaskSeedCommits,
        inverseSeed,
        true));

    permutationCommits.push_back(currPermutationCommits);
    freshPseudonymCommits.push_back(currFreshPseudonymCommits);
    freshPseudonymSeedCommits.push_back(currFreshPseudonymSeedCommits);
    serverTallyCommits.push_back(currServerTallyCommits);
    voteMatrixCommits.push_back(currVoteMatrixCommits);
    userTallyCommits.push_back(currUserTallyCommits);
    userTallyMaskSeedCommits.push_back(currUserTallyMaskSeedCommits);

    currentSeed = nextSeed;
}

/*
 * EPOCH HELPERS
 */

std::vector<std::vector<Proof>> PrsonaServer::epoch_calculations(
    std::vector<std::vector<Curvepoint>>& permutationCommits,
    std::vector<std::vector<Curvepoint>>& freshPseudonymCommits,
    std::vector<std::vector<Curvepoint>>& freshPseudonymSeedCommits,
    std::vector<std::vector<TwistBipoint>>& serverTallyCommits,
    std::vector<std::vector<std::vector<std::vector<CurveBipoint>>>>& voteMatrixCommits,
    std::vector<std::vector<std::vector<Curvepoint>>>& userTallyCommits,
    std::vector<std::vector<Curvepoint>> & userTallyMaskSeedCommits,
    const Scalar& power,
    bool doUserTallies)
{
    std::vector<std::vector<Proof>> retval;

    std::vector<Curvepoint> nextPseudonyms;
    for (size_t i = 0; i < currentPseudonyms.size(); i++)
        nextPseudonyms.push_back(currentPseudonyms[i] * power);

    std::vector<size_t> order = sort_data(nextPseudonyms);
    for (size_t i = 0; i < currentPseudonyms.size(); i++)
        nextPseudonyms[i] = currentPseudonyms[order[i]] * power;

    std::cout << "Generating permutation matrix." << std::endl;

    std::vector<std::vector<Scalar>> permutations =
        generate_permutation_matrix(power);

    std::cout << "Generating permutation commitment matrix." << std::endl;

    std::vector<std::vector<Scalar>> permutationSeeds;
    permutationCommits.clear();
    permutationCommits = 
        generate_commitment_matrix(permutations, permutationSeeds);

    std::cout << "Generating permutation proof." << std::endl;

    retval.push_back(generate_valid_permutation_proof(
        permutations, permutationSeeds, permutationCommits));

    std::cout << "Generating pseudonym matrix." << std::endl;

    std::vector<std::vector<Scalar>> freshPseudonymSeeds;
    freshPseudonymSeedCommits.clear();
    freshPseudonymCommits.clear();
    freshPseudonymCommits = 
        generate_pseudonym_matrix(
            permutations,
            power,
            freshPseudonymSeeds,
            freshPseudonymSeedCommits);

    // for (size_t i = 0; i < freshPseudonymCommits.size(); i++)
    // {
    //     Curvepoint sum = freshPseudonymCommits[i][0];
    //     for (size_t j = 1; j < freshPseudonymCommits[i].size(); j++)
    //         sum = sum + freshPseudonymCommits[i][j];
    //     std::cout << "Fresh pseudonym commit row " << i + 1 << " of " << permutationCommits.size()
    //         << (sum == nextPseudonyms[i] ? ": PASS" : ": FAIL") << std::endl;
    // }

    std::cout << "Generating pseudonym proof." << std::endl;

    retval.push_back(
        generate_proof_of_reordering_plus_power(
            permutations,
            power,
            permutationSeeds,
            freshPseudonymSeeds,
            currentPseudonyms,
            permutationCommits,
            freshPseudonymCommits,
            freshPseudonymSeedCommits));

    std::cout << "Generating server tally matrix." << std::endl;

    std::vector<std::vector<Scalar>> serverTallySeeds;
    serverTallyCommits.clear();
    serverTallyCommits = 
        generate_server_tally_matrix(
            permutations,
            serverTallySeeds);

    std::cout << "Generating server tally proof." << std::endl;

    retval.push_back(
        generate_proof_of_reordering<TwistBipoint>(
            permutations,
            permutationSeeds,
            serverTallySeeds,
            previousVoteTallies,
            permutationCommits,
            serverTallyCommits,
            bgnSystem.get_public_key().get_bipoint_twistgen(),
            bgnSystem.get_public_key().get_bipoint_twist_subgroup_gen()));

    std::cout << "Doing V * P." << std::endl;

    std::vector<std::vector<std::vector<Scalar>>> firstVoteMatrixSeeds;
    std::vector<std::vector<std::vector<Scalar>>> secondVoteMatrixSeeds;
    voteMatrixCommits.push_back(
        generate_vote_tensor(
            permutations,
            voteMatrix,
            firstVoteMatrixSeeds,
            false));

    std::cout << "Finishing V * P calculation." << std::endl;

    std::vector<std::vector<CurveBipoint>> partialVoteMatrix = 
        calculate_next_vote_matrix(voteMatrixCommits[0]);

    std::cout << "Doing P^T * (V * P)." << std::endl;

    voteMatrixCommits.push_back(
        generate_vote_tensor(
            permutations,
            partialVoteMatrix,
            secondVoteMatrixSeeds,
            true));

    std::cout << "Proving V * P." << std::endl;

    generate_vote_tensor_proofs(
        retval,
        permutations,
        permutationSeeds,
        firstVoteMatrixSeeds,
        voteMatrix,
        permutationCommits,
        voteMatrixCommits[0],
        false);

    std::cout << "Proving P^T * (V * P)." << std::endl;

    generate_vote_tensor_proofs(
        retval,
        permutations,
        permutationSeeds,
        secondVoteMatrixSeeds,
        partialVoteMatrix,
        permutationCommits,
        voteMatrixCommits[1],
        true);

    if (doUserTallies)
    {
        std::cout << "Generating user tally matrix." << std::endl;

        std::vector<Curvepoint> userTallyMasks;
        std::vector<std::vector<Scalar>> userTallyMaskSeeds;
        userTallyMaskSeedCommits.clear();
        std::vector<Curvepoint> userTallyMessages;
        std::vector<std::vector<Scalar>> userTallyMessageSeeds;
        userTallyCommits = 
            generate_user_tally_matrix(
                permutations,
                power,
                userTallyMasks,
                userTallyMessages,
                userTallyMaskSeeds,
                userTallyMaskSeedCommits,
                userTallyMessageSeeds);

        std::cout << "Proving user tally mask matrix." << std::endl;

        retval.push_back(
            generate_proof_of_reordering_plus_power(
                permutations,
                power,
                permutationSeeds,
                userTallyMaskSeeds,
                userTallyMasks,
                permutationCommits,
                userTallyCommits[0],
                userTallyMaskSeedCommits));

        std::cout << "Proving user tally message matrix." << std::endl;

        retval.push_back(
            generate_proof_of_reordering<Curvepoint>(
                permutations,
                permutationSeeds,
                userTallyMessageSeeds,
                userTallyMessages,
                permutationCommits,
                userTallyCommits[1],
                EL_GAMAL_GENERATOR,
                elGamalBlindGenerator));
    }

    std::cout << "Giving self updates." << std::endl;

    // Replace internal values
    update_data(
        freshPseudonymCommits,
        serverTallyCommits,
        voteMatrixCommits[1],
        userTallyCommits);

    return retval;
}

bool PrsonaServer::accept_epoch_updates(
    const std::vector<std::vector<Proof>>& pi,
    const std::vector<std::vector<Curvepoint>>& permutationCommits,
    const std::vector<std::vector<Curvepoint>>& freshPseudonymCommits,
    const std::vector<std::vector<Curvepoint>>& freshPseudonymSeedCommits,
    const std::vector<std::vector<TwistBipoint>>& serverTallyCommits,
    const std::vector<std::vector<std::vector<std::vector<CurveBipoint>>>>& voteMatrixCommits,
    const std::vector<std::vector<std::vector<Curvepoint>>>& userTallyCommits,
    const std::vector<std::vector<Curvepoint>>& userTallyMaskSeedCommits,
    bool doUserTallies)
{
    bool verification;

    if ((userTallyCommits.empty() && doUserTallies) || (!userTallyCommits.empty() && !doUserTallies))
    {
        std::cerr << "user tallies are not in expected state." << std::endl;
        return false;
    }

    if (pi.empty())
        return false;

    std::cout << "Verifying valid permutation matrix." << std::endl;

    verification =
        verify_valid_permutation_proof(pi[0], permutationCommits);
    if (!verification)
    {
        std::cerr << "Could not verify valid permutation matrix." << std::endl;
        return false;
    }

    std::cout << "Verifying valid pseudonym vector." << std::endl;

    verification = 
        verify_proof_of_reordering_plus_power(
            pi[1],
            currentPseudonyms,
            permutationCommits,
            freshPseudonymCommits,
            freshPseudonymSeedCommits);
    if (!verification)
    {
        std::cerr << "Could not verify valid pseudonym vector." << std::endl;
        return false;
    }

    std::cout << "Verifying valid server tally vector." << std::endl;

    verification = 
        verify_proof_of_reordering<TwistBipoint>(
            pi[2],
            previousVoteTallies,
            permutationCommits,
            serverTallyCommits,
            bgnSystem.get_public_key().get_bipoint_twistgen(),
            bgnSystem.get_public_key().get_bipoint_twist_subgroup_gen());
    if (!verification)
    {
        std::cerr << "Could not verify valid server tally vector." << std::endl;
        return false;
    }

    std::cout << "Verifying valid first half vote matrix." << std::endl;

    size_t currOffset = 3;
    verification = verify_vote_tensor_proofs(
        pi,
        currOffset,
        voteMatrix,
        permutationCommits,
        voteMatrixCommits[0],
        false);
    if (!verification)
    {
        std::cerr << "Could not verify first half vote matrix." << std::endl;
        return false;
    }

    std::cout << "Verifying valid second half vote matrix." << std::endl;

    std::vector<std::vector<CurveBipoint>> partialVoteMatrix =
        calculate_next_vote_matrix(voteMatrixCommits[0]);
    currOffset += voteMatrix.size();
    verification = verify_vote_tensor_proofs(
        pi,
        currOffset,
        partialVoteMatrix,
        permutationCommits,
        voteMatrixCommits[1],
        true);
    if (!verification)
    {
        std::cerr << "Could not verify second half vote matrix." << std::endl;
        return false;
    }

    currOffset += voteMatrix.size();

    if (doUserTallies)
    {
        std::vector<Curvepoint> userTallyMasks;
        std::vector<Curvepoint> userTallyMessages;
        for (size_t i = 0; i < currentUserEncryptedTallies.size(); i++)
        {
            userTallyMasks.push_back(currentUserEncryptedTallies[i].mask);
            userTallyMessages.push_back(currentUserEncryptedTallies[i].encryptedMessage);
        }

        std::cout << "Verifying valid user tally masks." << std::endl;

        verification = verify_proof_of_reordering_plus_power(
            pi[currOffset],
            userTallyMasks,
            permutationCommits,
            userTallyCommits[0],
            userTallyMaskSeedCommits);
        if (!verification)
        {
            std::cerr << "Could not verify user tally masks." << std::endl;
            return false;
        }

        currOffset++;

        std::cout << "Verifying valid user tally messages." << std::endl;

        verification = verify_proof_of_reordering<Curvepoint>(
            pi[currOffset],
            userTallyMessages,
            permutationCommits,
            userTallyCommits[1],
            EL_GAMAL_GENERATOR,
            elGamalBlindGenerator);
        if (!verification)
        {
            std::cerr << "Could not verify user tally messages." << std::endl;
            return false;
        }
    }

    std::cout << "Verifying pseudonyms are all different." << std::endl;

    verification = update_data(
        freshPseudonymCommits,
        serverTallyCommits,
        voteMatrixCommits[1],
        userTallyCommits);

    return verification;
}

std::vector<std::vector<Scalar>> PrsonaServer::generate_permutation_matrix(
    const Scalar& reorderSeed) const
{
    std::vector<std::vector<Scalar>> retval;
    for (size_t i = 0; i < currentPseudonyms.size(); i++)
    {
        std::vector<Scalar> currRow;
        for (size_t j = 0; j < currentPseudonyms.size(); j++)
            currRow.push_back(Scalar(0));

        retval.push_back(currRow);
    }

    std::vector<Curvepoint> nextPseudonyms;
    for (size_t i = 0; i < currentPseudonyms.size(); i++)
        nextPseudonyms.push_back(currentPseudonyms[i] * reorderSeed);

    std::vector<size_t> order = sort_data(nextPseudonyms);

    for (size_t i = 0; i < order.size(); i++)
        retval[order[i]][i] = Scalar(1);

    std::cout << "[";
    for (size_t i = 0; i < order.size(); i++)
    {
        std::cout << "[";
        for (size_t j = 0; j < order.size(); j++)
        {
            std::cout << retval[i][j] << (j == order.size() - 1 ? "]" : " ");
        }
        std::cout << (i == order.size() - 1 ? "]" : " ") << std::endl << (i == order.size() - 1 ? "" : " ");
    }

    return retval;
}

std::vector<std::vector<Curvepoint>> PrsonaServer::generate_commitment_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    std::vector<std::vector<Scalar>>& seeds) const
{
    std::vector<std::vector<Curvepoint>> retval;
    Curvepoint g = EL_GAMAL_GENERATOR;
    Curvepoint h = elGamalBlindGenerator;

    seeds.clear();
    for (size_t i = 0; i < permutations.size(); i++)
    {
        std::vector<Scalar> currSeeds;

        for (size_t j = 0; j < permutations[i].size(); j++)
            currSeeds.push_back(Scalar(0));

        seeds.push_back(currSeeds);
    }

    for (size_t i = 0; i < permutations.size(); i++)
    {
        std::vector<Curvepoint> currRow;

        size_t last = permutations[i].size() - 1;
        for (size_t j = 0; j < permutations[i].size(); j++)
        {
            Curvepoint element;

            if (j != last)
            {
                seeds[i][j].set_random();
                seeds[i][last] = seeds[i][last] - seeds[i][j];
            }

            element = g * permutations[i][j] + h * seeds[i][j];

            currRow.push_back(element);
        }
        retval.push_back(currRow);
    }

    return retval;
}

std::vector<std::vector<Curvepoint>> PrsonaServer::generate_pseudonym_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    const Scalar& power,
    std::vector<std::vector<Scalar>>& seeds,
    std::vector<std::vector<Curvepoint>>& seedCommits) const
{
    return generate_reordered_plus_power_matrix<Curvepoint>(
        permutations,
        power,
        currentPseudonyms,
        seeds,
        seedCommits,
        elGamalBlindGenerator);
}

std::vector<std::vector<TwistBipoint>> PrsonaServer::generate_server_tally_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    std::vector<std::vector<Scalar>>& seeds) const
{
    return generate_reordered_matrix<TwistBipoint>(
        permutations,
        previousVoteTallies,
        seeds,
        bgnSystem.get_public_key().get_bipoint_twist_subgroup_gen(),
        false);
}

std::vector<std::vector<std::vector<CurveBipoint>>> PrsonaServer::generate_vote_tensor(
    const std::vector<std::vector<Scalar>>& permutations,
    const std::vector<std::vector<CurveBipoint>>& currVoteMatrix,
    std::vector<std::vector<std::vector<Scalar>>>& seeds,
    bool inverted) const
{
    std::vector<std::vector<std::vector<CurveBipoint>>> retval;

    for (size_t i = 0; i < currVoteMatrix.size(); i++)
    {
        std::vector<std::vector<Scalar>> currSeeds;

        std::vector<CurveBipoint> inputRow;
        if (inverted)
        {
            for (size_t j = 0; j < currVoteMatrix.size(); j++)
                inputRow.push_back(currVoteMatrix[j][i]);
        }
        else
        {
            inputRow = currVoteMatrix[i];
        }
        
        retval.push_back(generate_reordered_matrix<CurveBipoint>(
            permutations,
            inputRow,
            currSeeds,
            bgnSystem.get_public_key().get_bipoint_curve_subgroup_gen(),
            false));

        seeds.push_back(currSeeds);
    }

    return retval;
}

std::vector<std::vector<CurveBipoint>> PrsonaServer::calculate_next_vote_matrix(
    const std::vector<std::vector<std::vector<CurveBipoint>>>& voteTensor) const
{
    std::vector<std::vector<CurveBipoint>> retval;

    for (size_t i = 0; i < voteTensor.size(); i++)
    {
        std::vector<CurveBipoint> currRow;
        for (size_t j = 0; j < voteTensor[i].size(); j++)
        {
            CurveBipoint sum = voteTensor[i][j][0];
            
            for (size_t k = 1; k < voteTensor[i][j].size(); k++)
                sum = sum + voteTensor[i][j][k];

            currRow.push_back(sum);
        }
        retval.push_back(currRow);
    }

    return retval;
}

void PrsonaServer::generate_vote_tensor_proofs(
    std::vector<std::vector<Proof>>& pi,
    const std::vector<std::vector<Scalar>>& permutations,
    const std::vector<std::vector<Scalar>>& permutationSeeds,
    const std::vector<std::vector<std::vector<Scalar>>>& matrixSeeds,
    const std::vector<std::vector<CurveBipoint>>& currMatrix,
    const std::vector<std::vector<Curvepoint>>& permutationCommits,
    const std::vector<std::vector<std::vector<CurveBipoint>>>& matrixCommits,
    bool inverted) const
{
    for (size_t i = 0; i < currMatrix.size(); i++)
    {
        std::vector<CurveBipoint> inputRow;
        if (inverted)
        {
            for (size_t j = 0; j < currMatrix.size(); j++)
                inputRow.push_back(currMatrix[j][i]);
        }
        else
        {
            inputRow = currMatrix[i];
        }
        
        pi.push_back(generate_proof_of_reordering<CurveBipoint>(
            permutations,
            permutationSeeds,
            matrixSeeds[i],
            inputRow,
            permutationCommits,
            matrixCommits[i],
            bgnSystem.get_public_key().get_bipoint_curvegen(),
            bgnSystem.get_public_key().get_bipoint_curve_subgroup_gen()));
    }
}

bool PrsonaServer::verify_vote_tensor_proofs(
    const std::vector<std::vector<Proof>>& pi,
    size_t start_offset,
    const std::vector<std::vector<CurveBipoint>>& currMatrix,
    const std::vector<std::vector<Curvepoint>>& permutationCommits,
    const std::vector<std::vector<std::vector<CurveBipoint>>>& matrixCommits,
    bool inverted) const
{
    bool retval = true;

    for (size_t i = 0; i < currMatrix.size(); i++)
    {
        std::vector<CurveBipoint> inputRow;
        if (inverted)
        {
            for (size_t j = 0; j < currMatrix.size(); j++)
                inputRow.push_back(currMatrix[j][i]);
        }
        else
        {
            inputRow = currMatrix[i];
        }

        size_t whichProof = i + start_offset;
        retval = retval && verify_proof_of_reordering<CurveBipoint>(
            pi[whichProof],
            inputRow,
            permutationCommits,
            matrixCommits[i],
            bgnSystem.get_public_key().get_bipoint_curvegen(),
            bgnSystem.get_public_key().get_bipoint_curve_subgroup_gen());
    }

    return retval;
}

std::vector<std::vector<std::vector<Curvepoint>>> PrsonaServer::generate_user_tally_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    const Scalar& power,
    std::vector<Curvepoint>& masks,
    std::vector<Curvepoint>& messages,
    std::vector<std::vector<Scalar>>& maskSeeds,
    std::vector<std::vector<Curvepoint>>& maskSeedCommits,
    std::vector<std::vector<Scalar>>& messageSeeds) const
{
    std::vector<std::vector<std::vector<Curvepoint>>> retval;

    masks.clear();
    messages.clear();
    for (size_t i = 0; i < currentUserEncryptedTallies.size(); i++)
    {
        masks.push_back(currentUserEncryptedTallies[i].mask);
        messages.push_back(currentUserEncryptedTallies[i].encryptedMessage);
    }

    retval.push_back(
        generate_reordered_plus_power_matrix<Curvepoint>(
            permutations,
            power,
            masks,
            maskSeeds,
            maskSeedCommits,
            elGamalBlindGenerator));

    retval.push_back(
        generate_reordered_matrix<Curvepoint>(
            permutations,
            messages,
            messageSeeds,
            elGamalBlindGenerator,
            false));

    return retval;
}

template <typename T>
std::vector<std::vector<T>> PrsonaServer::generate_reordered_plus_power_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    const Scalar& power,
    const std::vector<T>& oldValues,
    std::vector<std::vector<Scalar>>& seeds,
    std::vector<std::vector<Curvepoint>>& seedCommits,
    const T& h) const
{
    std::vector<std::vector<Scalar>> permutation_plus_power;
    seedCommits.clear();

    for (size_t i = 0; i < permutations.size(); i++)
    {
        std::vector<Scalar> currPermutations;
        std::vector<Curvepoint> currSeedCommits;
        for (size_t j = 0; j < permutations[i].size(); j++)
        {
            currPermutations.push_back(permutations[i][j] * power);
            currSeedCommits.push_back(Curvepoint());
        }
        permutation_plus_power.push_back(currPermutations);
        seedCommits.push_back(currSeedCommits);
    }

    std::vector<std::vector<T>> retval = 
        generate_reordered_matrix<T>(
            permutation_plus_power,
            oldValues,
            seeds,
            h,
            true);

    for (size_t i = 0; i < permutations.size(); i++)
        for (size_t j = 0; j < permutations[i].size(); j++)
            seedCommits[i][j] = EL_GAMAL_GENERATOR * seeds[i][j];
    
    return retval;
}

template <typename T>
std::vector<std::vector<T>> PrsonaServer::generate_reordered_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    const std::vector<T>& oldValues,
    std::vector<std::vector<Scalar>>& seeds,
    const T& h,
    bool cancelOut) const
{
    std::vector<std::vector<T>> retval;

    seeds.clear();
    for (size_t i = 0; i < permutations.size(); i++)
    {
        std::vector<Scalar> currSeeds;
        std::vector<T> currRow;
        for (size_t j = 0; j < permutations[i].size(); j++)\
        {
            currSeeds.push_back(Scalar(0));
            currRow.push_back(T());
        }
        seeds.push_back(currSeeds);
        retval.push_back(currRow);
    }

    for (size_t i = 0; i < permutations.size(); i++)
    {
        size_t last = permutations[i].size() - 1;
        for (size_t j = 0; j < permutations[i].size(); j++)
        {
            if (!cancelOut)
            {
                seeds[i][j].set_random();
            }
            else if (j != last)
            {
                seeds[i][j].set_random();
                seeds[i][last] = seeds[i][last] - seeds[i][j];
            }

            retval[i][j] = oldValues[j] * permutations[j][i] + h * seeds[i][j];
        }
    }

    return retval;
}

std::vector<size_t> PrsonaServer::sort_data(const std::vector<Curvepoint>& inputs) const
{
    std::vector<size_t> retval;

    // SortingType's index member allows us to replicate the "sort" across
    std::vector<SortingType> sortTracker;
    for (size_t i = 0; i < inputs.size(); i++)
    {
        SortingType curr;
        
        curr.pseudonym = inputs[i];
        curr.index = i;

        sortTracker.push_back(curr);
    }
    std::sort(sortTracker.begin(), sortTracker.end());

    for (size_t i = 0; i < inputs.size(); i++)
        retval.push_back(sortTracker[i].index);

    return retval;
}

bool PrsonaServer::update_data(
    const std::vector<std::vector<Curvepoint>>& freshPseudonymCommits,
    const std::vector<std::vector<TwistBipoint>>& serverTallyCommits,
    const std::vector<std::vector<std::vector<CurveBipoint>>>& voteMatrixCommits,
    const std::vector<std::vector<std::vector<Curvepoint>>>& userTallyCommits)
{
    std::vector<Curvepoint> newPseudonyms;
    std::vector<TwistBipoint> newVoteTallies;
    std::vector<EGCiphertext> newUserTallies;

    for (size_t i = 0; i < freshPseudonymCommits.size(); i++)
    {
        Curvepoint pseudonymSum = freshPseudonymCommits[i][0];
        TwistBipoint voteTallySum = serverTallyCommits[i][0];

        Curvepoint userTallyMask, userTallyMessage;
        if (!userTallyCommits.empty())
        {
            userTallyMask = userTallyCommits[i][0][0];
            userTallyMessage = userTallyCommits[i][0][1];
        }

        for (size_t j = 1; j < freshPseudonymCommits[i].size(); j++)
        {
            pseudonymSum = pseudonymSum + freshPseudonymCommits[i][j];
            voteTallySum = voteTallySum + serverTallyCommits[i][j];

            if (!userTallyCommits.empty())
            {
                userTallyMask = userTallyMask +
                    userTallyCommits[i][j][0];
                userTallyMessage = userTallyMessage +
                    userTallyCommits[i][j][1];
            }
        }

        newPseudonyms.push_back(pseudonymSum);
        newVoteTallies.push_back(voteTallySum);

        if (!userTallyCommits.empty())
        {
            newUserTallies.push_back(
                EGCiphertext(userTallyMask, userTallyMessage));
        }
    }

    if (!pseudonyms_sorted(newPseudonyms))
    {
        std::cerr << "Pseudonyms not sorted correctly." << std::endl;
        return false;
    }

    currentPseudonyms = newPseudonyms;
    previousVoteTallies = newVoteTallies;
    voteMatrix = calculate_next_vote_matrix(voteMatrixCommits);
    currentUserEncryptedTallies = newUserTallies;

    return true;
}

bool PrsonaServer::pseudonyms_sorted(
    const std::vector<Curvepoint> newPseudonyms) const
{
    bool retval = true;
    
    for (size_t i = 0; i < newPseudonyms.size() - 1; i++)
        retval = retval && (newPseudonyms[i] < newPseudonyms[i + 1]);

    return retval;
}

/*
 * DATA MAINTENANCE
 */

bool PrsonaServer::import_new_user_update(
    const std::vector<Proof>& pi,
    const std::vector<TwistBipoint>& otherPreviousVoteTallies,
    const std::vector<Curvepoint>& otherCurrentPseudonyms,
    const std::vector<EGCiphertext>& otherCurrentUserEncryptedTallies,
    const std::vector<std::vector<CurveBipoint>>& otherVoteMatrix)
{
    size_t newIndex = 0;
    if (!currentPseudonyms.empty())
        while (otherCurrentPseudonyms[newIndex] == currentPseudonyms[newIndex])
            newIndex++;

    Curvepoint shortTermPublicKey = otherCurrentPseudonyms[newIndex];

    bool flag = verify_proof_of_added_user(
        pi,
        currentFreshGenerator,
        shortTermPublicKey,
        bgnSystem.get_public_key().get_bipoint_curvegen(),
        bgnSystem.get_public_key().get_bipoint_curve_subgroup_gen(),
        bgnSystem.get_public_key().get_bipoint_twistgen(),
        bgnSystem.get_public_key().get_bipoint_twist_subgroup_gen(),
        newIndex,
        otherCurrentUserEncryptedTallies[newIndex],
        otherPreviousVoteTallies[newIndex],
        otherVoteMatrix);

    if (!flag)
    {
        std::cerr << "Other server added new user invalidly, aborting." << std::endl;
        return false;
    }

    for (size_t i = 0; i < otherCurrentPseudonyms.size(); i++)
    {
        if (i == newIndex)
            continue;

        size_t otherI = (i > newIndex ? i - 1 : i);

        flag = flag && otherCurrentPseudonyms[i] ==
                currentPseudonyms[otherI];
        flag = flag && otherCurrentUserEncryptedTallies[i] ==
                currentUserEncryptedTallies[otherI];
        flag = flag && otherPreviousVoteTallies[i] ==
                previousVoteTallies[otherI];

        for (size_t j = 0; j < otherCurrentPseudonyms.size(); j++)
        {
            if (j == newIndex)
                continue;

            size_t otherJ = (j > newIndex ? j - 1 : j);
            flag = flag && otherVoteMatrix[i][j] ==
                    voteMatrix[otherI][otherJ];
        }
    }

    if (!flag)
    {
        std::cerr << "Other server illicitly changed other value during new user add." << std::endl;
        return false;
    }

    previousVoteTallies = otherPreviousVoteTallies;
    currentPseudonyms = otherCurrentPseudonyms;
    currentUserEncryptedTallies = otherCurrentUserEncryptedTallies;
    voteMatrix = otherVoteMatrix;

    return true;
}

/*
 * DATA SAFEKEEPING
 */

/* This is what powers the "shuffle"; really, as pseudonyms get updated,
 * the pseudonyms are no longer in the order prescribed by operator<().
 * So, we put them (and everything else) back into that order,
 * effectively shuffling them (and making lookups easier later on). */
std::vector<size_t> PrsonaServer::order_data()
{
    std::vector<size_t> retval = sort_data(currentPseudonyms);

    // Order all other data in the same way, for consistency
    std::vector<Curvepoint> newPseudonyms;
    std::vector<TwistBipoint> newVoteTallies;
    std::vector<EGCiphertext> newUserEncryptedTallies;
    std::vector<std::vector<CurveBipoint>> newVoteMatrix;

    for (size_t i = 0; i < retval.size(); i++)
    {
        newPseudonyms.push_back(currentPseudonyms[retval[i]]);
        newVoteTallies.push_back(previousVoteTallies[retval[i]]);
        
        if (!currentUserEncryptedTallies.empty())
        {
            newUserEncryptedTallies.push_back(
                currentUserEncryptedTallies[retval[i]]);
        }

        std::vector<CurveBipoint> currNewRow;
        for (size_t j = 0; j < currentPseudonyms.size(); j++)
        {
            currNewRow.push_back(
                voteMatrix[retval[i]][retval[j]]);
        }
        newVoteMatrix.push_back(currNewRow);
    }

    previousVoteTallies = newVoteTallies;
    currentPseudonyms = newPseudonyms;
    currentUserEncryptedTallies = newUserEncryptedTallies;
    voteMatrix = newVoteMatrix;

    return retval;
}

/*
 * BINARY SEARCH
 */

// Completely normal binary search
size_t PrsonaServer::binary_search(const Curvepoint& index) const
{
    return PrsonaBase::binary_search(currentPseudonyms, index);
}

/*
 * VALID VOTE PROOFS
 */

bool PrsonaServer::verify_vote_proof(
    const std::vector<Proof>& pi,
    const std::vector<CurveBipoint>& oldVotes,
    const std::vector<CurveBipoint>& newVotes,
    const Curvepoint& shortTermPublicKey) const
{
    const BGNPublicKey& pubKey = bgnSystem.get_public_key();
    return PrsonaBase::verify_vote_proof(
        pubKey.get_bipoint_curvegen(),
        pubKey.get_bipoint_curve_subgroup_gen(),
        pi,
        oldVotes,
        newVotes,
        currentFreshGenerator,
        shortTermPublicKey);
}

void PrsonaServer::print_scores(const std::vector<TwistBipoint>& scores)
{
    std::cout << "[";
    for (size_t i = 0; i < scores.size(); i++)
    {
            std::cout << bgnSystem.decrypt(scores[i])
                << (i == scores.size() - 1 ? "]" : " ");
    }
    std::cout << std::endl;
}