Michelson

Summary

The encoding of Micheline has several points to be improved. We propose to extend it to reduce the encoding size. Our quick survey shows that the possible size reduction is -22%.

The size reduction directly affects the storage burn fee. It should also improve the context disk access and reduces the storage access gas costs.

The new enconding is not yet implemented. The extension may have runtime overhead of the serialization but we expect it minimum.

Optz は Tezos ブロックチェーンのスマートコントラクトで使われている Michelson プログラムの最適化器です。 Optz は Michelson プログラムを入力として受け取り、(可能ならば)最適化を行って同じ動作をするより小さい、効率的な Michelson プログラムを出力します。

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:

[続きを読む]

Optz is 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

After the rule-based transformation, A* algorithm finds the most optimal sequence of stack manipulation opcodes such as DROP, SWAP, DIG, DUG, DIP, DUP, CAR, CDR, PAIR, UNPAIR, and the push only opcodes like PUSH and EMPTY_SET. For example, the following opcode sequence found in an existing contract in Tezos mainnet:

Tezos のスマートコントラクトは Michelson という VM で動いていますが、この VM オプコードを記述してみます。支援ツールとして Emacs の Michelson モードを使います。