MIME-Version: 1.0
References: <rH1Js_T_UWcAg9lS9NDw_Qb6Js5bgs8rPILej69BjqsEZcJZwsvHhZRilkkOQZRGXabai63hrGgbTP2Yk99ojKEN6fU6HT4TmukiafqiKjo=@protonmail.com>
In-Reply-To: <rH1Js_T_UWcAg9lS9NDw_Qb6Js5bgs8rPILej69BjqsEZcJZwsvHhZRilkkOQZRGXabai63hrGgbTP2Yk99ojKEN6fU6HT4TmukiafqiKjo=@protonmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Mon, 27 Jun 2022 22:30:39 +0200
Message-ID: <CAPv7TjYD_sC+Hkfd=Ucf2E+6qWz7NLDHUg8sgjeS1AhGAThGXQ@mail.gmail.com>
To: Alfred Hodler <alfred_hodler@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000ca44aa05e273cbb9"
Subject: Re: [bitcoin-dev] [BIP proposal] Private Payments
Precedence: list

--000000000000ca44aa05e273cbb9
Content-Type: text/plain; charset="UTF-8"

Hi Alfred,

Thanks for taking the time to write a proposal.

>The inability of payment codes to explicitly state which address types
they derive places a burden on more resource constrained wallets

I agree it's not as efficient as it could be, but how big is this problem
in practice? Expecting payments on more addresses doesn't seem like a huge
overhead. Or are you talking about the hassle of having to support spending
from all these address types?

>a notification transaction is simply a single OP_RETURN containing a value
that only Alice and Bob can calculate

This seems to be the meat of the proposal. You're hiding the intended
recipient, but in doing so you introduce a scanning requirement. Of course
you only need to scan notification transactions, so it'll be much less
heavy than Silent Payments*, but it does make it rather difficult to
support light clients.

If some degree of scanning is acceptable, then Robin Linus' scheme may be
an interesting alternative:
https://gist.github.com/RobinLinus/4e7467abaf0a0f8a521d5b512dca4833

The basic idea is that everyone publishes a single pubkey on-chain, and
everyone derives a shared secret with everyone else's pubkey. It also
requires "scanning", but the number of transactions will be lower as it's
one tx per new pubkey as opposed to one tx per sender/recipient pair. This
also means it uses far less block space. The main downside is that you have
to watch as many incoming addresses as there are registered pubkeys, but
this could be indexed relatively efficiently. Also not light client
friendly, though.

And then of course there's the recent BIP47 discussion:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-June/020549.html

This proposes to outsource the publishing of the notification transaction
in order to break the link (as well as reduce block space usage). There's
no scanning, so this preserves light client support, but the downside here
is that you now need to anonymously pay a third party (e.g. over LN).

>demand that a notification transaction meets some minimum miner fee

Note that this mechanism is not safe against miners, as they can pay
themselves arbitrarily high fees with no downside.

Hope this helps.

Cheers,
Ruben


*Silent Payments:
https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8

