question about OKVS

[Fix3dP0int]

Is the definition of OKVS that OKVS(x) = random value where x is not in the key-value pair? As the below code shows, in paxos.init(n, binSize, w, ssp, dt, block(0, 0)); does the block(0, 0) mean the random value will equal (0, 0)? Because I need to do PSI inputing something decoded, and I found that there are many zeros in the list of values decoded. Please help me. Thanks!

void encode(const std::vector<block>& key, const std::vector<block>& value, std::vector<block>& OKVStable){
    u64 n = key.size();
    u64 w = 3, ssp = 40, nt = 4, binSize = 1 << 15;
    auto dt = PaxosParam::GF128;
    u64 baxosSize;
    {
        Baxos paxos;
        paxos.init(n, binSize, w, ssp, dt, oc::ZeroBlock);
        baxosSize = paxos.size();
    }
    OKVStable.resize(baxosSize);
    Baxos paxos;
    paxos.init(n, binSize, w, ssp, dt, block(0, 0));
    paxos.solve<block>(key, value, OKVStable, nullptr, nt);
}

void decode(const std::vector<block>& key, std::vector<block>& value, const std::vector<block>& OKVStable){
    u64 n = key.size();
    u64 w = 3, ssp = 40, nt = 4, binSize = 1 << 15;
    auto dt = PaxosParam::GF128;
    u64 baxosSize;
    {
        Baxos paxos;
        paxos.init(n, binSize, w, ssp, dt, oc::ZeroBlock);
        baxosSize = paxos.size();
    }
    Baxos paxos;
    paxos.init(n, binSize, w, ssp, dt, block(0, 0));
    paxos.decode<block>(key, value, OKVStable, nt);
}

[Fix3dP0int]

If it is right, how can I change the code to get the random value such that decoding is still working?

[ladnir]

That's is the randomness seed used to define the okvs matrix. In practice that should be random and chosen by the encoder.

There are two version, one that is randomized and one that isn't. The one that isn't fills the empty positions with zeros. The other fills with random values. If you want it to be randomized, solve(...) takes a prng pointer. Pass a non null prng. This prng should use a secret seed, eg sysRandomSeed() .

[Fix3dP0int]

Thanks! I change the encode function like below. It works successfully for a small amount of data. But when I test it for about million data, it SOMETIMES happens the error Duplicate keys were detected. So I guess that it is because the PRNG generated the duplicate values. Is the error really for this reason? Or just other reasons that I havn't found? the overview of my algorithm is that one party get the OKVS from the other party and he decode the OKVS inputting his own set. Then he will encode the key-value pair {his own set, decoded value}. So If the PRNG generate the same values, encoding will raise the error for duplicate keys. If it is right, do I have any method to avoid it? Or it should be thought as one acceptable probabilistic error? Please forgive my poor English. Hope that I made it clear.

void encode(const std::vector<block>& key, const std::vector<block>& value, std::vector<block>& OKVStable){
    PRNG prng(oc::sysRandomSeed()); 
    u64 n = key.size();
    u64 w = 3, ssp = 40, nt = 4, binSize = 1 << 15;
    auto dt = PaxosParam::GF128;
    u64 baxosSize;
    {
        Baxos paxos;
        paxos.init(n, binSize, w, ssp, dt, oc::ZeroBlock);
        baxosSize = paxos.size();
    }
    OKVStable.resize(baxosSize);
    Baxos paxos;
    paxos.init(n, binSize, w, ssp, dt, block(0, 0));
    paxos.solve<block>(key, value, OKVStable, &prng, nt);
}

[ladnir]

Your input key has duplicate. That's not allowed.

[Fix3dP0int]

OK. Thanks for replying. I have identified the cause of the error as a synchronization issue with the code I wrote myself.