Bitcoin Forum

I thought about how we could make a bitcoin address memorable.
Initially I thought about encoding a bitcoin address in base 2048, and reusing dictionaries of BIP39. (mnemonic)

However, a public key is 160 bit and doing so would require LOG(2^60, 2048)=15 words.
It is still hard to remember a public address.

Another way of doing so is publishing the address on the blockchain (in the output of a tx), and only remember : Block Height + Tx Index in the block + TxOut index

Such information can be encoded in 4 words with the help of a BIP39. (assuming height of 350 000, 10 000 tx per block, and 10 outputs by txout)

I intend to include that feature in the wallet I am developing, are you seeing any downside or alternative ? (Except a fork happening that would modify the address)

Only after enough confirmations.

I would by this short domain: "adr.ss"  (.ss is tld of south sudan)
Then I would use it to remember bitcoin addresses adr.ss/cakir redirects to my btc address etc.

Basically this idea existed more or less before in the form of the ill fated 'firstbits'; I consider this proposal to be ill-advised for the same reasons.

Addresses should generally not be reused. Reusing addresses harms the your security and privacy as well as the privacy of all Bitcoin users. Extensive address reuse contributes to systemic risks which endangers the system (what happens when RPG wielding ninjas show up at mining farms with demands to not mine transactions belonging to their enemies?  If regular transactions are conducted so that they are indistinguishable to their author's enemies we never need to find out). While the community may not go so far as to prohibit reuse, building infrastructure that rewards it is not a good plan.

These short addresses are immediately subject to lookalike attacks-- a popular address is "wolf larceny tape butter" ... great, I go and create "golf larceny tape butter", "wolf larceny ape butter", "wolf larceny tape butler" and so on... I spam these clones out in various places or just trust human error to guide things along, and now I'm receiving funds from other people. We don't even need an attacker here, all outputs are constantly being assigned addresses, the space of working addresses dense-- instead of the very intentionally sparse case which we have with addresses today where its nearly impossible to send to an incorrectly entered address.

As you note, the security here is totally undermined by a reorg. So beyond chance reorgs breaking things for people and causing their funds to go off to be lost in space, now there is a great incentive to reorg that didn't exist before. (there also is some fun nuisance perversion like miners selling high value vanity positions in blocks with this particular scheme; spamming up the chain to make sure to register the really goods one, sometimes requiring large indexes.).

One could not resolve these addresses without a copy of the entire blockchain or at least a forever growing unprunable database (as with firstbits) which would need to be accessable to each and every wallet. In practice most people would depend on centralized services to resolve these (as  they did with firstbits), and in practice the services will eventually return wrong results, even without intentional fraud (as with firstbits).  Of course, any of these services would be prime targets for compromise; a well timed replacement could redirect huge flows of funds.

This also requires a separate registration step, which reduces the scalability of the system due to additional overhead, and makes the system less instant gratification. You end up with something where you have to pay fees to establish an 'identity' just to receive funds to pay the fees with. Necessitating multiple use modes.

Less critically the use of a particular fixed wordlist is culture/language laden and has seemed to be somewhat problematic for BIP39; though I mention this only in passing.

I agree about privacy concern. But right now, we have no way of printing a payment destination on an unpowered and unconnected device (aka paper).
The exception is stealth addresses which I have great hope once we resolve the OP_RETURN problem.

What about publishing the stealth address on the blockchain instead of a Bitcoin Address ? This would solve your concern of privacy while still allowing to be remembered in a few words.

This is not the usage I am envisioning.
I don't want to use such address to be recognized. My use case is more between two persons wanting to exchange bitcoin without the need of a physical stuff that bear the address.
-"where to I pay your ?"
-"Pay me to : Red, Car, Building, Trigger"
For human recognition, encoding an address on an identicon is more appropriate. In fact, I'm also looking out how I can make an identicon safe from lookalike attacks.

Also, BIP39 lists are created by making it hard to confuse between two words. What is important in this case is not the string metric, but the "sound" metric of the words. Assuming words were wisely selected in bip39 dictionaries, we should be relatively safe.

Well, the only information that gives problems is the Transaction Index in the block.
If I can find another feature for identifying the address, a partial merkel tree would be enough for solving your issue about the need of having the whole blockchain.
The client would just rely on untrusted third party services (or by connecting to the bitcoin network) and just check that address given the words are correct.

I don't want any registration needed, so I won't do that.

Thanks, but I don't want any registration needed.

There is a whole host of separate problems there, including needing to witness the whole blockchain to scan for payments (it breaks SPV and/or makes you again depend on a central server)

The usecase you're describing is addressed by the payment protocol.  You give people a payment uri.

You cannot generally. Look alikes can be ground. There is a nice example of this for openssl picture fingprints that I'm having trouble finding.

There are plenty of lookalke/soundalike/mean-alike words in it e.g. [choice, choose], [drip, script, trip], [risk, brisk], [load, road] (just picked single words at random and found the first obvious matches; what-- no one ever confuses "r" and "l" sounds?).

That would, in fact, be an improvement over firstbits.

The process you described fundamentally requires registration. Before I can give you a short address I must have registered one in the blockchain.

My bad, I thought you were talking about a registration in a centralized service. (record off chain)

Depending on another server for scanning is not really a problem for my case. I don't want to make an autonomous wallet.
My main concern is that all information needed for a "brain address" is in the blockchain, and verifiable by devices without direct access to the whole blockchain.
I assume that the device depends on an untrusted server. (preferably another bitcoin node, at worse a third party server)

If Bob gives its "brain address" to Alice, Alice does not need the blockchain for fetching the full address, she can ask the resolution of it to an untrusted server, with proof.
If I find a good feature set for encoding the address, then Alice might be a simple SPV node.
The proof would be : [merkleblock + tx].

If I don't find a better feature set and stick with [height+tx index+txout index], Alice would depends on a server, but do not need to trust it. She is still able to verify the fetched address is not replaced/faked/bugged by herself.
In such case, my server would return the transaction + all transaction ids in the block + block header.
The proof would be : [blockheader + transaction ids in the block + tx].

I would prefer the first solution though... will sleep on that, thanks for the input !

How about adding a checksum in the encoded data ? Having the wrong word would not result in user's fund losses.

Couldn't we just use the existing DNS for this purpose?
Let's connect whatever public address to your email address!

Then people are able to pay to your email address instead.
It's also much easier to change the underlying public address into a new one.

i think someone should start a service where someone can store their bitcoin address online and get a personalized short link that they can open anywhere and get the address they stored there

That's called DNS, I just proposed it.
It already exist.

To make it decentralized, integrate the DNS into bitcoin, or use another alt (namecoin?)

No, I want someone to just take whatever address and find a way to memorize it easily, without registration except on the blockchain.
If you use DNS, then you use a payment address. (BIP70)
I don't want any data stored somewhere else than in the blockchain. (nor alt chain)

Same problem, out of blockchain registration, not something I want.

It is not. People would need to depends on a central trusted service instead of just consulting the blockchain. (Giving rise to attack/bugs of address replacement that gmaxwell talked about above)

Those with photographic memory can remember anything easily.

Can you offer Bitcoin memorization as a free service?

https://bitcointalk.org/index.php?topic=948359.msg10383498#msg10383498 (https://bitcointalk.org/index.php?topic=948359.msg10383498#msg10383498)

If someone wants to remember its priv key he can remember a few words that will lead to it and I think your proposition poses problems when we can get around not remembering our public key.

I have to agree with gmaxwell address reuse should be discouraged.  Yes I know people will do it anyways but I would not go out of my way to make it easier.  Firstbits was a valid system and easier to adopt/use that what you propose but it was still a bad idea and I am glad adoption died off. 

The major problem is that re-use reduces the privacy not just of the person who re-uses their addresses but for everyone else because it makes it easier to track transactions.  If all keys were used only once it would make graph mapping the blockchain much more difficult. If you want to enhance your wallet how about reducing the information leak from change addresses.  In theory any output can be the change but as practice most wallets implement this so poorly it becomes trivial to determine the change output.  There is a lot that can be done to make transactions more opaque so I would consider that an area to improve.

It isn't just wallet designers however.  It requires effort from all parties.  It would be useful if services provided the option for a user to provide an extended pubkey.  For example since people love change addresses a forum like this could have a field on the profile where the user provides an extended pubkey.  The site would not display the address publicly but would compute the next address from the extended pubkey and display that.  When a transaction is detected it would increment and display the next address.  Similarly mining pools could in a similar fashion send all user payments to a new address by just having the user provide an extendedpubkey instead of a static address.

Except you can't easily remember as 4 english words.

Like I said, an alternative is to publish a stealth address on the blockchain and referencing it by 4 words. It fix completely every of your complains.
I need a solution that work can be printed on an object or in the head without central trust. So I don't consider ext pubkey usable in my scenario.

Also my scheme is nothing like Firstbits, because it does not depends on centralized trust.

If you want to print an address on paper/phone shell/tee-shirt, you have three way of achieving that : Either a regular bitcoin address, either depending on a service with centralized trust weak to replacement (like payment url BIP70), either stealth addresses. Sadly there is no other alternatives.
We can scream all we want about privacy leaking, there is a specific problem and I see only two solution (but stealth address are not widely supported and very limiting because of OP_RETURN limit), privacy leaks are worth it for my users.
Telling them "don't do that because you put others at risk" is not an option. If this is the only downside, I'll implement my scheme with a fixed Bitcoin address and just wait better support for stealth address + a lift of OP_RETURN.

remebering an bitcoin address is good but  what will you do if you made a mistake will sending some bits
to it ? I think you can just create a simple email or text file in you computer and save it simply there .

FirstBits didn't require centralized trust.  Anyone could using the algorithm and a copy of the blockchain determine the firstbits of an address or the address from a firstbits.  It is no more or less centralized then the scheme you proposed.  It is more efficient but no more secure.  If you compute it yourself it is secure and if you don't you are trusting the person who computes it.


Well that isn't the only downside. What happens when someone who uses a wallet that doesn't support this scheme sees the mnemonic and wants to send funds to it.  How are they going to convert "yellow happy dog runner" into the proper address?  Well they could download some additional open source software, make sure it is legit, and use that along with the blockchain to compute the proper address.  They "could" do that but lets be honest they won't.  We already they won't because they could have decoded firstbit addresses on their own but they didn't.  What they will probably do is google "name-of-your-scheme" and very likely find a dishonest site which will decode "yellow happy dog runner" to an incorrect address owned by the site operator.  Maybe they even show the wrong transaction in the blockchain with a link to blockchain.info to make it look more legit.  They send funds to the address they think is right, the money is gone and your user and the sender are both confused as to what happened.

So yes if 100% of wallets natively supported your scheme it wouldn't require any third party trust (beyond trusting the wallet developer which is implicit to some degree).  Of course if 100% of wallets supported firstbits it also wouldn't require third party trust but we know how that turned out.

Indeed, I messed up with another service. By the way "1kk5k" is hardly memorizable, using words should be better.

Such argument apply to any new products.
"X will not be used by all, so you should not bother. proof, look at Y !", then we should stop innovating altogether.
The thing is, I have already people ready to use it, it takes me 1H to code in the wallet I am developping. So I'll just throw that out and see how it goes.
If wallet developers think it is a good idea, they'll decide by themselves.

The difference between 1kk5K and "Car Yellow Dog Building" is big for a user. (btw, I did not managed to make firstbits work for my address :( )
However I don't find the implementation details of firstbit, do you have a link ? I would like to know how they encoded the address reference.

In practice it did, because it required an unprunable copy of the whole blockchain to do anything with it. So everyone used it with various services and eventually the services returned inconsistent results (due to differently mishandling reorgs).

There are lots of things that can be done which are merely decentralization theater, sometimes because the design obfuscates the hidden decentralization, in other times because they're  not practical without it.  I'd say that was true for firstbits in practice, its true for the scheme here too though I believe it could be improved to be SPV-ish; but that still leaves the other downsides.

I found a way to fix all the problems you pointed out.

Having a SPV proof
I will encode a location in the blockchain in the following way :
[Height]-[PathToLeaf]-[TxOut index] (I'll call such information a "blockchain address")

[PathToLeaf] will be a bit array describing how to go from the merkle root down to the leaf representing the transaction. (1 for go right, 0 for go left)
This has the nice effect to be shorter than the [Tx Index] I thought about, but also to fit in a classical Partial Merkel Tree. (Log(N;2) bit on the transaction count of the block)

Fixing Address Reuse
If the blockchain address references a TxOut that is not OP_RETURN, then it it referencing the ScriptPubKey. (do not fix address reuse)
If the blockchain address references a TxOut that is a OP_RETURN, then, it checks if the content is a Bitcoin Payment URL. (fix the address reuse problem, because if it is BIP70, a new address will be evaluated each time)

Preventing user error caused by similar words
We can append a checksum at the end of the the "blockchain address" before encoding it in a "brain address" such as:
Brain Address = ([height]-[PathToLeaf]-[TxOut index]) + Hash([height]-[PathToLeaf]-[TxOut index])[0]
Now if the user mistake between two words, there will be no risk of sending funds to the wrong place.

Result: All blockchain reference and address could be represented in 3 or 4 easy to remember words, only with the blockchain.

This fix all shortcoming of firstbits :

• it remove any need of trust relationship with a "brain address" web service.
• payment destinations are memorizable
• A SPV client only need a partial merkle tree for checking the result
• No fixed address

Why would you want to remember a Bitcoin address at all? That's a mistake.

1. We got software to do that for us.
2. You should avoid reusing addresses as much as possible.

Let me quote myself from another thread:

As I said, I fixed the address reuse problem, so it should not be a concern.

The reason why I want to do that is kinda the same reason why most people memorize their own mobile phone number.
You can't have forgotten it at home when someone ask for it.

It sounds like your scheme (in the BIP70 case) is simply a URL shortener, except that in some cases it will end up being more of a URL lengthener.... remembering a few random English words seems harder to me than simply remembering a domain name that one creates for that purpose.


At least one online wallet does this, for example if you'd like to send me a tip, visit here: https://greenaddress.it/pay/GAMiQ3yzZFD6djdqpYo4YGdRHrMot/ (https://greenaddress.it/pay/GAMiQ3yzZFD6djdqpYo4YGdRHrMot/) (they have only my xpub, assuming of course that you trust their client software isn't malware).

Except you can't expect average Joe to manage his own domain name, and host his own payment server.
Average Joe can create an account on a third party payment server though.
But such server : either provide an url that can't be remembered and easily spelled. (http://payment.com/u/dzopUDZiziK)
Either use the user's name (http://payment.com/u/toto), but in such case, you can easily get misspell the user name or domain, resulting to money sent to someone else.

My scheme do works whatever how a payment url is created.

That's kind of the point though. If Joe can't run his own payment server (and wants to avoid address re-use), then he's stuck with a centralized solution anyways. And if he's stuck being centralized, there doesn't seem to be much reason to use the blockchain to look up some account ID if the centralized provider he's chosen can do it instead.


If the payment processor implements an easy URL scheme with a short checksum, than that's great. It doesn't require encoding anything on the blockchain, though.

Maybe there's more merit to the static-address solution you've described. I'm skeptical that it offers much improvement over firstbits, but I could be wrong.

Would you memorize your bank account number? I won't.

Why should I memorize by bitcoin address?

hey , would you please tell me why we should avoid reusing adresses ? cause i dont see a reason to do that. please aware me : >

I don't think that's a fair analogy.

(I think) OP's desire was to make it easy to create or reference a receive address in informal situations without carrying anything with you (e.g. splitting a bill with a friend). Traditional transaction mechanisms do that just fine today (cash: don't need to remember anything; checks: just need to remember your own name; centralized e-money (e.g. PayPal), just need to remember your email address/account ID).

I think such a mechanism for Bitcoin would be great, but I'm skeptical that any such mechanism would meet a reasonable set of minimum requirements. My own set of requirements would include:

• Easy to remember
• Easy to set up/maintain
• Decentralized
• No address re-use

If you can't achieve all of the above, than you need to prioritize. I'd nix either the first or the second, and that's what we already have today (base58check or BIP70). I think nixing either of the other two would be a worse idea, but that's subjective.

Hi Nicolas,
Really interesting idea but I fear you still have to cope with blockchain pruning if you plan to store this data in the bitcoin blockchain.
Why not rely on a bip70 uri stored in namecoin blockchain ?
Out of topic: congrats for your book. amazing work !

Do you memorize you mobile phone number ? I do, and my friends do.

Quoting myself (I thought about it after people on this thread told me it would be a significant problem, but not initially)



It does everything above, since the proof is a simple partial merkle tree (no trust relationship), that can reference a BIP70 address, as opposed to a fixed address, all data is stored on the blockchain.


Thanks laurent, the second part will release beginning of march. ;)
I don't want to rely on namecoin and another blockchain since the bitcoin network can already do that easily.
BIP70 is fine, but as I said, you can't ask Joe to register a domain name and hosting its server.
If Joe use a third party service for that, then, most of the time the url can't be memorized (hard to remember ids).
If it can be memorized, the longer the address, the higher the chances to send money to someone else by mistake.

