Proposal: Base58 encoded HD Wallet root key with optional encryption

[justusranvier]

I think that the HD root is actually useless in absence of limiting assumption on its key use that allow efficient discovery of associated funds.

I think the best default structure is a case where the root is used to produced an unlimited number of first level children (in sequence), and each child produces a linear series of payment addresses (also in in sequence).

Each first-level child of the root seed is called a payment channel.

Payment channel 0 is the internal use channel. It's where the client produces individual receive addresses and puts change outputs.

Each subsequent payment channel is given to individual senders as an xpub.

If Alice wants to receive bitcoins from Bob, she generates the next unused payment channel and gives the the appropriate xpub to Bob. Now Bob always knows how to send funds to Alice without any further key exchange (TOFU security). Bob can now tell his client "send X btc to Alice" and the client automatically does the right thing, and Alice's client already knows which addresses to expect future payments at because both clients are being sane and increment indexes monotonically.

[grau]

I think that the HD root is actually useless in absence of limiting assumption on its key use that allow efficient discovery of associated funds.

I think the best default structure is a case where the root is used to produced an unlimited number of first level children (in sequence), and each child produces a linear series of payment addresses (also in in sequence).

Your suggested assumption is equivalent with mine with a look ahead window of 1. I think that is too strict and give you an example why:

Assume Alice generates addresses for bills as consecutive keys of a root (or sub-root does not matter). Most bills get paid a few not.

Now Alice loses her hard drive that recorded all transactions but has the HD root stored. With an look ahead window of say 10, she would re-discover bill payments even if there are some gaps in between them in her key space.

[justusranvier]

Assume Alice generates addresses for bills as consecutive keys of a root (or sub-root does not matter). Most bills get paid a few not.

Now Alice loses her hard drive that recorded all transactions but has the HD root stored. With an look ahead window of say 10, she would re-discover bill payments even if there are some gaps in between them in her key space.

I'm fine with configurable lookahead windows, but I don't see how that fits into your example.

Alice presumably is receiving bill payments from a large number of payees.

Each of those payees should be generating deposit addresses themselves from a unique xpub Alice gave each of them.

If a payee does not pay a bill one month, there's absolutely no reason at all they should skip ahead.

Alice should also not be specifying the addresses to which each payee should send payment for a specific bill.

[grau]

In other words, I could modify the spec to encode up to 4 passwords into the checksum instead of the double SHA256 of the private key. Any less than 4 passwords would be filled with 5 random bits of data in the checksum for obfuscation.

I like in the current proposal that it checks the validity of the key not that of the passphrase.

The passphrase could actually be BIP39 input, then you have pronounceable passphrase for the real or any brute forced alternate password.
If brute forcing 32 bits is not feasible just reduce the checksum length.

[grau]

If a payee does not pay a bill one month, there's absolutely no reason at all they should skip ahead.

Usually it is not the payee who generates the addresses, but the one issuing the bill. It is also natural to associate 1-1 a bill with an address, as also the payment protocol suggests.

[justusranvier]

Usually it is not the payee who generates the addresses, but the one issuing the bill. It is also natural to associate 1-1 a bill with an address, as also the payment protocol suggests.

Then the payment protocol is broken and wrong from a privacy and commerce perspective, probably written by somebody with no business experience in net D billing.

The person issuing the bill has no idea how many transactions and addresses the payee needs to use to make a payment and shouldn't care.

[justusranvier]

Let me give you an example based on how companies actually do business in the real world. When factory A's maintenance department orders supplies from Grainger, Grainger makes no assumptions at all about how that invoice will ultimately be paid. It might be paid all at once in a single payment. There might be multiple invoices outstanding and the factory cuts a single check that covers all of them. There probably will be be a many-to-many relationship between the number of invoices and the number of payments.

Any accounting system that assumes a 1:1 invoice to payment relationships is hopelessly broken in the real world and should be discarded. Don't build that kind of brokenness into a protocol from the very beginning, especially when there are real negative privacy implications associated with doing so.

[grau]

Let me give you an example based on how companies actually do business in the real world. When factory A's maintenance department orders supplies from Grainger, Grainger makes no assumptions at all about how that invoice will ultimately be paid. It might be paid all at once in a single payment. There might be multiple invoices outstanding and the factory cuts a single check that covers all of them. There probably will be be a many-to-many relationship between the number of invoices and the number of payments.

