Here's an overview of a strong [1], append-only accumulator with your desired properties. This accumulator was originally introduced by Reyzin and Yakoubov in [3]:
- Supports provable batch additions.
- Is publicly updatable.
- The information to update all witnesses is sublinear in the number of elements added.
I'll describe this scheme by example, since formalization would be tedious and is not likely to enlighten.
First, take a look at the figure below.
It consists of a forest of Merkle trees. There's an old accumulator $F_7$ (orange nodes) and a new accumulator $F_{18}$ (orange & green nodes), which "includes" $F_7$. In fact, there's an append-only proof of this consisting of the filled-in nodes (e.g., nodes 000, 0010, 00110, 00111, 01, 1000).
The prover stores all the leafs and the internal nodes (which include root nodes), while the verifier stores a digest of size $O(\log{n})$ consisting of all the root nodes, where $n$ is the number of accumulated elements.
For example, if you look at just $F_7$ (i.e., ignore all the green stuff), its digest $d_7$ consists of $\{h_{000}, h_{0010}, h_{00110}\}$ where $h_w$ denotes the hash of node $w$. Similarly, the digest $d_{18}$ of $F_{18}$ consists of $\{h_0, h_{1000}\}$.
Key ideas
The scheme is just a small tweak to Crosby and Wallach's history tree [2].
Adding elements
To add an element to the accumulator, the prover appends a leaf to the forest and merges nodes only when necessary so that all tree sizes are a power of two.
I think it's best to try out an example on paper to see when you would merge nodes to maintain this invariant. Formally, let $w = v|b$ denote a node with prefix $v$ concatenated with $b\in\{0,1\}$ and let $v|\bar{b}$ denote its sibling, where $\bar{b} = 1-b$. The idea is to only merge nodes that are siblings (i.e., we only merge $v|0$ with $v|1$ only if they are both in the forest).
For example, node 1000 has no (right) sibling so it cannot be merged with anything. In contrast, node 01 and node 00 are siblings so they were merged, resulting in a parent node 0. This process can continue recursively. For example, consider what happened when node 00111 was added: the first merge of 00111 with 00110 triggered two other merges, eventually creating node 00.
Membership proofs
The proof for an element $x$ being in a digest $d$ is just a Merkle path from $x$ to one of the roots in $d$. For example, the image below shows proofs for two different elements $x$ and $y$ w.r.t. digest $d = h_0$. The proof for $x$ consists of the filled-in nodes (i.e., $\pi_x = \{h_{00000}, h_{0001}, h_{001}, h_{01}\}$), while the proof for $y$ consists of the bold-circled nodes (i.e., $\pi_y = \{h_{00101},h_{0011}, h_{000}, h_{01}\}$). (It so happened that the proofs share a common node $h_{01}$ which I highlighted differently.)
Append-only proofs
If you look again at the overview picture, the append-only proof between $F_7$ and $F_{18}$ consists of "deduplicated" Merkle sibling paths (i.e., the filled-in nodes from the figure) from the old roots of $F_7$ to the new roots in $F_{18}$. Specifically, the nodes with $\times$ on them are "deduplicated": they are computed by hashing up the filled-in nodes.
The proof also consists of extra roots like $h_{1000}$ (also filled-in in the figure). This proof is very similar to the append-only proof in history trees [2] (except it's called a consistency proof in that paper).
Importantly, the size of an append-only proof between $d_m$ and $d_n, m<n$ is $O(\log{n})$.
Updating membership proofs (after an append-only proof)
After a batch addition in the old accumulator with digest $d$, the verifier receives an append-only proof from the prover and ensures nothing has been maliciously removed from $d$ or modified. As you indicated in your question, the verifier has some old membership proofs w.r.t. the old digest $d$ that he wants updated so they can verify w.r.t. the new digest $d'$.
First, note that the old membership proofs are sibling paths to the old root.s
Second, note that append-only proof between $d$ and $d'$ are sibling paths from the old roots to the new roots.
Third, recall that the append-only proof is $O(\log{n})$-sized, where $n$ is the size of the new accumulator.
By now, you might notice that one can easily "compose" the old membership proofs with the append-only proof to obtain new membership proofs w.r.t. the new digest $d'$. This necessarily involves linear computation in the number of old membership proofs, since the verifier needs to update them all. However, the bandwidth required to update the old membership proofs is sublinear since it's just the $O(\log{n})$-sized append-only proof.
For example, the old proof for $y$ w.r.t. to $d$ was $\pi_y = \{h_{00101}\}$ and the new proof is $\pi_y' = \{h_{00101},h_{0011},h_{000}, h_{01}\}$. Note that the verifier needs to compute $h_{0011}$ from its two children: an old root from $F_7$ and the 8th leaf in $F_18$. The verifier can easily do that because it has all the necessary information: the 8th leaf is part of the append-only proof.
In general, one can argue this will work for any element $x$ in any digest $d$ with updated digest $d'$. Again, the intuition is that the append-only proof consists of "deduplicated" Merkle sibling paths from old roots to new roots (e.g., no point in including $h_{0011}$ because it can be recomputed from its children which are included).
Conclusion
A strong, publicly-updatable accumulator with "batch addition" that can update old membership proofs with sublinear bandwidth exists. A slight tweak to Crosby and Wallach's elegant history tree [2] construction gives exactly that.
Hope this make sense and helps!
References
[1] "Strong Accumulators from Collision-Resistant Hashing", by Philippe Camacho, Alejandro Hevia, Marcos Kiwi, and Roberto Opazo
[2] "Efficient Data Structures for Tamper-Evident Logging", by Scott A. Crosby, and Dan S. Wallach
[3] "Efficient Asynchronous Accumulators for Distributed PKI", Leonid Reyzin, and Sophia Yakoubov
