Algorithm for yPub to Address?

[EAWF]

Does someone have, or can you point me to a definitive resource containing the algorithm for the start to finish ypub to payment address derivation procedure?

Thanks in advance for your prompt response.

[nc50lc]

Wiki (from private/public key to address): Technical background of version 1 Bitcoin addresses
BIP-0032 (from extended public key to public keys): https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

Tool for testing: https://gobittest.appspot.com/Address

[pooya87]

Wiki (from private/public key to address): Technical background of version 1 Bitcoin addresses
Tool for testing: https://gobittest.appspot.com/Address

these links only cover legacy addresses and not anything SegWit related which is the case with extended keys starting with ypub. for that first is BIP49[1] for specifications then BIP32 that you already posted, also SLIP132 for a list of different version bytes[2] and finally to read SegWit related BIPs to understand how to derive each address type from the public keys gotten from the extended key[3][4]. this link also helps[5]


[1] https://github.com/bitcoin/bips/blob/master/bip-0049.mediawiki
[2] https://github.com/satoshilabs/slips/blob/master/slip-0132.md
[3] https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki
[4] https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki
[5] https://bitcoincore.org/en/segwit_wallet_dev/

[EAWF]

If it were that easy, I wouldn't have asked the question in the first place as I've been banging my head against the Internet for over a year trying to figure this algorithm out.

To help your understanding, the word Algorithm means "a step by step procedure to solve a problem from the beginning to the end," and not, look here and here and here and here and try to figure it out. 

So here's the challenge: Start with the Account Extended Public Key (ypub) and a child index, and describe the complete process required to derive a payment address that equals the payment address listed on Ian's page.

How about I make the challenge interesting and offer $250 USD in BTC at the Bitstamp current market price based on the date that the correct and complete algorithm is submitted here?

However, three rules:
1. The algorithm must be in pure pseudocode (a text based explanation) that an average middle or high-schooler would understand.
2. References to functions such as Base58 encoding/decoding, hexadecimal/binary conversions, RIPEMD-160, SHA-256, SHA-512, as well as string parsing are acceptable.
3. In the case of two or more correct answers arriving, the winner will be the best, most usable algorithm, and the tie-breaker will be the timestamp of the submission.

Here are the test vectors that I will use as proof that the algorithm is correct:
1. Access Ian Coleman's BIP36 Mnemonic Generator: https://github.com/iancoleman/bip39 and enter the mnemonic phrase:

Code:

abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon about

2. Select the BIP49 tab.
3. Take note of the Account Extended Public Key section. This will be the first input to the algorithm, the account-level extended public key that would be exported from a Mycelium(Android) wallet, for example.
4. The second input to the algorithm is found in the Derived Addresses section, and for an example, you would probably want to test the algorithm with the first derivation path listed: m/49'/0'/0'/0/0() , so we're looking to derive the payment address listed on that line, the child index of zero.

I'm looking forward to the correct answer. I'm told by many that this is a "piece of cake," so it should be easy BTC for someone.

Thanks in advance for your time, consideration and competition.

[pooya87]

If it were that easy, I wouldn't have asked the question in the first place as I've been banging my head against the Internet for over a year trying to figure this algorithm out.

To help your understanding, the word Algorithm means "a step by step procedure to solve a problem from the beginning to the end," and not, look here and here and here and here and try to figure it out. 

well the problem is that the algorithm is complicated and long to explain step by step. and you didn't ask for that kind of explanation in your initial question which is why the type of response you've gotten is "look here and there" additionally these are resources that explain the algorithm a lot better than we can do. usually you have to first look at them then ask about only parts that you don't get not from scratch.

How about I make the challenge interesting and offer $250 USD in BTC at the Bitstamp current market price based on the date that the correct and complete algorithm is submitted here?

alright, challenge accepted! LOL

