I wrote a post on reddit somewhere back in January about something similar. It wasn't multi-party in, multi-party out, but one party in, multi-party out.

Here's a writeup how it would work:

Most financial relationships between merchants and suppliers, employers and employees, subscriptions, leases, mortgages, rent, etc ,etc, are long standing relationships. The vast majority of payments flow through these channels. And we can do some really smart things with these.

Let’s look at a website.

A customer selects a number of goods on a website and proceeds to checkout. He selects bitcoin as payment option. The web server now contacts the payment router and requests a payment request for $X. The payment router now looks in its local database of creditors and starts to query a number of them for partial amounts. A couple of seconds later they all respond and the payment router now combines these payment requests, signs it, and feeds it back to the web server. The web server presents this payment request to the user, user makes payment and done. For the next customer, a completely different set of creditors could be selected, etc. You get the picture.

We just settled a number of partial debts across multiple creditors with a single transaction. Not only that, but for all we know, those creditors did the same thing and also forwarded the request to one or more of its creditors. So it could very well be that we went several hops deep (depending on the allotted time, I’m sure prefetching could work here as well).

The velocity of those coins just increased significantly.

And there are other advantages too:

- Number of transactions is reduced, reducing pressure on the blockchain;
- Large part of the debt settlement between multiple parties is now extracted out of the transaction chain, increasing privacy amongst all participants;
- No changes needed to user wallets to make this work. BIP 70 support is enough;
- No changes needed to Bitcoin either, it’s all just plain transactions;
- Would still work nicely with multi-party transactions (escrow) - the final payout transactions would contain the routing part;
- Hardly any real protocol development needed, other than the communication between payment routers, which should be minimal;
- Accounting side is simple. The relevant transaction outputs show up on both sides of the balance sheet;
- It’s completely distributed. The relationships are all one to one, but can chain and fan out quite easily and dynamically;
- You could still forward parts to a payment processor for conversion to fiat;
- Since you never take possession of (some) of the payment, there’s no exposure to volatility on the bitcoin that’s forwarded;
- Graceful degradation - the payment router can even collect on a local xpub address if all other options fail.

There’s no way you’d even be able to come close to something like this using traditional payment methods.

It would work for individual users as well. You can either setup your own payment router, add your own creditors, your savings xpub, your spending xpub, etc, and have your local wallet send out payment requests to that router when you request payment from someone. Your employer can hook up to it and trickle your salary in that way or you could use a service setup by some company to handle it for you.

You guys might be interested in this:

https://www.reddit.com/r/Bitcoin/comments/2wfpzk/subspace_a_new_messaging_protocol_for_bitcoin/

It's still in early development, but it seems to be more scalable and more secure than BitMessage.

The bloom basically gives us 2 things, an easy way to detect typo's and in the event of a brute-force attack, it yields a significant number of false positives which all require a full scan of the blockchain, which I thought was a nice trade-off for the lower number of entropy bits.

If that first feature is somehow not effective enough, we could either tweak the bloom arguments or move to the 16 bit method that gmaxwell proposed.

Updated.

Changed the preH and postH calculation, updated the test vectors.

Why is this posted in Development & Technical Discussion?

No, doesn't work on iPhone.

Darn. Oh well, was worth a shot.

txbtsogb_jjuimfqa_s7sgkbaq_qkjxygyi_xk3deuxm_rm1uqte8_nukemm6y_xujjjzbr

works fine.

Updated wording of parts of the spec.

No. Due to how BIP32 works, that's not possible. The initial key in BIP32 is not derived using ECC, but is generated using HMAC-SHA512. So the same trick as used in BIP38 is not possible.

Updated the spec.

Changed prefix to 2 bytes, 'RK' and 'rk' for clear version and encrypted version respectively.
Added entropy field to encrypted version, moved KDF field from prefix into entropy field.
Changed computation of H to use PBKDF2-HMAC-SHA512 instead of Scrypt.
Changed checksum field to bloom field in encrypted version. Now supports 2 passwords.

Yes. I'm making the change right now. I'm currently updating the test vectors and adding new ones, plus second password.

No BIP number as of yet. I'll have to ask the list again, once we've finished the bloom filter stuff.

I'd say call it HD wallet root key.

Ok, I've done some searching and unfortunately, there are no 2 byte prefixes for all 3 possible lengths if we increase everything by 1 or 2 bytes. But I found a way to make it work if we increase by 1/2/3 bytes for the 16/32/64 byte root keys respectively. Not ideal, but at least there's a pattern.

I've also changed the prefix from 'ws' and 'WS' to 'rk' and 'RK', something I wanted to do ever since the term 'root key' was introduced.

The unencrypted lengths stay the same, but the prefix length is reduced to 2 bytes, giving us one extra byte.

Actually, 1 byte less works for the unencrypted variant. Updated the table.

Length	Prefix	Min	Max	Count
24	RK	0x28C1	0x28C6	6
40	RK	0x4AC5	0x4AD1	13
72	RK	0xFBB3	0xFBDE	44
26	rk	0xF83F	0xF853	21
43	rk	0x6731	0x6739	9
76	rk	0x4EB4	0x4EB9	6

So the unencrypted format becomes something like:

prefix(2 bytes) + date(2 bytes) + checksum(4 bytes) + root key(16/32/64 bytes)


The encrypted format becomes something like:

prefix(2 bytes) + date(2 bytes) + KDF(5 bits) + entropy(11/19/27 bits) + bloom filter(4 bytes) + encrypted root key(16/32/64 bytes)


Thoughts?

There's a third option. Basically, if we want the same security as we have right now, the bloom has to be based on the full decryption pass and thus can't be part of the salt.

So we need to add some extra bytes for salt entropy. Currently, the prefix is 3 bytes long. I'll have to check, but if we add 1 or 2 extra bytes, it'll become 2 bytes again, giving us either 11 or 19 bits of extra entropy (+ 5 bits for KDF selection).

I'll try and have a look at that tomorrow.

Actually, it makes you wonder whether or not the key needs to be encrypted with a strong KDF at all at that point. If the strong KDF is used to generate the bloom filter, then the hash used to encrypt is going to be irrelevant, right? As an attacker, you're testing to see if you generated a password that passes the bloom filter and you move on from there, so that's the step that should be costly.

So that means that this is the step that has to be outsourced. And that means that we need a good salt for this step. So we're right back where we started.

Actually, come to think of it, this gives a brute-force attack a big optimization. They only have to test against the bloom filter now. There's no need to do the strong hash. So this has to be hashed using the strong hash.

How many iterations do you suggest if we were to add this as one of the KDFs?


Very well, I'll see if I can rework it to use PBKDF2-SHA512 for the preH and postH sorry, I meant for H.


This means doing the strong hash multiple times and not being able to outsource it. I think it's fine to use something like a double SHA256 here. It's not going to leak anything useful anyway.

We've got 32 possible KDFs. Surely that's enough to have a Scrypt parameter set for every hardware platform that wants to implement this? Additionally, I want to add support for catena in the future as it fixes some issues found in Scrypt. See: https://github.com/cforler/catena


It uses Scrypt 10,1,1 purely for the key stretching. I didn't want to muck about with a fixed output length hash function, because I potentially need more bytes than SHA512 currently provides.


I'm right there with you, but I also want to preserve the entropy of preH's salt.



Currently the checksum is a subsection of the hash of the HD wallet master private key and is used in the salt.

Since for the second password we basically don't know what the key is until we decrypt for the first time, we can't change the bloom.

We'd either have to remove the checksum from the salt (losing entropy) or change the input of the bloom (not being based on the HD wallet master private key).