Recursive Plonk+FRI+GKR

A *very* rough cost estimate.

by Daniel Lubarov

HTML

<h1>Recursive PLONK + DEEP-FRI</h1>
<p>This is a cost estimate for a recursion scheme with</p>
<ul>
<li>TurboPLONK style arithmetization</li>
<li>A DEEP-FRI-like scheme for verifying constraints on polynomials</li>
<li>optionally, a GKR sub-protocol to verify MiMC hash evaluations, as suggested <a href="https://hackmd.io/@uCHu_NMSQ4mIUvA8i4qAyg/rkxBcmvcI">here</a>.</li>
</ul>
<p>This is a very rough cost estimate. We only account for field multiplications, ignoring other costs like additions or memory lookups. We're likely over-estimating argument sizes, since the estimate includes overlapping Merkle proofs.</p>
<p>The estimate is especially crude if the GKR option is enabled. We don't currently account for GKR proving costs. For the GKR verifier, we only account for the cost of evaluating MLEs of hash inputs/outputs, which dominates asymptotically. Notably, we don't account for the cost of generating the initial Fiat-Shamir challenge, which is a major unknown. There are some <a href="https://hackmd.io/@uCHu_NMSQ4mIUvA8i4qAyg/rkxBcmvcI#Generating-the-initial-randomness">ideas</a> for doing this efficiently, but they have not been proven sound.</p>
<hr />

<div id="fri">
  <p>Degree of inner proof: 2^<input v-model="inner_degree_log"> = {{ inner_degree }}</p>
  <p>Security parameter: <input v-model="security_bits"> bits</p>
  <p>Field size <input v-model="field_bits"> bits</p>
  <p>Cost of field multiplication: <input v-model="field_mul_ns"> ns</p>
  <p>Parallelism: <input v-model="threads"> threads</p>
  <p>Codeword rate: <input v-model="rate"></p>
  <p>Hash: <select v-model="hash">
    <option value="gmimc">GMiMC_erf</option>
    <!-- <option value="mimc">MiMC-2p/p</option> -->
    <option value="rescue">Rescue</option>
    <!--<option value="poseidon">Poseidon</option>-->
  </select></p>
  <p v-if="hash == 'gmimc'">GMiMC rounds: {{ gmimc_rounds }}</p>
  <p v-if="hash == 'rescue'">Rescue rounds: {{ rescue_rounds }}</p>
  <p><input type="checkbox" v-model="gkr">...

CSS

input {
  width: 50px;
}

Vue

let app = new Vue({
  el: '#fri',
  
  data: {
  	gkr: false,
    conjecture: true,
    inner_degree_log: 17,
  	security_bits: 128,
    field_bits: 64,
    field_mul_ns: 3,
    threads: 6,
    rate: 1/8,
    hash: 'gmimc',
  },
  
  computed: {
    inner_degree() {
      return Math.pow(2, this.inner_degree_log);
    },
    
  	delta() {
      if (this.conjecture) {
      	return (1 - this.rate);
      } else {
    		return (1 - Math.sqrt(this.rate));
      }
    },
    
  	rounds() {
      // Simplified soundness analysis.
      //let log = Math.log2(Math.max(1 - this.delta, Math.sqrt(this.rate)));
      let log = Math.log2(1 - this.delta);
    	return Math.ceil(-this.security_bits / log);
    },
    
    hashes_per_round() {
      // In the first round, each query involves three Merkle proofs, corresponding to the three rounds of prover messages in Plonk, plus one for preprocessed polynomials.
      let hashes = 4 * this.inner_degree_log;
      
      // In the first round, some of the oracles' leaves have several field elements, so a bit more hashing is needed to compress them to a single leaf element.
      hashes += 6;
      
      // Merkle proofs for subsequent rounds.
      for (var degree_log = this.inner_degree_log - 2; degree_log > 2; degree_log -= 2) {
        hashes += degree_log + 2;
      }
      
      return hashes;
    },
    
    argument_size_kb() {
    	return Math.round(this.argument_size_bits / 8 / 1024);
    },
    
    argument_size_bits() {
    	return this.rounds * this.argument_bits_per_round;
    },
    
    argument_bits_per_round() {
    	let bits_per_hash = this.security_bits * 2;
    	let bits = 0;
      
      // In the first round, each query involves three Merkle proofs, corresponding to the three rounds of prover messages in Plonk, plus one for preprocessed polynomials.
      bits += 4 * bits_per_hash * this.inner_degree_log;
      
      // In the first round, some of the oracles' leaves have several field elements, so a bit...