On Mon, Jun 27, 2022 at 9:14 PM Alfred Hodler via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi,
>
> There have been attempts to create static payment codes that function as a
> way for transacting parties to create "private" addresses, where private
> stands for "known only to transacting parties". BIP47 was one such standard.
>
> The standard suffered from a number of problems:
>
> 1. The standard promised extensibility through versioning but it never
> used that capability to follow innovations in the Bitcoin protocol. It was
> designed around the idea that legacy p2pkh addresses would always be the
> primary and only way to transact. As new standard script types started to
> emerge (Segwit v0, Taproot), the creators dealt with the problem by stating
> that implementing wallets should scan for all existing standard scripts.
> The inability of payment codes to explicitly state which address types they
> derive places a burden on more resource constrained wallets.
>
> 2. The standard relied on a notification mechanism in order to connect a
> sender with a recipient, which included either offchain technology
> (Bitmessage), or so called "notification addresses" which a) left a
> footprint b) created toxic change. That type of footprint is particularly
> harmful because it makes it obvious that a particular recipient is going to
> receive private transactions. If the notifying party performs this process
> with coins linked to its identity (i.e. tainted or non-anonymized inputs),
> it forever becomes visible that Alice connected with Bob despite the fact
> that her payment code was blinded. While future transactions and their
> amounts aren't visible, this metadata makes it possible to build a social
> graph.
>
> 3. The standard was implemented only by an entity that disavowed the BIP
> process and didn't wish to use it to keep the standard up to date. Further
> updates did take place but only outside the BIP process, creating a lack of
> clarity as to what the real specification is. Ultimately the standard was
> abandoned.
>
> I propose to build on the idea of payment codes under a new BIP with the
> following principal differences:
>
> 1. The new standard will allocate a 2-byte bitflag array that will signal
> address/script types that the receiver is deriving. Since the vast majority
> of scripts are p2pkh (47.3%) and p2wpkh (26.2%), bits 0 and 1 will be used
> for those respectively. Bit 2 will be p2tr. The remaining 13 bits are
> reserved for future standard script types.
>
> 2. Notification transactions still exist but no longer leave a privacy
> footprint on the blockchain. Instead, a notification transaction is simply
> a single OP_RETURN containing a value that only Alice and Bob can
> calculate. If Alice's notification transaction uses UTXOs not associated
> with her identity, there is never a footprint showing that either her or
> Bob are using private payments. If Alice uses tainted coins, only she is
> exposed as a user of Private Payments but Bob still isn't.
>
> 3. Payment code versioning is no longer done because it creates the
> potential for fragmentation and disparate standard updates by different
> parties that don't follow the BIP process (BIP47 is a good example of that).
>
> 4. Relying on static compressed pubkeys as opposed to extended keys means
> shorter payment codes.
>
> ==Proposed Payment Code Structure==
>
> bytes 0-1: - enabled (watched) address types (16 possible address types)
> bytes 2-35: - compressed public key P
>
> ==Encoding==
>
> A payment code is encoded in base58check and the version byte produces "S"
> for the first character. A code might look like
> "SwLUHs3UfMUXq956aXLTUPPfow7a8gDfSUUAtafwqHcobf6mKcMbJk".
>
> ==Pubkey Derivation==
>
> Recipient's payment code pubkey `P` is derived from a master key using the
> following path: `m/purpose'/coin_type'/account'`. `purpose` will be defined
> once a BIP number is assigned. Its corresponding private key is `p`.
>
> Notifier/sender's pubkey `N` is derived using the following derivation
> path: `m/purpose'/coin_type'/account'/*`, where each recipient gets a new
> index. This way send-side privacy is always preserved. Its corresponding
> private key is `n`.
>
> ==Notifications==
>
> Alice wants to notify Bob that he will receive future payments from her.
> Alice selects any UTXO in her wallet (preferably not associated with her)
> and `n_Alice`. Alice selects the public key contained in Bob's payment code
> `P_Bob`. Alice performs the following process (`*` and `+` are EC
> operations):
>
> notification = SHA256(n_Alice * P_Bob)
>
> Alice then constructs a 72-byte OP_RETURN output whose value is set to
> `BIPXXXX + notification + N_Alice` (`+` is concat) and sends it in a
> transaction containing no other outputs (XXXX to be replaced once a BIP
> number is assigned). Alice MUST now keep track of `n_Alice` or its
> derivation path as it will be used in future transactions exclusively with
> Bob (not for spending but to calculate secret addresses).
>
> Bob's wallet receives whole blocks but doesn't need to waste resources on
> decoding them if the environment is resource constrained. Bob simply needs
> find the string BIPXXXX in the binary blob that represents an undecoded
> block. Once found, Bob extracts the subsequent 32 bytes (`notification`)
> and the subsequent 33 bytes (`N_Alice`). The benefit of this approach is
> that Bob doesn't have to decode blocks and extract pubkeys from scriptsigs.
>
> Since ECDH dictates that SHA256(n_Alice * P_Bob) == SHA256(N_Alice *
> p_Bob), Bob calculates the expected notification value and checks if it
> matches the first value in the payload. If so, Bob found a notification
> transaction addressed to himself and stores `N_Alice` in order to be able
> to detect and spend future payments from Alice. The added benefit of this
> approach over BIP47 is that Bob doesn't learn Alice's payment code, so
> Alice can pay Bob without revealing her identity. To take advantage of
> these privacy benefits, Alice simply has to engage in coin control on her
> end. A real world scenario where this might be useful is anonymous
> donations to a party whose wallet may be seized in the future. Seizing such
> a wallet won't reveal who Alice is (as long as she engages in coin
> control), whereas BIP47 would by default leak her identity even if her
> coins as anonymized.
>
> If this process fails for any reason, Bob assumes a spurious notification
> or one not addressed to himself and gives up.
>
> ==Transacting==
>
> Now that they are connected, Alice can send transactions to Bob. Alice
> needs to keep track of her transaction count toward Bob; let's name that
> counter `X`. This process is similar to what BIP47 does.
>
> Alice calculates a secret point:
>
> S = n_Alice * P_Bob
>
> Alice calculates a shared secret:
>
> s = SHA256(S, X)
>
> Alice calculates Bob's ephemeral public key and its associated address
> where the funds will be sent:
>
> P_Bob' = P_Bob + s*G
>
> When Bob detects a payment to `P_Bob'`, he can spend such coins by
> calculating the shared secret `s` in the same manner using `N_Alice` and
> `p_Bob` and performing:
>
> p_bob' = p_bob + s
>
> The fact that Alice and Bob are using a shared counter means we can do
> away with chain codes and make payment codes much smaller. Bob simply needs
> to derive a number of addresses to watch with respect to some gap limit
> (which can be as low as 1 in practice).
>
> ==Anti-spam==
>
> While DoS hasn't been a problem with BIP47, it is possible to build
> anti-spam measures into payment codes. The owner of a code could simply
> demand that a notification transaction meets some minimum miner fee or a
> multiple of some trailing average. This would help prevent spam
> notifications that might otherwise overwhelm a payment code with addresses
> to watch. But that is purely optional.
>
> Looking forward to hearing thoughts and ideas.
>
> Alfred
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--000000000000ca44aa05e273cbb9
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Alfred,<div><br></div><div>Thanks for taking the time t=
o write a proposal.<br><div><br></div><div>&gt;The inability of payment cod=
es to explicitly state which address types they derive places a burden on m=
ore resource constrained wallets</div><div><br></div><div>I agree it&#39;s =
not as efficient as it could be, but how big is this problem in practice? E=
xpecting payments on more addresses doesn&#39;t seem like a huge overhead. =
Or are you talking about the hassle of having to support spending from all =
these address types?</div><div><br></div><div>&gt;a notification transactio=
n is simply a single OP_RETURN containing a value that only Alice and Bob c=
an calculate</div><div><br></div><div>This seems to be the meat of the prop=
osal. You&#39;re hiding the intended recipient, but in doing so you introdu=
ce a scanning requirement. Of course you only need to scan notification tra=
nsactions, so it&#39;ll be much less heavy than Silent Payments*, but it do=
es make it rather difficult to support light clients.</div><div><br></div><=
div>If some degree of scanning is acceptable, then Robin Linus&#39; scheme =
may be an interesting alternative:</div><div><a href=3D"https://gist.github=
.com/RobinLinus/4e7467abaf0a0f8a521d5b512dca4833">https://gist.github.com/R=
obinLinus/4e7467abaf0a0f8a521d5b512dca4833</a><br></div><div><br></div><div=
>The basic idea is that everyone publishes a single pubkey on-chain, and ev=
eryone=C2=A0derives a shared secret with everyone else&#39;s pubkey. It als=
o requires &quot;scanning&quot;, but the number of transactions will be low=
er as it&#39;s one tx per new pubkey as opposed to one tx per sender/recipi=
ent pair. This also means it uses far less block space. The main downside i=
s that you have to watch as many incoming addresses as there are registered=
 pubkeys, but this could be indexed relatively efficiently. Also not light =
