[bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity

[Dr Maxim Orlovsky <orlovsky@protonmail.com>]

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:

![image](https://user-images.githubusercontent.com/372034/107058405-dd645580-67d4-11eb-986f-a0211d2dd54f.png)


=================

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