Цель высокого уровня: дерево Веркла (дерево Меркла, использующее алгебраические векторные обязательства на каждом уровне, а не хэши) с глубиной г
где я могу доказать существование н
пары ключ/значение в дереве. Предполагая, что у верификатора уже есть обязательство корня дерева, а также пары ключ/значение, я хотел бы, чтобы дополнительный размер доказательства был сублинейным в любом г
или же н
, а в идеале и то, и другое. Нулевое знание не требуется.
Я просмотрел сообщения Виталика и Данкрада о аргументе внутреннего продукта в стиле Bulletproofs и пакетной обработке полиномиальных обязательств KZG на https://vitalik.ca/general/2021/06/18/verkle.html и https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html.
Если я правильно понимаю, то для доказательства n отношений вида f_i (x_i) = y_i
, предполагая, что у проверяющего уже есть все x_i/y_i, доказательство состоит из одного обязательства для каждого многочлена f_i
, а также пакетное доказательство постоянного (относительно n) размера. Обязательства на каждый узел являются здесь основными затратами и означают, что мы можем добиться лишь приблизительного (глубина дерева Меркла / глубина дерева Веркла ~= 8x) улучшения пропускной способности.
Обратите внимание, что для каждого пути эти отношения обладают тем свойством, что f_i(x_i) = F_{i+1}
, куда Ф
представляет обязательство. Кажется, это может помочь сократить доказательство для каждого пути, но у меня нет конкретных идей.
Любые ссылки/соответствующие документы будут полезны. Спасибо!