bitcoin script与逆波兰运算(一)

2017-12-19 本文已影响113人已不再更新_转移到qiita

直接入正题,我们看下 a8d0c0184dde994a09ec054286f1ce581bebf46446a512166eae7628734ea0a5 这个txid,
执行脚本是 OP_DUP OP_HASH160 721afdf638d570285d02d3076d8be6a03ee0794d OP_EQUALVERIFY OP_CHECKSIG.

bitcoin script 是一种基于栈的,类似Forth的一门语言,可以把bitcoin script当作在bitcoin系统中使用的一种特殊的计算机语言(但是bitcoin script不具备图灵完备性, 缺少循环, 因此又不能说是计算机语言),但是在语言设计思想上跟Forth类似(有多类似我不知道, Forth诞生在很古老的时期).

很抽象, 不懂, 那我们先从计算器说起, linux自带了有2个很好玩儿的命令行计算器bc dc.

玩玩BC计算器

在命令行输入 bc, 即进入 bc计算器, 接着输入 1 + 2, 再按确认键,会得到计算结果.
继续输入 1 + 2*3 , (1+2)*3 , 计算结果都是正确的.

试试DC计算器

在命令行输入 dc, 进入dc计算器, 输入 1 2 + p (注意有空格), 按确认键, 猜猜得到什么结果?
再试试 5 2 * p, 6 4 - p , 72 9 / p.
在 dc计算器中 1 2 + 表达的含义就是 1 + 2, p是 print的缩写,打印最后的结果(打印的是栈顶元素)

这种把操作符置后的方式叫逆波兰表达式 ,即 RPN，更通俗的叫法是后缀表达式 .
人类更容易理解的模式: X <op> Y, <op> 指代 + - * /, RPN的模式: X Y <op> .

RPN有好处么

不需要括号也不需要定义优先级就可以运算

用dc 计算 1 + 2*3 即 1 2 3 * + p, 含义(1 (2 3 *) + ) p , 先计算 2 3 * 得到 result, 再计算
1 result +

(1+2) * 3 即 1 2 + 3 * p, 含义 ((1 2 + ) 3 *), 先计算 1 2 +得到 res, 再计算 res 3 *

使用逆波兰表达式和栈我们也可以很方便的实现一个简单的计算器

栈就用数组表示: []-[]-[]-[] ... [] , 左边第一个位置叫栈顶, 设定坐标是 0, 之后的依次类推 .

当输入的是数字时, 放入数组的第一个位置,
比如我们输入 1, 栈就是 [1]-[]-[]-[] ... []
输入2, 栈就是 [1]-[2]-[]-[] ... []
输入+, 栈就不是 [1]-[2]-[+]-[] ... [], 而是弹出2个元素(弹出来元素就没了), index是0的元素赋值给 op1,
index是1的元素赋值给 op2, 既然是 +，表达式就是 res= op1 + op2, 然后把 res放到栈顶，栈的状态就是[3]...[]

如果输入 1 2 -, 重复以上步骤， res= op1 - op2, 注意 op1 op2赋值的顺序。然后把 res放到栈顶，栈的状态就是[-1]...[]

如果是错误的表达式，比如输入 1 +，
输入 1, 栈是 [1]-[]-[]-[] ... []
输入 +, 检查栈的长度，如果小于2，给予警告，栈不变还是 [1]-[]-[]-[] ... []
在继续输入 2，栈 [1]-[2]-[]-[] ... []，重复之前的过程。
+- */ 这些运算符号不会保留在栈中，只会操作栈里的元素。

如果输入 1 4 + 3 *
输入1 [1]-[]-[]...[]
输入2 [1]-[4]-[]...[]
输入+ [5]-[]-[]...[]
输入3 [5]-[3]-[]...[]
输入* [15]-[]-[]...[]

如果输入 1 2 3 * + p
输入1 [1]-[]-[]...[]
输入2 [1]-[2]-[]...[]
输入3 [1]-[2]-[3]...[]
输入* [1]-[6]-[]...[]
输入+ [7]-[]-[]...[]

实现个简单的dc

代码看 github
下载完, 执行 make, 得到一个 dc的执行文件，执行 ./dc
输入 1 2 + p 再回车, 看看结果吧.

转换一种形式

把 + 替换成 ADD

输入 1 2 ADD, 这样带来一个问题，ADD 是3个字符，之前我们说过，栈是不保存操作符的.
怎么办呢? dc只能处理单字符, 我们转换下就可以处理多字符.

//伪代码
str = "1 2 ADD"
tokens = str.split('')  // ['1', '2', 'ADD']
token_trans = tokens.trans()  // 转换成 ['1', '2', '+']
// 又回到了之前的处理步骤

那把ADD替换成0x93可以么? 只能计算加减乘除, 弱爆了, 我要定义个 OP_SHA256 操作符,代号是0xa8.
当输入 shooter2017 OP_SHA256 时, 就对 shooter2017 进行 sha256 计算.
再定义些 OP_HASH160 OP_CHECKSIG OP_CHECKSIGVERIFY OP_CHECKMULTISIG呢?

参考：
https://en.bitcoin.it/wiki/Script
https://en.wikipedia.org/wiki/Reverse_Polish_notation
https://www.computerhope.com/unix/udc.htm
https://github.com/ChristopherA/Learning-Bitcoin-from-the-Command-Line/blob/master/07_2_Running_a_Bitcoin_Script.md
https://www.jianshu.com/p/ca1e5daf5c6b