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;
}

Twistpoint PrsonaServer::get_fresh_generator(
    std::vector<Proof>& pi) const
{
    pi = currentGeneratorProof;
    return currentFreshGenerator;
}

/*
 * 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).
Twistpoint PrsonaServer::add_curr_seed_to_generator(
    std::vector<Proof>& pi,
    const Twistpoint& 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).
Twistpoint PrsonaServer::add_next_seed_to_generator(
    std::vector<Proof>& pi,
    const Twistpoint& 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<TwistBipoint> PrsonaServer::get_current_votes_by(
    Proof& pi,
    const Twistpoint& shortTermPublicKey) const
{
    std::vector<TwistBipoint> retval;
    size_t voteSubmitter = binary_search(shortTermPublicKey);
    retval = voteMatrix[voteSubmitter];

    pi = generate_valid_vote_row_proof(retval);
    return retval;
}

std::vector<std::vector<TwistBipoint>> 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 Twistpoint& shortTermPublicKey) const
{
    EGCiphertext retval;
    size_t tallyOwner = binary_search(shortTermPublicKey);
    retval = currentUserEncryptedTallies[tallyOwner];
    
    pi = generate_valid_user_tally_proof(retval);
    return retval;
}

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

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

std::vector<Twistpoint> PrsonaServer::get_current_pseudonyms() const
{
    return currentPseudonyms;
}

/*
 * PROOF COMMITMENT GETTERS
 */

Proof PrsonaServer::get_vote_row_commitment(
    const Twistpoint& 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 Twistpoint& request) const
{
    size_t requestID = binary_search(request);
    return generate_valid_user_tally_proof(currentUserEncryptedTallies[requestID]);
}

Proof PrsonaServer::get_server_tally_commitment(
    const Twistpoint& 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);
}

void PrsonaServer::print_current_commitments() const
{    
    std::stringstream helper; 
    std::cout << "Commitments:\n";
    std::cout << "User tallies:\n";
    for (size_t i = 0; i < currentUserEncryptedTallies.size(); i++)
    {
        helper.str("");
        helper << currentUserEncryptedTallies[i];
        std::cout << "Tally " << i + 1 << " of " << currentUserEncryptedTallies.size() << ": " << std::hex << oracle(helper.str()) << std::dec << "\n";
    }

    std::cout << "Server tallies:\n";
    for (size_t i = 0; i < previousVoteTallies.size(); i++)
    {
        helper.str("");
        helper << previousVoteTallies[i];
        std::cout << "Tally " << i + 1 << " of " << previousVoteTallies.size() << ": " << std::hex << oracle(helper.str()) << std::dec << "\n";
    }
}

