Skip to content

Instantly share code, notes, and snippets.

@Kixunil
Last active April 14, 2023 22:07
Show Gist options
  • Save Kixunil/0ddb3a9cdec33342b97431e438252c0a to your computer and use it in GitHub Desktop.
Save Kixunil/0ddb3a9cdec33342b97431e438252c0a to your computer and use it in GitHub Desktop.
Efficient reusable Taproot addresses

Reusable taproot addresses

Abstract

This document proposes a new scheme to avoid address reuse while retaining some of the convenience of address reuse, keeping recoverability purely from Bitcoin time chain and avoiding visible fingerprint. The scheme has negligible average overhead.

Motivation

Address reuse is one of the most horrible things people can do for privacy. However, the convenience can not be ignored and human beings are therefore incentivized to reuse addresses. This is especially the case in long-term business relationships, when it's convenient to avoid roundtrip of generating a new address.

There are existing schemes that tried to address this issue:

  • Stealth addresses - they used ECDH to generate a new address for a new transaction putting ephemeral public keys in OP_RETURN outputs As a result they had significant overhead and visible footprint. Nonetheless their version is being used in Monero.
  • Reusable payment codes (BIP 47) - a slight improvement over Stealth addresses. While they only require special transaction for initialization, subsequent transactions being free from overhead and visible fingerprint, the initial transaction must happen before real business activity and it produces effectively toxic change that may be difficult to handle. The initial transaction has no value besides providing convenient privacy. An alternate version proposed sending the required data over Bitmessage. This solved the problem with cost and footprint but introduced inability to recover coins purely from seed. In other words, the key received over bitmessage has to be backed up for every counterparty. Further, it requires yet another protocol that is not widely used.

This document proposes to solve the size/footprint issues of BIP 47 without losing the ability to recover from seed even if one of the parties is unavailable.

Construction

Initial transaction

Similarly to BIP 47, this scheme uses a notification transaction. However unlike BIP 47, the notification transaction is also a "real" transaction. It is the transaction performed when the parties conduct business for the first time using this scheme. The sender of notification transaction MUST be spending at least one input of one of these types:

  • P2PK
  • P2PKH
  • P2SH-P2WPKH
  • P2WPKH
  • P2TR

The sender MUST be capable of receiving to Taproot. The receiver MUST use Taproot for receiveing. (In principle, P2PK could be used instead of Taproot but such would be very unusual and thus suspicious.) The transacting parties MAY use PayJoin but MUST NOT involve a third party in it.

When using this scheme, the sender MUST generate a change using the following algorithm.

  1. Select an input with lowest index, belonging to the sender, being one of the types listed above. Let's call it sender key input.
  2. Let p_sender be the private key associated with sender key input.
  3. Let P_receiver be the Taproot address used by the receiver.
  4. Calculate shared_secret = SHA256(p_sender*P_receiver) (ECDH)
  5. Calculte offset = HMAC(shared_secret, CHANGE_KEY_CONSTANT) where CHANGE_KEY_CONSTANT is an arbitrary constant defined by the protocol
  6. Calculate P_change = (offset + p_sender)*G
  7. Calculate and securely cache relationship_seed = HMAC(shared_secret, RELATIONSHIP_SEED_CONSTANT) where RELATIONSHIP_SEED_CONSTANT is an arbitrary constant defined by the protocol that MUST NOT be equal to CHANGE_KEY_CONSTANT
  8. Use P_change in the change output script

The receiver watches the address and reacts to received transaction by performing this check:

  1. Select an input with lowest index, not belonging to the receiver, being one of the types listed above - the sender key input.
  2. Let P_sender be the public key associated with sender key input.
  3. Let p_receiver be the private key associated with Taproot address used by the receiver.
  4. Calculate shared_secret = SHA256(P_sender*p_receiver) (ECDH)
  5. Calculte offset = HMAC(shared_secret, CHANGE_KEY_CONSTANT)
  6. Calculate P_change = offset*G + P_sender
  7. Check that P_change matches the key used in change.
  8. If the key doesn't match, don't continue
  9. Calculate relationship_seed = HMAC(shared_secret, RELATIONSHIP_SEED_CONSTANT) and cache it securely
  10. Precompute a reasonably large number of offsets using a cryptographically secure PRNG seeded by relationship_seed
  11. For each offset compute P_i = (offset_i + p_receiver) * G
  12. Start watching the chain for incoming transactions on public keys generated above