client friendly, though.</div><div><br></div><div>And then of course there&=
#39;s the recent BIP47 discussion:</div><div><a href=3D"https://lists.linux=
foundation.org/pipermail/bitcoin-dev/2022-June/020549.html">https://lists.l=
inuxfoundation.org/pipermail/bitcoin-dev/2022-June/020549.html</a><br></div=
><div><br></div><div>This proposes to outsource the publishing of the notif=
ication transaction in order to break the link (as well as reduce block spa=
ce usage). There&#39;s no scanning, so this preserves light client support,=
 but the downside here is that you now need to anonymously pay a third part=
y (e.g. over LN).</div><div><br></div><div>&gt;demand that a notification t=
ransaction meets some minimum miner fee</div><div><br></div><div>Note that =
this mechanism is not safe against miners, as they can pay themselves arbit=
rarily high fees with no downside.</div><div><br></div><div>Hope this helps=
.</div><div><br></div><div>Cheers,</div><div>Ruben</div></div><div><br></di=
v><div><br></div><div>*Silent Payments:=C2=A0<a href=3D"https://gist.github=
.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8">https://gist.github.com/=
RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8</a></div></div><br><div class=
=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Mon, Jun 27, 2022=
 at 9:14 PM Alfred Hodler via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev=
@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; w=
rote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0p=
x 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
There have been attempts to create static payment codes that function as a =
way for transacting parties to create &quot;private&quot; addresses, where =
private stands for &quot;known only to transacting parties&quot;. BIP47 was=
 one such standard.<br>
