Alexander Chepurnoy, Vasily Kharin, Dmitry Meshkov

Self-reproducing Coinsas Universal Turing Machine0Overview

The paper is online: https://arxiv.org/abs/1806.10116

1

Overview

The paper is online: https://arxiv.org/abs/1806.10116
The very general question: how can we do more with less?

1

Questions

Can we achieve Turing completeness without jump (or equivalent) opcode?

2

Questions

Can we achieve Turing completeness without jump (or equivalent) opcode?
Can we do it in UTXO model?

2

Questions

Can we achieve Turing completeness without jump (or equivalent) opcode?
Can we do it in UTXO model?
If so, what is the practical use of it?

2

Outline

Turing completeness in blockchain environment
Scripting language prerequisites, UTXO's, ERGO
General construction + Proof of Turing completeness
Practical cases
Conclusions

3

Turing Completeness and Blockchain

A system is Turing complete if it can emulate universal Turing machine4Turing Completeness and Blockchain

A system is Turing complete if it can emulate universal Turing machine
Blockchain requires constant block validation time4Turing Completeness and Blockchain

A system is Turing complete if it can emulate universal Turing machine
Blockchain requires constant block validation time
There is a popular tenet in the folklore that if one needs Turing completeness on blockchain, jump, while, orrecursion must be present on the script level
There is a popular tenet in the folklore that if one needs Turing completeness on blockchain, jump, while, orrecursion must be present on the script level4Turing Completeness and Blockchain

A system is Turing complete if it can emulate universal Turing machine
Blockchain requires constant block validation time
There is a popular tenet in the folklore that if one needs Turing completeness on blockchain, jump, while, orrecursion must be present on the script level
There is a popular tenet in the folklore that if one needs Turing completeness on blockchain, jump, while, orrecursion must be present on the script level
But imagine Ethereum

where there is gas limit per block, and all the state changes are reversed after transaction

script execution (and payment amount is not dependent on the program). Then the Ethereumis notTuring-complete.

4Bitcoin⊕ : Boxes, Registers, Scripting

TX

Box0

Box1

Box2

5

Bitcoin⊕ : Boxes, Registers, Scripting

TXBox0

Box1

Box25

Bitcoin⊕ : Boxes, Registers, Scripting

TX

Box

Box0

R0 Monetary value
R1 Guarding Script

Box1

R2 General Purpose···Box2

R9 General purpose

5

Bitcoin⊕ : Boxes, Registers, Scripting

TX

Box

Box0

R0 Monetary value
R1 Guarding Script

Box1

R2 General Purpose
···

Box2

R9 General purpose

5

Bitcoin⊕ : Boxes, Registers, Scripting
Scripting language
TX

Box

Box0

R0 Monetary value
R1 Guarding Script

Box1

R2 General Purpose
···

Box2

R9 General purpose

5

Bitcoin⊕ : Boxes, Registers, Scripting
Scripting languageBasic arithmetics

TX

Box

Box0

R0 Monetary value
R1 Guarding Script

Box1

R2 General Purpose
···

Box2

R9 General purpose

5

Bitcoin⊕ : Boxes, Registers, Scripting
Scripting language
Basic arithmetics

TX

Box

Box0

If-then-else clause

R0 Monetary value
R1 Guarding Script

Box1

R2 General Purpose
···

Box2

R9 General purpose

5

Bitcoin⊕ : Boxes, Registers, Scripting
Scripting language
Basic arithmetics

TX

Box

Box0

R0 Monetary value

If-then-else clause
Cryptographic primitives

R1 Guarding Script
Box1

R2 General Purpose
···

Box2

R9 General purpose

5Bitcoin⊕ : Boxes, Registers, Scripting
Scripting language
Basic arithmetics

TX

Box

Box0

R0 Monetary value
R1 Guarding Script

If-then-else clause
Cryptographic primitives
Array declaration (predefined size) andaccess operations

Box1

R2 General Purpose
···

Box2

R9 General purpose

5

Bitcoin⊕ : Boxes, Registers, Scripting
Scripting language
Basic arithmetics

TX

Box

Box0

R0 Monetary value
R1 Guarding Script

If-then-else clause
Cryptographic primitives
Array declaration (predefined size) andaccess operations

Box1

R2 General Purpose

Context data···

Box2

R9 General purpose

HEIGHT: Int
SELF: BoxINPUTS: Array[Box]
OUTPUTS: Array[Box]5Bitcoin⊕ : Boxes, Registers, Scripting
Scripting language
Basic arithmetics

TX

Box

Box0

R0 Monetary value
R1 Guarding Script

If-then-else clause
Cryptographic primitives
Array declaration (predefined size) andaccess operations

Box1

R2 General Purpose

Context data···

Box2

R9 General purpose

HEIGHT: Int
SELF: BoxINPUTS: Array[Box]
OUTPUTS: Array[Box]5

Rule 110 Cellular Automaton
Turing completeness can be demonstrated by simulating asimple Turing complete system.

