Bech32 of Transaction as DID

[kimdhamilton]

From @ChristopherA on June 30, 2017 6:44

I really like idea of using a bech32 encoded DID:BTCR as @sipa did some amazing work investing a good error detecting AND correcting encoding algorithm. https://github.com/sipa/bech32

@veleslavs & @jonasschnelli's proposal for encoding the transaction index and block number also make great sense, and I like that the magic values can be used to identify different variants blockchains close to bitcoin (I hope they propose a lightcoin value as it already supports segwit) https://github.com/veleslavs/bips/blob/Bech32_Encoded_TxRef/bip-XXXX-Bech32_Encoded_Transaction_Postion_References.mediawiki

However, this proposal is still not officially a BIP, we don't know who else is supporting it, has not been adopted elsewhere, and may change.

We should check with Blockstack to see if they are up to supporting this proposal or if they have reservation. (I hope they like it).

cc: @muneeb-ali @shea256 @jcnelson

Copied from original issue: WebOfTrustInfo/btcr-hackathon#2

[kimdhamilton]

From @jonasschnelli on June 30, 2017 7:55

However, this proposal is still not officially a BIP, we don't know who else is supporting it, has not been adopted elsewhere, and may change.

Yes. It's currently in the "discussion-phase", although, there was not a single response (AFAIK) on the mailing list.

[...] identify different variants blockchains close to bitcoin (I hope they propose a lightcoin value as it already supports segwit)

