1 of 43

Bits, Booleans,

Battlestar Galactica

How bitvm works

2 of 43

Outline

What bitvm is

What bitvm can and can’t do

Boolean circuits

Putting them in bitcoin addresses

How hashlocks and taproot fix everything

3 of 43

What bitvm is

��Bitvm is a virtual computer

Like real computers, it can run programs

Its programs go inside btc addresses

​

4 of 43

What bitvm is

�Bitvm programs typically run “off chain”

Two counterparties both run the program

If a party runs it wrong, they lose sats be-�cause the code is *also* in a btc address

5 of 43

What bitvm is

This bitvm address has an “addition” program in it

bc1gh3395j0asmng9498qkf

Yeah, we funded it together & we both checked the code

6 of 43

What bitvm is

I assert that 1 + 1 = 3

bc1gh3395j0asmng9498qkf

K, send me “bit commitments” for each number

7 of 43

What bitvm is

0 0 0 1 + 0 0 0 1 = 0 0 1 1

Whoa, my copy of bitvm says your equation is false!

8 of 43

What bitvm is

Rats, you caught me!

bc1gh3395j0asmng9498qkf

I can prove your error on bitcoin and take your money!

9 of 43

What bitvm can do

Currently: add, compare, and count

In theory: run any (converted) program

I see a path to do these things:

  • Any two player game, such as chess
  • Bonded covenants (but not “real” covenants)
  • Optimistic sidechains (basically better federations)

10 of 43

Bitvm limitations

Bitvm contracts need at least�2 parties: a prover and a verifier

Bitvm contracts need interactive�setup and execution

Bonded covenants can be broken�for a high price

11 of 43

Bitvm limitations

Optimistic sidechains trust at�least 1 person (but it can be you!)

Disputing a large program would�likely be very expensive

A mining pool with a hashrate�majority can steal from bitvm

12 of 43

A very basic computer

AND

GATE

13 of 43

A very basic computer

AND

GATE

14 of 43

A very basic computer

AND

GATE

15 of 43

A very basic computer

AND

GATE

16 of 43

A very basic computer

AND

GATE

17 of 43

Logic gates

1� 1

1

0� 1

1

1� 1

0

0� 1

0

18 of 43

A 2 bit adder

AND

GATE

XOR

GATE

0

​

​

​

0

19 of 43

A 2 bit adder

​

AND

GATE

XOR

GATE

0

​

​

​

1

20 of 43

A 2 bit adder

AND

GATE

XOR

GATE

0

​

​

​

1

21 of 43

A 2 bit adder

AND

GATE

XOR

GATE

1

​

​

​

0

22 of 43

An 8 bit adder

23 of 43

An IBM cpu

24 of 43

An IBM cpu

25 of 43

Anatomy of a “regular” bitcoin transaction

0100000001186f9f998a5aa6f048e51dd8419a14d8a0f1a8a2836dd734d2804fe65fa35779000000008b483045022100884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb02204b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e381301410484ecc0d46f1918b30928fa0e4ed99f16a0fb4fde0735e7ade8416ab9fe423cc5412336376789d172787ec3457eee41c04f4938de5cc17b4a10fa336a8d752adfffffffff0260e31600000000001976a914ab68025513c3dbd2f7b92a94e0581f5d50f654e788acd0ef8000000000001976a9147f9b1a7fb68d60c536c2fd8aeaa53a8f3cc025a888ac00000000

26 of 43

Anatomy of a “regular” bitcoin transaction

0100000001186f9f998a5aa6f048e51dd8419a14d8a0f1a8a2836dd734d2804fe65fa35779000000008b483045022100884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb02204b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e381301410484ecc0d46f1918b30928fa0e4ed99f16a0fb4fde0735e7ade8416ab9fe423cc5412336376789d172787ec3457eee41c04f4938de5cc17b4a10fa336a8d752adfffffffff0260e31600000000001976a914ab68025513c3dbd2f7b92a94e0581f5d50f654e788acd0ef8000000000001976a9147f9b1a7fb68d60c536c2fd8aeaa53a8f3cc025a888ac00000000

27 of 43

The “script sig” aka “witness stack”

0100000001186f9f998a5aa6f048e51dd8419a14d8a0f1a8a2836dd734d2804fe65fa35779000000008b483045022100884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb02204b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e381301410484ecc0d46f1918b30928fa0e4ed99f16a0fb4fde0735e7ade8416ab9fe423cc5412336376789d172787ec3457eee41c04f4938de5cc17b4a10fa336a8d752adfffffffff0260e31600000000001976a914ab68025513c3dbd2f7b92a94e0581f5d50f654e788acd0ef8000000000001976a9147f9b1a7fb68d60c536c2fd8aeaa53a8f3cc025a888ac00000000

28 of 43

Spending via a “sum to 3” program

0100000001186f9f998a5aa6f048e51dd8419a14d8a0f1a8a2836dd734d2804fe65fa357790000000006515203935387ffffffff0260e31600000000001976a914ab68025513c3dbd2f7b92a94e0581f5d50f654e788acd0ef8000000000001976a9147f9b1a7fb68d60c536c2fd8aeaa53a8f3cc025a888ac00000000

