npub1at…y3z5a

Last Notes

2023-07-28 15:08:07 UTC

- reply

📅 Original date posted:2023-07-27
🗒️ Summary of this message: Proof of knowledge of the r values used in Wagner's attack does not prevent the attack. The attacker chooses the r values.
📝 Original message:
No, proof of knowledge of the r values used to generate each R does not prevent
Wagner's attack. I wrote
> Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that
> c[0] + ... + c[K-1] = c[K].
You can think of this as actually choosing scalars r2[0], ..., r2[K-1] and
define R2[i] = r2[i]*G. The attacker chooses r2[i]. The attack wouldn't make
sense if he didn't.

2023-07-27 00:26:34 UTC

- reply

📅 Original date posted:2023-07-26
🗒️ Summary of this message: Blind Schnorr signatures can solve the issue of blinding, but not the problem of client-controlled forged signatures. Recent work proposes alternative approaches for blind Schnorr signatures.
📝 Original message:
While this may solve blinding, I don't see how it solves the problem that the
client can forge signatures because the client is in control of challenge e'.
This is not special to MuSig(2), but is also the reason why original blind
Schnorr signatures are insecure (as demonstrated in David Wagner's "A
Generalized Birthday Problem" paper).
For some more recent work on blind Schnorr signatures, see:
- https://eprint.iacr.org/2019/877.pdf Blind Schnorr Signatures and Signed
ElGamal Encryption in the Algebraic Group Mode
- https://eprint.iacr.org/2020/1071.pdf On Pairing-Free Blind Signature Schemes
in the Algebraic Group Model
In particular, the first paper proposes a less-efficient variant of blind
Schnorr signatures that is secure under concurrent signing if the "mROS" problem
is hard (which is imho plausible). Another potential approach is using
commitments and a ZKP as I mentioned earlier in this thread. This scheme is
"folklore", in the sense that it is being discussed from time to time but isn't
specified and does not have a security proof as far as I am aware.

2023-07-27 00:26:33 UTC

- reply

📅 Original date posted:2023-07-26
🗒️ Summary of this message: Attacks on nonces and challenges cannot be prevented by proving knowledge of the signing key (proof of possession, PoP).
📝 Original message:
None of the attacks mentioned in this thread so far (ZmnSCPxj mentioned an
attack on the nonces, I mentioned an attack on the challenge c) can be prevented
by proving knowledge of the signing key (usually known as proof of possession,
PoP).

2023-07-24 15:55:41 UTC

- reply

📅 Original date posted:2023-07-24
🗒️ Summary of this message: The meaning and connection between "posk" and the attack remains unclear and undefined.
📝 Original message:
Not sure what "posk" is or how it relates to the attack.

2023-07-24 15:55:41 UTC

- reply

📅 Original date posted:2023-07-24
🗒️ Summary of this message: Party 1 is unable to determine the final value of (R, s1+s2) or m, but a blinding step may be missing, allowing the server to scan the blockchain for signatures and compute corresponding hashes to check for a match.
📝 Original message:
> Party 1 never learns the final value of (R,s1+s2) or m.
Actually, it seems like a blinding step is missing. Assume the server (party 1)
received some c during the signature protocol. Can't the server scan the
blockchain for signatures, compute corresponding hashes c' = H(R||X||m) as in
signature verification and then check c == c'? If true, then the server has the
preimage for the c received from the client, including m.

2023-07-24 15:55:41 UTC

- reply

📅 Original date posted:2023-07-24
🗒️ Summary of this message: The text discusses concerns about the proposed scheme for blind music and suggests an alternative approach that may be worth exploring.
📝 Original message:
Hi Tom,
I'm not convinced that this works. As far as I know blind musig is still an open
research problem. What the scheme you propose appears to try to prevent is that
the server signs K times, but the client ends up with K+1 Schnorr signatures for
the aggregate of the server's and the clients key. I think it's possible to
apply a variant of the attack that makes MuSig1 insecure if the nonce commitment
round was skipped or if the message isn't determined before sending the nonce.
Here's how a malicious client would do that:
- Obtain K R-values R1[0], ..., R1[K-1] from the server
- Let
R[i] := R1[i] + R2[i] for all i <= K-1
R[K] := R1[0] + ... + R1[K-1]
c[i] := H(X, R[i], m[i]) for all i <= K.
Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that
c[0] + ... + c[K-1] = c[K].
- Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1].
- Let
s[K] = s[0] + ... + s[K-1].
Then (s[K], R[K]) is a valid signature from the server, since
s[K]*G = R[K] + c[K]*a1*X1,
which the client can complete to a signature for public key X.
What may work in your case is the following scheme:
- Client sends commitment to the public key X2, nonce R2 and message m to the
server.
- Server replies with nonce R1 = k1*G
- Client sends c to the server and proves in zero knowledge that c =
SHA256(X1 + X2, R1 + R2, m).
- Server replies with s1 = k1 + c*x1
However, this is just some quick intuition and I'm not sure if this actually
works, but maybe worth exploring.

2023-06-09 13:04:07 UTC

- reply

📅 Original date posted:2021-10-09
📝 Original message:
Hi,
it seems like parts of this proposal rely on deterministic nonces in MuSig.
Generally, this is insecure unless combined with heavy machinery that proves
correctness of the nonce derivation in zero knowledge. If one signer uses
deterministic nonces and another signer uses random nonces, then two signing
sessions will have different challenge hashes which results in nonce reuse by
the first signer [0]. Is there a countermeasure against this attack in the
proposal? What are the inputs to the function that derive DA1, DA2? Is the
assumption that a signer will not sign the same message more than once?
It may be worth pointing out that an adaptor signature scheme can not treat
MuSig2 as a black box as indicated in the "Adaptor Signatures" section [1]. In
particular, generally the secret X must be input to the hash function that
generates nonce coefficient k. Otherwise, an attacker can grind through
challenge hashes by varying X without affecting the aggregate nonce and produce
a forgery. For the same reason, the message m is included in hash function
inputs of k. However, taking X into account when computing k shouldn't be an
issue for protocols making use of adaptor signatures because k does not need to
be determined before signing time and X is required to be known at that point
anyway.
[0] https://medium.com/blockstream/musig-dn-schnorr-multisignatures-with-verifiably-deterministic-nonces-27424b5df9d6
See "The attack works as follows."
[1] MuSig2 adaptor signature issue: https://github.com/ElementsProject/scriptless-scripts/issues/23,
PR: https://github.com/ElementsProject/scriptless-scripts/pull/24

