With Utreexo, full nodes can build and verify blocks without storing the UTXO set. This is done by using proofs that the UTXOs in a transaction are included in the Utreexo accumulator. These proofs are broadcast with the transaction. To update the Utreexo accumulator, the only thing required are the UTXOs to be added, and the inclusion proofs of the now-used outputs to be removed.
However, I don’t see anywhere in the paper that describes how unused inclusion proofs are updated in this process. It only mentions that “maintaining and updating proofs of every element in the set incurs no additional computational cost above computing the roots”. I would guess that in the process of adding or deleting leaves, every UTXO who’s proof changes will be touched, and could therefore be easily extracted simultaneously. Does anyone know more in depth how that process would happen?
Also, bonus question: do other kinds of accumulators (eg RSA accumulators) have a way of keeping proofs up to date like this?