(you can skip to step 4.1 if you don't have the mnemonic)
1. using PBKDF2 (RFC8018) derive the BIP32 entropy from the mnemonic

Code:

byte[] pass = UTF8_Decode(mnemonic)
byte[] salt = UTF8_Decode("mnemonic" + passphrase)
Bip32_entropy = PBDKF2.GetBytes(pass, salt, c=2048, dkLen=64, PRF=HMACSHA512)

2. use the entropy to get the private key and chain code for the master private key

Code:

byte[] ba512 = HMACSHA512(data=entropy, key=UTF8_Decode("Bitcoin seed"))
byt[] firstHalf = ba512.SubArray(startIndex=0, count=32)
byt[] secondHalf = ba512.SubArray(startIndex=32, count=32)
int256 k = firstHalf.ToInt(BigEndian=true)
if (k == 0  OR k > Secp256k1.Order) 
   fail;
else
   continue;
byte[] privateKey = firstHalf 
byte[] chainCode = secondHalf
int depth = 0
ParentFingerPrint = {0,0,0,0}
ChildNumber = {0,0,0,0}

3. choose a desired path
m/49'/0'/0'/0/0

4. derive child keys step by step for each index in the path (`|` is concatination)
- we already have m
- 49' (index=49 + 2^31)
- 0' (index=0 + 2^31)
- 0' (index=0 + 2^31)
- 0 (index=0)
loop for each index above:

Code:

if(index >  2^31)
    byte[] dataToHash = 0x00 | privateKey | (index).ToBytes
else
    byte[] pubKeyBytes = privateKey.ToPublicKey.TobytesCompressed
    byte[] dataToHash = pubKeyBytes | (index).ToBytes

byte[] ba512 = HMACSHA512(data=dataToHash, key=chainCode)
byt[] firstHalf = ba512.SubArray(startIndex=0, count=32)
byt[] secondHalf = ba512.SubArray(startIndex=32, count=32)
int256 k = privateKey.ToInt
k = k + firstHalf.ToInt(BigEndian=true) MOD Secp256k1.Order
if (k == 0) 
   fail;
else
   continue;
byte[] privateKey = firstHalf 
byte[] chainCode = secondHalf
int depth =  depth  + 1

4.1. the case for not having the mnemonic and only having the extended public key at index m/49'/0'/0'/0 (bold part above) and wanting to derive the /0 and /1 and /2 etc public keys

Code:

byte[] ba78 = Base58WithChecksum.Decode_Check_and_removeChecksum(ypubString)
byte[] ver = ba78.SubArray(0,4)
check(ver == SLIP0132_version)
byte depth = ba78.SubArray(4,1)
check(depth == depthOfTheCurrentIndex)
byte[] pubKeyBytes = ba78.SubArray(45, 33)
check(pubKeyBytes[0] != 0)

for final index:
- 0

Code:

if(index >  2^31)
    fail;
else
    byte[] dataToHash = pubKeyBytes | (index).ToBytes

byte[] ba512 = HMACSHA512(data=dataToHash, key=chainCode)
byt[] firstHalf = ba512.SubArray(startIndex=0, count=32)
EllipticCurvePoint p = (firstHalf.ToInt(BigEndian=true) * Secp256k1.Generator) + (pubKeyBytes.ToEllipticCurvePoint)

note: `*` and `+` in last line above are point multiplication and point addition on an elliptic curve!

5. getting public key

Code:

Check(p is on Secp256k1 curve)
publicKey pub = p

6. getting the address:

Code:

keyhash = RIPEMD160(SHA256(pub))
redeemScript = OP_0 <keyhash>
scriptPubKey = OP_HASH160 RIPEMD160(SHA256(redeemScript)) OP_EQUAL

checksum = SHA256(SHA256(0x05 | RIPEMD160(SHA256(redeemScript)))).SubArray(0,4)
address = Base58Encode(0x05 | RIPEMD160(SHA256(redeemScript)) | checksum)

example:

Code:

pub = 039b3b694b8fc5b5e07fb069c783cac754f5d38c3e08bed1960e31fdb1dda35c24
keyhash = f990679acafe25c27615373b40bf22446d24ff44
redeemScript = 0014f990679acafe25c27615373b40bf22446d24ff44
scriptPubKey = a9143fb6e95812e57bb4691f9a4a628862a61a4f769b87

checksum = ca97ac44
address = Base58Encode(053fb6e95812e57bb4691f9a4a628862a61a4f769bca97ac44) = 37VucYSaXLCAsxYyAPfbSi9eh4iEcbShgf

good luck

[btc_enigma]

Just try any of the below two libraries. They have support for recognizing and deriving addresses from segwit xpubs

https://github.com/dan-da/hd-wallet-derive
https://github.com/shivaenigma/pycoin

[EAWF]

OK, so, the "answers" have convinced me that no one is interested in the reward, so I'm cancelling the reward offer as of this posting. Pooya87 came the closest as (s)he provided the correct formulae, even though it was camouflaged in a lot of other stuff. BUT, since (s)he failed to provide it in the algorithmic form, it's a loser due to a simple failure to read and follow directions.

“Programmers are not to be measured by their ingenuity and their logic but by the completeness of their case analysis.” - Alan J. Perlis

Thanks to all who participated in this exercise. I'll leave some thoughts and quotes for your consideration and education:

When your customer chooses to put their business online it's a huge risk because they see all the hacks and breaches.  It's a requirement of your program to keep their data safe & secure. For insurance against possible bugs and holes in the code, your code MUST be readable and understandable.

Maybe it will help to think about it this way:
Satoshi didn't just start writing code. The white paper came first. In effect, the white paper is the algorithm for the original bitcoin code.

“Some of the best programming is done on paper, really. Putting it into the computer is just a minor detail.” - Max Kanat-Alexander

“Progress is possible only if we train ourselves to think about programs without thinking of them as pieces of executable code. ” - Edsger W. Dijkstra

“We are looking at a society increasingly dependent on machines, yet decreasingly capable of making or even using them effectively.” - Douglas Rushkoff

To the respondents who mentioned or inferred the word, "library" in their answer:

The efficiency and speed of the program is directly proportionate to the amount of lines it has to process within the code. Fill a program with bloated libraries, the program WILL run slower.

“We see a lot of feature-driven product design in which the cost of features is not properly accounted. Features can have a negative value to customers because they make the products more difficult to understand and use. We are finding that people like products that just work. It turns out that designs that just work are much harder to produce that designs that assemble long lists of features.”  - Douglas Crockford

“Any fool can write code that a computer can understand. Good programmers write code that humans can understand.” - Martin Fowler

Spaghetti code is not "readable" code.

“Object-oriented programming offers a sustainable way to write spaghetti code. It lets you accrete programs as a series of patches.” - Paul Graham

“But while you can always write 'spaghetti code' in a procedural language, object-oriented languages used poorly can add meatballs to your spaghetti.” - Andrew Hunt

[pooya87]

OK, so, the "answers" have convinced me that no one is interested in the reward, so I'm cancelling the reward offer as of this posting. Pooya87 came the closest as (s)he provided the correct formulae, even though it was camouflaged in a lot of other stuff.

it is probably because your account is brand new and you didn't escrow the "reward". i only replied because i didn't care and i would have replied the same way even if you never mentioned "reward" that is why i loled

although i am wondering why you said it is "camouflaged in a lot of other stuff"! what other stuff? it is a literal translation from my own implementation of BIP32 to pseudo-code as you asked. step 4.1: https://i.imgur.com/i8NpSwq.jpg

Fill a program with bloated libraries, the program WILL run slower.

i don't think so. a library is not something you "load" like an application to take time, it is just a set of codes that your program accesses. if you want a certain set of classes, then it will only access those when you run your application. i haven't experienced any speed penalties by adding libraries to my projects ever!

[EAWF]

1) My bad on the reward. I guess I'm just old-fashioned and used to a world where, if someone makes a promise, or an offer like that, they stand by it, and don't go running to mommy or daddy, or a lawyer, or an escrow holder to weasel out of a deal. I wrote it, I stood by it, and no one was able to follow the terms of the offer.