/*
 * 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 Twistpoint& 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;
    CurveBipoint encryptedDefaultTally = bgnSystem.get_public_key().curveEncrypt(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.
    TwistBipoint encryptedDefaultVote, encryptedSelfVote;
    Scalar currDefaultSeed, currSelfSeed;
    encryptedDefaultVote = bgnSystem.get_public_key().twistEncrypt(currDefaultSeed, DEFAULT_VOTE);
    encryptedSelfVote = bgnSystem.get_public_key().twistEncrypt(currSelfSeed, Scalar(MAX_ALLOWED_VOTE));

    std::vector<TwistBipoint> 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<TwistBipoint>& newVotes,
    const Twistpoint& shortTermPublicKey)
{
    size_t voteSubmitter = binary_search(shortTermPublicKey);
    std::vector<TwistBipoint> 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 Twistpoint& firstGenerator)
{
    if (!verify_generator_proof(pi, firstGenerator, numServers))
    {
        std::cerr << "Could not verify generator proof, aborting." << std::endl;
        return false;
    }

    currentGeneratorProof = pi;
    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).
Twistpoint PrsonaServer::add_rand_seed_to_generator(
    std::vector<Proof>& pi,
    const Twistpoint& 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 Twistpoint& 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(previousVoteTallies[j], voteMatrix[j][i]);

            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
    CurveBipoint 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;
}

void PrsonaServer::receive_tallied_scores(
    const std::vector<EGCiphertext>& userTallyScores,
    const std::vector<CurveBipoint>& serverTallyScores)
{
    currentUserEncryptedTallies = userTallyScores;
    previousVoteTallies = serverTallyScores;
}

void PrsonaServer::encrypt(
    CurveBipoint& element,
    const Scalar& value)
{
    bgnSystem.encrypt(element, value);
}

/*
 * 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<Twistpoint>>>& permutationCommits,
    std::vector<std::vector<std::vector<Twistpoint>>>& freshPseudonymCommits,
    std::vector<std::vector<std::vector<Twistpoint>>>& freshPseudonymSeedCommits,
    std::vector<std::vector<std::vector<CurveBipoint>>>& serverTallyCommits,
    std::vector<std::vector<std::vector<std::vector<TwistBipoint>>>>& partwayVoteMatrixCommits,
    std::vector<std::vector<std::vector<std::vector<TwistBipoint>>>>& finalVoteMatrixCommits,
    Twistpoint& nextGenerator)
{
    nextSeed.set_random();

    std::vector<std::vector<Twistpoint>> currPermutationCommits;
    std::vector<std::vector<Twistpoint>> currFreshPseudonymCommits;
    std::vector<std::vector<Twistpoint>> currFreshPseudonymSeedCommits;
    std::vector<std::vector<CurveBipoint>> currServerTallyCommits;
    std::vector<std::vector<std::vector<TwistBipoint>>> currPartwayVoteMatrixCommits;
    std::vector<std::vector<std::vector<TwistBipoint>>> currFinalVoteMatrixCommits;
    std::vector<std::vector<Twistpoint>> currUserTallyMaskCommits;
    std::vector<std::vector<Twistpoint>> currUserTallyMessageCommits;
    std::vector<std::vector<Twistpoint>> currUserTallySeedCommits;
    pi.push_back(epoch_calculations(currPermutationCommits, currFreshPseudonymCommits, currFreshPseudonymSeedCommits, currServerTallyCommits, currPartwayVoteMatrixCommits, currFinalVoteMatrixCommits, currUserTallyMaskCommits, currUserTallyMessageCommits, currUserTallySeedCommits, nextSeed, nextGenerator, false));

    permutationCommits.push_back(currPermutationCommits);
    freshPseudonymCommits.push_back(currFreshPseudonymCommits);
    freshPseudonymSeedCommits.push_back(currFreshPseudonymSeedCommits);
    serverTallyCommits.push_back(currServerTallyCommits);
    partwayVoteMatrixCommits.push_back(currPartwayVoteMatrixCommits);
    finalVoteMatrixCommits.push_back(currFinalVoteMatrixCommits);

    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(
    const std::vector<Proof>& generatorProof,
    std::vector<std::vector<std::vector<Proof>>>& pi,
    std::vector<std::vector<std::vector<Twistpoint>>>& permutationCommits,
    std::vector<std::vector<std::vector<Twistpoint>>>& freshPseudonymCommits,
    std::vector<std::vector<std::vector<Twistpoint>>>& freshPseudonymSeedCommits,
    std::vector<std::vector<std::vector<CurveBipoint>>>& serverTallyCommits,
    std::vector<std::vector<std::vector<std::vector<TwistBipoint>>>>& partwayVoteMatrixCommits,
    std::vector<std::vector<std::vector<std::vector<TwistBipoint>>>>& finalVoteMatrixCommits,
    std::vector<std::vector<std::vector<Twistpoint>>>& userTallyMaskCommits,
    std::vector<std::vector<std::vector<Twistpoint>>>& userTallyMessageCommits,
    std::vector<std::vector<std::vector<Twistpoint>>>& userTallySeedCommits,
    const Twistpoint& 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<Twistpoint>> currPermutationCommits;
    std::vector<std::vector<Twistpoint>> currFreshPseudonymCommits;
    std::vector<std::vector<Twistpoint>> currFreshPseudonymSeedCommits;
    std::vector<std::vector<CurveBipoint>> currServerTallyCommits;
    std::vector<std::vector<std::vector<TwistBipoint>>> currPartwayVoteMatrixCommits;
    std::vector<std::vector<std::vector<TwistBipoint>>> currFinalVoteMatrixCommits;
    std::vector<std::vector<Twistpoint>> currUserTallyMaskCommits;
    std::vector<std::vector<Twistpoint>> currUserTallyMessageCommits;
    std::vector<std::vector<Twistpoint>> currUserTallySeedCommits;
    pi.push_back(epoch_calculations(currPermutationCommits, currFreshPseudonymCommits, currFreshPseudonymSeedCommits, currServerTallyCommits, currPartwayVoteMatrixCommits, currFinalVoteMatrixCommits, currUserTallyMaskCommits, currUserTallyMessageCommits, currUserTallySeedCommits, inverseSeed, nextGenerator, true));

    permutationCommits.push_back(currPermutationCommits);
    freshPseudonymCommits.push_back(currFreshPseudonymCommits);
    freshPseudonymSeedCommits.push_back(currFreshPseudonymSeedCommits);
    serverTallyCommits.push_back(currServerTallyCommits);
    partwayVoteMatrixCommits.push_back(currPartwayVoteMatrixCommits);
    finalVoteMatrixCommits.push_back(currFinalVoteMatrixCommits);
    userTallyMaskCommits.push_back(currUserTallyMaskCommits);
    userTallyMessageCommits.push_back(currUserTallyMessageCommits);
    userTallySeedCommits.push_back(currUserTallySeedCommits);

    currentSeed = nextSeed;
}

/*
 * EPOCH HELPERS
 */

