First release of Optz Michelson optimizer

We have released Optz, an optimizer of Michelson programs, the base language for Tezos smart contract. It takes a Michelson code as input and then returns a smaller and more efficient equivalent code.

Optimization of Michelson opcode sequences

The optimization consists of 2 parts: rule-based transformation and optimal stack manipulation search by A* algorithm.

Rule based code transformation

Dozens of rewriting rules replace opcodes with better ones, such as:

PAIR; CDR  =>  DROP
   
DIP n { a }; DIP n { b }  =>  DIP n { a; b }
   
SWAP; op  =>  op  # when op is a commutative binary operator
   
NOT; IF { a } { b }  =>  IF { b } { a }

Search for the optimal stack manipulation sequences

A* algorithm finds the most optimal sequence of stack manipulation opcodes such as DROP, SWAP, DIG, DUG, DIP, DUP, and the push only opcodes like PUSH and EMPTY_SET. For example, the following opcode sequence :

DIG 1; DUP 1; DUG 2; PUSH c0; DIG 2; PUSH c1; DIG 4

is replaced with a shorter equivalent one:

PUSH c0; DIG 1; PUSH c1; DUP 4

The search space explodes exponentially when the range of the stack touched by the target opcodes and the number of constants in it grows. To finish the optimization in a reasonable time, the maximum size of the search space is introduced.

Special case for drop-only sequence

Compilers from higher-level languages to Michelson clean the stack when the program execution exits each functional and variable scope. We have observed some compilers tend to produce very long inefficient stack cleaning opcode sequences. They are too big for the above A* algorithm to optimize.

To optimize these stack cleaners, a special case of stack manipulation optimization is introduced for “drop only sequences”, which never push nor reorder stack elements but only drop some of them. The optimal opcodes are easily constructible for these drop-only sequences, therefore no size restriction is necessary. For example,

DROP 2; DIG 1; DROP 1; DIG 1; DROP 1; DIG 3; DROP 1; DIG 3; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1; DIG 4; DROP 1

can be optimized to the following much shorter efficient code:

DROP 2; DUG 2; DROP 2; DIG 3; DIG 4; DROP 2; DIP 4 { DROP 6 }

Optimization of Tezos Mainnet contracts

We have tested Optz against 1711 different Michelson contracts deployed on Tezos Mainnet between 2021-02-18 and 2022-02-17.

All the contracts are optimized within 1 second by a laptop (Mac Book Pro 13-inch 2017) and the output Michelson encoding size is 94.0% of the inputs in average. Some are reduced by over 30%!

Try Optz now

We have released the source code, a Docker image, and also a web app of Optz. Please check Optz page for further information.