06 = 6 byte # 52 = OP_2 93 = OP_ADD �03 = 3 byte # the program = 935387 53 = OP_3�51 = OP_1 its anatomy = 935387 87 = OP_EQUAL

29 of 43

Bitcoin Script’s built-in functions

  • Signature functions: CHECKSIG & CHECKMULTISIG�
  • Password functions: HASH160 & SHA256�
  • Time functions: CLTV (absolute time) & CSV (relative time)�
  • Math functions: ADD, SUB, GREATERTHAN, LESSTHAN, EQUAL�
  • Stack functions: DUP, DROP, SWAP, ROT, DEPTH�
  • Boolean functions: AND, OR, NOT, NAND, NOR, XOR, XNOR�
  • Branching logic: IF/THEN/ELSE, VERIFY, RETURN�
  • Full list: https://en.bitcoin.it/wiki/Script

30 of 43

Boolean AND program in bitcoin script

Use this library: https://www.npmjs.com/package/@cmdcode/tapscript�var script = [� 'OP_BOOLAND'

];�var address = tapscript.Address.p2wsh.fromScript(script, "testnet");�console.log(address);�//tb1qqczaz56whzv4l68u0h83ltqzt6j7ym7zd443lsk8n2s0qs2eaaqsh92y5r

31 of 43

Spending via a “boolean AND” program

0100000001186f9f998a5aa6f048e51dd8419a14d8a0f1a8a2836dd734d2804fe65fa3577900000000045151019affffffff0260e31600000000001976a914ab68025513c3dbd2f7b92a94e0581f5d50f654e788acd0ef8000000000001976a9147f9b1a7fb68d60c536c2fd8aeaa53a8f3cc025a888ac00000000

04 = 4 byte # the program = 9a� 51 = OP_1 9a = OP_BOOLAND� 01 = 1 byte #

32 of 43

A few problems

The witness stack is malleable

Need >100 megabytes

Can’t use >400 kilobytes

Solution

Hashlocks and taproot fix this

33 of 43

How taproot helps

One address, many scripts

Each script has an identifier

Normally, the spender picks�which one to use

But hashlocks allow Vicky to�pick a script on Paul’s behalf

34 of 43

Transferring state with hashlocks

Address A

​

Show Preimage X or Preimage Y

​

Then the sats must go to Address B

Address B

​

Preimage X = 0�Preimage Y = 1

​

Vicky can spend w/ both preimages

35 of 43

Our logic gate is bigger now (1/3): NOT gate

OP_SHA256 //this hashlock ensures Vicky picks the script� 99ebdc5d4b54fe94a5750bb887d3944 OP_EQUALVERIFY� OP_SHA256 //the next two one let Paul pick a 1 or a 0� a93ef3a7b083e2d631f6f4d1c9053549 OP_EQUAL� OP_IF� OP_1� OP_ELSE� 64c319be85f63748e891d5d7785e2e95 OP_EQUALVERIFY� OP_0� OP_ENDIF

36 of 43

Our logic gate is bigger now (2/3): NOT gate

OP_NOT� OP_SWAP� OP_SHA256� 47217b232be277635ea84b85f63748e OP_EQUAL� OP_IF� OP_1� OP_ELSE� 980ce21ed17038ec7c1f3254f4064d65 OP_EQUALVERIFY� OP_0� OP_ENDIF

37 of 43

Our logic gate is bigger now (3/3): NOT gate

OP_EQUAL� OP_IF //continue the challenge/response game� OP_0� <pauls_pubkey> OP_CHECKSIGADD� <vickys_pubkey> OP_CHECKSIGADD� OP_2 OP_EQUAL� OP_ELSE //otherwise let Vicky spend the money unilaterally� <2 weeks> OP_CHECKSEQUENCEVERIFY� <vickys_pubkey> OP_CHECKSIG� OP_ENDIF

38 of 43

Hooking Logic Gates Together

AND

GATE

XOR

GATE

39 of 43

Hooking Logic Gates Together

​

� A/B� C/D

AND

GATE

XOR

GATE

E/F

​

​

​

G/H

40 of 43

Hooking Logic Gates Together

​

� A/B� C/D

AND

GATE

XOR

GATE

E/F

​

​

​

G/H

NAND

GATE

41 of 43

Response Addresses

Every response address�has multiple script paths

Paul wins if Vicky is slow

Vicky wins if Paul equivocated

Or Vicky can challenge again�but only by unlocking a hashlock

Hashlock 150 for Vicky

Hashlock 150 for Paul

42 of 43

Binary Search aka Bisection

AND

GATE

XOR

GATE

NAND

GATE

XOR

GATE

AND

GATE

XOR

GATE

NAND

GATE

43 of 43

References

  1. Reverse Engineering a Standard Cell by Ken Shirriff
  2. Mastering Bitcoin by Andreas Antonopolous
  3. Bitcoin Script by The Bitcoin Wiki
  4. BitVM by Robin Linus
  5. Tapleaf Circuits by Super Testnet