To secure the output against misuse one could require that the "pre-hash" be included when a transaction is relayed or when a block is published. For Bitcoin the ScriptHash = RIPEMD160(SHA256(script)). So the RIPEMD160 hash would be in the output and the transmitting node would also include the prehash (output of the SHA256 function) with the transaction. Nodes would take the SHA256 "prehash" hash it and verify it matches the output to confirm the output has a valid hash. Once a txn was sufficiently deep in the blockchain to make re-orgs unlikely, nodes could discard the prehash.
When someone independantly invents the same idea, you know it must be at least somewhat good.
(uh, well actually, maybe not.
)
I called this P2SH^2:
http://sourceforge.net/p/bitcoin/mailman/message/30705609/Any other ideas?
Yes, I have a more powerful scheme that doesn't _ever_ distribute the pre-image, it goes as follows:
First some super sloppy background so the rest makes sense to people who don't know it (you can skip if you're familiar with pairing crypto):
A BLS signature is a simple signature scheme for pairing cryptography which uses groups where computational discrete log is believed intractable but the decisional discrete log problem is tractable. BLS signatures have the important property that a signature is _unique_ for a given pubkey,message tuple there is only one signature possible. Pairing crypto works like ECC, but you have an additional operation pairing(point, point) that can be used to solve the decisional discrete log problem.
The construction of a BLS signature is,
G is a generator of the group, I'm writing it additively here.
H(y) is that converts y to a point on the curve such that the discrete log is not known. (e.g. it's some direct bit coercion not y*G)
secret key: x
pubkey: xG
sign: sig = x H(message)
verify: pairing(H(message), pubkey) == pairing(sig, g)
Verification is basically answering the question "Is sig the ECDH value for the pair of points pubkey and H(message)".
Here is how you can use this to suppress the convert channel:
H2 = sha256 or what have you, random collision resistant hash.
secret key: x == data you want to encode
pubkey: xG == assuming the data is the size of the order of the group this is a one way computable bijection, if the data you wanted to encode was a a secure hash, so is the pubkey.
proof: proof = x H(H2(pubkey))
Proof now shows that pubkey is a point you know the discrete log of, hardness of the discrete log in the group shows you can't pick some data embedding pubkey as you wouldn't know the discrete log.
You transmit {pubkey, proof}
You can't do this trick using regular ECDSA/schnorr signatures as far as I can tell because the non-uniqueness allows you to use knowledge of the nonce as a trapdoor.
This reduces your covert channel to only the small bits that you can afford to grind into it with guess and check. If the values already have to meet some computational criteria (e.g. you always have to grind) then any additional grinding is a multiplication on that, so with a linear cost to honest users that exponential cost channel can be made as computationally expensive as you like.
Better: a complete failure of the cryptosystem only reintroduces the covert-channel, it doesn't compromise the security of your P2SH.
Downside: The proof adds another group-element (e.g. 32 bytes for 256 bit security) size amount of data, and the verification takes on the order of 1ms. Hashing (required at spending time) requires a point scalar multiply, which is also slower than a classical hashing function (though much better than a half ms).
It may be possible to construct something similar with RSA signatures; but I haven't tried and the cost of deterministically generating a private key (hashing your message) may be problematic... and obviously the size would be unattractive. I think basically the same can be done with any unique signature scheme where the signature leaks no information about the private key (E.g. doesn't work with a lamport signature, though they're trivially unique).
I'm pretty sure it's impossible.
The impossible presented. I'm glad to be of service.
So you stick your non-transaction data in there as the "prehash".
Yes, but you can verify this prehash only for blocks on the tip, not the history. and forget about it. So I think that fits at least some definitions of "out of the blockchain". (Though as I just demonstrated even that weakness can be closed.)
Anything here works better with a somewhat narrow definition of "out of a blockchain". Even with outputs fixed signatures still end up with a covert channel (though something with very limited functionality could also make it arbitrarily narrow, again using unique signatures), but most of my thought in this space has been centred around eliminating high bandwidth covert channels for data that all participants are strongly forced by the system to store.
There are also other things that can be done here. A utxo is, roughly, txid:vout -> {scriptPubkey, value}. You could instead store H1(txid:vout) -> Enc(H2(txid:vout), {scriptPubkey, value}) to locally blind yourself to this data until the very moment it's needed (when a block shows up that actually spends the output).