2023-06-09 13:04:07 UTC

- reply

📅 Original date posted:2021-10-10
📝 Original message:
> H( private-key, msg, other-party's-nonce-pair, 1 )
That should work. I had thought that other-party's-nonce-pair would be unique
unknown randomness, but I can see now that it can be rederived from RA(n) or
RB(n).
> Hmm, you had me panicking that I'd been describing how to combine the
> two despite having decided it wasn't necessary to combine them...
Ah, should have read that part more closely. The proposal uses the single sig
adaptor sig variant.

2023-06-07 23:11:19 UTC

- reply

📅 Original date posted:2022-07-08
📝 Original message:Half-aggregation has been mentioned several times on this list in various
contexts. To have a solid basis for discussing applications of half-aggregation,
I think it's helpful to have a concrete specification of the scheme and a place
for collecting supplemental information like references to cryptographic
security proofs. You can find the BIP draft at
https://github.com/ElementsProject/cross-input-aggregation/blob/master/half-aggregation.mediawiki
Similar to BIP-340, this BIP draft specifies only the cryptographic scheme and
does not prescribe specific applications. It has not received an extensive
security review yet. Thanks to Elliott Jin and Tim Ruffing for the review so
far. One new feature that the specified scheme has is "incremental aggregation"
which allows aggregating additional BIP-340 signatures into an existing
half-aggregate signature.
While BIP-340 has a pseudocode specification and a reference implementation in
python, this BIP draft has a formal specification written in hacspec [0] and
auxiliary pseudocode. The formal specification is a mathematically precise
description of the scheme, which paves the way for computer-aided formal proofs.
Software tools ("proof assistants") allow proving properties about the formal
specification ("no integer overflow") and apply formal software verification
("implementation is behaviorally equivalent to the spec"). I don't have concrete
plans (nor the skillset) to use these techniques. Still, I think this is an
exciting area to explore because it has the potential to increase the Bitcoin
ecosystem's robustness significantly and has little downside. Since hacspec's
syntax is a subset of Rust's syntax, one can use the standard rust toolchain to
compile, execute and test the specification.
You can find a blog post that gives a broader context at
https://blog.blockstream.com/half-aggregation-of-bip-340-signatures/
[0] https://github.com/hacspec/hacspec

2023-06-07 23:09:58 UTC

- reply

📅 Original date posted:2022-05-26
📝 Original message:Thanks for the detailed feedback. Let me try to summarize your argument: Key
aggregation should fail if there are duplicate keys because this is likely a bug
and continuing might be dangerous. If it is not a bug but a dishonest signer
trying to disrupt, then resuming the protocol and trying to identify the
dishonest signer does not work because partial signatures are not real
signatures.
I disagree that identifying dishonest signers is useless. But if I try hard, I
can see your point that honest signers should not continue in order to protect
terribly broken implementations. Broken could mean that signers reuse nonces,
output their secret key instead of a partial signature, etc. However, terribly
broken implementations are terribly broken. It seems very unlikely that they're
nice enough to truthfully indicate their brokenness by copying someone elses
public key. Perhaps they use the sum of every other key, actually create a
proper public key, or do something entirely different. So I think in practice,
it is implausible to find a single instance of an implementation that doesn't
survive partial signature creation by looking at duplicate public keys.
However, your suggestion to abort in KeyAgg when encountering duplicate public
keys is compatible with the MuSig2 BIP draft. No one can force a signer to
accept an arbitrary set of public keys for the multi-signature, so signers are
always fine to abort at the key aggregation stage to try to protect terribly
broken co-signers. In that sense, the BIP draft takes a more general and
flexible approach. I doubt that identifying duplicate public keys is less
complex. The only consequence of allowing duplicate public keys is that the
`GetSecondKey` is required to loop over the public keys. Aborting when
encountering duplicate public keys also has the added complexity of giving users
the unspecific instruction to "debug signers X and Y" versus "there's something
definitely wrong with signer Z".
As mentioned above, I don't follow your argument that identifying signers
claiming the public key of other signers is useless. I do think the "persistent"
case is interesting. It's easy to imagine persistent identities not tied to
secp256k1 curve points. Only for creating BIP-340 multi-signatures do they use
secp256k1 public keys. These keys can be fresh, or if they are persistent, the
participants may want to rotate them from time to time. So there are plenty of
opportunities for an attacker to overtake a participant and try to disrupt the
protocol. You mention that duplicating keys would require "a Sybil at two
indices", but actually a single malicious signer that copies some public key is
sufficient.
Your analysis of the "spontaneous" case misses that partial signature
verification identifies at least one of the dishonest signers and therefore
allows to make progress. This closes the DoS vector as far as the MuSig protocol
is concerned. If there are multiple disruptive signers, they may not all be
identified in a single round but require multiple signing attempts. Of course,
applications that use MuSig and replace disruptive signers with just some other
arbitrary nym may be so unlucky that it always has disruptive signers. But
that's a problem of the application layer, and it's easy to conceive smarter
peer selection.
I agree that the claim "any signer who prevents a signing session from
completing successfully by sending incorrect contributions in the session can be
identified" is incorrect. We can identify at least one, and that means
applications can make progress. I opened a PR to fix the wording [0].
[0] https://github.com/jonasnick/bips/pull/25

2023-06-07 23:09:57 UTC

- reply

📅 Original date posted:2022-05-23
📝 Original message:Thank you for taking the time to look at the BIP and reference code, waxwing. I
don't know if you're overlooking anything, so let me try to restate the
paragraph in the BIP draft that attempts to cover this topic [0].
Suppose signers would just abort in the presence of identical public keys. In
that case, a disruptive signer can permanently DoS-attack a session by simply
copying the public key of some other signer. Therefore, the BIP is much more
useful if it can deal with identical public keys.
The MuSig2 BIP draft requires some added complexity to handle identical public
keys (because of the MuSig2* optimization). But this solution naturally allows
identifying and removing disruptive signers, which ultimately reduces the
complexity for MuSig2 users.
[0] https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki#public-key-aggregation

2023-06-07 23:07:00 UTC

- reply

📅 Original date posted:2022-04-28
📝 Original message:Happy to hear that the BIP draft is already useful and thank you, Laolu, for
extracting the test vectors.
> an implementation must make the _pre tweaked_ combined key available to the caller
To apply the Taproot tweak with the key aggregation algorithm as specified you
would have to do the following (slightly simplified):
P := KeyAgg(pk_1, ..., pk_n, tweaks = [])
t := hash_TapTweak(P, root)
Q := KeyAgg(pk_1, ..., pk_n, tweaks = [t])
This unnecessarily recomputes the pre-tweaked key aggregate. In the BIP, there
are more places where the specified algorithms unnecessarily recompute certain
values. I believe this is justified if it makes the spec significantly easier to
understand. In this case, however, it's clear that calling KeyAgg multiple times
for the same set of public keys is not intuitive at all. This is something I had
not fully considered before. Thanks for bringing it up.
The approach you're taking in btcd makes a lot of sense to me. But in the
specification, we want to avoid specifying how exactly the tweaks are derived.
In the libsecp256k1-zkp implementation, key aggregation and tweaking are
separated into different functions. But this requires keeping state between key
aggregation and tweaking, which is why we had not chosen this approach for the
BIP. I will investigate how in the BIP, we can also split key aggregation and
tweaking and minimize complexity.
> My reading here is that [...] last party doesn't (?) need to worry about their
> nonces
Your reading is mostly right. Brandon describes correctly how and why to modify
the nonce generation algorithm. I opened a PR that replaces the description of
this signing mode with a precise specification. Indeed, the result is that the
last party doesn't need to worry about their nonce (even if the other parties
use bad randomness).
[0] https://github.com/jonasnick/bips/pull/11

