libdpf/test/tests/verifiable_test.cpp

#include <gtest/gtest.h>
#include <tuple>

#include <array>
#include <cstdint>
#include <cstring>
#include <vector>

#include "dpf.hpp"
#include "grotto/offset_horner.hpp"
#include "grotto/offset_poly.hpp"
#include "grotto/carry.hpp"

using Interior = dpf::prg::aes128;
using Exterior = dpf::prg::aes128;

TEST(Verifiable, HonestPointAccepts)
{
    using Input = std::uint8_t;
    const Input alpha = 0x2a;
    const std::uint64_t beta = 7;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(alpha, beta, dpf::verifiable{});
    EXPECT_TRUE(decltype(k0)::is_verifiable);
    EXPECT_FALSE(decltype(k0)::is_multilevel);

    dpf::proof_token pi0{}, pi1{};
    const auto y0 = *dpf::eval_point(k0, alpha, dpf::prove(pi0));
    const auto y1 = *dpf::eval_point(k1, alpha, dpf::prove(pi1));
    EXPECT_EQ(dpf::reconstruct(y0, y1), beta);
    EXPECT_TRUE(dpf::verify(pi0, pi1));

    dpf::proof_token q0{}, q1{};
    const Input other = static_cast<Input>(alpha ^ 1);
    EXPECT_EQ(dpf::reconstruct(*dpf::eval_point(k0, other, dpf::prove(q0)),
                  *dpf::eval_point(k1, other, dpf::prove(q1))),
        0);
    EXPECT_TRUE(dpf::verify(q0, q1));
}

TEST(Verifiable, TamperedCwRejects)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{3},
        std::uint64_t{1}, dpf::verifiable{});

    // Flip every correction seed so an on-path level with control bit 1
    // mixes the tamper (a single level-0 flip is invisible when t=0 there).
    for (auto & cs : const_cast<typename std::decay_t<decltype(k0)>::correction_seeds_array &>(
             k0.correction_seeds()))
    {
        cs[0] = simde_mm_xor_si128(cs[0], simde_mm_set1_epi8(1));
    }

    dpf::proof_token pi0{}, pi1{};
    (void)*dpf::eval_point(k0, Input{3}, dpf::prove(pi0));
    (void)*dpf::eval_point(k1, Input{3}, dpf::prove(pi1));
    EXPECT_FALSE(dpf::verify(pi0, pi1));
}

TEST(Verifiable, BatchVerify)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{1},
        std::uint64_t{9}, dpf::verifiable{});

    std::vector<dpf::proof_token> left, right;
    for (Input x = 0; x < 8; ++x)
    {
        dpf::proof_token a{}, b{};
        (void)*dpf::eval_point(k0, x, dpf::prove(a));
        (void)*dpf::eval_point(k1, x, dpf::prove(b));
        left.push_back(a);
        right.push_back(b);
    }
    EXPECT_TRUE(dpf::verify_batch(left, right));
    left[2][0] = simde_mm_xor_si128(left[2][0], simde_mm_set1_epi8(0xff));
    EXPECT_FALSE(dpf::verify_batch(left, right));
    // Restore and swap second halves of two slots — must still reject.
    left[2][0] = simde_mm_xor_si128(left[2][0], simde_mm_set1_epi8(0xff));
    std::swap(left[1][1], left[3][1]);
    EXPECT_FALSE(dpf::verify_batch(left, right));
    right.pop_back();
    EXPECT_FALSE(dpf::verify_batch(left, right));
}

TEST(Verifiable, HalfTreeXorPayload)
{
    using Input = std::uint16_t;
    using Ht = dpf::prg::aes128_ccr;
    const Input alpha = 0x0101;
    auto [k0, k1] = dpf::make_dpf<Ht, Ht>(alpha,
        dpf::xor_wrapper<std::uint64_t>{0xdeadbeefull}, dpf::verifiable{});
    EXPECT_TRUE(decltype(k0)::tree::is_half_tree);

    dpf::proof_token pi0{}, pi1{};
    const auto y0 = *dpf::eval_point(k0, alpha, dpf::prove(pi0));
    const auto y1 = *dpf::eval_point(k1, alpha, dpf::prove(pi1));
    EXPECT_EQ(dpf::reconstruct(y0, y1), dpf::xor_wrapper<std::uint64_t>{0xdeadbeefull});
    EXPECT_TRUE(dpf::verify(pi0, pi1));
}

