Non-power-of-two inner product proof

[oleganza]

Problem

Inner product proof requires inputs with power-of-two items. This could hurt performance of proving and verification up to 2x on input sizes that are just-a-bit-larger that a power of two.

For example, a confidential assets scheme has 8+64 multipliers per transfer, where 8 are used for mixes and shuffles, and 64 are for the range proof. This means, the closest power of two is exceeded by merely 11%, making the padding increase the cost almost two-fold.

Suggestion

We can modify the IPP in a compatible manner (that is, when the input length is power-of-two, IPP remains exactly the same) by padding the inputs with zero scalars 0 and identity points O. This padding does not change the original relation and, due to the use of challenges when folding the lo/hi halves of the vectors, does not interfere with other scalars or generators.

P = <a, G> + <b, H> + <a,b> Q = 
  = <a, G> + <0, O> + <b, H>  + <0, O> + <a,b> Q + <0,0> Q

This way, the verifier does not have to include operations on the identity points in the megacheck, and therefore removes the overhead.

To make it similarly more efficient for the prover, we can rearrange the padding in the following manner:

1. Let n be size of inputs and k = ceil(log_2(n)) the next power of two.
2. Pad the inputs to the even size n' = 2*ceil(n/2). In other words, add 0 and O to the scalars and generators accordingly, if the input size is odd. Otherwise, do nothing.
3. Split each input vector in half.
4. Pad each resulting vector to an even size n'' = 2*ceil(n'/2) again (if needed).
5. We can proceed until we get to the size one. This will effectively pad the input with interspersed zeroes.

18-item input to be padded to 32-item input:
[a b c d e f g h i j k l m n o p q r]

We need 14 zeroes which we will arrange as 2*(4+2+1):

a b c d e f g h i j k l m n o p q r

already even, no padding added:

a b c d e f g h i j k l m n o p q r

split in half and fold (9-item vector of [a+j, b+k, ...]):

a b c d e f g h i
j k l m n o p q r

pad to even:

a b c d e f g h i 0
j k l m n o p q r 0

split in half and fold (5-item vector of [a+j+f+o, b+k+g+p, ...]):

a b c d e
j k l m n
f g h i 0
o p q r 0

pad to even:

a b c d e 0
j k l m n 0
f g h i 0 0
o p q r 0 0

split in half and fold:

a b c
j k l
f g h
o p q
d e 0
m n 0
i 0 0
r 0 0

pad to even:

a b c 0
j k l 0
f g h 0
o p q 0
d e 0 0
m n 0 0
i 0 0 0
r 0 0 0

split in half and fold:

a b
j k
f g
o p
d e
m n
i 0
r 0
c 0
l 0
h 0
q 0
0 0
0 0
0 0
0 0

(already padded)

split in half and fold:

a
j
f
o
d
m
i
r
c
l
h
q
0
0
0
0
b
k
g
p
e
n
0
0
0
0
0
0
0
0
0
0

The result is equivalent to padding the input as:

a b c 0 d e 0 0 f g h 0 i 0 0 0 j k l 0 m n 0 0 o p q 0 r 0 0 0

The big downside of this approach is that indices of the points get shifted in a funny pattern that the megacheck has to be aware of. But hopefully there is a not very horrible formula to do that.

[suyash67]

Is the above strategy for non-power of two secret vectors implemented anywhere? I am working on a bulletproofs-like protocol for a different problem. Seems like it is unavoidable to use non-power of two in my protocol. Any help is much appreciated.

[hdevalence]

I could be mistaken, but no, I don't think so.