2) Camouflage: Where you tripped was that you didn't read the offer/directions and follow them.
I asked for an algorithm to begin with the exported account-level extended public key, and you began with the master private key/seed of the wallet.
I'm not looking at the big picture of a creating a wallet. I'm focusing in from the perspective of someone who already owns an HD wallet and want's to trade products and services for bitcoin as a business, and have the remittances show up automatically IN their wallet, under a separate account. 
As you probably already know, HD supported wallets have that fun little "multiple account" feature that allows a seller to have a personal account (i.e. Account 0) and once it's funded, they can open a second account (i.e. Account 1) that can be used to keep sales remittances separated from their personal bitcoin, but the wallet can be used to spend from either account, or even transfer from one account to the other if they so wish.
With that wallet, Merchant's CAN easily export the "CoinType, MainNet, Account-Level" extended public key for use on unrelated servers and have the funds arrive in the HD Wallet's account directly.
I'm building a small toolbox of algorithms (Bitcoin-Merchants-Toolbox) that cover deriving out a "Wallet/CoinType/MainNet/Account/Payment-Address" level public key from the exported xpub, ypub, or zpub, that can be hard-coded into a simple function that will return a payment address to be used on for the customer's bitcoin payment.
Examples:

Code:

getAddressX(index)→ Payment Address beginning with "1"
getAddressY(index)→ Payment Address beginning with "3"
getAddressZ(index)→ Payment Address beginning with "bc1"

Merchant's CAN'T do this easily.

3) Libraries: OK, you got me started so ...
<rant>
Let's take bitcoinjs-lib for an example. If you are using it on a web page, then you have two options: <script>embedded js code</script> OR <script src="bitcoinjs-lib.js"></script> in the header. The former method is actually faster because the latter requires another download call to pull in the script from the server.
The smallest version of BitcoinJS-Lib is bitcoinjs-min.js and tops out at 215Kb. If you're only using one or two functions that consist of say 1 or 2Kb of code, then effectively you've wasted time and bandwidth downloading bytes that you didn't really need to get your job accomplished. Not a problem if you get unlimited bandwidth from your server provider, but if the code will be used on a popular site, those bandwidth rates are going to add up to big money which is saved by writing slimmed down(concise) code.
Not to mention that it would take you days of following the spaghetti code to be able to COMPLETELY VERIFY the code as bug-free and thereby trust-able. Hell, I don't even trust the code that *I* write, must less ask YOU to trust what I write.
</rant>

Make sense?

[EAWF]

In case anyone is interested, i have the following Git Repository running to document the algorithm for this.

[url src="https://github.com/EAWF/Bitcoin-Merchants-Toolbox"]Bitcoin Merchants Toolbox[/url]