* [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
@ 2021-02-05 17:51 Dr Maxim Orlovsky
2021-02-05 22:00 ` Dmitry Petukhov
` (2 more replies)
0 siblings, 3 replies; 10+ messages in thread
From: Dr Maxim Orlovsky @ 2021-02-05 17:51 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
Hi,
Background
==========
Had a discussion last night in Bitcoin Core IRC with Peter Wuille on different topics regarding key derivations, security, key tweaks in context of Schnorr signatures & Taproot. Would like to share some action points and plans that emerged from there:
1. There is a real need for BIP-43 based new BIP with a new purpose field for keys used in Schnorr signatures. Peter will not do it (he is not very much interested in spending his time on wallet-level stuff), so someone else should.
2. Keys used in Schnorr signatures MUST NEVER BE used in ECDSA signatures, otherwise there is a risk of private key leak via correlation attack. This is rationale behind N1.
3. The other need (not discussed with Peter) is to change the general structure of derivation path used before with BIP-44, 45, 84. This change is required to enable the use of all modern wallet use cases under a single standard: single-sigs & multi-sigs, ECDSA & BIP340 signatures.
4. Embedding multisig support in a hierarchical format requires introduction of a “signer id” concept as a part of the derivation path. I found a way how this can be done seamlessly, leading to emergence of decentralized identity as a side effect.
Proposal
========
Derivation path structure & purpose values
------------------------------------------
The new format for the hierarchical derivation BIP32 path is the following:
m/purpose’/blockchain’/identity’/scope'/case/index
**Purpose:**
BIP-43 purpose values under the proposal:
- 340’ for BIP340 signatures
- ???’ for old-style ECDSA signatures (??? will be set to the BIP number of this standard once it gets assigned)
Thus, purpose will be used to signify the type of the signature.
NB: purpose MUST be hardened since otherwise a key leak may occur.
**Blockchain:**
was not there before, but now we should have it:
- to prevent key reuse across blockchains & combined inter-chain analysis
- to get rid of using custom xpub prefixes (like SLIP-132) which are very unwelcomed by the community and are unnecessary since we have descriptors.
Testnet path `1` covers all testnets (no problem with key re-use for valueless testnet or inter-testnet chainanalysis) - this follows the logic of recent changes in other standards related to testnet (use the same Bech32 prefixes for all testnets).
Testnet path is unhardened from this point & till the end of the derivation path: no need to prevent private key leak there, simplifies test software (hardened paths require private key access for derivation).
Devs are free to choose other unhardened number if they need, without changing the standard - unhardened numbers will never be used for chains with real value.
**Identity and scope**
Hardened components signify the main identity (decentralized id) and the scope under that id used in context of specific multisig wallet or other identity case. Scope is required to use the same id with different peers without exposing the main identity xpub (and, thus, the scope must be hardened as well).
**Case**
This is the same as a “change” field before (under BIP44 etc), however it is proposed to change the name to denote that the field may have other values and is used for signalling support for some custom features (for instance, pay-to-contract or sign-to-contract schemes, which may be used for client-side validation like in RGB protocol etc).
**Index**
Sequentially increased index like in BIP44
Identity basics
---------------
**Identity index** SHOULD be a random number within BIP32 hardened index range.
Rationale: derivation path may be kept public (see decentralized logins below), and use of sequential numbers will leak information of how many identities are used by some person.
**(Identity) scope index**: depending on whether revocation is enabled:
- if revocation is not enabled, or before the first revocation, it SHOULD be any random hardened number
- otherwise, it must be a number provided during the revocation procedure for the previous scope
Rationale for identity scope: it is required for an identity to be safely usable under multiple multisig wallets/descriptors without exposure of the identity xpub to unrelated parties. Its introduction also allows to use the keys derived under the same identity index as a universal decentralized identity (see details below) without the risk of correlation analyses; especially when they are used outside of the transaction context (for instance as a part of login) without the risk of chain analysis against such data (linking logins to onchain transactions).
Identity representations
------------------------
The XpubIdentifier created with extended public key under BIP32 derivation path ending at the level of the identity index is called **bitcoin decentralized id** (hereinafter simply **decentralized id**).
Rationale: XpubIdentifier is a hash of the extended public key, thus id does not leak any confidential information about the user, her/his outputs or any keys used in the setup and after. As a 256-bit number it is sufficient for global unique identification; and it is created in such a way that it will always be unique for each user (based on the selection of random number), seed & derivation path combination; which allows each user to have multiple unique decentralized ids without any significant risk collision. These ids will be scoped to some blockchain & authorization scheme (based on the use of specific signature algorithm).
Decentralized id can be used as a unique user login or a key for searching user metadata with different centralized or decentralized systems, which design is outside of the scope of this proposal (however there is a WIP in this regard involving client-validated LN-based smart contract system).
Aside from the decentralized id, when a user needs to use the identity under some scope (i.e. creating multisig wallet or registering/signing up to some online service or an app) he should use the following string, called “decentralized login” and/or “decentralized id string":
m/purpose’/blockchain'/identity’=[decentralized_id]/scope’=[scope_xpub]
Where:
- purpose', blockchain’, identity’ and scope' have the meaning according to this proposal (see the proposed BIP43 derivation path structure above);
- * decentralized_id* is the decentralized id (XpubIdentifier value at that derivation path level) encoded as BIP350 Bech32m string with HRP set ot `bcid`;
- **scope_xpub* is the Base64-encoded xpubkey (according to BIP32) derived at that level.
Rationale on the use of Bech32m encoding for XpubIdentifier
- the standard 64-hex string can be easily confused with other 64-hex strings such as transaction ids, XpubIdentifiers, SHA256(d) hash values etc. Bech32 prefix provides context making it unambiguously parsable by software
- Bech32m contains a checksum which makes it easier to check whether two ids are equal visually
- `bcid` HRP is selected to signify that this particular id standard is based on bitcoin ecosystem and Secp256k1 curves.
Rationale on login string:
- decentralized login string is designed in such a way that it can both be an id backup for the id owner (providing full information necessary for deriving keys under this id or checking the value of the scoped xpub from the seed) - and give the context (blockchain and signature algo) under which this id is valid.
- text representation of the login string is easy to check in the logs and simple to use in text-based protocols such as HTTP for authentication.
NB: If the revocation protocol is supported this string MUST be suffixed with a revocation single-use-seal (see below) in form of `?txid:vout`
**Examples:**
Decentralized id: bcid1ncr68x65lpvpz8nqtjrchnheru2e5x9rcdf2dk (this id corresponds to XpubIdentifier 9e07a39b54f858111e605c878bcef91f159a18a3; since I do not have Bech32m at hand I have temporally used Bech32)
Decentralized login: m/340’/0'/[bcid1ncr68x65lpvpz8nqtjrchnheru2e5x9rcdf2dk]/20721421274’=[xpub6FHa3pjLCk84BayeJxFW2SP4XRrFd1JYnxeLeU8EqN3vDfZmbqBqaGJAyiLjTAwm6ZLRQUMv1ZACTj37sR62cfN7fe5JnJ7dh8zL4fiyLHV]
Decentralized login with key revocation: m/340’/0'/[bcid1ncr68x65lpvpz8nqtjrchnheru2e5x9rcdf2dk]/20721421274’=[xpub6FHa3pjLCk84BayeJxFW2SP4XRrFd1JYnxeLeU8EqN3vDfZmbqBqaGJAyiLjTAwm6ZLRQUMv1ZACTj37sR62cfN7fe5JnJ7dh8zL4fiyLHV]?0e94ada127fbbc6d2152b18a50fd02ea9aaa608ec20cfc606ad327da1c255201:1
Multisig wallets with decentralized id
--------------------------------------
In case of multisig wallet creation, the parties may share their decentralized id strings in one of two forms:
1. Compact, skipping the scope xpub and replacing it with 32-bit xpub fingerprint:
```
m/purpose’/blockchain'/identity’=[decentralized_id]/scope’=[scope_xpub_fingerprint]
```
2. Full, as specified in the previous section
This will provide all parties with a sufficient information to construct full paths with a sequentally-increased final indexes
m/purpose’/blockchain’/identity’/scope'/case/index
for change and normal cases.
The first option will allow all parties to prepare PSBTs for the common signing process; however they will not be able to generate invoices or track blockchain for new transactions. However, on the other hand, that will not leak the scoped xpub.
The second option allows full features for multisig wallets, including invoice creating and onchain tracking.
Authenticating with decentralized id
------------------------------------
To authenticate (or register) a user must provide the authentification service with the following information:
- Login string from the previous section
- Random number within the **unhardened** BIP32 index range
- A signature, created according to the signature algorithm specified as a part of login (ECDSA or BIP340) with the private key derived with the following derivation path:
m/purpose’/blockchain'/identity’/scope’/random_seed
where *random_seed* is the random number from the above.
This scheme is non-interactive and can be used for authentication, authorization and registration with servers or applications.
Rationale:
- random number is required for avoiding private key reuse
- it is unhardened so the public key required for signature verification may be generated by the service from the scoped identity xpub provided as a part of the login
- random number can’t be a challenge from the service side since it will (a) make the protocol interactive, introducing unnecessary complexity and (b) will allow malicious servers to repeat the same challenge for private key correlation analysis if BIP340 signature is used.
Identity revocations
--------------------
It will be possible to revoke identities using single-use-seals mechanics ([originally proposed by Peter Todd][1]) based on bitcoin blockchain. What's important here is that this will not lead to the increase in transaction size and may be simply combined with normally happening transactions using special signature design procedure (see below).
NB: Since the revocation procedure is non-trivial, it is proposed to have the first version of the standard to be published without it and add it later by using the suffix `?txid:vout` with the revocation single-use-seal added to the identity string.
The protocol runs as follows:
### Identity creation
Alice, after creating a decentralized identity under this standard and its first scope, chooses some of her existing bitcoin UTXOs and uses it as a suffix for the identity/login string. It is important that:
- the UTXO must be protected by a key from the derivation path unrelated to the used identity.
- the UTXO should be mined at a safe depth, such that reogs would have a negligible probability.
- should be spendable by a single signature from a private key in Alice's possession.
### Identity scope revocation
If Alice needs to revoke specific scoped identity xpub (for instance, a private key leak happened) she needs to:
1. Spend the previously specified revocation UTXO signalling about the revocation by setting two most significant bits of the random number `k` used during the signature creation to `01` value.
2. Use the first output of the spending transaction as a new revocation UTXO.
3. For now, she needs to use 32-byte fingerprint | 0x8000000 of the transaction as a new identity scope for future logins and key derivations under the same identity.
### Full identity revocation
Alice also has an option of completely revoking the identity without providing a new scope, which will be an equivalent of removing login or cancelling participation in a multisig wallet. To do so she just needs to set two most significant bits to `10` value instead of `01`.
### Identity revocation detection
Other parties knowing Alice's identity string (her multisig co-signers under the same identity scope or services that her login information is) will know about revocation by monitoring the spending of the revocation UTXO in the blockchain and checking firts two most significant bit values in `k` value computable from the the signature in the spending input. They will be able to monitor consequent revocations using the first output from the revocation transaction as a new single-use-seal. They will also update Alice’s identity scope accordingly and will be able to verify Alice’s new signatures without any communications with her. It’s quite important that they will also be able to decline Alice's login attempts with the revoked key from the moment the revocation tx got into mempool, i.e. instantly.
### Spending single-use-seal without revocation
If, because of whatever reason, Alice needs to spend the UTXO which was previously marked as a revocation UTXO without the actual revocation, she can do that by setting ‘k’ two most significant bits to `00` value. The new revocation UTXO will become assigned to the first input of that transaction, but the identity would not be revoked and the scope value will not change.
Visual summaries
================
I have prepared some visual summary covering the proposal, which may simplify its analysis:
=================
Hope that all make sense. Me and my colleagues spent more than a year on finding ways to build decentralized identity standard suitable for cypherpunk needs, and this is the first part of what I came up with. Since I am also engineer behind [RGB smart contracts][2] (allow complex logic on top of bitcoin transactions & Lightning channels using client-side-validation and single-use-seals), the proposed identity, if accepted, will be later accompanied by layer-2 and 3 solutions on top, giving user the ability to provide the identity meta-information (name, surname, emails, avatars etc) with such features as:
- decentralized non-blockchain database & search engine for metadata: LN network
- no centralized notary: I will not need to ask anyone’s permission if I’d like to change my name
- partial meta-information disclosures: ability to selectively hide some fields
- multiple IDs under some root ID: unlinkable, until I disclose the link myself (and I can prove that the link exists, if I need)
- can be combined with bitcoin multisigs without confidentiality leaks: no onchain analysis is possible
Since there is no need to make that part of BIPs, I narrowed this proposal down to the part which is relevant only in the context of Layer 1 stuff.
——
[1]: https://building-on-bitcoin.com/docs/slides/Peter_Todd_BoB_2018.pdf
[2]: https://rgb-org.github.io/
Kind regards,
Dr Maxim Orlovsky,
LNP/BP Standards Association (https://lnp-bp.org)
& Pandora Core AG
GPG: FBDE A843 3DDC 1E69 FA90 C35E FFC0 2509 47E5 C6F7
https://github.com/dr-orlovsky
IRC: dr-orlovsky@freenode (usually in #rust-bitcoin, #lnp-bp & ##taproot-activation)
Twitter: @dr_orlovsky
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
2021-02-05 17:51 [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity Dr Maxim Orlovsky
@ 2021-02-05 22:00 ` Dmitry Petukhov
2021-02-11 7:27 ` Dr Maxim Orlovsky
2021-02-05 22:37 ` Christopher Allen
2021-02-06 1:15 ` Pieter Wuille
2 siblings, 1 reply; 10+ messages in thread
From: Dmitry Petukhov @ 2021-02-05 22:00 UTC (permalink / raw)
To: bitcoin-dev
В Fri, 05 Feb 2021 17:51:27 +0000
Dr Maxim Orlovsky via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> Testnet path is unhardened from this point & till the end of the
> derivation path: no need to prevent private key leak there,
> simplifies test software (hardened paths require private key access
> for derivation).
I believe this will reduce robustness and will add complexity to the
test software instead. If the derivation path is hardened in 'production
code' and is unhardened in 'test code', then: code paths that depend on
hardened derivation may not be tested; there will be unnecessary
code that will need to deal with 'un-hardening' the paths for test code.
It is much more robust to just change the 'purpose' part of the path,
and leave the rest unchanged.
It is OK to require privkey access to hardened paths in test
software, because the same behaviour is expected in 'production'.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
2021-02-05 17:51 [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity Dr Maxim Orlovsky
2021-02-05 22:00 ` Dmitry Petukhov
@ 2021-02-05 22:37 ` Christopher Allen
2021-02-11 7:28 ` Dr Maxim Orlovsky
2021-02-06 1:15 ` Pieter Wuille
2 siblings, 1 reply; 10+ messages in thread
From: Christopher Allen @ 2021-02-05 22:37 UTC (permalink / raw)
To: Dr Maxim Orlovsky, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 566 bytes --]
Concept ACK.
I, in my role as a co-author of the emerging W3C Decentralized Identifier
standard and of the BTCR DID method, organizer of the Bitcoin Airgapped
Wallet Community (
https://github.com/blockchainCommons/airgapped-Wallet-Community/discussions),
and as principal architect of Blockchain Commons, am very interested in
supporting discussion on this topic, and implementation of anything we
decide. I also have some Patron's to Blockchain Commons interested in this
topic and may be willing to financially support some reference code.
-- Christopher Allen
[-- Attachment #2: Type: text/html, Size: 858 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
2021-02-05 17:51 [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity Dr Maxim Orlovsky
2021-02-05 22:00 ` Dmitry Petukhov
2021-02-05 22:37 ` Christopher Allen
@ 2021-02-06 1:15 ` Pieter Wuille
2021-02-11 14:38 ` Dr Maxim Orlovsky
2 siblings, 1 reply; 10+ messages in thread
From: Pieter Wuille @ 2021-02-06 1:15 UTC (permalink / raw)
To: Dr Maxim Orlovsky, Bitcoin Protocol Discussion
On Friday, February 5, 2021 9:51 AM, Dr Maxim Orlovsky via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
> Hi,
>
> Background
>
> ====================
>
> Had a discussion last night in Bitcoin Core IRC with Peter Wuille on different topics regarding key derivations, security, key tweaks in context of Schnorr signatures & Taproot. Would like to share some action points and plans that emerged from there:
>
> 1. There is a real need for BIP-43 based new BIP with a new purpose field for keys used in Schnorr signatures. Peter will not do it (he is not very much interested in spending his time on wallet-level stuff), so someone else should.
> 2. Keys used in Schnorr signatures MUST NEVER BE used in ECDSA signatures, otherwise there is a risk of private key leak via correlation attack. This is rationale behind N1.
Hi Maxim,
thanks for bringing up this discussion here. I'd like to clarify a few things though, as I think the above is formulated far too strongly.
There are two issues here: (1) reasons to avoid reusing the same key for privacy reasons, and (2) reasons to avoid using related keys for cryptographic reasons. And in practice, solutions to the first (which we already need, unrelated to Taproot/Schnorr) mean the second is largely moot.
# Don't reuse keys for privacy/organizational reasons.
Reusing the same key in Bitcoin scripts - for use in distinct signature schemes or not - should always be avoided. It has obvious privacy implications; I don't think this is controversial, and it's a problem that exists today, unrelated to Taproot. E.g. you don't want to reuse the same keys as both single-sig and participation in multisig.
My personal view here is that distinct standard derivation paths help with this in the simple cases, but they're not a full solution in the most general case. E.g. if you want to use one seed/root to participate in multiple sets of multisig policies, you'll need some kind of index to assign to each anyway. For this reason in general I prefer solutions that explicitly track what path is used for what.
# Don't use related keys for cryptographic reasons
There are some concerns to address here, but I want to make it clear there are no known attacks against usage of related keys across ECDSA and Schnorr, and I don't expect there will be. However, there is probably no proof for this, and creating one may be tricky. On the other hand, the ecosystem (Bitcoin, but also many other applications) has accepted ECDSA long ago, while it had no security proofs whatsoever (and even the ones that exist now rely on fairly unusual assumption; a proof for security of mixed Schnorr/ECDSA usage would inherently need equally unusual assumptions too).
Now, as soon as a hardened derivation separates different uses there is no concern at all. So any solution for avoiding key reuse (section above) that works by assigning (implicitly or explicitly) different hardened derivation paths (as BIP43 etc. do) to different uses implies there is never any concern about related keys across Schnorr/ECDSA.
If the keys are not separated by a hardened step, it's more complicated. Looking at the different cases:
(1) Signing with related ECDSA keys (e.g. two unhardened child keys from the same xpub)
- This is very common on BIP32 usage today, so hopefully it is secure! Tim Ruffing pointed me today to https://link.springer.com/chapter/10.1007/978-3-030-36938-5_8 whose abstract seems to indicate they prove this is actually secure, but I don't know under what assumptions. Note that the comment there about Schnorr not having this property does not apply to BIP340, because it uses key-prefixed Schnorr.
(2) Signing with related Schnorr keys.
- I believe this is secure simply because BIP340 challenges commit to the pubkey (key prefixing), and thus a signature on one shouldn't teach you anything about others. A formal proof is probably a bit longer, but still trivial to construct.
(3) The real question: signing with a Schnorr key that is related to an ECDSA key.
- I don't expect that this is easy to prove, but I have a very hard time imagining how it could be exploitable, given the use of domain-separated hashes. Aspects such as BIP340's key prefixing and the fact that Bitcoin sighashes indirectly commit to the (set of) signing pubkeys make it even harder.
# TL;DR
* For privacy reasons, you should use separate keys/derivation branches for different uses in all circumstances (duh).
* To stay within the realm of provably security it's advisable to make sure ECDSA key and Schnorr keys use distinct hardened derivation steps.
* Even if you don't, you're really just back to the level of assurance we had about unhardened BIP32 ECDSA keys before a proof was known (which I think most people aren't even aware of).
Cheers,
--
Pieter
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
2021-02-05 22:00 ` Dmitry Petukhov
@ 2021-02-11 7:27 ` Dr Maxim Orlovsky
0 siblings, 0 replies; 10+ messages in thread
From: Dr Maxim Orlovsky @ 2021-02-11 7:27 UTC (permalink / raw)
To: Dmitry Petukhov; +Cc: bitcoin-dev
Hi Dmitry,
Thank you very much for readying and analyzing my proposal!
>> Testnet path is unhardened from this point & till the end of the
>> derivation path: no need to prevent private key leak there,
>> simplifies test software (hardened paths require private key access
>> for derivation).
>
> I believe this will reduce robustness and will add complexity to the
> test software instead. If the derivation path is hardened in 'production
> code' and is unhardened in 'test code', then: code paths that depend on
> hardened derivation may not be tested; there will be unnecessary
> code that will need to deal with 'un-hardening' the paths for test code.
<...>
> It is OK to require privkey access to hardened paths in test
> software, because the same behaviour is expected in 'production’.
You are right, agree
> It is much more robust to just change the 'purpose' part of the path,
> and leave the rest unchanged.
Not sure whether the purpose is the correct place to indicate testnet: in this case it we will have to support one testnet per each blockchain type (which is not the case). So probably we should reserve a single dedicated value for any testnet withing ``blockchain` field using hardened path as you suggested - for instance, 0xFFFFFFFF may do the job.
Kind regards,
Maxim
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
2021-02-05 22:37 ` Christopher Allen
@ 2021-02-11 7:28 ` Dr Maxim Orlovsky
0 siblings, 0 replies; 10+ messages in thread
From: Dr Maxim Orlovsky @ 2021-02-11 7:28 UTC (permalink / raw)
To: Christopher Allen; +Cc: Bitcoin Protocol Discussion
Hi Christopher,
Thank you very much! Will look forward to talk to you regarding all of these, as we discussed elsewhere.
Kind regard,
Maxim
> On Feb 5, 2021, at 23:37, Christopher Allen <ChristopherA@lifewithalacrity•com> wrote:
>
> Concept ACK.
>
> I, in my role as a co-author of the emerging W3C Decentralized Identifier standard and of the BTCR DID method, organizer of the Bitcoin Airgapped Wallet Community (https://github.com/blockchainCommons/airgapped-Wallet-Community/discussions), and as principal architect of Blockchain Commons, am very interested in supporting discussion on this topic, and implementation of anything we decide. I also have some Patron's to Blockchain Commons interested in this topic and may be willing to financially support some reference code.
>
> -- Christopher Allen
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
2021-02-06 1:15 ` Pieter Wuille
@ 2021-02-11 14:38 ` Dr Maxim Orlovsky
2021-02-11 20:31 ` Pieter Wuille
[not found] ` <CALqxMTG1MG+PvLfSLRqsa_yHBQOdu7BOqBjm4_ShSsB3CNSCOA@mail.gmail.com>
0 siblings, 2 replies; 10+ messages in thread
From: Dr Maxim Orlovsky @ 2021-02-11 14:38 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Protocol Discussion
Hi Pieter,
... and sorry for misspelling your name in my first e-mail :(
Thank you very much for all the clarifications; it’s good to have them sorted out and clearly structured. From what you wrote it follows that we still need to reserve a dedicated purpose (with new BIP) for BIP340 signatures to avoid key reuse, am I right?
Kind regards,
Maxim
> On Feb 6, 2021, at 02:15, Pieter Wuille <bitcoin-dev@wuille•net> wrote:
>
>
> On Friday, February 5, 2021 9:51 AM, Dr Maxim Orlovsky via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>> Hi,
>>
>> Background
>>
>> ====================
>>
>> Had a discussion last night in Bitcoin Core IRC with Peter Wuille on different topics regarding key derivations, security, key tweaks in context of Schnorr signatures & Taproot. Would like to share some action points and plans that emerged from there:
>>
>> 1. There is a real need for BIP-43 based new BIP with a new purpose field for keys used in Schnorr signatures. Peter will not do it (he is not very much interested in spending his time on wallet-level stuff), so someone else should.
>> 2. Keys used in Schnorr signatures MUST NEVER BE used in ECDSA signatures, otherwise there is a risk of private key leak via correlation attack. This is rationale behind N1.
>
> Hi Maxim,
>
> thanks for bringing up this discussion here. I'd like to clarify a few things though, as I think the above is formulated far too strongly.
>
> There are two issues here: (1) reasons to avoid reusing the same key for privacy reasons, and (2) reasons to avoid using related keys for cryptographic reasons. And in practice, solutions to the first (which we already need, unrelated to Taproot/Schnorr) mean the second is largely moot.
>
>
> # Don't reuse keys for privacy/organizational reasons.
>
> Reusing the same key in Bitcoin scripts - for use in distinct signature schemes or not - should always be avoided. It has obvious privacy implications; I don't think this is controversial, and it's a problem that exists today, unrelated to Taproot. E.g. you don't want to reuse the same keys as both single-sig and participation in multisig.
>
> My personal view here is that distinct standard derivation paths help with this in the simple cases, but they're not a full solution in the most general case. E.g. if you want to use one seed/root to participate in multiple sets of multisig policies, you'll need some kind of index to assign to each anyway. For this reason in general I prefer solutions that explicitly track what path is used for what.
>
>
> # Don't use related keys for cryptographic reasons
>
> There are some concerns to address here, but I want to make it clear there are no known attacks against usage of related keys across ECDSA and Schnorr, and I don't expect there will be. However, there is probably no proof for this, and creating one may be tricky. On the other hand, the ecosystem (Bitcoin, but also many other applications) has accepted ECDSA long ago, while it had no security proofs whatsoever (and even the ones that exist now rely on fairly unusual assumption; a proof for security of mixed Schnorr/ECDSA usage would inherently need equally unusual assumptions too).
>
> Now, as soon as a hardened derivation separates different uses there is no concern at all. So any solution for avoiding key reuse (section above) that works by assigning (implicitly or explicitly) different hardened derivation paths (as BIP43 etc. do) to different uses implies there is never any concern about related keys across Schnorr/ECDSA.
>
> If the keys are not separated by a hardened step, it's more complicated. Looking at the different cases:
>
> (1) Signing with related ECDSA keys (e.g. two unhardened child keys from the same xpub)
>
> - This is very common on BIP32 usage today, so hopefully it is secure! Tim Ruffing pointed me today to https://link.springer.com/chapter/10.1007/978-3-030-36938-5_8 whose abstract seems to indicate they prove this is actually secure, but I don't know under what assumptions. Note that the comment there about Schnorr not having this property does not apply to BIP340, because it uses key-prefixed Schnorr.
>
> (2) Signing with related Schnorr keys.
>
> - I believe this is secure simply because BIP340 challenges commit to the pubkey (key prefixing), and thus a signature on one shouldn't teach you anything about others. A formal proof is probably a bit longer, but still trivial to construct.
>
> (3) The real question: signing with a Schnorr key that is related to an ECDSA key.
>
> - I don't expect that this is easy to prove, but I have a very hard time imagining how it could be exploitable, given the use of domain-separated hashes. Aspects such as BIP340's key prefixing and the fact that Bitcoin sighashes indirectly commit to the (set of) signing pubkeys make it even harder.
>
>
> # TL;DR
>
> * For privacy reasons, you should use separate keys/derivation branches for different uses in all circumstances (duh).
> * To stay within the realm of provably security it's advisable to make sure ECDSA key and Schnorr keys use distinct hardened derivation steps.
> * Even if you don't, you're really just back to the level of assurance we had about unhardened BIP32 ECDSA keys before a proof was known (which I think most people aren't even aware of).
>
> Cheers,
>
> --
> Pieter
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
2021-02-11 14:38 ` Dr Maxim Orlovsky
@ 2021-02-11 20:31 ` Pieter Wuille
2021-02-18 18:58 ` Dr Maxim Orlovsky
[not found] ` <CALqxMTG1MG+PvLfSLRqsa_yHBQOdu7BOqBjm4_ShSsB3CNSCOA@mail.gmail.com>
1 sibling, 1 reply; 10+ messages in thread
From: Pieter Wuille @ 2021-02-11 20:31 UTC (permalink / raw)
To: Dr Maxim Orlovsky; +Cc: Bitcoin Protocol Discussion
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, February 11, 2021 6:38 AM, Dr Maxim Orlovsky <orlovsky@protonmail•com> wrote:
> Thank you very much for all the clarifications; it’s good to have them sorted out and clearly structured. From what you wrote it follows that we still need to reserve a dedicated purpose (with new BIP) for BIP340 signatures to avoid key reuse, am I right?
Maybe, but it would be for a particular way of using keys (presumably: single-key pay-to-taproot), not just the signature scheme itself. If you go down this path you'll also want dedicated branches for multisig participation, and presumably several interesting new policies that become possible with Taproot.
The only thing ECDSA/Schnorr specific about this is that - if you want to maintain provable security - the keys used for ECDSA and BIP340 should be separated by a hardened step. It seems however that all approaches people actually use to prevent reuse do that already.
And as I said, dedicated branches only help for the simple case. For example, it doesn't address the more general problem of preventing reuse of keys in multiple distinct groups of multisig sets you participate in. If you want to solve that you need to keep track of index is for participating in what - and once you have something like that you don't need dedicated purpose based derivation at all anymore.
So I'm not sure I'd state it as us *needing* a dedicated purpose/branch for single-key P2TR (and probably many other useful ways of using taproot based spending policies...). But perhaps it's useful to have.
Greg Maxwell pointed out to me that there may be another reason to want non-reuse across ECDSA and BIP340 keys: if someone were to do all of these wrong:
* not follow BIP340 and re-use RFC6979 for BIP340 nonce generation
* reuse the same keys for both
* sign the same message with both
... you would actually leak your private key. This isn't a concern for Bitcoin transaction signing however, as the sighash (message) indirectly commits to BIP341 or not, and thus it'd be impossible to construct colliding messages. Still, it's a consideration to factor in.
Cheers,
--
Pieter
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
[not found] ` <CALqxMTG1MG+PvLfSLRqsa_yHBQOdu7BOqBjm4_ShSsB3CNSCOA@mail.gmail.com>
@ 2021-02-18 18:52 ` Dr Maxim Orlovsky
0 siblings, 0 replies; 10+ messages in thread
From: Dr Maxim Orlovsky @ 2021-02-18 18:52 UTC (permalink / raw)
To: Adam Back; +Cc: Bitcoin Protocol Discussion
Hi Adam,
Commenting on your question:
> With segWit vs pre-SegWit didn't wallets just select and standardize
> on a different HD derivation path?
>
> Is there something else needed than a Schnorr derivation path?
The general accepted practice (defined in BIP43) is to define a dedicated purpose field for each kind of key derivation and address encoding. There is a dedicated purpose for pre-SegWit, SegWit, multisigs — and now a purpose for Schnorr sigs/Taproot outputs is needed. That is why I brought forward this proposal, which addresses exactly this need - and also will support at the same time multisigs and pre-Taproot outputs, making all previously used purpose fields redundant, simplifying future wallets.
Kind regards,
Maxim
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity
2021-02-11 20:31 ` Pieter Wuille
@ 2021-02-18 18:58 ` Dr Maxim Orlovsky
0 siblings, 0 replies; 10+ messages in thread
From: Dr Maxim Orlovsky @ 2021-02-18 18:58 UTC (permalink / raw)
To: Pieter Wuille; +Cc: Bitcoin Protocol Discussion
Hi Pieter,
Addressing your comments:
>> Thank you very much for all the clarifications; it’s good to have them sorted out and clearly structured. From what you wrote it follows that we still need to reserve a dedicated purpose (with new BIP) for BIP340 signatures to avoid key reuse, am I right?
>
> Maybe, but it would be for a particular way of using keys (presumably: single-key pay-to-taproot), not just the signature scheme itself. If you go down this path you'll also want dedicated branches for multisig participation, and presumably several interesting new policies that become possible with Taproot.
Yes, previously we had a dedicated standards (BIPs) for purpose fields on each variant: single-sig, multi-sig etc. With this proposal I simplify this: you will have a dedicated deterministically-derived *hardened* keys for each use case under single standard, which should simplify future wallet implementations.
> And as I said, dedicated branches only help for the simple case. For example, it doesn't address the more general problem of preventing reuse of keys in multiple distinct groups of multisig sets you participate in. If you want to solve that you need to keep track of index is for participating in what - and once you have something like that you don't need dedicated purpose based derivation at all anymore.
In the BIP proposal there is a part on how multisigs can be created in a simple and deterministic way without keys reuse.
> So I'm not sure I'd state it as us *needing* a dedicated purpose/branch for single-key P2TR (and probably many other useful ways of using taproot based spending policies...). But perhaps it's useful to have.
My proposal is to have a new purpose field supporting all the above: hardened derivation that supports for multisigs, single-sigs etc.
Kind regards,
Maxim
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2021-02-18 18:59 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-02-05 17:51 [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity Dr Maxim Orlovsky
2021-02-05 22:00 ` Dmitry Petukhov
2021-02-11 7:27 ` Dr Maxim Orlovsky
2021-02-05 22:37 ` Christopher Allen
2021-02-11 7:28 ` Dr Maxim Orlovsky
2021-02-06 1:15 ` Pieter Wuille
2021-02-11 14:38 ` Dr Maxim Orlovsky
2021-02-11 20:31 ` Pieter Wuille
2021-02-18 18:58 ` Dr Maxim Orlovsky
[not found] ` <CALqxMTG1MG+PvLfSLRqsa_yHBQOdu7BOqBjm4_ShSsB3CNSCOA@mail.gmail.com>
2021-02-18 18:52 ` Dr Maxim Orlovsky
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox