Ключевым моментом является то, что они используют универсальную схему:
Когда мы создаем SNARK для схемы SAT, мы используем QSP для универсальная схема, который имеет размер $O(|C| \log |C|)$ куда $|С|$ — максимальный размер схем в задаче о выполнимости.
Универсальная схема — это схема, которая может вычислять любую другую схему. В этом обобщении и появляется дополнительный логарифмический множитель. Это объясняется в начале раздела 3:
Для прямого сравнения с Гротом мы можем оперировать $u$ быть адаптивно выбранной схемой путем построения $R$ [(отношение)] из
универсальная схема. В этом случае размер вычислительной схемы $R$ может быть больше
чем $|у|$ на логарифмический коэффициент, что соответственно увеличивает размер CRS и вычисление прувера до $\тильда{О}(|и|)$. Если $u$ ... можно выбирать неадаптивно, наша схема становится более эффективной.
$\тильда{О}$ нотация скрывает логарифмические множители. В конце упоминают, что зная конкретную схему $u$ было бы более эффективным - это то, что вы имеете в виду. Причина адаптивной надежности заключается в том, что это более правильно моделирует то, как протокол, вероятно, будет использоваться в реальных ситуациях - часто вы ожидаете, что доказывающий увидит CRS, прежде чем начать свое доказательство, чтобы они могли выбрать утверждение, которым они являются (возможно, ложно) пытаются доказать на основе CRS (адаптивно).
Эта бумага объясняет эффективную конструкцию универсальной схемы и дает объяснение того, как такие схемы работают в предварительных упражнениях (например, см. стр. 4-7). Интуитивно логарифмический коэффициент вводится потому, что эти схемы, как правило, строятся рекурсивно, причем каждая подзадача примерно вдвое меньше, поэтому у нас есть обычный логарифмический коэффициент, который мы получаем при работе с бинарными деревьями. Для лучшего объяснения я думаю, что лучше всего прочитать саму статью.
