Catena – An Efficient Bitcoin Non-equivocaton Witnessing Scheme

 

Security often relies on non-equivocation. For instance, whenever a Certificate Authority (CA) equivocates via signing certificates in a contradictive manner for the same given identity, it can impersonate internet services and undermine users’ privacy. Practically speaking, this has already occurred several times. To avoid equivocation, Certificate Transparency (CT) is proposed as means of publicly logging all certificates issued by a CA. Nevertheless, a CT log server has the capability of equivocating about issued certificates’ logs and when collaborating with a colluding CA, impersonation attacks can be launched.

Even though gossiping about logs can aid in detection of equivocation, the process can be rather slow or cannot happen at all, given the fact that gossip messages can be infinitely delayed. The Tor network represents a good example, where malicious servers are capable of equivocating about the group of Tor relays and trace back users, i.e. deanonymize them, via tricking them to connect to malicious relay nodes. Accordingly, it is widely believed that non-equivocation represents a pivotal security requirement across many of today’s systems, including cryptocurrency blockchains, public key distribution systems and software transparency schemes.

Unfortunately, it is almost impossible to achieve non-equivocation without relying on trusted third parties. To address this impossibility, systems enforce a weaker feature known as “fork consistency”. Fork consistent systems render equivocation a “permanent” state and thus, simpler to prove in the future when users can communicate, or “gossip”, out of band. Nonetheless, for systems such as public key platforms and Tor’s servers, equivocation attacks can be launched and go undetected while seriously undermining users’ security and privacy.

A recently published paper presented a solution to this problem via “Catena”, an efficiently verifiable Bitcoin witnessing protocol. Catena enables an endless number of thin clients, e.g. mobile phones, to efficiently approve, or agree on, a log of application specific statements which are managed via an adversarial server. Catena deploys a log in the form of a chain of OP_RETURN transactions and prevents the occurrence of forks in the log through shielding bitcoin’s blockchain against double spend attacks. Particularly, whenever a log server wants to equivocate, it has to launch a double spending attack. Accordingly, Catena logs are rather difficult to fork similarly to bitcoin; a malicious user who does not control an enormous portion of the network’s hashing power will not be able to fork bitcoin and so, will not be able to fork Catena’s log too.

On the other hand, apart from previous studies and researches, Catena reduces the required bandwidth for log auditors from 90 GB to less than 100 MB. To be more precise, Catena’s users will only need to download all headers of bitcoin blocks (they are currently less than 35 MB) and a small, 600 byte, proof for every statement in each block.

The below diagram shows how Catena works. Catena represents a long chain of bitcoin transactions. For each Catena transaction, there are two outputs:

1. A continuation output which is the amount that will be spent by the next Catena transaction, thus, forming a chain.
2. An OP_RETURN output, which is responsible for committing an application specific statement.

The server will pay transaction fees for each statement issued. For applications that can publish a large number of statements, batching can be done to minimize the fees.

 

Catena is implemented in Java via the bitcoinj library. Catena is used to extend CONIKS, which  is a recent transparency scheme, to witness bitcoin’s blockchain public key directory, where auditors can efficiently verify it. Catena can maximize the security of many of today’s online systems including Tor’s servers, public key directories of various cryptocurrency blockchains and schemes of software transparency.