Fully succinct SNARK ⇒ SNARG for NP with sublinear proofs
Statement
A fully succinct SNARK yields a SNARG for NP with sublinear proofs: for an relation whose verifier runs in time , a proof that is a proof that . Fix with for ; instances of length at most 1 are padded, or decided by directly. The statements then satisfy , so the SNARK’s knowledge soundness for that applies. The comes from alone, and completeness carries over. With the polynomial bounding the SNARK’s proofs, , and since is a polynomial, for every constant there is a polynomial with . Knowledge soundness for adaptively chosen statements implies adaptive soundness — folklore.