Any accounting system that assumes a 1:1 invoice to payment relationships is hopelessly broken in the real world and should be discarded. Don't build that kind of brokenness into a protocol from the very beginning, especially when there are real negative privacy implications associated with doing so.

I agree that more than one transaction might be used to pay a bill, but do not see how that disallows that those transactions send to the same address.
I also do not see the privacy violation you claim this imposes. What did I miss?

[justusranvier]

I agree that more than one transaction might be used to pay a bill, but do not see how that disallows that those transactions send to the same address.
I also do not see the privacy violation you claim this imposes. What did I miss?

I don't even know where to start if you're not already aware of the reasons why addresses should never be reused. That's pretty fundamental to the blockchain model.

http://bitcoin.org/en/bitcoin-for-developers

You should never use the same address for more than one transaction.

https://bitcointalk.org/index.php?topic=334316.0

http://coinconsultancy.com/2013/07/10/reclaiming-financial-privacy-with-hd-wallets/

http://www.coindesk.com/merge-avoidance-privacy-bitcoin/

[grau]

I agree that more than one transaction might be used to pay a bill, but do not see how that disallows that those transactions send to the same address.
I also do not see the privacy violation you claim this imposes. What did I miss?

I don't even know where to start if you're not already aware of the reasons why addresses should never be reused. That's pretty fundamental to the blockchain model.

http://bitcoin.org/en/bitcoin-for-developers

You should never use the same address for more than one transaction.

https://bitcointalk.org/index.php?topic=334316.0

http://coinconsultancy.com/2013/07/10/reclaiming-financial-privacy-with-hd-wallets/

http://www.coindesk.com/merge-avoidance-privacy-bitcoin/

You must be joking. I leave this as is as this is off topic here.

[justusranvier]

You must be joking. I leave this as is as this is off topic here.

Ok, now I'm really concerned.

You're seriously saying you don't see why two transactions in the form (A->C, B->C) have a privacy problem that the two transactions (A->C, B->D) don't have?

[grau]

You must be joking. I leave this as is as this is off topic here.

Ok, now I'm really concerned.

You're seriously saying you don't see why two transactions in the form (A->C, B->C) have a privacy problem that the two transactions (A->C, B->D) don't have?

You used to be a nice chap, so I put aside my embarrassment that you think I would not understand the basics and attempt to elaborate:

Yes, re-using addresses is bad in general and should be avoided if done for no reason, but is not a dogma.
In case of a bill where the address is generated to collect payments for that bill, I see no problem with it. But even if you would want to address that one could create more than one address for a bill that the payee can chose from. Still I think that the person who creates the bill should be in control of where he wants to receive the money and not hop that the payee makes some sensible choice out of a huge range he has to potentially monitor.

[justusranvier]

Yes, re-using addresses is bad in general and should be avoided if done for no reason, but is not a dogma.
In case of a bill where the address is generated to collect payments for that bill, I see no problem with it. But even if you would want to address that one could create more than one address for a bill that the payee can chose from.

You're vastly underestimating the problem.

Actions which reduce privacy are, by the nature of the blockchain, permanent and their ramifications are not always apparent at the time of the event. Actions today which may seem to be no big deal are only going to grow in severity over time as blockchain analysis techniques get more advanced. Dogmatically avoiding address reuse is the only responsible policy. It's not sufficient to ensure privacy but it is a minimum necessary condition.

Putting control over privacy in the hands of businesses who hand out invoices guarantees it will be destroyed because many businesses are privacy-hostile or just don't give a shit. The only possibility of having good behaviour on the network is if the required actions are under the control of the payers, not the payees. This is where control over privacy should properly reside anyway because it leaves both sides free to choose how much privacy they do or do not want. A payee who receives unmerged outputs to distinct addresses is free to merge them if he or she wants, but a payer who is only allowed a single address to pay to has someone else's privacy police imposed on them unilaterally.

Still I think that the person who creates the bill should be in control of where he wants to receive the money and not hop that the payee makes some sensible choice out of a huge range he has to potentially monitor.

The attack vector you're describing exists no matter how many addresses are used for a transaction. A malicious customer could send 1000 separate outputs to the same address just as easily as he should send 1 output to 1000 separate addresses.

[grau]

I understand your concern and support any remedy to it to the extent it is feasible - means can be implemented efficiently.

Both of us propose unique addresses per bill. Now let's review the choices:

1. The creator of the bill (business) presents the address(es) - This is potentially bad for the privacy of the payee since it could be poorly chosen such as: recurring, customer linked or master public key leaked.

