arkworks-rs / bcs Goto Github PK

Summary

We need to support multiple evaluation domains for LDT, and allow the user to have flexibility to choose which domain they want when they send polynomials.

Warning ahead: this can increase cognitive overhead for users (users will potentially need to deal with LDT implementation stuff) and make this library hard to use if not doing it elegantly. Need to find a way to support this feature without making the API too complex.

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

One good thing in libiop's bcs is that it contains proof of work for Fiat-Shamir style transform to increase hardness for each round submission. We can probably proof of work algorithms in crypto-primitives and use it here once it's ready.

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

Problem Definition

For now, in BCS algorithm, LDT uses a separate transcript, and keeps a mutable reference of all oracles in another transcript. This is counterintuitive because the LDT algorithm is querying some oracles outside its own transcript.

Proposal

In the future, we can let both use same transcript. Instead of giving a Vec<&mut Oracle> to LDT, we can just give them Vec<MsgRoundRef>, which can make code much easier to understand.

Blocking: #6

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

Summary

As discussed with @ValarDragon , to implement more efficient sumcheck (which is in Aurora paper), we need to have Virtual Oracle implemented. As the name suggests, the virtual oracle only depends on previously sent oracles, so querying this virtual oracle is the same as querying some previous oracles.

Virtual oracle will also be used for degree test. It will have test_bound which is used by LDT, and constraint_bound, which is helpful for determine number of queries.

Some basic structure for virtual oracle. For now, we assume all oracles are evaluated on the same evaluation domain.

struct VirtualOracle {
     dependencies: Vec<MsgRoundRef>, // also need to be virtual oracle
     point_evaluator: Box<dyn fn (transcript_messages, dependencies, query: usize, query_point: F) -> F,
     coset_evaluator: Option<Box<dyn fn (transcript_messages, dependencies, coset_query: usize, coset: Radix2CosetDomain<F>) -> F>>
     constraint_degree_bound: usize.
     tested_degree_bound: usize
}

• dependencies contains the OracleRef (we can think it as an Oracle ID) used by this virtual oracle.
• point_evaluator is a function that given the previously sent oracles and query, return the point
• coset_evaluator is a similar function that can be used to calculate coset
• constraint_bound will probably not used by LDT for now, but is a hint to determine number of queries for soundness
• tested_bound will be used for LDT.

For example, we have a virtual oracle h(x) = f(x)h(x)/Z_H(x) where Z_H(x) is a vanishing poly for user defined H (think about summation domain for sumcheck). Then, the point evaluator will be |msgs, query| f_oracle.query(query) * h_oracle.query(query) / precomputed_Z_H.query(query).

We need to think carefully on how to implement this in constraints. Is there a way to not let user define the point evaluator and coset evaluator twice? If not, we also need a test to make sure point evaluator is consistent.

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

Summary

Implement univariate lincheck as described in BCRSVW19.

Proposal

Here is the writeup for lincheck protocol: https://hackmd.io/@tsunrise/H11cj5Byq

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned