Stack Rotation Opcodes

Stack Rotation Opcodes

Author: Joonmo Yang<jmyang@codechain.io>

Created: 2019-10-30

1. Abstract

This CIP describes a new set of opcodes for CodeChain VM that moves the items in the middle of the stack to the top. It includes ROLL and ROLLN.

2. Motivation

When there are multiple conditions to check in a single CodeChain script, it is common to access the items in the middle of the stack. In addition, most of such cases only use those items once, so the items are usually dropped after the usage. This behavior can be implemented by combining COPY and DROP opcodes in the current system, but it’s so frequently used that it’d be better to provide a new specialized instruction. By introducing new opcodes, the scripts that originally used complex combinations of existing instructions will have to write only one opcode for the expected behavior.

3. Specification

3.1. ROLL(0x37)

  1. Read the next script byte(refer this value as i)
  2. Remove the ith stack item(stack top is 0th value)
  3. Push the removed item to the top of the stack

3.2. ROLLN(0x38)

  1. Read the next two script bytes(refer this value as i and n)
  2. Fail immediately if n == zero or i < n - 1
  3. Remove the ith stack item(stack top is 0th value)
  4. Push the removed item to the top of the stack
  5. Repeat 3~4 n times

4. Example

NOTE: the stack is written in the order of bottom to top. I.e. the rightmost item is the stack’s topmost item.

  • PUSH 1 PUSH 2 PUSH 3 PUSH 4 ROLL 2 → stack: [0x01, 0x03, 0x04, 0x02]
  • PUSH 1 PUSH 2 PUSH 3 PUSH 4 ROLL 3 → stack: [0x02, 0x03, 0x04, 0x01]
  • PUSH 1 PUSH 2 PUSH 3 PUSH 4 ROLLN 3 1 → stack: [0x02, 0x03, 0x04, 0x01]
  • PUSH 1 PUSH 2 PUSH 3 PUSH 4 ROLLN 3 2 → stack: [0x03, 0x04, 0x01, 0x02]

I’m not familiar with the notation.
Isn’t the last item usually the top when we describe the stack?

Oh, is it? I didn’t know that.
Could you give me some reference about it?

Well, I cannot found the reference, but it’s too natural in LTR context.

It seems Bitcoin wiki writes stack from bottom to top. I’ll follow their notation.