<br>
The standard suffered from a number of problems:<br>
<br>
1. The standard promised extensibility through versioning but it never used=
 that capability to follow innovations in the Bitcoin protocol. It was desi=
gned around the idea that legacy p2pkh addresses would always be the primar=
y and only way to transact. As new standard script types started to emerge =
(Segwit v0, Taproot), the creators dealt with the problem by stating that i=
mplementing wallets should scan for all existing standard scripts. The inab=
ility of payment codes to explicitly state which address types they derive =
places a burden on more resource constrained wallets.<br>
<br>
2. The standard relied on a notification mechanism in order to connect a se=
nder with a recipient, which included either offchain technology (Bitmessag=
e), or so called &quot;notification addresses&quot; which a) left a footpri=
nt b) created toxic change. That type of footprint is particularly harmful =
because it makes it obvious that a particular recipient is going to receive=
 private transactions. If the notifying party performs this process with co=
ins linked to its identity (i.e. tainted or non-anonymized inputs), it fore=
ver becomes visible that Alice connected with Bob despite the fact that her=
 payment code was blinded. While future transactions and their amounts aren=
&#39;t visible, this metadata makes it possible to build a social graph.<br=
>
<br>
3. The standard was implemented only by an entity that disavowed the BIP pr=
ocess and didn&#39;t wish to use it to keep the standard up to date. Furthe=
r updates did take place but only outside the BIP process, creating a lack =
of clarity as to what the real specification is. Ultimately the standard wa=
s abandoned.<br>
<br>
I propose to build on the idea of payment codes under a new BIP with the fo=
llowing principal differences:<br>
<br>
1. The new standard will allocate a 2-byte bitflag array that will signal a=
ddress/script types that the receiver is deriving. Since the vast majority =
of scripts are p2pkh (47.3%) and p2wpkh (26.2%), bits 0 and 1 will be used =
for those respectively. Bit 2 will be p2tr. The remaining 13 bits are reser=
ved for future standard script types.<br>
<br>
2. Notification transactions still exist but no longer leave a privacy foot=
print on the blockchain. Instead, a notification transaction is simply a si=
ngle OP_RETURN containing a value that only Alice and Bob can calculate. If=
 Alice&#39;s notification transaction uses UTXOs not associated with her id=
entity, there is never a footprint showing that either her or Bob are using=
 private payments. If Alice uses tainted coins, only she is exposed as a us=
er of Private Payments but Bob still isn&#39;t.<br>
<br>
3. Payment code versioning is no longer done because it creates the potenti=
al for fragmentation and disparate standard updates by different parties th=
at don&#39;t follow the BIP process (BIP47 is a good example of that).<br>
<br>
4. Relying on static compressed pubkeys as opposed to extended keys means s=
horter payment codes.<br>
<br>
=3D=3DProposed Payment Code Structure=3D=3D<br>
<br>
bytes 0-1: - enabled (watched) address types (16 possible address types)<br=
>
bytes 2-35: - compressed public key P<br>
<br>
=3D=3DEncoding=3D=3D<br>
<br>
A payment code is encoded in base58check and the version byte produces &quo=
t;S&quot; for the first character. A code might look like &quot;SwLUHs3UfMU=
Xq956aXLTUPPfow7a8gDfSUUAtafwqHcobf6mKcMbJk&quot;.<br>
<br>
=3D=3DPubkey Derivation=3D=3D<br>
<br>
Recipient&#39;s payment code pubkey `P` is derived from a master key using =
the following path: `m/purpose&#39;/coin_type&#39;/account&#39;`. `purpose`=
 will be defined once a BIP number is assigned. Its corresponding private k=
