The Michelson Language

A contract a day

Below, you'll find the contracts from my contract-a-day series. These contracts were all written directly in Michelson. They're going to be short and hopefully descriptive. I've also included some information about how to run these contracts and do my best to keep them updated as the Michelson language changes.

If you have any requests, questions, or want to contribute, feel free to contact me. I'm on the Tezos Riot chat at milodavis. I'm also reachable by email.

The contracts are below the explanation on how to develop Michelson on the alphanet. Feel free to skip past it.

Many of the easier contracts appeared early in the sequence. If you're new to Michelson, the bottom of the list is likely more helpful.

Contracts are easier to write and read if you have good tooling. There's an Emacs mode available in the Tezos repository which, though a work in progress, is a big help. The installation instructions can be found here. You can also try Michelson online.

Running on the alphanet

Here's how to run a contract on the alphanet. The container: prefix tells the docker to copy the file into the container before running the client. It does change the path, so just know that it's still your file that's causing the errors.

Typechecking contract on the alphanet

./alphanet.sh client typecheck program container:/tmp/program.tz

Run a contract on an input

Replace [STORAGE] with a value of the storage type and [INPUT] with a value of the parameter type.

./alphanet.sh client run program container:/tmp/program.tz on storage [STORAGE] and input [INPUT]

Typecheck a piece of data

Same as above. Just replace [DATA_LITERAL] and [TYPE] with the piece of data and expected type.

./alphanet.sh client typecheck data [DATA_LITERAL] against type [TYPE]

Originate a contract on the alphanet

This will push the contract live to the blockchain.

By default, the alphanet has the identity my_identity installed. It also has the account my_account available as a source of funds (with a decent starting balance).

./alphanet.sh client originate contract [CONTRACT_NAME] for [IDENTITY] transferring [STARTING_BALANCE] from [SOURCE_OF_FUNDS] running container:[PATH_TO_PROGRAM]

Here's a full example:

./alphanet.sh client originate contract program for my_identity transferring 100 from my_account running container:/tmp/program.tz

Data Literals

Here are some examples of data literals. There are current issues with the parsing of negative integers on the command line. This problem will be fixed shortly. The outer quotes are necessary when passing on the command line.

Type Data
unit Unit
nat 12312321
int 12312321
int '(-12223)'
string '"hello"'
string "\"hello\""
bool True
bool False
timestamp 10000
timestamp '"2017-08-14T18:00:21Z"'
tez '"100.00"'
signature '"96c724f3eab3da9eb0002caa5456aef9a7c716e6d6d20c07f3b3659369e7dcf5b66a5a8c33dac317fba6174217140b919493acd063c3800b825890a557c39e0a"'
(lambda unit unit) {}
(lambda string string) {PUSH string "hello"; CONCAT}
key '"tz1faswCTDciRzE4oJ9jn2Vm2dvjeyA9fUzU"'
(contract unit unit) '"tz1faswCTDciRzE4oJ9jn2Vm2dvjeyA9fUzU"'
(map nat bool) '(Map (Item 100 False) (Item 90 True))'
(set nat) '(Set 1 2 3 4')'
(list int) '(List 1 -123 12312)'
(option bool) (Some False)
(option bool) None
(or nat bool) '(Left 100)'
(or nat bool) '(Right False)'

August 24, 2017: Map to fold

Firstly, this is the final contract in my contract-a-day series. I'm going to take a break, and then I'll be back with new, and different, posts about the Michelson language. There'll be more tutorials, ideas, and patterns. I'm also excited to be able to talk about some of the great new features coming to the language. For everyone who's been reading this blog, thank you for sticking with me through all of these contracts, useful, and ridiculous.

For this contract, I'm going to reimplement something that's in the language, MAP. You are almost certainly wondering why I would want to do this. The reason is because I've become extremely interested in how recursive procedures will look when compiled down to Michelson. In the general case, you can use a loop and a list to simulate the stack. If you are operating on a list, set, or map, you may be able to use the REDUCE instruction to simplify things.

parameter (pair (lambda int int) (list int));
return (list int);
storage unit;
code { DIP{NIL int};
       CAR;
       DUP;
       DIP{CAR; PAIR};          # Unpack data and setup accumulator
       CDR;
       LAMBDA (pair int (pair (lambda int int) (list int)))
              (pair (lambda int int) (list int))
              # Apply the lambda and add the new element to the list
              { DUP; CDAR;
                DIP{ DUP; DIP{CDAR}; DUP;
                     CAR; DIP{CDDR; SWAP}; EXEC; CONS};
                PAIR};
       REDUCE; CDR; DIP{NIL int}; # First reduce
       LAMBDA (pair int (list int))
              (list int)
              {DUP; CAR; DIP{CDR}; CONS};
       REDUCE;                  # Correct list order
       UNIT; SWAP; PAIR}        # Calling convention

August 23, 2017: Sorting a list

Today, we're going to sort a list. For simplicity, I'm using insertion sort. This was one of the harder contracts I've written and it took me a few tries to get the data marshalling in the second case right.

Here's the insertion function written in OCaml:

let rec insert n = function
  | [] -> [n]
  | hd :: tl ->
      if hd > n
      then n :: hd :: tl
      else hd :: (insert n tl)

Unfortunately, in Michelson, we can't just push a call frame onto the stack. We need to manually do things. I'm essentially using the zipper datastructure, which I've implemented previously. The zipper acts just like my call stack in the OCaml version. I save the first part of the list off, before adding it reversing it back onto the other list once I find the correct location.

parameter (list int);
return (list int);
storage unit;
code { CAR;                     # Access list
       # Insert procedure
       LAMBDA (pair int (list int))
              (list int)
              { DUP; CDR; DIP{CAR}; # Unpack accumulator and existing list
                DIIP{NIL int}; PUSH bool True; # Setup loop
                LOOP { IF_CONS { SWAP;
                                 DIP{DUP; DIIP{DUP}; DIP{CMPLT}; SWAP}; # Duplicate numbers
                                 SWAP;
                                 # If less than
                                 IF { DIP{SWAP; DIP{CONS}}; PUSH bool True}
                                    # Otherwise
                                    { SWAP; CONS; PUSH bool False}}
                               # Ending case
                               { NIL int; PUSH bool False}};
                SWAP; CONS; SWAP; # Finish lists
                LAMBDA (pair int (list int))
                       (list int)
                       {DUP; CAR; DIP{CDR}; CONS};
                REDUCE};
       NIL int; SWAP; DIP{SWAP}; # Accumulator for reverse onto
       REDUCE;                  # Execute reverse onto
       UNIT; SWAP; PAIR}        # Calling convention

August 22, 2017: A list of transactions

Disclaimer: this contract can be attacked. Do not use the code in production unless you are aware of the risks you introduce. This is a contract that transfers a list of people currency. This contract can be prevented from making later transactions if a malicious contract uses up all of the available gas. Unless you hand pick all of the contracts, don't trust that they won't be manipulated in this way.

Currently, the TRANSFER_TOKENS instruction is forbidden inside of lambdas. This is an issue that is being fixed, but for now, we need to use a loop. The loop iterates through each element of the list and makes the transfer. The annotated contract is below:

parameter unit;
storage (list (contract unit unit));
return unit;
code { CDR; PUSH bool True;     # Setup loop
       LOOP {IF_CONS { PUSH tez "1.00"; UNIT; TRANSFER_TOKENS; # Make transfer
                       DROP; PUSH bool True}                   # Setup for next round of loop
                     { NIL (contract unit unit); PUSH bool False}}; # Data to satisfy types and end loop
       UNIT; PAIR};                                                 # Calling convention