TEST(Verifiable, SamePublicPart)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{5},
        std::uint64_t{2}, dpf::verifiable{});
    EXPECT_TRUE(dpf::same_public_part(k0, k1));

    auto & cw = const_cast<typename std::decay_t<decltype(k0)>::interior_node &>(
        k0.correction_words()[0]);
    cw = simde_mm_xor_si128(cw, simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::same_public_part(k0, k1));
}

TEST(Verifiable, DefaultKeyUnchangedLayout)
{
    using Input = std::uint8_t;
    auto [a0, a1] = dpf::make_dpf<Interior, Exterior>(Input{1}, std::uint64_t{3});
    auto [b0, b1] = dpf::make_dpf<Interior, Exterior>(Input{1}, std::uint64_t{3},
        dpf::verifiable{});
    EXPECT_FALSE(decltype(a0)::is_verifiable);
    EXPECT_TRUE(decltype(b0)::is_verifiable);
    EXPECT_EQ(sizeof(a0.correction_words()), sizeof(b0.correction_words()));
    EXPECT_EQ(std::tuple_size_v<typename decltype(a0)::correction_seeds_array>, 0u);
    EXPECT_GT(std::tuple_size_v<typename decltype(b0)::correction_seeds_array>, 0u);
}

TEST(Extractable, Fp61ReconstructAndSketch)
{
    using Input = std::uint8_t;
    const Input alpha = 0x11;
    const dpf::fp61 beta{42};
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(alpha, beta,
        dpf::extractable{}, dpf::verifiable{});
    EXPECT_TRUE(decltype(k0)::is_extractable);
    EXPECT_TRUE(decltype(k0)::is_verifiable);
    EXPECT_TRUE(dpf::same_public_part(k0, k1));

    const auto y0 = *dpf::eval_point(k0, alpha);
    const auto y1 = *dpf::eval_point(k1, alpha);
    EXPECT_EQ(dpf::reconstruct(y0, y1), beta);

    std::array<Input, 4> pts{0x10, 0x11, 0x12, 0x13};
    std::array<dpf::fp61, 4> r{
        dpf::fp61{3}, dpf::fp61{5}, dpf::fp61{7}, dpf::fp61{11}};
    std::array<dpf::fp61, 4> s0{}, s1{};
    for (std::size_t i = 0; i < pts.size(); ++i)
    {
        s0[i] = (*dpf::eval_point(k0, pts[i])).raw();
        s1[i] = (*dpf::eval_point(k1, pts[i])).raw();
    }
    auto sk0 = dpf::sketch_fold(s0, r);
    auto sk1 = dpf::sketch_fold(s1, r);
    EXPECT_TRUE(dpf::sketch_verify(sk0, sk1));

    // Two hot points: forge by XORing a second beta into another share.
    s0[0] = s0[0] + beta;
    sk0 = dpf::sketch_fold(s0, r);
    sk1 = dpf::sketch_fold(s1, r);
    EXPECT_FALSE(dpf::sketch_verify(sk0, sk1));
}

TEST(Extractable, IncrementalPrefix)
{
    using Input = std::uint16_t;
    const Input alpha = 0x00ab;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(alpha,
        dpf::at<8>(dpf::fp61{1}), dpf::extractable{});
    EXPECT_TRUE(decltype(k0)::is_extractable);
    EXPECT_TRUE(decltype(k0)::is_multilevel);

    const auto p0 = *dpf::eval_point(dpf::out<0>, k0, alpha);
    const auto p1 = *dpf::eval_point(dpf::out<0>, k1, alpha);
    EXPECT_EQ(dpf::reconstruct(p0, p1), dpf::fp61{1});
}

