Quick (and maybe uninformed) note: one of the bottlenecks on doing fullchain ZKP is the necessity on entire rule set being prooven in each block. If we assume the POW only, maybe just untill few blocks behind the tip, couldn’t we make a light client ZKP based?
In that way, light clients could startup new light clients in seconds, just distributing ZKPs. Those would prove the chain to be valid, to have X size, to be related to Y tip header and to be related to Z utreexo commit.