On the Burning Address of Wormhole Protocol
Long Wen
August 28, 2018
Proof-of-Burn (PoB) mechanism is utilized in Wormhole protocol to exchange Bitcoin Cash (BCH) for Wormhole Cash (WHC). To take the BCH that have been exchanged for WHC out of circulation, Wormhole team has picked a special Bitcoin Cash address for which no one has a corresponding private key of the burning address:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqu08dsyxz98whc.
This is the new form of BCH address, and the corresponding traditional address is: 1111111111111111115KMYP7R278. The hexadecimal representation is:
00–000000000000000000000000000000000071E76C-501B5A27.
According to the traditional address format specification, the first byte “00” is the version number, the last four bytes “501B5A27” are checksum,and the 20 bytes “000000000000000000000000000000000071E76C” in the middle are the 160-bit cryptographic hash.
Note that Wormhole team DOES NOT know any pubkey that satisfies the following equation:
RIPEMD160(SHA256(pubkey))=000000000000000000000000000000000071E76C.
That is, Wormhole team DOES NOT know any public/private key pair corresponding to the burning address. It would be less controversial if the 160-bit all-zero hash value has been chosen as the burning address. The problematic thing is that this specific address has been used prior to the birth of Wormhole protocol, see [1]. Thus the team decided to choose another one as Wormhole’s burning address. There are two more concerns to the selection of burning address besides the obvious restriction that on one is supposed to have any corresponding public/private key pair: ¹ the address should be fresh new and preferably featured with some characteristics unique to Wormhole protocol. After taking all these things into consideration, Wormhole team started with the 160-bit all-zero hash value and looped upward with step-size 1 until an address ended with substring “whc” is obtained according to Bitcoin Cash’s new address encoding rule. The process is demonstrated with codes in Github repository [2]. It is worth mentioning that the native cryptocurrency, XCP, in project Counterparty was also created by PoB mechanism [3, 4].
Is the burning address selected via the aforementioned process actually a valid Bitcoin Cash address? Or is there any pubkey value satisfying the above equation? The answer is yes. The hash function utilized in the generation of Bitcoin Cash address RIPEMD160(SHA256(pubkey)) maps pubkey to a 160-bit hash value. The order of the elliptic curve points’ addition group, based on elliptic curve secp256k1, is:
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.
Likewise, the number of possible values for private key is n≈2²⁵⁶. (Without loss of generality, we do not discuss several rare cases where some possible values are not suitable candidate for private key, e.g. when private key is 0 or 1 , the corresponding public key would be the point at infinity or the base point, respectively.) Due to the pairwise relationship between public key and private key, the number of possible values for public key is also n ≈ 2²⁵⁶. Thus, the hash function RIPEMD160(SHA256(pubkey)) can be roughly regarded as a mapping: {0,1}²⁵⁶ → {0,1}¹⁶⁰. As 2²⁵⁶/2¹⁶⁰ = 2⁹⁶and in the Random Oracle Model (ROM) the output distribution of hash function RIPEMD160(SHA256(pubkey)) can be regarded as a uniform distribution over {0,1}¹⁶⁰, then following the pigeonhole principle we have:
∀h ∈ {0, 1}¹⁶⁰, ||{pubkey : RIPEMD160(SHA256(pubkey)) = h}|| ≈ 2⁹⁶,
where || · || denotes the number of elements in a set. We can then draw a conclusion that for any 160-bit hash value, there are about 2⁹⁶ public key values making the address, which encodes the hash value, a valid address. Or in other words, there is at least one public/private key pair corresponding to Wormhole’s burning address and the burning address is indeed a valid Bitcoin Cash address.
Two questions arise when arguing the unidirectionality of the burning address: 1): How can one con rm that Wormhole team does not possess any pubic/private key pair related to the burning address? 2): Is it possible for any attacker to nd any pubic/private key pair related to the address and steal the coins as there are roughly 2⁹⁶ possible private key values that can spend the coins?
The 160-bit hash value encoded in the burning address is “000000000000000000000000000000000071E76C”. It does not require a good insight to notice that there are 137 leading zeros in the hash value. To elaborately construct the address, Wormhole team need to iterate through massive amounts of possible values of pubkey until the leftmost 137 bits of RIPEMD160(SHA256(pubkey)) are all zero. A careful reader would have found the similarity between the mentioned process and the puzzle solving process in the PoW mechanism: exhaustive search as many values as possible to obtain a hash value located in a tiny region of the target domain. Take the block at height 534965 (refer to [5]) as an example, the block hash in hexadecimal representation is
0000000000000000000a5c2378be75b246dae8932e3679f 3b8542173c1015547,
There are 76-bit leading zeros. According to the PoW mechanism, the miners need to complete expec- tantly about 2⁷⁶ computation in order to construct the block. In a similar way, Wormhole team needs to nish about 2¹⁷³ computation in order to successfully construct the burning address through hash function RIPEMD160(SHA256(pubkey)). This level of computation is way beyond the hashing power of the whole BCH network, even far beyond the sum of hashing powers of all cryptocurrency networks employing the PoW mechanism and is apparently impractical currently. Thus, the first concern related to the unidirectionality of burning address can be clarified: Wormhole team does not possess any public/private key pair related to the burning address.
Deducing pubkey according to the 160-bit hash value encoded in the burning address can be expressed with cryptographic terms: break the preimage resistant property of hash function RIPEMD160(SHA256(·)). This kind of attack would require approximate 2¹⁶⁰ computation. The massive computation resources required to complete the task are far beyond mankind’s current ability and is impractical even in the near future (We do not discuss the fancy quantum computing here). If there is anyone who can successfully launch the attack, then the mighty attacker can attack any account within Bitcoin Cash network. Under such circumstance, the following account with 270,000 coins should be more attractive: referring to [6]:
bitcoincash:qp0k6fs6q2hzmpyps3vtwmpx80j9w0r0acmp8l6e9v.
Thus we can clarify the second concern by now: it is impractical to deduce the preimage pubkey.
The last question: is it possible that birthday attack can speed up the whole attack procedure? As all kinds of introduction level cryptographic materials have mentioned that 160-bit hash value can provide only 80-bit security. Is it possible that 2⁸⁰ computation is enough to accomplish the attack? The answer is negative, birthday attack is not suitable in this context.
When discussing the security of hash function, one would normally refer to three properties: preimage resistance/one-way function, second-preimage resistance and collision resistance:
- preimage resistance: given hash value h, it’s impractical to obtain message m s.t. hash(m) = h.
- second-preimage resistance: given m1, it’s impractical to obtain m2 s.t. hash(m2) = hash(m1).
- collision resistance: it’s impractical to nd two messages m1 and m2 s.t. hash(m1) = hash(m2).
The attacker’s autonomy is gradually enhanced in the three scenarios above, meaning the cost to accomplish the corresponding attack is gradually declining. Or one can reasoning backward, if a hash function is collision resistant, one can prove that the hash function is also second-preimage resistant as well as preimage resistant through reduction. However, a successful collision attack against a hash function does not mean the attacker can break the second-preimage resistant property, let alone the preimage resistant property. For example, although Steven et al. have demonstrated actual collision attack against SHA-1 at CRYPTO 2017 [7], the one-way property of SHA-1 is not compromised as the current best preimage attack can only target truncated SHA-1 and demands impractical computing resources [8]. Besides, the security of HMAC based on SHA-1 is still intact [9].
The security of different application scenarios relies on different security properties of hash function. The security of Merkle tree used in Bitocoin Cash block construction, e.g. the computation of Merkle root hash, rely on the collision resistant property of SHA256(SHA256(·)). Yet, during the generation of Bitcoin Cash address, it is the preimage resistant property of RIPEMD160(SHA256(·)) that provides the security foundation.
Birthday attack² simply gives the security boundary of hash function in collision attack context: 160-bit hash function output can provide about 80-bit security strength. But as previously mentioned, the security of Worm- hole’s burning address is secured by the preimage resistant property of RIPEMD160(SHA256(·)). Currently, there is no better attack than exhaustive search to break the preimage resistant property of RIPEMD160(SHA256(·)). Thus, if anyone wants to deduce a public key value according to the 160-bit hash value encoded in the burning address, it would require about 2¹⁶⁰ computation, which is impractical. On the other hand, although SHA-1 and RIPEMD-160 both produce 160-bit hash value and there is some practical collision against SHA-1, there is only theoretic collision attack against RIPEMD-160, refer to the most recent result from ASIACRYPT 2017 [10]. A recent proposed preimage attack against RIPEMD-160 in [11] is also quite theoretical. Thus, currently and in a foreseeable future, there is no need to worry about the preimage resistant property of RIPEMD160(SHA256(·)).
To sum up, we have described the selection process of Wormhole’s burning address, the validation of the burning address and the related security consideration. Also, we clarify that Wormhole team does not possess any public/private key pair related to the burning address by estimating the impractical computation resources required to break the statement.
Note
References
[1] BTC.com. Bitcoin Cash Address: 0000000000000000000000000000000000000000.
https://bch.btc.com/1111111111111111111114oLvT2
[2] Github Project. genburn. Codes for Generating Wormhole’s Burn Address.
https://github.com/copernet/genburn
[3] Blockchain.com. XCP Proof-of-Burn Address.
https://www.blockchain.com/btc/address/1CounterpartyXXXXXXXXXXXXXXXUWLpVr
[4] Counterparty blog: Why Proof-of-Burn. https://counterparty.io/news/why-proof-of-burn/
[5] BTC.com. Bitcoin Cash Block Height 534965.
https://bch.btc.com/0000000000000000007ab116ea2dd1c7031b01895daa16e27d78986c141b888e
[6] BTC.com. Bitcoin Cash Address: qp0k6fs6q2hzmpyps3vtwmpx80j9w0r0acmp8l6e9v. https://bch.btc.com/19hZx234vNtLazfx5J2bxHsiWEmeYE8a7k.
[7] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov: The First Collision for Full SHA-1. CRYPTO (1) 2017: 570–596. https://shattered.io/static/shattered.pdf
[8] Thomas Espitau, Pierre-Alain Fouque, Pierre Karpman: Higher-Order Di fierential Meet-in-The-Middle Preimage Attacks on SHA-1 and BLAKE. IACR Cryptology ePrint Archive 2015: 515 (2015). https://eprint.iacr.org/2015/515.pdf
[9] Mihir Bellare: New Proofs for NMAC and HMAC: Security without Collision Resistance. J. Cryptology 28(4): 844–878 (2015). https://cseweb.ucsd.edu/~mihir/papers/hmac-new.pdf
[10] Fukang Liu, Florian Mendel, Gaoli Wang: Collisions and Semi-Free-Start Collisions for Round-Reduced RIPEMD-160. ASIACRYPT (1) 2017: 158–186. https://eprint.iacr.org/2017/800.pdf
[11] Yanzhao Shen, Gaoli Wang: Improved Preimage Attacks on RIPEMD-160 and HAS-160. KSII TRANS- ACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 12, NO. 2, 2018. http://www.itiis.org/digital-library/manuscript/file/1926/TIIS+Vol+12,+No+2-11.pdf
