[messaging] Simple decentralised KeyBase using the blockchain

Ben Harris mail at bharr.is
Fri Dec 12 18:24:13 PST 2014

Hi All,

I love the idea of KeyBase, but as I'm still waiting in the invite queue
I'd also love a de-centralised version. I've just thrown some ideas around
and would like to see if it holds up to the scrutiny of the group.

The rough idea is to use the 40 socially-responsible bytes in OP_RETURN to
encode something that allows:
  - Me to see that my key-information has been published (block chain is
public, so yay).
  - Me to see that other people aren't trying to imitate me.
  - Everyone to see when I have revoked a key.
  - My contacts to find my key-information.

The simplest KeyBase-esq design is just to publish on your Twitter - "my
key fingerprint is X". The problem is that Twitter might change that to
mention fingerprint Y for select users.

So instead we take all our keys (A), our supported social profiles (B) and
a SHA224 of a 224 bit revocation code (X), concatenate them and hash the
result with SHA224 (C). Concatenate will probably just mean place in sorted

C is then your 224 bit key ID.
Next we take all your profiles in B, calculate the SHA224 of the [account
type] || [account id] (e.g. "twitteruser1") and take the 32 least
significant bits of each to get D (which has the same number of entries as
B, but only 32 bits for each).

Now we publish a transaction to bitcoin and encode the following in the
OP_RETURN. The transaction contains C and D. It fits nicely when there are
only two entries in D, otherwise we do the following.

For the first two profiles publish
"PK" 0 C |D| D(0) D(1)
Where "PK" is the two ascii bytes PK as a magic number. 0 is 0 byte as the
packet type, |D| is the total number of social profiles, D(x) is the x-th
social profile.

For subsequent packets in groups of 6, the packet type is 1, C is only the
first 96-bits of C, and |D| is an incrementing number
"PK" 1 trunc(C) 0 D(x) ...
"PK" 1 trunc(C) 1 D(x) ...

Once this is confirmed in the blockchain, we publish C to our limited
social profiles (Twitter), or ABCX to a full profile (gist/reddit). ABCX
can also be sent to key directories (like KeyBase) or key-directories can
just scrape social profiles.

## Lookup
To confirm someone's ID you start by finding ABCX on their full social
profile (or searching their social name on a key directory). Once you have
ABCX, you check the blockchain for revocation of X, then confirm the
blockchain has D that matches B. Then look up proofs on all the social
profiles mentioned in B.

If this all passes you have the keys for the user.

## Revocation
To revoke publicly, you post an OP_RETURN message with X and the first 80
bits of C.
"PX" trunc(C) X

X can probably be calculated with PBKDF using the hash of AB as the salt.

## Notes
The purpose of D is to detect when someone is planning to impersonate you.
There will probably be collisions in 32-bits but we can only fit so much
in. I expect keydirectories may have a notification service to email you
when a matching D appears.

If OP_RETURN is increased to 80bytes we can fit 10 extra D into each packet.

Mobile apps may choose to trust a key-directory, if they have a list of
block headers the key-directory can still prove that the responses to
queries have been put in the blockchain. Revocation is much weaker here (as
you can't prove it doesn't exist), but multiple independent key-directories
logging PX messages should be as good as reasonably practicable.

The economic value in brute-forcing someone's revocation key should be
close to 0. Users should still pick a good one though.

Putting all of ABCX into the blockchain is do-able (P2SH), but not a
socially acceptable use of bitcoin resources (and might get plugged with

I looked at better ways of encoding D - bloom tables, golomb coding, matrix
filter. In the end this was the simplest and good enough (I think?).

I'd love some feedback, and I would still rather hear the feedback even if
it will take too much time/effort to reword it in a nice way (so don't
delete it just because you think it is too harsh).

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141213/f85ae30d/attachment.html>

More information about the Messaging mailing list