std::vector<std::vector<Proof>> PrsonaServer::epoch_calculations(
    std::vector<std::vector<Twistpoint>>& permutationCommits,
    std::vector<std::vector<Twistpoint>>& freshPseudonymCommits,
    std::vector<std::vector<Twistpoint>>& freshPseudonymSeedCommits,
    std::vector<std::vector<CurveBipoint>>& serverTallyCommits,
    std::vector<std::vector<std::vector<TwistBipoint>>>& partwayVoteMatrixCommits,
    std::vector<std::vector<std::vector<TwistBipoint>>>& finalVoteMatrixCommits,
    std::vector<std::vector<Twistpoint>>& userTallyMaskCommits,
    std::vector<std::vector<Twistpoint>>& userTallyMessageCommits,
    std::vector<std::vector<Twistpoint>>& userTallySeedCommits,
    const Scalar& power,
    const Twistpoint& nextGenerator,
    bool doUserTallies)
{
    std::vector<std::vector<Proof>> retval;

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

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

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

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

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

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

    retval.push_back(generate_proof_of_reordering<CurveBipoint>(permutations, permutationSeeds, serverTallySeeds, previousVoteTallies, permutationCommits, serverTallyCommits, bgnSystem.get_public_key().get_bipoint_curvegen(), bgnSystem.get_public_key().get_bipoint_curve_subgroup_gen()));

    std::vector<std::vector<std::vector<Scalar>>> partwayVoteMatrixSeeds;
    std::vector<std::vector<std::vector<Scalar>>> finalVoteMatrixSeeds;
    partwayVoteMatrixCommits.clear();
    partwayVoteMatrixCommits = generate_vote_tensor(permutations, voteMatrix, partwayVoteMatrixSeeds, false);

    std::vector<std::vector<TwistBipoint>> partialVoteMatrix = calculate_next_vote_matrix(partwayVoteMatrixCommits);

    finalVoteMatrixCommits.clear();
    finalVoteMatrixCommits = generate_vote_tensor(permutations, partialVoteMatrix, finalVoteMatrixSeeds, true);

    generate_vote_tensor_proofs(retval, permutations, permutationSeeds, partwayVoteMatrixSeeds, voteMatrix, permutationCommits, partwayVoteMatrixCommits, false);

    generate_vote_tensor_proofs(retval, permutations, permutationSeeds, finalVoteMatrixSeeds, partialVoteMatrix, permutationCommits, finalVoteMatrixCommits, true);

    if (doUserTallies)
    {
        std::vector<Twistpoint> userTallyMasks;
        std::vector<Twistpoint> userTallyMessages;
        std::vector<std::vector<Scalar>> userTallySeeds;
        userTallyMaskCommits.clear();
        userTallyMessageCommits.clear();
        userTallySeedCommits.clear();
        generate_user_tally_matrix(permutations, power, nextGenerator, currentPseudonyms, userTallyMasks, userTallyMaskCommits, userTallyMessages, userTallyMessageCommits, userTallySeeds, userTallySeedCommits);

        retval.push_back(generate_user_tally_proofs(permutations, power, nextGenerator, permutationSeeds, userTallySeeds, currentPseudonyms, userTallyMasks, userTallyMessages, permutationCommits, userTallyMaskCommits, userTallyMessageCommits, userTallySeedCommits));
    }

    // Replace internal values
    update_data(freshPseudonymCommits, serverTallyCommits, finalVoteMatrixCommits, userTallyMaskCommits, userTallyMessageCommits);

    return retval;
}