Cook, M.: Universality in elementary cellular automata(https://git.io/vj6sw)

6Rule 110 Cellular Automaton
Turing completeness can be demonstrated by simulating asimple Turing complete system.

Cook, M.: Universality in elementary cellular automata(https://git.io/vj6sw)

6Rule 110 Cellular Automaton
Turing completeness can be demonstrated by simulating asimple Turing complete system.

x = ` · c · r + c · r + c + r mod 2

Cook, M.: Universality in elementary cellular automata(https://git.io/vj6sw)

6Rule 110 Cellular Automaton
Turing completeness can be demonstrated by simulating asimple Turing complete system.

x = ` · c · r + c · r + c + r mod 2
let indices: Array[Int]=Array(0, 1, 2, 3, 4, 5)
let inLayer: Array[Byte]=SELF.R3[Array[Byte]].value
fun procCell(i: Int): Byte = {let l = inLayer((if(i==0) 5 else (i-1)))
let c = inLayer(i)let r = inLayer((i + 1) % 6)((l * c * r + c * r + c + r) % 2).toByte}(OUTPUTS(0).R3[Array[Byte]].value==indices.map(procCell)) &&(OUTPUTS(0).R1 == SELF.R1)

Cook, M.: Universality in elementary cellular automata(https://git.io/vj6sw)

6Rule 110 Cellular Automaton
Turing completeness can be demonstrated by simulating asimple Turing complete system.

x = ` · c · r + c · r + c + r mod 2
let indices: Array[Int]=Array(0, 1, 2, 3, 4, 5)
let inLayer: Array[Byte]=SELF.R3[Array[Byte]].value

Transaction 1

fun procCell(i: Int): Byte = {Output[0]Input[x1]let l = inLayer((if(i==0) 5 else (i-1)))

payloadscriptlet c = inLayer(i)···let r = inLayer((i + 1) % 6)

Transaction 2((l * c * r + c * r + c + r) % 2).toByte

Output[0]Input[x2]payloadscript}···(OUTPUTS(0).R3[Array[Byte]].value==

Transaction 3
Output[0]Input[x3]payloadscriptindices.map(procCell)) &&(OUTPUTS(0).R1 == SELF.R1)···

Cook, M.: Universality in elementary cellular automata(https://git.io/vj6sw)

6Rule 110 Cellular Automaton
Turing completeness can be demonstrated by simulating asimple Turing complete system.

x = ` · c · r + c · r + c + r mod 2
let indices: Array[Int]=Array(0, 1, 2, 3, 4, 5)
let inLayer: Array[Byte]=SELF.R3[Array[Byte]].value

Transaction 1

fun procCell(i: Int): Byte = {Output[0]Input[x1]let l = inLayer((if(i==0) 5 else (i-1)))

payloadscriptlet c = inLayer(i)···let r = inLayer((i + 1) % 6)

Transaction 2((l * c * r + c * r + c + r) % 2).toByte

Output[0]Input[x2]payloadscript}···(OUTPUTS(0).R3[Array[Byte]].value==Transaction 3
Output[0]Input[x3]payloadscriptindices.map(procCell)) &&(OUTPUTS(0).R1 == SELF.R1)···

We just allowed recursive calls by granting the script
Cook, M.: Universality in elementary cellular automata(https://git.io/vj6sw)

access to an output.
6

Rule 110 Cellular Automaton: Infinite Tape
Use transaction chaining to share memory between the transactions
T X0

T X3

T X6

T X9

T X1

T X4

T X7

T X10

T X2

T X5

T X8T X11

2 1 0
5 4 3
8 7 6
11 10 9https://git.io/vj6rX
7

Examples

Crowdfunding
Demurrage currency
Oracles (w. authenticated state)
Decentralized exchanges
https://github.com/ergoplatform/ergo/blob/master/papers/yellow

8Practical Case: Ergo Token Emission

coins per block80
60

let epoch = 1 + (HEIGHT-fixedRatePeriod)/epochLength40

let out = OUTPUTS(0)let coinsToIssue = if(HEIGHT < fixedRatePeriod) fixedRate

20

else fixedRate - oneEpochReduction*epoch00

24time, years

68

let correctCoinsConsumed = coinsToIssue==(SELF.value - out.value)
let sameScriptRule = SELF.propositionBytes==out.propositionBytes

1.0

let heightIncreased = HEIGHT>SELF.R3[Long].value

×108

let heightCorrect = out.R3[Long].value==HEIGHT

net supply

0.8

let lastCoins = SELF.value<=oneEpochReduction

0.6(correctCoinsConsumed && heightCorrect && heightIncreased &&0.4,→sameScriptRule) || (heightIncreased && lastCoins)

0.2
0.00

https://github.com/ergoplatform/ergo/blob/master/papers/yellow
24time, years

689Conclusions

Turing Completeness of the blockchain system can be achieved by unwinding the recursive calls between thetransactions. It fully complies with the blockchain requirements, and does not require ad-hoc structures to bypass
the halting problem
We provide the explicit proof of the Turing completeness of Ergo blockchain scripting system. To our knowledge,
this is the first proof of that kind
The construction is explicit, and the functionality is fully implemented
Self-reproducing coins allow one to make practical constructions. As an example, significant fraction of thevalidation rules can be brought from the hard-coded form to the scripting layer. Moreover, the logic of arbitrarycomplexity can be potentially implemented

10Thank you for your attention
10