AuxPOW Puzzle

Post Reply
phelix
Posts: 1631
Joined: Thu Aug 18, 2011 6:59 am

AuxPOW Puzzle

Post by phelix » Thu Mar 12, 2015 4:56 pm

This python code checks the work done for Namecoin blocks. Unfortunately it does not yet work with merge mined blocks with auxiliary proof of work (auxPOW). Who can solve the puzzle and make the code work? The puzzle should be self contained. (Let me know if something is missing as I did not yet try it myself.)

The point of this is building an API server that includes some additional data with a name lookup so that it can be verified that the data is original.

Info on how to build the hash chain:
https://en.bitcoin.it/wiki/Merged_mining_specification
https://github.com/namecoin/namecoin/bl ... -mining.md

(block data removed, full version here: https://gist.github.com/phelixbtc/b48b420132c1c1f228ac )

Code: Select all

import hashlib
import struct

####http://python-bitcoinlib.readthedocs.org/en/latest/_modules/bitcoin/core/serialize.html
def uint256_from_str(s):
    """Convert bytes to uint256"""
    r = 0
    t = struct.unpack(b"<IIIIIIII", s[:32])
    for i in range(8):
        r += t[i] << (i * 32)
    return r

def uint256_from_compact(c):
    """Convert compact encoding to uint256
    Used for the nBits compact encoding of the target in the block header. """
    nbytes = (c >> 24) & 0xFF
    v = (c & 0xFFFFFF) << (8 * (nbytes - 3))
    return v 
####

def reverse_byte_order(data):
    return data[::-1]

def get_merkle_parents(data):
    if len(data) % 2:
        data.append(data[-1])
    hashes = []
    half = len(data) / 2
    for i in range(half):
        hashes.append((dsha256(data[i * 2] + data[i * 2 + 1])))
    if len(hashes) == 1:
        return hashes
    return hashes + get_merkle_parents(hashes)

def get_merkle_tree(txs_data):
    """hex in, hex out"""
    if len(txs_data) == 0:
        return 0
    if len(txs_data) == 1:
        #return dsha256(txs_data[0])
        return [txs_data[0]]
    txs_data_rev = []
    for t in txs_data:
        txs_data_rev.append(reverse_byte_order(t.decode("hex")))
    treeHashed = get_merkle_parents(txs_data_rev)
    tree = []
    for t in treeHashed:
        tree.append(reverse_byte_order(t).encode("hex"))
    tree = txs_data + tree
    return tree

def get_merkle_root(txs_data):    
    return get_merkle_tree(txs_data)[-1]

def dsha256(data):
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()

def hash_block(B):
    blkheader = ""
    blkheader += struct.pack('<I', B['version'])
    blkheader += B['previousblockhash'].decode("hex")[::-1]
    blkheader += B["merkleroot"].decode("hex")[::-1]
    blkheader += struct.pack('<I', B['time'])
    blkheader += struct.pack('<I', B['bits'])
    blkheader += struct.pack('<I', B['nonce'])
    h = dsha256(blkheader)[::-1]
    return h.encode("hex")

def check_pow(blockHash, bits):
    target = uint256_from_compact(bits)

    if len(blockHash) == 64:
        blockHash = blockHash.decode("hex")
    assert(len(blockHash) == 32)
    
    blockHash = reverse_byte_order(blockHash)  # why?
    nHash = uint256_from_str(blockHash)

    #print "target:", target
    #print "nHash:", nHash

    return nHash <= target

if __name__ == "__main__":
    # block data as from client
    b10001 = {u'merkleroot': u'41183c608fc0cac556f219330c418cf0381c178d3f25db5b254af204340aa4b8', ...
    b19199 = {u'merkleroot': u'0f8e8a23da3c8e53f9ef1f6722d0667e228b9275cd61e9a1460d717763d89894', ...
    b200000 = {u'merkleroot': u'ca714d4f72d212bbbb3521886ff2561f54506cdbb2515acb2d26842005fe7744', ...

    for b in [b10001, b19199, b200000]:
        print "block height:", b["height"]
        print "original block hash:", b["hash"]
        print "hashed block ok:", hash_block(b) == b["hash"]
        print "calculated merkle root ok:", get_merkle_root(b["tx"]) == b["merkleroot"]
        print "pow check:", check_pow(b["hash"], b["bits"])
        print
Output:
block height: 10001
original block hash: 000000000012718050e3537c3c355f3746fc8cd6434d44e79417276d6683b7ab
hashed block ok: True
calculated merkle root ok: True
pow check: True

block height: 19199
original block hash: 000000000000b19f0ad5cd46859fe8c9662e8828d8a75ff6da73167ac09a9036
hashed block ok: True
calculated merkle root ok: True
pow check: True

block height: 200000
original block hash: bdec8422dcad4c6168041068ab8f00d73efb38556cd47cf5af157649ab39855d
hashed block ok: True
calculated merkle root ok: True
pow check: False
nx.bit - some namecoin stats
nf.bit - shortcut to this forum

domob
Posts: 1123
Joined: Mon Jun 24, 2013 11:27 am
Contact:

Re: AuxPOW Puzzle

Post by domob » Thu Mar 12, 2015 6:25 pm

I've not looked at the code ... you could take a look at Namestamp, which does a full check of the auxpow. One important piece of information from the back of my mind: One of the hashes (I think it is the Merkle hash of the "tree of merge-mined chains" embedded into the coinbase) has its bytes reversed. I do not know why, but that's how it is. You can check the code in auxpow.cpp.
BTC: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS
Use your Namecoin identity as OpenID: https://nameid.org/

josephbisch
Posts: 69
Joined: Sun Nov 23, 2014 3:34 pm
os: linux

Re: AuxPOW Puzzle

Post by josephbisch » Thu Mar 12, 2015 6:38 pm

I'm not sure what is exactly going on. If the point of check_pow() is to determine whether a block has auxpow or not, you can just check the version in the block header.

The last paragraph of this blog post may be of help.

I think it seems easy. Based on the version, you either read the extra auxpow data or you don't. Maybe I don't understand what it is you are asking.

phelix
Posts: 1631
Joined: Thu Aug 18, 2011 6:59 am

Re: AuxPOW Puzzle

Post by phelix » Fri Mar 13, 2015 8:05 am

josephbisch wrote:I'm not sure what is exactly going on. If the point of check_pow() is to determine whether a block has auxpow or not, you can just check the version in the block header.

The last paragraph of this blog post may be of help.

I think it seems easy. Based on the version, you either read the extra auxpow data or you don't. Maybe I don't understand what it is you are asking.
The point is to establish a hash chain between a name_operation and POW. To do so you need to hash various constants...
nx.bit - some namecoin stats
nf.bit - shortcut to this forum

johnc
Posts: 89
Joined: Sun Dec 28, 2014 10:03 am

Re: AuxPOW Puzzle

Post by johnc » Sun Mar 15, 2015 3:14 am

I think Phelix wonders what nmc does exactly to check that a nmc block passes the difficulty test. (after block 19200)

obviously there will be different rules for before and after that block.

I would say it's hash of the bitcoin block , but it's really some merkle tree hash, for me it's like inception, so i cannot explain it...

phelix
Posts: 1631
Joined: Thu Aug 18, 2011 6:59 am

Re: AuxPOW Puzzle

Post by phelix » Fri Aug 14, 2015 12:59 pm

phelix wrote:I recently solved the AuxPOW puzzle myself: http://blockchained.com/stuff/auxpowpuzzle_solve.py_ Learned something. :mrgreen:

I will try and make it a proper module.
nx.bit - some namecoin stats
nf.bit - shortcut to this forum

Post Reply