There is a 5-bit magic (https://github.com/veleslavs/bips/blob/Bech32_Encoded_TxRef/bip-XXXX-Bech32_Encoded_Transaction_Postion_References.mediawiki#reserved-values) that should allow some other blockchains.

The "Bech32 Encoded Transaction Postion References" proposal is independent from SegWit. All it does it creating a reference to a confirmed transaction with error correction and with a char-length as short as possible.

As an example: "tx1-rk63-uvxf-9pqc-sy" is my official communication key reference (after the BIP above). It's a revokable pubkey and it allows anyone to establish a secure connection (the initial setup at least).

And the great thing about light client is...

The txref parsing will give you block hight and tx position.

• A light client can fetch the required headers (just a couple of KBs when using checkpoins or a couple of MB when it doesn't).
• The light client can fetch the block where the tx-ref points to
• The light client can grab the txid as the given position and analysis it (example: check if the key is revoke, etc.)

(is a 5seconds process even if the light clients has no header chain yet)

[kimdhamilton]

From @ChristopherA on July 8, 2017 2:28

@jonasschnelli Your example above:

"tx1-rk63-uvxf-9pqc-sy" is my official communication key reference (after the BIP
above). It's a revokable pubkey and it allows anyone to establish a secure connection
 (the initial setup at least).

This is EXACTLY what DIDs are for! Bootstrapping into a secure setup with another party. There is actually a fairly large community of people working at this at #RebootingWebOfTrust community and in the W3C's Credentials CG and Verifiable Claims WG.

In effect you have the first DID which is did:btcr:tx1-rk63-uvxf-9pqc-sy -- searching on it in Google I see that you are already using it in your Twitter profile!!

Until I have my converter code all fixed, what is the txid of that? What are your ideas about revocation?

[kimdhamilton]

From @sipa on July 8, 2017 2:32

Please don't abuse the UTXO set as key revocation storage :(

[kimdhamilton]

From @ChristopherA on July 8, 2017 2:45

@sipa, @petertodd had some ideas about how we can minimize that in the future. I'm not sure it will go to zero, but much reduced. He hasn't published his technique yet but I presume it will also be similar to one he is working on for #opentimestamps

For now we are trying to get a prototypes functioning, but your concern is valid and been noted for some time (it is issue #4 in this repo for instance :-) )

[kimdhamilton]

From @veleslavs on July 9, 2017 12:19

@sipa one of the core benefits of using the blockchain for identity enrolment is the ability to use proof-of-burn; and proof-of-burn absolutely is not an 'abuse' of blockchain space. Bitcoin has natural anti-ddos preterites that users, quite legitimately, wish to make use of. One of these uses is WoT.

On revocation, revocations are indeed a natural utility of a globally consistant and replicated databases, such as Bitcoin. I would argue that having revocations that are globally propagated is a feature and certainly not a 'abuse'.

The fact that the blockchain is has a limited amount of storage is one of the core features that makes it attractive for use in WoT projects, all WoT projects are plagued by the "Default Trust Problem" that is a subset of the "Normalisation over a Null Field Problem". The use of a non-free enrolment transaction solves this fundamental problem of Web Of Trust Networks in a very natural and complete manner.

Please have a look at my and @jonasschnelli 's work-in-progress BIP for WoT enrolment transactions. There is some parts that are under active consideration (for example, making full use of SegWit), however; this BIP makes it clear that the utility of the blockchain isn't strictly only useful for financial transactions.

We would, of course, encourage your technical, rather than political feedback. Everyone has a slightly different view of what Bitcoin is. I personally hold the view that every use-case of block-space should be treated equality, based upon the natural metric of transaction fees.

https://github.com/veleslavs/bips/blob/wip/bip-XXXX-Revocable_Public_Key_Enrolment_Transaction_with_Optional_Cost.mediawiki

[kimdhamilton]

From @veleslavs on July 9, 2017 12:37

@ChristopherA A pull request for our Bech32 encoding of Transaction References has been opened: https://github.com/bitcoin/bips/pull/555

No number has been assigned as of yet.

[kimdhamilton]

From @sipa on July 9, 2017 16:35

@veleslavs Well, it just doesn't scale. You can't expect there to exist an unspent UTXO for every human in the world (or any meaningful subset thereof). Don't start off building technology that will be unusable before it reaches any sizable goal.

I personally hold the view that every use-case of block-space should be treated equality, based upon the natural metric of transaction fees.

Let's agree to disagree then. Also, you're not just using block space, but UTXO space which is far more precious and not paid for. As Bitcoin's UTXO set grows - especially when accelerated by uses that don't contribute to its monetary value - I expect that at some point a soft fork will be introduced that makes its growth restricted.

[kimdhamilton]

From @jonasschnelli on July 9, 2017 18:28

I guess the whole WOT layer is currently in experimenting phase. I'd say let them try out things.

Don't start off building technology that will be unusable before it reaches any sizable goal.

Wouldn't the same argument be true for Bitcoin as a payment system (at least back in 2009)?

[kimdhamilton]

From @sipa on July 9, 2017 18:30

Wouldn't the same argument be true for Bitcoin as a payment system (at least back in 2009)?

Even in 2009, the assumption wasn't that every payment would happen on chain (see early writeups on payment channels, etc).

[kimdhamilton]

From @ChristopherA on July 9, 2017 18:55

@sipa, @jonasschnelli @veleslavs — an interesting point of the DID (Decentralized IDentifier) approach is that a Bitcoin DID doesn't have to scale for all the humans in the world. Instead there can be many DID methods, each which can have different requirements. There are already two different DIDs with different properties proposed for Ethereum (the biggest one being uPort), one for an identity specific blockchain called Sovrin or Hyperledger Indy, one for an IPFS based identity info, and a legacy PGP one.

This means that each DID method can serve its own niche. In the case of this hackathon, we are creating a spec for high value pseudoanonymous identities, for with Bitcoin is ideal. See the example of a young female British programmer of Syrian descent described in verifiable claims use case I wrote up in https://github.com/w3c/vc-use-cases/issues/31 (which I plan to move here).

The DID:BTCR method is much more restrictive than other DID methods. I want to minimize scaling issues such as UTXO bloat now, and later to work with Bitcoin associated layer 2 solutions (maybe a DID is a spent transaction pointing to a specialized sidechain), but to be absolutely clear, we don't want give everyone on earth a bitcoin UTXO.

[kimdhamilton]

From @ChristopherA on July 9, 2017 19:1

@sipa, @jonasschnelli, @veleslavs — for an example of an identity focused bitcoin-style sidechain, see http://www.truthcoin.info/blog/codex-identity-sidechain/ by Paul Sztorc (@truthcoin) — he is the creator of drive chain and is a member of the #RebootingWebOfTrust community. That proposal is only a napkin concept, but my point is that as L2 solutions emerge, we can use them to scale Bitcoin style DIDs.

[kimdhamilton]

From @sipa on July 9, 2017 19:1

Why for example not point to an input that via sign-to-contract commits to the identity and a revocation key, and say that if any later transaction input that signs with the revocation key appears, it is to be considered revoked?

That consumes less block space, is more flexible (only depends on inputs, not whole transactions in a specific format), makes the transactions not distinguishable from normal ones (so you don't risk censorship, which AFAICT is the only reason for using a public chain in the first place), and the identity does not occupy UTXO space.

[kimdhamilton]

From @ChristopherA on July 9, 2017 19:9

@sipa - Can you write up with just a little more detail what that looks like? A napkin skech? I've been trying to get @petertodd to write up his similar thoughts for 9 months. For instance, how does one search for that later transaction that revokes using a light client?

@jonasschnelli — Or maybe you grok better what @sipa is proposing? What was your approach to revoke your id of tx1-rk63-uvxf-9pqc-sy ?

[kimdhamilton]

From @sipa on July 9, 2017 19:17

To register an identity, spend any transaction output (for which you have the key), using a sign-to-contract signature. That is a normal, valid, ECDSA signature that is indistinguishable from a normal one. However, it can be proven to commit to some data (which in this case has same function as the "Signing Data" + a revocation scriptPubkey).

To refer to an identity, just point to that input, give the revocation scriptPubKey, and show that it in fact commits to the expected data.

To revoke a key, spend any output with the revocation scriptPubKey. You can search for this revocation using BIP37, but only if you know about the identity in the first place.

[kimdhamilton]

From @sipa on July 9, 2017 19:24

Actually, why does the identity establishment need to go in the chain in the first place? Just tell people "My identity key is X, if you ever see a spend on the chain that uses some_derivation_function(X), it is revoked"?

[kimdhamilton]

From @jonasschnelli on July 9, 2017 19:31

In general I agree with @sipa about the censorship problem and the fact that UTXO "spam" (OP_RETURN) is not scalable. The sign-to-contract signature sound promising (need to have a closer look).

I haven't really took a close look into revocation (I'm more following this WOT topic in a low-prio manner) but I kinda liked that with the tx-ref id (like my tx1-rk63-uvxf-9pqc-sy) you can lookup my identity-key with a single ~1MB SPV block fetch and know wether its revoked or not (SPV/non-validation though).

Actually, why does the identity establishment need to go in the chain in the first place?

I guess the usability layer is quite important. You can handout pubkeys, sure. I just like the fact that I can handout the unique tx1-rk63-uvxf-9pqc-sy which allows everyone to check how much I have "burned" to proof my identity and if it's revoked or not.

[kimdhamilton]

From @sipa on July 9, 2017 19:39

I guess the usability layer is quite important. You can handout pubkeys, sure.

So the only reason to store the registration on the chain is so that you can have a short identifier ?

That sounds ridiculous to me. You're introducing a costly and censorship-enabling step to your protocol just so the string you have to pass to someone else is a few characters shorter?

[kimdhamilton]

From @ChristopherA on July 9, 2017 19:42

I would love to figure out a way to address @sipa's concerns and find a way to use sign-to-contract, integrate it with @veleslavs's @jonasschnelli's thoughts proposed in #24, and somehow find a way to do rotation and a DDO pointer. If we can do this, not only can it be a useful BIP, but I'd be willing to drop my BTCR prototype idea and move to making did:tx1 method a W3C standard track document as well.

[kimdhamilton]

From @jonasschnelli on July 9, 2017 19:54

That sounds ridiculous to me. You're introducing a costly and censorship-enabling step to your protocol just so the string you have to pass to someone else is a few characters shorter?

As you know, I often look from an angel where usability is important and I think a few characters matter for an identity system. IMO, a short ~identifier (like a phone-number) is a key-feature how to attract users who are familiar with centralised systems.

@sipa: I agree with you on the censorship-enabling problem.

I guess some of the desired properties are:

• Short identifier
• Light client lookup possible (ideally a single block, filtering avoided)
• indistinguishable from other transaction (censorship-resistance)

Is this short-id approach a sledgehamer for cracking a nut regarding using the Bitcoin-Blockchain? I don't know. I guess people need to experiment,... and debating with @sipa will very likely improve the available proposals and ideas. Also, be aware that not everyone has the experience on a level where @sipa is.

Helping, explaining and pinpoint (concept) flaws is what the WOT guys need.

[kimdhamilton]

From @sipa on July 9, 2017 19:58

Short identifiers are fundamentally incompatible with censorship resistance, I believe (my sign-to-contract idea above does not support it, as you need to communicate the revocation key and s2c proof).

If you have a short identifier, which presumably means it cannot contain cryptographic material, it likely means that the registration (and revocation key/puzzle) is visible to people who do not have the identifier (by scanning the chain for things that are interpretable as registrations). This means that miners will know what to censor if they're colluding with someone who's trying to prevent you from revoking.

[kimdhamilton]

From @ChristopherA on July 9, 2017 20:21

This is why I like the idea of our DIDs just being a block number and a transaction id. If you want true censorship resistance that don't do an op_return (what we call a default DDO) and use the first spent output as a revocation, then this transaction indistinguishable from any other transaction. Clearly that causes UTXO bloat, and it can't be rotated, but if a user wants a simple censorship resistant DID that has a proof of existence timestamp and a published public key, it can't be beat. If you don't need that level of censorship resistance, use a more scalable solution.

[kimdhamilton]

From @sipa on July 9, 2017 20:25

@ChristopherA You want censorship resistance for the revocation, not the publishing. If you're being censored for registering, just don't start using the identity and try again. If your revocation is censored, your identity may have been stolen.

Regardless of how you encode things, if your identifier is short, it means that the revocation is detectable for everyone.

[kimdhamilton]

From @petertodd on July 10, 2017 0:2

@sipa your comment "Regardless of how you encode things, if your identifier is short, it means that the revocation is detectable for everyone." is incorrect. The length of identifier is irrelevant to whether or not revocation is detectable by everyone.

First of all, regardless of whether the identifier is a cryptographically secure 256-bit commitment or some sort of short id, anyone who already knows the revocation conditions can obviously detect a revocation and thus has an opportunity to censor it. The only way to avoid that problem is time-lock crypto. (1)

So, let's assume we're talking about a scenario where the adversary doesn't know the revocation conditions. For this to be true requires us to have consensus over the set of short ids, without making the actual cryptographic conditions attached to those short-ids public.

We can easily achieve this by having the short id be a tuple of block height and transaction # (2), where the transaction commits to the cryptographic conditions for that short id in something like an OP_RETURN or secp256k1 commitment(3), without actually publishing those conditions. For example, suppose we want to generate a short-id for a master pubkey that's revocable by publishing a revocation nonce. Our protocol to assign that short-id can be to create a transaction where the first input must spend a single-CHECKSIG output, with (master-pubkey, H(revocation-nonce)) committed via a secp256k1 commitment.

Even though what the short-id commits to isn't public, it's easy to see that the short-id is still a perfectly secure commitment: provided Bitcoin's consensus does not itself fail, it is not possible to construct a false proof for any other identity that has the same short-id.

Revocation Condition Promiscuity

The real question though is how exactly are these short-ids being used? Somehow a user needs to be able to get the data associated with a given id; we're obviously not going to publish all that data in the Bitcoin blockchain.

For short-ids to be useful, it must not be possible to always pass that data directly from user-to-user - if it was we wouldn't need the short-ids in the first place. So we must have a situation where users get short ids from other users over bandwidth constricted mediums like business cards, and the actual data the short-ids commit to is found via something like the PGP keyserver infrastructure.

The thing is, such infrastructure has to be very carefully designed to avoid making revocation conditions public, or you'll make the censorship issue moot. For example, if I'm using my short-id to sign emails, the best you could do is have a protocol where something like H(H(revocation-nonce)) is published on that infrastructure, and email signatures include H(revocation-nonce). But this fails the moment I send a signed email to a public mailing list, or sign a public git commit; the most valuable, widely used, identities are the most vulnerable.

Short IDs vs Short Commitments

Depending on Bitcoin is itself a huge usability issue for a lot of reasons, such as dealing with contentious hard forks. These issues are all avoided if the primary identifiers is a cryptographically secure commitment rather than a short id. Notably, cryptographic attestations should sign a full cryptographically secure commitment rather than a short ID. Equally, that allows us to use those full commitments when possible, e.g. where we're verifying an identity via a QR-code, a Keybase-like automated means such as a Tweet, or a device to device NFC connection.

In the best case, users shouldn't have to deal with meaningless numbers at all. Signal is a good example here, with its UI based around a verification number that's ideally verified via QR-code in a phone-to-phone fashion. Similarly, look at how Keybase verifies that user accounts are tied to identities.

So let's recast these human-meaningless numbers as verification numbers that help you verify an identity rather than identities themselves. Doing this immediately has one huge advantage: verification numbers can be changed independently of the identity. So if Bitcoin splits, we can figure out what "Bitcoin" now means after the split, and give users the ability to get a new, updated, verification number for their cryptographic identity once the dust settles.

Note how this strongly suggests that the whole DID concept is flawed.

How Many Bits Does an Identity Verification Commitment Need?

Specifically, do we need collision resistance, or just second-preimage resistance?

Given that digital identities aren't scarce I can't see why we need collision resistance when UI flows are cast as verification. So long as cryptographic attestations are on full-collision resistant commitments, by preventing birthday collisions you're simply preventing the identity owner from creating two identities, something they can do anyway.

That means our identity verification commitments just need 128bits, or 26+3 bech32 characters. Is typing in 29 characters really so onerous that we want to add a Bitcoin dependency? Heck, we can easily shorten that further with some grinding, which could also double as a checksum. 32 bits of grinding is feasible, which could get us down to 19 character verification commitments like l5rj-jhrt-ec4o-j3xu-r6i That's only three more characters than credit card numbers, and just two characters longer than the transaction position reference BIP proposes.

Footnotes

1) Basically, design the revocation scheme such that if the block interval is x, it takes k*x inherently serial computation to check if a given message published to the revocation medium is in fact a revocation. This could be implemented via hash chains, as my https://github.com/petertodd/timelock does, but for a truly practical implementation you need a timelock crypto scheme where the end result of the attempted decryption can be trustlessly proven so untrusting peers can collaborate; I don't know of any such timelock scheme right now.

Related is a rolling retroactive revocation scheme. Basically, commit to a set of revocation conditions, one for each time interval, and revoke via publishing a revocation prior to when the revocation condition is revealed. Validators would then not consider a signature valid until the revocation conditions had been published. This gives characteristics similar to just using short expiry times, while still being able to reliably revoke even in the event of full compromise of all secret keys.

2) Note how we could add a third merkle tree to scale via allowing multiple short ids to be created with a single transaction, by having the transaction actually commit to a merkle tree of commitments, with a shrot-id being the tuple (block #, tx #, id #)

3) That you may want more than one commitment method strongly suggests that short-ids should be versioned, to allow new commitment methods to be added in the future.

[kimdhamilton]

From @ChristopherA on July 10, 2017 0:9

See also my new issue on censorship resistance of revocation in #25

[kimdhamilton]

From @veleslavs on July 10, 2017 3:41

@sipa thank you for you prompt reply. I would like to (hopefully) address both the concerns of scaling that you brought up.

You can't expect there to exist an unspent UTXO for every human in the world (or any meaningful subset thereof). Don't start off building technology that will be unusable before it reaches any sizable goal.

I can completely agree in the case that Bitcoin was the only blockchain in the world; however the case is that there are many blockchains with significantly differing security and data costs involved. - This gives users a choice if they wish to enrol their ID on a expensive and high security blockchain as Bitcoin; or a more economically priced blockchain such as Litecoin. - Bech32_Encoded_TxRef have been deliberately designed to support multiple blockchains and systems; so that any system that makes use of them can be transparent to users. (of course GUI's will need to be well-designed to show the relevant information and not confuse users).

If there is a multitude of different blockchains (or more likely side chains), then the case every person having few UTXO outputs becomes quire compelling. - They will also always need at-least one output on a blockchain to hold their actual funds. So this is only a linear increase of scale.

As Bitcoin's UTXO set grows - especially when accelerated by uses that don't contribute to its monetary value - I expect that at some point a soft fork will be introduced that makes its growth restricted.

I hope this will happen also. I hope that transaction fees one-day closely follow the actual costs involved for the network; however the difference between a 'economic' and 'non-economic' transaction is in the eye of the beholder.

[kimdhamilton]

From @veleslavs on July 10, 2017 4:1

I don't get the particular concern about censoring ID's on the blockchain. ID's are enrolled virgin and have no political value until they are actually used for a political purpose. Once they have been successfully inserted and buried in the blockchain dose the censorship concern still stand?; I cannot see how censorship here can be a concern.

About revocation: A revocation should be gossiped throughout the network; the moving of the revocation output should be a mer formality; the ID should be considered revoked well before the revocation transaction has actually been committed to the network.

I recommended using the simple pre-image to a 256bit hash as the revocation key. If a standard template is used for ID enrolment; the anyone will be able to generate the revocation spend from just the pre-image value. However, I'm sure people here can come up with more clever crypto; I just personally like having really dumb and simple crypto for revocation; but it is just a preference.

[kimdhamilton]

From @veleslavs on July 10, 2017 4:12

Myself and some of my friends have put a great-deal amount of work into designing a set-of-supporting infrastructures for supporting ID's; the WoT and it's associated distributed and decentralised data-structures. However the work is in a form that is far-too-young to publish publicly yet. When you dig into the decentralised WoT problem you quickly find it is dungeon with dragons and many bodies of failed attempts (well, every attempt so far hasn't gained transaction).

The approach that we have been taking that is radical to the other attempts: we have full-dependance on Proof-of-Burn and Proof-of-Blockchain-Commitment for anti-spam/anti-ddos. This is something that the other approaches have all failed with: "What happens if I create 1TB of ID's and flood the network". Well, with Bitcoin; you would have to insert that 1TB of ID's into the blockchain; and that would be very expensive (well indeed it would be impossible).

But don't let this stop you for formulating your own proposals; Unfortunately, I do not have the time to work full-time on this right now (at the end of the month I will be back full-time in WoT world).

[kimdhamilton]

From @ChristopherA on July 10, 2017 4:37

@veleslavs Don't concern yourself that we are rushing. Even this purpose of this virtual hackathon is to better inform us about the issues, which will prepare us for our next F2F in Boston in October. You'll see in our GitHub that we've been working on this hard since Pieter Wuille, Greg Maxwell, Peter Todd & others joined us for the first #RebootingWebOfTrust in November of '15.

You'll find many documents from our members in our repos, both in the topic directories for each event, and the collaborative documents that we have done together, the highlights of which are listed at http://www.weboftrust.info/papers.html

I'd love to support your efforts in any way we can. A particular advantage is that we have the potential to also affect the broader community through our W3C and United Nations efforts.

Is there anything we can do this week to help? Any unanswered questions? And of course, we also would love to help when you are back more full time on WoT. And of course we'd love to have you at the October #RebootingWebOfTrust if you can make it!

[kimdhamilton]

From @narula on July 11, 2017 20:27

@veleslavs gossiping to the network is not a long term solution. The revocation must be stored somewhere so a future user can find it. Where are you storing it?

[kimdhamilton]

From @veleslavs on July 13, 2017 13:8

@narula the long term solution that I had proposed is that the revocation output is spent. With UTXO commitments this becomes very quick to lookup and verify. The gossiping network is for new revocations.

However on a side note; having a indexing server for 7B+ ID's and revocations is not that unreasonable. So the gossiping network in-itself with quite a reasonable amount of storage can work well without a blockchain for revocation. - The total number of ID's is restricted by blockchain space; so we don't have the problem of an attacker pumping the network with TB's of random ID's.