[bitcoin-dev] Signet: static genesis block, and dynamic message start
Hello, I am proposing a modification to BIP-325 to make the genesis block static and to rely on the message start to avoid collision between signets when multiple nets exist simultaneously: https://github.com/bitcoin/bips/pull/900 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Hash function requirements for Taproot
Good morning LL, Thank you very much for this work, it seems quite interesting. > 5. You can completely circumvent this result by using coin-tossing rather > than MuSig for the key generation protocol. In most cases this doesn't even > add any extra rounds of communication since you are doing 3-round coin > tossing to choose the R values for the signatures that spend from the joint > output anyway. You can just toss your public keys in parallel. I am uncertain what you mean here by "coin-tossing". >From the comparison to MuSig, I imagine it is an interactive key generation >protocol like this: * Everybody generates fresh keypairs. * Everybody sends the hash of their pubkey to everyone else. * After receiving a hash of pubkey from everyone else, everybody sends their pubkey to everyone else. * They add all their pubkeys to generate the aggregate key (and if using Taproot, use it as the internal key). Is that correct? In any case, the comparison to MuSig signing appears to imply interactive key generation. The advantage of MuSig is that it requires no interactivity for key generation of n-of-n (I am told it requires interactivity to generate k-of-n). However, it can generally be pointed out that, before you put anything into an n-of-n, you would damn well sure want to have *some* assurance that you can get it out later. So in general you would need coordination and interaction anyway to arrange getting into an n-of-n in the first place. On the other hand, it would be best to have at least some minimum of privacy by always interacting over Tor and having a Tor .onion address, which has absolutely horrid latency because human beings cry when peeling onions. So in general reducing the latency by reducing communication rounds is better in general. Counter to this, assuming you use an n-of-n in an offchain protocol of some sort, the number of communication rounds to generate the aggregate key may be dwarfed by the total number of communication rounds to create signatures to update the offchain protocol. Counter counter to this is that one plan for reducing communications rounds for creating signatures during offchain operation is to (haha) use a Taproot with an n-of-n internal key and a tapscript that has n `OP_CHECKSIG` operations, so that for normal operation you just toss individual signatures at each other but at termination of the offchain protocol you can do the heavy MuSig-style signing with the n-of-n aggregate key. Regards, ZmnSCPxj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] RFC: Kicking BIP-322 (message signing) into motion
OP_MESSAGEONLY would make "dumb" signers like HWW more difficult to support. They'd have to do script interpretation to make sure they're not signing something real with funds. Just FYI. On Wed, Mar 4, 2020 at 9:35 AM Luke Dashjr via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > In addition to starting with proof-of-funds instead of proof-of-receiver, > it > would be nice to integrate with Taproot somehow or another. Perhaps > OP_MESSAGEONLY is the most straightforward way to do this? It might be a > good > idea to have a message type after the opcode too. > > On Wednesday 04 March 2020 06:23:53 Karl-Johan Alm via bitcoin-dev wrote: > > Hello, > > > > I noticed recently that a PR to Bitcoin Core that pretty much touched > > everything my BIP-322 pull request touches (around the same > > complexity) was merged without a thought given to BIP-322 > > compatibility, despite the BIP-322 PR being open for 2x the time. I > > can only conclude from this that people dislike BIP-322 in its current > > form, which the 9 month old pull request stagnating can probably > > attest to. > > > > There are several things that I can do to make this a bit more > > appealing to people, which would hopefully kick the progress on this > > forward. I have already put in a non-trivial amount of energy and > > effort into maintaining the pull request as is, so I'd prefer if > > people were harsh and unfiltered in their criticism rather than polite > > and buffered, so I can beat this thing into shape (or abandon it, in > > the worst case). > > > > = > > 1. People use signmessage as a way to prove funds. This is misleading > > and should be discouraged; throw the sign message stuff out and > > replace it entirely with a prove funds system. > > > > I know in particular luke-jr is of this opinion, and Greg Maxwell in > > https://github.com/bitcoin/bitcoin/pull/16440#issuecomment-568194168 > > leans towards this opinion as well, it seems. > > > > = > > 2. Use a transaction rather than a new format; make the first input's > > txid the message hash to ensure the tx cannot be broadcasted. This has > > the benefit of being able to provide to an existing hardware wallet > > without making any modifications to its firmware. > > > > I think Mark Friedenbach and Johnson Lau are of this opinion, except > > Johnson Lau also suggests that the signature hash is modified, see > > https://github.com/bitcoin/bips/pull/725#issuecomment-420040430 -- > > which defeats the benefit above since now hw wallets can no longer > > sign. > > > > Prusnak (I think he works at Trezor; apologies if I am mistaken) is > > against this idea, and proposes (3) below: > > https://github.com/bitcoin/bips/pull/725#issuecomment-420210488 > > > > = > > 3. Use Trezor style > > > > See https://github.com/trezor/trezor-mcu/issues/169 > > > > This has the benefit of already being adopted (which clearly BIP-322 > > is failing hard at right now), but has the drawback that we can no > > longer do *generic* signing; we are stuck with the exact same > > limitations as in the legacy system, which we kinda wanted to fix in > > the updated version. > > > > = > > 4. Introduce OP_MESSAGEONLY > > > > Quoting Johnson Lau at > > https://github.com/bitcoin/bips/pull/725#issuecomment-420421058 : > > """ > > OP_MESSAGEONLY means the script following the code would never be > > valid. For example, a scriptPubKey: > > > > OP_IF OP_MESSAGEONLY OP_ELSE OP_ENDIF OP_CHECKSIG > > > > For messaging purpose, OP_MESSAGEONLY is considered as OP_NOP and is > > ignored. A message could be signed with either key_m or key_s. > > > > For spending, only key_s is valid. > > > > I don't think it is a big problem to consume a op_code. If this is a > > real concern, I could modify it as follow: in message system, > > OP_RETURN will pop the top stack. If top stack is msg in hex, it is > > ignored. Otherwise, the script fails. > > """ > > > > = > > 5. Some other solution > > ___ > > 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 > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] RFC: Kicking BIP-322 (message signing) into motion
In addition to starting with proof-of-funds instead of proof-of-receiver, it would be nice to integrate with Taproot somehow or another. Perhaps OP_MESSAGEONLY is the most straightforward way to do this? It might be a good idea to have a message type after the opcode too. On Wednesday 04 March 2020 06:23:53 Karl-Johan Alm via bitcoin-dev wrote: > Hello, > > I noticed recently that a PR to Bitcoin Core that pretty much touched > everything my BIP-322 pull request touches (around the same > complexity) was merged without a thought given to BIP-322 > compatibility, despite the BIP-322 PR being open for 2x the time. I > can only conclude from this that people dislike BIP-322 in its current > form, which the 9 month old pull request stagnating can probably > attest to. > > There are several things that I can do to make this a bit more > appealing to people, which would hopefully kick the progress on this > forward. I have already put in a non-trivial amount of energy and > effort into maintaining the pull request as is, so I'd prefer if > people were harsh and unfiltered in their criticism rather than polite > and buffered, so I can beat this thing into shape (or abandon it, in > the worst case). > > = > 1. People use signmessage as a way to prove funds. This is misleading > and should be discouraged; throw the sign message stuff out and > replace it entirely with a prove funds system. > > I know in particular luke-jr is of this opinion, and Greg Maxwell in > https://github.com/bitcoin/bitcoin/pull/16440#issuecomment-568194168 > leans towards this opinion as well, it seems. > > = > 2. Use a transaction rather than a new format; make the first input's > txid the message hash to ensure the tx cannot be broadcasted. This has > the benefit of being able to provide to an existing hardware wallet > without making any modifications to its firmware. > > I think Mark Friedenbach and Johnson Lau are of this opinion, except > Johnson Lau also suggests that the signature hash is modified, see > https://github.com/bitcoin/bips/pull/725#issuecomment-420040430 -- > which defeats the benefit above since now hw wallets can no longer > sign. > > Prusnak (I think he works at Trezor; apologies if I am mistaken) is > against this idea, and proposes (3) below: > https://github.com/bitcoin/bips/pull/725#issuecomment-420210488 > > = > 3. Use Trezor style > > See https://github.com/trezor/trezor-mcu/issues/169 > > This has the benefit of already being adopted (which clearly BIP-322 > is failing hard at right now), but has the drawback that we can no > longer do *generic* signing; we are stuck with the exact same > limitations as in the legacy system, which we kinda wanted to fix in > the updated version. > > = > 4. Introduce OP_MESSAGEONLY > > Quoting Johnson Lau at > https://github.com/bitcoin/bips/pull/725#issuecomment-420421058 : > """ > OP_MESSAGEONLY means the script following the code would never be > valid. For example, a scriptPubKey: > > OP_IF OP_MESSAGEONLY OP_ELSE OP_ENDIF OP_CHECKSIG > > For messaging purpose, OP_MESSAGEONLY is considered as OP_NOP and is > ignored. A message could be signed with either key_m or key_s. > > For spending, only key_s is valid. > > I don't think it is a big problem to consume a op_code. If this is a > real concern, I could modify it as follow: in message system, > OP_RETURN will pop the top stack. If top stack is msg in hex, it is > ignored. Otherwise, the script fails. > """ > > = > 5. Some other solution > ___ > 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
[bitcoin-dev] Hash function requirements for Taproot
Hi List, I recently presented a poster at the Financial Cryptography conference '2020 which you can find here: https://github.com/LLFourn/taproot-ggm/blob/master/main.pdf. It attempts to show the security requirements for the tweak hash function in Taproot. In this post I'll give a long description of it but first let me tl;dr: Taproot requires no new assumptions of SHA256 over what are already made by Schnorr signatures themselves with one exception: when using a non-interactive key generation protocol to produce a Taproot internal key (e.g MuSig). To prove security in this scenario we need a make an additional assumption about SHA256: as well as being collision resistant (i.e. find two hashes h_1 - h_2 = 0), it must satisfy a more general kind of collision resistance where it is hard to find h_1 - h_2 = d for *any d* when the adversary is challenged to find h_1 and h_2 with random prefixes. This is obviously a plausible assumption. Put informally, it says that zero is not a special case where finding collisions is difficult but rather solving the 2-sum problem is hard for all values of d (when challenged with random prefixes). Now the long version. My motivation for creating this poster came from questions I had after discussions in Taproot Study Group #18 (this study group initiative was a great idea btw). The main question I had was "Why is Taproot binding?" i.e. why is it true that I can only commit to one Merkle root. Isn't it possible that a malicious party could produce a second covert Taproot spend that none of the other parties to the output agreed to? I submitted a poster proposal to FC to force myself to get to the bottom of it. The premise of the poster is to use the Generic Group Model to try and figure out how the hash function would have to fail for Taproot to be insecure. Most of the poster is taken up cartoon reductions I made to remind myself as to why what I was saying might be true. They are incomplete and difficult to parse on their own so hopefully this post is a useful companion to them. === The Security of Taproot === There are three scenarios/games we must consider when asking whether Taproot is secure in the context of Bitcoin: 1. Taproot Forge: Forging taproot spends must be hard. The adversary must not be able to take a public key off the blockchain and produce a forged Taproot spend from it. 2. Covert Taproot: When an adversary is executing a multi-party key generation protocol (e.g. MuSig) it should be hard for them to produce a covert malicious Taproot spend from the joint key i.e. when honest parties think there is no Taproot on a key there shouldn't be any Taproot on the key. Note this is not guaranteed to be hard by 1 being hard. 3. Second Covert Taproot: Like 2, except that if honest parties agree to a Taproot spend then the adversary shouldn't be able to generate a second Taproot spend they are unaware of. Properties (1) and (2) can be argued succinctly if we just prove that Taproot is a secure commitment scheme. It should be clear that if a Taproot external key T = X + H(X||m)*G is a secure commitment scheme (Hiding and Binding) to any arbitrary message m, then it is a secure commitment scheme to a Merkle root. If so, then properties (1) and (3) hold. (1) holds because if you can create an opening to a commitment not generated by you, you either broke hiding (if your opening is the same as the honest one) or broke binding (if it's different). (3) holds because you must have broken binding as there are now two openings to the same commitment. Property (2) is more difficult to argue as it depends on the multi-party key generation protocol. Case in point: Taproot is completely broken when combined with a proof of knowledge key generation protocol where along with their public keys each party provides a proof of knowledge of the secret key. Where X_1 is the key of the honest party, the malicious party can choose their key X_2 to be G*H(X_1 || m) where m is a malicious Merkle root. Clearly the malicious party has a covert Taproot for X = X_1 + X_2 and can produce a proof of knowledge for X_2. Given this definition of security, we now move onto how we should model the problem to prove they hold. === Generic Group Model vs Random Oracle Model === For practical cryptographic schemes you often have to idealise one of its components to prove it secure. The most popular candidate for idealisation is the hash function in the Random Oracle Model (ROM), which idealises a hash function as a "random oracle", a black box which spits out random values for each input. For example, the original "forking lemma" proof by Pointcheval and Stern [1] shows the Schnorr signature scheme is unforgeable in this model if the discrete logarithm problem is hard. In other words, idealising the hash function allows us to isolate what security assumptions we are making about the group (e.g. the discrete logarithm problem being hard in it). But what if we want to know what assumptions we a