Need help reversing bitcoinutils "tagged_hash" to generate Taproot addresses

BTCW

copper member

Activity: 193

Merit: 255

Click "+Merit" top-right corner

Think I nailed it!

I don't think such concrete Python code has been published elsewhere; correct me if I'm wrong. Anyways, here we go.

Let's start with some imports and two functions:

Code:

import hashlib, base58, bitcoinutils.bech32
from fastecdsa import keys, curve, ecdsa, point
curve = curve.secp256k1

def privkey_to_pubkey_hex(privkey, compressed=False):
    #Accept 64 char HEX, WIF and arbitrary length integer numbers as inputs
    
    try: #Is it WIF?
        privkey_hex = base58.b58decode_check(privkey).hex()
        privkey_hex = privkey_hex.replace('0x','')
        if len(privkey_hex) == 68:
            privkey_hex = privkey_hex[2:-2]
        if len(privkey_hex) == 66:
            privkey_hex = privkey_hex[2:]
    except:
        pass
    try: #Is it HEX?
        if int(str(privkey),16):
            privkey_hex = privkey
            privkey_hex = privkey_hex.replace('0x','')
            if len(privkey_hex) == 68:
                privkey_hex = privkey_hex[2:-2]
            if len(privkey_hex) == 66:
                privkey_hex = privkey_hex[2:]
    except:
        pass
    try: #Is it INT?
        if isinstance(privkey, int):
            privkey_hex = hex(privkey)[2:].zfill(64)
    except:
        pass
           
    try:
        privkey_int = int(privkey_hex,16)
        pub_key = keys.get_public_key(privkey_int, curve)
        uncompressed_public_key = '04'+str(hex(pub_key.x)[2:]).zfill(64)+str(hex(pub_key.y)[2:]).zfill(64)
        if compressed==False:
            return uncompressed_public_key
        else:
            if int(str(pub_key.y)) % 2 == 0:
                compressed_public_key = '02'
            else:
                compressed_public_key = '03'
            
            compressed_public_key += str(uncompressed_public_key[2:66])
            
            return compressed_public_key
    except:
        pass