2. The customer pick the address(es) - This is potentially bad for the business since it could reveal its revenue to competitor if customer re-uses or leaks the master public.

Whoever creates the address has the means of hurting the privacy of the other.

You value privacy of the customer higher and I sympathize with that, but do not support it for pragmatic reasons, that are:
The customer will likely use simpler software and several devices. Chances that he is not tracking the sequence numbers correctly or is leaking the master public are good. There is also a scale issue. If one assumes that businesses have magnitudes more customer than the number of businesses a customer deals with, then it is likely that 2. would magnify the effort on monitoring and reconciling payments on the side that already has the bigger problem.

[justusranvier]

2. The customer pick the address(es) - This is potentially bad for the business since it could reveal its revenue to competitor if customer re-uses or leaks the master public.

The customer doesn't have "the" master public key, they have one specific to them. At worst, they can leak the amount they, and only they, have paid.

There is also a scale issue. If one assumes that businesses have magnitudes more customer than the number of businesses a customer deals with, then it is likely that 2. would magnify the effort on monitoring and reconciling payments on the side that already has the bigger problem.

Any serious B2B or B2C business is already using net accounting that does not assume a 1:1 relationship between invoices and payment - if they weren't things would blow up all the time.

Think about it: a phone company issues a $50 invoice to a customer in November. The customer is late with the payment and hasn't paid by the time the December bill posts. Now he owes $100.

The customer can pay that as a $100 lump sum and the phone company's accounting system will have no problem whatsoever. The customer can even pay $75 when the December bill posts, and then $25 a week later. Their accounting system will have no problems keeping track of which invoices are paid and which are outstanding in either case.

Maybe I need to write up a guide to business accounting practises for Bitcoin developers as a blog post. Implementing net accounting is not hard, but if somebody naively implements accounting with an embedded assumption that for every invoice there will be exactly one payment things are going to fail hard for somebody when real life fails to live up to the requirements of their accounting model.

[grau]

I get your point with the net accounting, but do not think that it has to be solved with giving the customer the choice of addresses to use. The business can net across payments received and bills written and keep track of the outstanding amount also while generating addresses. Newly issued bills could also indicate and expect net outstanding amount on their address.

I look forward to your blog post. Please also address my concern there that the customer would need more sophisticated wallet maintaining his master public at the business and his last used sequence across his devices / wallet instances otherwise it converges to a more complicated, but equivalent model of the business providing the address.

[grau]

Since the last points I raised on-topic are important for a scaleable implementation, may I re-quote:

A HD root can generate 2^32-1 keys and any of these keys might be the root for a further derivation. Now assume you get a HD root and would want to determine the funds associated with it. It is not feasible to find them in absence of assumptions. I suggested some assumptions I keep while developing HD wallets.

Assumptions:

1. : the root you have identifies leafs of the hierarchy. If not then use the same assumptions on the sub-levels on-by-one.
2. : if key(n) derivable from the current root is first used in block b then key(m) | m>n is not used in block d | d < b.
3. : if you do not find a use for key (n) then there is no use of any key (m) | m > n + w.

You might not like to have the assumptions, but I think they are sensible. I can not see how you implement scaleable discovery of funds associated with a root without these or similar assumptions.

If brute forcing the checksum for an alternate password is not feasible with 4 bytes then reduce the checksum length instead of introducing a more complex concept.

I think that the HD root is actually useless in absence of limiting assumption on its key use that allow efficient discovery of associated funds.

I suggest to include the start key sequence (n) corresponding the key birth date and the size of the look ahead window (w) into the proposal. A wallet should seek to limit the expansion of the key set during the scan by spending older outputs and re-set n with birth date whenever possible. 4 bytes are needed for n, 2 bytes should be sufficient for w.

[justusranvier]

otherwise it converges to a more complicated, but equivalent model of the business providing the address.

If the business tells the client the next unused index value each time it sends an invoice that would solve the problem you describe without removing the client's ability to choose how many new addresses to use

[grau]

otherwise it converges to a more complicated, but equivalent model of the business providing the address.

If the business tells the client the next unused index value each time it sends an invoice that would solve the problem you describe without removing the client's ability to choose how many new addresses to use

The business would also have to re-tell the master public in case the customer does not have it at hand and we are back to square one.

[justusranvier]

The business would also have to re-tell the master public in case the customer does not have it at hand and we are back to square one.

Not really. An xpub + index hint does not restrict the customer's client in the same way a single address or static list of addresses restricts the client.