Trustless Bitcoin bounty for SHA1, SHA256, etc. collisions

http://sourceforge.net/p/bitcoin/mailman/message/31397880/

by nullc • 13 years ago

17 5 13 years ago

nullc3• 13 years ago

Many people aren't aware of it but the backend Bitcoin system has no concept of "addresses". Instead when you make a transaction it specifies small bits of forth-like program code (https://en.bitcoin.it/wiki/Script) that provides rules that redeemer of the coins must satisfy to spend the coins.

The normal 1xxx addresses are just template for a ECDSA checking script. There are also 3xxx addresses where the address is a hash of an arbitrary script, and the redeemer provides the script and satisfies it.

This can enable powerful applications like "trustless escrows" with no mediator trusted to hold the coins, or bindings to external zero knoweldge proof systems (https://en.bitcoin.it/wiki/User:Gmaxwell/why_hash_locked).

In the posting linked here the author has paid funds to be redeemed by someone who can provide collisions for a non-linear (SHA1, RIPEMD160, SHA256, RIPEMD160(SHA256()), SHA256(SHA256()), and ABS() are the respective bounties)

Anyone who has Bitcoin can add to these bounties by simply sending funds to the respective 3xxx address which is a hash of the rules that check for a collision for the given function. The Bitcoin system itself arbitrates the rules, so there is no other party that must be trusted to pay or whom could withdraw the bounty after you begin your effort.

The SHA1 bounty has address 37k7toV1Nv4DfmQbmZ8KuZDQCYK9x5KpzP (https://blockchain.info/address/37k7toV1Nv4DfmQbmZ8KuZDQCYK9...)

A disassembly of its script is:

    OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL

Or, in English: Duplicate the last two elements on the stack ([A] [B] -> [A] [B] [A] [B]), then compare if the top two elements are equal and push the result, if they're not equal remove the result and continue processing, then compute the SHA1 of the top element on the stack ([A] [B] -> [A] [sha1(B)]), then swap the top two elements ([sha1(B)] [A]), then compute the SHA1 of the top element ([sha1(B)] [sha1(A)]), and compare the result. If the final state is true the script passes and the spend is permitted.

blake8086• 13 years ago

Does this mean you can create a script to reward finding the preimage of an arbitrary sha hash?

nullc3• 13 years ago

Yes, or _disclosing_ one (see the 'Why hash locked' link for example of how that can be used to bootstrap more powerful protocols).

iSnow• 13 years ago

Thanks for the explanation, I am still trying to wrap my head around how bitcoin really works. This is so freaking incredible.

nullc3• 13 years ago

No problem, a lot of the "block explorer sites" give a very highly cooked view and really obfuscates the underlying behavior (e.g. makes transactions look like they have a from address, translates scripts into addresses and don't let you see them directly, or doesn't show output indexes, etc).

There really isn't a good low level viewer out there other than the Bitcoin-qt debug console or the bitcoind rpc.

Trustless Bitcoin bounty for SHA1, SHA256, etc. collisions

Related Stories