TEST(Verifiable, IntervalProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{0x20},
        std::uint64_t{1}, dpf::verifiable{});
    dpf::proof_token a{}, b{};
    dpf::prove_interval(k0, Input{0x1c}, Input{0x24}, dpf::prove(a));
    dpf::prove_interval(k1, Input{0x1c}, Input{0x24}, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
}

TEST(Verifiable, IntervalEvalProveMatchesProveInterval)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{0x20},
        std::uint64_t{7}, dpf::verifiable{});
    dpf::proof_token p0{}, p1{}, e0{}, e1{};
    dpf::prove_interval(k0, Input{0x10}, Input{0x18}, dpf::prove(p0));
    dpf::prove_interval(k1, Input{0x10}, Input{0x18}, dpf::prove(p1));
    EXPECT_TRUE(dpf::verify(p0, p1));

    auto buf0 = dpf::make_output_buffer_for_interval(k0, Input{0x10}, Input{0x18});
    auto buf1 = dpf::make_output_buffer_for_interval(k1, Input{0x10}, Input{0x18});
    dpf::eval_interval(k0, Input{0x10}, Input{0x18}, buf0, dpf::prove(e0));
    dpf::eval_interval(k1, Input{0x10}, Input{0x18}, buf1, dpf::prove(e1));
    EXPECT_TRUE(dpf::verify(e0, e1));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(p0, e0));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(p1, e1));

    // Tamper party 0's token after an honest fold.
    e0[0] = simde_mm_xor_si128(e0[0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(e0, e1));
}

TEST(Verifiable, FullProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{0x55},
        std::uint64_t{3}, dpf::verifiable{});
    dpf::proof_token a{}, b{};
    dpf::prove_full(k0, dpf::prove(a));
    dpf::prove_full(k1, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
    a[0] = simde_mm_xor_si128(a[0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(a, b));
}

TEST(Verifiable, SequenceProveIntervalCovers)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{0x22},
        std::uint64_t{9}, dpf::verifiable{});
    // Two runs: [0x10,0x12] and [0x20,0x21], plus an isolated 0x30.
    const Input xs[] = {0x10, 0x11, 0x12, 0x20, 0x21, 0x30};
    dpf::proof_token a{}, b{};
    dpf::prove_sequence(k0, std::begin(xs), std::end(xs), dpf::prove(a));
    dpf::prove_sequence(k1, std::begin(xs), std::end(xs), dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));

    // eval_sequence(..., prove) uses the same interval-run covers.
    auto buf0 = dpf::make_output_buffer_for_subsequence(k0, std::begin(xs), std::end(xs));
    auto buf1 = dpf::make_output_buffer_for_subsequence(k1, std::begin(xs), std::end(xs));
    dpf::proof_token e0{}, e1{};
    dpf::eval_sequence(k0, std::begin(xs), std::end(xs), buf0, dpf::prove(e0));
    dpf::eval_sequence(k1, std::begin(xs), std::end(xs), buf1, dpf::prove(e1));
    EXPECT_TRUE(dpf::verify(e0, e1));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(a, e0));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(b, e1));
}

TEST(Verifiable, DoernerShelatProve)
{
    using Input = std::uint8_t;
    const Input alpha = 0x44;
    const std::uint64_t beta = 5;
    Input x0 = 0x12;
    Input x1 = static_cast<Input>(alpha ^ x0);
    struct Pad
    {
        std::uint64_t n = 1;
        simde__m128i block()
        {
            auto v = simde_mm_set_epi64x(static_cast<long long>(n),
                static_cast<long long>(n * 9 + 3));
            n += 2;
            return v;
        }
        std::uint8_t bit() { return static_cast<std::uint8_t>(n++ & 1u); }
    };
    HEDLEY_PRAGMA(GCC diagnostic push)
    HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
    dpf::ds_randomness<simde__m128i (*)(), Pad> rng{
        dpf::uniform_sample<simde__m128i>, Pad{}};
    HEDLEY_PRAGMA(GCC diagnostic pop)
    auto [s0, s1] = dpf::make_dpf_doerner_shelat<Interior, Exterior>(
        x0, x1, rng, beta, dpf::verifiable{});

    EXPECT_TRUE(decltype(s0)::is_verifiable);
    dpf::proof_token a{}, b{};
    EXPECT_EQ(dpf::reconstruct(*dpf::eval_point(s0, alpha, dpf::prove(a)),
                  *dpf::eval_point(s1, alpha, dpf::prove(b))),
        beta);
    EXPECT_TRUE(dpf::verify(a, b));
}

