[bitcoin-dev] libsecp256k1 v0.4.1 released
Hello, Today we'd like to announce the release of version 0.4.1 of libsecp256k1: https://github.com/bitcoin-core/secp256k1/releases/tag/v0.4.1 This release slightly increases the speed of the ECDH operation and significantly enhances the performance of many library functions when using the default configuration on x86_64. For a list of changes, see the CHANGELOG.md: https://github.com/bitcoin-core/secp256k1/blob/master/CHANGELOG.md ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for MuSig2 PSBT Fields
It is true that BIP 327 ("MuSig2") does not include adaptor signatures. The
rationale behind this decision was as follows:
- the BIP is already long and complicated enough without adaptor signatures; it
should be possible to propose a separate adaptor signature BIP on top in a
modular fashion
- as far as I know, there's no security proof except for a hard-to-follow sketch
that I wrote a few years ago [0]
- at the time, there seemed to be a higher demand for single-signer adaptor
signatures
In spite of the missing specification, we added some version of adaptor
signatures to the libsecp256k1-zkp MuSig2 module in order to allow
experimentation.
As for standardizing MuSig2 adaptor signatures, it seems noteworthy that there
exist alternative designs to the implementation in the libsecp256k1-zkp module:
the current libsecp256k1-zkp PR for (single-signer) Schnorr adaptor signatures
[1] uses a slightly different API. Instead of sending the adaptor point along
with the adaptor signature, the point is extracted from an adaptor signature.
This simplifies the API and reduces communication at the cost of making batch
verification of multiple adaptor sigs impossible.
[0] https://github.com/BlockstreamResearch/scriptless-scripts/pull/24
[1] https://github.com/BlockstreamResearch/secp256k1-zkp/pull/268
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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). ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
Not sure what "posk" is or how it relates to the attack. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
> 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. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Blinded 2-party Musig2
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. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] MuSig2 BIP
We updated the MuSig2 BIP draft to fix the vulnerability published in an earlier post [0]. We also wrote an article [1] that contains a description of 1. the vulnerable scheme (remember that the original MuSig2 scheme is not vulnerable because it doesn't allow tweaking) 2. an attack against the vulnerable scheme using Wagner's algorithm 3. a fixed scheme that permits tweaking Moreover, we implemented the "BLLOR" attack mentioned in the article which works against the reference python implementation of the previous version of the MuSig2 BIP draft (takes about 7 minutes on my machine) [2]. The fix of the MuSig2 BIP is equivalent to the fix of the scheme in the article [1]: before calling ''NonceGen'', the signer must determine the (potentially tweaked) secret key it will use for this signature. BIP MuSig2 now ensures that users can not accidentally violate this requirement by adding a mandatory public key argument to ''NonceGen'', appending the public key to the ''secnonce'' array and checking the public key against the secret key in ''Sign'' (see the pull request for the detailed changes [3]). [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021000.html [1] https://github.com/jonasnick/musig2-tweaking [2] https://gist.github.com/robot-dreams/89ce8c3ff16f70cb2c55ba4fe9fd1b31 (must be copied into the bip-musig2 directory) [3] https://github.com/jonasnick/bips/pull/74 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] MuSig2 BIP
It is still true that cryptography is hard, unfortunately. Yannick Seurin, Tim
Ruffing, Elliott Jin, and I discovered an attack against the latest version of
BIP MuSig2 in the case that a signer's individual key A = a*G is tweaked before
giving it as input to key aggregation.
In more detail, a signer may be vulnerable if _all_ of the following conditions
are true:
1. The signer supports signing with a tweaked individual key (as provided to
key aggregation) and the tweak is known to the attacker (e.g., as in BIP 32
unhardened derivation).
2. The signer's public key appears at least two times with different tweaks in
the set of public keys that are aggregated. This would, for example, be the
case if a signer with public key A=a*G creates partial signatures for an
aggregate key corresponding to public key set {A, A+t*G} where t is some
tweak. Note that an attacker could make this condition true by using the key
B = A+t*G after having seen A.
3. The signer uses "concurrent signing", i.e., the signer stores secnonces for
multiple signing sessions.
4. The secret key provided to the Sign algorithm is not yet fully determined
when the
NonceGen algorithm is called. This would, for example, be the case if the
attacker, after having seen the nonce of the signer, can influence whether a
or a+t will be provided as a secret key to Sign.
In this scenario, an attacker may forge a signature for any message and any
aggregate public key that contains the signer's individual public key A (with
any attacker-chosen tweak). In particular, the attacker may forge a signature
for any message and the public key A itself.
Condition 4 should only apply in relatively rare cases unless the signer is
tricked into such a situation.
Fix:
Note that if the optional secret key argument is provided to the NonceGen
algorithm and matches the secret key provided to the Sign algorithm, then
Condition 4 will not hold. Thus, one definite fix is to make the secret key
argument to the NonceGen algorithm mandatory. We are investigating other options
and will follow up shortly with a concrete fix of the BIP draft.
This discovery does not invalidate the security proof of the scheme as presented
in the MuSig2 paper because the security model in the paper does not support
tweaking a signer's key.
If you've implemented the BIP draft in your library or are already using it in
production don't hesitate to reach out to clarify the implications of this
discovery.
Tim Ruffing, Elliott Jin, Jonas Nick
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] MuSig2 BIP
Since the initial publication of the BIP draft, we incorporated feedback from this mailing list and the development git repository and made significant improvements compared to the initial version. There are multiple implementations today, and there have been no requests for major changes or features in the past weeks. This indicates that now is a good time to proceed with the next step of the BIP process. We opened a pull request with the MuSig2 BIP in the git repository: https://github.com/bitcoin/bips/pull/1372 Special thanks goes to my co-authors Tim Ruffing and Elliott Jin as well as Adam Gibson, Anthony Towns, arik-so, Bastien Teinturier, Brandon Black, Greg Sanders, Jesse Posner, Lloyd Fournier, mplsgrant, nickfarrow, niftynei, Olaoluwa Osuntokun, Pieter Wuille, Riccardo Casatta, Russell O'Connor and Rusty Russell for their valuable feedback. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP draft: Half-Aggregation of BIP-340 Signatures
To be clear, whether "half aggregation needs a new output type or not" does not become clear in the draft BIP because it is out of scope. Half-aggregation has a few possible applications. The draft only specifies the cryptographic scheme. The StackExchange post you link to argues that CISA requires a new output type. The same argument applies to half aggregating signatures across transaction inputs (CISHA, if you will). The only difference to "full aggregation" is that the transaction signature is a single half-aggregate signature instead of a 64-byte signature. You're right that it's possible to do batch verification of Taproot output key spends (Schnorr signatures) and script spends (key tweaks). ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] BIP draft: Half-Aggregation of BIP-340 Signatures
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
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] MuSig2 BIP
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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] MuSig2 BIP
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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] MuSig2 BIP
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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
On the topic of half aggregation, Chalkias et al. gave a convincing security proof last year: https://eprint.iacr.org/2021/350 As an aside, half aggregation is not exactly the scheme in the OP because that one is insecure. This does not affect Zmn's conclusion and was already pointed out in the original half aggregation thread: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014306.html It is required that each of the "s"-values are multiplied with a different unpredictable value, for example like this: https://github.com/ElementsProject/cross-input-aggregation/blob/master/slides/2021-Q2-halfagg-impl.org#schnorr-signature-half-aggregation-1 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] [dlc-dev] CTV dramatically improves DLCs
Thank you, that's an interesting application of OP_CTV. Perhaps worth pointing out that this does not require OP_CTV but could also be enabled by other covenant constructions. For example, it seems like ANYPREVOUT-based covenants provide similar benefits. The script of the Taproot leaves could be set to CHECKSIGVERIFY CHECKSIGVERIFY where is an ANYPREVOUTANYSCRIPT signature of the CET for public key P = G. When using nonce R = G, signature creation has negligible computational cost (s = 1 + H(R, P, m)). A downside compared to CTV is the additional overhead of 64 witness bytes (). ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility
> [...] we can use 2-party ECDSA to create 2-of-2 multisignature addresses that > look the same as regular single-signature addresses[2]. Even the old-style > p2pkh addresses starting with 1 can be CoinSwap addresses. Probably worth considering that p2pkh, p2wpkh and p2sh are vulnerable to the (well-known) birthday attack with 2^80 operations on average if they encode a multisig policy [0]. This is a large number but not the security margin we are used to. It is possible to reduce the feasibility of the attack by requiring 2^80 interactions instead of purely offline operations. This works by adding a commitment round for all public keys involved in the policy. Now in order to test whether a public key results in a collision, the attacker must first engage in a commitment protocol with that public key. The "Fast Secure Two-Party ECDSA Signing" protocol by Lindell [1] already has such a commitment round (for reasons unrelated to Bitcoin). For example, the Gotham City two-party ECDSA wallet [2] has this security model because it builds on the Lindell scheme and uses p2sh-p2wpkh. [0] https://bitcoin.stackexchange.com/questions/54841/birthday-attack-on-p2sh [1] https://eprint.iacr.org/2017/552.pdf [2] https://github.com/KZen-networks/gotham-city On 5/25/20 1:21 PM, Chris Belcher via bitcoin-dev wrote: > === Abstract === > > Imagine a future where a user Alice has bitcoins and wants to send them > with maximal privacy, so she creates a special kind of transaction. For > anyone looking at the blockchain her transaction appears completely > normal with her coins seemingly going from address A to address B. But > in reality her coins end up in address Z which is entirely unconnected > to either A or B. > > Now imagine another user, Carol, who isn't too bothered by privacy and > sends her bitcoin using a regular wallet which exists today. But because > Carol's transaction looks exactly the same as Alice's, anybody analyzing > the blockchain must now deal with the possibility that Carol's > transaction actually sent her coins to a totally unconnected address. So > Carol's privacy is improved even though she didn't change her behaviour, > and perhaps had never even heard of this software. > > In a world where advertisers, social media and other companies want to > collect all of Alice's and Carol's data, such privacy improvement would > be incredibly valuable. And also the doubt added to every transaction > would greatly boost the fungibility of bitcoin and so make it a better > form of money. > > This undetectable privacy can be developed today by implementing > CoinSwap, although by itself that isn't enough. There must be many > building blocks which together make a good system. The software could be > standalone as a kind of bitcoin mixing app, but it could also be a > library that existing wallets can implement allowing their users to send > Bitcoin transactions with much greater privacy. > > == CoinSwap == > > Like CoinJoin, CoinSwap was invented in 2013 by Greg Maxwell[1]. Unlike > CoinJoin it is relatively complicated to implement and so far has not > been deployed. But the idea holds great promise, and fixes many of the > problems of some kinds of CoinJoins. CoinSwap is the next step for > on-chain bitcoin privacy. > > CoinSwap is a way of trading one coin for another coin in a > non-custodial way. It is closely related to the idea of an atomic swap. > Alice and Bob can trade coins with each other by first sending to a > CoinSwap address and having those coins then sent to Bob: > > Alice's Address 1 > CoinSwap Address 1 > Bob's Address 1 > > An entirely separate set of transactions gives Bob's coins to Alice in > return: > > Bob's Address 2 > CoinSwap Address 2 > Alice's Address 2 > > Where the symbol > is a bitcoin transaction. > > Privacy is improved because an observer of the blockchain cannot link > Alice's Address 1 to Alice's Address 2, as there is no transaction > between them. Alice's Address 2 could either be an address in Alice's > wallet, or the address of someone else she wants to transfer money to. > CoinSwap therefore breaks the transaction graph heuristic, which is the > assumption that if a transaction A -> B is seen then the ownership of > funds actually went from A to B. > > CoinSwap doesnt break any of bitcoin's assumptions or features like an > auditable supply or pruning. It can be built on today's bitcoin without > any new soft forks. > > CoinSwap can't improve privacy much on its own, so it requires other > building block to create a truly private system. > > === ECDSA-2P === > > The original CoinSwap idea uses 2-of-2 multisig. We can get a slightly > bigger anonymity set by using 2-of-3 multisigs with a fake third public > key. For a much greater anonymity set we can use 2-party ECDSA to create > 2-of-2 multisignature addresses that look the same as regular > single-signature addresses[2]. Even the old-style p2pkh addresses > starting
Re: [bitcoin-dev] BIP-341: Committing to all scriptPubKeys in the signature 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@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation
> Let me put change (1) into my own words. Correct, except that the speedup from is_even(y) over is_quadratic_residue(y) affects signing and not keypair generation. > With change (2), I feel like including this auxiliary random data is overkill > for the spec. [...] I feel similarly about hashing the public key to get the > nonce. It's not clear why removing these features from the spec would be an improvement. The BIP follows a more reasonable approach: it specifies a reasonably secure signing algorithm and provides the rationale behind the design choices. This allows anyone to optimize for their use case if they choose to do so. Importantly, "reasonably secure" includes misuse resistance which would be violated if the pubkey was not input to the nonce generation function. > Perhaps they even deserve their own BIP? Yes, a standard for nonce exfiltration protection and MuSig would be important for compatibility across wallets. On 2/26/20 4:20 AM, Lloyd Fournier via bitcoin-dev wrote: > Hi Pieter, > > Let me put change (1) into my own words. We are already computing affine > coordinates since we store public keys as the affine x-coordinate. It is > faster to compute is_even(y) than is_quadratic_residue(y) so we get a speed > up here during keypair generation. In the verification algorithm, we do the > following for the public key x_only => affine + negate if not is_even(y) > => jacobian. The minor slowdown in verification comes from the extra > evenness check and possible negation which we didn't have to be done in the > previous version. This seems like a reasonable change if it makes things > easier for existing code bases and infrastructure. > > With change (2), I feel like including this auxiliary random data is > overkill for the spec. For me, the main point of the spec is the > verification algorithm which actually affects consensus. Providing a note > that non-deterministic signatures are preferable in many cases and here's > exactly how you should do that (hash then xor with private key) is > valuable. In the end, people will want several variations of the signing > algorithm anyway (e.g. pass in public key with secret key) so I think > specifying the most minimal way to produce a signature securely is the most > useful thing for this document. > > I feel similarly about hashing the public key to get the nonce. A note in > the alternative signing section that "if you pass the public key into > `sign` along with the secret key then you should do hash(bytes(d) || > bytes(P) || m)" would suffice for me. > > Despite only being included in the alternative signing section, I it would > be nice to have a few of test vectors for these alternative methods anyway. > Perhaps they even deserve their own BIP? > > Cheers, > > LL > > > On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Hello list, >> >> Despite saying earlier that I expected no further semantical changes >> to BIP 340-342, I've just opened >> https://github.com/bitcoin/bips/pull/893 to make a number of small >> changes that I believe are still worth making. >> >> 1. Even public keys >> >> Only one change affects the validation rules: the Y coordinate of >> 32-byte public keys is changed from implicitly square to implicitly >> even. This makes signing slightly faster (in the microsecond range), >> though also verification negligibly slower (in the nanosecond range). >> It also simplifies integration with existing key generation >> infrastructure. For example BIP32 produces public keys with known >> even/oddness, but squaredness would need to be computed separately. >> Similar arguments hold for PSBT and probably many other things. >> >> Note that the Y coordinate of the internal R point in the signature >> remains implicitly square: for R the squaredness gives an actual >> performance gain at validation time, but this is not true for public >> keys. Conversely, for public keys integration with existing >> infrastructure matters, but R points are purely internal. >> >> This affects BIP 340 and 341. >> >> 2. Nonce generation >> >> All other semantical changes are around more secure nonce generation >> in BIP 340, dealing with various failure cases: >> >> * Since the public key signed for is included in the signature >> challenge hash, implementers will likely be eager to use precomputed >> values for these (otherwise an additional EC multiplication is >> necessary at signing time). If that public key data happens to be >> gathered from untrusted sources, it can lead to trivial leakage of the >> private key - something that Greg Maxwell started a discussion about >> on the moderncrypto curves list: >> https://moderncrypto.org/mail-archive/curves/2020/001012.html. We >> believe it should therefore be best practice to include the public key >> also in the nonce generation, which largely mitigates this problem. >> >> * To protect against fault injection attacks it is
Re: [bitcoin-dev] Taproot (and graftroot) complexity (reflowed)
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:
>
>/\
> /\ { 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 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.
>
>
Re: [bitcoin-dev] Safer NOINPUT with output tagging
<--- not replying to list as this is off-topic > Hey Alejandro, thanks for the pointer. Is there a summary of how the opcode you're proposing would look like? Is pairing crypto strictly necessary or would interactive key aggregation schemes like Bellare-Neven work as well? Best, Jonas On 2/9/19 10:01 AM, Alejandro Ranchal Pedrosa via bitcoin-dev wrote: > Hi all, >> >> 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. >> > An eltoo-like protocol that works (without going on-chain) if you can't > predict in advance who will become absent would be a childchain. If the > off-chain protocol can continue updating in the abscence > of other parties, it means that other parties' signatures must not be > required when they are not involved in the off-chain state update. If other > parties' signatures must not be required, there must > be a way of having a common verifiable 'last state' to prevent a party to > simultaneously 'fork' the state with two different parties, and double-spend. > A solution for this is a childchain for Bitcoin. > An example of this is what is known as a 'Broken Factory' attack [1] > (https://bitcoin.stackexchange.com/questions/77434/how-does-channel-factory-act/81005#81005) > >> 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. > > I believe that in many cases other parties won't be able to continue until > the unresponsive parties go back online. That might be true in particular > scenarios, but generally speaking, the party might > have gone unresponsive during a factory-level update (i.e. off-chain closing > and opening of channels), while some parties might have given out their > signature for the update without receiving a fully > signed transaction. In this case they do not even know which channel they > have open (the one of the old state that they have fully signed, or the one > for the new state that they have given out their > signature for). This is known as a 'Stale Factory', and can be exploited by > an adversary in a 'Stale Factory' attack [1]. Even if they knew which state > they are in (i.e. the party went unresponsive > but not during a factory-level update), some of them might have run out of > funds in some of their channels of the factory, and might want to update, > while they will not be willing to wait for a party > to go back online (something for which they also have zero guarantees of). > > An eltoo-like protocol that works (allowing going on-chain) if you can't in > advance who will become absent, then this is precisely why 'Transaction > Fragments' have been suggested. They allow an > eltoo-like protocol even when one cannot predict in advance who will become > absent, or malicious (by publishing invalid states), cause the non-absent > parties can unite their fragments and create a > valid spendable factory-level transaction that effectively kicks out the > malicious parties, while leaving the rest of the factory as it was. To the > best of my understanding, the eltoo original > proposal also allows this though. > > Best, > > Alejandro. > > [1]: Scalable Lightning Factories for Bitcoin, > https://eprint.iacr.org/2018/918.pdf > > > On 08/02/2019 20:01, Jonas Nick via bitcoin-dev 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 & sta
Re: [bitcoin-dev] Safer NOINPUT with output tagging
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) and C. Outputs of the settlement tx Y are > untagged(A) 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 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) ] -> [ >>
Re: [bitcoin-dev] Safer NOINPUT with output tagging
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
Re: [bitcoin-dev] Multi party Schnorr Rust implementation
> For deterministic nonces, you generate r=H(p,m) based on the message > being signed and your private key, so can only start this process when > you start signing, and the sharing rounds mean interactivity. It's not your point but it should be noted that this is not secure unless all other signers give you zero knowledge proof that they've generated their nonce in the same way. Otherwise, if your asked to sign the same message you'll use the same nonce for two different challenges. In your example you'd compute s=r+H(R',P',m)*p and s'=r+H(R'',P',m)*p from which an observer can compute the secret key p. On 11/28/18 10:49 AM, Anthony Towns via bitcoin-dev wrote: > On Tue, Nov 27, 2018 at 10:33:30PM -0800, Devrandom via bitcoin-dev wrote: >> Are there any candidates for non-interactive threshold signatures? >> Interactive >> signatures are not very suitable for air-gapped use cases. > > I think you can work around this to some extent by "batching" signing > requests. > > (Background: > > For interactive multisignatures (threshold or not), the protocol is: > >produce secret nonce r, calculate public nonce R=r*G >everyone shares H(R) >everyone shares R, checks received values match received hashes >everyone calculates s=r+H(R',P',m)*p, shares s > > For deterministic nonces, you generate r=H(p,m) based on the message > being signed and your private key, so can only start this process when > you start signing, and the sharing rounds mean interactivity. > > ) > > But you don't strictly need deterministic nonces, you just have to never > use the same nonce with a different message. If you arrange to do that > by keeping some state instead, you can calculate nonces in advance: > > phase 1: > produce secret nonces r1..r1024, calculate R1..R1024 > share H(R1)..H(R1024) > > phase 2: > store other parties hashes, eg as H1..H1024 > share R1..R1024 > > phase 3: > check received nonces match, ie H(R1)=H1, etc > > phase 4: > request to sign msg m, with nonce n > if nonce n has already been used, abort > mark nonce n as having being used > lookup other signer's nonces n and sum them to get R' > calculate s = rn + H(R',P',m)*p > share s > > That way you could do phases 1-3 once, and then do 1024 signatures during > the month on whatever your current timetable is. > > You could also combine these phases, so when you get a signing request you: > >* receive msg to sign m, n=4; everyone else's R4, H(R5) > >* check H(R4) = previously received "H(R4)" >* calculate R4' by summing up your and everyone's R4s >* bump state to n=5 >* do the signature... > >* send sig=(s,R4), R5, H(R6) > > which would let you have an untrusted app that does the coordination and > shares the nonces and nonce-hashes, and getting all the needed air-gapped > communication in a single round. (This is effectively doing phase 3 and > 4 for the current signature, phase 2 for the next signature, and phase > 1 for the signature after that all in one round of communication) > > That seems almost as good as true non-interactivity to me, if your signing > hardware is capable of securely storing (and updating) a few kB of state > (which is probably not quite as easy as it sounds). > > Cheers, > aj > > ___ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP sighash_noinput
Oh, I missed that that's still the case with NOINPUT - thanks for pointing it
out. In that case there's no reason to sign the other inputs' sequence and
that's even better because the current NOINPUT proposal already enables
taprootifiability of eltoo unilateral closings.
On 9/26/18 7:45 PM, Johnson Lau wrote:
> In BIP143, the nSequence of the same input is always signed, with any
> hashtype. Why do you need to sign the sequence of other inputs?
>
>> On 26 Sep 2018, at 5:36 PM, Jonas Nick via bitcoin-dev
>> wrote:
>>
>>> At the risk of bikeshedding, shouldn't NOINPUT also zero out the
>>> hashSequence so that its behaviour is consistent with ANYONECANPAY?
>>
>> There is a good reason for not doing that. If NOINPUT would sign the
>> hashSequence then it would be possible to get rid of OP_CSV in eltoo update
>> scripts. As a result update scripts could be taprootified because the more
>> common branch (settlement) would be just a 2-of-2 multisig. Applying taproot
>> would then make unilateral settlement look like a single pubkey spend and
>> avoid
>> having to reveal the unexecuted (update) branch.
>>
>> Eltoo update transaction outputs consist of two branches, update and
>> settlement, where the update branch can be spend by a more recent update
>> transaction if an obsolete update transaction ends up spending the funding
>> output. The settlement branch is a 2-of-2 multisig with a relative timelock
>> using OP_CSV. Removing OP_CSV is possible because both parties signature is
>> required to spend the update transaction. They will only sign if the input
>> has
>> the right sequence numbers which is sufficient to enforce the timeout
>> (BIP68) -
>> assuming they are covered by the signature.
>>
>> There's a catch: hashSequence includes the sequence numbers of all
>> transaction
>> inputs. That's not a problem for eltoo because settlement transactions only
>> have one input. The update mechanism with update transactions relies on being
>> able to bump the fee by unilaterally adding inputs and and change outputs to
>> the transaction. That's also not a problem because update spends do not use
>> relative timelocks and they are signed with SINGLE. So whenever NOINPUT is
>> combined SINGLE the hashSequence should be zeroed. This is in fact what a
>> minimal change to the current NOINPUT implementation would naturally do (see
>> below). However, that's error-prone when using NOINPUT in other contexts so
>> in
>> general it would be better if NOINPUT would only sign the sequence number of
>> the corresponding input.
>>
>> Another downside of this approach is that you can never rebind to an output
>> with an OP_CSV that requires a larger sequence number, unless you also sign
>> with SIGHASH_SINGLE. It's difficult to imagine application where this would
>> be
>> an issue.
>>
>> This is the modification to the NOINPUT implementation
>> (https://github.com/cdecker/bitcoin/commits/noinput) which makes eltoo
>> unilateral closes taprootifiable:
>> +++ b/src/script/interpreter.cpp
>> @@ -1223,7 +1223,7 @@ uint256 SignatureHash(const CScript& scriptCode, const
>> CTransaction& txTo, unsig
>> hashPrevouts = cacheready ? cache->hashPrevouts :
>> GetPrevoutHash(txTo);
>> }
>>
>> -if (!(nHashType & SIGHASH_ANYONECANPAY) && (nHashType & 0x1f) !=
>> SIGHASH_SINGLE && (nHashType & 0x1f) != SIGHASH_NONE && !noinput) {
>> +if (!(nHashType & SIGHASH_ANYONECANPAY) && (nHashType & 0x1f) !=
>> SIGHASH_SINGLE && (nHashType & 0x1f) != SIGHASH_NONE) {
>> hashSequence = cacheready ? cache->hashSequence :
>> GetSequenceHash(txTo);
>> }
>>
>> On 5/1/18 4:58 PM, Russell O'Connor via bitcoin-dev wrote:
>>> At the risk of bikeshedding, shouldn't NOINPUT also zero out the
>>> hashSequence so that its behaviour is consistent with ANYONECANPAY?
>>>
>>
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP sighash_noinput
> At the risk of bikeshedding, shouldn't NOINPUT also zero out the
> hashSequence so that its behaviour is consistent with ANYONECANPAY?
There is a good reason for not doing that. If NOINPUT would sign the
hashSequence then it would be possible to get rid of OP_CSV in eltoo update
scripts. As a result update scripts could be taprootified because the more
common branch (settlement) would be just a 2-of-2 multisig. Applying taproot
would then make unilateral settlement look like a single pubkey spend and avoid
having to reveal the unexecuted (update) branch.
Eltoo update transaction outputs consist of two branches, update and
settlement, where the update branch can be spend by a more recent update
transaction if an obsolete update transaction ends up spending the funding
output. The settlement branch is a 2-of-2 multisig with a relative timelock
using OP_CSV. Removing OP_CSV is possible because both parties signature is
required to spend the update transaction. They will only sign if the input has
the right sequence numbers which is sufficient to enforce the timeout (BIP68) -
assuming they are covered by the signature.
There's a catch: hashSequence includes the sequence numbers of all transaction
inputs. That's not a problem for eltoo because settlement transactions only
have one input. The update mechanism with update transactions relies on being
able to bump the fee by unilaterally adding inputs and and change outputs to
the transaction. That's also not a problem because update spends do not use
relative timelocks and they are signed with SINGLE. So whenever NOINPUT is
combined SINGLE the hashSequence should be zeroed. This is in fact what a
minimal change to the current NOINPUT implementation would naturally do (see
below). However, that's error-prone when using NOINPUT in other contexts so in
general it would be better if NOINPUT would only sign the sequence number of
the corresponding input.
Another downside of this approach is that you can never rebind to an output
with an OP_CSV that requires a larger sequence number, unless you also sign
with SIGHASH_SINGLE. It's difficult to imagine application where this would be
an issue.
This is the modification to the NOINPUT implementation
(https://github.com/cdecker/bitcoin/commits/noinput) which makes eltoo
unilateral closes taprootifiable:
+++ b/src/script/interpreter.cpp
@@ -1223,7 +1223,7 @@ uint256 SignatureHash(const CScript& scriptCode, const
CTransaction& txTo, unsig
hashPrevouts = cacheready ? cache->hashPrevouts :
GetPrevoutHash(txTo);
}
-if (!(nHashType & SIGHASH_ANYONECANPAY) && (nHashType & 0x1f) !=
SIGHASH_SINGLE && (nHashType & 0x1f) != SIGHASH_NONE && !noinput) {
+if (!(nHashType & SIGHASH_ANYONECANPAY) && (nHashType & 0x1f) !=
SIGHASH_SINGLE && (nHashType & 0x1f) != SIGHASH_NONE) {
hashSequence = cacheready ? cache->hashSequence :
GetSequenceHash(txTo);
}
On 5/1/18 4:58 PM, Russell O'Connor via bitcoin-dev wrote:
> At the risk of bikeshedding, shouldn't NOINPUT also zero out the
> hashSequence so that its behaviour is consistent with ANYONECANPAY?
>
> On Mon, Apr 30, 2018 at 12:29 PM, Christian Decker via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hi all,
>>
>> I'd like to pick up the discussion from a few months ago, and propose a new
>> sighash flag, `SIGHASH_NOINPUT`, that removes the commitment to the
>> previous
>> output. This was previously mentioned on the list by Joseph Poon [1], but
>> was
>> never formally proposed, so I wrote a proposal [2].
>>
>> We have long known that `SIGHASH_NOINPUT` would be a great fit for
>> Lightning.
>> They enable simple watch-towers, i.e., outsource the need to watch the
>> blockchain for channel closures, and react appropriately if our
>> counterparty
>> misbehaves. In addition to this we just released the eltoo [3,4] paper
>> which
>> describes a simplified update mechanism that can be used in Lightning, and
>> other
>> off-chain contracts, with any number of participants.
>>
>> By not committing to the previous output being spent by the transaction,
>> we can
>> rebind an input to point to any outpoint with a matching output script and
>> value. The binding therefore is no longer explicit through a reference, but
>> through script compatibility, and the transaction ID reference in the
>> input is a
>> hint to validators. The sighash flag is meant to enable some off-chain
>> use-cases
>> and should not be used unless the tradeoffs are well-known. In particular
>> we
>> suggest using contract specific key-pairs, in order to avoid having any
>> unwanted
>> rebinding opportunities.
>>
>> The proposal is very minimalistic, and simple. However, there are a few
>> things
>> where we'd like to hear the input of the wider community with regards to
>> the
>> implementation details though. We had some discussions internally on
>> whether to
>> use a separate opcode or a sighash flag, some feeling that the sighash
Re: [bitcoin-dev] Multisignature for bip-schnorr
Your multisignature writeup appears to be vulnerable to key cancellation attacks because the aggregated public key is just the sum of public keys (and there is no proof of knowledge of the individual secret keys). Therefore, in a multisignature between Alice and an attacker, the attacker can choose their key to be -alice_key+attacker_key resulting in an aggregated key for which the attacker can sign alone (without requiring Alice's partial signature). The Schnorr BIP links to the MuSig paper which describes a secure key aggregation scheme. See https://eprint.iacr.org/2018/068 On 8/7/18 6:35 AM, nakagat via bitcoin-dev wrote: > Hi all, > > I wrote a multisignature procedure using bip-schnorr. > > If you have time to review and give feedback, I’d really appreciate it. > Thanks in advance! > > Multisignature > https://gist.github.com/tnakagawa/0c3bc74a9a44bd26af9b9248dfbe598b > > Original > https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#Multisignatures_and_Threshold_Signatures > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