August 21, 2017: Append two lists

Michelson has a minimal standard library, so we're missing some operations that might come in handy. One such operation is appending two lists. Unfortunately, the standard recursive list reverse is out of the question. Let's look at that procedure in OCaml:

let rec append l1 l2 =
  match l1 with
  | [] -> l2
  | hd :: tl -> hd :: (append tl l2)

This looks straightforward: we cons the first element of the list onto the result of appending the tail and the second list. However, this hides an important detail: the stack. The list is effectively reversed onto the stack before the CONS instructions are executed. Michelson doesn't have such a facility, so we have to simulate one by transforming our recursive procedure into an iterative one. Let's look at that in OCaml:

let rec reverse l acc =
  match l with
  | [] -> acc
  | hd :: tl -> reverse tl (hd :: acc)

let append l1 l2 =
  reverse (reverse l1 []) l2

This is completely tail recursive, meaning that we can simulate it with a tail recursive reduce, or an iterative loop. This gets us the following Michelson code:

parameter (pair (list int) (list int));
return (list int);
storage unit;
code { CAR; DUP; DIP{CDR}; CAR; # Unpack lists
       NIL int; SWAP;           # Setup reverse accumulator
       LAMBDA (pair int (list int))
              (list int)
              {DUP; CAR; DIP{CDR}; CONS};
       REDUCE;                  # Reverse list
       LAMBDA (pair int (list int))
              (list int)
              {DUP; CAR; DIP{CDR}; CONS};
       REDUCE;                  # Append reversed list
       UNIT; SWAP; PAIR}        # Calling convention

August 20, 2017: More Set Operations

Michelson has set data structures, but there are some missing operations. Fortunately, we can implement these ourselves. Today, I'm going to provide contracts that implement two of these operations, set union and subset. The first takes two sets and returns their union. The second takes two sets and returns True if the first is a subset of the second. Here are the two contracts:

Union

parameter (pair (set string) (set string));
return (set string);
storage unit;
code { CAR;                     # Get the parameter
       DUP; CAR; DIP{CDR};      # Unpack the sets
       LAMBDA (pair string (set string)) # Lambda for reduce
              (set string)
              { DUP;
                CAR;
                DIP{CDR};       # Unpack accumulator and string
                PUSH bool True;
                SWAP;
                UPDATE};        # Add it to the set
       REDUCE;                  # Execute reduce
       UNIT; SWAP; PAIR}        # Calling convention

Subset

parameter (pair (set string) (set string));
return bool;
storage unit;
code { CAR; DUP; CDR; DIP{CAR}; # Unpack lists
       PUSH bool True;
       PAIR; SWAP;              # Setup accumulator
       LAMBDA (pair string (pair bool (set string)))
              (pair bool (set string))
              { DUP;            # Unpack accumulator and input
                CAR;
                DIP{ CDR; DUP; DUP; CDR;
                     DIP{CAR; DIP{CDR}}};
                MEM;            # Check membership
                AND;            # Combine accumulator and input
                PAIR};
       REDUCE;                  # Reduce
       CAR;                     # Get the accumulator value
       UNIT; SWAP; PAIR}        # Calling convention

August 19, 2017: Intro to Conditionals

Most, if not all interesting contracts rely on some sort of conditional. Today, I've devised a contract to introduce you to three different conditionals in Michelson. Those three conditionals are IF, IF_NONE, and IF_LEFT. Each operates on a different type. The first is the classic if that takes the first branch if the boolean on top of the stack is True and the second if it is False. The other two statements are more like pattern matches.

IF_NONE takes the first branch if the value on top of the stack is the value None and the second if it is (Some value). The value is placed on top of the stack in the second branch. Both branches must still return the same type.

IF_LEFT gives you the left value of the type in the first branch and the right value of the type in the second branch. You can use an or type to differentiate between values of the same type as well, which is a good idea if you need to represent that.

I'm also going to take a minute to talk about the FAIL instruction. Use it when you reach a state in your contract that should not happen or that cannot be recovered. A nice pattern to avoid nesting too deeply in conditionals is to fail in one of the branches, leaving the second empty. If your inputs are not valid, bail out. It's far better to stop and not be available than to be insecure.

So, to the contract. This contract is nonsense. It can receive different values

  • (Left string) - Return the string
  • (Right (option int)) - Fail if None or negative and return the empty string otherwise
parameter (or string (option int));
storage unit;
return string;
code { CAR;                      # Access the storage
       IF_LEFT {}                # The string is on top of the stack, nothing to do
               { IF_NONE { FAIL}  # Fail if None
                         { PUSH int 0; CMPGT; # Check for negative number
                           IF {FAIL}          # Fail if negative
                              {PUSH string ""}}}; # Push the empty string
       UNIT; SWAP; PAIR}                          # Calling convention

August 18, 2017: Stack Manipulations

This contract is meant to introduce the basic stack manipulations in Michelson. Here's what they are:

  • DUP - Copy the item on top of the stack, giving you two items
  • DROP - Throw away the item on top of the stack
  • SWAP - Exchange the places of the stack's top two items
  • PUSH type [value] - Put a [value] (which is of type type) on top of the stack

Here are two examples, designed to focus on stack manipulation:

This contract adds a given value to a list twice:

parameter nat;
storage (list nat);
return unit;
code { DUP;                     # Duplicate the storage and parameter
       CAR;                     # Extract the parameter
       DIP{CDR};                # Extract the storage
       DUP;                     # Duplicate the parameter
       DIP{CONS};               # Add the first instance of the parameter to the list
       CONS;                    # Add the second instance of the parameter to the list
       PUSH unit Unit;          # Put the value Unit on the stack (calling convention)
       PAIR}                    # Finish the calling convention

This contract demonstrates a use for swaps two elements:

parameter (or (pair string bool) (pair bool string));
storage unit;
return (pair bool string);
code { CAR;                     # Access the parameter
       IF_LEFT { DUP;           # Duplicate so we can access both elements
                 CAR;           # Get the first element
                 SWAP;          # Swap the two elements to get the correct order
                 CDR}           # Access the second element
               { DUP;           # Duplicate so we can access both elements
                 CAR;           # Get the first element
                 DIP{CDR}};     # Get the second element
       PAIR;                    # Calling convention:
       PUSH unit Unit;
       SWAP;
       PAIR}

This contract gets the first element of a list:

parameter (list bool);
return (option bool);
storage unit;
code { CAR;                     # Access the parameter
       IF_CONS { SOME;          # Make the option type
                 SWAP;          # Expose the tail of the list
                 DROP}          # Drop it because we don't need it
               {NONE bool};     # Push None (no first element)
       PUSH unit Unit;          # Calling convention:
       SWAP;
       PAIR}

August 17, 2017: More introductory contracts

I've been getting messages asking how to get started with Michelson. Today, I'm going to write a few different contracts that I hope will help introduce the language. These contracts are meant to show the basic mechanics of Michelson.

The first contract is meant to show the calling convention. Contracts take a pair, consisting of the parameter and the storage value. They must end with a pair consisting of the return value and the new storage value. If you wish to omit any of these values, set the type to be unit.

This contract is going to store a new value in the storage and return the previous storage value. To accomplish this, the storage, parameter, and return types must all be the same. I've chosen to make them all strings, though any type would work here.