TEST(Verifiable, CmpIntervalProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x20}, dpf::lt(std::uint64_t{1}),
        dpf::verifiable{});
    dpf::proof_token a{}, b{};
    dpf::prove_cmp_interval(k0, Input{0x10}, Input{0x28}, dpf::prove(a));
    dpf::prove_cmp_interval(k1, Input{0x10}, Input{0x28}, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));

    auto buf0 = dpf::make_output_buffer(dpf::cmp, k0, Input{0x10}, Input{0x28});
    auto buf1 = dpf::make_output_buffer(dpf::cmp, k1, Input{0x10}, Input{0x28});
    dpf::proof_token e0{}, e1{};
    dpf::eval_interval(dpf::cmp, k0, Input{0x10}, Input{0x28}, buf0, dpf::prove(e0));
    dpf::eval_interval(dpf::cmp, k1, Input{0x10}, Input{0x28}, buf1, dpf::prove(e1));
    EXPECT_TRUE(dpf::verify(e0, e1));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(a, e0));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(b, e1));
    e0[0] = simde_mm_xor_si128(e0[0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(e0, e1));
}

TEST(Verifiable, CmpFullAndSequenceProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x55}, dpf::gt(std::uint64_t{1}),
        dpf::verifiable{});
    dpf::proof_token a{}, b{};
    dpf::prove_cmp_full(k0, dpf::prove(a));
    dpf::prove_cmp_full(k1, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));

    const Input xs[] = {0x10, 0x11, 0x20};
    dpf::proof_token s0{}, s1{};
    dpf::prove_cmp_sequence(k0, std::begin(xs), std::end(xs), dpf::prove(s0));
    dpf::prove_cmp_sequence(k1, std::begin(xs), std::end(xs), dpf::prove(s1));
    EXPECT_TRUE(dpf::verify(s0, s1));

    auto buf0 = dpf::make_output_buffer(dpf::cmp, k0, 3);
    auto buf1 = dpf::make_output_buffer(dpf::cmp, k1, 3);
    dpf::proof_token e0{}, e1{};
    dpf::eval_sequence(dpf::cmp, k0, std::begin(xs), std::end(xs), buf0,
        dpf::prove(e0));
    dpf::eval_sequence(dpf::cmp, k1, std::begin(xs), std::end(xs), buf1,
        dpf::prove(e1));
    EXPECT_TRUE(dpf::verify(e0, e1));
}

TEST(Verifiable, CmpInnerProductProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x18}, dpf::lt(std::uint64_t{1}),
        dpf::verifiable{});
    const std::uint64_t w[] = {1, 2, 3, 4};
    dpf::proof_token a{}, b{};
    const auto d0 = dpf::eval_inner_product(dpf::cmp, k0, Input{0x10}, Input{0x13},
        w, dpf::prove(a));
    const auto d1 = dpf::eval_inner_product(dpf::cmp, k1, Input{0x10}, Input{0x13},
        w, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
    (void)d0;
    (void)d1;
}

TEST(Verifiable, IdcfPointProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x2a}, dpf::idcf(dpf::gt(std::uint64_t{1})),
        dpf::verifiable{});
    dpf::proof_token a{}, b{};
    dpf::eval_point(dpf::cmp, k0, Input{0x30}, dpf::prove(a));
    dpf::eval_point(dpf::cmp, k1, Input{0x30}, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
    a[0] = simde_mm_xor_si128(a[0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(a, b));
}

TEST(Verifiable, BlockedCmpPointProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x2a},
        dpf::block_width<4>(dpf::lt(std::uint64_t{1})), dpf::verifiable{});
    EXPECT_GT(decltype(k0)::cmp_block, 0u);
    dpf::proof_token a{}, b{};
    dpf::eval_point(dpf::cmp, k0, Input{0x11}, dpf::prove(a));
    dpf::eval_point(dpf::cmp, k1, Input{0x11}, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));

    // Native key of the same alpha yields a different token domain.
    auto [n0, n1] = dpf::make_dpf(Input{0x2a}, dpf::lt(std::uint64_t{1}),
        dpf::verifiable{});
    dpf::proof_token c{}, d{};
    dpf::eval_point(dpf::cmp, n0, Input{0x11}, dpf::prove(c));
    dpf::eval_point(dpf::cmp, n1, Input{0x11}, dpf::prove(d));
    EXPECT_TRUE(dpf::verify(c, d));
    EXPECT_FALSE(dpf::detail::vdpf::proof_equal(a, c));

    a[0] = simde_mm_xor_si128(a[0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(a, b));
}

