A (Relaxed) PCS by Merkle Trees and Low-Degree Tests
Chapter three dives into a first Succinct Argument of Circuit Satisfiability. It does so by introducing what it calls a Relaxed Polynomial Commitment Scheme that combines Merkle Trees and Low-Degree tests. Implementing a first Succinct Argument sounds like an interesting challenge, let's find out.
In Chapter 7 The Books gives the main definitions and the motivations for the new objects called Polynomial Commitment Schemes. Essentially what we want is a scheme where $\mathcal{P}$ would "commit" to the evaluations of some polynomial and its degree to be later tested by $\mathcal{V}$.
The Scheme
The Scheme itself as it is quoting The Book:
Let $\tilde{w} : \mathbb{F}^{\log n} \rightarrow \mathbb{F}$ be a ($\log n$)-variate multilinear polynomial over $\mathbb{F}$.
Let $s$ be the string consisting of all $|\mathbb{F}|^{\log n}$ evaluations of $\tilde{w}$.
One obtains a polynomial commitment scheme by applying a Merkle-tree based string commitment scheme to $s$ and then applying a low-degree test to $s$.
Let's try to decompose it.
Merkelizing the Evaluations
This is the easier part. Suppose for example that we have a function $\mathbb{F_5}^2$. The evaluation table for this function would look as follows:
| 0 0 | 0 1 | 0 2 | .. | 5 4 | 5 5 |
|---|---|---|---|---|---|
| s[0] | s[1] | s[2] | .. | s[23] | s[24] |
And in order for $\mathcal{P}$ to commit to all the evaluations of this function it needs to create a Merkle Tree of $s$ and send $\mathcal{V}$ the root of this tree. Later when $\mathcal{V}$ asks $\mathcal{P}$ to reveal any of the evaluations, $\mathcal{P}$ replies with the evaluation + a proof of this evaluation's inclusion into the tree. Since merkelizing things is such a common theme in the blockchain space I am not going to go into it any further.
Running a Low-Degree Test
The explanation from The Book is a bit handwavy so it probably makes sense to look into [AS03] paper:
The low degree test is presented with $f:\mathbb{F}^m \rightarrow \mathbb{F}$ and an integer $d$. It is also presented a table that is meant to be "proof" that $f$ is degree $d$ polynomial. This table contains for each line in $\mathbb{F}^m$ a univariate degree $d$ polynomial that supposedly describes restriction of $f$ to that line. We will use the term $\textit{d-oracle}$ for any table that contains, for each line in $\mathbb{F}^m$ a univariate degree $d$ polynomial.
$$ \boxed{ \begin{aligned} &\text{\bf{The Low Degree Test:}}\cr &\text{Pick a random line } l \text{ in } \mathbb{F}^m\cr &\text{and read the univariate polynomial, say } p_l(t)\cr &\text{which the given \textit{d-oracle} contains for this line.}\cr &\text{Randomly pick a point $x$ on line $l$ and check}\cr &\text{whether $p_l$ correctly describes $f$ at $x$.}\cr &\text{If so, ACCEPT, else REJECT} \end{aligned} } $$
The Test from the paper [AS03] is not interactive, and assumes the oracle access to the whole $\textit{d-oracle}$ table. So here are a few ideas to take this description to the PCS protocol from The Book:
- At the beginning of the protocol $\mathcal{P}$ commits to the Merkle tree of the string of $f$ evaluations and to the claimed degree $d$ of $f$ by sending these values to $\mathcal{V}$.
- $\mathcal{V}$ picks a random line $l$ in $\mathbb{F}^m$ and sends it to $\mathcal{P}$.
- $\mathcal{P}$ replies with a univariate polynomial $p_l$ which it claims to be a restriction of $f$ to $l$.
- $\mathcal{V}$ generates a random $x \in \mathbb{F}$. Then it evaluates line $l$ on $x$ to obtain a point in $\mathbb{F}^m$. $\mathcal{V}$ sends this point to $\mathcal{P}$ and $\mathcal{P}$ replies with a corresponding value from $s$ and with the proof this evaluation's membership in the Merkle tree which was previously committed to by $\mathcal{P}$.
- $\mathcal{V}$ checks that $p_l(x)$ equals the received value from $s$ and that this value belongs to the Merkle tree.
Implementation
Restricting a polynomial to a line has been described and implemented in a previous post on GKR. What we need is the machinery to merkelize the evaluations string $s$.
All Values of $\mathbb{F}$
First we need to be able to evaluate our function $f$ on all values in $\mathbb{F}^m$. It would be great to introduce a helper trait that would allow the code to iterate over all possible values of $\mathbb{F}$:
/// Iterate over all possible values of a finite field.
pub trait IF: Field {
type Values: IntoIterator<Item = Self>;
fn all_values() -> Self::Values;
}
Now in order to turn all values in $\mathbb{F}$ into all values in $\mathbb{F}^m$ we need to build all permutations of values in $\mathbb{F}$ of length $m$. Since building such permutations is not the topic of this post the readily available code can be used to extend the above trait with a helper function:
pub trait IF: Field {
type Values: IntoIterator<Item = Self>;
fn all_values() -> Self::Values;
fn all_multidimentional_values(m: usize) -> Vec<Vec<Self>> {
let mut res: Vec<_> =
permutations::permutations(&Self::all_values().into_iter().collect::<Vec<_>>(), m)
.collect();
res.sort();
res
}
}
Prover
$\mathcal{P}$ is initialized with some polynomial $f$, our implementation as usual is going to be quite generic. Here, it is being generic over a field $\mathbb{F}$, the $f$ and the parameters of the Merkle tree:
pub struct Prover<F: Field, M: MultilinearExtension<F>, P: Config<Leaf = F>> {
tree: MerkleTree<P>,
values_convenience_map: HashMap<Vec<F>, usize>,
poly: M,
values: Vec<F>,
}
The implementation allows any MerkleTree configuration to be used with only
restriction that the leafs of the tree have to be elements in $\mathbb{F}$.
Also Prover holds a convenience map from $\mathbb{F}^m$ to indices in the
evaluations string $s$.
Now to create a new $\mathcal{P}$ and populate all the fields in the above struct a fairly involved logic has to be implemented:
impl<F: IF, M: MultilinearExtension<F>, P: Config<Leaf = F>> Prover<F, M, P> {
/// Create a new Prover.
pub fn new(
poly: M,
leaf_chr_params: <<P as Config>::LeafHash as CRHScheme>::Parameters,
two_to_one_params: <<P as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters,
) -> Result<Self> {
let all_values = F::all_multidimentional_values(poly.num_vars());
// Populate s
let all_poly_values: Result<Vec<_>> = all_values
.iter()
.map(|value| poly.evaluate(value).ok_or(Error::PolyEvalDimMismatch))
.collect();
let all_poly_values = all_poly_values?;
// Length of array for `MerkleTree` has to be a power of two, so
// extend s with zeros up to that length.
let all_values_len = all_poly_values.len();
let values: Vec<_> = all_poly_values
.iter()
.cloned()
.chain((all_values_len..all_values_len.next_power_of_two()).map(|_| F::zero()))
.collect();
// Build a convenience indexing map
let values_convenience_map = all_values
.iter()
.enumerate()
.map(|(i, value)| (value.clone(), i))
.collect();
// Build a MerkleTree.
let tree: MerkleTree<P> =
MerkleTree::new(&leaf_chr_params, &two_to_one_params, values.clone())?;
Ok(Self {
tree,
poly,
values_convenience_map,
values,
})
}
}
To complete the implementation of $\mathcal{P}$ three functions have to be added:
/// Get the merkle root.
pub fn merkle_root(&self) -> P::InnerDigest {
self.tree.root()
}
/// Restrict to line.
pub fn poly_restriction_to_line(&self, b: &[F], c: &[F]) -> univariate::SparsePolynomial<F> {
restrict_poly(b, c, &self.poly)
}
/// Challenge
pub fn challenge(&self, point: Vec<F>) -> Result<(Path<P>, F)> {
let point_index = self.values_convenience_map.get(&point).unwrap();
Ok((
self.tree.generate_proof(*point_index)?,
self.values[*point_index],
))
}
First one returns the root of the Merkle tree of $s$ $\mathcal{P}$ commits to at the beginning of the protocol.
The second one restricts committed $f$ to a random line $x$ picked by $\mathcal{V}$.
The third one answers $\mathcal{V}$'s request to revel $s$ value at a given point along with the proof of this value's membership in the committed Merkle tree.
Verifier
The $\mathcal{V}$ is going to hold quite a lot of data:
/// The Verifier in the Relaxed PCS protocol.
pub struct Verifier<F: Field, P: Config<Leaf = F>> {
x: F,
degree: usize,
challenge_point: Vec<F>,
line: Vec<univariate::SparsePolynomial<F>>,
num_vars: usize,
prover_univariate: Option<univariate::SparsePolynomial<F>>,
merkle_root: P::InnerDigest,
leaf_chr_params: LeafParam<P>,
two_to_one_params: TwoToOneParam<P>,
}
When a new $\mathcal{V}$ is created it has to be initialized with the values of degree $d$ and the root of the Merkle Tree of $s$ $\mathcal{P}$ has committed to:
impl<F: Field, P: Config<Leaf = F>> Verifier<F, P> {
/// Create a new Verifier.
pub fn new(
num_vars: usize,
degree: usize,
merkle_root: P::InnerDigest,
leaf_chr_params: <<P as Config>::LeafHash as CRHScheme>::Parameters,
two_to_one_params: <<P as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters,
) -> Self {
Then it picks the random line in $\mathbb{F}^m$ to send it to the $\mathcal{P}$.
To do so $\mathcal{V}$ generates two random points in $\mathbb{F}^m$ and uses the
function line implemented earlier for the GKR protocol:
pub fn random_line<R: Rng>(&mut self, rng: &mut R) -> (Vec<F>, Vec<F>) {
let b: Vec<F> = (0..self.num_vars).map(|_| F::rand(rng)).collect();
let c: Vec<F> = (0..self.num_vars).map(|_| F::rand(rng)).collect();
self.line = line(&b, &c);
(b, c)
}
When $\mathcal{P}$ has sent a univariate polynomial $p_l$ claimed to be a restriction of $f$ to the line generated earlier, $\mathcal{V}$ checks its degree and saves to evaluate it later:
pub fn committed_univariate(&mut self, p: univariate::SparsePolynomial<F>) -> Result<()> {
if p.degree() > self.degree {
return Err(Error::DegreeMismatch);
}
self.prover_univariate = Some(p);
Ok(())
}
Then $\mathcal{V}$ needs to pick a random point along the picked line $l$ and send it to $\mathcal{P}$ querying the corresponding value in $s$ along with the proof:
/// Challenge the prover at some point.
pub fn challenge_prover<R: Rng>(&mut self, rng: &mut R) -> Vec<F> {
self.x = F::rand(rng);
self.challenge_point = self
.line
.iter()
.map(|poly| poly.evaluate(&self.x))
.collect();
self.challenge_point.clone()
}
Finally the $\mathcal{P}$'s reply has to be verified against the earlier committed root of Merkle Tree of $f$ and also $\mathcal{V}$ needs to check that value from $s$ $\mathcal{P}$ has replied with equals $p_l(x)$:
/// Verify the prover's reply.
pub fn verify_prover_reply(&self, path: Path<P>, leaf: F) -> Result<()> {
path.verify(
&self.leaf_chr_params,
&self.two_to_one_params,
&self.merkle_root,
leaf,
)?;
let eval = self
.prover_univariate
.as_ref()
.ok_or(Error::NoProverPoly)?
.evaluate(&self.x);
if leaf != eval {
return Err(Error::EvalMismatch(
format!("{:?}", leaf),
format!("{:?}", eval),
));
}
Ok(())
}
Testing
The testing code configures the Merkle Trees the same way testing code in
ark-crypto-primitives
does with the only exception is that the implementation of Config is generic
over field $\mathbb{F}$ and uses a wrapper for a hasher to go from this generic
field type to bytes for hash convenience:
type LeafH = pedersen::CRH<JubJub, Window4x256>;
struct CHROverField<F> {
__f: PhantomData<F>,
}
impl<F: Field> CRHScheme for CHROverField<F> {
type Input = F;
type Output = <LeafH as CRHScheme>::Output;
type Parameters = <LeafH as CRHScheme>::Parameters;
fn setup<R: Rng>(
r: &mut R,
) -> std::result::Result<Self::Parameters, ark_crypto_primitives::Error> {
LeafH::setup(r)
}
fn evaluate<T: Borrow<Self::Input>>(
parameters: &Self::Parameters,
input: T,
) -> std::result::Result<Self::Output, ark_crypto_primitives::Error> {
let bytes = to_uncompressed_bytes!(input).map_err(|_| Box::new(Error::ToBytesError))?;
LeafH::evaluate(parameters, bytes.as_ref())
}
}
This way in the config for the merkle tree the associated Leaf type can be our field
and not the [u8] slice:
struct JubJubMerkleTreeParamsFp5;
impl Config for JubJubMerkleTreeParamsFp5 {
type Leaf = Fp5;
type LeafDigest = <LeafH as CRHScheme>::Output;
type LeafInnerDigestConverter = ByteDigestConverter<Self::LeafDigest>;
type InnerDigest = <CompressH as TwoToOneCRHScheme>::Output;
type LeafHash = CHROverField<Fp5>;
type TwoToOneHash = CompressH;
}
Conclusion
In this a first Succinct Argument from The Book has been implemented.
The implementation is available at
b73f65d.
As always the implementation has been made extremely generic over
everything and turned out quite good I believe. Thank you for reading
and stay tuned for the future posts!
Reference List.
YouTube: Log Degree Testing - Alessandro Chiesa
Robust Characterizations of Polynomials with Applications to Program Testing