[messaging] Simple decentralised KeyBase using the blockchain

zaki at manian.org zaki at manian.org
Mon Dec 22 20:39:29 PST 2014

Hi Ben, your proposed idea seems like one of many applications of what is
being referred to as "proof of publication" applications of a blockchain.

Proof of Publication seems to be a fairly hot topic in both crypto startup
land at the moment with the announcement of Ethereum fork Eris and a long
thread on the bitcoin-dev mailing list.


One of the central debates is the concept of keeping a tree headers in the
blockchain like Keybase and Factom do allowing an efficient proof of
timestamping of data. Or hashed directly into the blockchain as you and
Peter Todd proposed to permit proof of non-publication.

Anyway here is the a link to the discussion.


US number: +1 650-492-8286
Text Secure
Surespot/Wickr: zmanian
Public Key

On Mon, Dec 22, 2014 at 8:11 PM, Ben Harris <mail at bharr.is> wrote:

> Looks similar, but pushing the whole object onto the blockchain instead of
> a tiny amount. Probably a better solution than trying to cram as much as
> possible into 40 bytes on a protocol that is hostile to non-transactional
> data.
> On 17 December 2014 at 21:59, Joseph Bonneau <jbonneau at gmail.com> wrote:
>> Hi Ben-
>> Is what you're describing similar to Onename (https://onename.io/)? They
>> use Namecoin instead of Bitcoin so that transferring/updating your info is
>> more straightforward and you can have a human-readable handle, but
>> otherwise I think they have the same idea of using a blockchain and
>> collecting verification of your social media accounts.
>> Joe
>> On Fri, Dec 12, 2014 at 9:24 PM, Ben Harris <mail at bharr.is> wrote:
>>> 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 JSON.
>>> 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
>>> P2SH2).
>>> 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).
>>> Thanks
>>> -Ben
>>> _______________________________________________
>>> Messaging mailing list
>>> Messaging at moderncrypto.org
>>> https://moderncrypto.org/mailman/listinfo/messaging
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141222/0f4b658e/attachment.html>

More information about the Messaging mailing list