Created by Matteo Campanelli

Date: 20230213

(A more formal version of some of the notes for batch Testudo are available here. Also embedded at the end of this document)

Main Protocol

The following notes build up to batch Testudo by describing a batch (data parallel Spartan) starting from Spartan itself. See last two slides if you are in a rush to see what the batch case Spartan looks like. See last slide for efficiency comparison.

Spartan_batch.pdf

V’s cost for public input processing

The verifier’s steps for public input processing are derivable straightforwardly from Spartan pg 20; they are basically the same.

For the special case of many proofs on the same input, see this doc (also embedded below)

https://hackmd.io/@LIRa8YONSwKxiRz3cficng/HyQHHcsAi

Proof size

Proof size in Batch Testudo follows largely the trend in the original Testudo. If one excludes the computational commitment part, only difference is that:

• the MIPP/PST is done one the size of the global witness (the concatenation of all subwitnesses)