parameter string;
return string;
storage string;                 # Note that all three values are of the same type
code { DUP; # In order to access both the storage and parameter, I need to duplicate the (pair parameter storage)
       CAR; # Access the parameter
       SWAP;            # Exchange top and second element on the stack
       CDR;             # Get the storage in the pair
       PAIR};           # Generate pair of elements

I run this contract with the following command line, which runs the contract as if the storage value is '"hello"':

tezos-client run program contracts/swap_storage_input.tz on storage '"hello"' and input '"world"'

Lets look at each instruction in that contract and what they do:

  • DUP - Duplicate the value on top of the stack
  • CAR - Access the first element of the pair on top of the stack. This replaces the pair, so if you need to access other elements, you must explicitly duplicate it.
  • SWAP - Exchange the top two values on the stack.
  • CDR - Access the second element of the pair on top of the stack. This replaces the pair, so if you need to access other elements, you must explicitly duplicate it.
  • PAIR - Make a pair from the top two elements on the stack.

Here is the same contract as the one above, written with DIP. The DIP instruction allows you to work on elements that are not the top of the stack. A good way of thinking about DIP is as if you save the top element of the stack and run a series of commands. After you finish the DIP, you push the top element back onto the top of whatever the stack looks like after the dip finishes.

parameter string;
storage string;
return string;
code { DUP;                     # Duplicate the (pair parameter storage)
       CDR;                     # Access the storage
       DIP{CAR};                # Access the parameter, but leave the storage unchanged on top of the stack
       PAIR}                    # Pair the elements, fulfilling the calling convention

Here's another example that gets the minimum of two numbers. This is meant to show how the IF instruction works.

parameter (pair int int);
return int;
storage unit;
code { CAR;                     # Ignore the storage
       DUP;                     # Duplicate so we can get both the numbers passed as parameters
       DUP;                     # Second dup so we can access the lesser number
       CAR; DIP{CDR};           # Unpack the numbers on top of the stack
       CMPLT;                   # Compare the two numbers, placing a boolean on top of the stack
       IF {CAR} {CDR};          # Access the first number if the boolean was true
       UNIT;                    # Push storage value
       SWAP;                    # Correct order for calling convention pair
       PAIR}                    # Pair the numbers satisfying the calling convention

In Michelson, there are two types of operations: those that operate on the stack, moving or duplicating elements, and those that operate on the top element or elements of the stack. When applying operations that operate on elements, you can think of a sequence as composition. For example, the operations ABS; NEG should be seen as applying an absolute value and then negating the result. The following example in C or Java would correspond neg(abs(x)).

The stack is the most intimidating part of Michelson. When I write complicated contracts that involve a lot of moving operations around, I sometimes use a piece of paper to write down the desired stack state. I also make heavy use of the Michelson emacs mode. Tooling helps tame the stack, but nothing has helped me more than experience. At this point, I've written a decent amount of Michelson. Write something super simple. Get a feel for how to write contracts and then build on that knowledge and experience to larger and more complicated contracts.

August 16, 2017: Auction

Today I'm going to write a contract for an auction. The mechanics are simple: anyone can provide any amount of funds. After the timestamp, the contract stops accepting new transactions and the winner is the person with the highest bid. The item is distributed off chain. I allow people to increase the bid by any amount, as an exercise, change this. Bids are pseudonymous. This helps purchasers of coveted items, like a bathrobe monogrammed with the Tezos logo (Please, please, please make this happen, Arthur), can avoid unwanted celebrity. Signing a message with the winning key allows for the item to be delivered only to the correct person.

parameter key_hash;
storage (pair timestamp (pair tez key_hash));
return unit;
code { DUP; CDAR; DUP; NOW; CMPGT; IF {FAIL} {}; SWAP; # Check if auction has ended
       DUP; CAR; DIP{CDDR}; AMOUNT; PAIR; SWAP; DIP{SWAP; PAIR}; # Setup replacement storage
       DUP; CAR; AMOUNT; CMPLE; IF {FAIL} {};  # Check to make sure that the new amount is greater
       DUP; CAR;                               # Get amount of refund
       DIP{CDR; DEFAULT_ACCOUNT}; UNIT; TRANSFER_TOKENS; # Make refund
       PAIR}                                             # Calling convention

August 15, 2017: Bitwise XOR/Find the non-duplicated number

Here's a fun puzzle: given a list of numbers, all of which appear an even number of times except for one, find the number that appears an odd number of times. The list is guaranteed to be non-empty. The trick is to reduce the list, combining the numbers using XOR. The advantage of XOR is that when you XOR a number with another twice, you get back the other number. This means that 300 XOR 41231 XOR 300 is 41231. So, all we have to do is apply the REDUCE operation to each pair of numbers. Here's the contract:

parameter (list nat);
return nat;
storage unit;
code { CAR; IF_CONS {} {FAIL};  # Check for empty list (not permitted)
       SWAP;
       LAMBDA (pair nat nat)
              nat
              { DUP; CAR; DIP{CDR}; XOR}; # XOR the numbers together
       REDUCE;                            # Reduce the list
       UNIT; SWAP; PAIR}                  # Calling convention

August 14, 2017: Zipper

One of my all-time favorite data structures is the Zipper. The Zipper, provides a purely functional way to move have a pointer into a data structure and simulate moving in any direction in constant time. This is often accomplished via a double-linked imperative data structure and a pointer, however functional languages discourage this sort of thing. The Zipper works by creating a context with a hole. The original paper is a good read, but here's the gist of the version for lists:

  • You pair the original list with an empty one
  • To move left, you pop an element from the first list and push it onto the second
  • To move right, you pop an element from the second list and push it onto the first
  • Elements are added to the first list at the current location
  • Element are returned from the head of the first list

Here's a Michelson implementation:

parameter string;
return string;
storage (pair (list string) (list string));
code { DUP; CAR; DIP{CDR; DUP; CAR; DIP{CDR}};      # Unpack storage and lists
       DUP;
       PUSH string "GET";
       CMPEQ;                   # Check for "GET
       IF { DROP;               # Ignore "GET"
            IF_CONS {} {FAIL}}  # Return first element or fail if first list is empty
          { DUP; PUSH string "LEFT"; CMPEQ; # Check against "LEFT"
            IF { DROP; IF_CONS {SWAP; DIP{CONS}} {FAIL}} # Move element from first list to second
               { DUP; PUSH string "RIGHT"; CMPEQ;        # Check against "RIGHT"
                 IF { DROP; DIP{ IF_CONS {} {FAIL}}; SWAP; CONS } # Move element from second list to first
                    { CONS }};                                    # Add element to first list
            PUSH string ""};                                      # Give back empty return
       DIP{PAIR}; PAIR}                                           # Calling convention

There is an unfortunate problem with this contract: it sometimes returns nonsense data. This is because there are illegal states that are still representable. Even more unfortunately, there is no way to fix this problem within Michelson. For example, an option type might be a better indicator than an empty string, but I can still return a value when inserting or moving the position in the list. I can also return no value when "GET" is called, though this would potentially allow me to avoid calling the FAIL instruction. There are plans to fix this problem, but they are still being worked out and have not yet been implemented.

August 13, 2017: Nat to String

Unfortunately, Michelson doesn't currently contain a way of converting a number to a string. Fortunately, we can write one. I'm using the dispatch pattern from yesterday. It simplifies things reducing the number of cases from 10 to 1. I could also make this contract cheaper to execute by keeping the map in storage, however that makes the command lines annoyingly long.

