开源 Bitcoin P2P电子货币系统背后的技术(三)

作者:李雪愚

前面讲了交易单,接下来讲讲交易单的类型和交易验证的实现细节。
交易的类型与验证

交易单(Transaction)目前被bitcoin分为3种:
按IP地址转账(Transfer)
按接收地址转账(Transfer)
造币(Generation)

通过前面对交易单的描述,我想大家应该已经知道,交易的验证是通过不断的追溯交易单来完成的。那么交易验证的细节是如何实现的,bitcoin的交易验证的实现细节是很意思的,它是通过脚本来实现验证的,这样bitcoin就实现了一个可被脚本扩展的行为,更加广义的”交易”,这可以保证足够的灵活性和可扩展,可以想象也许以后会有真正的分布式计算任务跑在上面作为一笔交易。因此要想讲清楚验证的细节,就不得不从脚本系统讲起了。

脚本系统

Bitcoin的脚本系统是使用类FORTH语言(FORTH在嵌入式设备中是我最喜欢的一种语言)实现的,FORTH系统是面向栈的“高级机器”语言,它兼具了高级语言的特性(面向WORD)和机器语言的高性能与小尺寸,唯一的缺点就是可读性不高,基本上可以把FORTH当一种高级的机器语言吧。Bitcoin在实现上做了许多简化和特殊实现,所以只能算是类FORTH的系统。

在FORTH系统中所有的命令(函数)都被称为单词(WORD),所有数据的处理都要压入数据栈上进行,所以FORTH被称为面向栈的语言。
比如 1和2相加,在FORTH系统中则是 1 2 +,数字 1,2 表示将它们压入到数据栈中(在FORTH解释器执行后实际指令会有OP_PUSH),+的操作则是将栈顶和次栈顶的数字取出并相加,并将结果压回数据栈。

Bitcoin的脚本系统的所有的操作指令(单词)见后面的附录,不是所有的操作指令都能被执行支持,因为安全上的考虑有的操作指令被禁止掉了,比如大多数的字符串操作和乘除运算。

在FORTH系统中一般会定义该系统是8位FORTH, 16位FORTH还是32/64位FORTH,这和数据栈的值长有关。在Bitcoin中的脚本系统使用的堆栈是用(vector<vector<unsigned char> >)来模拟的,它在数据栈的每一项都是以字符串的形式存放,它的数值是统一用CBigNum来运算的(读到这里应该明白为啥bitcoin会限制乘除运算了),每一次从数据栈中压入(CBigNum.getvch())或者取出数值(CastToBigNum(stacktop[-1]))都要进行一次转换。看着这样的实现,让我有点发怵,本能的不喜欢,怎么能把高效的FORTH搞成这个样子。Bitcoin的脚本系统与FORTH一样,有两个堆栈,一个数据栈,在Bitcoin中被称为main stack,一个返回栈,在Bitcoin中被称为alt stack(事实上在Bitcoin中将alt stack作为数据栈的中转而还没有作为FORTH意义上的返回栈). Bitcoin的脚本系统没有实现单词定义,流程跳转,循环控制(FOR, WHILE),对IF的实现非常丑陋。事实上我对Bitcoin的脚本实现不是十分认可,堆栈采用变长的数据值,直接将big number 作为opcode,导致每一次opcode执行开销无法控制,由于没有完整实现FORTH的控制指令,导致用trick的方式来实现IF指令,在bitcoin中也因此无法定义新的WORD。总之我很不喜欢bitcoin的这个脚本引擎实现(参见script.cpp)。

