Date: Fri, 05 Feb 2021 17:51:27 +0000
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: Dr Maxim Orlovsky <orlovsky@protonmail.com>
Reply-To: Dr Maxim Orlovsky <orlovsky@protonmail.com>
Message-ID: <D962F4E0-E10F-433D-BFC9-3462A8A9CF7A@protonmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures &
	decentralized identity
Precedence: list

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