2023-06-07 23:06:59 UTC

- reply

📅 Original date posted:2022-04-05
📝 Original message:Tim Ruffing, Elliott Jin, and I are working on a MuSig2 BIP that we would like
to propose to the community for discussion. The BIP is compatible with BIP340
public keys and signatures. It supports tweaking, which allows deriving BIP32
child keys from aggregate keys and creating BIP341 Taproot outputs with key and
script paths. You can find the BIP draft at:
https://github.com/jonasnick/bips/blob/musig2/bip-musig2.mediawiki
The draft is in a state where it should be possible to write an implementation
based on the BIP that passes the basic test vectors (as, e.g., demonstrated by
[0]). The draft BIP also contains a reference implementation in python. Please
be aware that this is only a draft and that it may still be necessary to make
small tweaks to the algorithms and test vectors.
[0] https://github.com/btcsuite/btcd/pull/1820

2023-06-07 18:24:14 UTC

- reply

📅 Original date posted:2020-05-05
📝 Original message:This is a reasonable suggestion. Committing to every spent scriptPubKey and
therefore every element of the TxOut instead of just the amount makes sense
conceptually. And it would be a small diff (~4 lines + rationale) compared to
the current bip-taproot version.
As far aas I understand, coinjoin with offline signers would be substantially
harder without this proposal. There is a WIP "SLIP" that helped me understand
how the Proof of Ownership would work [0]. For every input, the offline signing
device verifies a signature against the corresponding scriptPubKey. In order to
obtain the correct scriptPubKey, sending the whole input transaction to the
signing device is prohibitive when the available bandwidth is low (QR codes).
The idea of only sending the transaction midstate along with the rest of
to-be-hashed transaction data is an improvement, but still results in a lot of
data (whole vout and witness stacks). Adding a new sighash flag that marks
coinjoin transactions would be a step backwards fungibility-wise.
Thus, the same reasoning for for committing to the input values in the
transaction digest to allow compact fee proofs would similarly apply the
scriptPubKeys - with the only difference that coinjoins with offline signers are
less common.
The downsides of this proposal seem to be limited. It requires additional
review, but the BIP is only in the draft stage and should incorporate reasonable
feedback. It does not invite further scope creep because the full TxOut would be
already included. The costs to verifiers is only slightly increased using
Anthony Town's suggested sighash change. Availability of the scriptPubKeys for
signing devices does not seem to be an issue because the input amounts are
already required. And if all inputs belong to the signing device, there's no
additional data sent to the device.
[0] https://github.com/satoshilabs/slips/blob/slips-19-20-coinjoin-proofs/slip-0019.md
On 4/29/20 2:57 PM, Andrew Kozlik via bitcoin-dev wrote:
> Hi everyone,
>
> In the current draft of BIP-0341 [1] the signature message commits to the
> scriptPubKey of the output being spent by the input. I propose that the
> signature message should commit to the scriptPubKeys of *all* transaction
> inputs.
>
> In certain applications like CoinJoin, a wallet has to deal with
> transactions containing external inputs. To calculate the actual amount
> that the user is spending, the wallet needs to reliably determine for each
> input whether it belongs to the wallet or not. Without such a mechanism an
> adversary can fool the wallet into displaying incorrect information about
> the amount being spent, which can result in theft of user funds [2].
>
> In order to ascertain non-ownership of an input which is claimed to be
> external, the wallet needs the scriptPubKey of the previous output spent by
> this input. It must acquire the full transaction being spent and verify its
> hash against that which is given in the outpoint. This is an obstacle in
> the implementation of lightweight air-gapped wallets and hardware wallets
> in general. If the signature message would commit to the scriptPubKeys of
> all transaction inputs, then the wallet would only need to acquire the
> scriptPubKey of the output being spent without having to acquire and verify
> the hash of the entire previous transaction. If an attacker would provide
> an incorrect scriptPubKey, then that would cause the wallet to generate an
> invalid signature message.
>
> Note that committing only to the scriptPubKey of the output being spent is
> insufficient for this application, because the scriptPubKeys which are
> needed to ascertain non-ownership of external inputs are precisely the ones
> that would not be included in any of the signature messages produced by the
> wallet.
>
> The obvious way to implement this is to add another hash to the signature
> message:
> sha_scriptPubKeys (32): the SHA256 of the serialization of all
> scriptPubKeys of the previous outputs spent by this transaction.
>
> Cheers,
> Andrew Kozlik
>
> [1]
> https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#common-signature-message
> [2]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014843.html
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

