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] Multi party Schnorr Rust implementation
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
Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT
We are also prototyping the OP_CHECKSIGFROMSTACK mechanism using Liquid/Elements. Given uncertainty about which features will actually be deployed on mainnet, we're exploring all possibilities so as to provide feedback about the "best" way to implement a covenant/vault, also including the OP_CHECKOUTPUTVERIFY originally proposed by Eyal et al. That's 3 ways to implement a covenant/vault, if there's others I'd be happy to hear about it. ;-) Thanks for the OP_PUSHTXDATA ref, I'm reading now... Personally I think the OP_CHECKSIGFROMSTACK is probably the most elegant mechanism. Thanks for the feedback! Johnson Lau [jl2...@xbt.hk] wrote: > This is incompatible with bip-schnorr, which intentionally disallow such use > by always committing to the public key: > https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > > With the recent fake Satoshi signature drama, and other potential ways to > misuse and abuse, I think this is a better way to go, which unfortunately > might disallow some legitimate applications. > > Covenants could be made using OP_CHECKSIGFROMSTACK > (https://fc17.ifca.ai/bitcoin/papers/bitcoin17-final28.pdf) or OP_PUSHTXDATA > (https://github.com/jl2012/bips/blob/vault/bip-0ZZZ.mediawiki). I think this > is the next step following the taproot soft fork > > > On 28 Nov 2018, at 8:54 AM, Bob McElrath via bitcoin-dev > > wrote: > > > > I have been working on an experimental wallet that implements Bitcoin > > Covenants/Vaults following a blog post I wrote about 2 years ago, using > > "Pay-to-Timelock Signed Transaction" (P2TST). (Also mentioned recently by > > kanzure in a talk somewheres...) The idea is that you deposit to an > > address for > > which you don't know the private key. Instead you construct a second > > transaction sending that to a timelocked staging address for which you DO > > have > > the privkey (it also has an IF/ELSE condition with a second spending > > condition > > for use in case of theft attempt). In order to do this you either have to > > delete the privkey of the deposit address (a difficult proposition to know > > it's > > actually been deleted), but instead one can construct a signature directly > > using > > a RNG, and use the SIGHASH to compute the corresponding pubkey via ECDSA > > recover, from which you compute the corresponding address. In this way your > > wallet is a set of P2TST transactions and a corresponding privkey, with a > > (set > > of) emergency keys. > > > > This interacts with NOINPUT in the following way: if the input to the > > transaction commits to the pubkey in any way, you have a circular > > dependency on > > the pubkey that could only be satisfied by breaking a hash function. This > > occurs with standard sighash's which commit to the txid, which in turn > > commit to > > the address, which commits to the pubkey, so this construction of > > covenants/vaults requires NOINPUT. > > > > AFAICT sipa's proposal is compatible with the above vaulted construction by > > using SIGHASH_NOINPUT | SIGHASH_SCRIPTMASK to remove the > > scriptPubKey/redeemScript from the sighash. Putting the > > scriptPubKey/redeemScript in the sighash introduces the same circular > > dependency, but SIGHASH_SCRIPTMASK removes it. > > > > One would probably want to provide the fee from a separate wallet so as to > > be > > able to account for fluctuating fee pressures when the unvaulting occurs a > > long > > time after vaulting. Thus you'd want to use SIGHASH_SINGLE so that a > > fee-wallet > > can add fees (or for composability of P2TSTs), and SIGHASH_NOFEE as well. > > > > P.S. Also very excited to combine the above idea with > > Taproot/Graftroot/g'Root. > > > > -- > > Cheers, Bob McElrath > > > > "For every complex problem, there is a solution that is simple, neat, and > > wrong." > >-- H. L. Mencken > > > > ___ > > bitcoin-dev mailing list > > bitcoin-dev@lists.linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > > > !DSPAM:5bfe5494217527839717631! -- Cheers, Bob McElrath "For every complex problem, there is a solution that is simple, neat, and wrong." -- H. L. Mencken ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT
This is incompatible with bip-schnorr, which intentionally disallow such use by always committing to the public key: https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki With the recent fake Satoshi signature drama, and other potential ways to misuse and abuse, I think this is a better way to go, which unfortunately might disallow some legitimate applications. Covenants could be made using OP_CHECKSIGFROMSTACK (https://fc17.ifca.ai/bitcoin/papers/bitcoin17-final28.pdf) or OP_PUSHTXDATA (https://github.com/jl2012/bips/blob/vault/bip-0ZZZ.mediawiki). I think this is the next step following the taproot soft fork > On 28 Nov 2018, at 8:54 AM, Bob McElrath via bitcoin-dev > wrote: > > I have been working on an experimental wallet that implements Bitcoin > Covenants/Vaults following a blog post I wrote about 2 years ago, using > "Pay-to-Timelock Signed Transaction" (P2TST). (Also mentioned recently by > kanzure in a talk somewheres...) The idea is that you deposit to an address > for > which you don't know the private key. Instead you construct a second > transaction sending that to a timelocked staging address for which you DO have > the privkey (it also has an IF/ELSE condition with a second spending condition > for use in case of theft attempt). In order to do this you either have to > delete the privkey of the deposit address (a difficult proposition to know > it's > actually been deleted), but instead one can construct a signature directly > using > a RNG, and use the SIGHASH to compute the corresponding pubkey via ECDSA > recover, from which you compute the corresponding address. In this way your > wallet is a set of P2TST transactions and a corresponding privkey, with a (set > of) emergency keys. > > This interacts with NOINPUT in the following way: if the input to the > transaction commits to the pubkey in any way, you have a circular dependency > on > the pubkey that could only be satisfied by breaking a hash function. This > occurs with standard sighash's which commit to the txid, which in turn commit > to > the address, which commits to the pubkey, so this construction of > covenants/vaults requires NOINPUT. > > AFAICT sipa's proposal is compatible with the above vaulted construction by > using SIGHASH_NOINPUT | SIGHASH_SCRIPTMASK to remove the > scriptPubKey/redeemScript from the sighash. Putting the > scriptPubKey/redeemScript in the sighash introduces the same circular > dependency, but SIGHASH_SCRIPTMASK removes it. > > One would probably want to provide the fee from a separate wallet so as to be > able to account for fluctuating fee pressures when the unvaulting occurs a > long > time after vaulting. Thus you'd want to use SIGHASH_SINGLE so that a > fee-wallet > can add fees (or for composability of P2TSTs), and SIGHASH_NOFEE as well. > > P.S. Also very excited to combine the above idea with > Taproot/Graftroot/g'Root. > > -- > Cheers, Bob McElrath > > "For every complex problem, there is a solution that is simple, neat, and > wrong." >-- H. L. Mencken > > ___ > 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] Safer sighashes and more granular SIGHASH_NOINPUT
> On 28 Nov 2018, at 11:41 AM, Pieter Wuille via bitcoin-dev > wrote: > > So a combined proposal: > * All existing sighash flags, plus NOINPUT and MASK > (ANYONECANPAY/NOINPUT/MASK are encoded in 2 bits). > * A new opcode called OP_MASKEDPUSH, whose only runtime behaviour is > failing if not immediately followed by a push, or when appearing as > last opcode in the script. I suggest to use the place of OP_RESERVED (0x50) as OP_MASKEDPUSH. The reason is 0x50 is not counted towards the 201 opcode limit, so people could mask as many pushes as needed. In a new script version, of course, we could make any opcode not being counted. But that would just create another special case in the EvalScript() code. (Or, maybe we should limit the use of OP_MASKEDPUSH? I think this is open for discussion.) > * Signatures are 64 plus an optional sighash byte. A missing sighash > byte implies ALL, and ALL cannot be specified explicitly. > * The sighash is computed from the following: > * A 64-byte constant tag > * Data about the spending transaction: >* The transaction version number >* The hash of txins' prevouts+amounts+sequences (or nothing if > ANYONECANPAY) Do you want to make it 1 hash or 3 hashes? With 3 hashes, it could share hashPrevouts and hashSequence with BIP143. Making everything 1 hash will only result in redundent hashing for each input >* The hash of all txouts (or just the corresponding txout if > SINGLE; nothing if NONE) Starting from this sighash version, I think we should forbid the use of SINGLE without a matching output. Also, the undefined output type should also be invalid. >* The transaction locktime > * Data about the output being spent: >* The prevout (or nothing if NOINPUT) >* The amount >* The sequence number >* The hash of the scriptPubKey (or nothing if MASK) I think we should just use the scriptPubKey, since sPK is fixed size (23-byte for p2sh and 35-byte for native segwit). In order to distinguish p2sh and native segwit for MASKED NOINPUT, you also need to commit to an additional 1-bit value > * Data about the script being executed: >* The hash of the scriptCode (after masking out, if MASK is set) For direct key-spending (i.e. not taprooted script), I suggest to set the H(scriptCode) to zero, for the following reasons: 1) Since we have already committed to sPK, which is already a *direct* hash of scriptCode, it is redundant to do it again. 2) This could save one SHA256 compression for direct key-spending, which is probably 90% of all cases 3) This allows hardware wallet to tell whether they are using direct-spending path or taproot script path Since we may want 3) anyway, we don’t need to commit to another 1-bit value if we simply set H(scriptCode) to zero We should also ban MASKED NOINPUT for direct-spending, which doesn’t make sense. And it is not safe since both H(scriptCode) and sPK are empty. >* The opcode number of the last executed OP_CODESEPARATOR (or > 0x if none) > * The sighash mode This proposal will only use 4 out of the 8 sighash bits. Do we want to make those 4 unused bits invalid, or ignored? Leaving at least 1 bit valid but ignored (“bit-x"), and 1 bit invalid (“bit-y”), will allow opt-in/out hardfork replay-protection, for example: * default signatures are those with both bit-x and bit-y unset. * If we want to make default signatures replayable across chains, the new fork should reject signatures with bit-x, and accept sigs with or without bit-y. In this case, defaults sigs are valid for both chains. Sigs with bit-x is valid only for original chain, and sigs with bit-y is valid only for new chain. * If we want to make default signatures non-replayabble, the new fork should reject all default sigs, but accept sigs with either bit-x or bit-y set. In this case, default sig is valid only for original chain. Sigs with bit-x is valid for both chains, and sigs with bit-y is valid only for new chain. Replayability is sometimes desirable, for example, an LN opened before a fork should be able to be settled on both chains ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Multi party Schnorr Rust implementation
Hi, AFAIK, There is no way to do threshold signatures non-interactively for the general case of t out of n. Even if you are willing to maintain additional data structure on top of the standard and change verification algorithm (see for example appendix B in [1] where they use bitmaps). The best way that I came up with so far (which I plan to implement in the library) is to take SS01 paper [2], this also the paper cited in bip-schnorr [3], and to replace Pedersen VSS with Feldman VSS (Feldman VSS implementation can be found in [4] ). Basically taking the DKG from GG18 without paillier and the dlog pok (threshold ecdsa paper [5]) and use it for the threshold schnorr DKG and for the ephemeral key distributed generation. This will cause the lost of Robustness but will be more efficient. Generally speaking - the purpose of using threshold security is to replace hw security. The assumption is that you would rather trust that no more than t out of n different machines will get corrupted at same time than to trust one secure hardware. Maybe that relax a bit the demand for using air gapped devices? [1] https://docs.zilliqa.com/whitepaper.pdf [2] https://github.com/KZen-networks/multi-party-schnorr/blob/master/papers/provably_secure_distributed_schnorr_signatures_and_a_threshold_scheme.pdf [3] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#multisignatures-and-threshold-signatures [4] https://github.com/KZen-networks/curv/tree/master/src/cryptographic_primitives/secret_sharing [5] http://stevengoldfeder.com/papers/GG18.pdf On Wed, Nov 28, 2018 at 8:33 AM Devrandom wrote: > Hi Omer, > > Are there any candidates for non-interactive threshold signatures? > Interactive signatures are not very suitable for air-gapped use cases. > > On Tue, Nov 27, 2018 at 11:18 AM Omer Shlomovits via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Hello all, >> >> I am working for the past few months with collaborators (in cc) on >> providing Rust reference implementations to existing multi party schemes >> for Schnorr signatures [1]. This includes aggregated signatures, >> accountable signatures (which for n out of n are multi-signatures) and >> threshold signatures (wip). >> The project can be found here: >> https://github.com/KZen-networks/multi-party-schnorr . >> We aim that if the protocol is run in a configuration of a single party >> it will be bip-schnorr [2] compliant. >> >> Hope you'll find it useful :) >> Questions, suggestions and pull requests are welcome! >> >> >> [1] >> https://github.com/KZen-networks/multi-party-schnorr/tree/master/papers >> [2] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki >> ___ >> 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