Repeated sending

Each time the sender wishes to send to the receiver he computes P_i = offset_i * G + P_receiver, where offset_i denotes a random nonce generated by same PRNG mentioned in step 9 above. The sender then sends coins to P_i. The receiver has these addresses and private keys pre-cached so he can easily identify incoming transaction and spend the associated coins whenever needed.

Recovery

Sender

In case of data loss, the sender recovers the history, coins and relationships using this algorithm:

  1. Scan the chain for all transactions associated with BIP32 addresses
  2. Every time a transaction is found which cointains at least two Taproot outputs that don't match any of the BIP32 addresses perform the following
  3. For each output attempt to repeat the algorithm above deriving the shared_secret and the change output and check if the change output matches one of the outputs in the transaction
  4. If match was found precompute offsets and the associated addresses and add them with the change output to the list of scanned addresses.

Receiver

  1. Scan the chain for all transactions associated with BIP32 addresses
  2. Every time a transaction is found which contains at least one additional Taproot output, attempt to recompute shared_secret and check if any of the outputs matches expected change
  3. If a match is found, precompute the offsets and add the corresponding keys to the list of scanned addresses.

Conclusion

As can be seen from the above, the notification transaction looks like a regular transaction. Since the outside observers can not compute shared_secret (assuming ECDH is secure), they can not determine whether this protocol is being used nor compute the following addresses. The protocol has same advantages over Stealth addresses as BIP 47, but in addition, the notification transactions can not be identified by outside parties, the changes are not neccessarily that toxic (mixing is obviously still recommended) and the overhead is generally lower.

While it may seem that the overhead is zero, it's not exactly the case. The overhead of notification transaction over not using this protocol is:

  • The contruction requires Taproot which is on average a little bit larger than P2WPKH.
  • Skipping the change output in the rare cases when it wouldn't be needed (sufficient UTXO available) is not possible.
  • Tricks using PayJoin to open a Lightning channel or participate in other contracts are not possible or require additional output.
  • Opening a Lightning channel with the change or sending the change to someone else is impossible.
  • Batching several notification transactions produces a change output for each receiver. On the bright side, this can be used to simulate Samourai-style Stonewall, getting a bit more privacy for the added fee.

It can be argued that until various batching tricks become widely used this overhead is small.

@Kixunil
Copy link
Author

Kixunil commented Dec 31, 2021

@LaurentMT they must not, this is not a finalized BIP but rather a high-level overview of the idea. If this is implemented it must use one specific PRNG.

@akarve there is probably still shitload of typos, LOL. I guess better leave it for a BIP or something.

@sanket1729 interesting trick to make it usable out of the box! I've glossed over stuff like tweaking as I don't expect there to be an issue with computation of addresses caused by it.

I'm thinking of creating a repo/org for people interested in developing this idea. Feel free to ping me if anyone is interested.
It'd be nice to also figure out a nice way of representing these addresses (BIP21 with etra=1 seems most compelling so far)
I'd also like to address reverse sending - from sender to receiver. So far having reverse_relationship_seed = HMAC(shared_secret, REVERSE_RELATIONSHIP_SEED_CONSTANT) seems good but maybe there's something better.

@RubenSomsen
Copy link

Nice write-up. It makes a lot of sense that you're bringing this up now, since taproot exposes the pubkey by default, which makes things a lot easier.

Your protocol variant does re-introduce one of the issues that the original stealth protocols sought to avoid: having to calculate a shared secret for (almost) every transaction on the blockchain. Since you never know when a new person might want to establish a shared secret with you, you have to keep scanning forever. ECC multiplication isn't cheap (especially when not multiplying by G), but it can basically be seen as an added validation cost to running a full node (and restoring back-ups) for those who want more privacy.

