Using the mentioned protocol, “RME-based common exponent Schnorr protocol” (Henry14 3.2.3.3), the verifier performs 2+k ECC mults per proof, where k is the number of silent payment outputs, but the k mults can be shared for a batch of proofs, which large transactions can be a significant improvement in verifier complexity.
Compared to this protocol the strawman protocol I described in the previous comment is broken in two ways, not just one:
- two verification equations are needed, instead of only one (section 4.2 describes a lattice basis attack on soundness since the prover’s responses are undetermined)
- de-linearization (or in the multiplicative terms of Henry14, RME) is needed for soundness as well (see section 3.1.4.3)
In a non-interactive setting, the t_i terms of the random linear combination is generated by hashing.
If $t_i = H(B_1, B_2, \dots, B_k)$ ($B_i$ is supposed to be {B_{scan}}_i but that apparently isn’t in github’s latex regex =P) the $k$ proofs would share the same delinearized sum $\sum_{i=1}^k t_i B_i$, which appears as a term in the 2nd verification equation. This reduces $k^2$ ECC mults to $k$ (but asymptotically is the same because of other side of the equation still has a $\sum_{i=1}^{k} t_i S_i$ term where $S_i = aB_i$ is a public input).
Unfortunately the full set of SP_V0_INFO fields to be finalized before DLEQ proofs can be computed in that case, but if I understand Lemma 3.5 I think the $t_i$ values used for this can be derived as $t_i = H(B_i)$ without destroying the proof of soundness. If this is correct then this reduction in verifier computation could be applied to batch-verify whatever $k$ batch-DLEQs, but number of roundtrips is not reduced because new proofs would be needed for the new outputs, and verifiers would need to be given explicit subsets of the outputs for each batch proof indicating what it covers, instead of being able to construct the proof statements implicitly from the set of all SP_V0_INFO fields, so it’s not clear that this is a meaningful improvement over hashing all of the $B_i$s to delinearize.