bool PrsonaServer::accept_epoch_updates(
    const std::vector<std::vector<Proof>>& pi,
    const std::vector<std::vector<Twistpoint>>& permutationCommits,
    const std::vector<std::vector<Twistpoint>>& freshPseudonymCommits,
    const std::vector<std::vector<Twistpoint>>& freshPseudonymSeedCommits,
    const std::vector<std::vector<CurveBipoint>>& serverTallyCommits,
    const std::vector<std::vector<std::vector<TwistBipoint>>>& partwayVoteMatrixCommits,
    const std::vector<std::vector<std::vector<TwistBipoint>>>& finalVoteMatrixCommits,
    const std::vector<std::vector<Twistpoint>>& userTallyMaskCommits,
    const std::vector<std::vector<Twistpoint>>& userTallyMessageCommits,
    const std::vector<std::vector<Twistpoint>>& userTallySeedCommits,
    const Twistpoint& nextGenerator,
    bool doUserTallies)
{
    bool verification;

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

    if (pi.empty())
        return false;

    size_t currOffset = 0;

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

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

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

    verification = verify_vote_tensor_proofs(pi, currOffset, voteMatrix, permutationCommits, partwayVoteMatrixCommits, false);
    currOffset += voteMatrix.size();
    if (!verification)
    {
        std::cerr << "Could not verify first half vote matrix." << std::endl;
        return false;
    }

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

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

        verification = verify_user_tally_proofs(pi[currOffset], nextGenerator, currentPseudonyms, userTallyMasks, userTallyMessages, permutationCommits, userTallyMaskCommits, userTallyMessageCommits, userTallySeedCommits);
        currOffset++;
        if (!verification)
        {
            std::cerr << "Could not verify user tallies." << std::endl;
            return false;
        }
    }

    verification = update_data(freshPseudonymCommits, serverTallyCommits, finalVoteMatrixCommits, userTallyMaskCommits, userTallyMessageCommits);

    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<Twistpoint> 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);

    return retval;
}

