From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id B7EC3C013A for ; Fri, 5 Feb 2021 17:51:40 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id A76EF87268 for ; Fri, 5 Feb 2021 17:51:40 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 9Q8ukcQvpdFv for ; Fri, 5 Feb 2021 17:51:38 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40136.protonmail.ch (mail-40136.protonmail.ch [185.70.40.136]) by whitealder.osuosl.org (Postfix) with ESMTPS id E5D8887266 for ; Fri, 5 Feb 2021 17:51:37 +0000 (UTC) Date: Fri, 05 Feb 2021 17:51:27 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1612547493; bh=hVDeA5GxMIMHTKl/G2JGddhuWItxRsZrttUfCQ3pZJo=; h=Date:To:From:Reply-To:Subject:From; b=sa5/BQzT/3R+gK1hz5MlvrK9HiTF6in+3fbiPMHNZtKJKz2igtUqTygNkUKQfTVsB fXUZnqjiqETUrBs9o9fK4gfA1SzI/ahdpM//JI7j/bQDp4KtdB5w4hbuXvMblEutRH H7uY6gWa7APaNc6VWevWbnGAg/m1OmJNnHszGLP0= To: Bitcoin Protocol Discussion From: Dr Maxim Orlovsky Reply-To: Dr Maxim Orlovsky Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Mailman-Approved-At: Fri, 05 Feb 2021 18:39:20 +0000 Subject: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 05 Feb 2021 17:51:40 -0000 Hi, Background =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Had a discussion last night in Bitcoin Core IRC with Peter Wuille on differ= ent topics regarding key derivations, security, key tweaks in context of Sc= hnorr signatures & Taproot. Would like to share some action points and plan= s that emerged from there: 1. There is a real need for BIP-43 based new BIP with a new purpose field f= or keys used in Schnorr signatures. Peter will not do it (he is not very mu= ch 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 struc= ture of derivation path used before with BIP-44, 45, 84. This change is req= uired to enable the use of all modern wallet use cases under a single stand= ard: single-sigs & multi-sigs, ECDSA & BIP340 signatures. 4. Embedding multisig support in a hierarchical format requires introductio= n of a =E2=80=9Csigner id=E2=80=9D concept as a part of the derivation path= . I found a way how this can be done seamlessly, leading to emergence of de= centralized identity as a side effect. Proposal =3D=3D=3D=3D=3D=3D=3D=3D Derivation path structure & purpose values ------------------------------------------ The new format for the hierarchical derivation BIP32 path is the following: =09m/purpose=E2=80=99/blockchain=E2=80=99/identity=E2=80=99/scope'/case/ind= ex **Purpose:** BIP-43 purpose values under the proposal: - 340=E2=80=99 for BIP340 signatures - ???=E2=80=99 for old-style ECDSA signatures (??? will be set to the BIP n= umber 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 u= nwelcomed by the community and are unnecessary since we have descriptors. Testnet path `1` covers all testnets (no problem with key re-use for valuel= ess testnet or inter-testnet chainanalysis) - this follows the logic of rec= ent changes in other standards related to testnet (use the same Bech32 pref= ixes 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 chang= ing the standard - unhardened numbers will never be used for chains with re= al value. **Identity and scope** Hardened components signify the main identity (decentralized id) and the sc= ope under that id used in context of specific multisig wallet or other iden= tity case. Scope is required to use the same id with different peers withou= t exposing the main identity xpub (and, thus, the scope must be hardened as= well). **Case** This is the same as a =E2=80=9Cchange=E2=80=9D field before (under BIP44 et= c), 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 featur= es (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 ra= nge. Rationale: derivation path may be kept public (see decentralized logins bel= ow), and use of sequential numbers will leak information of how many identi= ties 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 b= e any random hardened number - otherwise, it must be a number provided during the revocation procedure f= or the previous scope Rationale for identity scope: it is required for an identity to be safely u= sable under multiple multisig wallets/descriptors without exposure of the i= dentity xpub to unrelated parties. Its introduction also allows to use the = keys derived under the same identity index as a universal decentralized ide= ntity (see details below) without the risk of correlation analyses; especia= lly 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 (link= ing logins to onchain transactions).=20 Identity representations ------------------------ The XpubIdentifier created with extended public key under BIP32 derivation = path ending at the level of the identity index is called **bitcoin decentra= lized id** (hereinafter simply **decentralized id**). Rationale: XpubIdentifier is a hash of the extended public key, thus id doe= s 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 w= ill always be unique for each user (based on the selection of random number= ), seed & derivation path combination; which allows each user to have multi= ple 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 de= sign is outside of the scope of this proposal (however there is a WIP in th= is regard involving client-validated LN-based smart contract system). Aside from the decentralized id, when a user needs to use the identity unde= r some scope (i.e. creating multisig wallet or registering/signing up to so= me online service or an app) he should use the following string, called = =E2=80=9Cdecentralized login=E2=80=9D and/or =E2=80=9Cdecentralized id stri= ng": =09m/purpose=E2=80=99/blockchain'/identity=E2=80=99=3D[decentralized_id]/sc= ope=E2=80=99=3D[scope_xpub] Where: - purpose', blockchain=E2=80=99, identity=E2=80=99 and scope' have the mean= ing according to this proposal (see the proposed BIP43 derivation path stru= cture above); - * decentralized_id* is the decentralized id (XpubIdentifier value at that= derivation path level) encoded as BIP350 Bech32m string with HRP set ot `b= cid`; - **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 strin= gs such as transaction ids, XpubIdentifiers, SHA256(d) hash values etc. Bec= h32 prefix provides context making it unambiguously parsable by software - Bech32m contains a checksum which makes it easier to check whether two id= s are equal visually - `bcid` HRP is selected to signify that this particular id standard is bas= ed on bitcoin ecosystem and Secp256k1 curves. Rationale on login string:=20 - 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 der= iving 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 th= is 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 wi= th a revocation single-use-seal (see below) in form of `?txid:vout` **Examples:** Decentralized id: bcid1ncr68x65lpvpz8nqtjrchnheru2e5x9rcdf2dk (this id corr= esponds to XpubIdentifier 9e07a39b54f858111e605c878bcef91f159a18a3; since I= do not have Bech32m at hand I have temporally used Bech32) Decentralized login: m/340=E2=80=99/0'/[bcid1ncr68x65lpvpz8nqtjrchnheru2e5x= 9rcdf2dk]/20721421274=E2=80=99=3D[xpub6FHa3pjLCk84BayeJxFW2SP4XRrFd1JYnxeLe= U8EqN3vDfZmbqBqaGJAyiLjTAwm6ZLRQUMv1ZACTj37sR62cfN7fe5JnJ7dh8zL4fiyLHV] Decentralized login with key revocation: m/340=E2=80=99/0'/[bcid1ncr68x65lp= vpz8nqtjrchnheru2e5x9rcdf2dk]/20721421274=E2=80=99=3D[xpub6FHa3pjLCk84BayeJ= xFW2SP4XRrFd1JYnxeLeU8EqN3vDfZmbqBqaGJAyiLjTAwm6ZLRQUMv1ZACTj37sR62cfN7fe5J= nJ7dh8zL4fiyLHV]?0e94ada127fbbc6d2152b18a50fd02ea9aaa608ec20cfc606ad327da1c= 255201:1 Multisig wallets with decentralized id -------------------------------------- In case of multisig wallet creation, the parties may share their decentrali= zed id strings in one of two forms: 1. Compact, skipping the scope xpub and replacing it with 32-bit xpub finge= rprint: ``` =09m/purpose=E2=80=99/blockchain'/identity=E2=80=99=3D[decentralized_id]/sc= ope=E2=80=99=3D[scope_xpub_fingerprint] ``` 2. Full, as specified in the previous section This will provide all parties with a sufficient information to construct fu= ll paths with a sequentally-increased final indexes =09m/purpose=E2=80=99/blockchain=E2=80=99/identity=E2=80=99/scope'/case/ind= ex for change and normal cases. The first option will allow all parties to prepare PSBTs for the common sig= ning process; however they will not be able to generate invoices or track b= lockchain for new transactions. However, on the other hand, that will not l= eak the scoped xpub. The second option allows full features for multisig wallets, including invo= ice creating and onchain tracking. Authenticating with decentralized id ------------------------------------ To authenticate (or register) a user must provide the authentification serv= ice 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 follo= wing derivation path: =09m/purpose=E2=80=99/blockchain'/identity=E2=80=99/scope=E2=80=99/random_s= eed where *random_seed* is the random number from the above. This scheme is non-interactive and can be used for authentication, authoriz= ation 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 ma= y be generated by the service from the scoped identity xpub provided as a p= art of the login - random number can=E2=80=99t 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 priv= ate 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 s= ize and may be simply combined with normally happening transactions using s= pecial signature design procedure (see below). NB: Since the revocation procedure is non-trivial, it is proposed to have t= he first version of the standard to be published without it and add it late= r by using the suffix `?txid:vout` with the revocation single-use-seal adde= d 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 su= ffix 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.=20 - the UTXO should be mined at a safe depth, such that reogs would have a ne= gligible probability. - should be spendable by a single signature from a private key in Alice's p= ossession. ### Identity scope revocation If Alice needs to revoke specific scoped identity xpub (for instance, a pri= vate key leak happened) she needs to: 1. Spend the previously specified revocation UTXO signalling about the revo= cation by setting two most significant bits of the random number `k` used d= uring the signature creation to `01` value. 2. Use the first output of the spending transaction as a new revocation UTX= O. 3. For now, she needs to use 32-byte fingerprint | 0x8000000 of the transac= tion as a new identity scope for future logins and key derivations under th= e same identity. ### Full identity revocation Alice also has an option of completely revoking the identity without provid= ing a new scope, which will be an equivalent of removing login or cancellin= g participation in a multisig wallet. To do so she just needs to set two mo= st significant bits to `10` value instead of `01`. ### Identity revocation detection Other parties knowing Alice's identity string (her multisig co-signers unde= r the same identity scope or services that her login information is) will k= now about revocation by monitoring the spending of the revocation UTXO in t= he blockchain and checking firts two most significant bit values in `k` val= ue computable from the the signature in the spending input. They will be ab= le to monitor consequent revocations using the first output from the revoca= tion transaction as a new single-use-seal. They will also update Alice= =E2=80=99s identity scope accordingly and will be able to verify Alice= =E2=80=99s new signatures without any communications with her. It=E2=80= =99s quite important that they will also be able to decline Alice's login a= ttempts with the revoked key from the moment the revocation tx got into mem= pool, i.e. instantly. ### Spending single-use-seal without revocation If, because of whatever reason, Alice needs to spend the UTXO which was pre= viously marked as a revocation UTXO without the actual revocation, she can = do that by setting =E2=80=98k=E2=80=99 two most significant bits to `00` va= lue. The new revocation UTXO will become assigned to the first input of tha= t transaction, but the identity would not be revoked and the scope value wi= ll not change. Visual summaries =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D I have prepared some visual summary covering the proposal, which may simpli= fy its analysis: ![image](https://user-images.githubusercontent.com/372034/107058405-dd64558= 0-67d4-11eb-986f-a0211d2dd54f.png) =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Hope that all make sense. Me and my colleagues spent more than a year on fi= nding 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 bit= coin transactions & Lightning channels using client-side-validation and sin= gle-use-seals), the proposed identity, if accepted, will be later accompani= ed by layer-2 and 3 solutions on top, giving user the ability to provide th= e identity meta-information (name, surname, emails, avatars etc) with such = features as: - decentralized non-blockchain database & search engine for metadata: LN ne= twork - no centralized notary: I will not need to ask anyone=E2=80=99s permission= if I=E2=80=99d like to change my name - partial meta-information disclosures: ability to selectively hide some fi= elds - multiple IDs under some root ID: unlinkable, until I disclose the link my= self (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. =E2=80=94=E2=80=94 [1]: https://building-on-bitcoin.com/docs/slides/Peter_Todd_BoB_2018.pdf [2]: https://rgb-org.github.io/=20 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-ac= tivation) Twitter: @dr_orlovsky