parameter nat;
storage unit;
return string;
code { CAR;
       # Dispatch pattern for converting digits to strings
       EMPTY_MAP nat string;
       PUSH string "0"; SOME; PUSH nat 0; UPDATE;
       PUSH string "1"; SOME; PUSH nat 1; UPDATE;
       PUSH string "2"; SOME; PUSH nat 2; UPDATE;
       PUSH string "3"; SOME; PUSH nat 3; UPDATE;
       PUSH string "4"; SOME; PUSH nat 4; UPDATE;
       PUSH string "5"; SOME; PUSH nat 5; UPDATE;
       PUSH string "6"; SOME; PUSH nat 6; UPDATE;
       PUSH string "7"; SOME; PUSH nat 7; UPDATE;
       PUSH string "8"; SOME; PUSH nat 8; UPDATE;
       PUSH string "9"; SOME; PUSH nat 9; UPDATE;
       SWAP; DUP; PUSH nat 0; CMPEQ; # Handle the case of 0
       IF {PUSH string "0"} {PUSH string ""}; SWAP;
       PUSH bool True;          # Do while loop (it's just easier)
       LOOP { DUP; PUSH nat 0; CMPEQ;
              IF { PUSH bool False}   # Halt condition
                 { PUSH nat 10; SWAP; EDIV; # Execute division
                   IF_NONE {FAIL} {}; # Impossible -- we explicitly divide by 10
                   DUP; CAR;
                   # Add digit to string
                   DIP{ CDR; SWAP;
                        DIP{ DIP{DUP}; GET;
                             IF_NONE {FAIL} {}};
                        SWAP; CONCAT}; PUSH bool True}};
       # Cleanup and calling convention
       DROP; DIP{DROP; UNIT}; PAIR}

August 12, 2017: The Dispatch Pattern

Today, I'm writing a contract that you should not rely on. It's not exactly insecure, but anyone can add to its code. This contract is about the pattern it implements. The dispatch pattern uses message passing as a succinct way of performing case analysis. This contract allows users to provide either a string, or a pair of a string and a lambda. If the contract is given a string, it calls the in the map that corresponds to the value in the map. If the string is not in the map, we fail. Otherwise, we call the lambda and return its result. Why is this pattern useful? It reduces complexity if you have a large number of complicated cases. You can also add cases as you implement more functionality which avoids writing a bunch of FAIL instructions just so you can run the case you're working on.

parameter (or string (pair string (lambda unit string)));
return string;
storage (map string (lambda unit string));
code { DUP; DIP{CDR}; CAR;      # Unpack stack
       IF_LEFT { DIP{DUP}; GET; # Get lambda if it exists
                 IF_NONE {FAIL} {}; # Fail if it doesn't
                 UNIT; EXEC }        # Execute the lambda
               { DUP; CAR; DIP {CDR; SOME}; UPDATE; PUSH string ""}; # Update the storage
       PAIR}                                              # Calling convention

Because it is non-obvious, the concrete syntax for a lambda is {INSTRUCTION ...}. The identity lambda is written {}.

August 11, 2017: Maximum in list

Today's contract finds the maximum number in a list. Here it is:

parameter (list nat);
storage unit;
return (option nat);
code { CAR;                     # Get the list
     IF_CONS                  # If the list contains an element
       { SWAP;                # Setup our reduce invariant
         LAMBDA (pair nat nat)
                nat
                { DUP; DUP; CAR; DIP{CDR};
                  CMPGT; IF {CAR} {CDR}}; # Find the maximum number
         REDUCE;                          # Reduce the list
         SOME}                            # Return the value
       { NONE nat};                       # No values in list, return none
     UNIT; SWAP; PAIR};                   # Calling convention

August 10, 2017: Payouts based on the Data Publisher

Hey folks, remember the data publisher contract from July 29th? I'm going to do something with it. Today, I'm going to write a contract that uses data publisher to decide which of two contracts to pay on a predefined date. Tomorrow, I'm going to implement the same contract using the parameterized payouts contract from August 4th (rewritten to store integers) and then I'm going to compare the two implementations to see which I like better. I think it'll be interesting to see what differs and help evaluate whether parameterized contracts are a good design pattern for Michelson.

The integer version of the data publisher contract is as follows:

# NONE if user wants to get the value
# SOME (signed hash of the string, string)
parameter (option (pair signature (pair int nat)));
return int;
storage (pair (pair key nat) int);
code { DUP; CAR; DIP{CDR; DUP};
       IF_NONE { AMOUNT; PUSH tez "1.00"; # The fee I'm charging for queries
                 CMPLE; IF {} {FAIL};
                 CDR; PAIR}
               { SWAP; DIP{DUP}; CAAR; DIP{DUP; CAR; DIP{CDR; H}; PAIR};
                 CHECK_SIGNATURE; ASSERT; DUP; CDDR; DIIP{DUP; CADR};
                 DIP{SWAP}; ASSERT_CMPEQ;
                 CDR; DUP; DIP{CAR; DIP{CAAR}}; CDR; PUSH nat 1; ADD;
                 DIP{SWAP}; SWAP; PAIR; PAIR; PUSH string ""; PAIR}}

The contract that allows users to speculate on the value will take two contracts from unit to unit and an integer value. It will also store the publisher and the timestamp at which the payout will be made and the amount of the payout.

parameter unit;
storage (option
           (pair (pair (contract unit unit) (contract unit unit))
                 (pair (pair timestamp (contract (option (pair signature int)) int))
                       (pair tez int))));
return unit;
code { CDR; IF_NONE {FAIL} {}; # Check if settlement has already ocurred
       DUP; CDAAR; NOW; CMPLT; IF {FAIL} {}; # Check the timestamp
       DUP; CDADR; DIP{SOME}; PUSH tez "1.01"; NONE (pair signature int);
       TRANSFER_TOKENS; DIP{IF_NONE{FAIL} {}};
       DIP{DUP; CDDR; DUP; CDR}; CMPGT;
       SWAP;
       DIP{ IF {CAAR} {CADR};
            DIP{ NONE (pair (pair (contract unit unit) (contract unit unit))
                            (pair (pair timestamp (contract (option (pair signature int)) int))
                                  (pair tez int)))}};
       CAR; UNIT; TRANSFER_TOKENS; PAIR}

August 9, 2017: Generate N identity contracts

Have you ever wanted to generate a huge number of identity contracts? Yeah, me too! So, how to write one? It's actually relatively simple. We just need to loop and create a contract each time.

parameter nat;
return unit;
storage (list (contract string string));
code { DUP;
       CAR;                     # Get the number
       DIP{CDR};                # Put the accumulator on the stack
       PUSH bool True;          # Push true so we have a do while loop
       LOOP { DUP; PUSH nat 0; CMPEQ; # Check if the number is 0
              IF { PUSH bool False}   # End the loop
                 { PUSH nat 1; SWAP; SUB; ABS; # Subtract 1. The ABS is to make it back into a nat
                   UNIT;                       # Storage type
                   LAMBDA (pair string unit)   # Identity contract
                          (pair string unit)
                          {};
                   PUSH tez "5.00"; # Strating balance
                   PUSH bool False; DUP; # Not spendable or delegatable
                   NONE key_hash;
                   # This is once again my key from the alphanet.
                   # I highly encourage you to send funds to it
                   # Will it help you? Will it help me? The answer is no,
                   # However, do it anyway
                   PUSH key_hash "tz1cxcwwnzENRdhe2Kb8ZdTrdNy4bFNyScx5";
                   CREATE_CONTRACT; # Make the contract
                   SWAP;            # Add to the list
                   DIP{CONS};
                   PUSH bool True}}; # Continue the loop
       DROP; UNIT; PAIR}             # Calling convention