std::vector<std::vector<Twistpoint>> PrsonaServer::generate_commitment_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    std::vector<std::vector<Scalar>>& seeds) const
{
    std::vector<std::vector<Twistpoint>> retval;
    Twistpoint g = EL_GAMAL_GENERATOR;
    Twistpoint 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<Twistpoint> currRow;

        size_t last = permutations[i].size() - 1;
        for (size_t j = 0; j < permutations[i].size(); j++)
        {
            Twistpoint 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<Twistpoint>> PrsonaServer::generate_pseudonym_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    const Scalar& power,
    std::vector<std::vector<Scalar>>& seeds,
    std::vector<std::vector<Twistpoint>>& seedCommits) const
{
    return generate_reordered_plus_power_matrix<Twistpoint>(permutations, power, currentPseudonyms, seeds, seedCommits, elGamalBlindGenerator);
}

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

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

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

        std::vector<TwistBipoint> 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<TwistBipoint>(permutations, inputRow, currSeeds, bgnSystem.get_public_key().get_bipoint_twist_subgroup_gen(), false));

        seeds.push_back(currSeeds);
    }

    return retval;
}

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

    for (size_t i = 0; i < voteTensor.size(); i++)
    {
        std::vector<TwistBipoint> currRow;
        for (size_t j = 0; j < voteTensor[i].size(); j++)
        {
            TwistBipoint 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<TwistBipoint>>& currMatrix,
    const std::vector<std::vector<Twistpoint>>& permutationCommits,
    const std::vector<std::vector<std::vector<TwistBipoint>>>& matrixCommits,
    bool inverted) const
{
    for (size_t i = 0; i < currMatrix.size(); i++)
    {
        std::vector<TwistBipoint> 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<TwistBipoint>(permutations, permutationSeeds, matrixSeeds[i], inputRow, permutationCommits, matrixCommits[i], bgnSystem.get_public_key().get_bipoint_twistgen(), bgnSystem.get_public_key().get_bipoint_twist_subgroup_gen()));
    }
}

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

    for (size_t i = 0; i < currMatrix.size(); i++)
    {
        std::vector<TwistBipoint> 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<TwistBipoint>(pi[whichProof], inputRow, permutationCommits, matrixCommits[i], bgnSystem.get_public_key().get_bipoint_twistgen(), bgnSystem.get_public_key().get_bipoint_twist_subgroup_gen());
    }

    return retval;
}