2023-06-07 18:22:52 UTC

- reply

📅 Original date posted:2020-02-10
📝 Original message:I agree with most of the comments so far, but the group brings up an often
overlooked point with respect to the privacy benefits of taproot. In the extreme
case, if there would be no policies that have both a key and a script spend
path, then taproot does not improve anonymity sets compared to the "Taproot
Public NUMS Optimization" proposal (which saves 8 vbytes in a script-spend). (*)
In fact, the cases where scripts would have to be used given usage of Bitcoin
today are be rare because threshold policies, their conjunctions and
disjunctions can be expressed with a single public key. Even if we disregard
speculation that timelocks, ANYPREVOUT/NOINPUT and other interesting scripts
will be used in the future (which can be added through the leaf or key versions
without affecting key-spend anonymity sets), not all of today's applications are
able to be represented single public keys because there are applications that
can not deal with interactive key setups or interactive signing. For
applications where this is possible it will be a gradual change because of the
engineering challenges involved. For example, k-of-n threshold policies could
have the most likely k-of-k in the taproot output key and other k-of-k in the
leaves, instead of going for a k-of-n taproot output key immediately.
Given that anonymity sets in Bitcoin are permanent and software tends to be
deployed longer than anyone would expect at the time of deployment,
realistically Taproot is superior to the "Public NUMS Optimization" and "An
Alternative Deployment Path".
(*) One could argue that the little plausible deniability gained by a very small
probability of the change of a script-spend being a key-spend and vice versa is
significantly better than no probability at all.
On 2/9/20 8:47 PM, Bryan Bishop via bitcoin-dev wrote:
> Apologies for my previous attempt at relaying the message- it looks like
> the emails got mangled on the archive. I am re-sending them in this
> combined email with what I hope will be better formatting. Again this is
> from some nym that had trouble posting to this mailing list; I didn't see
> any emails in the queue so I couldn't help to publish this sooner.
>
> SUBJECT: Taproot (and Graftroot) Complexity
>
> This email is the first of a collection of sentiments from a group of
> developers who in aggregate prefer to remain anonymous. These emails have
> been sent under a pseudonym so as to keep the focus of discussion on the
> merits of the technical issues, rather than miring the discussion in
> personal politics. Our goal isn't to cause a schism, but rather to help
> figure out what the path forward is with Taproot. To that end, we:
>
> 1) Discuss the merits of Taproot's design versus simpler alternatives (see
> thread subject, "Taproot (and Graftroot) Complexity").
>
> 2) Propose an alternative path to deploying the technologies described in
> BIP-340, BIP-341, and BIP-342 (see thread subject, "An Alternative
> Deployment Path for Taproot Technologies").
>
> 3) Suggest a modification to Taproot to reduce some of the overhead (see
> thread subject, "Taproot Public NUMS Optimization").
>
> Now that the BIP has moved to draft we felt that now was the time to
> prioritize review to make sure it was an acceptable change for our
> activities. As a group, we're excited about the totality of what Taproot
> has to offer. However, after our review, we're left perplexed about the
> development of Taproot (and Graftroot, to a lesser extent).
>
> We also want to convey that we have nothing but respect for the developers
> and community who have poured their heart and soul into preparing Taproot.
> Self evidently, it is an impressive synthesis of ideas. We believe that the
> highest form of respect to pay such a synthesis of ideas is a detailed and
> critical review, as it's pertinent to closely consider changes to Bitcoin.
>
>
> In essence, Taproot is fundamentally the same as doing
> https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki and Schnorr
> signatures separately.
>
> The main reason for putting them together -- as mentioned in the BIP -- is
> a gain in efficiency. But this efficiency pre-supposes a specific use case
> and probability distribution of use cases.
>
> Compare:
>
> Suppose a MAST for {a,b,c,d,e,f,g,h} spending conditions it looks something
> like this:
>
>
> /\
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f g h
>
> If we want this to be functionally equivalent to Taproot, we add a new path:
>
> /\
> /\ {<pk> schnorr_checksig}
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f g h
>
> Now, to spend from this MBV you have to reveal 32 bytes on the stack for
> the not taken branch, and 35 bytes for the <pk> schnorr_checksig (1 byte
> push, 33 bytes PK, 1 byte checksig).
>
> This is 67 bytes more than Taproot would require for the same spending
> condition.
>
> However, suppose we wanted to use one of the script paths instead. We still
> need to have one extra hash for the {<pk> schnorr_checksig} (depending on
> if we put the key in this position or not--see below). But now we can spend
> with just a logarithmic control program path.
>
> However, if we do the same script via taproot, we now need to provide the
> base public key (33 bytes) as well as the root hash (32 bytes) and path and
> then the actual scripts. With the need for 2 push bytes, this ends up being
> back at 67 bytes extra.
>
> Is Taproot just a probability assumption about the frequency and likelihood
> of the signature case over the script case? Is this a good assumption? The
> BIP only goes as far as to claim that the advantage is apparent if the
> outputs *could be spent* as an N of N, but doesn't make representations
> about how likely that N of N case would be in practice compared to the
> script paths. Perhaps among use cases, more than half of the ones we expect
> people to be doing could be spent as an N of N. But how frequently would
> that path get used? Further, while the *use cases* might skew toward things
> with N of N opt-out, we might end up in a power law case where it's the one
> case that doesn't use an N of N opt out at all (or at a de minimis level)
> that becomes very popular, thereby making Taproot more costly then
> beneficial.
>
> Further, if you don't want to use a Taproot top-level key (e.g., you need
> to be able to audit that no one can spend outside of one of the script
> conditions), then you need to use a NUMS (nothing up my sleeve) point. This
> forces users who don't want Taproot to pay the expense, when if they just
> had a MAST based witness type they would be cheaper. So if this use case is
> at all common, Taproot leaves them worse off in terms of fees. Given that
> script paths are usually done in the case where there is some contested
> close, it's actually in the interest of protocol developers that the
> contested script path be as efficient as possible so that the fees paid
> maximally increase the feerate. We think this can be fixed simply in
> Taproot though, as noted below.
>
>
>
> On privacy, we're also a bit confused as to the goal of Taproot over MAST
> and Schnorr. Earlier, we presented a design with MAST which is very close
> to Taproot. However, it'd also be possible to just add {<pk>
> schnorr_checksig} to the set {a,b,c,d,e,f,g,h}, shuffle them, and compute
> some MAST structure (perhaps probability encoded) on them. This has the
> effect of not having much additional fees for adding the extra Schnorr path
> at redeem time (only 1 extra branch on 2/8 script paths), e.g.
>
>
> /\
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f/\ {<pk> schnorr_checksig}
> g h
>
> We could argue that this is more private than Taproot, because we don't
> distinguish between the Schnorr key case and other cases by default, so
> chain analyzers can't tell if the signature came from the Taproot case or
> from one of the Script paths. There's also no NUMS point required, which
> means chain analyzers can't tell when you spend that there was no top level
> key if the NUMS point is not per-output indistinguishable. By using a
> semi-randomized MAST structure, chain analyzers also can't tell exactly how
> big your spend condition MAST was. In particular, you care more about
> privacy when you are contesting a close of a channel or other script path
> because then the miners could be more likely to extract a rent from you as
> "ransom" for properly closing your channel (or in other words, in a
> contested close the value of the closing transaction is larger than usual).
>
> It would also be possible to do something really simple which is to allow
> the witness type to be either a MAST hash OR a schnorr key (but not a
> Taproot). This allows you to not completely fracture the anonymity set
> between people who want plain Schnorr and people who want MAST (at least
> until they go to spend). This fix can also be used in Taproot in place of a
> NUMS point, to decrease extra fees. It's unclear if this plays negatively
> with any future batch validation mechanism though, but the contextual
> checks to exclude a witness program from the batch are relatively simple.
> See thread subject, "Taproot Public NUMS Optimization".
>
> The considerations around Graftroot, a proposed delegation mechanism, is a
> bit similar. Delegation is a mechanism by which a UTXO with script S can
> sign a script R which can then be executed in addition to S without
> requiring a transaction. This allows an output to monotonically and
> dynamically increase the number of conditions under which it can be spent.
> As noted by Pieter Wiulle here:
> https://github.com/kanzure/diyhpluswiki/commit/a03f6567d714f8733b578de263a4b149441cd058
> delegation was originally possible in Bitcoin, but got broken during an
> emergency fork to split the scriptSig and scriptpubkey separation. Rather
> than adding some fancy delegation mechanism in Bitcoin, why not just have a
> P2SH-like semantic which allows a delegated script to be evaluated? See
> BIP-117 https://github.com/bitcoin/bips/blob/master/bip-0117.mediawiki.
> This way we aren't special casing where delegation can occur, and we can
> allow taproot nested spending conditions (i.e., with timelocks) to generate
> their own delegations. As I've seen Graftroot discussed thus far, it is as
> a top-level witness program version like Taproot and non-recursive. Similar
> to the above discussion, top-level is more efficient if you suspect that
> delegation will be most likely occurring at the top level, but it's not
> clear that's a good assumption as it may be common to want to allow
> different scripts to delegate.
>
>
> Overall, we are left with concerns both about the merit of doing Taproot
> versus alternatives, as well as the process through which we got to be here.
>
> 1) Is Taproot actually more private than bare MAST and Schnorr separately?
> What are the actual anonymity set benefits compared to doing the separately?
>
> 2) Is Taproot actually cheaper than bare MAST and Schnorr separately? What
> evidence do we have that the assumption it will be more common to use
> Taproot with a key will outweigh Script cases?
>
> 3) Is Taproot riskier than bare MAST and Schnorr separately given the new
> crypto? How well reviewed is the actual crypto parts? None of us personally
> feel comfortable reviewing the crypto in Schnorr -- what's the set of
> people who have thoroughly reviewed the crypto and aren't just ACKing
> because they trust other developers to have looked at it close enough?
>
> 4) Design wise, couldn't we forego the NUMS point requirement and be able
> to check if it's a hash root directly? This would encumber users who don't
> need the key path a cheaper spend path. See thread subject, "Taproot Public
> NUMS Optimization".
>
> 5) Is the development model of trying to jam a bunch of features into
> Bitcoin all at once good for Bitcoin development? Would we be better off if
> we embraced incremental improvements that can work together (e.g., MAST and
> then Schnorr)? Although the BIP raises some points about anonymity sets
> being why to do them all at once, it's not clear to me this argument holds
> water (same goes for businesses not upgrading). If we can take things as
> smaller steps, we are not only more secure, but we also have more time to
> dedicate review to each change independently. We also end up co-mingling
> changes that people end up accepting only because they want one and they're
> bundled (e.g., MAST and Schnorr, MAST seems like a much less risky addition
> versus Schnorr). See thread subject, "An Alternative Deployment Path for
> Taproot Technologies".
>
>
>
>
> Our provocation with this email is primarily that we think we should more
> carefully consider the benefits of Taproot over simpler primitives that are
> not only easier to review, but could have been made available much sooner
> rather than waiting on putting everything all together for an unclear
> aggregate benefit.
>
> We do think that most of the developers have been honest about the benefits
> of Taproot, but that on closer look we feel the general ecosystem has
> oversold Taproot as being the key enabler for a collection of techniques
> that we could do with much simpler building blocks.
>
>
> At the end of the day, we do not strongly advocate not deploying Taproot at
> this point in the review cycle. We think the Taproot Public NUMS
> Optimization may be a good idea, worth considering if it's not insecure, as
> it cuts through the case where you would otherwise need a NUMS point.
> Things like TapScript and its MAST mechanisms are well designed and offer
> exciting new deployment paths, and would be something we would use even if
> we opted for MAST instead of Taproot. However, we also believe it is our
> duty to raise these concerns and suggestions, and we look forward to
> listening to the responses of the community.
>
> Great thanks,
>
> The Group
>
> ----
>
> SUBJECT: An Alternative Deployment Path for Taproot Technologies
>
> This email is the second of a collection of sentiments from a group of
> developers who in aggregate prefer to remain anonymous. These emails have
> been sent under a pseudonym so as to keep the focus of discussion on the
> merits of the technical issues, rather than miring the discussion in
> personal politics. Our goal isn't to cause a schism, but rather to help
> figure out what the path forward is with Taproot. To that end, we: [clip
> repeat]
>
> As a follow up to our prior message, we propose a different path forward
> for the Taproot family of changes:
>
> 1) A separate soft-fork for Merkle Branch Witnesses based on Taproot;
>
> 2) A separate soft-fork for Schnorr Signatures
>
> 3) A separate follow up soft-fork which enables Taproot and Graftroot
>
> We think that the first 2 forks can be offered at the same time or one at a
> time.
>
> Taproot, as a follow up to changes 1 and 2, can be enabled as a soft-fork
> on the existing semantics, but requiring a new witness version. With the
> Public NUMS Optimization, wallets could upgrade by just changing one
> version byte to be in the same anonymity set as Taproot.
>
> It's not clear to us that the time to prepare a BIP and implementation for
> 1 and 2 at this point would be any less than the time to do Taproot as
> currently proposed. However, we believe that such a deployment plan is a
> reasonable option as it is more conservative, as Merkle Branch witnesses
> are relatively simple and users only have to use Schnorr signing if they
> want to, and can otherwise continue to use ECDSA. A further benefit of
> waiting on 3 is that we get to collect real world protocol engineering
> experience to see how frequently the Taproot frequency of use assumption
> holds, and if it is worth doing or not.
>
>
> Great thanks,
>
> The Group
>
>
> ----
>
> SUBJECT: Taproot Public NUMS Optimization
>
> This email is the third of a collection of sentiments from a group of
> developers who in aggregate prefer to remain anonymous. These emails have
> been sent under a pseudonym so as to keep the focus of discussion on the
> merits of the technical issues, rather than miring the discussion in
> personal politics. Our goal isn't to cause a schism, but rather to help
> figure out what the path forward is with Taproot. To that end, we: [clipped
> again]
>
> We propose to modify Taproot's specification in BIP-341 by adding the rule:
>
> If there is one element on the witness stack:
>
> 1) Attempt hashing it to see if it's equal to the witness program. The
> first byte is the control byte for leaf versioning.
>
> 2) If it's not the witness program, and it's 65 bytes, try signature
> validation
>
> If there is more than one element on the witness stack:
>
> If the control block is even, treat it as a non-Taproot MAST and get the
> leaf version as the last byte of the script (so you can pop it off before
> hashing).
>
>
> If greater anonymity is required, a NUMS point can still be used in
> Taproot, at the expense of the additional data. However, if NUMS points are
> just a couple well known constants this could actually decrease privacy as
> then the NUMS points could differ from application to application
> fingerprinting wallets. Instead, the NUMS point should only be used when a
> single use nonce can be sent, so that NUMS cannot be distinguished from a
> normal Taproot to a third party who doesn't know the setup (e.g., that the
> NUMS is H(X) for known X).
>
>
> Great thanks,
>
> The Group
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