下一篇将接着介绍下和交易验证相关的几个操作符:OP_DUP, OP_HASH160, OP_EQUALVERIFY , OP_CHECKSIG 的功能,现在有点倦了。
enum opcodetype
{
// push value
OP_0=0,
OP_FALSE=OP_0,
OP_PUSHDATA1=76,
OP_PUSHDATA2,
OP_PUSHDATA4,
OP_1NEGATE,
OP_RESERVED,
OP_1,
OP_TRUE=OP_1,
OP_2,
OP_3,
OP_4,
OP_5,
OP_6,
OP_7,
OP_8,
OP_9,
OP_10,
OP_11,
OP_12,
OP_13,
OP_14,
OP_15,
OP_16,

// control
OP_NOP,
OP_VER,
OP_IF,
OP_NOTIF,
OP_VERIF,
OP_VERNOTIF,
OP_ELSE,
OP_ENDIF,
OP_VERIFY,
OP_RETURN,

// stack ops
OP_TOALTSTACK,
OP_FROMALTSTACK,
OP_2DROP,
OP_2DUP,
OP_3DUP,
OP_2OVER,
OP_2ROT,
OP_2SWAP,
OP_IFDUP,
OP_DEPTH,
OP_DROP,
OP_DUP,
OP_NIP,
OP_OVER,
OP_PICK,
OP_ROLL,
OP_ROT,
OP_SWAP,
OP_TUCK,

// splice ops
OP_CAT,
OP_SUBSTR,
OP_LEFT,
OP_RIGHT,
OP_SIZE,

// bit logic
OP_INVERT,
OP_AND,
OP_OR,
OP_XOR,
OP_EQUAL,
OP_EQUALVERIFY,
OP_RESERVED1,
OP_RESERVED2,

// numeric
OP_1ADD,
OP_1SUB,
OP_2MUL,
OP_2DIV,
OP_NEGATE,
OP_ABS,
OP_NOT,
OP_0NOTEQUAL,

OP_ADD,
OP_SUB,
OP_MUL,
OP_DIV,
OP_MOD,
OP_LSHIFT,
OP_RSHIFT,

OP_BOOLAND,
OP_BOOLOR,
OP_NUMEQUAL,
OP_NUMEQUALVERIFY,
OP_NUMNOTEQUAL,
OP_LESSTHAN,
OP_GREATERTHAN,
OP_LESSTHANOREQUAL,
OP_GREATERTHANOREQUAL,
OP_MIN,
OP_MAX,

OP_WITHIN,

// crypto
OP_RIPEMD160,
OP_SHA1,
OP_SHA256,
OP_HASH160,
OP_HASH256,
OP_CODESEPARATOR,
OP_CHECKSIG,
OP_CHECKSIGVERIFY,
OP_CHECKMULTISIG,
OP_CHECKMULTISIGVERIFY,

// expansion
OP_NOP1,
OP_NOP2,
OP_NOP3,
OP_NOP4,
OP_NOP5,
OP_NOP6,
OP_NOP7,
OP_NOP8,
OP_NOP9,
OP_NOP10,

// template matching params
OP_PUBKEYHASH = 0xfd,
OP_PUBKEY = 0xfe,

OP_INVALIDOPCODE = 0xff,
};
附录Bitcoin脚本系统单词列表
参见:https://en.bitcoin.it/wiki/Script:
常量
常量就是用来把数据压入栈中的单词:单词 虚拟指令(opcode) 输入 输出 Description
OP_0, OP_FALSE 0 Nothing. 0 压入数字0到栈中
N/A 1-75 (special) data 将紧随 opcode 的data数据 opcode个字节压入到堆栈。opcode兼作数据长度指示。
OP_PUSHDATA1 76 (special) data 紧随该指令的下一个字节是被压入数据大小,然后是被压入数据
OP_PUSHDATA2 77 (special) data 紧随该指令的两个字节是被压入数据大小,然后是被压入数据.
OP_PUSHDATA4 78 (special) data 紧随该指令的4个字节是被压入数据大小,然后是被压入数据.
OP_1NEGATE 79 无. -1 压入-1
OP_1, OP_TRUE 81 无. 1 压入1.
OP_2-OP_16 82-96 无. 2-16 2-16被压入.

控制流单词 Opcode 输入 输出 描述
OP_NOP 97 无 无 空指令.
OP_IF 99 <expression> if [statements] [else [statements]] endif If 判断指令,取出栈顶值,如果栈顶值为1, 则if后面的语句被执行,否则else中的语句被执行。
OP_NOTIF 100 <expression> ifnot [statements] [else [statements]] endif Ifnot 判断指令,取出栈顶值,如果栈顶值为0, 则if后面的语句被执行,否则else中的语句被执行。
OP_ELSE 103 <expression> if [statements] [else [statements]] endif 放置在 OP_IF 或OP_NOTIF 后的指令,当前面的条件不满足的时候执行
OP_ENDIF 104 <expression> if [statements] [else [statements]] endif 结束 if/else 执行块.
OP_VERIFY 105 True / false Nothing / False 标记交易单无效
如果栈顶值不为真。当栈顶值为真,移除该栈顶值,否则保留该值。
OP_RETURN 106 Nothing Nothing 标记交易单无效.

