Score:2

Can we pad witness of bulletproof and dory to be exponential size?

cy flag

Bulletproof and dory reduce the witness size by a half during each interaction, until the witness is compressed to be only one element. But what about the witness is not precisely exponential size? Can we still use the two schemes by padding the witness?

fgrieu avatar
ng flag
Had to google [Bulletproffs](https://eprint.iacr.org/2017/1066) and [Dory](https://eprint.iacr.org/2020/1274).
Score:1
ru flag

I can answer this for bulletproofs; I assume that the Dory set-up is similar.

Bulletproofs allow aggregation of the computation of two verifications of distinct commitment statements into a single computation per page 13 of the original paper. Thus if we wish to verify $n$-statements, we can aggregate these into $\lceil n/2\rceil$ computations (with one of our statements possibly not paired), then aggregate these into $\lceil (\lceil n/2\rceil)/2\rceil =\lceil n/4\rceil$ computations (again with at most one statement possibly unpaired) and thence $\lceil n/2^i\rceil$ computations for $i=3,4,5,\ldots$ once we reach $i=\lceil(\log n)/\log 2\rceil$ we have aggregated to a single computation and there is no further benefit. Note that we do not require that $n$ is power of 2, we simply possibly omit at most one statement from aggregation at each level.

We could instead add some redundant statements, or publicly known statements to increase the initial collection of statements to a power of 2 and not increase the overall final value of $i$ (which could be termed padding), but this does not add anything beyond additional computational overhead.

Walker avatar
cy flag
Thanks a lot. Just like zero-padding.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.