def decompress_point(x, curve):
    y_squared = (x**3 + curve.a * x + curve.b) % curve.p
    y = pow(y_squared, (curve.p + 1) // 4, curve.p)
    if y % 2 == 0:
        return point.Point(x, y, curve=curve)
    else:
        return point.Point(x, curve.p - y, curve=curve)

And in action:

Code:

seed = '0000000000000000000000000000000000000000000000000000000000000001'
short_x = privkey_to_pubkey_hex(seed, compressed=True)[2:]
tag_hash = hashlib.sha256('TapTweak'.encode()).hexdigest()
tagged_hash = hashlib.sha256(bytes.fromhex(tag_hash + tag_hash + short_x)).hexdigest()
tagged_hash_pubx = privkey_to_pubkey_hex(tagged_hash, compressed=True)[2:]

point1 = decompress_point(int(short_x, 16), curve)
point2 = decompress_point(int(tagged_hash_pubx, 16), curve)

point_add = point1 + point2
tweaked_witness = hex(point_add.x)[2:]
print(bitcoinutils.bech32.encode('bc', 1, bytes.fromhex(tweaked_witness)))

Tweaked Taproot demystified - mission accomplished - the output is the desired Taproot public address!

Code:

bc1pmfr3p9j00pfxjh0zmgp99y8zftmd3s5pmedqhyptwy6lm87hf5sspknck9

Yay.

Thank you for all your support. This was the least user-friendly address generation code thus far

BTCW

copper member

Activity: 193

Merit: 255

Click "+Merit" top-right corner

Quote from: pooya87 on January 16, 2024, 11:28:28 AM

Quote from: BTCW on January 16, 2024, 08:08:45 AM

Code:

hashlib.sha256(bytes.fromhex('e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9' + 'e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9' + '79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798')).hexdigest()

does not give

Code:

da4710964f7852695de2da025290e24af6d8c281de5a0b902b7135fd9fd74d21

It's not supposed to give 0xda47... because that is your tweaked public key. You need to compute the hash above multiplied by generator point to get a new point (pubkey) and then add that to your original public key to get 0xda47...

Code:

t = SHA256(SHA256("TapTweak") | SHA256("TapTweak") | pub_bytes)
pub_tweak = pub + (t * G).

Convert the hash bytes to t in big endian order.
t*G is EC point multiplication (just like you'd get pubkey from a private key)
+ is EC point addition.

So, in Python?

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: BTCW on January 16, 2024, 08:08:45 AM

Code:

hashlib.sha256(bytes.fromhex('e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9' + 'e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9' + '79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798')).hexdigest()

does not give

Code:

da4710964f7852695de2da025290e24af6d8c281de5a0b902b7135fd9fd74d21

It's not supposed to give 0xda47... because that is your tweaked public key. You need to compute the hash above multiplied by generator point to get a new point (pubkey) and then add that to your original public key to get 0xda47...

Code:

t = SHA256(SHA256("TapTweak") | SHA256("TapTweak") | pub_bytes)
pub_tweak = pub + (t * G).

Convert the hash bytes to t in big endian order.
t*G is EC point multiplication (just like you'd get pubkey from a private key)
+ is EC point addition.

BTCW

copper member

Activity: 193

Merit: 255

Click "+Merit" top-right corner

Quote from: pooya87 on January 16, 2024, 07:27:21 AM

Quote from: BTCW on January 16, 2024, 04:33:29 AM

Code:

A tagged hash is: SHA256( SHA256("TapTweak") || 
                              SHA256("F") ||
                              data
                            )

You posted this correctly in OP but changed it here. The second hash is also SHA256 of "TapTweak" (not F).

Code:

SHA256("TapTweak")=e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9

tagged_hash = SHA256(e80f...c5e9 | e80f...c5e9 | 79be...1798)

| is byte concatenation and 79be...1798 is the pubkey.

Gotcha, the only problem is that

Code:

hashlib.sha256(bytes.fromhex('e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9' + 'e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9' + '79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798')).hexdigest()

does not give

Code:

da4710964f7852695de2da025290e24af6d8c281de5a0b902b7135fd9fd74d21

In other words, we cannot yet reproduce the bitcoinutils' method. (Not only bitcoinutils; several libraries give the same result.)

Edit/addition - for reference - and what we aim to reproduce:

Code:

>>>bitcoinutils.keys.PrivateKey.from_wif('KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73sVHnoWn').get_public_key().get_taproot_address().to_string()
>>>bc1pmfr3p9j00pfxjh0zmgp99y8zftmd3s5pmedqhyptwy6lm87hf5sspknck9
>>>bitcoinutils.keys.PrivateKey.from_wif('KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73sVHnoWn').get_public_key().get_taproot_address().to_witness_program()
>>>da4710964f7852695de2da025290e24af6d8c281de5a0b902b7135fd9fd74d21

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: BTCW on January 16, 2024, 04:33:29 AM

Code:

A tagged hash is: SHA256( SHA256("TapTweak") || 
                              SHA256("F") ||
                              data
                            )

You posted this correctly in OP but changed it here. The second hash is also SHA256 of "TapTweak" (not F).

Code:

SHA256("TapTweak")=e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9

tagged_hash = SHA256(e80f...c5e9 | e80f...c5e9 | 79be...1798)

| is byte concatenation and 79be...1798 is the pubkey.

BTCW

copper member

Activity: 193

Merit: 255

Click "+Merit" top-right corner

Quote from: achow101 on January 15, 2024, 08:21:22 PM

Have you tried reading the BIP? https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#constructing-and-spending-taproot-outputs

Many times, yes. It is pretty technical and a tad vague regarding the exact code.

I tried this pseudocode

Code:

 A tagged hash is: SHA256( SHA256("TapTweak") || 
                              SHA256("F") ||
                              data
                            )
    Returns hashlib object (can then use .digest() or hexdigest())

as so:

Code:

taptweek_hash1 = hashlib.sha256('TapTweak'.encode()).hexdigest()
#e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9
taptweek_hash2 = hashlib.sha256('F'.encode()).hexdigest()
#f67ab10ad4e4c53121b6a5fe4da9c10ddee905b978d3788d2723d7bfacbe28a9

tagged_hash = hashlib.sha256(bytes.fromhex('e80fe1639c9ca050e3af1b39c143c63e429cbceb15d940fbb5c5a1f4af57c5e9' + 'f67ab10ad4e4c53121b6a5fe4da9c10ddee905b978d3788d2723d7bfacbe28a9' + '79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798')).hexdigest()

### >> 56d0345a861392e020a0fecdf2c2cffda10b340171f4a31d827eb63e9ccddeac ### NOT GOOD

No luck, yet. How does bitcoinutils do it?

achow101

staff

Activity: 3458

Merit: 6793

Just writing some code

Have you tried reading the BIP? https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#constructing-and-spending-taproot-outputs

BTCW

copper member

Activity: 193

Merit: 255

Click "+Merit" top-right corner

[Addition, the problem was solved down here]

Let's begin with this private key

Code:

0000000000000000000000000000000000000000000000000000000000000001

Using any good old tool, bitcoinutils included, it gives us

Code:

Private key compressed (WIF):                 KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73sVHnoWn
Public key compressed (HEX):                  0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

HASH160 uncompressed:                         91b24bf9f5288532960ac687abb035127b1d28a5
HASH160 compressed:                           751e76e8199196d454941c45d1b3a323f1433bd6

Legacy uncompressed public address (P2PKH):   1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm
Legacy compressed public address (P2PKH):     1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH
Nested segwit public address (P2SH-P2WPKH):   3JvL6Ymt8MVWiCNHC7oWU6nLeHNJKLZGLN
Native segwit public address (P2WPKH):        bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4

I won't go into legacy or nested segwit here, but I would like to mention how we easily derive the native segwit public address using the HASH160 compressed

Code:

bitcoinutils.bech32.encode('bc',0,bytes.fromhex('751e76e8199196d454941c45d1b3a323f1433bd6'))
#bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4

(Likewise, we can produce the segwit bech32 (P2WSH) address by using the single SHA256 of the compressed public key to get bc1qpac4ht6afshdx2tctnhjnetz7u6g3j9zhwwmc4cqkdsa2jumq42qd3drf7; another thread.)

However, here is where I need your help.

I know that the P2TR address corresponding to this private key and its witness program are

Code:

Tweaked Taproot public address (P2TR):        bc1pmfr3p9j00pfxjh0zmgp99y8zftmd3s5pmedqhyptwy6lm87hf5sspknck9
Witness program (HEX):                        da4710964f7852695de2da025290e24af6d8c281de5a0b902b7135fd9fd74d21

since I can quickly arrive at them using bitcoinutils

I can furthermore reproduce and verify it with:

Code:

bitcoinutils.bech32.encode('bc',1,bytes.fromhex('da4710964f7852695de2da025290e24af6d8c281de5a0b902b7135fd9fd74d21'))
#bc1pmfr3p9j00pfxjh0zmgp99y8zftmd3s5pmedqhyptwy6lm87hf5sspknck9

However, I fail to reverse how bitcoilutils does it. Specifically, this function from here that generates the tweaked public key...

Code:

def tagged_hash(data: bytes, tag: str) -> bytes:
    """
    Tagged hashes ensure that hashes used in one context can not be used in another.
    It is used extensively in Taproot

    A tagged hash is: SHA256( SHA256("TapTweak") ||
                              SHA256("TapTweak") ||
                              data
                            )
    """

    tag_digest = hashlib.sha256(tag.encode()).digest()
    return hashlib.sha256(tag_digest + tag_digest + data).digest()

... gives me a headache.

I don't see it. How do you go from the 32-byte x-only public address to that witness program?

In other words, how do I reproduce this transformation in Python (without relying on bitcoinutils as a mystery box library)?

Code:

Input:                                        79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
to 
Output:                                       da4710964f7852695de2da025290e24af6d8c281de5a0b902b7135fd9fd74d21

Need your help! I'm not sure what the library uses as its standard "TapTweak", and I get confused by bitcoinutil's nested (pun intended) code.

How do we use hashlib only and arrive at the same tweaked witness program, and thus the identical P2TR public address? I am very well aware you are allowed to use whatever as "TapTweak". Can we, however, simply reproduce the "library recipe"? What is its standard "TapTweak," and how to arrive at this public address, given the data above, using simple Python?

Many thanks.

Topic: Need help reversing bitcoinutils "tagged_hash" to generate Taproot addresses (Read 124 times)