堆栈操作Word Opcode Input Output Description
OP_TOALTSTACK 107 x1 (alt)x1 从数据栈中弹出栈顶 数据,压入辅助栈。
OP_FROMALTSTACK 108 (alt)x1 x1 从辅助栈弹出栈顶数据压入到数据栈
OP_IFDUP 115 x x / x x 如果栈顶非0则复制栈顶
OP_DEPTH 116 Nothing <Stack size> 获取堆栈数据个数
OP_DROP 117 x Nothing 丢弃栈顶数据.
OP_DUP 118 x x x 复制栈顶数据.
OP_NIP 119 x1 x2 x2 丢弃次栈顶数据
OP_OVER 120 x1 x2 x1 x2 x1 复制次栈顶数据到栈顶.
OP_PICK 121 xn … x2 x1 x0 <n> xn … x2 x1 x0 xn 复制第n项数据到栈顶.
OP_ROLL 122 xn … x2 x1 x0 <n> … x2 x1 x0 xn 将第n项数据移到栈顶.
OP_ROT 123 x1 x2 x3 x2 x3 x1 栈顶3项数据向左旋转.
OP_SWAP 124 x1 x2 x2 x1 栈顶2项数据交换.
OP_TUCK 125 x1 x2 x2 x1 x2 栈顶数据复制并插入到次栈顶数据前
OP_2DROP 109 x1 x2 Nothing 同 DROP,只是数据项是2项.
OP_2DUP 110 x1 x2 x1 x2 x1 x2 同 DUP,只是数据项是2项.
OP_3DUP 111 x1 x2 x3 x1 x2 x3 x1 x2 x3 同 DUP,只是数据项是3项.
OP_2OVER 112 x1 x2 x3 x4 x1 x2 x3 x4 x1 x2 同 OVER,只是数据项是2项.
OP_2ROT 113 x1 x2 x3 x4 x5 x6 x3 x4 x5 x6 x1 x2 同 ROT,只是数据项是2项.
OP_2SWAP 114 x1 x2 x3 x4 x3 x4 x1 x2 同 SWAP,只是数据项是2项.

字符串处理

字符串处理的大多数指令都被禁止了。Word Opcode Input Output Description
OP_CAT 126 x1 x2 out Concatenates two strings. [禁止]
OP_SUBSTR 127 in begin size out Returns a section of a string. [禁止]
OP_LEFT 128 in size out Keeps only characters left of the specified point in a string. [禁止]
OP_RIGHT 129 in size out Keeps only characters right of the specified point in a string. [禁止]
OP_SIZE 130 in in size 返回字符串长度

位运算Word Opcode Input Output Description
OP_INVERT 131 in out Flips all of the bits in the input. [禁止]
OP_AND 132 x1 x2 out Boolean and between each bit in the inputs. [禁止]
OP_OR 133 x1 x2 out Boolean or between each bit in the inputs. [禁止]
OP_XOR 134 x1 x2 out Boolean exclusive or between each bit in the inputs. [禁止]
OP_EQUAL 135 x1 x2 True / false Returns 1 if the inputs are exactly equal, 0 otherwise.
OP_EQUALVERIFY 136 x1 x2 True / false Same as OP_EQUAL, but runs OP_VERIFY afterward.

