Ryan Henry
0d22946a0e
Ship the TLS mesh, composer, Beaver/Yao/leaf MPC, prep/online paths, apps, and docs so the tree is pushable before elevating share_expr, security_mode, and prep resume. Co-authored-by: Cursor <cursoragent@cursor.com>
103 lines
4.8 KiB
Markdown
103 lines
4.8 KiB
Markdown
# Point-programmable vector commitments {#ppvc_manual}
|
||
|
||
\htmlonly
|
||
<div class="eli5"><b>ELI5.</b> The vector is bound before the coordinate is chosen. Each coordinate is a pair of 1-bit DPF roots, and both roots are committed with a Naor string. Opening one side of each pair writes the hidden coordinate, or the sum, onto a public index.</div>
|
||
\endhtmlonly
|
||
|
||
A point-programmable vector commitment binds a vector
|
||
`x` in `(Z/2^s Z)^n` and still lets one hidden coordinate be chosen
|
||
after the commitment is published.
|
||
|
||
`n` is a power of two, the bit length of the input type, and at most
|
||
2^20, because evaluation stores one entry per domain point. `s` is
|
||
the `Width` parameter, from 1 to 64.
|
||
The manual construction is `dpf::ppvc`. `dpf::k_ppvc<K, ...>` is `K`
|
||
independent copies of that object.
|
||
|
||
The committer samples an index `i` and builds `s` aligned 1-bit DPF
|
||
pairs there, the same point key as [DPF basics](@ref basics_body).
|
||
Both roots of every pair are bound with a Naor commitment under a
|
||
public matrix `A`. Opening releases one key from each pair, together
|
||
with a shift `delta = xi - i`.
|
||
|
||
Off `i`, the two keys of a pair evaluate to the same bit.
|
||
At `i`, they evaluate to opposite bits.
|
||
Choosing the side therefore writes an arbitrary value into that one
|
||
coordinate and leaves every other coordinate fixed.
|
||
The shift moves the written coordinate from `i` onto the public target
|
||
`xi`. The opening carries `delta`, not `i` and not `xi`.
|
||
|
||
`open(st, mu, tau, xi)` has two modes.
|
||
|
||
- `mu = 0` programs the coordinate. After rotation, entry `xi` equals `tau`.
|
||
- `mu = 1` programs the sum of every coordinate. That sum equals `tau`.
|
||
|
||
Those two maps are bijections on `Z/2^s Z`. Programming one of them
|
||
programs the other.
|
||
|
||
```cpp
|
||
using scheme = dpf::ppvc<std::uint8_t, 8>;
|
||
const auto pp = scheme::setup();
|
||
const auto [com, st] = scheme::commit(pp);
|
||
|
||
const std::uint8_t xi = 40;
|
||
const auto op = scheme::open(st, 0, 0x5a, xi);
|
||
const auto x = scheme::eval(op); // hidden indexing
|
||
const auto rotated = scheme::eval_rotated(op); // value 0x5a sits at xi
|
||
const bool ok = scheme::accept(pp, com, op, x, xi);
|
||
```
|
||
|
||
`setup` samples `A`. `setup_from_seed` expands one 128-bit seed into the
|
||
same matrix, which is the common random string when many sessions share
|
||
it. `commit` samples `i`. `commit_at` uses an index the caller already
|
||
chose. The shift hides `i` when that index was sampled independently of
|
||
`xi`. `commit_from_seed` and `commit_at_from_seed` rerun key generation
|
||
from a replica seed. Seed expansion keeps its counter in thread-local
|
||
storage, so two expansions on one thread must not overlap.
|
||
|
||
## What an opening proves {#ppvc_verify}
|
||
|
||
\htmlonly
|
||
<div class="eli5"><b>ELI5.</b> verify recomputes the Naor string on each opened root and compares it to the commitment. A root that was not the committed one fails. The check does not reveal the other coordinates.</div>
|
||
\endhtmlonly
|
||
|
||
`verify` checks each opened root against its Naor string.
|
||
`accept` also checks the programmed statement: the rotated coordinate
|
||
when `mu` is 0, the column sum when `mu` is 1.
|
||
|
||
Correction words travel with the opened key. They are not inside the
|
||
commitment. `verify` sees one side of each pair.
|
||
`check_well_formed` is the check on a replica the committer still holds:
|
||
shared correction words, party bits 0 and 1, both Naor openings, and
|
||
exactly one place where the two keys disagree, at the recorded index,
|
||
with payload 1.
|
||
`audit` expands a seed and accepts when the published commitment matches
|
||
that expansion and the replica is well formed.
|
||
When many replica seeds sit as leaves of a GGM tree, the audit opening of
|
||
the pool is a [`dpf::pprf_copath`](@ref dpf/pprf.hpp) built by
|
||
`dpf::puncture(master, live…, /*program_hidden=*/false)`: every audited
|
||
leaf re-expands with `dpf::pprf_eval`, and a live seed is never among the
|
||
published nodes. Sampling the audit set and combining live copies stay in
|
||
the protocol, not in this library.
|
||
|
||
`k_ppvc` asks for the same checks on every copy, and for distinct hidden
|
||
indices. `combine_rotated` adds the rotated vectors in `Z/2^s Z`.
|
||
Reprogramming copy `r` changes coordinate `xi[r]` of that sum.
|
||
|
||
The commitment is `2 * s * (3 * 128 + Sigma)` bits.
|
||
`Sigma` defaults to 128 and must be a multiple of 8.
|
||
The generator is `dpf::prg::aes128` unless another 128-bit PRG is named.
|
||
|
||
**Defined in**\n
|
||
@ref dpf/ppvc.hpp
|
||
|
||
**Try**\n
|
||
@ref mwe/ppvc.cpp
|
||
|
||
Naor's string commitment is Moni Naor, [Bit Commitment Using Pseudorandomness](@ref bib_naor), Journal of Cryptology 1991.
|
||
The point keys are the Boyle–Gilboa–Ishai construction named in
|
||
[DPF basics](@ref point_functions).
|
||
|
||
\htmlonly
|
||
<div class="tldr"><b>TL;DR.</b> Commit binds the vector before the coordinate is chosen, by committing both DPF roots. Open writes one coordinate or the sum onto a public index. verify checks those roots against the Naor strings.</div>
|
||
\endhtmlonly
|