Confusion over counting for 600 vector case

[kallewoof]

This paragraph:

https://github.com/AdamISZ/from0k2bp/blob/7b3c6dbe121c5fd8eaad5d018c39c4b2aff0bbe7/from0k2bp.tex#L1454-L1458

I tried to do this, by splitting the 600 length vectors into vectors of 10 elements each ([a1-a10, a11-a20, ...]) and doing the diagonal iteration. Since the length of this new vector is 60, this gives us -59 <= k <= 59 minus the k=0 case, resulting in 118 commitments for the first reduction. Where does "2*10- 1 = 19" come from?

[AdamISZ]

You can do it the other way - split the 600 length vectors into vectors of 60 elements each.

So a_1 = [a_1, a_2, ... , a_60] ; a_2 = [a_61, ...] etc.

Then the equivalent of the matrix on p. 23 would have 10 rows and 10 columns, and so you'd get the number of diagonals as 2x10 -1

There's a brief note in 5.4 that I think is relevant ('linear in the sum of the factors').

[kallewoof]

Ahh, that makes sense.

Is there a balance thing here? Why not do e.g. 6x100 instead to get even more compactness?

[AdamISZ]

Well, suppose you did 6 x 100 and then stopped; then you'd have to reveal 100 in the final step.

So you might do 6 x 100 and in the next recursion step do 100 = 10x10 etc. ... so as you can see there are multiple options. I chose 600 specifically because it had so many factors :)

When you get to the next section (bulletproofs) or earlier? (I forget exactly) I mumble something about halving at each step being "in some sense optimal". I suspect it depends on some fiddly details, but generally I think you want as many factors as possible to minimise the total you reveal.

[kallewoof]

I definitely didn't realize that, but it makes sense now that you mention it. Thanks a lot!