I think fundamentally the issue is you can't create trust out of nothing. Once you have something you trust, you can use cryptography to extend that trust in all sorts of complex ways. However you always need a starting point to bootstrap the system.

I feel like there is a big connection between this problem and trying to prove things in pure logic.

PKI is basically starting from axioms (i trust the following CA's as a starting point)

Tofu is the reflexive property - we know that x=x

Web of trust is some sort of coherence model (in the sense of https://en.m.wikipedia.org/wiki/Coherentism )

I think to make real progress on this problem, we need to make progress in epistomology.