What's perhaps more problematic is that in your protocol the sender is forced to follow a special protocol to recover their coins after restoring a backup, which may cause reluctance to use it, especially in cases where the sender doesn't particularly care about privacy.

But I believe a more simple protocol will suffice, as well as remove the complexity on the sender side. Instead of marking a change output, Bob (B) can just directly pay Alice into her stealth key (A) by sending funds to A'=hash(b*A)+A. This gets rid of the requirement of needing the sender to make a special change output, makes the payment immediate, and the cost for the recipient stays the same because they already had to scan every transaction anyway.

There are three downsides I can think of:

  1. If Bob practices key reuse and sends a second payment, the address will be the same. This can be mitigated by including more information in the shared secret hash, such as the txid of Bob's input or the nlocktime field at the current block height.
  2. Paying from a coinjoin won't be possible if you require the first input to be used. Scanning every single input instead of only every first input would solve this (but be more costly).
  3. Unless everyone cooperates, you may not be able to pay to a stealth key from an output you don't fully control (exchanges or multisig). In your protocol this is still possible (albeit a little clunky) by establishing a shared secret first, deriving a new address, and then making the payment elsewhere.

It's also possible to still preserve the payment code property by just making the first payment as I described above, and then continuing to use the shared secret for the payment code, but I do think there's a lot to say for the simplicity of foregoing the need for payment codes completely, and the downsides seem relatively minor.

In any case, I'm glad to see you revitalize this topic. It's something I had been meaning to revisit by the time taproot came out, but had completely forgotten.

Copy link

ghost commented Jan 1, 2022

But this thing is clever in that it uses the change scriptPubkey and destination pubkey for communication.

I think similar approach was used by Omni for communication in Class A and Class B transactions shared here:

https://github.com/OmniLayer/spec/blob/master/OmniSpecification-v0.6.adoc#a1-class-a-transactions-original-method

https://github.com/OmniLayer/spec/blob/master/OmniSpecification-v0.6.adoc#a2-class-b-transactions-multisig-method

@AdamISZ
Copy link

AdamISZ commented Jan 1, 2022

I think this is a clever blend of a few pre-existing ideas, I like it. However I'd like to unpack something that Ruben said because I believe it gets to a key point:

@RubenSomsen

Your protocol variant does re-introduce one of the issues that the original stealth protocols sought to avoid: having to calculate a shared secret for (almost) every transaction on the blockchain. Since you never know when a new person might want to establish a shared secret with you, you have to keep scanning forever.

I think there's several points to unpack there.
In the protocol as described in doc (not your variant): this is not true ... kinda. But I think the confusion is coming from focusing on two different use cases:

  1. A static key/code whatever, that you can post somewhere and receive donations/payments from anyone, while avoiding address reuse.
  2. An active request of a payment from Bob, by Alice, where Alice expects Bob might pay her again in future (friend; customer whatever)

