Thank you for thinking about this! I’m by no means an expert on these subjects, but here are my thoughts:
Regarding your first comment: I’m not sure I see how the scheme I proposed or the scheme you proposed here can increase security. It seems to me that both schemes make it more difficult to cheat at several layers simultaneously, but they don’t make it any more difficult to cheat at any given layer. I guess the question is, if you are able to cheat in a single layer, does this compromise the entire proof or do you need to cheat at more than one layer? If the former, then at best, the security stays the same.
Regarding other optimizations you mention here:
- Already implemented - reduced proof size by quite a bit.
- This could be significant too - though it’s quite a bit of work (primarily because I’d need to write optimized versions of octic polynomial evaluation/interpolation functions - otherwise proving time would suffer quite a bit).
- I’m not sure the benefit here would be meaningful. Yes, we could send fewer than 256 values, but then we’d have to send Merkle branches for the values that we do send. This probably would offset the savings quite a bit - so, net savings are unlikely to be more than 1% of proof size, and potentially less than that.
- I’m not sure I fully understood this. Is the suggestion to increase the number of last layer values beyond 256? If so, I think it could result in some savings - but I’ll need to think more about the exact benefit.
Regarding your last comment: the only tree the attacker would manipulate to influence the choice of indexes is the base layer tree (tree at depth d). All other trees are “fixed” - meaning, if you change any of them, you’d be changing the base layer tree too (so, it’s probably easier to manipulate the base tree directly).
One of the open questions in mind is: does my scheme make it somehow easier for the attacker to build trees at each layer in such a way that the probability of cheating at any one layer increases.