August 8, 2017: Logical implication

I'm going to try to start mixing in more straightforward contracts so that people who are just starting out can get a feel for Michelson. This one takes a pair of booleans and returns the logical implication.

parameter (pair bool bool);
return bool;
storage unit;
code { CAR; DUP; CAR; DIP{CDR}; # Unpack data
       NOT; OR;                 # Logical implies
       UNIT; SWAP; PAIR}        # Calling convention

August 7, 2017: A Parameterized vesting schedule

I'll return to the proxy contract in a day or so. For now, I'm going to implement as simpler contract that provides access to a number of coins, but only after a certain date. This contract relies on a few properties of the parameterizable payments contract to prevent the same transaction from being approved multiple times. Think about what they are. If you have a solution and wish to check it, feel free to contact me.

The entire state of this contract is perminetly set when the contract is created. The transactions in the parameterizable payments contract are also fixed upon creation, making it impossible for a quick sequence of messages from an attacker to register their transactions with the specified sequence numbers. Here's the annotated contract.

parameter nat;
return (pair nat bool);
storage (map nat timestamp);
code {DUP; CAR; DUP; DIIP{CDR; DUP}; # Unpack and duplicate the parameter and storage
      DIP{GET; IF_NONE{FAIL} {};     # Find the timestamp at which the transaction may be executed (if any)
          NOW; CMPGT};               # Check if the time has been reached
      PAIR; PAIR}                    # Cleanup and exit

August 6, 2017: Multisig

I'm now going to present a multisig contract to you. This contract allows users two users to approve a contract if and only if they both agree to the transfer. So, how do we implement this? The two individuals who hold the stored keys can submit a signed hash of an integer. If the hash validates, they have approved the transaction. For simplicity, users cannot reject a transaction. A transaction that is never approved is never executed, so it's not a huge issue to leave it partially approved. This mirrors the behavior of the parameterizable payments contract. Luckily, we don't need to modify the contract from yesterday to achieve this behavior. It's types are usable. So, what are our cases:

  • The contract receives (Left nat) - and the pair of booleans we store with that transaction to see if it is approved
  • The contract receives (Right (pair signature nat))
    • If the signature checks against the first key, put true in the first slot for that contract
    • If the signature does not check against the first key, check with the second key
      • If that signature checks, put true in the slot of the second contract
      • Otherwise, fail

As you can see, this specification creates a general structure for the conditional expressions in our contract. Below you'll find the annotated contract:

storage (pair (map nat (pair bool bool)) (pair key key));
return bool;
parameter (or nat (pair signature nat));
code { DUP; CAR; DIP{CDR};       # Stack rangling
       IF_LEFT { DIP{DUP; CAR}; GET; # Get the value stored for that index
                 IF_NONE { PUSH bool False} # If not referenced, reject
                         { DUP; CAR; DIP{CDR}; AND};
                 PAIR}
               { DUP; CAR; DIP{CDR; DUP; H}; PAIR; SWAP; # Create the signature pair
                 DIP{ DIP{DUP; CDR; DIP{CAR}; DUP};
                      SWAP; CAR; DIP{DUP}; CHECK_SIGNATURE }; # Check the first signature
                 SWAP;
                 # If the signature typechecked, get and update the first element of the pair
                 IF { DIP{DROP; SWAP; DUP}; DUP;
                      DIP{ GET; IF_NONE{PUSH (pair bool bool) (Pair False False)} {};
                           CDR; PUSH bool True; PAIR; SOME }}
                    # Check the second signature
                    { DIP{DIP{DUP; CDR}; SWAP; CHECK_SIGNATURE}; SWAP;
                      IF { DUP; DIP{DIP{SWAP; DUP}; GET}; SWAP;
                           IF_NONE {PUSH (pair bool bool) (Pair False False)} {};
                           CAR; PUSH bool True; SWAP; PAIR; SOME; SWAP}
                         {FAIL}};
                 # Update the stored value and finish off
                 UPDATE; PAIR; PUSH bool False; PAIR}}

Note: If users use the same key for multiple instances of these contracts, they become vulnerable to replay attacks. This could be fixed with a global, monitonically increasing counter stored for the entire blockchain.

August 5, 2017: A proxy for parameterization

Today's contract builds on yesterday's parameterized payments contract. Using the code from yesterday, we can implement simple strategies that are self contained. For example, you could configure things so that the contract could only make payments after a certain date, but thereafter approved all transactions:

parameter nat;
storage timestamp;
return (pair nat bool);
code {DUP; CAR; DIP{CDR; DUP; NOW; CMPGT}; PAIR; PAIR};

Of course, this is boring. I promised multisig, voting, and vesting schedules. I want to do better, but doing better requires multiple entry points or polymorphism. Essentially, I'd like a way to say that ∀ α, (contract (or nat α) bool), meaning that you can call one of the entrypoints of the contract to check if a transaction has been approved and another one to change the state of the contract. The polymorphism is used to allow our parameterizable contract to work. You can also do the same thing with multiple entrypoints. If you can mix in structural subtyping along with multiple entrypoints, this gets even cooler, but I digress.

The present state of things requires us to use a proxy contract. The proxy will have the type that the contract from yesterday expects, but it will make requests to a third contract that actually implements our strategy using the Left part of an or type. External users can change the third contract's internal state using the Right constructor as a second entrypoint. I'm going to write a version of this proxy contract tonight and build the interesting strategies I'm sure you're looking forward to over the next few days.

The basic structure of this contract is as follows: the contract is either passed Left nat or Right α. We have to fix α, but it's easy to change: you only have to rewrite two types.

Yesterday, I opted to have the contract that is queried return the natural number it is authorizing. In this one, I didn't. Which is the better design? I think this one is, but it also leads to a state where you can represent something in storage that is not always meaningful. This is a disadvantage of how Michelson prevents reentrancy attacks.

Here's the contract:

parameter nat;
storage (pair (option nat) (contract (or nat (pair signature nat)) bool));
return (pair nat bool);
code {DUP; CAR; DIP{CDDR; DUP}; DUP; DIP{SOME; PAIR; SWAP}; # Store the nat in strorage
      # Query our stored contract
      LEFT (pair signature nat); DIP{PUSH tez "0.00"}; TRANSFER_TOKENS;
      # Cleanup and finish
      DIP{DUP; CAR}; DIP{IF_NONE {FAIL} {}}; SWAP;
      PAIR; DIP{CDR; NONE nat; PAIR}; PAIR}

Exercise: Change this contract so that the contract it queries takes a boolean instead of (pair signature nat). Which locations need to be changed?

August 4, 2017: A parameterizable payments contract

Today we're going to explore a parameterizable contract for making payments. Depending on how this contract is initialized, this can implement a multisig contract, a vesting schedule, or a trap that never or always pays out. I'm going to write all of these over the next few days, starting with the last one.

So what's the basic idea:

  • One contract stores a map of transactions, stored according to an index
  • Another contract is passed an index and either approves or rejects it
  • If the contract is approved, it executes it