I believe this document is optimising for case 2. By making that first payment "just as normal" (at least assuming everyone uses taproot, let's say). Then it allows the receiver to do a check: did this guy (Bob here) use this snazzy stealth key trick? No: nothing to do. Yes: great, let me pre-cache 1000 future addresses to get payments from him in future.

But it doesn't really help you with case 1. There, as you point out, you're going to need to scan every tx that comes through on-chain anyway, so you may as well KISS and, as you say, do something like h(bA+stuff)G + A where A is this key that is published, and not bother with special change outputs (and you correctly point out that by adding 'stuff' you can avoid a trivial reuse issue).
Well; but this doesn't allow you to pre-cache, but then that's the whole point: pre-caching specifically only makes sense for repeated payments from the same payer.

I don't know the conclusion; two variants of the protocol? That does seem rather annoying.

@RubenSomsen
Copy link

RubenSomsen commented Jan 1, 2022

@AdamISZ thank you for your comments. You made me realize I misunderstood part of the post. I was under the mistaken impression that the first transaction wasn't specifically an interactive payment to the recipient. You are right that this means that what I am suggesting is essentially a different scheme.

To once again summarize the differences:

@Kixunil's scheme (the first 2 points are what I initially misunderstood):

  • No continuous scanning of every transaction
  • One-time interaction with the recipient (stateful for sender: if they forget, they need to interact again)
  • No on-chain footprint
  • Sender needs to follow a special protocol to be able to recover from backup (this downside can be mitigated, see below)

The payment code scheme:

  • No continuous scanning of every transaction
  • No interaction with the recipient
  • On-chain footprint (or alternatively one-time interaction and stateful backups)

My scheme:

  • Continuous scanning of every transaction (increases cost of running full node)
  • No interaction with the recipient
  • No on-chain footprint

And for completeness, you can also compare the above with the basic interactive scheme that people use today, which simply involves communicating with the recipient for each payment and receiving a freshly uncorrelated address.

Now that I no longer misunderstand @Kixunil's scheme, I see that it can also be improved by simply indicating that you may make future payments during the initial payment interaction. The recipient then gives you a BIP32 address from a different derivation path, and a payment to this address is interpreted as exchanging a shared secret for future payments (1st input key * recipient key = shared secret). You could simplify the scheme even further and simply expect future payments for every payment you receive (i.e. never use a different derivation path), but that would require more effort. In either case, this gets rid of the requirement of needing the sender to follow a special protocol to be able to recover from backup, which seems like a big win.

(Edit: looks like the derivation path idea is the same thing as what @sanket1729 suggested. My bad for missing it.)

(Edit2: @Kixunil's scheme can actually succinctly be summarized as follows: give out a BIP32 address upon first payment, so the sender can generate addresses on their own for future payments without further interaction).

Assuming the above is correct, this means the remaining difference between @Kixunil's scheme and my variant is the one-time interaction with each sender vs. continually scanning the entire blockchain.

Getting rid of the one-time interaction would be nice, especially since a significant number of payments will likely be one-time only. It certainly is appealing to just have a single "stealth" key and have that be enough for everyone to send you uncorrelated payments. The main question is just how costly the overhead of scanning the entire chain would be exactly.

Recovering from backup is probably a relatively minor concern because the data can be encrypted and backed up into the cloud, and only if cloud recovery fails, would a full rescan of the blockchain be required.

One more detail that I should mention is that it would be more practical to have your address consist of a scanning key and a spending key, where Alice's stealth address = concatenate(A_scan, A_spend) and the payment is calculated by Bob as hash(b*A_scan)*G+A_spend, so that payments can be scanned for and recognized with the secret key of A_scan, but funds can only be spent with A_spend (presumably on a hardware wallet, so it won't be practical to scan with this key). If the device that's scanning gets hacked, you lose your privacy (as is already the case today), but not your coins.

@Kixunil
Copy link
Author

Kixunil commented Jan 3, 2022

@AdamISZ very well written! You are correct and I initially intended case #2 but now I think it could be used for #1 too. The idea of backing up stuff to cloud and only do exhaustive scan for cloud failure scenarios as @RubenSomsen suggested sounds great. It still needs some other protocol to notify the receiver of this (is onion better than bitmessage?) so continuous scanning is not the default.

Good point about having a separate scanning key and the solution to achieve it!

@DON-MAC-256
Copy link

Thanks for the proposal @Kixunil. The discussion from @AdamISZ and @RubenSomsen is great as well. The scan-split key separation is a particularly nice touch.

An extension to BIP21 certainly makes sense when communicating this capability during a first-touch interaction (scenario #2).

Overall, this proposal could be more impactful as a challenger to BIP47 (scenario #1), requiring no prior interaction to create stealth addresses (and certainly no chain signature), and having reasonable scanning and recovery characteristics.

Forward-scanning the chain is a tall order, however, if this proposal expects widespread adoption. A formulation compatible with BIP-157 client-side filters would be extremely helpful, though it looks like that may not be possible.

Copy link

ghost commented Jan 4, 2022

I can get behind the effort of creating a better stealth address implementation. BIP47 suffers from a number of problems, not supporting receive addresses other than P2PKH probably being the biggest one. I opened a PR here to address that (the BIP is still in a draft state) and currently waiting to see if there's any traction.

I'm with @sanket1729 regarding using BIP32 instead of PRNG based offsets. BIP32 already provides address derivation out of the box, so that removes one more piece of complexity. I'd also have a low gap limit (maybe 1) on the precomputation, there's no need for the receiving wallet to look very far ahead and burden itself with scanning for a large number of addresses.

Will this support static payment codes or is the idea to simply have a public key (P_receiver) in lieu of a code? I'd like to see an encoding that makes it impossible to mistake that key for an actual receive key. BIP47 prevents confusion there by prefixing an xpub with a version byte and encoding it using base58.

@Kixunil
Copy link
Author

Kixunil commented Jan 4, 2022

BIP32 is a PRNG. :) I agree it looks best.

Gap limit definitely shouldn't be too low. It'd just risk similar horrible UX issues as today with low gap limits. The additional scanning overhead for empty addresses is quite small, I think, so shouldn't be an issue.

Will this support static payment codes

Not sure but as I said it might. In that case it really needs a different encoding.
In case of per-business exchange BIP21 is nicer because it's backwards-compatible and sending to it ordinarily is fine.

@Ziya-Sadr
Copy link

what would be a rough estimate for how long would it take for a sub 1000$ laptop to scan and perform the recovery process? I'm trying to understand if this could be realistically usable for average (but tech savvy) users

@Kixunil
Copy link
Author

Kixunil commented Jan 7, 2022

@Ziya-Sadr I think it should be faster than verifying whole chain (assuming you already have the chain). Before HW crisis it was possible to buy HW that can verify the chain in 12 hours for ~250 european shitcoins, so I think up to a day is a safe pessimistic upper bound. However it'd probably be significantly less in practice because there's very few taproot transactions (for now) and you can skip everything before Taproot activation. Or even before standardization of this thing.

@pointbiz
Copy link

pointbiz commented Mar 1, 2022

I think v3 and v3 of BIP47 is relevant to this discussion.
https://github.com/OpenBitcoinPrivacyProject/rfc/blob/master/obpp-05.mediawiki

@Kixunil
Copy link
Author

Kixunil commented Mar 1, 2022

Cool, didn't know about that one!

@inaltoasinistra
Copy link

I imagine there are some good reasons to avoid a simpler solution: use xpubs as reusable addresses. in this case the receiver deterministically generates the shared secret, s/he knows the addresses to watch and the sender knows the addresses to use.
thanks!

@Kixunil
Copy link
Author

Kixunil commented Mar 3, 2022

@inaltoasinistra xpub is essentially one-way, thus sender and receiver would have to exchange it both ways. With these Taproot addresses the receiver could easily send sats back (refund, return loan, ...)

Also if people are OK with chain scanning (maybe combined with bitmessage) this can work for donations (static address), which wouldn't be private in case of xpub.

@w0xlt
Copy link

w0xlt commented Mar 8, 2022

Very interesting. I am trying to learn more about this and implement a simple version in Rust using rust-secp256k1.

In the first part, the 5th step is:
P_change = (offset + p_sender)*G

And in the second part, the 5th step is:
P_change = offset*G + P_sender

Is it right ? Shouldn't this be the same calculation ?


EDIT: I noticed that the p_sender information is not available in the second part.
The code below is generating different values ​​for P_change. I verified that the offset is the same in both. Not sure if implemented correctly.

// PART 1 - step 5
// Calculate P_change = (offset + p_sender)*G
let _  = p_sender.add_assign(&offset);
let P_change = PublicKey::from_secret_key(&secp, &p_sender);

// ...

// PART 2 - step 5
// Calculate P_change = offset*G + P_sender
let p_secret_key = SecretKey::from_slice(&offset).unwrap();
let mut P_change = PublicKey::from_secret_key(&secp, &p_secret_key);
let _ = P_change.add_exp_assign(&secp, &P_sender.serialize());

@Kixunil
Copy link
Author

Kixunil commented Mar 8, 2022

implement a simple version in Rust

Awesome! I wanted to write it in Rust too but didn't have time yet.

Is it right ? Shouldn't this be the same calculation ?

It is because both equations give the same result. It's basically saying a*(b+c) = a*b + a*c

The code below is generating different values ​​for P_change

Strange, I don't see any bug there, maybe seeing more code would help. Anyway I think just using ecdh::SharedSecret::new() would save you a lot of trouble. :)

@w0xlt
Copy link

w0xlt commented Mar 8, 2022

Thanks. I changed step 3 to use ecdh::SharedSecret::new(). Simplified the code.

Full code is at https://github.com/w0xlt/taproot_reusable_addr/blob/master/src/main.rs
The result for cargo run is, for example:

----> offset 01: 5ef4aa5496bd21f79132336c802ca952b8d197148d0a0cb2ccce037fdd393dea
----> offset 02: 5ef4aa5496bd21f79132336c802ca952b8d197148d0a0cb2ccce037fdd393dea
P_change comparison: Less

Same offset, but comparison between P_changes does not return Ordering::Equal.

@Kixunil
Copy link
Author

Kixunil commented Mar 9, 2022

The problem is that add_exp_assign doesn't accept public key but a scalar and already performs both operations.
Applying this patch should work:

-    let p_secret_key = SecretKey::from_slice(&offset).unwrap();
-    let mut P_change = PublicKey::from_secret_key(&secp, &p_secret_key);
-    let _ = P_change.add_exp_assign(&secp, &P_sender.serialize());
+    let mut P_change = P_sender;
+    P_change.add_exp_assign(&secp, &offset).unwrap();

@w0xlt
Copy link

w0xlt commented Mar 9, 2022

Thanks! Now the script is working.

It calculates the change address on the sender and receiver side.

It also calculates the addresses to be used on both sides.

I think it's implemented up to the Recovery Part. The next step is to implement it in a wallet and interact with the blockchain.

If the script is run, the results will be like:

Change address that will be used by the sender:
bc1qfd70rws5jhjs5t5ykejqumsfqzdx86hjpn83qc45af469nstskzxzfq6zj
---
Addresses calculated by the sender. Must match those calculated by the receiver.
1: bc1qdvzwt8r2ucrtmpkqqsvqq2jctswtnwu8knqupmt20mdd80r7dr45a24yz3
2: bc1qdx9l0kyp204pta0tul7wpfh5jf2uvd44zdmla86nazcu8lp0x03wc3sl46
3: bc1qgmt5v0y9tg4vep8vtsxqlu6fhcruzy96m3es965u0pc8x6q0a8fwafsypy
4: bc1qfs0jr56t8qmfv8w9ma7mxz7z6u9rceydpxu9f5c573ldljs6y9k2axrqcl
5: bc1q2mm4jru9edjyex6zqjep9j6m77lw20s2vdnxp3m8ptej58mjsajzm6jdel
---
P_change keys match !
---
Addresses calculated by the receiver.
1: bc1qdvzwt8r2ucrtmpkqqsvqq2jctswtnwu8knqupmt20mdd80r7dr45a24yz3
2: bc1qdx9l0kyp204pta0tul7wpfh5jf2uvd44zdmla86nazcu8lp0x03wc3sl46
3: bc1qgmt5v0y9tg4vep8vtsxqlu6fhcruzy96m3es965u0pc8x6q0a8fwafsypy
4: bc1qfs0jr56t8qmfv8w9ma7mxz7z6u9rceydpxu9f5c573ldljs6y9k2axrqcl
5: bc1q2mm4jru9edjyex6zqjep9j6m77lw20s2vdnxp3m8ptej58mjsajzm6jdel
---

@Kixunil
Copy link
Author

Kixunil commented Mar 10, 2022

@w0xlt perfect, would you be up for making it into a library?

@w0xlt
Copy link

w0xlt commented Mar 11, 2022

Done !
https://github.com/w0xlt/reusable-taproot-addresses

To use the lib (example):

Cargo.toml

[package]
name = "test-lib"
version = "0.1.0"
edition = "2021"

[dependencies]
reusable_taproot_addresses = { git = "https://github.com/w0xlt/reusable-taproot-addresses.git" }
secp256k1 = { git = "https://github.com/rust-bitcoin/rust-secp256k1.git", rev = "39e47fb64", features = [ "rand-std", "bitcoin_hashes", "std" ] }
bech32 = "0.8.1"

main.rs

use bech32::{ToBase32, Variant};
use reusable_taproot_addresses::{sender, receiver};
use secp256k1::{Secp256k1, KeyPair, SecretKey, PublicKey};


fn main() {
    #![allow(non_snake_case)]

    let secp = Secp256k1::new();

    let sender_key_pair = KeyPair::new(&secp, &mut secp256k1::rand::thread_rng());
    let sender_secret_key = SecretKey::from_keypair(&sender_key_pair);
    let sender_pub_key = PublicKey::from_keypair(&sender_key_pair);

    let receiver_key_pair = KeyPair::new(&secp, &mut secp256k1::rand::thread_rng());
    let receiver_secret_key = SecretKey::from_keypair(&receiver_key_pair);
    let receiver_pub_key = PublicKey::from_keypair(&receiver_key_pair);

    let (P_change_sender, relationship_seed) = sender::generate_change_output_script(
        &sender_secret_key,
        &receiver_pub_key);

    let sender_change_address = bech32::encode("bc", P_change_sender.serialize().to_base32(), Variant::Bech32m).unwrap();
    println!("Change address that will be used by the sender:\n{}\n---", sender_change_address);

    let sender_addresses = sender::generate_public_keys_to_send(
        &relationship_seed,
        &receiver_pub_key);

    let receive_addresses = receiver::generate_public_keys_to_watch(
        &P_change_sender,
        &sender_pub_key,
        &receiver_secret_key);

    println!("Addresses calculated by the sender. Must match those calculated by the receiver.");

    for sa in sender_addresses {
        let encoded = bech32::encode("bc", sa.serialize().to_base32(), Variant::Bech32m).unwrap();
        println!("{}: {}", sa, encoded);
    }

    println!("---");

    println!("Addresses calculated by the receiver.");

    for ra in receive_addresses {
        let encoded = bech32::encode("bc", ra.serialize().to_base32(), Variant::Bech32m).unwrap();
        println!("{}: {}", ra, encoded);
    }

    println!("---");
}

@w0xlt
Copy link

w0xlt commented Mar 11, 2022

I configured the lib so that it has 3 external interfaces (functions).
They are:

pub fn sender::generate_change_output_script(sender_secret_key: &SecretKey, receiver_pub_key: &PublicKey) -> (PublicKey, [u8; 32]);

pub fn sender::generate_public_keys_to_send(relationship_seed: &[u8; 32], receiver_pub_key: &PublicKey) -> Vec<PublicKey>;

pub fn receiver::generate_public_keys_to_watch(P_change_sender: &PublicKey, sender_pub_key: &PublicKey, receiver_secret_key: &SecretKey) -> Vec<PublicKey>;

If another approach is preferred, let me know.

@dergigi
Copy link

dergigi commented Mar 14, 2022

Typo: receiveing -> receiving

@afilini
Copy link

afilini commented Mar 21, 2022

I hope it's not too late to propose changes to the protocol: I have recently implemented BIP47 in BDK and one of the issues I found was that in some cases it can be hard for a light wallet to recover the sender's pubkey, for instance if the server uses a P2PK or bare multisig input, because the pubkeys are not listed in the witness/scriptsig of the transaction. For a light client it can be hard to fetch an arbitrary tx given its txid (think about Core without txindex, or a wallet using compact block filters).

Taproot suffers from this same issue, because only the signature makes it into the witness of the tx. I'm wondering if it's possible to use some crypto magic to allow the receiver to recover the public key given the signature.

I should mention that I'm also not a fan of the fact that this protocol tweaks the change address. I know it's not as efficient, but I think I would still prefer something that uses an explicit OP_RETURN to notify the receiver, like BIP47 does. Assuming the receiver's payment code is public (if it's not I would have to communicate with the receiver to get a private code, which means I could just get an address) it's not that much worse in terms of privacy in my opinion.

EDIT:

@RubenSomsen just made me realize that this protocol assumes the receiver can give a fresh address to every different sender, so what I said earlier about the notification address being publicly known doesn't apply.

As @inaltoasinistra already pointed out, if there's interaction this protocol provides little benefits to just giving out an xpub imho

@w0xlt
Copy link

w0xlt commented Mar 23, 2022

I think we can use relationship_seed as master_seed in a new BIP32 wallet with some protocol-fixed derivation path .... The receiver can just importdescriptor(xpriv/m/PROTOCOL_FIXED_PATH/*) and let bitcoin core(or any other descriptor wallet) do its thing.

Since relationship_seed is the same for receiver and sender (relationship_seed = HMAC (shared_secret, RELATIONSHIP_SEED_CONSTANT)for both), how can this be used as a master seed for the receiver? I assume the sender will have access to the same addresses in this case.

I'm wondering what is the best way to integrate this with current version of Bitcoin Core or, at least, with rawtr() PR.

@sanket1729
Copy link

sanket1729 commented Mar 23, 2022

@w0xlt, my initial text was wrong(incomplete). You are right, what I described is insecure! Here is an updated version. Note that I have not thought about it enough to prove that it is secure.

The complete protocol would be:

Here all small letters p represents private keys and P represents public keys.

  1. After the first payment, the receiver would import the descriptor with the master private key p'_r = relationship_seed + p_reciever. For chain_code, it will choose some fixed defined constant. Note that the sender can compute the xpub using P'r = P_reciever + relationship_seed*G. The receiver will import the descriptor xpriv(p'r, fixed_chain_code)/Fixed_derivatoin_path. The sender can also similarly compute xpub(P'_R, fixed_chain_code)/Fixed_derivation_path. Now, the sender can send coins by deriving new addresses.

  2. The sender backup is however annoying. We need to explicitly keep track of coins. The corresponding private key is p'_s = relationship_seed + p_sender. We can then just use import rawtr(p's).

You would need some other software to do the EC/field math operations.

@w0xlt
Copy link

w0xlt commented Mar 25, 2022

@sanket1729 Thanks for your suggestions.

I applied them in the library and they worked.

The sender function generates a public key and the receive function, the private key of this public key.

pub fn sender::generate_master_extended_public_key(relationship_seed: &[u8; 32], receiver_pub_key: &PublicKey) -> PublicKey
pub fn receiver::generate_master_extended_private_key(P_change_sender: &PublicKey,sender_pub_key: &PublicKey, receiver_secret_key: &SecretKey) -> SecretKey

I added a test that confirms that the public key generated by the sender is the same calculated from the private key generated by the receiver.

With this public key, the sender can create the xpub while the receiver, the xpriv as you suggested.

I think this libraty might be ready to be tested with current version of Bitcoin Core + rawtr() PR.

@AdamISZ
Copy link

AdamISZ commented Apr 1, 2022

Small nit, in Repeated sending, the first line, you have P_i = offset_i * G + P_receiver * G but it should be without the final * G.

@Kixunil
Copy link
Author

Kixunil commented Apr 4, 2022

@afilini no problem, there still needs to be more discussion around these ideas. I'm happy I started something even if not perfect. E.g. @RubenSomsen had some other interesting ideas.

Yes, the only advantage over plain xpub is the sender doesn't need to send xpub to the receiver in the initial interaction to enable refunds. I'm not sure if it's worth the effort but the general progression of technology moving complexity from UI to implementation suggests it could be. I hope that Taproot pubkey not being not hashed could lead to some other ideas.

@w0xlt sorry for not reviewing your library yet, life was hard lately.

@AdamISZ thanks, this kind of mistake is worth fixing.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment