Halo Infinite reading notes === * [x] (page 1) "zk-SNARKs" => "zkSNARK" (the reasoning is that the long-form "zero knowledge SNARK" doe not have a dash, and that similarly prefixed terms such as "zkRollup" and "zkVM" do not usually have a dash) * [x] (page 1) "both private and public" => "private or public" * [x] (page 1) "a polynomial f ∈ F[x]" => "a polynomial f ∈ F[X]" * [x] (page 1) "of degree d" => "of degree at most d" * [x] (page 1) consider adding an index after the abstract (the paper is long with many sections) * [x] (page 2) "o(d log F)" => "o(d log |F|)" * [ ] (page 2) " including DARK, FRI, and Dory" => consider adding a footnote explaining the slight abuse of notation for FRI which is natively a low-degree test * [x] (page 2) "or equivalently Algebraic Holographic Proofs" => "or a equivalently Algebraic Holographic Proof" * [x] (page 2) "or no trusted setup [BFS20]" => may be worth adding references for Dory and FRI * [x] (page 2) "where the operators of the blockchain only need to store the latest proof that attests to the entire correct history of all transactions" => This sweeps under the rug important details such as data availability and the type of "operator" involved. A more restricted (and technically correct) statement could be "where the latest proof attests to the validity of state transitions in the blockchain history". * [x] (page 3) "and add runs in time poly(λ)" => "and add must run in time poly(λ)" * [ ] (page 4) "This includes the post-quantum FRI scheme." => It would be very helpful to add a sentence or two giving an intuitive explanation. If I understand correctly the performance gains of Halo Infinite versus naive recursive composition come from not having to do heavy Merkle proof verification in the recursive circuit. * [ ] (page 4) "a heuristic security assumption because they involve instantiating random oracles with concrete hash functions" => Explaining how this goes a bit further than the Fiat-Shamir transformation which also instantiates random oracles with concrete hash functions. My understanding is that the hash functions are instantiated in a non-black-box fashion inside circuits. * [ ] (page 4) "a heuristic security assumption" => Consider giving this assumption a name so that folks can easily refer to it. Brainstormed candidate name: "extended Fiat-Shamir assumption", "non-black-box Fiat-Shamir", "recursion assumption", "Halo assumption". * I approve of giving this a name. How about "white box Fiat–Shamir heuristic"? —Daira * [x] (page 6) "If G is abelian then for any n ∈ N and g ∈ G the element n·g is defined as adding n copies of g" => Consider removing "If G is abelian" which is a bit confusing given that the notation all works for non-abelian groups. * [x] (page 6) "A two-party interactive protocol name Label between parties A and B, where a and b are respectively private inputs to A and B, outA and outB are their private outputs, and c is a common input to both parties is denoted" => Should "name" be "named"? * [x] (page 6) "Label(A(a), B(b), c)" => "Label(a, b, c)" * [x] (page 6) "interactive protocols are a pair" => "an interactive protocol is a pair" or "interactive protocols are pairs" * [x] (page 6) "NI-Label(a, b)" => "NI-Label(a, c)" * [x] (page 6) "VLabel(tr, outB) → b ∈ {0, 1}" => What about the public input c? Is that folded into the transcript? * [x] (page 7) "NI-ProtocolName(a, b)" => Should this be "NI-Label(a, c)"? (Notice both the replacement of b by c, and the change of name.) * [x] (page 7) "soundness against restoration attacks" => Consider replacing by "state restoration soundness" which is the term used in the IOP paper. Also consider noting it is equivalent to round-by-round soundness (see https://eprint.iacr.org/2019/1261.pdf). * [ ] (page 7) inconsistency in various places between "zero knowledge" and "zero-knowledge" * [ ] (page 7) "An interactive proof satisfies honest verifier zero-knowledge" => Consider replacing "satisfies" by "is". * [ ] (page 8) "polynomials of degree d" => "polynomials of degree at most d" (same comment on page 11, 19, 44, 55) * [ ] (page 8) "and an opening string open ∈ {0, 1}*" => I'm confused by the opening string. You mention in an email thread it is a "hint". Can you give a non-trivial example of what the opening string is for some concrete PCS? BTW, why not cal it "hint" as opposed to "opening string". That would be clearer IMO. * [ ] (page 8) "Verify(pp, f, open, C)" => to match the order of Commit(pp, f) -> (C, open) would be a bit cleaner as "Verify(pp, f, C, open)" * [x] (page 8) "for a commitment C ∈ G," => extraneous comma * [ ] (page 8) "If the Eval verifier runs in time o(d·log |F|)" => Consider removing the dot in o(d·log |F|) to be consistent with page 2 * [ ] (page 8) "A non-succinct PCS is only interesting if it is hiding" => This reads as possibly an overstatement. A non-succint PCS could conceivably have interesting concrete properties, no? * https://eprint.iacr.org/2020/1618 shows that this statement is not correct; a non-succinct, non-hiding PCS can be interesting. —Daira * [ ] (page 8) "NI-Eval(pp, f, open, C, x, y)" => The paper mixes both the f(x) = y and f(z) = y conventions. For consistency I'd pick one and harmonise. * [x] (page 9) "must know a polynomial f(X)" => must know a polynomial f" * [x] (page 9) "binding as standard commitment scheme" => "binding as standard commitment schemes" * [x] (page 9) "b0 = b1 != 0" => a bit cleaner to write "b0 = b1 = 1" * [x] (page 9) "x0 != x1" => x0 and x1 are not defined * [x] (page 9) "≤ negl" => "≤ negl(λ)" (also use the same font as in "Basic notations" on page 6) * [ ] (page 9) The paragraph starting with "Some schemes" has compressed line heights * [ ] (page 10) "for a integer" => "for an integer" * [ ] (page 10) The definition of a homomorphic PCS is quite abstract. Would be great to illustrate what the groups G, H are for some concrete PCS, as well as concretely illustrate the homomorphisms φ and χ. * [x] (page 10) In the same way that the group G is called the "commitment group" it would help to give the group H a name as well. Is it the "hint group"? * [ ] (page 11) "over a prime field F = Fp" => Why the restriction to prime fields? * [ ] (page 11) The vector open = (open1, ..., openl) sometimes has a little arrow on it and sometimes not. * [x] (page 12) "an amortization ratios" => "amortization ratios" * [x] (page 12) "a PCS that is plausibly post-quantum" => Why "plausibly"? It was shown in https://eprint.iacr.org/2019/834.pdf that the PCS is provably secure in the QROM. * [x] (page 13) "once FRI Eval is run" => wrong font for "Eval" * [x] (page 13) "For technical reasons, unless the linear combination coefficients are chosen randomly, the aggregate commitment also needs to include a second commitment and is therefore not size-optimal." => Where can I learn more about this technicality? * [x] (page 13) "The prover can uses" => "The prover uses" * [x] (page 14) "ri ←R [0, 2^\kappa]" => inconsistent notation with ←$ * [x] (page 16) "Compiler III (hiding)Parameters" => missing space before "Parameters" * [x] (page 17) "Let f1, ... fk" => missing comma before fk * [x] (page 17) "Let f1, ... fk" => for notational consistency may be worth using l (as opposed to k) * [ ] (page 18) The paragraph starting with "The public output is a tuple" has compressed line heights. * [x] (page 19) "if and only f_i" => "if and only if f_i" * [x] (page 19) "The zero-knowledge simulator for this protocol," => extraneous comma * [x] (page 21) Looks like f' and open' have their 1 and q swapped. * [x] (page 30) "This conjecture is true in the random oracle model when n is a constant independent of the security parameter." => consider adding a reference * [ ] (page 42) "the Bulletproof PCS" => "the Bulletproofs PCS" * [ ] (page 43) "see Protocol 8.2 of Aurora [BCR+19])" => consider expanding a bit; the Aurora paper is quite notation-heavy and hard to follow * [x] (page 51) "and another that uses private PCS aggregation for the purpose of constructing efficient SNARKs" => "SNARKs and PCD"?