February 7, 2017

Some simple smart contracts to dispel the hype

In the past I’ve said that “smart contracts” are protocols for exchanging crypto-payment for some kind of specialized product or service without the need for trust. But within the Bitcoin-space I still see many examples of things that shouldn’t really be called a smart contract at all.

So here are some examples of some smart contracts that clearly show how payment can be given for some kind of service that has then been intertwined with payments so closely that trust is removed.

I’ll start with the simplest contract I know of and move on to some new contracts that help demonstrate the idea behind universal verifiability in trustless trade protocols. Here is the first contract.

Example 1: Paying for a hash collision #


value1 = get_input()
value2 = get_input()
btc_address = get_input()

# Values need to be different to prove a collision.
if value1 == value2:
    exit()

if sha256(value1) == sha256(value2):
    release_coins_to(btc_address)
else:
    # Not a valid collision so exit.
    exit()

There you have it. Probably the simplest smart contract that I know of. What does it do? Well it asks the user to provide two different values that both produce the same SHA256 hash. Doing this proves that the user has found a hash collision in SHA256 since normally a given value is suppose to map to a different hash (there are still no known collisions in SHA256.)

Why do this? Well, the importance of this service is that you get to learn if there might be underlying problems with the security of SHA256 in Bitcoin. Bitcoin uses double SHA256 for a lot of things so it will be harder to break - but to be prudent, knowing if there are problems is still useful.

So why is this “smart” and how is this “trustless”? First, no person has to manage the money or quality of the service. If this were a legal contract you would say something like “okay, I’ll give you $1000 to find me a SHA256 collision and if I fail to do this I agree to be held liable for damages.” But nothing about that contract physically prevents either side from cheating. So the person could simply refuse to give the money after learning the solution or a fake solution could be given to trick the buyer.

The smart contract above solves those problems by guaranteeing payment and service by using an immutable ledger of events (Bitcoin) and cryptography. Bitcoin already allows for transactions to specify complex conditions for redemption. So you can lock money up with the above conditions and then rely on the security of how PoW consensus works to guarantee that money is always (and only) paid for a solution.

Okay, I lied, maybe its a little more complex

The contract above was invented by Peter Todd but it actually contains an error because of how it was implemented. The original idea was to give anyone the ability to specify the destination if they can provide the solution but this means that the moment you go to claim the reward by broadcasting a transaction - other people also learn the same solution and can double-spend the coins with a higher fee before it gets confirmed.

What is needed to fix this problem is a mutex mechanism. We want to know who exactly was FIRST to find the reward so the right person gets it - and this functionality is exactly what blockchains allow us to do - they provide an ordered, eventually unbreakable record of events. So lets implement our mutex now with some pseudo-code.


value1 = get_input()
value2 = get_input()
btc_address = get_input()
contract_id = get_input()

save_contract_data(contract_id, sha256([value1, value2, btc_address])

This is called a commitment scheme. You’ve masked your solutions and provided a payout address. In a second transaction you can then unmask these values along with your Bitcoin address and the ledger can be used to prove who knew the solution at the earliest possible point in time.

Protip: you would also need to update the original contract so that people must reveal their commitments within a certain time frame to be valid and pay a fine for incorrect solutions (otherwise people can pretend to have the solution and delay the progress of verification.)

Example 2: Gambling. #

Above there were actually four components:

The original contract rules written in a programming language and enforced by the blockchain.
An initial commitment of secret values to satisfy those rules.
The release of the committed secrets and consensus on the immutably ordered results (given as input to the contract program.)
The results of that release.

This exact same idea will work for trustless gambling. Imagine two sides want to bet on the outcome of a coin flip.

Bob flips a coin and records the result as sha256(flip + rand_number).
Bob constructs a contract that says the following (contract_tx):
- If Alice can guess the coin flip she will get the coins but if she doesn’t I will get her coins.
- If I don’t reveal my commitment in a certain amount of time Alice will get all the coins by default (but only if she tries a guess by timeout / 2 (to avoid race conditions).) If Alice fails to guess and the timeout is reached I get any coins still in the contract (mine or mine + hers.)
- To validate Alice’s choice, the first four bytes of her choice are compared to the committed secret (once revealed) which must be either head or tail.
Alice makes a guess (guess_tx.) She doesn’t know what Bob’s coin flip is yet and she cannot brute force the hash because of the incredibly large random_number used to mask the secret.
Bob reveals the committed secret (reveal_tx.) He is forced to reveal this secret based on the contract rules even if he knows he has already lost. If he doesn’t the money is given to Alice anyway.
All parts of the contract have now been satisfied. A clear winner can be decided based on the original rules of the contract.

Here is the contract loosely as pseudo-code:

# Public information saved at the time of contract creation.
alice_btc_address = get_input()
bob_btc_address = get_input()
current_block_no = get_current_block_no()

# The secret part is created by Bob. Only Bob knows the full secret.
flip = random(["head", "tail"])
blinding = random(0 - 79228162514264337593543950336)
secret = flip + blinding
commitment = sha256(secret) # Public.

# Alice_guess and secret will be passed in from different transactions
# from Alice and Bob, respectively. Assume signatures are used.
function contract(alice_guess, secret):
    # The contract can timeout if Bob or Alice don't complete it.
    if get_current_block_no(alice_guess) >= current_block_no + 20:
        # Alice didn't guess the flip so she loses by default.
        if alice_guess == None:
            release_reward(bob_btc_address)

    if get_current_block_no(secret) >= current_block_no + 30:
        # Bob didn't release a valid secret so he loses by default.
        if sha256(secret) != commitment:
            release_reward(alice_btc_address)

    # Make sure to wait for min confirmations!
    # Otherwise betting can be attacked.
    if get_current_block_no(alice_guess) - current_block_no < 6:
        exit()
    if get_current_block_no(secret) - current_block_no < 6:
        exit()

    # Alice hasn't flipped yet.
    if alice_guess == None:
        exit()

    # Bob hasn't released the secret yet.
    if secret == None:
        exit()

    # Bob's secret is incorrect.
    if sha256(secret) != commitment:
        release_reward(alice_btc_address)

    # Alice won the guess.
    if alice_guess == secret[:4]:
        release_reward(alice_btc_address)
    else:
        # Bob tried to cheat.
        if secret[:4] not in ("head", "tail"):
            release_reward(alice_btc_address)
        else:
            # Bob won instead.
            release_reward(bob_btc_address)

Like the example above, this scheme takes place over multiple ordered transactions. First Bob defines a contract with a sealed commitment. Then Alice locks in her choice in another transaction. Then Bob reveals his commitment. Then the contract is finalized and the person who won can satisfy the redeem conditions and can move the locked-in coins for that contract any where they want.

Notice how the contract has a strict set of behavior. You’re looking at exactly what the sides can and cannot do and this structure has been enforced by using a combination of:

Cryptography (commitments and signatures.)
Game theory (disincentives for non-completion.)
Consensus (ordered events to decide on an outcome.)

This is a smart contract. For years we already had 1 and 2 but the introduction of 3 means that we can now start to represent new kinds of relationships in such a way that cheating is no longer an option. This idea is genuinely so ground breaking within trade that very few people understand it even inside the Bitcoin space.

Example 3: Paying for random data compression #

I have introduced two kinds of existing contracts. The first was a contract that paid for a hash collision and the second was a coin flipping / gambling protocol. These are both old contracts but how about something new and a little more interesting? How about paying for someone to produce a universal compressor for random data?

There is a competition that’s been running for 10 years now to create a program that can compress a sequence of random numbers by 1 byte. Just one byte and no one has done it yet (prob its impossible.) At this rate the creator will die before the problem is solved, removing the joy of future generations to waste time on impossible problems and that would be a tragedy. Fortunately though, because this is a mathematical relationship it can easily be represented as a smart contract so that:

Anyone can add to the reward bounty.
Anyone can claim the prize money so long as they can build the compressor …
Without being attacked like in example 1 (since we can use commitments) and …
Without being attacked period (hence “smart” contract.)

All of this can be encoded as a smart contract scheme that can validate the complexity and compression ratios of a solution so that anyone can contribute to the idea of building random data compression algorithms without the nasty business of trusted rewards.

Example 4: Paying for working exploits. #

Here’s another idea for a smart contract - the exploit contract. Imagine that a node can run any computable program in a virtual machine. A contract is then formed that says that if a person can produce an input for the program that can set a certain section of memory to a certain value (or do some kind of privileged action under the process) then coins can be redeemed.

You would use the exact same scheme as with the gambling protocol: commitments. However, you would also need to give the vendor time to patch their software and point the smart contract to the new patched binary otherwise an attacker can modify old exploits to claim future rewards and due to the halting problem it would be basically impossible to detect that an old exploit had been modified to trick the tests.

As I see it, far from this being a novel contract - this would actually solve two pain points for people in the InfoSec world by:

Avoiding submissions from auditors that were beyond the scope of the bounty program (this happens all the time with bug bounty programs - auditors sometimes even attack private network resources) and …
Providing an absolute, irrevocable reward (in the past auditors have been upset to receive only small rewards for their exploits and often no rewards at all.)
Making validation of exploits automatic and having rewards paid out straight away.

A 100% transparent bug bounty program. Btw, you can also still give out the exploits in private to the vendor and let them patch the binary by a given time-frame so you’re suddenly not screwing over all their customers and the blockchain will still allow rewards for users who committed the exploit hash before the binary hash was changed (patched.)

In fact, you can directly specify the patch duration and reward time-frame within the smart contract – and even impose penalties on the vendor for being too slow to patch software (and conversely: this could also discourage early disclosure.) Smart contracts are awesome.

Edit: Or how about patch contracts and rewards for patches? If exploits are verifiable then patches must be too (but that would really only work with software that has good test suites.) Autonomous bug bounties?

Example 5: Paying for software performance increases. #

This is more theoretical than anything but one can imagine using a variation of the idea above to incentivise people to increase the performance of software functions.

So imagine that you have a program that compresses images. You build a contract that says that if a particular operation can be done faster than a given (relative) benchmark then a reward is justified. But one problem you might run into with this is people trying to outsmart tests.

So if say: you have a static test for a compression algorithm that uses a fixed image then people might just make it so that a new version of the software has a hard-coded copy of the output file which it outputs when run with the test.

Again, it’s extremely difficult to detect nefarious changes like this but theoretically there should be certain kinds of software that can use dynamic and comprehensive testing systems that can’t be outsmarted like this so performance contracts might still be a possibility.

Other kinds of smart contracts #

There are many kinds of smart contracts already in existence but generally speaking these contracts are all based on solving a narrowly defined and highly specialized set of problems.

A good rule of thumb is that if all the information within a system can be self-contained it may be possible to turn it into a smart contract - but anything that depends on outside information (like real world events) can’t be represented as a smart contract.

Confusingly: this would mean that most of the stuff being done in Ethereum isn’t actually a smart contract but there is more to it than that. The original idea for smart contracts included the idea of checks and balances which gives us a much broader take on what a smart contract can be.

Consider what happens when you send a package:

You package your item and survey the inventory.
The item is handed to a courier who assesses the package, insures it if necessary, gathers a signature, and hands out a tracking number.
The tracking number is given to the recipient.
The courier delivers the package to the recipient.
The recipient surveys the content and signs for the package.

This scheme segregates the responsibilities of all three parties by using a system of checks and balances. The sender cannot lie to the buyer about sending the package because this is checked by the courier. The courier cannot lie about delivering the package because this is signed by the recipient. And the recipient cannot lie about receiving the package because the courier makes them sign for it.

Triple confirmation. Triple checks and balances. Segregation.

By segregating responsibilities and distributing trust, it is possible to create organizational structures that are far more secure than a trusted equivalent. But let us not discount one basic fact: trust is still a requirement even if it is reduced. So although the idea of being able to consign things like payments to multiple signers in a bullet-proof way is unique to the Bitcoin system the idea of having to trust people is not and I think many people today designing so-called “decentralized” systems forget this.

Check these out #

That’s it for now. If you’re interested in learning more about smart contracts here is a brief list of some schemes that are pretty cool. Some of these are my ideas, some other people:

Atomic cross-chain contracts.
Lightning channels.
Atomic cloud storage contracts (and to a lesser extent: pay for private key transactions.)
Namecoin.
Convenants
Datachains
Zero-knowledge contingent payments
Zero-knowledge atomic swaps
Decentralized lotteries
DoScoin (technically not trustless but very interesting.)

And … wait for it: Bitcoin itself is actually a smart contract since it creates an immutable ledger that trustlessly rewards coins for solving hash puzzles in exchange for helping to order events within that ledger (which can then serve as the foundation for other kinds of smart contracts.)

And they say Bitcoin is over-hyped … We’ve barely scratched the surface.

Tl; Dr: Smart contracts let you trade crypto-money for certain specialized products and services in a way where being scammed is magically impossible. This idea was mostly impossible before blockchains because bullet-proof, ordered events didn’t exist yet.

Kudos