ey is `p`.<br>
<br>
Notifier/sender&#39;s pubkey `N` is derived using the following derivation =
path: `m/purpose&#39;/coin_type&#39;/account&#39;/*`, where each recipient =
gets a new index. This way send-side privacy is always preserved. Its corre=
sponding private key is `n`.<br>
<br>
=3D=3DNotifications=3D=3D<br>
<br>
Alice wants to notify Bob that he will receive future payments from her. Al=
ice selects any UTXO in her wallet (preferably not associated with her) and=
 `n_Alice`. Alice selects the public key contained in Bob&#39;s payment cod=
e `P_Bob`. Alice performs the following process (`*` and `+` are EC operati=
ons):<br>
<br>
notification =3D SHA256(n_Alice * P_Bob)<br>
<br>
Alice then constructs a 72-byte OP_RETURN output whose value is set to `BIP=
XXXX + notification + N_Alice` (`+` is concat) and sends it in a transactio=
n containing no other outputs (XXXX to be replaced once a BIP number is ass=
igned). Alice MUST now keep track of `n_Alice` or its derivation path as it=
 will be used in future transactions exclusively with Bob (not for spending=
 but to calculate secret addresses).<br>
<br>
Bob&#39;s wallet receives whole blocks but doesn&#39;t need to waste resour=
ces on decoding them if the environment is resource constrained. Bob simply=
 needs find the string BIPXXXX in the binary blob that represents an undeco=
ded block. Once found, Bob extracts the subsequent 32 bytes (`notification`=
) and the subsequent 33 bytes (`N_Alice`). The benefit of this approach is =
that Bob doesn&#39;t have to decode blocks and extract pubkeys from scripts=
igs.<br>
<br>
Since ECDH dictates that SHA256(n_Alice * P_Bob) =3D=3D SHA256(N_Alice * p_=
Bob), Bob calculates the expected notification value and checks if it match=
es the first value in the payload. If so, Bob found a notification transact=
ion addressed to himself and stores `N_Alice` in order to be able to detect=
 and spend future payments from Alice. The added benefit of this approach o=
ver BIP47 is that Bob doesn&#39;t learn Alice&#39;s payment code, so Alice =
can pay Bob without revealing her identity. To take advantage of these priv=
acy benefits, Alice simply has to engage in coin control on her end. A real=
 world scenario where this might be useful is anonymous donations to a part=
y whose wallet may be seized in the future. Seizing such a wallet won&#39;t=
 reveal who Alice is (as long as she engages in coin control), whereas BIP4=
7 would by default leak her identity even if her coins as anonymized.<br>
<br>
If this process fails for any reason, Bob assumes a spurious notification o=
r one not addressed to himself and gives up.<br>
<br>
=3D=3DTransacting=3D=3D<br>
<br>
Now that they are connected, Alice can send transactions to Bob. Alice need=
s to keep track of her transaction count toward Bob; let&#39;s name that co=
unter `X`. This process is similar to what BIP47 does.<br>
<br>
Alice calculates a secret point:<br>
<br>
S =3D n_Alice * P_Bob<br>
<br>
Alice calculates a shared secret:<br>
<br>
s =3D SHA256(S, X)<br>
<br>
Alice calculates Bob&#39;s ephemeral public key and its associated address =
where the funds will be sent:<br>
<br>
P_Bob&#39; =3D P_Bob + s*G<br>
<br>
When Bob detects a payment to `P_Bob&#39;`, he can spend such coins by calc=
ulating the shared secret `s` in the same manner using `N_Alice` and `p_Bob=
` and performing:<br>
<br>
p_bob&#39; =3D p_bob + s<br>
<br>
The fact that Alice and Bob are using a shared counter means we can do away=
 with chain codes and make payment codes much smaller. Bob simply needs to =
derive a number of addresses to watch with respect to some gap limit (which=
 can be as low as 1 in practice).<br>
<br>
=3D=3DAnti-spam=3D=3D<br>
<br>
While DoS hasn&#39;t been a problem with BIP47, it is possible to build ant=
i-spam measures into payment codes. The owner of a code could simply demand=
 that a notification transaction meets some minimum miner fee or a multiple=
 of some trailing average. This would help prevent spam notifications that =
might otherwise overwhelm a payment code with addresses to watch. But that =
is purely optional.<br>
<br>
Looking forward to hearing thoughts and ideas.<br>
<br>
Alfred<br>
<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000ca44aa05e273cbb9--