libdpf/include/dpf/path_sketch.hpp

/// @file dpf/path_sketch.hpp
/// @brief VIDPF-style path-consistency sketches for incremental / IDPF keys.
/// @details Leaf one-hot is `sketch_fold` in verifiable.hpp. This header
///          checks that prefix payloads form a single spine: each depth is
///          weight-1 (or a single nonzero weight), and each parent equals the
///          sum of its children. Used by Poplar / Mastic one-time verification.
/// @copyright Copyright (c) 2019-2026 Ryan Henry and [others](@ref authors)
/// @license Released under a GNU General Public v2.0 (GPLv2) license;
///          see [LICENSE.md](@ref license) for details.

#ifndef LIBDPF_INCLUDE_DPF_PATH_SKETCH_HPP__
#define LIBDPF_INCLUDE_DPF_PATH_SKETCH_HPP__

#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

#include "hedley/hedley.h"

#include "dpf/dpf_key.hpp"
#include "dpf/eval_target.hpp"
#include "dpf/eval_walk.hpp"
#include "dpf/fp61.hpp"
#include "dpf/verifiable.hpp"

namespace dpf
{

namespace detail
{
namespace path_sketch_impl
{

template <typename Y>
HEDLEY_ALWAYS_INLINE
fp61 value_to_fp61(const Y & y) noexcept
{
    if constexpr (std::is_same_v<std::decay_t<Y>, fp61>)
        return y;
    else
        return fp61{static_cast<std::uint64_t>(y)};
}

template <typename T, typename = void>
struct has_raw_method : std::false_type
{ };

template <typename T>
struct has_raw_method<T, std::void_t<decltype(std::declval<const T &>().raw())>>
    : std::true_type
{ };

template <typename Share>
HEDLEY_ALWAYS_INLINE
fp61 share_to_fp61(const Share & s) noexcept
{
    if constexpr (std::is_same_v<std::decay_t<Share>, fp61>)
        return s;
    else if constexpr (std::is_integral_v<std::decay_t<Share>>)
        return fp61{static_cast<std::uint64_t>(s)};
    else if constexpr (has_raw_method<std::decay_t<Share>>::value)
        return value_to_fp61(s.raw());
    else
        return value_to_fp61(s);
}

}  // namespace path_sketch_impl
}  // namespace detail

/// @brief Weight-1 sketch of the `2^N` prefix shares at output `I`.
/// @details Opens to a valid `sketch_fold` iff exactly one prefix is nonzero
///          (unit path) or a single weight w sits on one prefix (weighted
///          IDPF). Consumes `2^N` challenges from `rs`.
template <std::size_t I, std::size_t N, typename KeyT>
sketch_share sketch_path_level(out_t<I, N>, const KeyT & key,
    const fp61 * rs, std::size_t n)
{
    static_assert(is_multilevel_key_v<KeyT>,
        "sketch_path_level: key must be multilevel / idpf");
    constexpr std::size_t nprefix = std::size_t{1} << N;
    if (rs == nullptr || n < nprefix)
        throw std::invalid_argument("sketch_path_level: need 2^N challenges");

    auto [buf, it] = eval_prefixes(out_t<I, N>{}, key);
    (void)buf;
    std::vector<fp61> ys;
    ys.reserve(nprefix);
    std::size_t i = 0;
    for (auto a = std::begin(it); a != std::end(it) && i < nprefix; ++a, ++i)
        ys.push_back(detail::path_sketch_impl::share_to_fp61(*a));
    if (ys.size() != nprefix)
        throw std::runtime_error("sketch_path_level: prefix count mismatch");
    return sketch_fold(ys, std::vector<fp61>(rs, rs + nprefix));
}

/// @brief Random linear check that parent[p] = left[2p] + right[2p+1].
/// @details Parent slot `I` has prefix length `N`; child is slot `I+1` with
///          length `N+1`. Consumes `2^N` challenges. Opens to 0 when the
///          two levels are consistent.
template <std::size_t I, std::size_t N, typename KeyT>
fp61 sketch_path_parent(out_t<I, N>, out_t<I + 1, N + 1>, const KeyT & key,
    const fp61 * gamma, std::size_t n)
{
    static_assert(is_multilevel_key_v<KeyT>,
        "sketch_path_parent: key must be multilevel / idpf");
    constexpr std::size_t nparent = std::size_t{1} << N;
    if (gamma == nullptr || n < nparent)
        throw std::invalid_argument("sketch_path_parent: need 2^N challenges");

    auto [bp, ip] = eval_prefixes(out_t<I, N>{}, key);
    auto [bc, ic] = eval_prefixes(out_t<I + 1, N + 1>{}, key);
    (void)bp;
    (void)bc;

    std::vector<fp61> parents;
    std::vector<fp61> children;
    parents.reserve(nparent);
    children.reserve(nparent * 2);
    for (auto a = std::begin(ip); a != std::end(ip); ++a)
        parents.push_back(detail::path_sketch_impl::share_to_fp61(*a));
    for (auto a = std::begin(ic); a != std::end(ic); ++a)
        children.push_back(detail::path_sketch_impl::share_to_fp61(*a));
    if (parents.size() != nparent || children.size() != nparent * 2)
        throw std::runtime_error("sketch_path_parent: prefix count mismatch");

    fp61 gap{};
    for (std::size_t p = 0; p < nparent; ++p)
    {
        const fp61 rel = parents[p] - children[2 * p] - children[2 * p + 1];
        gap = gap + gamma[p] * rel;
    }
    return gap;
}

/// @brief Whether two parent-gap shares open to zero.
HEDLEY_NO_THROW
HEDLEY_ALWAYS_INLINE
HEDLEY_CONST
bool sketch_path_verify_parent(fp61 g0, fp61 g1) noexcept
{
    return (g0 - g1).raw() == 0;
}

namespace detail
{
namespace path_sketch_impl
{

template <std::size_t Depth, std::size_t I>
struct verify_levels
{
    template <typename K0, typename K1>
    static bool run(const K0 & k0, const K1 & k1, const fp61 *& rs,
        std::size_t & left)
    {
        constexpr std::size_t N = I + 1;
        constexpr std::size_t nprefix = std::size_t{1} << N;
        if (left < nprefix)
            return false;
        const auto s0 = sketch_path_level(out_t<I, N>{}, k0, rs, left);
        const auto s1 = sketch_path_level(out_t<I, N>{}, k1, rs, left);
        if (!sketch_verify(s0, s1))
            return false;
        rs += nprefix;
        left -= nprefix;

        if constexpr (I + 1 < Depth)
        {
            constexpr std::size_t nparent = std::size_t{1} << N;
            if (left < nparent)
                return false;
            const fp61 g0 = sketch_path_parent(out_t<I, N>{},
                out_t<I + 1, N + 1>{}, k0, rs, left);
            const fp61 g1 = sketch_path_parent(out_t<I, N>{},
                out_t<I + 1, N + 1>{}, k1, rs, left);
            if (!sketch_path_verify_parent(g0, g1))
                return false;
            rs += nparent;
            left -= nparent;
            return verify_levels<Depth, I + 1>::run(k0, k1, rs, left);
        }
        return true;
    }
};

}  // namespace path_sketch_impl
}  // namespace detail

/// @brief One-time VIDPF path check for an IDPF of consecutive depths 1..Depth.
/// @details Challenge layout, consumed in order for I = 0 .. Depth-1:
///          - `2^(I+1)` challenges for the weight-1 sketch at `out<I, I+1>`
///          - if I+1 < Depth: `2^(I+1)` challenges for the parent relation
///            between `out<I, I+1>` and `out<I+1, I+2>`
/// @tparam Depth number of IDPF prefix slots (`idpf` with Depth betas)
template <std::size_t Depth, typename Key0, typename Key1>
bool verify_idpf_path(const Key0 & k0, const Key1 & k1,
    const fp61 * rs, std::size_t n)
{
    static_assert(Depth >= 1, "verify_idpf_path: Depth >= 1");
    static_assert(is_multilevel_key_v<Key0> && is_multilevel_key_v<Key1>,
        "verify_idpf_path: multilevel keys");
    if (!same_public_part(k0, k1))
        return false;
    if (rs == nullptr)
        return false;
    const fp61 * cursor = rs;
    std::size_t left = n;
    return detail::path_sketch_impl::verify_levels<Depth, 0>::run(
        k0, k1, cursor, left);
}

/// @brief Convenience overload taking a contiguous challenge vector.
template <std::size_t Depth, typename Key0, typename Key1>
bool verify_idpf_path(const Key0 & k0, const Key1 & k1,
    const std::vector<fp61> & rs)
{
    return verify_idpf_path<Depth>(k0, k1, rs.data(), rs.size());
}

/// @brief How many fp61 challenges `verify_idpf_path<Depth>` consumes.
HEDLEY_CONST
HEDLEY_ALWAYS_INLINE
constexpr std::size_t path_sketch_challenge_count(std::size_t depth) noexcept
{
    std::size_t n = 0;
    for (std::size_t i = 0; i < depth; ++i)
    {
        const std::size_t nprefix = std::size_t{1} << (i + 1);
        n += nprefix;
        if (i + 1 < depth)
            n += nprefix;
    }
    return n;
}

}  // namespace dpf

#endif  // LIBDPF_INCLUDE_DPF_PATH_SKETCH_HPP__