Why are zk-SNARKs possible, in layman's terms zk-SNARK: Zero-Knowledge Succinct Non-interactive Argument of Knowledge

From the Ethereum blog:


  One natural use case for the technology is in identity systems. For example, suppose that you want to prove to a system that you are (i) a citizen of a given country, and (ii) over 19 years old. Suppose that your government is technologically progressive, and issues cryptographically signed digital passports, which include a person’s name and date of birth as well as a private and public key. You would construct a function which takes a digital passport and a signature signed by the private key in the passport as input, and outputs 1 if both (i) the date of birth is before 1996, (ii) the passport was signed with the government’s public key, and (iii) the signature is correct, and outputs 0 otherwise. You would then make a zero-knowledge proof showing that you have an input that, when passed through this function, returns 1, and sign the proof with another private key that you want to use for your future interactions with this service. The service would verify the proof, and if the proof is correct it would accept messages signed with your private key as valid.


I bolded the parts which seem impossible to me intuitively. I found some research papers with very technical explanations, which I don't understand. Could someone explain why this is possible, in layman's terms? Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.

Some documentation and code
When you have eliminated the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes)


If I find you in my dorm room and the door and windows are intact, I can only conclude that you somehow learned the entry code, because I do not know of any other way by which you could have entered my room without breaking the door or windows.

A ZK-SNARK for a function $f$ is similar: if you present a proof for the result $1$ which can pass the verification procedure, it necessarily means that you must know an $x$ such that $f(x) = 1$. This is because we do not know of any (efficient) way to generate such a proof if you do not know such a value $x$. In fact, we have a proof that being able to do this would imply being able to solve certain mathematical problems which are believed to be hard (you can think of factoring integers, although the problems used to construct SNARKs are more complicated). So when you say


  Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.


... there may or may not be, but we do not know of any and we consider it very unlikely (i.e., impossible, for all practical purposes).