The Shape of the problem
The input is a string of bytes $\{D_1,D_2,D_3,...D_n\}$. This input needs to be chunked.
In the general case, I'll assume there is some hypothetical function chunk_at_index(Data[i-N:i+N]) which can be called to determine if the stream should be cut at index i. Any function that outputs a cut location given a section of the stream can be wrapped to produce this simpler function. This requires that chunking boundaries are stable and determined only by local information.
The general case is impossible
It is impossible to guarantee this in the general case while also ensuring that chunks meet a given (min/max) length criteria or maintain global stability. No such function can guarantee global stability of chunk boundaries after a local edit.
Consider the a string of repeated characters "aaaaaa[...]aaaa"
A function evaluated on a rolling window must either chunk on every byte or leave the entire string intact. No local function can stably decide where to draw chunk boundaries inside the uniform region without considering data outside that region.
Any algorithm that guarantees chunks fall in a certain size range has to be either unstable or use non-local information.
Consider the following string, with a section consisting of repeated 'a' characters. A hypothetical chunking function chunks it up as so. An edit is made and then it is re-chunked.
"Hello " "world!aa" "aaaaa" "aaaaa" "aaaHello " "world!
"Hello " "world!aa" "aaaaa" "aaaaa" "aaaHello " "world!
"Hello " "world!aa" "aaaaa" "aaaaa" "aHello " "world!
A change to the second chunk changes a chunk an arbitrary distance away.
A data compression algorithm could probably be built to pre-process the data in order to fix this. It would need some ability to recursively compress its own output to prevent its own output from having similar repeating patterns.
This illustrates the problem of finding features to use to cut the stream up reliably.
Prolly Trees Don't Have that Issue
Fortunately, Prolly trees are used to store sorted data items, typically key value pairs. Assuming the value is stored by a cryptographic hash reference in the serialized data and that the keys are close enough together, a chunking algorithm will have locally unique features with which to make a yes/no chunking decision for a given window onto the string. If an algorithm can't decide reliably where to make a cut it's the algorithm's fault.
Why a Rolling Hash?
A rolling hash takes a window of bytes in the string and outputs a score representing preference for that location as a chunk boundary.
This is a really powerful concept. The score represents how much the algorithm should want to split the stream at a particular spot. It's only dependent on the data near that index which is why chunk boundaries tend to be stable and re-synchronise.
For non-adversarial data a simple threshold works well to decide where to split but if the adversary can manipulate the scores, we need a better algorithm for choosing boundaries.
Requirements for the Rolling Hash
Any rolling hash will have an output range. If the attacker can completely control the output, they can create pathological score profiles that no function can use for choosing split points. Collisions and exact repetitions are quite problematic as are the integer function output limits. Normally an attacker would have to do 2^N work to set N bits of the function value. For universal hashes or anything else that uses tractable math to make calculating the hash over a rolling window efficient the output can be controlled trivially.
It seems necessary to use a strong hash algorithm for generating scores (essentially applying SHA2 or similar to the hash window). This ensures the attacker has to work harder to get a better score and can't cheat. all that's necessary is to build a splitting function that is computationally infeasible to mess with in the long term. Ideally something that gets quadratically or exponentially harder the longer it hasn't marked a chunk boundary.
Notation
The input is a string of bytes $\{D_1,D_2,D_3,...D_n\}$.
we compute a rolling hash function over this string to compute the score for each cut location. S(i) = SHA2(Data[i-A:i+A]). The scores can be seen as an array of values that can be sliced S[i:j].
The off by one issues here aren't too important. I'm similarly going to ignore issues relating to hash values at the start and end of the string where the hash window isn't full. the hash window size A should be a little larger than the minimum chunk size for reasons that will become clear later.
Localized Beauty Contest
A robust way to enforce a minimum chunk size is to select for values that are the smallest inside some local window. For stream index i we check that the score for that index S[i] is the minimum of the slice S[i-A:i+A] where A is the minimum chunk size. A point wins and becomes a chunk boundary if it is the minimum when it is in the center of the window. This can be done on a rolling window by keeping a sorted heap of values or the ascending minima algorithm. It chunks about once every 2*A bytes.
This doesn't enforce a maximum chunk length. If S[i] would win, the attacker can change some bytes around index i+2A to make S[i+A] lower. They repeat this at index i+A finding a change to make S[i+2A] lower still. When graphed out this looks like a stair step pattern.
The attacker does have to make sure these points aren't too good. Statistically, each time a better point arrives, that lower score will be about half the previous score. This ensures normal data has no very long chunks. If the attacker is naive search time roughly doubles for each step. The attacker can choose not to use values that are too low to make future searches easier though. Increasing compute cost per step slows the rate of difficulty increase proportionally making this attack quite practical.
Finding a "Good Place" to Cut an Evil String
The above algorithm provides a hard guarantee on minimum chunk size. Any change that can make additional cuts can break the minimum chunk size guarantee and usually will. Most things involving math on the score values directly will fail badly.
The attacker can also join sections of evil attack parts together. They just need to find a piece of "glue" that gives hash values in the transition region that meet their attack requirements.
One way to prevent that is with a hash tree. The score S[i], being a cryptographic hash, is a commitment on Data[i-A:i+A]. The hash SHA2(S[i] | S[j]) Changes unpredictably if data is changed in the vicinity of either index i or j.
Supposing we run into a stair-step pattern. Points are spaced too closely together to be used as chunk boundaries. Using the scores directly is difficult but we can make a new set of scores by hashing the points with either their left or right neighbor. The local contest algorithm can be applied to these new scores again to winnow down the list of remaining points. The process is repeated until, points are far enough apart to meet minimum chunk size requirements. Keeping the algorithm from making progress requires the attacker to arrange for values in successive layer to be a stair-step pattern This becomes exponentially harder the more layers are involved.
Let me make this all a bit more clear
Assume the indices $\{j_1,j_2,j_3,...j_n\}$ are the indices of all scores s[j] which were the minimum value for a window S[i-A:i+A] passed over by the first algorithm. These are the points in a stair step profile along with other points that "won" and are now chunk boundaries.
Any chunks that are above the maximum chunk size must be processed further.
Take the indices J[n:m] corresponding to a chunk over the maximum size with J[n] and J[m] being that chunk's boundaries.
Look up the corresponding "interesting" first level scores I_1[k]=S[J[k]] for k=n...m.
We construct $I_2[k]=SHA2(I_1[k],I_1[max(n,k-1)])$ for k=n...m, hashing in the left neighbor to get the next level of score values.
This series of $(J[k],I_2[k])$ (index,score) points is processed by a similar beauty contest algorithm that finds local minimum points. Unless there is a similar stair-step pattern in the I_2 points, some points will be eliminated or will win and become chunk boundaries. This can be repeated for successive levels hashing in left and right neighbors alternately at each level and applying the "beauty contest" algorithm to reduce the number of point and pick winners at each level.
Eventually chunks that are oversized will be cut into non-oversized pieces. This works locally too since we don't need to see the ends of a chunk to know it is oversized. Just seeing a long stretch of string with no chunk boundaries tells us we need to apply another layer.
Each additional layer gets exponentially harder for the attacker to add so there's a limit to the number of layers the chunking algorithm will have to look at. This ensures the function can be evaluated locally, requiring a little less than A*(Max layers+2) bytes of context ever be looked at.
I haven't done any analysis, but I'd guesstimate an attacker won't ever get past 40 layers or so.
I could throw together some python code implementing this if you're still confused.
This is an original algorithm so there might be some vulnerability I'm not seeing.
