70 lines
2.5 KiB
C++
70 lines
2.5 KiB
C++
|
#include <cstddef>
|
||
|
|
#include <cstdint>
|
||
|
|
#include <iostream>
|
||
|
|
#include <vector>
|
||
|
|
|
||
|
|
#include "dpf.hpp"
|
||
|
|
#include "dpf/app_flow.hpp"
|
||
|
|
#include "dpf/app_plans.hpp"
|
||
|
|
|
||
|
|
// Waldo, the FSS steps (Dauterman, Fang, Crooks, and Popa, S&P 2022). A
|
||
|
|
// private time-series database. The store is append-only: a new event writes
|
||
|
|
// a fresh point and never updates an old one. A range/threshold aggregate
|
||
|
|
// uses the comparison (DCF) channel: the parties dot the per-timestamp
|
||
|
|
// comparison shares with a public value column, so a SUM over the timestamps
|
||
|
|
// past a *secret* threshold reveals neither the threshold nor the matches.
|
||
|
|
//
|
||
|
|
// c++ -std=c++17 -march=native -I include -I thirdparty \
|
||
|
|
// examples/applications/waldo.cpp
|
||
|
|
|
||
|
|
int main()
|
||
|
|
{
|
||
|
|
constexpr std::size_t horizon = 256; // timestamp domain
|
||
|
|
|
||
|
|
// Append-only writes. Each event is a unit DPF at its timestamp; the
|
||
|
|
// servers fold it into their subtractive value shares. Never an update.
|
||
|
|
std::vector<std::uint64_t> col0(horizon, 0), col1(horizon, 0);
|
||
|
|
const std::pair<std::uint8_t, std::uint64_t> events[] = {
|
||
|
|
{30, 5}, {90, 8}, {200, 3}};
|
||
|
|
for (auto [ts, val] : events)
|
||
|
|
{
|
||
|
|
auto [k0, k1] = dpf::make_dpf(ts, val);
|
||
|
|
dpf::eval_full_add_into(col0, k0);
|
||
|
|
dpf::eval_full_add_into(col1, k1);
|
||
|
|
}
|
||
|
|
if (col0[90] - col1[90] != 8 || col0[30] - col1[30] != 5)
|
||
|
|
{
|
||
|
|
std::cerr << "waldo append\n";
|
||
|
|
return 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Public per-timestamp magnitudes (metadata the response consumes).
|
||
|
|
std::vector<std::uint64_t> magnitude(horizon, 0);
|
||
|
|
for (auto [ts, val] : events)
|
||
|
|
magnitude[ts] = val;
|
||
|
|
|
||
|
|
// Private-threshold aggregate: SUM of magnitudes at timestamps > T, with
|
||
|
|
// T secret. Key a gt comparison at T and dot its per-timestamp shares
|
||
|
|
// with the public magnitude column in one comparison walk.
|
||
|
|
constexpr std::uint8_t secret_T = 50;
|
||
|
|
auto [c0, c1] = dpf::make_dpf(secret_T, dpf::gt(std::uint64_t{1}));
|
||
|
|
const auto h0 = dpf::eval_full_inner_product(dpf::cmp, c0, magnitude);
|
||
|
|
const auto h1 = dpf::eval_full_inner_product(dpf::cmp, c1, magnitude);
|
||
|
|
const auto after = dpf::reconstruct_cmp_halves(h0, h1).raw();
|
||
|
|
// Timestamps 90 and 200 are past T=50: 8 + 3 = 11.
|
||
|
|
if (after != 11)
|
||
|
|
{
|
||
|
|
std::cerr << "waldo threshold aggregate " << after << "\n";
|
||
|
|
return 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
{
|
||
|
|
if (int rc = dpf::app::run_measured("waldo",
|
||
|
|
dpf::protocol::fss_cmp_plan(0), 8))
|
||
|
|
return rc;
|
||
|
|
}
|
||
|
|
|
||
|
|
std::cout << after << "\n";
|
||
|
|
return 0;
|
||
|
|
}
|