TEST(Verifiable, BlockedCmpIntervalProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x20},
        dpf::block_width<4>(dpf::gt(std::uint64_t{1})), dpf::verifiable{});
    dpf::proof_token a{}, b{};
    dpf::prove_cmp_interval(k0, Input{0x1c}, Input{0x24}, dpf::prove(a));
    dpf::prove_cmp_interval(k1, Input{0x1c}, Input{0x24}, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
}

TEST(Verifiable, GenevalTrieProve)
{
    using Input = std::uint8_t;
    const Input alpha = 0x2a;
    Input x0 = 0x11;
    Input x1 = static_cast<Input>(alpha ^ x0);
    struct Pad
    {
        std::uint64_t n = 1;
        simde__m128i block()
        {
            auto v = simde_mm_set_epi64x(static_cast<long long>(n),
                static_cast<long long>(n * 9 + 3));
            n += 2;
            return v;
        }
        void fill(void * p, std::size_t nbytes)
        {
            auto * b = static_cast<unsigned char *>(p);
            for (std::size_t i = 0; i < nbytes; ++i)
                b[i] = static_cast<unsigned char>(n + i * 17);
            n += nbytes;
        }
        std::uint8_t bit() { return static_cast<std::uint8_t>(n++ & 1u); }
    };
    HEDLEY_PRAGMA(GCC diagnostic push)
    HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
    dpf::ds_randomness<simde__m128i (*)(), Pad> rng{
        dpf::uniform_sample<simde__m128i>, Pad{}};
    HEDLEY_PRAGMA(GCC diagnostic pop)
    const Input qs[] = {0x2a, 0x2b};
    auto got = dpf::geneval_point(x0, x1, qs[0], rng, std::uint64_t{7});
    EXPECT_TRUE(dpf::verify(got.proof0, got.proof1));
    got.proof0[0] = simde_mm_xor_si128(got.proof0[0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(got.proof0, got.proof1));
}

TEST(Verifiable, GenevalCmpProve)
{
    using Input = std::uint8_t;
    const Input alpha = 0x30;
    Input x0 = 0x05;
    Input x1 = static_cast<Input>(alpha ^ x0);
    struct Pad
    {
        std::uint64_t n = 1;
        simde__m128i block()
        {
            auto v = simde_mm_set_epi64x(static_cast<long long>(n),
                static_cast<long long>(n * 9 + 3));
            n += 2;
            return v;
        }
        void fill(void * p, std::size_t nbytes)
        {
            auto * b = static_cast<unsigned char *>(p);
            for (std::size_t i = 0; i < nbytes; ++i)
                b[i] = static_cast<unsigned char>(n + i * 17);
            n += nbytes;
        }
        std::uint8_t bit() { return static_cast<std::uint8_t>(n++ & 1u); }
    };
    HEDLEY_PRAGMA(GCC diagnostic push)
    HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
    dpf::ds_randomness<simde__m128i (*)(), Pad> rng{
        dpf::uniform_sample<simde__m128i>, Pad{}};
    HEDLEY_PRAGMA(GCC diagnostic pop)
    const Input ends[] = {0x10, 0x20, 0x40};
    auto got = dpf::geneval_cmp(x0, x1, std::begin(ends), std::end(ends), rng,
        dpf::gt(std::uint64_t{1}));
    EXPECT_TRUE(dpf::verify(got.proof0, got.proof1));
}

TEST(Verifiable, OffsetHornerProve)
{
    using Input = std::uint8_t;
    constexpr std::size_t D = 1;
    const Input center = 12;
    auto mat = grotto::make_offset_horner_keys<Input, D>(center, dpf::verifiable{});
    EXPECT_TRUE(decltype(mat)::is_verifiable);
    const std::vector<Input> knots{0, 10, 50};
    const std::vector<std::array<std::uint64_t, D + 1>> coeff{
        {1, 0}, {0, 2}, {7, 1}};
    const Input eta = 3;
    dpf::proof_token t0[D + 1]{}, t1[D + 1]{};
    const auto v0 = grotto::offset_horner_eval<0, D, Input, true>(
        mat, knots, coeff, eta, t0);
    const auto v1 = grotto::offset_horner_eval<1, D, Input, true>(
        mat, knots, coeff, eta, t1);
    EXPECT_EQ(v0 + v1, grotto::offset_horner_clear<D>(center, knots, coeff, eta));
    for (std::size_t m = 0; m <= D; ++m)
        EXPECT_TRUE(dpf::verify(t0[m], t1[m]));
    t0[0][0] = simde_mm_xor_si128(t0[0][0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(t0[0], t1[0]));
}

TEST(Verifiable, PathPaintLcpProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x2a}, dpf::lcp(std::uint64_t{1}),
        dpf::verifiable{});
    dpf::proof_token a{}, b{};
    dpf::prove_cmp_interval(k0, Input{0x20}, Input{0x2f}, dpf::prove(a));
    dpf::prove_cmp_interval(k1, Input{0x20}, Input{0x2f}, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
    a[0] = simde_mm_xor_si128(a[0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(a, b));
}

TEST(Verifiable, OffsetPolyProve)
{
    using Input = std::uint8_t;
    const Input center = 12;
    auto mat = grotto::make_offset_poly_keys(center, 1, dpf::verifiable{});
    EXPECT_TRUE(mat.verifiable);
    const std::vector<Input> knots{0, 10, 50};
    const std::vector<std::vector<std::uint64_t>> coeff{{1, 0}, {0, 2}, {7, 1}};
    const Input eta = 3;
    dpf::proof_token t0[2]{}, t1[2]{};
    const auto v0 = grotto::offset_poly_eval<0>(mat, knots, coeff, eta, t0);
    const auto v1 = grotto::offset_poly_eval<1>(mat, knots, coeff, eta, t1);
    EXPECT_EQ(v0 + v1, grotto::offset_poly_clear(center, knots, coeff, eta));
    EXPECT_TRUE(dpf::verify(t0[0], t1[0]));
    EXPECT_TRUE(dpf::verify(t0[1], t1[1]));
    t0[1][0] = simde_mm_xor_si128(t0[1][0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(t0[1], t1[1]));
    EXPECT_TRUE(dpf::verify(t0[0], t1[0]));
}

TEST(Verifiable, BlockedCmpIntervalTamperRejects)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x20},
        dpf::block_width<4>(dpf::gt(std::uint64_t{1})), dpf::verifiable{});
    dpf::proof_token a{}, b{};
    dpf::prove_cmp_interval(k0, Input{0x1c}, Input{0x24}, dpf::prove(a));
    dpf::prove_cmp_interval(k1, Input{0x1c}, Input{0x24}, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
    for (auto & cs : const_cast<typename std::decay_t<decltype(k0)>::correction_seeds_array &>(
             k0.correction_seeds()))
        cs[0] = simde_mm_xor_si128(cs[0], simde_mm_set1_epi8(0x11));
    dpf::proof_token c{}, d{};
    dpf::prove_cmp_interval(k0, Input{0x1c}, Input{0x24}, dpf::prove(c));
    dpf::prove_cmp_interval(k1, Input{0x1c}, Input{0x24}, dpf::prove(d));
    EXPECT_FALSE(dpf::verify(c, d));
}

TEST(Verifiable, GenevalOffsetHornerProve)
{
    using Input = std::uint8_t;
    constexpr std::size_t D = 1;
    const Input center = 20;
    const Input share = 0x3c;
    const Input other = static_cast<Input>(center ^ share);
    const Input eta = 3;
    struct Pad
    {
        std::uint64_t n = 1;
        simde__m128i block()
        {
            auto v = simde_mm_set_epi64x(static_cast<long long>(n),
                static_cast<long long>(n * 9 + 3));
            n += 2;
            return v;
        }
        void fill(void * p, std::size_t nbytes)
        {
            auto * b = static_cast<unsigned char *>(p);
            for (std::size_t i = 0; i < nbytes; ++i)
                b[i] = static_cast<unsigned char>(n + i * 17);
            n += nbytes;
        }
        std::uint8_t bit() { return static_cast<std::uint8_t>(n++ & 1u); }
    };
    HEDLEY_PRAGMA(GCC diagnostic push)
    HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
    dpf::ds_randomness<simde__m128i (*)(), Pad> rng{
        dpf::uniform_sample<simde__m128i>, Pad{}};
    HEDLEY_PRAGMA(GCC diagnostic pop)
    const std::vector<Input> knots{0, 15, 40};
    const std::vector<std::array<std::uint64_t, D + 1>> coeff{{1, 0}, {2, 1}, {0, 3}};
    auto got = grotto::geneval_offset_horner<D>(share, other, eta, knots, coeff,
        std::move(rng));
    for (std::size_t m = 0; m <= D; ++m)
        EXPECT_TRUE(dpf::verify(got.proof0[m], got.proof1[m]));
    got.proof0[0][0] = simde_mm_xor_si128(got.proof0[0][0], simde_mm_set1_epi8(1));
    EXPECT_FALSE(dpf::verify(got.proof0[0], got.proof1[0]));
}

TEST(Verifiable, ZeroTokenRejects)
{
    dpf::proof_token z = dpf::detail::vdpf::zero_proof();
    EXPECT_FALSE(dpf::verify(z, z));
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{3},
        std::uint64_t{1}, dpf::verifiable{});
    dpf::proof_token a{}, b{};
    (void)*dpf::eval_point(k0, Input{3}, dpf::prove(a));
    (void)*dpf::eval_point(k1, Input{3}, dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
    EXPECT_FALSE(dpf::verify(a, z));
    EXPECT_FALSE(dpf::verify(z, b));
}

TEST(Verifiable, ColdAndWarmProveMatch)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{0x2a},
        std::uint64_t{7}, dpf::verifiable{});
    const Input x{0x11};
    dpf::proof_token cold0{}, cold1{};
    (void)*dpf::eval_point(k0, x, dpf::prove(cold0));
    (void)*dpf::eval_point(k1, x, dpf::prove(cold1));
    EXPECT_TRUE(dpf::verify(cold0, cold1));
    EXPECT_FALSE(dpf::detail::vdpf::proof_equal(cold0,
        dpf::detail::vdpf::zero_proof()));

    auto p0 = dpf::make_basic_path_memoizer(k0);
    auto p1 = dpf::make_basic_path_memoizer(k1);
    dpf::proof_token warm0{}, warm1{};
    (void)*dpf::eval_point(k0, x, dpf::prove(warm0), p0);
    (void)*dpf::eval_point(k1, x, dpf::prove(warm1), p1);
    // Second prove on the warm memoizer must match the cold token.
    dpf::proof_token again0{}, again1{};
    (void)*dpf::eval_point(k0, x, dpf::prove(again0), p0);
    (void)*dpf::eval_point(k1, x, dpf::prove(again1), p1);
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(cold0, warm0));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(cold0, again0));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(cold1, again1));
    EXPECT_TRUE(dpf::verify(again0, again1));
}

