LDT Trait

[tsunrise]

LDT Trait

We need to define LDT trait, which is high-level API for LDT. Implementation of LDT trait is stateless, and only has static method. Here is the proposed interface:

trait LDT<F: PrimeField> {
    
    type LDTProof;
    type LDTParameters;
    
    fn ldt_info(degree_bound: usize) -> (usize, RadixCosetDomain);
    
    fn prove<P: OracleWithCodewords>
        (param: Self::LDTParameters, codewords: IntoIterator<(&'mut P, usize)>) -> Self::LDTProof;
        
    fn verify<P: Oracle>
        (param: Self::LDTParameters, codewords: IntoIterator<(&'mut P, usize)>, proof: Self::LDTProof)
}

• ldt_info: Given the desired degree bound, LDT will returns the actual degree bound that will be enforced, and coset domain by which codeward will be used.
• prove: Given a list of codewords oracle with corresponding degree bound, return a proof showing the degree bound is enforced. The codewords oracle will not be in the Proof struct, and verifier needs the codewords oracles along with proof to complete.
  • Take FRI for example, LDT proof will contain oracle for each prover message involved in LDT. Such oracle does not need to contain entire codeword, but only the leaves being queried.
• verify: Given a list of codewords and LDT proof, verify if the codewords degree bound is actual enforced.

For constraints, there will be no prove function. The other two will have similar interface.

Oracles

We will also include an oracle trait in this repo. ark::bcs will use this trait as well.

• Oracle trait is a message oracle that can be queried. The oracle does not need to contain the entire message, but only need to contains messages that are going to be queried. Oracle is mainly used by verifier.

trait Oracle<F>{
    /// query some bits, and return answers and merkle tree path
    /// having merkle tree root inside implementation
    fn query(&mut self, position: &[usize]) -> Result<Vec<F>, ...>;
}

• OracleWithCodewords is an extension trait, which requires the oracle to contain the entire message for prover to use. Access to the entire messages will not be counted as a query.

trait OracleWithCodewords<F>: Oracle<F>{
    fn get_message(&self) -> &Vec<F>
}

Oracle will also have R1CS constraints with similar interface.

---

For Admin Use

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

[tsunrise]

The high-level implementation of LDT and its trait will be in ark-bcs instead. ark-bcs will be released soon!