Someone correct me if I'm wrong, but isn't there a relatively-easy solution to this?
Store everything in a versioned, secure-hashed repository. Git is too complex, just checksum everything and store it along with the code (this repository is created by the rest of this paragraph). Hand-build a minimal, trivially-human-readable (thus trustable by those who are interested) compiler to compile the first commit. Compile SHA. Get a secure hash of the binary. Store it.
Read the next commit. Verify there is no "compile('bug 1')" in that step. Compile it with v1, and store the hash. Continue.
You now have a chain of trust established, starting with something you can read easily, and building minimally at each step (just read the diffs). And you've got the signature of the trusted compiler at any stage. Now check the signature of the downloaded compiler against your known-trusted signature. Compile, secure in the knowledge you have no infected compiler - an infected one wouldn't match the signature of the compiler you could create from your most-recent trusted result.
This is extendable with digital signatures, the algorithms of which can be understood with a little number theory, and the code shortly thereafter. Choose who you trust, and spread the work out, just like every other trust-based system. Or trust nobody, and do it yourself (edit: yes, this implies you must build your own computer from tools you develop independently).
We've now arrived at the problems around trusting other humans, which are unsolvable. The fact of which must be accepted to varying degrees, or rejected entirely, which requires you to live in isolation. Since you're reading this, you're not in isolation, so you accept some level of human trust, so the previously-established chain of trust would solve the issue for you if the ones you trusted had approved the chain you're using.
In this setup, all you'd need to trust is others who fill the gaps you don't directly approve yourself (note that this includes the security / validity of the hash algorithm). Which is the best you can do without omniscience, which would solve the trust issue on its own anyway.
You are wrong, because you make a huge leap of faith here:
Choose who you trust
No-one deliberately chooses to use software written by people who are known to be untrustworthy! And never has! Yet we find ourselves in a less than perfect world...
>The fact of which must be accepted to varying degrees, or rejected entirely, which requires you to live in isolation.
If you trust nobody in anything, then you cannot live with other humans. If you don't remove yourself, others will remove you, and that's pretty fundamental in any society. So some degree of trust can be assumed to exist, and where it is placed is entirely outside anyone else's control. If there is none in anyone else helping on the computational trust chain, then to have any trustable system you must do it yourself or go without. There is no middle road.
I should also clarify that I'm not claiming we have anything quite like this today. Merely that such a system is possible - the compiler chain is bootstrap-able with minimal effort and determining your measure of trust of any given build is straightforward: if there's a gap in the chain, the answer is no, until someone you trust fills it in. If not, then yes.
edit: in any case, trust, like the communication it is founded on, is an inherently un-decidable problem. At some point, to do anything, some measure of blind trust must exist - for example, my belief that this universe is rational in a way humans can comprehend. Thus, if anything has been done, some trust exists, and the system is bootstrapped.
Store everything in a versioned, secure-hashed repository. Git is too complex, just checksum everything and store it along with the code (this repository is created by the rest of this paragraph). Hand-build a minimal, trivially-human-readable (thus trustable by those who are interested) compiler to compile the first commit. Compile SHA. Get a secure hash of the binary. Store it.
Read the next commit. Verify there is no "compile('bug 1')" in that step. Compile it with v1, and store the hash. Continue.
You now have a chain of trust established, starting with something you can read easily, and building minimally at each step (just read the diffs). And you've got the signature of the trusted compiler at any stage. Now check the signature of the downloaded compiler against your known-trusted signature. Compile, secure in the knowledge you have no infected compiler - an infected one wouldn't match the signature of the compiler you could create from your most-recent trusted result.
This is extendable with digital signatures, the algorithms of which can be understood with a little number theory, and the code shortly thereafter. Choose who you trust, and spread the work out, just like every other trust-based system. Or trust nobody, and do it yourself (edit: yes, this implies you must build your own computer from tools you develop independently).
We've now arrived at the problems around trusting other humans, which are unsolvable. The fact of which must be accepted to varying degrees, or rejected entirely, which requires you to live in isolation. Since you're reading this, you're not in isolation, so you accept some level of human trust, so the previously-established chain of trust would solve the issue for you if the ones you trusted had approved the chain you're using.
In this setup, all you'd need to trust is others who fill the gaps you don't directly approve yourself (note that this includes the security / validity of the hash algorithm). Which is the best you can do without omniscience, which would solve the trust issue on its own anyway.