TEST(Verifiable, LeafTamperRejectsBoundProof)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{5},
        std::uint64_t{11}, dpf::verifiable{});
    auto & leaf = std::get<0>(
        const_cast<typename std::decay_t<decltype(k0)>::leaf_wrapper_tuple &>(
            k0.leaf_nodes)).raw_leaf();
    auto * bytes = reinterpret_cast<unsigned char *>(&leaf);
    bytes[0] = static_cast<unsigned char>(bytes[0] ^ 0x5a);

    dpf::proof_token a{}, b{};
    (void)*dpf::eval_point(k0, Input{5}, dpf::prove(a));
    (void)*dpf::eval_point(k1, Input{5}, dpf::prove(b));
    EXPECT_FALSE(dpf::verify(a, b));
}

TEST(Verifiable, ValueWordTamperRejectsBoundProof)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf(Input{0x20}, dpf::lt(std::uint64_t{1}),
        dpf::verifiable{});
    auto & vcw = const_cast<typename std::decay_t<decltype(k0)>::value_cw_array &>(
        k0.value_cw());
    vcw[0] = static_cast<typename std::decay_t<decltype(k0)>::value_cw_word>(
        static_cast<std::uint64_t>(vcw[0]) ^ 1ull);

    dpf::proof_token a{}, b{};
    dpf::eval_point(dpf::cmp, k0, Input{0x10}, dpf::prove(a));
    dpf::eval_point(dpf::cmp, k1, Input{0x10}, dpf::prove(b));
    EXPECT_FALSE(dpf::verify(a, b));
}