parameter (or (pair string (pair tez (contract unit unit))) nat);
return unit;
storage (pair (contract nat (pair nat bool)) (pair nat (map nat (pair string (pair tez (contract unit unit))))));
code { DUP; DIP{CDR}; CAR;      # Get the input while preserving the output
       IF_LEFT { DIP{ DUP; CAR; SWAP; CDR; DUP; CAR; DIP{CDR}};
                 SOME; SWAP; DUP; DIP{UPDATE}; # Add the element to the map
                 PUSH nat 1; ADD; PAIR; SWAP;  # Add 1 to the index
                 PAIR; UNIT; PAIR}             # Cleanup and finish
               # Check our other contract to see if the transaction is allowed
               { DIP{DUP; CAR}; PUSH tez "0.00"; SWAP; TRANSFER_TOKENS;
                 # Arrange the stack
                 DUP; CDR;
                 IF { CAR; DUP; DIIP{DUP; CDDR; DUP};
                      DIP{ GET; # Get the value of the data
                           IF_NONE {FAIL} {}; # This should not happen
                           SWAP;
                           NONE (pair string (pair tez (contract unit unit)))};
                      UPDATE; # Delete the element
                      SWAP;
                      # More stack arranging
                      DIP{ SWAP; DUP; CAR; DIP{CDR}};
                      DIP{DIP{CAR; PAIR}; PAIR};
                      DUP; CDAR;
                      DIP{CDDR}; UNIT; TRANSFER_TOKENS; # Make the transfer
                      PAIR}
                    { FAIL }}}

Here's a simple contract that always allows a transaction. I wrote it to test the contract to make sure it works.

parameter nat;
return (pair nat bool);
storage unit;
code { CAR; PUSH bool True; SWAP;
       PAIR; UNIT; SWAP; PAIR}

So what's good about this contract? It's easy to extend. In fact, the next few days will be examples of how to do this. The downside is that it's partially insecure. There is potential for security vulnerabilities from the other contract returning bad data, but as you choose this contract, the security issues are limited.

August 3, 2017: Lambda, Map, and Creating Contracts

Today, I'm going to demonstrate how to use lambda and a higher order function. This function adds 1 to ever number in a list.

parameter (list int);
storage unit;
return (list int);
code { CAR;                      # Get the parameter
       LAMBDA int int { PUSH int 1; ADD }; # Create a lambda that adds 1
       MAP;                              # Map over the list
       UNIT;                             # Push Unit
       SWAP;                             # Reorder the stack for the PAIR
       PAIR }                             # Match the calling convetion

Okay, that contract wasn't too interesting, but we can leverage it to create one that is. This contract will create a new version of the previous contract every time it receives a transaction.

parameter unit;
return (contract (list int) (list int));
storage unit;
code { CAR;                      # Get the UNIT value (starting storage for contract)
       LAMBDA (pair (list int) unit) # Start of stack for contract (see above)
              (pair (list int) unit) # End of stack for contract (see above)
              # See the contract above. I copied and pasted
              { CAR;
                LAMBDA int int {PUSH int 1; ADD};
                MAP;
                UNIT;
                SWAP;
                PAIR };
       AMOUNT;                   # Push the starting balance
       PUSH bool False;          # Not spendable
       DUP;                      # Or delegatable
       NONE key_hash;                 # No delegate
       PUSH key_hash "tz1cxcwwnzENRdhe2Kb8ZdTrdNy4bFNyScx5";
       CREATE_CONTRACT;          # Create the contract
       UNIT;                     # Ending calling convention stuff
       SWAP;
       PAIR}

Bam. You can now spawn as many add1list contracts as you want. I proudly present "unhelpful contract as a service".

August 2, 2017: Lock contract

Today we're going to write a contract that locks up funds until a timestamp is reached. Once that timestamp is reached, it transfers the amount of funds to a the contract it has stored. Note, this contract needs to a transfer to execute, but anyone can trigger it by transferring 0 Tez, plus the fee for the baker after the deadline is reached. Once again I've annotated each line.

parameter unit;
storage (pair timestamp (pair tez (contract unit unit)));
return unit;
code { CDR;                      # Ignore the parameter
       DUP;                      # Duplicate the storage
       CAR;                      # Get the timestamp
       NOW;                      # Push the current timestamp
       CMPLT;                    # Compare to the current time
       IF {FAIL} {};             # Fail if it is too soon
       DUP;                      # Duplicate the storage value
       # this must be on the bottom of the stack for us to call transfer tokens
       CDR;                      # Ignore the timestamp, focussing in on the tranfser data
       DUP;                      # Duplicate the transfer information
       CAR;                      # Get the amount of the transfer on top of the stack
       DIP{CDR};                 # Put the contract underneath it
       UNIT;                     # Put the contract's argument type on top of the stack
       TRANSFER_TOKENS;          # Make the transfer
       PAIR}                     # Pair up to meet the calling convention

The prevous example was a reasonable contract. Here is a bad example. Do not write this second contract. It is attackable. You have been warned.

Before I explain what's wrong with this contract, see if you can figure out what's going on. It's very closely related to the previous contract with seemingly minor differences. The answer is after the code, which I haven't annotated.

parameter unit;
storage (pair timestamp (pair (contract unit unit) (contract unit unit)));
return unit;
code { CDR; DUP; CAR; NOW; CMPLT; IF {FAIL} {};
       DUP; CDAR; PUSH tez "100"; UNIT; TRANSFER_TOKENS; DROP;
       DUP; CDDR; PUSH tez "100"; UNIT; TRANSFER_TOKENS; PAIR }

This contract is just like the other one, but it makes a transfer to two contracts. I've also hard coded in the amount they receive. The problem with this contract is that it's possible to deny the second person their money. The first person won't get it either, but they can use up all available gas, preventing the contract from ever finishing. So here's the lesson: never make a transfer to an unknown contract when more operations rely on that transfer going through. In the first example, the only person who doesn't get paid is the owner of the contract to which you're trying to make thetransfer. In the second, another person is denied the funds that they would otherwise receive.

To prevent this attack, I recommend making all withdrawls via default accounts, which cannot run code and are safe, or based around a pull model, in which users request a withdrawl. The second approach is still vulnerable to reentrancy bugs. Be extremely careful when writing contracts like these.

As a challenge, can you write a contract that will make the second transfer impossible? I've provided one below as well.

parameter unit;
storage unit;
return unit;
code { DROP; PUSH bool True; LOOP {PUSH bool True}; UNIT; UNIT; PAIR }

August 1, 2017: Some simpler examples

I've realized that most of the contracts so far have been either empty, like the identity contract, or more complicated like several of the others. Though I do enjoy the challenge of writing them, I'm going to provide two contracts today that are much simpler. They are meant to show the basic ways to manipulate data with the stack and how the calling convention works.

Here's a contract that adds one to the input. The comments go through what each instruction does and why it's needed.

parameter int;
storage unit;
return int;
code {CAR;                      # Get the parameter
      PUSH int 1;               # We're adding 1, so we need to put 1 on the stack
      ADD;                      # Add the two numbers
      UNIT;                     # We need to put the storage value on the stack
      SWAP;                     # The values must be rearranged to match the return calling convention
      PAIR}                     # Create the end value

As an exercise, how could you replace the SWAP in that contract with a DIP sequence?

Here's another contract. This one returns a string concatenated with one that is stored in the storage. Once again, I'm going to provide an explanation of each instruction.

