OP_HASH256 of a negative number

Question

transaction 9 in block 251684 spends transaction 25 of block 249957. the script to be evaluated here is:

OP_PUSHDATA0(20) 16cfb9bc7654ef1d7723e5c2722fc0c3d505045e OP_SIZE OP_DUP OP_TRUE
OP_GREATERTHAN OP_VERIFY OP_NEGATE OP_HASH256 OP_HASH160 OP_SHA256 OP_SHA1
OP_RIPEMD160 OP_EQUAL

the problem i have is with how to sha256 a negative number. so far i have the following:

op: OP_PUSHDATA0(20) 16cfb9bc7654ef1d7723e5c2722fc0c3d505045e,
                    new stack: [0x16cfb9bc7654ef1d7723e5c2722fc0c3d505045e]
op: OP_SIZE,        new stack: [0x16cfb9bc7654ef1d7723e5c2722fc0c3d505045e, 20]
op: OP_DUP,         new stack: [0x16cfb9bc7654ef1d7723e5c2722fc0c3d505045e, 20, 20]
op: OP_TRUE,        new stack: [0x16cfb9bc7654ef1d7723e5c2722fc0c3d505045e, 20, 20, 1]
op: OP_GREATERTHAN, new stack: [0x16cfb9bc7654ef1d7723e5c2722fc0c3d505045e, 20, 1] (since 20 > 1)
op: OP_VERIFY,      new stack: [0x16cfb9bc7654ef1d7723e5c2722fc0c3d505045e, 20]
op: OP_NEGATE,      new stack: [0x16cfb9bc7654ef1d7723e5c2722fc0c3d505045e, -20]
op: OP_HASH256,     new stack: [0x16cfb9bc7654ef1d7723e5c2722fc0c3d505045e, ???]

Answer 1

This is an extremely useful site for debugging bitcoin scripts: http://webbtc.com/script.

Bitcoin uses a custom way to serialize integers, shown here. This is confusing, but keeps the number of bytes on the stack small as possible. Let's walk through the basic execution:

exec : 20 OP_NEGATE OP_HASH256
stack: 

exec : OP_NEGATE OP_HASH256
stack: 0x14

exec : OP_HASH256
stack: 0x94

exec : 
stack: 0xaf462e245a0f463a93e23a54eb0b4d0d8da7a951e4d0b41015782a27e80a2e2c

The confusing step is really the OP_NEGATE. To negate an integer that fits into 1 byte without having the MSB set, you just XOR with 0x80. Hence, 0x14 ^ 0x80 -> 0x94.

The script debugger I linked to above verifies this result. This python code verifies the result as well:

import hashlib
import binascii

def SHA256d(string):
    bin = binascii.unhexlify(string)
    hash = hashlib.sha256(hashlib.sha256(bin).digest()).digest()
    raw = str(binascii.hexlify(hash))[2:-1]
    return raw

print (SHA256d("94"))

Prints:

af462e245a0f463a93e23a54eb0b4d0d8da7a951e4d0b41015782a27e80a2e2c

Answer 2

The value that is hashed is the single byte 0x94.

The stack contains vectors of unsigned chars. OP_NEGATE converts the int -20 into a vector of unsigned chars by calling CScriptNum::getvch() here:

stack.push_back(bn.getvch());

CScriptNum::getvch() serializes ints into bytes by taking its absolute value, encoding the result in little-endian form using the fewest number of bytes possible, and then guarantying that the most significant bit of the most significant byte is set if and only if the value is negative.

Therefore -20 is serialized into the single byte 0x80 + 20 == 0x94.

This can be further verified by completing the rest of the script:

$ python
>>> from hashlib import *
>>> h = chr(0x80 + 20)
>>> h = sha256(sha256(h).digest()).digest()
>>> h = new('ripemd160', sha256(h).digest()).digest()
>>> h = sha256(h).digest()
>>> h = sha1(h).digest()
>>> h = new('ripemd160', h).digest()
>>> print h.encode('hex')
16cfb9bc7654ef1d7723e5c2722fc0c3d505045e

As an aside: that's a rather, uhm, interesting script you've found....