[Cryptography] Is it mathematically provably impossible to construct a mechanism to test for back doors in programs?

[ianG]

Talking about proof of work and so forth, seen on the net:


==================
In Bitcoin, such a fork is useless, since you’re just increasing the
amount of time you would need to catch up. In blockchain-based proof of
work, however, it is a serious problem. The reason is that if you start
a fork straight from the genesis block, then while your mining will be
slow at first, after a few hundred blocks you will be able to fill the
blockchain up with contracts that are very easy for you to mine, but
difficult for everyone else. One example of such a contract is simply:

i = 0
while sha3(i) !=
0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f:
    i = i + 1

You know that the contract will take exactly one million rounds before
the hash matches up, so you can calculate exactly how many steps and how
much gas it will take to run and what the state will be at the end
immediately, but other people will have no choice but to actually run
through the code. An important property of such a scheme, a necessary
consequence of the halting problem, is that *it is actually impossible*
(as in, mathematically provably impossible, not Hollywood impossible)
*to construct a mechanism for detecting such clever contracts in the
general case without actually running them*. Hence, the
long-range-attacker could fill the blockchain with such contracts,
“mine” them, and convince the network that it is doing a massive amount
of work when it is actually just taking the shortcut. Thus, after a few
days, our attacker will be “mining” billions of times faster than the
main chain, and thereby quickly overtake it.
====================
http://blog.ethereum.org/2014/05/15/long-range-attacks-the-serious-problem-with-adaptive-proof-of-work/



The bit half-way through second para.  It seems to be an interesting
property;  can someone work through the logic of it for me?

I'm specifically wondering whether we are limiting this case to all
backdoors, backdoors of the nature of a public-private key pair, or
something in between.

E.g., if it is impossible to detect any backdoor, why do we favour open
source, which might provide a neat mechanism to insert undetectable back
doors?  Just to be controversial...



iang