arkworks-rs / poly-commit Goto Github PK
View Code? Open in Web Editor NEWA Rust library for polynomial commitments
License: Apache License 2.0
A Rust library for polynomial commitments
License: Apache License 2.0
Generic struct, such as kzg10::Commitment<E: PairingEngine>(pub E::G1Affine)
without proper constructor can be hard to instantiate, as the compiler will complain about "expected type, but found struct" problem.
Assume you got a GroupAffine
point (SW or TE), which is supposed to be a kzg10::Commitment
, and you try to reconstruct the commitment out of the underlying point value, except you can't with current API.
| .map(|[x, y]| Commitment(GroupAffine::new(x, y, false)))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found struct `ark_ec::short_weierstrass_jacobian::GroupAffine`
|
= note: expected associated type `<E as PairingEngine>::G1Affine`
found struct `ark_ec::short_weierstrass_jacobian::GroupAffine<_>`
(side note: I concede that technically we can use CanonicalDeserialize
into a Commitment
, but that's a bit troublesome.)
TBD
Latest version is not building. We should target published crates instead of github branches so we can publish a new version for this crate
Unpublished branches are harder to manage and keep track of semver/latest updates
Fix minor issues and prepare to release
The current interface doesn't allow room for certain optimizations to open
.
Specifically, for linear code schemes such as Ligero, during commit
we compute the merkle root, and to create the proof in open
we again recompute the merkle tree to then send merkle proofs for a bunch of leaf indices. Ideally the open
stage shouldn't need to recompute the tree.
We introduce a gap between the output of commit
and the input to check
.
Namely, commit
would return an ExtendedCommitment
(aka PrivateCommitment
?) , and verify
would only receive the Committment
. We also introduce a trivial into()
method that's a no-op in all current schemes, but for linear codes it sheds a few fields, such as the coefficients matrix, extended coefficients matrix and the merkle tree, saving the need to recompute them.
We can then leverage this new interface to further simplify the commit
and open
trait methods: instead of having a separate argument rands
, we place the rands
on the ExtendedComittment
. Then the into()
method would shed the rands
field when converting it to be used in check
.
0.5.0-alpha release is missing for this crate. Are you planning to publish it along with other ark-* crates?
(Eg: test that enforcing a degree bound d for a degree-(d+2) polynomial leads to failure)
Hey!
I've been with the ark-poly-commit
library.
And I have my Error
enum where inside I have an ArkPolyCommit
error variant.
The issue is that seems I can't do:
pub fn universal_setup<R: RngCore>(
max_degree: usize,
rng: &mut R,
) -> Result<UniversalSRS<F, PC>, MyError> {
PC::setup(max_degree, None, rng)
.map_err(|err| ark_poly_commit::Error::from)?
}
Nor
pub fn universal_setup<R: RngCore>(
max_degree: usize,
rng: &mut R,
) -> Result<UniversalSRS<F, PC>, MyError> {
PC::setup(max_degree, None, rng)?
}
And I have the From<ark-poly-commit-error> for MyError
ofc.
The issue I see is that PolynomialCommitment
has an associated Error type. And although the associated trait bounds seem correct. I can't make it work as requires me to add generics in all my errors where this should not be necessary.
See: https://github.com/arkworks-rs/poly-commit/blob/master/src/lib.rs#L174
Wondering how does people sort this out without ugly solutions like https://github.com/ZK-Garage/plonk/blob/master/plonk-core/src/error.rs#L96-L107.
Ideally, can't we remove the Error
type from the trait and just leave the regular error? This would make integration within enums much easier.
Marlin's trim function is missing checks to ensure that each enforced_degree_bound is within the supported degree
Maybe a PCWithStrictBounds: PolynomialCommitment
. It would have default methods that implement a "naive" shift-based bounding strategy, and these methods can be overriden by concrete implementors.
Currently the API for PC schemes follows the definition in the Marlin paper. This means that instead of generating an opening challenge for batch verification via a random oracle, methods on PolynomialCommitment
explicitly take as input an opening challenge.
This reduces flexibility in challenge generation, and also increases the chance of mistakes in challenge generation due to incorrect domain separation or incorrect state chaining
Hence, we should define a common random oracle interface, and should use this interface consistently in PolynomialCommitment
, as well as downstream in marlin
. Goals include making the construction modular with respect to choice of concrete random oracle (eg: blake2s, Poseidon, etc), and enabling optimizations like sampling short linear combination coefficients, instead of sampling them as powers of opening_challenge
.
Prior art include libraries like merlin, and the ad-hoc impl in marlin
I‘m reading the paper Proof-Carrying Data from Accumulation Schemes,and there maybe something wrong in the "Figuer 1" Open
setup evaluation formula, just as shown below:
And "Figuer 1" has no reference in the paper anywhere.
As per the discussion in #139
We're using Arkworks at sifraitech/rust-kzg and are currently undergoing a migration to EIP-4844 by using ethereum/c-kzg-4844 as a reference. The said implementation loads trusted setups from files, e.g., trusted_setup.txt, that hold the following information:
G1Count | G2Count | [G1] | [G2]
On the contrary, Arkworks invokes the method kzg10::setup
and feeds it a RngCore
object to generate the setup, which is not as secure as loading the precomputed G1
and G2
points from a file.
As far as I'm understanding, powers_of_g
and powers_of_gamma_g
are responsible for holding G1
and G2
points, respectively. But as you can see, the type of powers_of_gamma_g
is BTreeMap::<usize, G1Affine>
, which by definition cannot hold G2
points. We attempted to replace the values of powers_of_g
with G1
points loaded from a setup file, but we are unsure of where to put the G2
points.
Allow us to load G1
and G2
points from a file rather than relying on the setup function.
The PolynomialCommitment
trait is a little cumbersome with all the wrapper types.
See if we can simplify the trait and then implement it for all schemes. Some ideas:
check
-> verify
- there are a lot of name variations in the literature for the same algorithm, though check
seems to be used less frequently. verify
is more intuitive IMO.LabeledPolynomial
construction is cumbersome: introduce a from
conversion on Polynomial<F>
with some reasonable defaults, or:trim
function, which would take the parameters from the max degree of all labeled polys we are working with.QuerySet
from
a vector of (vectors of?) points. Construct Evaluations
from QuerySet
and a Vec<Polynomial>
.ChallengeGenerator
automatically? We know the sponge, and we know whether the poly is uni- or multi-variate, so this can be part of e.g. setup.See also jellyfish PCS trait, although the Espresso traits aren't as generic as they are mostly tailored for KZG.
@alxiong
Neither in kzg10 nor in marlin_pc.
If you still plan to employ it, please notice that it contains precomputed powers of the generator as g1 prepared. It may worth considering wNAF instead, or at least use E::G1Projective::batch_normalization_into_affine.
When we are writing tests, we want to forge a trivial circuit with a specific number of constraints and nonzero entries, though the circuit itself is trivial (we may just write the same LC a million times).
This, however, would fail. A trivial constraint system may cause A, B, C matrices in Marlin to be too simple, such as after "row", "col" computation, the "val" polynomial could become a degree-zero polynomial.
Poly-commit, specifically KZG10 implementation, for some reasons, refuses to commit a degree-zero polynomial (during commit
and open
).
Error::check_degree_is_within_bounds(polynomial.degree(), powers.size())?;
which,
pub(crate) fn check_degree_is_within_bounds(
num_coefficients: usize,
num_powers: usize,
) -> Result<(), Self> {
if num_coefficients < 1 {
Err(Error::DegreeIsZero)
} else {
Self::check_degree_is_too_large(num_coefficients, num_powers)
}
}
Reading KZG10, it seems not obvious that degree-zero polynomial cannot be committed? I guess you can commit a degree-zero polynomial (which is a constant)?
Should we remove this restriction?
Hi,
I am encountering problems when trying to build the master branch of this library. It seems that common dependencies such as ark-ec
or ark-serialize
(see attached pictures for examples of the ecountered errors) fail to build. However, I have used such libraries for other Rust projects without issues. I tried modified Cargo.toml
to address these issues but then other dependency problems arise. Can you assist me with this problem? Thanks a lot!
In many PCSs, a prover commits to a polynomial and is subsequently queried about the value of that committed polynomial at a point chosen by the verifier - letting the verifier learn that actual value during the process.
However, this is not the case for all PCSs: sometimes, the verifier just wants to be convinced that a committed polynomial, at a point of their choice, takes a value the prover only commits to without revealing it in plain. This is, for instance, the case of Hyrax (cf. section 6 here), which is currently PRed (see #130). It is not unthinkable that more such schemes will be added as the module grows.
The current PolynomialCommitment
trait does not handle that situation very elegantly - in particular, the method check
receives a list of expected evaluations. How Hyrax was patched to fit this paradigm is outlined in the linked PR.
Three possible ways forward come to mind:
check
method simply disregard the received evaluations in evaluation-hiding PCSs. This seems inelegant and might lead to misuse where the programmer passes a certain evaluation to that function, receives positive confirmation, and thinks those evaluations were matched against the proof and correspond to evaluations of the committed polynomial. This issue could be mitigated with good documentation.check
by an Option
wrapper around that. Each implementor, depending of which of the two paradigms it fits, would panic if it receives the opposite of what it expects and otherwise run business as usual. By what it expects I mean Some
for PCSs where evaluations are meant to be learnt by the verifier and None
for evaluation-hiding ones. This change would indeed be breaking but the changes would be minimal.evaluation_hiding
flag inside the current trait. Here I don't have many specific proposals, but I am up for discussion. A point in favour of this is that evaluation-hiding PCSs pay a performance cost due to their nature and the plug-out-plug-in design aim of the PolynomialCommitment
trait in its current form would put them in the same bag as non-hiding PCSs.At this moment, the second option seems the most appealing. I am happy to explore other possibilities, though.
PC::check
is implemented with optional rng:
Lines 225 to 233 in 9da67e2
However, rng is mandatory for check_combinations
Line 344 in 9da67e2
Even tho PC::batch_check
forwards that as optional
Line 292 in 9da67e2
This creates downstream conflicts for types that comply with PC::check
and will have the rng as optional. In case the user will not provide the rng, we can defer to
poly-commit/src/optional_rng.rs
Line 12 in 9da67e2
Update PC::check_combinations
and PC::batch_check
to take the rng as optional
poly-commit/src/ipa_pc/data_structures.rs
Lines 115 to 117 in 1861953
Hi,
I assume the recent renaming of some curves in Zexe:
This PR renames some modules relating to the concrete curves that are implemented in zexe.
edwards_bls12 -> edwards_on_bls12_377
jubjub -> edwards_on_bls12_381
edwards_sw6_ -> edwards_on_cp6_782
sw6 -> cp6_782
upsets Cargo:
cargo build
error: failed to select a version for `algebra`.
versions that meet the requirements `*` are: 0.1.0
the package `poly-commit` depends on `algebra`, with features: `jubjub` but `algebra` does not have these features.
LigeroPCS requires the prover & the verifier to do some Merkle tree operations in the non-interactive setting.
Specifically, the prover's commitment is a Merkle root, and the verifier should check well-formedness of such a commitment against the provider proofs (MT paths) for a couple of leaf indices.
We are trying to use a Merkle Tree from crypto-primitives inside the commit
method (and equivalently, Path
in the check
method) - which requires the parties to provide a concrete instantiation of a CRHScheme
and TwoToOneCRHScheme
.
Currently we can do it like:
impl<..., C> PolynomialCommitment<F, P, S>
for Ligero<F, C, ...>
where
...,
C: merkle_tree::Config + 'static,
{
...
fn check<'a>(
vk: &Self::VerifierKey,
...,
rng: Option<&mut dyn RngCore>,
) -> Result<bool, Self::Error>
where
Self::Commitment: 'a,
{
let mut rng = rng.unwrap();
// take the first committment
let labeled_commitment = commitments.into_iter().next().unwrap();
// IS THERE A BETTER WAY?
let leaf_hash_params = C::LeafHash::setup(&mut rng).unwrap();
let two_to_one_params = C::TwoToOneHash::setup(&mut rng).unwrap();
// well-formedness check internally verifies some merkle paths, which requires passing the params
Self::well_formedness_check(
labeled_commitment.commitment(),
&leaf_hash_params,
&two_to_one_params,
);
This looks a bit hacky, because probably the rng
parameter wasn't meant to be used for constructing structs that are part of the setup.
A more natural way to do this would be to have
pub struct LigeroPCS<
F: PrimeField,
C: Config,
...,
> {
leaf_hash_params: C::LeafHash,
two_to_one_params: C::TwoToOneHash,
}
and then when we need either of the params, we'd call self.leaf_hash_params
, for example. The problem is of course that neither the interface for commit
nor check
exposes a &self
parameter, so there's no way to access parameters from the struct implementing PolynomialCommitment
.
I propose changing the method signature of the associated PolynomialCommitment
methods to include a (non-mutable) &self
, e.g.
/// check but with individual challenges
fn check<'a>(
&self,
vk: &Self::VerifierKey,
commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
point: &'a P::Point,
values: impl IntoIterator<Item = F>,
proof: &Self::Proof,
challenge_generator: &mut ChallengeGenerator<F, S>,
rng: Option<&mut dyn RngCore>,
) -> Result<bool, Self::Error>
where
Self::Commitment: 'a;
The alternative for this Ligero PC is to have the merkle tree parameters be part of Self::{Verifier,.Commiter}Key
, but that introduces a great deal of additional constraints (serialization, Sync
etc.) which are cumbersome to enforce on C::LeafHash
etc.
The check functions run succinct_check without validating the inputs beforehand. If an input passed to check is malformed, then succinct check may throw an assertion error.
Streamline visibility in mod kzg
: currently it offers entities which can be obtained only from other modules which is confusing.
fn open...
are pub(crate)
and it seems like it's the only way to get Proof
in kzg10
; of course, it is used in other modules, but it makes disentangling that thing quite confusing.
Either pub
those functions from kzg
, either pub use
entities from kzg
in modules where they can actually be obtained and pub(crate)
them in kzg
.
I tried following the directions provided in the README.md. On running cargo build --release
, I am getting several issues, some of which are shown in the following image:
git commit hash is: 88c97d2
My OS is MacOS Ventura 13.1.
My system is MacBook Air M2.
Clang --version:
Apple clang version 14.0.0 (clang-1400.0.29.202)
Target: arm64-apple-darwin22.2.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin
In Aleo, we notice that Sonic/AuroraLight KZG10 has space for optimization in the pairing equation check.
https://github.com/arkworks-rs/poly-commit/blob/master/src/sonic_pc/mod.rs#L106
Currently, when Sonic handle k
combined comms, it provides k+2
entries to the Millier loop.
for (degree_bound, comm) in combined_comms.into_iter() {
let shift_power = if let Some(degree_bound) = degree_bound {
vk.get_shift_power(degree_bound)
.ok_or(Error::UnsupportedDegreeBound(degree_bound))?
} else {
vk.prepared_h.clone()
};
g1_projective_elems.push(comm);
g2_prepared_elems.push(shift_power);
}
g1_projective_elems.push(-combined_adjusted_witness);
g2_prepared_elems.push(vk.prepared_h.clone());
g1_projective_elems.push(-combined_witness);
g2_prepared_elems.push(vk.prepared_beta_h.clone());
However, indeed you can reduce it to l+2
where l
is the number of combined comms that require a degree bound. Basically, all the entries where the second term is prepared_h
can be put together.
Sum the combined comms that do not require a degree bound first and then combine it with the existing entry about witness, on prepared_h
.
Currently, opening challenges are univariate, such that challenges={x, x^2, x^3, ...}
where x
is random. Now ark-sponge
is stable, so we want to use the sponge API instead. Specifically, opening challenges will have two strategies:
x
from sponge, and challenges[i] = x^{i+1}
We define the strategy as an enum
, and define a challenge generator to replace opening_challenges: dyn Fn(u64)-> F
.
#[derive(Copy, Clone)]
pub struct ChallengeGenerator<'a, S: 'a + CryptographicSponge> {
sponge_state: &'a mut S,
strategy: ChallengeStrategy
}
pub enum ChallengeStrategy {
Multivariate,
Univariate
}
ChallengeGenerator
will have method next()
to get the next random challenge.
PolyCommit
pub trait PolynomialCommitment<F: Field, P: Polynomial<F>: Sized, S: CryptographicSponge> {
fn setup<R: RngCore>(
max_degree: usize,
num_vars: Option<usize>,
rng: &mut R,
) -> Result<Self::UniversalParams, Self::Error>;
fn trim(
pp: &Self::UniversalParams,
supported_degree: usize,
supported_hiding_bound: usize,
enforced_degree_bounds: Option<&[usize]>,
) -> Result<(Self::CommitterKey, Self::VerifierKey), Self::Error>;
fn commit<'a>(
ck: &Self::CommitterKey,
polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>,
rng: Option<&mut dyn RngCore>,
) -> Result<
(
Vec<LabeledCommitment<Self::Commitment>>,
Vec<Self::Randomness>,
),
Self::Error,
>
where
P: 'a;
fn open<'a>(
ck: &Self::CommitterKey,
labeled_polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>,
commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
point: &'a P::Point,
opening_challenges: ChallengeGenerator<_, S>,
rands: impl IntoIterator<Item = &'a Self::Randomness>,
rng: Option<&mut dyn RngCore>,
) -> Result<Self::Proof, Self::Error>;
fn batch_open<'a>(
ck: &Self::CommitterKey,
labeled_polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>,
commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
query_set: &QuerySet<P::Point>,
opening_challenges: ChallengeGenerator<_, S>,
rands: impl IntoIterator<Item = &'a Self::Randomness>,
rng: Option<&mut dyn RngCore>,
) -> Result<Self::BatchProof, Self::Error>;
fn check<'a>(
vk: &Self::VerifierKey,
commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
point: &'a P::Point,
values: impl IntoIterator<Item = F>,
proof: &Self::Proof,
opening_challenge: ChallengeGenerator<_, S>,
) -> Result<bool, Self::Error>
where
Self::Commitment: 'a;
fn batch_check<'a, R: RngCore>(
vk: &Self::VerifierKey,
commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
query_set: &QuerySet<P::Point>,
evaluations: &Evaluations<P::Point, F>,
proof: &Self::BatchProof,
opening_challenge: ChallengeGenerator<_, S>,
) -> Result<bool, Self::Error>
where
Self::Commitment: 'a;
fn open_combinations<'a>(
ck: &Self::CommitterKey,
linear_combinations: impl IntoIterator<Item = &'a LinearCombination<F>>,
polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>,
commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
query_set: &QuerySet<P::Point>,
opening_challenge: ChallengeGenerator<_, S>,
rands: impl IntoIterator<Item = &'a Self::Randomness>,
rng: Option<&mut dyn RngCore>,
) -> Result<BatchLCProof<F, P, Self>, Self::Error>
where
P: 'a,
Self::Randomness: 'a,
Self::Commitment: 'a;
fn check_combinations<'a, R: RngCore>(
vk: &Self::VerifierKey,
linear_combinations: impl IntoIterator<Item = &'a LinearCombination<F>>,
commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
eqn_query_set: &QuerySet<P::Point>,
eqn_evaluations: &Evaluations<P::Point, F>,
proof: &BatchLCProof<F, P, Self>,
opening_challenge: ChallengeGenerator<_, S>,
) -> Result<bool, Self::Error>
where
Self::Commitment: 'a;
}
Using the PCS in a wider context will require absorbing the commitment for Fiat Shamir.
The current challenge is that Absorb
is not implemented for AffineRepr
, and the current pairing-based schemes in this repo have commitments of the form:
pub struct Commitment<E: Pairing>(
/// The commitment is a group element.
pub E::G1Affine,
);
We unfortunately can't add a blanket impl like:
impl<T> Absorb for T
where
T: AffineRepr,
{
fn to_sponge_bytes(&self, dest: &mut Vec<u8>) {
todo!()
}
fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
todo!()
}
}
Rust complains "conflicting implementations of trait absorb::Absorb
for type u8
".
We could add Absorb
on AffineRepr
in the ec crate. However, aside from creating a cyclic dependency from ec
to crypto-primitives
, I think this is not the best design.
One solution is to further restrict G: AffineRepr + Absorb
. This propagates into a lot of trait bounds in the poly-commit repo, though. The upside is that it doesn't require any upstream changes, and the two current implementors of AffineRepr
which are the structs short_weierstrass::Affine
and twisted_edwards::Affine
already have Absorb
implemented.
Larger breaking refactor that makes use of the fact that most pairing computations (and certainly our implementations in ec::models
) only ever support SW. The proposal is then to rip out the associated type G1Affine
from Pairing
, and restrict the class of pairings that can be done to SW-curves, so that we can have:
pub struct Commitment<P: SWCurveConfig>(
/// The commitment is a group element.
pub Affine<P>,
);
This almost works, as we still have IPA Commitment
struct here in poly-commit which uses the trait AffineRepr
(i.e. not an associated type from Pairing
):
pub struct Commitment<G: AffineRepr> {
/// A Pedersen commitment to the polynomial.
pub comm: G,
...
}
And so mixing in Option 2 would need to happen anyway, but limited to one PCS.
Any other ideas?
In the test_template function and equation_test_template in lib.rs, the randomly generated degree_bounds are sampled randomly from a range up to max_degree when they should have a maximum degree of supported_degree. So, degree_bounds passed into the trimming function can be invalid.
Hello,
Does this scheme allow the commitment to a certain degree d polynomial, or only to a polynomial of at most degree D? In other words, can you verify the degree of the committed polynomial?
Thanks!
The KZG10
struct which implements a polynomial commitment scheme on its own does not implement the PolynomialCommitment
trait. Either it should be implemented and/or the trait itself should be simplified to make this implementation easier.
latest commit: cafc05e
Instead of a trusted dealer generating the UniversalParams, can they be generated in a distributed way?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.