数学运算Word Opcode Input Output Description
OP_1ADD 139 in out 1 is added to the input.
OP_1SUB 140 in out 1 is subtracted from the input.
OP_2MUL 141 in out The input is multiplied by 2. [禁止]
OP_2DIV 142 in out The input is divided by 2. [禁止]
OP_NEGATE 143 in out The sign of the input is flipped.
OP_ABS 144 in out The input is made positive.
OP_NOT 145 in out If the input is 0 or 1, it is flipped. Otherwise the output will be 0.
OP_0NOTEQUAL 146 in out Returns 1 if the input is 0. 0 otherwise.
OP_ADD 147 a b out a is added to b.
OP_SUB 148 a b out b is subtracted from a.
OP_MUL 149 a b out a is multiplied by b. [禁止]
OP_DIV 150 a b out a is divided by b. [禁止]
OP_MOD 151 a b out Returns the remainder after dividing a by b. [禁止]
OP_LSHIFT 152 a b out Shifts a left b bits, preserving sign. [禁止]
OP_RSHIFT 153 a b out Shifts a right b bits, preserving sign. [禁止]
OP_BOOLAND 154 a b out If both a and b are not 0, the output is 1. Otherwise 0.
OP_BOOLOR 155 a b out If a or b is not 0, the output is 1. Otherwise 0.
OP_NUMEQUAL 156 a b out Returns 1 if the numbers are equal, 0 otherwise.
OP_NUMEQUALVERIFY 157 a b out Same as OP_NUMEQUAL, but runs OP_VERIFY afterward.
OP_NUMNOTEQUAL 158 a b out Returns 1 if the numbers are not equal, 0 otherwise.
OP_LESSTHAN 159 a b out Returns 1 if a is less than b, 0 otherwise.
OP_GREATERTHAN 160 a b out Returns 1 if a is greater than b, 0 otherwise.
OP_LESSTHANOREQUAL 161 a b out Returns 1 if a is less than or equal to b, 0 otherwise.
OP_GREATERTHANOREQUAL 162 a b out Returns 1 if a is greater than or equal to b, 0 otherwise.
OP_MIN 163 a b out Returns the smaller of a and b.
OP_MAX 164 a b out Returns the larger of a and b.
OP_WITHIN 165 x min max out Returns 1 if x is within the specified range (left-inclusive), 0 otherwise.

加密相关Word Opcode Input Output Description
OP_RIPEMD160 166 in hash The input is hashed using RIPEMD-160.
OP_SHA1 167 in hash The input is hashed using SHA-1.
OP_SHA256 168 in hash The input is hashed using SHA-256.
OP_HASH160 169 in hash The input is hashed twice: first with SHA-256 and then with RIPEMD-160.
OP_HASH256 170 in hash The input is hashed two times with SHA-256.
OP_CODESEPARATOR 171 Nothing Nothing All of the signature checking words will only match signatures to the data after the most recently-executed OP_CODESEPARATOR.
OP_CHECKSIG 172 sig pubkey True / false The entire transaction’s outputs, inputs, and script (from the most recently-executed OP_CODESEPARATOR to the end) are hashed. The signature used by OP_CHECKSIG must be a valid signature for this hash and public key. If it is, 1 is returned, 0 otherwise.
OP_CHECKSIGVERIFY 173 sig pubkey True / false Same as OP_CHECKSIG, but OP_VERIFY is executed afterward.
OP_CHECKMULTISIG 174 sig1 sig2 … <number of signatures> pub1 pub2 <number of public keys> True / False For each signature and public key pair, OP_CHECKSIG is executed. If more public keys than signatures are listed, some key/sig pairs can fail. All signatures need to match a public key. If all signatures are valid, 1 is returned, 0 otherwise.
OP_CHECKMULTISIGVERIFY 175 sig1 sig2 … <number of signatures> pub1 pub2 … <number of public keys> True / False Same as OP_CHECKMULTISIG, but OP_VERIFY is executed afterward.

伪词(Pseudo-words)

下列词汇用于在内部使用,在脚本系统中实际上不存在的词。Word Opcode Description
OP_PUBKEYHASH 253 表示OP_HASH160 后的公开密钥散列
OP_PUBKEY 254 表示一个公开密钥(可以被 OP_CHECKSIG).
OP_INVALIDOPCODE 255

保留词(Reserved words)

没有被定义的opcode被保留以后使用,如果在脚本中使用这些保留词,要么被忽略,要么使得交易无效。Word Opcode When used…
OP_RESERVED 80 Transaction is invalid
OP_VER 98 Transaction is invalid
OP_VERIF 101 Transaction is invalid
OP_VERNOTIF 102 Transaction is invalid
OP_RESERVED1 137 Transaction is invalid
OP_RESERVED2 138 Transaction is invalid
OP_NOP1-OP_NOP10 176-185 The word is ignored.

转自http://www.showmuch.com/a/20110602/111007.html