parameter string;
storage string;
return string;
code {DUP;                      # We're going to need both the storage and parameter
      CAR;                      # Get the parameter
      DIP{CDR;                  # Get the storage value
          DUP};                 # We need to replace it in the storage, so we dup it
      SWAP;                     # Get the order we want (this is optional)
      CONCAT;                   # Concatenate the strings
      PAIR}                     # Pair them up, matching the calling convention

July 31, 2017: King of Tez

Come listen fair Tezosians (yes, I'm taking a position on what the citizens of the Tezos commonwealth should be called), Tezos is transitioning to a hereditary monarchy. Okay, not in the protocol layer, but in the contracts layer. Okay, not in the contracts layer either, just in a single contract. Also, it's not hereditary and the monarch has no power, but like Ethereum and their King of Ether Contract, we can allow a King of Tez to be chosen.

Whoever transfers the most to the contract, becomes the King of Tez, with their key immortalized in the blockchain. My contract is meant to mirror the Ethereum version, with the difference that their contribution limits have been removed. After two weeks, any amount of funds makes you the King of Tez for at least the next two weeks. If someone transfers a greater amount of Tez to the contract in that time, they become the king of Tez, but you receive the funds they put in.

Here's the annotated contract:

parameter key_hash;
storage (pair timestamp (pair tez key_hash));
return unit;
code { DUP; CDAR;
       # If the time is more than 2 weeks, any amount makes you king
       NOW; CMPGT;
       # User becomes king of tez
       IF { CAR; AMOUNT; PAIR; NOW; PUSH int 604800; ADD; PAIR }
          # Check balance to see if user has paid enough to become the new king
          { DUP; CDDAR; AMOUNT; CMPLT;
            IF { FAIL }             # user has not paid out
               { CAR; DUP;
                 # New storage
                 DIP{ AMOUNT; PAIR; NOW; PUSH int 604800; ADD; PAIR };
                 # Pay funds to old king
                 DEFAULT_ACCOUNT; AMOUNT; UNIT; TRANSFER_TOKENS; DROP }};
       # Cleanup
       UNIT; PAIR };

July 30, 2017: A simple system of accounts

Today's contract implements a simple way to have multiple users have accounts. This contract could be the basis of a more complicated contract that stores data and balances. This contract just stores balances, but it could be adapted to do something cooler.

The contract has two ways to operate: one to make deposits and one to make withdrawls. We're going to differentiate the two ways of entering the contract via an or type. The Left constructor is used to add to an account, adding to an existing one if it exists. The Right constructor is used for making a withdrawl. To authenticate a user, they submit a signature along with the amount they wish to withdraw. The amount in the account is also checked.

Here's the annotated contract:

# This is a very simple accounts system.
# (Left key) initializes or deposits into an account
# (Right key (pair tez (signed tez))) withdraws tez amount to a
# DEFAULT_ACCOUNT created from the key if the balance is available
# and the key is correctly signed
parameter (or key_hash (pair key (pair tez signature)));
# Maps the key to the balance they have stored
storage (map key_hash tez);
return unit;
code { DUP; CAR;
       # Deposit into account
       IF_LEFT { DUP; DIIP{ CDR; DUP };
                 DIP{ SWAP }; GET;
                 # Create the account
                 IF_NONE { DIP{ AMOUNT; SOME }; UPDATE; UNIT; PAIR }
                         # Add to an existing account
                         { AMOUNT; ADD; SOME; SWAP; UPDATE; UNIT; PAIR }}
               # Withdrawl
               { DUP; DUP; DUP; DUP;
                 # Check signature on data
                 CAR; DIIP{ CDAR; H }; DIP{ CDDR; PAIR }; CHECK_SIGNATURE;
                 IF {} { FAIL };
                 # Get user account information
                 DIIP{ CDR; DUP }; CAR; HASH_KEY; DIP{ SWAP }; GET;
                 # Account does not exist
                 IF_NONE { FAIL }
                         # Account exists
                         { DUP; DIIP{ DUP; CDAR; DUP };
                           # Ensure funds are available
                           DIP{ CMPLT }; SWAP;
                           IF { FAIL }
                              { SUB; DIP{ DUP; DIP{ SWAP }}; DUP;
                                # Delete account if balance is 0
                                PUSH tez "0.00"; CMPEQ;
                                IF { DROP; NONE tez }
                                   # Otherwise update storage with new balance
                                   { SOME };
                                SWAP; CAR; HASH_KEY; UPDATE;
                                SWAP; DUP; CDAR;
                                # Execute the transfer
                                DIP{ CAR; HASH_KEY; DEFAULT_ACCOUNT }; UNIT; TRANSFER_TOKENS;
                                PAIR }}}}

Important Note: This contract is vulnerable to replay attacks. I've ignored this vulnerability because users can only move funds to the contract and back to themselves. If you are implementing accounts that give users the ability to withdraw funds to another address, add an index for each user. The user should instead sign a pair, consisting of the integer and tez amount. The integer should be incremented after every transaction. If you do not do this, an attacker can replay a signed transaction an unlimited number of times.

July 29, 2017: A Data Publisher

It would be nice to have trustworthy people be able to publish data that the rest of us could use in our own contracts. Currently, I don't produce any data worth sharing, but other people often do. Today, I'm going to show a simple contract that allows someone to publish data securly and charge a fee for accessing it.

When a data publisher wishes to start sharing data, they publish a public key and announce the data that they will be publishing to a given contract. They sign each updated piece of data as they publish it. The signature is checked to ensure that no one else can write to the contract. Queries can be made at a price (1 tez in my example). Users aren't paying for the information, which they could obtain by looking at the contract's storage, they are paying for the trusted supplier. The data supplier provides honest data and, in return, is payed a sum on every transfer for it.

Writing contracts with multiple branches is difficult. The best way I've found to do it is to plan ahead by listing all the possible states your contract can reach. In this one, they nest as follows:

  • Data is requested
  • Data update
    • Key is authentic
    • Key is not authentic

From there, I can more easily track what data I need in each case. In the first, I can ignore the key completely. In the second, I need to verify the data. If the data is signed correctly, I replace the stored data and return the empty string. I could return an option type from the contract, however that would make for a more complicated API for querier. Furthermore, this return type cannot enforce the property that the return value depends on the input. For this guarantee, I would need dependent types, which Michelson does not have.

I also need a counter to prevent replay attacks on the contract. If I don't have this counter, malicous individuals can call the contract with a previously signed update message, which means that they can reset the value to an old one.

# NONE if user wants to get the value
# SOME (signed hash of the string, string)
parameter (option (pair signature (pair string nat)));
return string;
storage (pair (pair key nat) string);
code { DUP; CAR; DIP{CDR; DUP};
       IF_NONE { AMOUNT; PUSH tez "1.00"; # The fee I'm charging for queries
                 CMPLE; IF {} {FAIL};
                 CDR; PAIR}
               { SWAP; DIP{DUP}; CAAR; DIP{DUP; CAR; DIP{CDR; H}; PAIR};
                 CHECK_SIGNATURE; ASSERT; DUP; CDDR; DIIP{DUP; CADR};
                 DIP{SWAP}; ASSERT_CMPEQ;
                 CDR; DUP; DIP{CAR; DIP{CAAR}}; CDR; PUSH nat 1; ADD;
                 DIP{SWAP}; SWAP; PAIR; PAIR; PUSH string ""; PAIR}}

Note: this contract can be adapted to publish any kind of data by replacing the type string in the parameter and return declarations.

July 28, 2017: A Safe Queue

Today I'm going to write a queue. Stop, do not tune out. This is actually a cool one. We need to build a queue that works in Michelson and is not vulnerable to a bad amortized worst case. This is a problem because the usual functional queue will not work. As a general rule, never write operations that are Ω(n) if n is a value that users can increase. For example, if users can add to a list, and your contract performs a linear time operation on that list, your contract can be completely disabled if users can add enough elements to it.

This contract is a safe queue. When I first thought about building a queue in Michelson, I thought about the traditional functional queue. The issue with this approach is the worst-case running time. For those not familiar with it, the basic functional queue consists of a pair of singly-linked lists (like the list type in Michelson). When a new element is added, it is added to the second list. When an element is needed and the first list is not empty, the top element is returned. If the first list is empty, the second list is reversed and becomes the new first list, with the second list being replaced with the empty list. This queue operates in amortized-constant time, but has a linear-time worst case. This creates a way to attack a contract by submitting values until the reverse operation cannot be completed with the available gas. Depending on your contract, this attack might be prohibitively expensive, but it is better not to take any chances.

The map-based queue I'm using is similarly straightforward. When the contract starts, both the numbers in storage are initialized to zero. When someone adds an element, it is added to the map with the key set to the second number. The second number is then incremented. When a number is removed, the first number is incremented and the value is removed from the map. As long as both numbers start at the same number things will always stay in sync.

Here's a simple example of the state of the queue if the stored values were strings:

Operation Numbers Map Returns
Initial (0, 0) (Map ) -
Add "hello" (0, 1) (Map (Item 0 "hello")) -
Add "world" (0, 2) (Map (Item 0 "hello") (Item 0 "world")) -
Pop (1, 2) (Map (Item 0 "world")) "hello"
Pop (2, 2) (Map ) "world"

This contract will create a queue of strings, just like the above example. This contract has two possible paths through the code: one in which a user adds to the queue, and another in which the user requests the first element. If a caller requests the first element when the queue is empty, it will return None. When a user adds an element to the queue, the contract will also return None. This value can be ignored.

parameter (option string);
storage (pair (pair nat nat) (map nat string));
return (option string);
code { DUP; CAR;
       # Retrieving an element
       IF_NONE { CDR; DUP; CAR; DIP{CDR; DUP}; DUP;
                 CAR; SWAP; DIP{GET}; # Check if an element is available
                 SWAP;
                 # Put NONE on stack and finish
                 IF_NONE { NONE string; DIP{PAIR}; PAIR}
                         # Reoption the element and remove the entry from the map
                         { SOME;
                           DIP{ DUP; DIP{ CAR; DIP{ NONE string }; UPDATE };
                                # Increment the counter and cleanup
                                DUP; CAR; PUSH nat 1; ADD; DIP{ CDR }; PAIR; PAIR};
                           PAIR }}
               # Arrange the stack
               { DIP{DUP; CDAR; DIP{CDDR}; DUP}; SWAP; CAR;
                 # Add the element to the map
                 DIP{ SOME; SWAP; CDR; DUP; DIP{UPDATE};
                      # Increment the second number
                      PUSH nat 1; ADD};
                 # Cleanup and finish
                 PAIR; PAIR; NONE string; PAIR }}

Here's how to originate the contract, using some of the data from the test/test-utils.sh script:

tezos-client originate contract queue for ${KEY1} transferring 100 from bootstrap1 \
       running queue.tz \ # Replace this with the path to the contract on your system
       -init '(Pair (Pair 0 0) (Map))'

And here's how to add an element to it:

tezos-client transfer 0.00 from bootstrap1 to queue -arg '(Some "hello")'

Finally, here's how you get the first element from it:

tezos-client transfer 0.00 from bootstrap1 to queue -arg 'None'

July 27, 2017: Reverse

Here's a contract that takes a list of strings and reverses it. This contract gets into the list instructions and the LOOP instruction.

parameter (list string);
return (list string);
storage unit;
code { CAR; NIL string; SWAP; PUSH bool True; # Set up loop
       LOOP { IF_CONS {SWAP; DIP{CONS}; PUSH bool True} # Cons onto accumulator if non-empty
                      {NIL string; PUSH bool False}};   # Handle empty list
       DROP; UNIT; SWAP; PAIR}

The trick to writing contracts with loops is to keep your loop invariant in mind. Don't think about what changes on each cycle through the loop, think about what stays the same. I've also boxed up my termination behavior inside of my loop instead of doing a check and putting a boolean on top of the stack initially. To me, this seems like a better pattern. This contract is a little awkward because I push an extra NIL onto the stack before the loop ends. I do this only to make the types work out. It's less than ideal, but I can't think of a good way to avoid it.

Exercise: What is my loop invariant? What needs to be on the stack at the end of each cycle? How to I make sure that this is the case?

Previously, it was necessary to use a loop to reverse a contract due to a bug within the Michelson implementation, however now it's fully possible to reverse a list using REDUCE. That contract is as follows:

parameter (list string);
storage unit;
return (list string);
code { CAR; NIL string; SWAP;   # Setup
       LAMBDA (pair string (list string))
              (list string)
              {DUP; CAR; DIP{CDR}; CONS}; # Cons onto list
       REDUCE; UNIT; SWAP; PAIR};         # Perform reverse and clean up

July 26, 2017: At least

I'm very important, so when people send me money, they always send me a lot. Just in case any plebians want to waste my time with small dollar contributions to my greatness, I'm going to reject those transactions.

parameter unit;
return unit;
storage tez;                    # How much you have to send me
code {CDR; DUP;                 # Get the amount required (once for comparison, once to save back in storage)
      AMOUNT; CMPLT;            # Check to make sure no one is wasting my time
      IF {FAIL} {UNIT; PAIR}}   # Finish the transaction or reject the person

The useful part of this contract is the following sequence structure:

PUSH tez "[MINIMUM_TRANSACTION]"; AMOUNT; CMPLT; IF {FAIL} {};

This sequence ensures that a transaction is greater than the specified minimum transaction. This is helpful for any contract that enforces a fee.

Tip: use the -amount flag to test contracts that require a minimum balance. The following command line will allow you to test this contract.

tezos-client run program contracts/at_least.tz on storage '"100.00"' and input Unit -amount '99.00' # Should Fail
tezos-client run program contracts/at_least.tz on storage '"100.00"' and input Unit -amount '100.00' # Should succeed

July 25, 2017: Take my money

Here's a more interesting contract. It sends money to anyone who asks for it. Why would you want this contract? I don't have an answer for you, but hey, it includes a transfer.

parameter key_hash;
return unit;
storage unit;
code { CAR; DEFAULT_ACCOUNT; # Create an account for the recipient of the funds
       DIP{UNIT};             # Push a value of the storage type below the contract
       PUSH tez "1.00";       # The person can have a ꜩ
       UNIT;                 # Push the contract's argument type
       TRANSFER_TOKENS;      # Run the transfer
       PAIR };                # Cleanup and put the return values

Tip: to see what the instructions do to the stack, run:

tezos-client typecheck program take_my_money.tz -details

July 24, 2017: Identity

Lets start with the identity contract. Michelson isn't polymorphic, so it's going to be the identity contract for strings. Here it is:

parameter string;
return string;
storage unit;
code {};

The stack starts with the following: (Pair string Unit). The contract must end with a pair consisting of the return value and the storage. In this case, the return type is string and the storage type is unit, therefore this type must be (pair string unit). That is exactly our starting type, so we don't need to do anything to have this contract conclude. You can write the identity contract for other types by changing the types for the parameter and return.