void PrsonaServer::generate_user_tally_matrix(
    const std::vector<std::vector<Scalar>>& permutations,
    const Scalar& power,
    const Twistpoint& nextGenerator,
    const std::vector<Twistpoint>& currPseudonyms,
    std::vector<Twistpoint>& masks,
    std::vector<std::vector<Twistpoint>>& maskCommits,
    std::vector<Twistpoint>& messages,
    std::vector<std::vector<Twistpoint>>& messageCommits,
    std::vector<std::vector<Scalar>>& userTallySeeds,
    std::vector<std::vector<Twistpoint>>& userTallySeedCommits) const
{
    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);
    }

    maskCommits.clear();
    messageCommits.clear();
    userTallySeeds.clear();
    userTallySeedCommits.clear();

    for (size_t i = 0; i < permutations.size(); i++)
    {
        std::vector<Scalar> currSeeds;
        std::vector<Twistpoint> currRow;
        for (size_t j = 0; j < permutations[i].size(); j++)
        {
            currSeeds.push_back(Scalar(0));
            currRow.push_back(Twistpoint());
        }
        userTallySeeds.push_back(currSeeds);
        maskCommits.push_back(currRow);
        messageCommits.push_back(currRow);
        userTallySeedCommits.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 (j != last)
            {
                userTallySeeds[i][j].set_random();
                userTallySeeds[i][last] = userTallySeeds[i][last] - userTallySeeds[i][j];
            }

            maskCommits[i][j] = masks[j] * permutations[j][i] * power +
                currPseudonyms[j] * power * permutations[j][i] * userTallySeeds[i][j] +
                elGamalBlindGenerator * userTallySeeds[i][j];

            messageCommits[i][j] = messages[j] * permutations[j][i] +
                nextGenerator * permutations[j][i] * userTallySeeds[i][j] +
                elGamalBlindGenerator * userTallySeeds[i][j];

            userTallySeedCommits[i][j] = EL_GAMAL_GENERATOR * userTallySeeds[i][j];
        }
    }
}

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<Twistpoint>>& 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<Twistpoint> currSeedCommits;
        for (size_t j = 0; j < permutations[i].size(); j++)
        {
            currPermutations.push_back(permutations[i][j] * power);
            currSeedCommits.push_back(Twistpoint());
        }
        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<Twistpoint>& 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<Twistpoint>>& freshPseudonymCommits,
    const std::vector<std::vector<CurveBipoint>>& serverTallyCommits,
    const std::vector<std::vector<std::vector<TwistBipoint>>>& voteMatrixCommits,
    const std::vector<std::vector<Twistpoint>>& userTallyMaskCommits,
    const std::vector<std::vector<Twistpoint>>& userTallyMessageCommits)
{
    std::vector<Twistpoint> newPseudonyms;
    std::vector<CurveBipoint> newVoteTallies;
    std::vector<EGCiphertext> newUserTallies;

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

        Twistpoint userTallyMask, userTallyMessage;
        if (!userTallyMaskCommits.empty())
        {
            userTallyMask = userTallyMaskCommits[i][0];
            userTallyMessage = userTallyMessageCommits[i][0];
        }

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

            if (!userTallyMaskCommits.empty())
            {
                userTallyMask = userTallyMask + userTallyMaskCommits[i][j];
                userTallyMessage = userTallyMessage + userTallyMessageCommits[i][j];
            }
        }

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

        if (!userTallyMaskCommits.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<Twistpoint> 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
 */

void PrsonaServer::export_new_user_update(
    std::vector<CurveBipoint>& otherPreviousVoteTallies,
    std::vector<Twistpoint>& otherCurrentPseudonyms,
    std::vector<EGCiphertext>& otherCurrentUserEncryptedTallies,
    std::vector<std::vector<TwistBipoint>>& otherVoteMatrix) const
{
    otherPreviousVoteTallies = previousVoteTallies;
    otherCurrentPseudonyms = currentPseudonyms;
    otherCurrentUserEncryptedTallies = currentUserEncryptedTallies;
    otherVoteMatrix = voteMatrix;
}

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

    Twistpoint shortTermPublicKey = otherCurrentPseudonyms[newIndex];

    bool flag = verify_proof_of_added_user(pi, currentFreshGenerator, shortTermPublicKey, bgnSystem.get_public_key().get_bipoint_twistgen(), bgnSystem.get_public_key().get_bipoint_twist_subgroup_gen(), bgnSystem.get_public_key().get_bipoint_curvegen(), bgnSystem.get_public_key().get_bipoint_curve_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<Twistpoint> newPseudonyms;
    std::vector<CurveBipoint> newVoteTallies;
    std::vector<EGCiphertext> newUserEncryptedTallies;
    std::vector<std::vector<TwistBipoint>> 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<TwistBipoint> 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 Twistpoint& index) const
{
    return PrsonaBase::binary_search(currentPseudonyms, index);
}

/*
 * VALID VOTE PROOFS
 */

bool PrsonaServer::verify_vote_proof(
    const std::vector<Proof>& pi,
    const std::vector<TwistBipoint>& oldVotes,
    const std::vector<TwistBipoint>& newVotes,
    const Twistpoint& shortTermPublicKey) const
{
    const BGNPublicKey& pubKey = bgnSystem.get_public_key();

    return PrsonaBase::verify_vote_proof(pubKey.get_bipoint_twistgen(), pubKey.get_bipoint_twist_subgroup_gen(), pi, oldVotes, newVotes, currentFreshGenerator, shortTermPublicKey);
}

void PrsonaServer::print_scores(
    const std::vector<CurveBipoint>& 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;
}