2023-06-07 18:16:14 UTC

- reply

📅 Original date posted:2019-02-09
📝 Original message:Johnson's modification solves the issue I pointed out.
Moreover, as Johnson and I discussed in private, using different locktimes for
X and Y is not necessary. They can have the same relative locktime. If A and B
would only sign Y as soon as the update tx is confirmed, there is no risk of Y
changing its txid and therefore invalidating updates built on it.
On 2/9/19 10:15 AM, Johnson Lau wrote:
> This is really interesting. If I get it correctly, I think the fungibility hit could be avoided, just by making one more signature, and not affecting the blockchain space usage.
>
> Just some terminology first. In a 3-party channel, “main channel” means the one requires all parties to update, and “branch channel” requires only 2 parties to update.
>
> By what you describe, I think the most realistic scenario is “C is going to offline soon, and may or may not return. So the group wants to keep the main channel open, and create a branch channel for A and B, during the absence of C”. I guess this is what you mean by being able to "predict in advance who will become absent”
>
> I call this process as “semi-cooperative channel closing” (SCCC). During a SCCC, the settlement tx will have 2 outputs: one as (A & B), one as (C). Therefore, a branch channel could be opened with the (A & B) output. The channel opening must use NOINPUT signature, since we don’t know the txid of the settlement tx. With the output tagging requirement, (A & B) must be tagged, and lead to the fungibility loss you described.
>
> However, it is possible to make 2 settlement txs during SCCC. Outputs of the settlement tx X are tagged(A&B) and C. Outputs of the settlement tx Y are untagged(A&B) and C. Both X and Y are BIP68 relative-time-locked, but Y has a longer time lock.
>
> The branch channel is opened on top of the tagged output of tx X. If A and B want to close the channel without C, they need to publish the last update tx of the main channel. Once the update tx is confirmed, its txid becomes permanent, so are the txids of X and Y. If A and B decide to close the channel cooperatively, they could do it on top of the untagged output of tx Y, without using NOINPUT. There won’t be any fungibility loss. Other people will only see the uncooperative closing of the main channel, and couldn’t even tell the number of parties in the main channel. Unfortunately, the unusual long lock time of Y might still tell something.
>
> If anything goes wrong, A or B could publish X before the lock time of Y, and settle it through the usual eltoo style. Since this is an uncooperative closing anyway, the extra fungibility loss due to tagging is next to nothing. However, it may suggest that the main channel was a multi-party one.
>
> For C, the last update tx of the main channel and the settlement tx Y are the only things he needs to get the money back. C has to sign tx X, but he shouldn’t get the complete tx X. Otherwise, C might have an incentive to publish X in order to get the money back earlier, at the cost of fungibility loss of the branch channel.
>
> To minimise the fungibility loss, we’d better make it a social norm: if you sign your tx with NOINPUT, always try to make all outputs tagged to be NOINPUT-spendable. (NOTE: you can still spend tagged outputs with normal signatures, so this won’t permanently taint your coins as NOINPUT-spendable) It makes sense because the use of NOINPUT signature strongly suggests that you don’t know the txid of the parent tx, so you may most likely want your outputs to be NOINPUT-spendable as well. I thought of making this a policy or consensus rule, but may be it’s just overkill.
>
>
>
>> On 9 Feb 2019, at 3:01 AM, Jonas Nick <jonasdnick at gmail.com> wrote:
>>
>> Output tagging may result in reduced fungibility in multiparty eltoo channels.
>> If one party is unresponsive, the remaining participants want to remove
>> the party from the channel without downtime. This is possible by creating
>> settlement transactions which pay off the unresponsive party and fund a new
>> channel with the remaining participants.
>>
>> When the party becomes unresponsive, the channel is closed by broadcasting the
>> update transaction as usual. As soon as that happens the remaining
>> participants can start to update their new channel. Their update signatures
>> must use SIGHASH_NOINPUT. This is because in eltoo the settlement txid is not
>> final (because update tx is not confirmed and may have to rebind to another
>> output). Therefore, the funding output of the new channel must be NOINPUT
>> tagged. Assuming the remaining parties later settle cooperatively, this loss
>> of fungibility would not have happened without output tagging.
>>
>> funding output update output settlement outputs update output
>> [ A & B & C ] -> ... -> [ (A & B & C & state CLTV) | (As & Bs & Cs) ] -> [ NOINPUT tagged: (A' & B'), -> ...
>> C' ]
>> If the expectation is that the unresponsive party returns, fungibility is
>> not reduced due to output tagging because the above scheme can be used
>> off-chain until the original channel can be continued.
>>
>> Side note: I was not able to come up with an similar, eltoo-like protocol that works
>> if you can't predict in advance who will become absent.
>>
>> On 12/13/18 12:32 PM, Johnson Lau via bitcoin-dev wrote:
>>> NOINPUT is very powerful, but the tradeoff is the risks of signature replay. While the key holders are expected not to reuse key pair, little could be done to stop payers to reuse an address. Unfortunately, key-pair reuse has been a social and technical norm since the creation of Bitcoin (the first tx made in block 170 reused the previous public key). I don’t see any hope to change this norm any time soon, if possible at all.
>>>
>>> As the people who are designing the layer-1 protocol, we could always blame the payer and/or payee for their stupidity, just like those people laughed at victims of Ethereum dumb contracts (DAO, Parity multisig, etc). The existing bitcoin script language is so restrictive. It disallows many useful smart contracts, but at the same time prevented many dumb contracts. After all, “smart” and “dumb” are non-technical judgement. The DAO contract has always been faithfully executed. It’s dumb only for those invested in the project. For me, it was just a comedy show.
>>>
>>> So NOINPUT brings us more smart contract capacity, and at the same time we are one step closer to dumb contracts. The target is to find a design that exactly enables the smart contracts we want, while minimising the risks of misuse.
>>>
>>> The risk I am trying to mitigate is a payer mistakenly pay to a previous address with the exactly same amount, and the previous UTXO has been spent using NOINPUT. Accidental double payment is not uncommon. Even if the payee was honest and willing to refund, the money might have been spent with a replayed NOINPUT signature. Once people lost a significant amount of money this way, payers (mostly exchanges) may refuse to send money to anything other than P2PKH, native-P2WPKH and native-P2WSH (as the only 3 types without possibility of NOINPUT)
>>>
>>> The proposed solution is that an output must be “tagged” for it to be spendable with NOINPUT, and the “tag” must be made explicitly by the payer. There are 2 possible ways to do the tagging:
>>>
>>> 1. A certain bit in the tx version must be set
>>> 2. A certain bit in the scriptPubKey must be set
>>>
>>> I will analyse the pros and cons later.
>>>
>>> Using eltoo as example. The setup utxo is a simple 2-of-2 multisig, and should not be tagged. This makes it indistinguishable from normal 1-of-1 utxo. The trigger tx, which spends the setup utxo, should be tagged, so the update txs could spend the trigger utxo with NOINPUT. Similarly, all update txs should be tagged, so they could be spent by other update txs and settlement tx with NOINPUT. As the final destination, there is no need to tag in the settlement tx.
>>>
>>> In payer’s perspective, tagging means “I believe this address is for one-time-use only” Since we can’t control how other people manage their addresses, we should never do tagging when paying to other people.
>>>
>>> I mentioned 2 ways of tagging, and they have pros and cons. First of all, tagging in either way should not complicate the eltoo protocol in anyway, nor bring extra block space overhead.
>>>
>>> A clear advantage of tagging with scriptPubKey is we could tag on a per-output basis. However, scriptPubKey tagging is only possible with native-segwit, not P2SH. That means we have to disallow NOINPUT in P2SH-segwit (Otherwise, *all* P2SH addresses would become “risky” for payers) This should be ok for eltoo, since it has no reason to use P2SH-segwit in intermediate txs, which is more expensive.
>>>
>>> Another problem with scriptPubKey tagging is all the existing bech32 implementations will not understand the special tag, and will pay to a tagged address as usual. An upgrade would be needed for them to refuse sending to tagged addresses by default.
>>>
>>> On the other hand, tagging with tx version will also protect P2SH-segwit, and all existing wallets are protected by default. However, it is somewhat a layer violation and you could only tag all or none output in the same tx. Also, as Bitcoin Core has just removed the tx version from the UTXO database, adding it back could be a little bit annoying, but doable.
>>>
>>> There is an extension to the version tagging, which could make NOINPUT even safer. In addition to tagging requirement, NOINPUT will also sign the version of the previous tx. If the wallet always uses a randomised tx version, it makes accidental replay very unlikely. However, that will burn a few more bits in the tx version field.
>>>
>>> While this seems fully compatible with eltoo, is there any other proposals require NOINPUT, and is adversely affected by either way of tagging?
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev at lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>
>
>

2023-06-07 18:16:10 UTC

- reply

📅 Original date posted:2019-02-08
📝 Original message:Output tagging may result in reduced fungibility in multiparty eltoo channels.
If one party is unresponsive, the remaining participants want to remove
the party from the channel without downtime. This is possible by creating
settlement transactions which pay off the unresponsive party and fund a new
channel with the remaining participants.
When the party becomes unresponsive, the channel is closed by broadcasting the
update transaction as usual. As soon as that happens the remaining
participants can start to update their new channel. Their update signatures
must use SIGHASH_NOINPUT. This is because in eltoo the settlement txid is not
final (because update tx is not confirmed and may have to rebind to another
output). Therefore, the funding output of the new channel must be NOINPUT
tagged. Assuming the remaining parties later settle cooperatively, this loss
of fungibility would not have happened without output tagging.
funding output update output settlement outputs update output
[ A & B & C ] -> ... -> [ (A & B & C & state CLTV) | (As & Bs & Cs) ] -> [ NOINPUT tagged: (A' & B'), -> ...
C' ]
If the expectation is that the unresponsive party returns, fungibility is
not reduced due to output tagging because the above scheme can be used
off-chain until the original channel can be continued.
Side note: I was not able to come up with an similar, eltoo-like protocol that works
if you can't predict in advance who will become absent.
On 12/13/18 12:32 PM, Johnson Lau via bitcoin-dev wrote:
> NOINPUT is very powerful, but the tradeoff is the risks of signature replay. While the key holders are expected not to reuse key pair, little could be done to stop payers to reuse an address. Unfortunately, key-pair reuse has been a social and technical norm since the creation of Bitcoin (the first tx made in block 170 reused the previous public key). I don’t see any hope to change this norm any time soon, if possible at all.
>
> As the people who are designing the layer-1 protocol, we could always blame the payer and/or payee for their stupidity, just like those people laughed at victims of Ethereum dumb contracts (DAO, Parity multisig, etc). The existing bitcoin script language is so restrictive. It disallows many useful smart contracts, but at the same time prevented many dumb contracts. After all, “smart” and “dumb” are non-technical judgement. The DAO contract has always been faithfully executed. It’s dumb only for those invested in the project. For me, it was just a comedy show.
>
> So NOINPUT brings us more smart contract capacity, and at the same time we are one step closer to dumb contracts. The target is to find a design that exactly enables the smart contracts we want, while minimising the risks of misuse.
>
> The risk I am trying to mitigate is a payer mistakenly pay to a previous address with the exactly same amount, and the previous UTXO has been spent using NOINPUT. Accidental double payment is not uncommon. Even if the payee was honest and willing to refund, the money might have been spent with a replayed NOINPUT signature. Once people lost a significant amount of money this way, payers (mostly exchanges) may refuse to send money to anything other than P2PKH, native-P2WPKH and native-P2WSH (as the only 3 types without possibility of NOINPUT)
>
> The proposed solution is that an output must be “tagged” for it to be spendable with NOINPUT, and the “tag” must be made explicitly by the payer. There are 2 possible ways to do the tagging:
>
> 1. A certain bit in the tx version must be set
> 2. A certain bit in the scriptPubKey must be set
>
> I will analyse the pros and cons later.
>
> Using eltoo as example. The setup utxo is a simple 2-of-2 multisig, and should not be tagged. This makes it indistinguishable from normal 1-of-1 utxo. The trigger tx, which spends the setup utxo, should be tagged, so the update txs could spend the trigger utxo with NOINPUT. Similarly, all update txs should be tagged, so they could be spent by other update txs and settlement tx with NOINPUT. As the final destination, there is no need to tag in the settlement tx.
>
> In payer’s perspective, tagging means “I believe this address is for one-time-use only” Since we can’t control how other people manage their addresses, we should never do tagging when paying to other people.
>
> I mentioned 2 ways of tagging, and they have pros and cons. First of all, tagging in either way should not complicate the eltoo protocol in anyway, nor bring extra block space overhead.
>
> A clear advantage of tagging with scriptPubKey is we could tag on a per-output basis. However, scriptPubKey tagging is only possible with native-segwit, not P2SH. That means we have to disallow NOINPUT in P2SH-segwit (Otherwise, *all* P2SH addresses would become “risky” for payers) This should be ok for eltoo, since it has no reason to use P2SH-segwit in intermediate txs, which is more expensive.
>
> Another problem with scriptPubKey tagging is all the existing bech32 implementations will not understand the special tag, and will pay to a tagged address as usual. An upgrade would be needed for them to refuse sending to tagged addresses by default.
>
> On the other hand, tagging with tx version will also protect P2SH-segwit, and all existing wallets are protected by default. However, it is somewhat a layer violation and you could only tag all or none output in the same tx. Also, as Bitcoin Core has just removed the tx version from the UTXO database, adding it back could be a little bit annoying, but doable.
>
> There is an extension to the version tagging, which could make NOINPUT even safer. In addition to tagging requirement, NOINPUT will also sign the version of the previous tx. If the wallet always uses a randomised tx version, it makes accidental replay very unlikely. However, that will burn a few more bits in the tx version field.
>
> While this seems fully compatible with eltoo, is there any other proposals require NOINPUT, and is adversely affected by either way of tagging?
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>