|
BTW even instantiating 2^32 addresses is a significant task (2^32 HmacSHA512 + 2^32 * EC add + 2^31 EC multiplication + 2 * SHA256 + RIPEM160) then you have a few hashes to look up a bloom filter of 4 GB to identify 1% false positives, that is 42 million
random accesses to a database.
And all you have with that are transactions that deposited to the address. Then you need further passes to find those transactions spending those deposits.
go for it.
|
|
|
|
I think it's impossible to enforce that addresses are used in sequence, considering that customers won't pay in sequence, refund addresses given to suppliers could be funded months after issuance, etc.
Assuming that the master public is not disclosed, then it is only the owner of the master key capable to add to the set of known members of the sequence. He can impose a maximum gap by not disclosing more than w new addresses until one of them is used on the block chain. So how would you scan the blockchain to reconstruct the tree? Well, it's an issue of scale mostly. Using lookahead windows is a quite narrow view and will cause problems very quickly.
So instead, construct a bloom filter that will filter the blockchain a few days since birth of the root key. Constructing a bloom filter that scans for a million possible addresses would take 1,198,132 bytes, with 6 hash functions for a false positive hit rate of 1%. No need to keep all those addresses in memory.
Second, you can construct a hash table with a 4 byte partial hash of the address as key, that will then give you the hierarchy where the key lives. If you get a hit on the hash table, you can then reconstruct the branch and do a full address match. Should it hit, you can keep the branch in memory, and even expand your coverage, should the address live near an edge of the tree currently in the bloom filter / hash table.
Even if you were to expand this to 10 million addresses, you'd still only need 11,981,322 bytes of memory for the bloom filter. The hash table is a little heavier, but is still quite manageable.
In other words, this scales quite well and does a far better job at finding relevant transactions than any kind of window based scanning can ever do.
We have not a 1 or 10 million possible addresses but 2^32 that is 429 times 10 million. Scale your numbers accordingly. Also keep in mind that retrieving those 1% false positives is not cheap plus lookup is usually not just for transactions benefiting an address but for transactions that spend that output. I think you will revert to the suggestions after you attempted to implement a HD scan. I did. |
|
|
|
There is an other reason why the receiver has to provide a payment address with the bill: By doing so, receiver declares that he is in (exclusive) control of the key that belongs to that address, so a payment made to that is received by him. It is not deniable. The receiver however has to be able to revoke that declaration for the future, since he might lose keys or might have legitimate reasons for using a new master key generating the addresses (be it for performance or a merger). The simplest way of implicit revoke is to agree that with any new bill, and new address with it, all previous addresses are no longer valid for payment. There should also be an explicit expiry for the bill, so a new one with new address is issued if the previous is not paid. Add the requirement that new bills should indicate net outstanding amount and the option that a bill could offer more than one new address and we are all happy. Last message on-topic: https://bitcointalk.org/index.php?topic=258678.msg4180842#msg4180842 |
|
|
|
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. I do not see the fundamental difference between xpub + index and an address list to choose from. The business has to limit the index range it monitors for performance reasons, that is effectively giving an address list. Actually the business has to send xpub with every bill otherwise we would need yet an other more complex protocol for key revoke in case previously used key was compromised. I think that for reasons of performance at the receiver side, simplicity and privacy at the payee side, it makes sense that the receiver generates a choice of addresses valid for any payment starting with the time point of that bill. And yes, receiver should track outstanding amount by netting all previous bills and funds received on any address previously communicated. That however is a requirement of bookkeeping either. |
|
|
|
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. |
|
|
|
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. |
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
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. |
|
|
|
You must be joking. I leave this as is as this is off topic here. |
|
|
|
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? |
|
|
|
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. |
|
|
|
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. |
|
|
|
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. |
|
|
|
|
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.
Assume you get a HD root where random child keys are used to store funds with, and even random child keys were used to start an other hierarchy level.. and so on. Now write an algorithm that finds the funds associated with that root in human timescale.
|
|
|
|
|
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.
|
|
|
|
Therefore I suggest to extend the proposal with a start key index (4 bytes) and a look ahead window (4 bytes).
Actually 2 bytes should be more than enough for look ahead. |
|
|
|
For plausible deniability it should be possible to mine an alternate password that create a key that passes the checksum as is.
If you mean mining a password on the current checksum (as currently defined in the spec), then you've got quite a bit of work ahead of you. Matching a 32bit checksum is a lot of work and the resulting password could be total gibberish and pretty hard to remember, not to mention that you're basically brute forcing the KDF, which is was chosen to resist such attacks. Or am I misunderstanding what you mean? Yes, its a lot of work, but doable and the denial is then rather plausible. If you think that is too big of a hurdle then reduce the checksum length. Awesome!  Storing the HD root is useful. Recreating the keys that are used on the block chain needs however further conventions, so it can be done in a scalable manner. Let's call the keys generated by the root key(0), key(1), key (3).... Now let us assume that if key (n) is first used in block b, then there should be no reference to key(m) (m > n) in any block before b. With this rule one can efficiently scan the block chain in a single pass using a look ahead window of w: Assume key(s) is used after block b (identified by the birth date of the root) and scan subsequent blocks. If any key (m) (s<=m<s+w) is used then continue scanning with w := w + m - s; from that block on. Note that the search window increases during the scan. A good HD wallet software would further optimize the use of keys such that it seeks to reduce the search window by spending outputs on keys earlier in the key sequence. It would seek to re-set first key index s with a new birth date. Therefore I suggest to extend the proposal with a start key index (4 bytes) and a look ahead window (4 bytes). |
|
|
|
|
For plausible deniability it should be possible to mine an alternate password that create a key that passes the checksum as is.
|
|
|
|
|
Show Posts