That's a lot of if, that in any case my scheme would solve.

My scheme would have a checksum embedded and can fit any payment destination (BIP70 or fixed address) in 4 easy to remember, and hard to mix up words.

I thought we agreed that it didn't meet both "Easy to set up/maintain" and "No address re-use" at the same time, given that BIP70 isn't easy to run on your own (or it fails "Decentralized" if you use a 3rd-party processor which implements BIP70)?

Nobody has discussed that this proposal is anglocentric. I speak Spanish, and it's as hard for me to learn “car yellow what” than “1hshbx”.

How is PathToLeaf different that the txIndex? It looks to me that if you write the txIndex in binary, you have the same result.


It fixes the address reuse if and only if the user is willing to set up a payment server. But later you say that most people wouldn't go through the trouble of doing so.


It works with a carefully crafted dictionary. What would you use? Would you be able to provide one for different languages? The checksum detects errors but doesn't correct them. Your friend would not be able to pay you.


But it prevents pruning. Eventually, people will not have your tx if it's buried deep down and they will rely on an online service.

In any case, I'm not sure there is a need for this. If it's a large amount, I would prefer to give a QR code or a payment URL (if I'm a business). For a small amount, I would tell my friend that I will email him the address later or I'd set up a gmail account pay-hhanh00@gmail.com with an autoreply that gives a payment address.

It says in OP it will follow BIP39 wordlists, there are other languages: https://github.com/bitcoin/bips/blob/master/bip-0039/bip-0039-wordlists.md

I agree that there is still a trust relationship between the BIP70 provider and the user.
However there is no trust relationship between a "Brain address" provider and its user. (contrary to firstbits)
What we can't do with my scheme is having both : No address reuse + No trust relationship with BIP70 provider, you have to pick one of those.

It can be solved theorically by publishing a Stealth Address in the OP_RETURN instead of a bitcoin payment url.
But I don't think Stealth Addresses are wild spread enough for now, and is a pain because of OP_RETURN limits.


You have indeed the same result, the difference is that a PathToLeaf is an information that can be checked in a Partial Merkle Tree (SPV), while TxIndex is not.

The difference is in the size of the proof. In the first case, the "brain address provider" would need to send you either the whole block as the specified Height to prove he is not lying, or the ordered list of all Transaction Ids in the block. (this latter proof is compact enough but can't be fetched directly on the bitcoin network)
In the second case, the "brain address provider" just need to give you the Transaction + Block Header + Partial Merkle Tree to it. (such information can be retrieved directly by connecting to the bitcoin network, on low capacity/bandwidth devices)

I would use BIP39 dictionary. https://github.com/bitcoin/bips/blob/master/bip-0039/bip-0039-wordlists.md (https://github.com/bitcoin/bips/blob/master/bip-0039/bip-0039-wordlists.md)
Currently supported are English,Japanese,Spanish,Chinese (Simplified),Chinese (Traditional) and more will be provided by the community in the future.

You can rely on an untrusted "brain address provider" thanks to the simplicity of the proof, people don't need the full blockchain.

Maybe, the best way to know is to try, and I will.
My point is that you don't memorize wire transfer account number because you can't, not because you don't have the need.
This is why people still remember their phone number, it can fit in their brain. A BIP70 most likely do not and is prone to lookalike attacks.
I believe that if people have a way to easily memorize a payment destination, they will use it.

I have a subtle exercise for you, advocating about remembering/sharing a payment url :
What is the difference between "http://payment.com/u/tata" and "http://payment.com/u/tata" ? (you can try comparing these two addresses in your favorite programming language, they are not the same)

(Slightly OT) FYI BIP39 wordlists aren't guaranteed to use unique words wrt each other; in particular the two Chinese word lists share over 50% of their words so you'd probably need to choose one over the other (or neither).

You have not fixed the following problems:

1. blockchain reorg

2. Miners may try to fill up a block with garbage for a vanity address

To fix the reorg problem you have to include blockhash and/or tx-hash somewhere in your formula. This is tricky because that would lengthen the address

To fix the vanity address problem miner shouldn't be able to determine the address before a block is found. Again, this is avoided if the blockhash is part of the formula

------------------------
I'd like to propose the following method for referring any ScriptPubKey on the blockchain. I don't care how people interpret the information in the ScriptPubKey:

Version: 1 bit (always 0)
Height: 20 bits (up to block 1048576, enough for 13 years)
txIndex: 19 bits (up to 524288 tx/block, won't happen until the blocksize is >110MB)
TxOut index: 8 bits (up to 256 outputs/tx)
Checksum: 29 bits (slightly weaker than 32 bits in a standard bitcoin address)
Total: 77 bits, requiring 7 words to encode

All components are zero-padded. Anything beyond block 1048576 / txIndex 524288 / TxOut index 256 are invalid.

Checksum is the first 29 bits of SHA256(Blockhash-ScriptPubKey)

The 48-bits (Version-Height-txIndex-TxOut index) is split into 6 fragments of 8-bits
The 29-bits Checksum is split into 5 fragments of 5-bits and 1 fragment of 4-bits
Fragments are concatenated alternatively, so miners are not able to mine a vanity address without giving up a successful block hash.

To resolve the address, an SPV node has to obtain the ScriptPubKey with Height-txIndex-TxOut index, and verify the Checksum with Blockhash-ScriptPubKey

Reducing to 6 words is possible but it reduces the checksum security and future compatibility
Version: 1 bit (always 0)
Height: 20 bits (reducing to 19 bits will make it overflows in less than 4 years)
txIndex: 16 bits (up to 65536 tx/block, won't happen until the blocksize is >13MB)
TxOut index: 5 bits (up to 32 outputs/tx)
Checksum: 24 bits (Not sure if this is enough)
Total: 66 bits

Or 5 words:
Version: 1 bit (always 0)
Height: 20 bits
txIndex: 13 bits (up to 8192 tx/block, won't happen until the blocksize is >1.5MB)
TxOut index: 4 bits (up to 16 outputs/tx)
Checksum: 17 bits (This could be risky)
Total: 55 bits

8 words would be good enough for foreseeable future. It's still much better than encoding an 160-bits address with 15 words:
Version: 1 bit (always 0)
Height: 22 bits (enough for >70 years)
txIndex: 25 bits (enough for 6.8GB block)
TxOut index: 11 bits (up to 2048 outputs/tx)
Checksum: 29 bits
Total: 88 bits

This is the problem of the wallet implementation. Whether they are using my spec or not, they need to manage that correctly (needed for checking a Partial Merkel Tree), this is orthogonal to my spec.
Do you refer to the fact that one "brain address" might point to an invalid TxOut after a reorg ?
One way to mitigate that is to ask for 101 confirmations. (coinbase maturity)
However, the fact that some services will not want waiting so much time, even if my spec ask for it, might be troublesome. I don't have a better solution though.

Why would they do that ? there is nothing to win by doing that.

I will not use your encoding technique.
The reason is that there is no reason to choose the number of words in a "brain address". As opposed to a private key, the fewer the better.
The best way to encode a "Brain Address" is to use the VarInt encoding that all bitcoin wallet already implement. (or the less supported CompactVarInt internal to bitcoin core)

Also, encoding the TxIndex is inferior to encoding the PathToLeaf, for 2 reasons : it takes more space, and more than a simple Partial Merkle Tree would be required as proof. (whose proof checks are already implemented in all SPV wallets)
Code reuse would be maximized, code error minimized, so adoption by wallet providers should be better.

Moreover, each words represents 11 bits of information.
If we need 23 bit for encoding an address, then we have 10 bit that serve for nothing. I propose to fit the checksum inside.
The size of the checksum in bit would be something like Max(5, UnusedBitCount).

This should represent all current payment destination on 3 or 4 words. And it will goes up very very slowly.

I'm completely confused by what you are saying now. The txindex = path. How can one be better than the other unless you are adding data.
I guess we will see once you implement it.
The worst that can happen is people losing their coins  :P

Very cool what you guys are trying to do.

However, isn't this the wrong way around? Maybe use the brainwallet method: creating a key BASED on a certain seed (that's easy to remember)?

Initially I wanted to encode BlockHeight,TxIndex,TxoutIndex as you said.
If Alice asks to Malicious to resolve BlockHeight,TxIndex,Txout Index and Malicious resolve to address X, then Alice need a proof that Malicious is not lying.
If you use TxIndex, this proof must be the whole block at BlockHeight (which is big) OR the blockheader + list of all transaction id inside. (which is not supported by the bitcoin network)

If instead of TxIndex, you encode PathToLeaf, then Alice can ask the Transaction + Merkle Tree of it as proof, which is both : compact and already supported by SPV wallets and the bitcoin network.

This is called BIP39, and it deals with a private key. There is no way to get a secure key with less than 12 words.
The goal of my proposition is not about encoding a private key, but encoding a payment destination in 3 or 4 words. (BIP70 or address)

Ah, I see. I completely misunderstood, then.

No, you take the txindex and interpret it as a position in the merkle tree. The tree has all the tx ordered by index as its leaf. It's the same value.

Yes you are right, geez I made it more complicated than what it should be.
Also, I was wrong about using VarInt. Since it works only on byte boundaries, we'll loose space with it.
Your proposition for encoding seems better in fact even though 5-8 words seems a lot to remember though. :(

Given 300 000 blocks, 1000 tx, 10 TxOut, 256 bit of checksum, I calculated 4 words though.

A way of serializing the data similar to VarInt (but with different boundaries), might better adapted to earlier and future address (early address would be small, and older bigger).
I'll try to propose something.

A bip 32 seed is 128 bit long and takes 12 words. How did you figure out to use only 4?

I did not, I just explained him that my goal was NOT about encoding a private key ;)

Just use the blockhash as part of the checksum as I suggested. It's quite obvious.



Why won't they do that? Let say address of the block 987654 txindex 7777 output 888 is "best adult web". This address will be extremely valuable and all miners will try to grab it.

[/quote]

Do you really think 5 bits of checksum is enough? An address with random error will have 3.125% of probability to be valid. It's just unacceptable especially for bitcoin which getting refund is totally impossible.

Except the one that discover the vanity address also know the private key. Would you buy the key knowing someone you don't know own it ?

I think it is enough, at the first place most words in BIP39 are hard to get wrong. But you might be right, I will play a bit with several way of encoding it, and see if I can find a compromise between size (which I would like max 4 words for now) and checksum.
Right now, hhanh00 proposed something with more checksum, I hope finding something more space efficient though.

I can't add the 32 bytes, it would result in something nobody can remember. How much bit do you think should mitigate the problem enough ?
Ok I understood what you meant, great idea.

Miners could sell the block space for the vanity address without knowing the private key. All they need to do is to put their client's transactions in the appropriate positions. If the incentive is big enough, strong miners may even try to orphan other people's block to grab a good address.

My proposal will insert bits derived from the block-hash everywhere in the address, so it is not possible to mine a vanity address without discarding a successful block.


This is not true. Please don't assume all people are native English speakers. Even for native speakers many words are still very similar

gmaxwell has list some examples of poorly chosen words in BIP39: [choice, choose], [drip, script, trip], [risk, brisk], [load, road]

some more: [awake, aware, away], [stamp, stand], [price, pride], [steak, stick] (frankly speaking, I can't differentiate between "steak" and "stick" at all)

5 bits is unacceptable. I think 16-bits is really minimum, with an error tolerance of 1/65536. 20-bits will give 1 in a million.

Let say 1% of the world population will exchange their bitcoin address once per day, which is 70,000,000/day

0.01% of them will make a random mistake. So there will be 7000 mistakes/day.

With 5-bits of checksum, there will be 218 irreversible erroneous transaction/day
With 16-bits of checksum, this reduce to once per day
With 21-bits of checksum, this reduce to once per 300 days
Satoshi uses a 32-bits checksum in bitcoin address. That becomes once per 1681 years

Having an address with only 4 words is great, but it gives a false sense of security. If we are going to establish an industry standard, I believe we have a moral responsibility to lay users. We all make mistakes, and I'm sure 0.01% is way underestimated.

(You may argue that a random mistake may just point to a non-existing output but I've already used conservative parameters in my estimation)

So your proposal of adding the blockhash in the checksum would do the trick for preventing vanity addresses ?

I see your point with the checksum, I'll try to find a good way of encoding all of that. I came up with the 5 bit from the BIP39 checksum, but such checksum would be less used than a "brain address".

And the checksum has to be broken down into pieces and inserted in every 11-bit block to make sure every word is pseudo-random. Vanity addresses are still possible, just by pure luck. No mining of vanity address is possible.


Encoding of private key and public key are different concepts. If you made a small mistake in private key, it is very likely to recover it by some burst force. If you sent you bitcoin to a wrong public key, it is totally irreversible.

Case 1: Alice would like to transmit the private key "ABCD1234" to Bob. The private key has no checksum and is carrying 100BTC on the blockchain. However, due to unstable network, Bob received "ABBD1234". Bob will immediately find that the private key carries no bitcoin and will ask Alice to resubmit. Even if he can't reach Alice again, he can still try to burst force it with the available information.

Case 2: Alice would like to transmit the public key "ABCD1234" to Bob. The public key has no checksum. However, due to unstable network, Bob received "ABBD1234". Bob sent 100BTC to "ABBD1234" and screwed up

It makes sense, thanks for your input, will try to make something out of all of that !

With 16 bit of checksum, it is possible to fit everything in 5 words.
Knowing the block, we know how much transaction there is, so we know how much bits to use for encoding.
Knowing the transaction, you know how much bits to use for encoding the TxOut index.

So if we take 24 bit for Block height (block 16 777 216), the transaction count is currently 10 bits, the TxOut index will be 1 bit most of the time. (OP_RETURN + Change)

So this gives us
24 + 10 + 1 + 16 = 51 bits for a 16 bit checksum, (5 words)

I would like to find a more efficient way of encoding the block though. (instead of hardcoding 24 bits)
I suspect I can fit some information about the block in the checksum.

good idea. This saves a lot.

You certainly don't need 24 bits for block height. It takes >300years. All cryptography in current form should have been broken long before that. 22 bits (70 years) would be enough.

The TxOut index is controlled by user so let's assume it to be usually 1 bit (because people want a short address)

I want at least 20 bits of checksum (1 in a million error tolerance)

I prefer to leave 1 version bit for future extension. (otherwise we may need to use a completely different word list for future encoding scheme)

-----------------
So a 5-words address would have

1 version bit
22 block height bits
1 to 11 txIndex bits
1 to 11 txOutputIndex bits
at least 20 checksum bits

The txIndex and txOutputIndex will always use the least possible bits, leaving more room for the checksum.

For example, if a block is known to have only 500 txs, the txIndex will only take 9 bits so the txOutputIndex may take at most 3 bits. If there is only 3 outputs (2 bits) in the tx, the checksum will have 21 bits

EDIT: If there is not enough bits left to fully encode txOutputIndex, the earlier outputs are assumed. For example, if there are 14 outputs (4 bits) in the tx but only 2 bits is left for txOutputIndex, we could still encode the first 4 outputs with 5 words.

Similarly, if a block has more than 2048 txs, a 5-words address is still valid if it is referring to first 2048 tx in the block and it is referring to the first or second output
------------------
If an address can't fit-in a 5-words address, it would need 6 words anyway. So a 6-words address would have

1 version bit
22 block height bits
1 to 22 txIndex bits
1 to 22 txOutputIndex bits
at least 20 checksum bits

22 txIndex bits should be enough for a 800MB block. If that's still not enough, it could be extended to 7-words in a similar way.

It is also valid to encode a 5-words address in 6-words, for extra checksum security.

I'm not sure if this is a right way to go. A checksum should be statistically independent from the information. Otherwise, it's not a checksum

Yes, and I think 5 words is no so bad in fact. Short term human memory remember 7 items, our phone numbers are 10 numbers.
I don't think I'll be able to fit that in 4 words anyway.

To convert the bits into final address, we first serialize version-height-txIndex-txOutputIndex (the "information"). The information should be within 25-35 bits, and checksum is 20-30 bits

To derive the first word, we take the first 4 bits from checksum and the first 7 bits from information. This is repeated until all information bits are included. The rest will be checksum if there is any left *

A 6-words address would be encoded similarly, with 3 bits of checksum and 8 bits of information for each word.


* I put checksum before the information to make each word looks more "random". Otherwise, some words would be used more frequently than others, especially the first 2 words which encodes the block height.

It makes sense, the only thing I would fix is the size of the checksum to make it minimum 16, rounded up to fill the unused avalaible bits.
If we have 6 words but actually use 56 bits, then we can add 10 bits to the checksum.

Do you see a way of improving hardcoding the size of the block height ? 22 bits is only ok until block height of 4 million... I agree that we don't care right now, but if we find a nice way to increase without doing a new spec, it would be nice.

What about having 4 bit that give information about the number of bit of the block height ? (0 = 19, 4 = 23)
stupid idea :p

I'm coding it the way you proposed. We'll see if I find an idea for encoding the block height in a more efficient and general manner. (it is sad that we also use 22 bit even for the first blocks)

Actually I believe we will have some better way to encode before block 4M. It is also likely that there will be significant change in the blockchain structure and this scheme will obsolete. In such case, probably 21 bits is already enough as I expect such change would happen in 30 years.

There is always a big temptation to reduce the number of checksum bits but each bit you cut halves the security.

Wow, just now, the block 346019 has 2064 transactions.

I implemented it exactly as you proposed.
https://github.com/NicolasDorier/NBitcoin/blob/master/NBitcoin/BrainAddress.cs (https://github.com/NicolasDorier/NBitcoin/blob/master/NBitcoin/BrainAddress.cs)

We are already at 5 words though. (16 bit checksum)
I also check, if there is unused bits, that they are all to 0.

I still think 16 bits of checksum is overkill.

If there is a mistake, the info should not be : out of the chain, out of the block, out of the transaction, but also encoded correctly. (correct number of bit for encoding transaction index and txout index)

We need some independent security experts to suggest the appropriate number of checksum bits.

Thanks for your coding but I can't read C. I'd like to illustrate with some examples:

---------------------
The only output in the genesis block:

version: 0
height: 0000000000000000000000
txindex: 0
outputindex: 0

information: 0000000000-0000000000-00000

blockhash: 0x000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
scriptPubKey: 0x4104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4 cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac
SHA256(blockhash-scriptPubKey) = afb4b496b902df5adc89d9d89080f6dc80383dbe6e1067140721ed53e2ccbedb
Checksum = First 30 bits* of SHA256 hash = 1010-1111-1011-0100-1011-0100-1001-01

With 1-bit checksum and 10-bit information for each word**, it becomes:
1(c)
0000000000(i)
0(c)
0000000000(i)
1(c)
00000(i)
011111011010010110100100101(c)

So the 5 words address will be
10000000000-00000000000-10000001111-10110100101-10100100101
i.e. length-abandon-limit-regret-pigeon


* I still assume minimum 20-bit checksum. It could be encoded in 4 words if 16-bit checksum is used.
** Since you are using 16-bit checksum instead of 20-bit as I suggest, there might not be enough checksum bits for each word if 4 checksum bits is used. So I'd like to standardize it to be 1+10 instead of 4+7 as I suggested before.

Personally I think five words would be easy enough and if the checksum was spread across all five then that should help to prevent the five word sets from looking too similar to others that are from the same block.

In the example above I use 1 checksum + 10 information for each word. Maybe 2+9 is better to make the words look more "random"

With 2-bit checksum and 9-bit information for each word, it becomes:
10(c)
000000000(i)
10(c)
000000000(i)
11(c)
0000000(i)
111011010010110100100101(c)

So the 5 words address will be
10000000000-10000000000-11000000011-10110100101-10100100101
i.e. length-length-scatter-regret-pigeon

Example 2: the 4th output (sending to 17SEHdQNxrP64M6aUkDJtoUKAhSMujamhE) of 9abcc1383bcc5eb980dd263837c7bd368d0fd5d1696a89e49dc9e63c82e7ce16

The block has 460 transactions so 9 bits is needed for txindex
The tx has 21 outputs so 5 bits is needed to encode all outputs. However, with only 5 words and 20bits of checksum, only 3 bits is left. That means we could only encode the first 8 outputs.

version: 0
height: 0001010100011111100110 (346086)
txindex: 101111010 (378, or the 379th tx)
outputindex: 011 (3, or the 4th output)

information: 000010101-000111111-001101011-11010011

blockhash: 0x000000000000000000e83a55db617b5db59ce161f8ef4d0989b8c6d1a3e82102
scriptPubKey: 0x76a91446963eb29098f58519f94bd8c3130f5b5166123488ac
SHA256(blockhash-scriptPubKey) = 34e17a91bcccfb02b4eec27d035c3f5c2150675ede100d1be7549f2629b93a8a
Checksum = First 20 bits of SHA256 hash = 0011-0100-1110-0001-0111

With 2-bit checksum and 9-bit information for each word, it becomes:
00(c)
000010101(i)
11(c)
000111111(i)
01(c)
001101011(i)
00(c)
11010011(i)
111000010111(c)

So the 5 words address will be
00000010101-11000111111-01001101011-00110100111-11000010111
i.e. actor-side-estate-crunch-seed

I would think 16 bits of checksum would be reasonable enough (in which case you'd be able to handle up to 128 outputs which I would think should cover the vast majority of transactions in the blockchain).

But perhaps 18 bits of checksum with up to 32 outputs would be a better trade-off (some blockchain stats would be helpful to know how likely it is that the first occurrence of an address is part of a transaction with X outputs).

You could also shrink the amount of checksum bits according to this (as it isn't so likely to normally occur anyway).

I actually quite like this idea compared to firstbits - hopefully this can be added to a block explorer when you've finalised it.

My own thinking is that this could be handy for remembering a cold storage address when say you are out without your own computer but need to find an address for someone to send to.

Why cant we just , be able to register our adresses in the bitcoin wallet , that would then give our adress a unique name , that you could alternatively send to this would be pretty easy to make right ? : >

^^^ this is why "ad sig" campaigns suck...

Anyway, I'll provide test vectors soon, with a spec better redacted.
I'll post the test vectors here, and try out with yours.

The way it currently works, it automatically adapt to the size of block/transaction.
For example, if a block have 512 transaction, I'll use only 9 bits for encoding the tx index.
If it has 513, I use 10 bits.
Same principle with TxOut : if the transaction has 2 outputs, I encode it on 1 bit.

The checksum is in fact a little bigger than 16 bits. The reason is that I plan to use the spare bits to fit more checksum.
16 bits would be the minimum up to 26. (depending on the number of spare bit)

I'm playing with all those observations a little bit, post some result here, and if we seem to agree, I'll redact a proper specification on github.

Because it does not fix the problem I try to resolve : storing a payment destination in your head which you can freely give orally to someone you just met, without any third party trust relationship involved (which would be subject to attacks/bug).

I just find a problem: how could a SPV client count the number of transactions in a block, without downloading the whole block?

Related discussion: https://bitcointalk.org/index.php?topic=975648.0

If this could not be done, your proposal won't work for SPV clients without trusting a centralized service

If this could be done, there is an even more compact way to encode transactions: just number all transactions chronologically. According to blockchain.info

https://blockchain.info/charts/n-transactions-total?timespan=all&showDataPoints=false&daysAverageString=1&show_header=true&scale=0&address=

we have about 61,000,000 transactions. This could be encoded with only 26 bits. Since most blocks are not full, this must be much more efficient.

It works.
The SPV client will receive : BlockHeader + Partial Merkle Tree + Transaction.

The length of the partial merkle tree tell you the transaction count upper bound, and this is what we need to define how much bit it takes. (Bit Count = TreeDepth)
We don't need the precise number, just the upper bound.

Moreover, the transaction count is included into the merkleblock.

I did it !!! SPV Compatible.

https://github.com/NicolasDorier/NBitcoin/blob/master/NBitcoin/BrainAddress.cs#L110 (https://github.com/NicolasDorier/NBitcoin/blob/master/NBitcoin/BrainAddress.cs#L110)

The Brain Address can be verified just with : Chain Headers + Transaction + MerkleBlock. :)

More test vector + better spec later !

I didn't know this. Then why couldn't we just number all transactions consecutively and use it as the index? Therefore, we don't need to worry for inadequate bits for txIndex. Moreover, as most blocks are not full, this must be much more efficient than indexing by height-txIndex.

Right now there is about 61,000,000 tx from the genesis block, and is growing by 100,000 tx/day. Assuming a 100x growth, we would have 36,500,000,000 tx in 10 years. This could be encoded with 36bits. Using the height-txIndex index it would take 22+16=38bits, assuming 70,000tx/block. With 10,000x growth, that will be 42bits and 45bits respectively.

I know the transaction count in merkleblock may not be trustworthy. However, as the calculation of checksum involves the concerned scriptPubKey, such attack should not be possible.

However, this will require SPV nodes to keep a record of transaction count in all blocks in the history.

Because of the size of the proof.
Right now the proof is Transaction + Merkle Block.
With your transaction count, the proof would be Transaction + Merkle Blocks until genesis.
To prevent any tampering, the SPV client would also need to store all those blocks, and check them every time.
It is sure more efficient, but the burden of proof is too big.

It is. Without the right count, you can't build the PartialMerkleTree correctly.(you get the wrong shape)
And with the wrong PartialMerkleTree, you end up with the wrong merkle root.
Is it possible to build a valid PartialMerkelTree with the wrong TransactionCount ? I think it is not but sadly I have no proof. But as you said, if I get the wrong transaction, the checksum would catch the error.

In my code snippet, I assumed that the SPV client know the Transaction before hand. Which is false.
But with a pure SPV, it is still possible to get it:

-Set Bloom Filter to match everything.
-Ask the filtered block
-Get the transaction that interest you.

I don't like this solution because it would ask the SPV to download the whole block.
A better way, with the same problem is to:

-Clear the Bloom Filter
-Ask the whole block
-Get the transaction that interest you.

But as I said, I don't like the idea of a SPV having to download the whole block.

A better way would be to solve the brain address thanks to a third party service, and just ask for the proof along with the resolution.
I don't expect wallet in the future (nor now) will be pure SPV anyway.

I believe the future is centralized bitcoin services (hostable by yourself if you are concerned about privacy), where the server delivers compact proof, and client are responsible of checking them.
I don't believe 100% SPV client will spread on the long term.

I think there is a better way to encode the address. Assuming a 5 words address, just serialize the following:

Height: x bits
TxIndex: y bits
OutputIndex: z bits
Checksum: 54-x-y-z bits

(If 54-x-y-z < c, the address is invalid and more words are required. c is the minimum checksum size)

The result is called the "raw address".

Take the last c bits of the raw address (the "encryption key")

Use the encryption key to XOR the first 54-c bits of the raw address (the "encrypted address").

The final address is [encrypted address-encryption key-0] (The last 0 is the version bit)

-----------------------
Example: the output in the genesis block:

height: 0000000000000000000000
txindex: 0
outputindex: 0

blockhash: 0x000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
scriptPubKey: 0x4104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4 cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac
SHA256(blockhash-scriptPubKey) = afb4b496b902df5adc89d9d89080f6dc80383dbe6e1067140721ed53e2ccbedb
Checksum = First 30 bits* of SHA256 hash = 101011111011010010110100100101

So the raw address is 0000000000000000000000-0-0-101011111011010010110100100101

Assuming c is 20, the encryption key is 11010010110100100101. It is repeated in order to encrypt the first 34 bits of the raw address

XOR (00000000000000000000-00001010111110) with (11010010110100100101-11010010110100) = 11010010110100100101-11011000001010

Final address = 11010010110100100101-11011000001010-11010010110100100101-0

Decode of the address is trivial.

-----------------------------------------------------------------------

Rationale:

1. This introduces entropy to every bit of the address. Even the raw address of 2 outputs are very similar, the output will be statistically independent

2. This could be easily extended to any size of c and number of words used

3. Since the BIP39 word list sorts alphabetically, putting the version bit at last make sure that the first letter of the last word could cover a-z (thus less error-prone because human tends to recognize vocabulary with the first and last letter: see: http://www.ecenglish.com/learnenglish/lessons/can-you-read). Otherwise it will only cover a-l (0-1023)

4. It looks more tidy than my previous proposal

To make it more compact, if there is only one tx in a block (i.e. the coinbase), the txindex will take 0 bit. Similarly, if there is only one output in a tx, the outputindex will take 0 bit.

In this case, a 5-word address with 22-bit height and minimum 20-bit checksum may encode up to 2¹²=4096 tx in a block, if the user is referring to the first output.

I see some inconsistency, can you tell me if I reformulate right ?

I assume you mean 55. There is 55 bits in 5 words.


So

Checksum = SHA256(Concat(blockhash,scriptPubKey))

raw address = blockheight(22)-txindex(1)-outputindex(1)-checksum(8*32)

Then you truncate checksum to get a raw address of 55 bit. (so you keep only the 33 first bit)

raw address = blockheight(22)-txindex(1)-outputindex(1)-checksum(21)

The checksum meet the minimum size, so you keep 5 words.

Now you define

EncryptionKey = checksum(20)

So we have :
EncryptedAddress = raw address(35) - EncryptionKey

It's 54 because 1 is left for the version bit

To formal define:

Definitions:
The address takes w-words
Height will take x bits, where x is fixed.
Checksum will take at least c bits
TxIndex and OutputIndex are counted starting from 0.

We first set w = 1 (we may have a better initial value if x and c are known)
TxIndex will take y bits, where

• y1 = ceiling(log(tx count in the block, 2))
• y2 = 11w-1-x-c
• y3 = ceiling(log(TxIndex of the interested tx + 1, 2)
• y = max(y3, min(y1, y2))
  

OutputIndex will take z bits, where

• z1 = ceiling(log(output count in the tx, 2))
• z2 = 11w-1-x-y-c
• z3 = ceiling(log(OutputIndex of the interested output + 1, 2)
• z = max(z3, min(z1, z2))
  

Checksum will take 11w-1-x-y-z bits. If 11w-1-x-y-z < c, increase w by 1 and repeat until we find the smallest solution for w.

In English:

If there is enough space, I'll use y1 bit to encode TxIndex. Otherwise, I'll use y2, given that it's enough to encode my interested tx. Otherwise, we need more words
If there is enough space after y is fixed, I'll use z1 bit to encode OutputIndex. Otherwise, I'll use z2, given that it's enough to encode my interested output. Otherwise, we need more words

1 bit is deducted for version bit

Checksum = SHA256(Concat(blockhash,scriptPubKey))

RawAddress = blockheight(x)-txindex(y)-outputindex(z)-checksum(8*32)

Then you truncate checksum to get a RawAddress of 11w-1 bit.

RawAddress = blockheight(x)-txindex(y)-outputindex(z)-checksum(11w-1-x-y-z)

The checksum has to meet the minimum size c.

Now you define

EncryptionKey = least significant c bits of RawAddress
If 11w-1-c =< c, FinalEncryptionKey = EncryptionKey(11w-1-c)
If 2c >= 11w-1-c > c, FinalEncryptionKey = Concat(EncryptionKey, EncryptionKey(11w-1-2c))
If 3c >= 11w-1-c > 2c, FinalEncryptionKey = Concat(EncryptionKey, EncryptionKey, EncryptionKey(11w-1-3c))
etc

So we have :
EncryptedAddress = XOR(RawAddress(11w-1-c),FinalEncryptionKey)
FinalAddress = Concat(EncryptedAddress,EncryptionKey,0)

To decode, just derive the FinalEncryptionKey with EncryptionKey, and XOR with EncryptedAddress, concat the result with EncryptionKey, and the result will be RawAddress

To decode, we can determine w with number of words used, so we will know y2 = 11w-1-x-c. We will also know y1 by the block height. Therefore, y=min(y1, y2)

With y confirmed, we can determine z2 = 11w-1-x-y-c, and z1 by retrieving the tx. Therefore, z = min(z1, z2)

With x, y, z fixed, the rest will be checksum

I don't have the prove but I believe this is the most compact way to present an address

This leaves only 2 parameters to set: x and c.
x=22 for 70 years, 21 for 30 years, and 20 for 10 years
c maybe somewhere between 16-20. I prefer the upper bound.

I think this proposal is better than the previous.
The only thing that is strange is :

What this final 0 is for ?

Just to be clear, "better" is not "more efficiently" ? but easier to implement right ?

I don't see any flaw right now, I'll sleep on it tonight and implement it if I don't find any problem.

Also you don't include TxIndex in the checksum. I think we should.
If a bit is flipped on the TxIndex, then the checksum will not see it. Agreed that we don't care, since the ScriptPubKey will still have to be the same.
However, I see no reason why not to include it.

[UPDATE]One reason to include txindex in the hash : if someone wants to communicate the transaction id by using a "brain address"[/UPDATE]

Yes, just easier and tidier.

0 is the address version. We have to spend at least one bit to denote the version. Otherwise, we need an entirely different word list to upgrade the scheme in the future (e.g. due to some major hardfork in the blockchain)

ok perfect for me, I prefer this proposal, I'll give it a try.

Hmmm ... The English description doesn't match the pseudo code (a bug?). Moreover, it looks like the intended algorithm has collisions (different pairs of inputs that lead to the same encoded value pre checksum).

I think it's correct but I can present in a different way:

The address takes w-words
Height will take x bits, where x is fixed.
Checksum will take at least c bits
TxIndex and OutputIndex are counted starting from 0.

Define
y3 = ceiling(log(TxIndex of the interested tx + 1, 2))
z3 = ceiling(log(OutputIndex of the interested output + 1, 2))
w = ceiling((x + y3 + z3 + c + 1)/11)

TxIndex will take y bits, where

• y1 = ceiling(log(tx count in the block, 2))
• y2 = 11w-1-x-c
• y = min(y1, y2))
  

If (y3 > y), increase w by 1 and start again from the beginning

OutputIndex will take z bits, where

• z1 = ceiling(log(output count in the tx, 2))
• z2 = 11w-1-x-y-c
• z = min(z1, z2)
  

If (z3 > z), increase w by 1 and start again from the beginning

Checksum will take 11w-1-x-y-z bits.

It's ambiguous because given an encoded value, you don't know where the separation between txindex and outputindex is.

To keep things simple, let's say
- x = c = 0
- w = 1
- and 8 bits per word instead of 11.

if i have 0101 0000, is it
- txindex = 0 and outputindex = 1010000 or
- txindex = 01 and outputindex = 010000 or
- txindex = 010 and outputindex = 10000 or
- txindex = 0101 and outputindex = 0000 etc

the checksum introduces another issue. Since it has variable length, where does it start?

Then you may also want to include outputindex as different output may have different meaning, even if they use the same scriptPubKey

So checksum = SHA256(blockhash-txindex-outputindex-scriptPubKey)

And I think x could be a VarInt

For height =< 1048576 (0-1111-1111-1111-1111-1111), it is encoded as usual with x = 21

For height > 1048576, the binary code will start as 1, followed by the height as 23 bit integer. Therefore x = 24. For example, block 1234567 is 1001-0010-1101-0110-1000-0111

Assuming 144 block/day and no hardfork to decrease block interval, we can keep x=21 until 2028. By 2028, I believe the block size will be very big and 6-word address will be the norm.

And the whole scheme is valid until 2168. The timestamp in block header will overflow in 2106 so I don't care anything after that.

There is no ambiguity. Just a repost:

To decode, we can determine w with number of words used, so we will know y2 = 11w-1-x-c. We will also know y1 by the block height. Therefore, we know y=min(y1, y2)

With y confirmed, we can determine z2 = 11w-1-x-y-c, and z1 by retrieving the tx. Therefore, we know z = min(z1, z2)

With x, y, z fixed, the rest will be checksum

You are only decoding to one of the possible pairs.
Just walk through the steps with my example if you don't believe me. I could be wrong, so it's good to have another person check. Better yet, post a reference implementation and anyone can verify.

Let me have a better example.

First of all, the number of bits must be a multiple of 11. To make it simple, let me use 22.

let's set x = 3, c = 4

let's say there is an address: 10101100110-00110101010 (w=22)

Since x=3, the block height is 101 = 5

So we look up the blockchain for block 5. Let's assume that the block has 40 transactions.

So y1 = ceiling(log(40,2)) = 6

We also know y2 = 11w-1-x-c = 22-1-3-4=14

So y = min(y1,y2) = 6

So txIndex is the next 6 bits: 011001 = 25

So we retrieve the 26th transaction in the block 5. Let's assume the transaction has 5 outputs.

So z1 = ceiling(log(5,2)) = 3

We also know z2 = 11w-1-x-y-c = 22-1-3-6-4 = 8

So z = min(z1,z2) = 3

So outputIndex is the next 3 bits: 100 = 4.

So the following bits: 011010101 are the checksum

The last bit is version bit and must be 0

So this address refers the the 5th output of the 26th transaction in the block 5. It is the only possible interpretation

=====

EDIT: it may not be very obvious but with w, x, c, and blockhash all determined, y is a fixed value. Similarly, with w, x, y, c, and txid all determined, z is a fixed value.

Too much idea. I'd consolidate everything in one post. I hope this will become a BIP.

BIP: xxxx
Title: Mnemonic code for referencing transaction output in the blockchain
Authors: Nicolas Dorier, jl2012
Status: Draft
Type: Standards Track
Created: 2015

==Abstract==

This BIP describes the implementation of a mnemonic code for referencing any transaction output in the blockchain.

==Motivation==

==Generating the mnemonic address==

Definitions:

blockHeight: the height of the referenced block. Genesis block is 0
blockHash: the hash of the referenced block
txIndex: index of the referenced transaction in the block. Index of the first transaction in a block is 0
outputIndex: index of the referenced output in the transaction. Index of the first output in a transaction is 0
scriptPubKey: the scriptPubKey of the referenced output
c: a fixed integer, the minimal number of bits for checksum (to be defined later)
y_min = ceiling(log(txIndex + 1, 2))
z_min = ceiling(log(outputIndex + 1, 2))

Step1: Determine the number of bits and encoding of blockHeight
blockHeight takes x bits and is encoded as follow:

• For height =< 1,048,575 (0-1111-1111-1111-1111-1111), blockHeight is the height as 21bit interger
• For 1,048,575 < height =< 8,388,607, blockHeight is Concat(1, height as 23 bit integer), which totally takes 24bit. For example, block 1234567 is 1001-0010-1101-0110-1000-0111
• For height > 8,388,607, it is undefined and returns error

Step2: Determine the lower bound of words required for the mnemonic address

• w = ceiling((x + y_min + z_min + c + 1)/11)

Step3: Determine the number of bits for txIndex
txIndex takes y bits:

• y1 = ceiling(log(total number of transactions in the block, 2))
• y2 = 11w-1-x-c
• y = min(y1, y2))
• If (y_min > y), increase w by 1 and go back to Step 3 (This condition is not possible as the initial value of w must provide enough space for y_min)

Step4: Determine the number of bits for outputIndex
outputIndex takes z bits:

• z1 = ceiling(log(total number of output in the transaction, 2))
• z2 = 11w-1-x-y-c
• z = min(z1, z2)
• If (z_min > z), increase w by 1 and go back to Step 3

Step5: Calculate the checksum

• rawChecksum = SHA256(SHA256(Concat(blockHash-txIndex-outputIndex-scriptPubKey)))    (I don't know why but Satoshi never used single SHA256)
• (for simplicity, the length of txIndex and outputIndex here is same as those determined in Step 3 and 4 respectively)
• checksum = rawChecksum(11w-1-x-y-z) (the most significant 11w-1-x-y-z bits of rawChecksum)

Step6: Get the rawAddress = Concat(blockHeight-txIndex-outputIndex-checksum)

Step7: Get the encryptionKey = least significant c bits of rawAddress

Step8: Get the finalEncryptionKey

• If 11w-1-c =< c, finalEncryptionKey = encryptionKey(11w-1-c)
• If 2c >= 11w-1-c > c, finalEncryptionKey = Concat(EncryptionKey, EncryptionKey(11w-1-2c))
• If 3c >= 11w-1-c > 2c, finalEncryptionKey = Concat(EncryptionKey, EncryptionKey, EncryptionKey(11w-1-3c))

etc

Step9: Get the encryptedAddress = XOR(rawAddress(11w-1-c),finalEncryptionKey)

Step10: Get the finalAddress = Concat(encryptedAddress,encryptionKey,0)
The last 0 denotes the address version

Step11: Convert finalAddress into mnemonic code following BIP-0039


==Decoding the mnemonic address==

Step1: Determine w = number of words in the mnemonic code

Step2: Convert mnemonic code into finalAddress following BIP-0039

Step3: If the last bit of finalAddress is 0, drop it. If it is 1, return error.

Step4: Get the encryptionKey = least significant c bits of finalAddress

Step5: Get the finalEncryptionKey

• If 11w-1-c =< c, finalEncryptionKey = encryptionKey(11w-1-c)
• If 2c >= 11w-1-c > c, finalEncryptionKey = Concat(EncryptionKey, EncryptionKey(11w-1-2c))
• If 3c >= 11w-1-c > 2c, finalEncryptionKey = Concat(EncryptionKey, EncryptionKey, EncryptionKey(11w-1-3c))

etc

Step6: Get the decryptedAddress = XOR(finalAddress(11w-1-c),finalEncryptionKey)

Step7: Get the rawAddress = Concat(decryptedAddress, encryptionKey)

Step8: Determine the blockHeight

• If the first bit of rawAddress is 0, take the first 21 bit out of rawAddress. This is the blockHeight
• If the first bit of rawAddress is 1, drop it. Take the first 23 bit out of rawAddress. This is the blockHeight
• If the block does not exist, return error

Step9: Determine the txIndex

• Look up the blockchain for the referenced block and determine the total number of transactions in the block
• y1 = ceiling(log(total number of transactions in the block, 2))
• y2 = 11w-1-x-c
• y = min(y1, y2))
• Take the first y bits out of rawAddress. This is the txIndex
• If the transaction does not exist, return error

Step10: Determine the outputIndex

• Look up the referenced transaction and determine the total number of outputs in the transaction
• z1 = ceiling(log(total number of outputs in the transaction, 2))
• z2 = 11w-1-x-y-c
• z = min(z1, z2))
• Take the first z bits out of rawAddress. This is the outputIndex
• If the output does not exist, return error

Step11: Calculate the checksum

• Determine the blockHash and scriptPubKey
• rawChecksum = SHA256(SHA256(Concat(blockHash-txIndex-outputIndex-scriptPubKey)))
• checksum = rawChecksum(11w-1-x-y-z)
• If checksum equals to the remaining bits of rawAddress, the address is successfully resolved. Otherwise, return error.

==SPV client compatibility==

==Test vectors==

EDIT: I corrected a bug in the steps 3 and 4 of the generation code

(It looks better in markdown)

Using the same values for `x=3`, `c=4` and the blockchain:
I want to encode a tx at index 3, output index = 0
My tx index is 11b. `y3=2` and `z3=1`
Now I go through the encoding steps.
- `w = ceil(3+2+0+4+1)/11 = 1`
- There are 40 tx, so `y1=6`
- `y2=11-1-3-4 = 3`
- `y=min(3,6)=3`
- `y3>y`? no. don't increase `w` but use 3 bits. txindex is encoded as `011`.

Next phase. Let's say there are 2 outputs in that tx.
- `z1=1`
- `z2=11-1-3-4-4 = 0`
- `z=min(1,0) = 0`
- `z3>z` ? yes. increase w. `w=2` and retry
- `z2=22-1-3-4-4 = 11`
- `z=min(1,22)=1`
- `z3>z` ? no. use `z=1`. utxo index is encoded as `0`.
- checksum takes `22-1-3-3-1 = 14` bits

My result is
`1010110xxxx-xxxxxxxxxx0`

Yours is
`10101100110-00110101010`

The beginning is the same. Let's say the checksum is 0110-xxxxxxxxxx
I get `1010110110-xxxxxxxxxx0`

The decoder will think the txindex is yours and fail to validate.
In fact, my address will fail for any value of the checksum because the decoder will look at a different tx than mine.

As output index=0,
z3=log(0+1)=0

Try again with the correct z3

Right, I changed that to match your value but there is no need for it. Use tx output = 1 then. The point is that w gets incremented after y was chosen based on w=1.

jl2012, I think your spec is correct but can be explained more easily.
I'm trying to implement that, once I am done, I will try to reformulate that without changing the meaning.

I overviewed what you said, hhanh00, I'll find ambiguity by implementing it if there is.

jl2012, I'll create a BIP doc on github, it will be more easy to collaborate this way.
Can you give your github id ? hhanh00 also if you want to participate ? so I can give write rights.

See my BIP above. After increasing w, you should go back to step 3. In your example, you only go back to step 4

This is not simple, the SHA operation is waiting for data at the byte boundary.
So for the implementation I am doing, I'm just using encoding blockhash,txindex and outputIndex in pure classical little endian.

Well, I have a hard time seeing what you are implementing. I thought you meant to go to step 4 because if I have to go to step 3 the case isn't that useful.

If in step 3, y = y2 because you have enough bits left then you use them all. Next in step 4, there won't be any left. So unless utxo index = 0, you will have to increase w and go back to the beginning. What's the idea behind this case then?

This is different than what I think you meant in English.

By the bold sentence, I mean to re-evaluate the y with more words. It may not be clear enough.

Anyway, I try to redo your example:

Using the same values for `x=3`, `c=4` and the blockchain:
I want to encode a tx at block 5, index 3, output index = 1
Therefore, `y<sub>min</sub>=2` and `z<sub>min</sub>=1`
Now I go through the encoding steps.
- `w = ceil(3+2+1+4+1)/11 = 1`
- There are 40 tx, so `y1=6`
- `y2=11-1-3-4 = 3`
- `y=min(3,6)=3`
- `y<sub>min</sub>>y`? no. don't increase `w` but use 3 bits. txindex is encoded as `011`.

Next phase. Let's say there are 2 outputs in that tx.
- `z1=1`
- `z2=11-1-3-3-4 = 0`
- `z=min(1,0) = 0`
- `z<sub>min</sub>>z` ? yes. increase w. `w=2` and retry


- `y2=22-1-3-4 = 14`
- `y=min(14,6)=6`
- `y<sub>min</sub>>y`? no. don't increase `w` but use 6 bits. txindex is encoded as `000011`.


- `z2=22-1-3-6-4 = 8`
- `z=min(1,8)=1`
- `z<sub>min</sub>>z` ? no. use `z=1`. utxo index is encoded as `1`.
- checksum takes `22-1-3-6-1 = 11` bits

Result is
`1010000111x-xxxxxxxxxx0`

----------------
decode:

x=3, so it's block 101, i.e. block 5
Because it is block 5, we know y1=6; because it has 2 words, we know y2=14. Therefore, we know y=6. Therefore, txindex is 000011=3
Because it is index 3, we know z1=1; because it has 2 words, we know z2=8. Therefore, we know z=1. Therefore, outputindex is 1=1
The rest is 11 bit checksum + 1 bit version

Yeah, you end up using y1 and z1. The only time it's not the case is when txindex is small enough and utxo index = 0. If that's the intent, it's better to call it out explicitly and formulate a direct method (without loops). It'd be easier to prove that it's uniquely decodable. I think it's not worth the trouble and I'd discard that special case.

Why not try same ways that used to generate private key with brain wallet?

I think there are few possible situations.

Using y1 and z1: having enough space to fully encode txindex and outputindex (i don't call it UTXO index because I don't care whether it is spent or not.)

Using y1 and z2: having enough space to fully encode txindex, but not enough for outputindex. Here z2 could be anything from 0 to infinity

Using y2 and z=0: having not enough space to fully encode txindex, and outputindex is 0

So yes, if y=y2 is used, z must be 0.

My (practical) approaches:

#1
Advantage: Works on every internet capable computer without any prior arrangements if you trust traditional block explorers like blockchain.info, otherwise additional trusted software setup is required. Very easy to memorize.
Disadvantage: You're likely going to fund criminals some satoshis.

Creating:
1. Just generate a bunch of random bitcoin addresses (a₁, a₂, ... a_n)
2. Send 0.00005460 to each a₁ ... a_n
3. Choose a brain wallet "b" with your full name (not an issue, bitcoiner who reuse don't care about privacy anyways) or something very easy to memorize. If address "b" has already transactions, use another phrase and repeat 3
4. Send a₁ ... a_n to b (brain wallet), don't care whether your satoshi are being flushed by the bots because you just do it once

Receiving bitcoins:
1. Enter your brain wallet phrase and navigate to "b". The inputs of the first transaction seen on blockchain are holding your secure generated a₁ ... a_n bitcoin addresses
2. Choose one from a₁ ... a_n
3. Receive

Sending bitcoins:
1. Open your client which contains the securely generated private keys of a₁ ... a_n
2. Send


#2

Using namecoin


Feel free to improve it if you think it's useful.

I implemented at : https://github.com/NicolasDorier/NBitcoin/blob/master/NBitcoin/MnemonicReference.cs#L91 (https://github.com/NicolasDorier/NBitcoin/blob/master/NBitcoin/MnemonicReference.cs#L91)
Basically there are 2 importants methods :

• Create, which create the mnemonic from the (Chain, Transaction, MerkleBlock, txOutIndex).
• Parse, which parse and verify the mnemonic from (Chain, Transaction,MerkleBlock,sentence).

Other Create/Parse methods are just additional overload that end up to the 2 main one.

The spec as is written is complicated to understand. I will reformulate that, however there is no incoherence when one parse and verify. (as you can see in my code, there is no "y0,y1,y2, zX")
I will send you some test vectors.

The goal of this BIP is to have untrusted block explorer resolving the "brain address" with a compact crypto proof, so it does not fit.

That makes sense. The 2nd case implies that outputindex is small enough - so we are not talking about a large range actually. With 3 different paths, you need to prove that there is no overlap. Basically, proving the unicity of the encoded value.

Edit: What I mean is this: http://en.wikipedia.org/wiki/Variable-length_code - Uniquely decodable codes

Other than the possibility of the random number generator not working correctly address reuse does not automatically "harm" anything.  It fully depends on the use case of the individual.  Many users realize a benefit of address reuse because of usability and transparency.  There is a general bias among the developers over what they perceive as "harm" concerning privacy issues.  Nobody should be "penalized" because they have a system that depends on address re-use if there are no other security issues surrounding that.  The developers should also not try to influence the code based on their personal biases over the wishes of many users.

Genesis mainnet : "near scrap six gauge"

Min checksum size : 20,
Actual checksum size : 22

Checksum component :
  block id : 6fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000
  txIndex : 00000000
  txOutIndex : 00000000
  scriptPubKey : 4104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4ce f38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac

Calculated checksum : f254d8424d94a4a4ab37f199504207442d15d20e1481f844e50b3be0f809e6e4


rawAddress before checksum :
00000000 00000000 00000 (21 bits)

after checksum :
00000000 00000000 00000|111 00100111 00110000 010 (43 bits)

encryption key:
10010011 10011000 0010

final address : (encrypted|encryptionkey|version)

10010011 10011000 00101111 00|100111 00110000 010|0 (44 bits)

Via BIP39 : "near scrap six gauge"

I'm not sure how to prove but it looks quite obvious.

y is a function of y1 and y2
y1 is a function of blockHeight
y2 is a function of w, x, c
Since blockHeight, w, x, c are all known value, there is only one possible value for y

Again, z is a function of z1 and z2
z1 is a function of blockHeight and txIndex
z2 is a function of w, x, y, c
If these values are all known, there is only one possible value for z
(Obviously, you can't determine z before y is determined)

Maybe someone can try to find a counter-example

Assuming minimum checksum of 19 bit, the first output of the generation reward could be encoded by 4 words until this scheme overflow at block 8,388,607. An extra bonus for miner

Other example : I took txOutIndex = 1 of 4a85f6cc29aca334c1a78c5db74b492b741e67958aee59ff827c4c0862f4fbc1 (that's me !)

txOutIndex = 1,
txIndex = 597,
blockheight = 327535,

Min checksum size : 20,
Actual checksum size : 20 (geez at 1 bit I would stepped up 1 words)


Checksum component :
 blockId : d99211bfbc1efcdbf6787b54c2ce614adcf54049d1ce90170000000000000000
 txIndex : 55020000
 txOutIndex : 01000000
 scriptPubKey : 76a914356facdac5f5bcae995d13e667bb5864fd1e7d5988ac

Checksum : 34daf60a9d3bb907f8f9a36321ec36c9bfdaa1c8c178c73aa30d60c5b67e411c

RawAddress before checksum :  (10 bits for txIndex -967 tx-, 3 for txout -4 txout-)
01111011 01111111 10010|101 0101001|1 00 (34 bits)

After checksum :
01111011 01111111 10010|101 0101001|1 00|000111 00010000 010111 (54 bits)

Encryption key:
00011100 01000001 0111 (20 bits)

Final address :
01100111 00111110 11100100 10010111 00|000111 00010000 010111|0 (55 bits)

BIP39 : "grunt warm chair athlete alarm"

I think we should remove a few bit from checksum we are almost stepping up 6 words which start to be hard to remember.

To avoid 6 words users should always "register" their address with the first output.

For the checksum bit issue I think we need comments from more experts. Changing to 19-bit may be a good idea as that will secure at least one 4-word address for each block. Miners may earn some service charge by putting their client's output in these prestigious positions.

I'm encoding it wrong...  4 should be "11" not "100", so I can squeeze out a bit.


The size of the brain address depends on the number of transaction in the block and of the number of output in the block. It does not depends on the position.


How so ? 19 + 21 + 1 = 41, if the miner wants such small addess he needs txIndex written on 3 bits, or 8 address in his blocks.

It does depend on the position. Try to encode the first output of this tx: https://blockchain.info/tx/bddc5f6c9fe232110d11235df76814ae3a0f9b7286bb991294310cae03384a4e

The raw address without checksum is
00110101 00001001 01010|000 00000000| 0000000
Calculated checksum is 26.

6 words. "arm voyage width veteran palm tattoo"

I keep forgetting that it goes back to the beginning. Then there is no problem.

mh, while I was coding and you talked, I guess I did not see you found a way to encode txIndex and outputIndex better.
Trying to reread all of that. In my implementation I using ceil(log(txCount;2)

There is something wrong with your code

It is txIndex 0 and outputIndex 0, so
y_min = ceiling(log(txIndex + 1, 2)) = 0
z_min = ceiling(log(outputIndex + 1, 2)) = 0

w = ceiling((x + ymin + zmin + c + 1)/11) = 4 (if c is 20)

y1 is a big number because there is a lot of txs, but y2 = 11w-1-x-c = 2, and it is not smaller than y_min, so y = 2;

z1 is a big number because there is a lot of outputs, but z2 = 11w-1-x-y-c = 0, and it is not smaller than z_min, so z=0;

so it could be done with 4 words, including 2 bit of txIndex, 0 bit of outputIndex, and 20 bits of checksum

I'm understanding now how you want to encode y and z !
Good job, this is awesome !

Modifying my code...

I don't have a rigorous proof but I believe this is not only a one-to-one function, but also the most efficient way to encode.

Assuming a minimum checksum size of 19, in every block before 1,048,575, there must be at least 4 4-word addresses: the first output of the first 8 txs in the block

After block 1,048,575, only the first output of the coinbase tx is 4-word.

How the current implementation addresses the following criticism?


The current implementation does not restrict the type of output. It applies to any scriptPubKey. So people may, for example, 'register' stealth address with OP_RETURN. This implementation could also replace txid in daily use. It is even better than txid because it directs to a specific output in a tx.


With adequate checksum bits, the odds of successful lookalike attacks is extremely slim. Even a miner could not try to mine a "vanity address" because they have to discard successful block hash for such vanity address mining (blockhash is part of the checksum)


A reorg will make the checksum invalid. The address is safe to use even with only 1 confirmation. As mentioned, it is not possible to mine a vanity address


It is SPV verifiable. In practice, an SPV client will ask a centralized service to resolve, and to provide the compact proof


People could do it when they are doing real transaction, so the marginal cost and harm is lowered

I'll implement that during next week + provide a public service that other people can play with it.
I'll also copy your BIP + what we talked about on github.

I'm thinking if we should allow encoding of tx inputs with this scheme. Not sure if it is really useful. It could be done with 2 ways:

1. Put all inputs behind outputs. If there are 6 outputs and 3 inputs, index 0-5 will be the outputs and 6-8 will be the inputs. This won't affect the length of output addresses but input addresses may need more words.

2. Use 1 bit to denote input/output. This may increase the length of output addresses

I think we should make another BIP if we want to extend on inputs.

Let's not forget that this BIP is for people to remember a payment destination.
I don't see any usecase where someone would want to rememember an input.

Even if it is the case, we should make a new BIP because we don't have the same security requirement for referencing TxIn, so we would be able to remove most of the checksum.

great you remembered your address.  what about your private key?  isn't that a bit more important?

That's just not the point of this BIP. BIP39 already deals with that, and you can't compress the private key as an address.

Wow this is useful, but too hard for me to remember.
Good to know tho, ;)

Since you make the 'reference' transaction, you can make one that has a low number of txo. Let's say your txo index has to be < 4. 2 bits are enough to encode that offset. You want 20 bits of checksum so txo index and checksum fit in 22 bits or 2 words.

The block height is encoded with a continuation bit and either 20 or 31 bits for a total of either 21 bits if height < 2^20 (~1 million) or 32 bits if above but lower than (2^31). Add the version bit and it comes exactly to either 2 or 3 words.

TxIndex is simply encoded as words.

Recap:
# first part
- version bit: always 0
- length indicator
    - if 0: use 2 words
    - if 1: use 3 words
- block height

# 2nd part - always 2 words
- txo index: 2 bits
- checksum: 20 bits

# remaining words
- tx index

For any reference tx below index 2048 before height 2^20, it is guaranteed to be 5 words. The format is pretty constant and doesn't rely on txcount or the number of txo in the reference tx. Moreover, generation and parsing is straight forward.

Without the ability to encode all outputs in the blockchain, the use of such mnemonic address is highly restricted. For example, people may want to use a mnemonic address to replace txid in daily use but the outputindex may not be <4. One particular useful case is for stealth address payment. The payer may use mnemonic address to help the payee to locate the output

If your BIP wants to cover every tx output, I agree with you.
However, it was under my impression that the original proposal was about remembering an address that you previously set up.

An implementation in F#

The goal is to express the bitcoin address of someone in 4 words, given that it is on the blockchain.
The BIP morphed into a general way of referencing any output. Which is compatible with the initial goal, and do not require a special "publishing step" for things already in the blockchain.

hhanh00, I like the fact that your proposal needs less words and is easier to implement though.

If people want to use mnemonic address to reference a txid, then I would say that the limitation of the txo count does not matter.
If the user knows that it is a transactionId, he will just ignore the 2 bits of txoindex.

Do you see another use case which might limit the usage ?
It is true that mostly what is published in the blockchain today use less that 4 txo, would we severly limit use cases by using a fixed 2 bit for txo index ?

With checksum=20bits and blocks with =< 2048 txs, my proposal already guarantees a 5-word address for the first 4 outputs of any tx, same as hhanh00's. If your code gives you a 6-word address, there must be something wrong.

I can't see any reason not to allow people to encode the 5th output. With techniques like coinjoin, future transactions may have many outputs. Bitcoin is in its infancy and we won't know how people will use the blockchain in the future.
 

My code was wrong, I was using log(txcount;2) for encoding.

The only reason I see is the word size. Ease of implementing is not a big deal though, just a nice to have.
But I read too fast hhanh00 proposal. Only the "2 or 3 words" popped to my eyes. So yes, I still prefer yours, I agree that having a way to encode arbitrary output (not just 4 first) justify by far the added complexity.

In my case, the txIndex <= 2048 guarantees 5 words regardless of the number of tx in the block. Could be the same for yours but I haven't checked.

PS: You can try it out online at https://www.fpcomplete.com/user/hhanh00/adopted/txencoding

Actually I found a great way ;D (but I don't suggest it. don't use it if you don't know what you're doing)
Here it is;
Private key's WIF wallet format starts with 5 and aditional 50 chars right?
So I've manually created this priv key: "5karartma1karatma2karartma3karartma4karartma5karart" (you got the logic) and this priv key refers to; 19Er7sHyYjXFankLwfv9Xxm5T3X4QxcbKY

Well, basically I'm saying; don't try to remember address, remember it's priv key ;D

5karartma1karatma2karartma3karartma4karartma5karart

This is an invalid WIF private key.

(you did notice the guy has an ad sig post and so is just posting to get his count up?)

This topic is about Bitcoin addresses not private keys.

According to blockchain.info wallet, it's not. I imported it and wallet accepted it. But I didn't try to send btc yet.
edit: I've sent some btc to it; https://blockchain.info/tx/eb982663b019abc759b7b1853efda29786159ddc98013ed6058104f94d7e6563
if you like you can import it and clear the balance ;)

If you're thinking that, I'm "sig spammign" you should use the "Report to moderator" link under the message ;)

Bitcoin addresses are generated according to private keys. You're tied up to private key to create a memorizable key.
Let's say you may try to create 1CIYAM1234567.... which is easy to remember. But you need lots of computer power to get kinda address.
Basically we may say you can't create such an address. (All bytes should be chosen by you).

If you can't create an address you like, Then why don't you just remember the priv key? "which you can clearly remember".

Not the point of this BIP. The goal is to remember a payment destination that you can share with others.
If you attempt to create a private key that can be remembered, then you will loose your money. Simple as that.

I like OpenAlias for this.

its coin agnostic and uses DNS: https://openalias.org/

but it doesnt solve the address-reuse problem gmaxwell mentioned.

The private key is certainly invalid. One more reason NOT to use blockchain.info wallet (and they are delisted from bitcoin.org already)

It does please re-read what we talked about.
You solution involve trust relationship.

its just a dns record.
dnssec may be used by shops and private persons may use namecoin.

dnssec still has a trust relationship; bit domains dont.

This is just not the point of this BIP. We don't want any registration process on another alt chain nor alt database (DNS), and want to be verifiable by current SPV wallet easily.

i don't want to criticize your work and i think it is very interesting from a technical point of view.

its just not usable (for me).
all "normal" persons wont never remember multiple words nor an address (they would ctrl-c both).
add the address-reuse problem to this and please tell me: what do you actually want to solve (means: use-case)?

The response to this question is the same than this one : "Why everybody remember its own mobile phone number ?"
For those same reason we create this BIP.

I pointed out a simple use case as to why I like this idea.

You are "out and about" and have an opportunity to say exchange some BTC for some fiat (person to person) but you don't have your computer handy.

If you can use a system like this then you can find a payment address just from memory (rather than copy and paste).

Firstbits was a way to do this (but has now been abandoned) so this is another idea (and yes I am well aware that re-use of addresses is not advised).

Of course if we all have apps we trust on mobile phones to store our payment addresses the point is probably mute (so just how needed this idea might be is hard to say).

But still if you have two separate computers (and no ability to use QR codes) then having an easier way to "type in the address" can be useful.

maybe its just me, but i would not trust my brain remembering the words correctly.
a checksum (as planned) is a good idea.

i just compare it to the amount of phone calls i get from people who didn't intend to call me in the first place.

but i am unsure: so lets see. a BIP is not a bad idea at all; if it gets accepted by "normal" people everything is fine. a solution only for btc-enthusiasts seems unnecessary.

Even with that, it won't work.
Wallet providers would not develop coherent integration between all trusted payment address stores of the market.
The matter is different when trust relationship is removed, we can get a coherency accross all bitcoin applications.

If your payment destination on Coinbase is "CIYAM". Sure you can remember CIYAM easily.
However, your payer must use a software that integrate with Coinbase.

By only using the blockchain + compact proof, then all software supporting Bitcoin can support this protocol without any additional trust need to multiple trust parties.

Exactly the reason why people remember their mobile phone number. Except that you replace "opportunity to exchange some BTC" with "opportunity to get the pretty girl". ;)

We'll see, accepted or not this will be implemented. We'll see if people use it.
My point is that people remember the 10 digit of their phone number, and there is a reason for it. "Being Geek" is not the reason why they are doing it.

Encode (blockheight, txIndex, txoIndex, pubScript) into a list of numbers between 0 and 2047.

Preconditions: txoIndex < 4

The result is the concatenation of three sub lists that encodes each part
## blockHeight
- The blockheight split into blocks of 10 bits, least significant block first.
- All blocks except the last one has its most significant bit (11th bit) set to 1

## txoIndex and checksum
- The DSHA-256 is calculated over the pubScript
- The first 2 bytes + 4 Least significant bits of the 3rd byte are kept, giving the 20-bit checksum
- The txoIndex is appended
- The 22 bit result is split into two groups of 11 bits

## txIndex
- The txIndex is split into groups of 11 bits, least significant byte first

# Transform the list into words

Notes:
- There is no version bit. The context should make the version clear. Alternatively, when
the encoding needs to change, a different list of words can be substituted.
- No limit on the blockheight
- For the first 2^20 blocks and txIndex below 2^11, the scheme results in 5 words. It is independent
from the actual number of transactions in the block
- The encoding is essentially a combination of a variable length integer with continuation bit, a fixed record and a variable
length integer.
- The checksum only covers the pubscript. The goal of the method is to locate a particular address or more generally a
particular pubscript. The blockHeight, txIndex and txoIndex provide the 'coordinates' of the pubscript and the checksum
makes sure that it is the right one. If there is a block reorg, the decoding will retrieve a different pubscript and the verification
will fail.
- The encoding is a pure function. It only takes the location and the content of the data. No need for other information from the blockchain.
- The result is not further encrypted. It is a public scheme.

I'm a newb in Haskell so this is probably not idiomatic:

It is an impossible task to find 2048 completely different and easily memorable words


I think 8 million blocks is already "no limit", and it's likely to have a hardfork that will obsolete any current address scheme


It is the only benefit but the cost is to strictly limit the use of such address and ignore many sophisticated use of the blockchain.


Please refer to gmaxwell's criticism in the first page. Without covering the blockheight in the checksum, a miner could mine a "vanity address" without any cost. If the incentive is big enough (e.g. the address is "best adult adult adult web"), miners will fill the block with garbage and orphan other people's block in order to grab it.

Inclusion of txIndex and txoIndex in checksum is for different use case. In some application, e.g. smart-property, the position of the output could be as important as the scriptPubKey.


Any addresses of this kind are meaningless without information from the blockchain. And the complexity added is completely transparent to end users. No one is expected to encode or decode it by hand.

I beg to differ. Our vocabulary exceeds 10 000 words. Besides these words are not so memorable (at least for me) and I'm not sure they were meant to be.

It's quite big enough. But omitting the version bit simplifies the encoding.

We have different use case in mind.

An address points to a very specific location and one would have to be quite clever to produce a correct spot. Then he would have to mine the correct script and work with the miner to get the spot. I think he deserves that spot.

From a coding point of view, having fewer dependencies is good.

Eventually, people will vote for a BIP with their wallet ... app. It seems that we reach a point where we understand the pros/cons of each scheme. So I wish you good luck with your BIP and hope that it will be a big success.

hhanh00, I don't really understand the pros of your scheme right now.
Except the block limit. It does not seems to be more compact. Maybe more easy to implement, but with good test vectors we should have no problem's with jl2012's scheme.
I agree. And if there is another version of the scheme the checksum will be able to detect if it's a valid address mnemonic or not anyway.
I don't understand this argument. Can you details ?
This is true, but I will only implement one of those in NBitcoin. If the market choose the other scheme I will adapt, but the wallet app most of the time rely on what their Bitcoin framework offers.
I just want to find the most compact way of doing it.
Why does the encryption is a problem ?
The way jl2012 does it provide an uniform distribution on the probability of each word of occuring, which is a nice thing to have.

hhanh00, Your way of doing does not seems more compact but is also less flexible, can you provide a clear pros/cons list ? because except ease of implementation and block limit, I don't see anything.

hhanh00's scheme guarantees 5-words address for the first 4 outputs in the first 2048 tx in any block, regardless the number of tx in the block
my scheme guarantees 5-words address for the first 4 outputs in any block with =< 2048tx (similar but a bit less efficient)

However, the cost of the extra efficiency is:

hhanh00's scheme works only with the first 4 outputs in any tx
my scheme works with any output in any tx

-------------------------------

Since the address is only 44-77bits, dropping the version bit may lead to unintentional birthday attack between the old and new schemes: http://en.wikipedia.org/wiki/Birthday_attack

i.e. An address is valid in both schemes but interpreted differently

Any mathematician to explain?

In that case, you need something like  oldscheme://web-satoshi-away-load  and newscheme://web-satoshi-away-load  , essentially adding 1 more bit to the address externally

Your scheme save bits if the address is on the first output. (it can be encoded in 0 bits)
If we strip out the version bit, then we earn a third bit.

So it would push the limit to =< 16384. Alternatively, I think we can squeeze the checksum a bit.
Even if Bitcoin becomes an overnight success, one can publish an output multiple time on the blockchain to increase the odd to be in a block with few transactions.

Yes, it guarantees 5-words address for the first output in the first 8192 txs in any block, regardless the total number of tx in the block.
-----------------
The version bit may be removed but be prepared to externalize it. It could also help implementing the scheme to alt-coins. We may have something like:

bitcoin:load-road-road-load-road
litecoin:road-load-load-road-load

and in the future, after a significant hardfork, we have

bitcoin2:load-road-road-load-road, which will be interpreted differently

Not sure if this is a good way to go

I don't think it is useful at this point to format the mnemonic into an url.
If there is an url, the user is mostly clicking on that or put it into QR code, and in both case would not need a mnemonic.

I thought you guys were headed towards a consensus - but now we have two ideas?

It is not about URL. If there will be any update with this scheme, without a version bit, future users has to tell people whether this is a version 1 or version 2 address. Otherwise, birthday collision is very likely: an address (with or without checksum) being perfectly legal in different schemes

People are always free to propose different ideas. I just want more people to comment and criticize.

To be honest it is now confusing exactly what is on offer (it got rather technical and I didn't have enough time to delve into it).

Perhaps a simple summary of the two options could be provided?

There are many dimensions:

1. Do we want the ability to encode all outputs in the blockchain, or just some of it (say, only the first 4 outputs in all txs)? hhanh00's scheme is easier to implement as it only encodes the first 4 outputs in a tx. My scheme is more complex and the length of all components are variable.

2. hhanh00's address is shorter than mine in some case, while the opposite in some other case.

3. How many bits of checksum is needed? I proposed 20bits so the error tolerance is about 1 in a million. Should we use more? Could we squeeze a few bits for other purpose? (Satoshi used 32 bits in standard bitcoin address.)

4. Do we need a version bit (like in standard bitcoin address)? It will occupy 1 bit (which could be otherwise used for other purpose. In order to keep the address short, every bit is very valuable) but it makes potential future upgrade easier. Otherwise, future upgrade will need to use 2048 completely different words, or people have to denote the version of the address externally (e.g. using a URL like header)

5. Do we want miner to have the ability to mine a vanity address? My scheme disallows it in response to gmaxwell's comments (see first page). The other scheme allows miners to mine vanity address.

6. Do we want the addresses look like random (i.e. outputs/txs close to each other will have statistically unrelated addresses) or not?

Thanks for the summary:


I guess the "target audience" is what matters (for me 4 outputs would be fine as I would be using it for "cold storage" which would have generally only 1 output anyway).


I think 5 "words" is fine (whichever approach).


As many as possible without adding an extra word.


A version bit seems reasonable to me.


I am not quite sure of the implications of this - but it would be better to probably not allow it.


If the point is to help someone remember the address then random is better so they don't get confused IMO.

My scheme allows users to choose. If you want the shortest possible address, always put your interested scriptPubKey as the first output. If you have some special reasons (e.g. when using smart property which the order of outputs is material), you can use my scheme to refer to any outputs on the blockchain.


Basically, 5 words is guaranteed in most cases for both proposal if the 1MB block space is not increased.


You are begging the question: in my scheme, the only way to ensure no extra word is to use 0-bit checksum.

So go back to the question, how many bits of checksum is needed?



The implication is a miner may try to fill up a block with garbage in order to grab a vanity address. It also offers extra incentive to orphan other people's block.

copied your bip here : https://github.com/NicolasDorier/BIP-MnemoReference/blob/master/bip-mnemo.mediawiki
I can give you git access if you need to.

I'm implementing it on NBitcoin, it seems to work.
I'm testing more deeply, and try to generate some test vectors.

I rephrased your spec to be more easy to understand and implement.
I also based my implementation on the spec notation, so it is easy to implement on other language by copying my code.
Tell me what you think about it.

I think someone should start a service where someone can store their bitcoin address online

and get a personalized short link that they can open anywhere and get the address they stored there

I don't understand why we cannot use namecoin for this, instead of polluting bitcoin blockchain with unecessary bytes and adding OP_RETURN.
Also if suppose you want to change the name with which you refer the address with , you can do that as well on namecoin . And it will take care of name conflicts as well.

If you are concerned about centralization , you can query a few namecoin nodes or run your own node.
Is there a major reason for not using namecoin ?

I would very much doubt that the developers of any major Bitcoin wallets are going to include support for Namecoin anytime in the near future to accomplish what this topic is about so proposing its use here doesn't seem to make much sense.

As CIYAM said, implementing a wallet only for bitcoin is complicated enough, having two blockchain is overkill for what I want to do with the BIP.
I also don't want the hassle to host nodes for several blockchain on mobile devices, this is development overkill.

What I am proposing does not require any alt chain, and would works fine with current SPV wallets. (no much dev)

Took time to read through most of the comments. This looks quite promising theoretically , specially how you have avoided user typing wrong Mnemonic code

One thing , I was thinking is about the practical application of this:

• Crowdfunding address: I was hoping it could be used here, but unfortunately I think crowdfunding funding websites would rather prefer vanity addresses than this. Say I have a website called bitcoinkite , I would prefer something like KiteybXcBLb1EdJHzULptUws4haRwamuS  rather than "arm voyage width veteran palm tattoo" which would be totally unrelated to my product
• Personal exchange of address: This is when I send someone my address and tell him to transfer money to it. So in this case I would probably copy paste the address and send it to that person. In this case I would use mnemonic only if:
  
  Quote
  cost of remembering the Mnemonic <  Number of times I reuse this address * cost of copy/pasting the address
  Since I don't trust my memory most of the times , I would have to reuse the address lots of times to make this any helpful
• Memorization incentive/ Personalization: You are forgetting that I have no motivation to memorize a random mnemonic . This is the reason people choose passwords that are more personal. So if the Mnemonic is my favourite song , then I will remember it. Already people are having hard time remembering the ten different password. It doesn't give me any incentive memorization a totally unrelated Mnemonic. I would rather copy paste my bitcoin address, since I would anyway use not use it more than 5-6 times. Note, that we cannot use a phone number analogy here. Inspite of random digits people will force to remember phone number, since they know that they are stuck with it for next year or so.

So this is only useful if I massively reuse my address, say for next 6 months , say I keep giving same address to anyone I speak to . This definitely is not encouraged as everyone pointed out already.

Are there any other applications of this ?

I bet you memorize your phone number ? why  ?
Well, people remember the 10 digits of their phone number, so 4 words seems not a big deal.

Also how do you transfer would you transfer address over the phone ? how do you transfer it when you don't have your btc wallet with you ?

This has been responded, such address can point on a OP_RETURN that have a payment address (BIP70) or a stealth address, which would fix address reuse problems.

I don't know more about this but I think no ways is easy to remember it

Bitcoin address must be used as copycat as per bitcoin wiki. It means there is no need of remembering it. For checking whether using the correct (my address of some's address) I usually remember last 3 characters.

I think that there will not be easy ways to remember Bitcoin address and honestly you don't need to remember it and shouldn't remember it.

Just save it

There is.

Why, then, everybody remember his own phone number ? Nobody gave me a response.

I also want know how to remember a bitcoin address ? ? Any great was ? If so, Please teach me how?Thx !

Like this : https://github.com/NicolasDorier/BIP-MnemoReference/blob/master/bip-mnemo.mediawiki (https://github.com/NicolasDorier/BIP-MnemoReference/blob/master/bip-mnemo.mediawiki)