TEST(Verifiable, MakeCsMatchesHashNodeXor)
{
    // Local transcript of party/oblivious_hash.hpp: cs = H(s0) XOR H(s1).
    const std::size_t level = 3;
    const psnip_uint64_t prefix = 0x2a;
    const simde__m128i s0 = simde_mm_set_epi64x(0x1111, 0x2222);
    const simde__m128i s1 = simde_mm_set_epi64x(0x3333, 0x4444);
    const auto cs = dpf::detail::vdpf::make_cs(level, prefix, s0, s1);
    const auto h0 = dpf::detail::vdpf::hash_node(level, prefix, s0);
    const auto h1 = dpf::detail::vdpf::hash_node(level, prefix, s1);
    dpf::cs_block xor_h{
        simde_mm_xor_si128(h0[0], h1[0]),
        simde_mm_xor_si128(h0[1], h1[1]),
        simde_mm_xor_si128(h0[2], h1[2]),
        simde_mm_xor_si128(h0[3], h1[3])};
    EXPECT_EQ(std::memcmp(&cs, &xor_h, sizeof(cs)), 0);

    constexpr std::size_t tagged =
        dpf::detail::blocked::fold_spine_tag | level;
    const auto cs_b = dpf::detail::vdpf::make_cs(tagged, prefix, s0, s1);
    const auto hb0 = dpf::detail::vdpf::hash_node(tagged, prefix, s0);
    const auto hb1 = dpf::detail::vdpf::hash_node(tagged, prefix, s1);
    dpf::cs_block xor_hb{
        simde_mm_xor_si128(hb0[0], hb1[0]),
        simde_mm_xor_si128(hb0[1], hb1[1]),
        simde_mm_xor_si128(hb0[2], hb1[2]),
        simde_mm_xor_si128(hb0[3], hb1[3])};
    EXPECT_EQ(std::memcmp(&cs_b, &xor_hb, sizeof(cs_b)), 0);
    EXPECT_NE(std::memcmp(&cs, &cs_b, sizeof(cs)), 0);
}

TEST(Verifiable, InnerProductProve)
{
    using Input = std::uint8_t;
    auto [k0, k1] = dpf::make_dpf<Interior, Exterior>(Input{0x10},
        std::uint64_t{3}, dpf::verifiable{});
    std::array<std::uint64_t, 8> w{};
    w.fill(1);
    dpf::proof_token a{}, b{}, p0{}, p1{};
    dpf::eval_inner_product(k0, Input{0x0c}, Input{0x13}, w,
        dpf::prove(a));
    dpf::eval_inner_product(k1, Input{0x0c}, Input{0x13}, w,
        dpf::prove(b));
    EXPECT_TRUE(dpf::verify(a, b));
    dpf::prove_interval(k0, Input{0x0c}, Input{0x13}, dpf::prove(p0));
    dpf::prove_interval(k1, Input{0x0c}, Input{0x13}, dpf::prove(p1));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(a, p0));
    EXPECT_TRUE(dpf::detail::vdpf::proof_equal(b, p1));
}