CHECKMULTISIGVERIFY with public key hashes? Is it possible to create a script that implements m of n pay to public key hash neatly? One way to do it would be to make use of OP_IF. But, that's not neat.

CHECKMULTISIGVERIFY can implement m of n, however, it takes public keys instead of public key hashes.

Thanks
I think I've figured out how to do it. (Not neatly, though.)

Here's a 3-of-5 pay to multi-pubkeyhash:

scriptSig: &lt;key1&gt; &lt;key2&gt; &lt;key3&gt; &lt;sig1&gt; &lt;sig2&gt; &lt;sig3&gt; &lt;pos1&gt; &lt;pos2&gt; &lt;pos3&gt;
scriptPubKey: &lt;hash1&gt; &lt;hash2&gt; &lt;hash3&gt; &lt;hash4&gt; &lt;hash5&gt;

// key1

// get the key &lt;key1&gt; and hash it
+2 13 OP_PICK OP_DUP OP_HASH160
// copy pos1
+1 9 OP_PICK 
// check 2 &lt; pos1 &lt; 7
+0 OP_DUP 2 7 OP_WITHIN OP_VERIFY
// copy to alt stack
+0 OP_DUP OP_TOALTSTACK
// get hash at pos1
-2 OP_PICK OP_EQUALVERIFY
// check signature
-1 11 OP_PICK OP_SWAP OP_CHECKSIGVERIFY

// key2

// get the key &lt;key2&gt; and hash it
+2 12 OP_PICK OP_DUP OP_HASH160
// copy pos2
+1 8 OP_PICK 
// check 2 &lt; pos2 &lt; 7
+0 OP_DUP 2 7 OP_WITHIN OP_VERIFY
// check pos2 &lt; pos1
+0 OP_DUP OP_FROMALTSTACK OP_LESSTHAN OP_VERIFY
// copy to alt stack
+0 OP_DUP OP_TOALTSTACK
// get hash at pos2
-2 OP_PICK OP_EQUALVERIFY
// check signature
-1 10 OP_PICK OP_SWAP OP_CHECKSIGVERIFY

// key3

// get the key &lt;key3&gt; and hash it
+2 11 OP_PICK OP_DUP OP_HASH160
// copy pos3
+1 7 OP_PICK 
// check 2 &lt; pos2 &lt; 7
+0 OP_DUP 2 7 OP_WITHIN OP_VERIFY
// check pos3 &lt; pos2
+0 OP_DUP OP_FROMALTSTACK OP_LESSTHAN OP_VERIFY
// get hash at pos3
-2 OP_PICK OP_EQUALVERIFY
// check signature
+0 9 OP_PICK OP_SWAP OP_CHECKSIG


(The number at the start of each line is how many stack elements that line adds or removes.)

The idea is that the spender provides the keys, the signatures, and the index of the hash that they're signing for. (keyN, sigN, and posN.) To prevent someone from providing the same index three times, we check that pos1 > pos2 > pos3. It's much longer than an equivalent multisig script, but on the plus side we do fewer signature verifications. (Normal 3-of-5 multisig will do up to 5 signature operations, but we only do 3.)

(Standard disclaimer about using untested scripts applies. If I made an off-by-one error above, all your money's gone.)