Puzzle

Mon 20 January 2014

Famous 3D puzzle (Photo credit: Wikipedia)

The question is: what is a puzzle? The answer I prefer is: a riddle whose solution is hard to find but easy to verify. In computer science, it’s used to provide proof-of-work and usually implemented through cryptographic mechanisms. I found versions of cryptographic proof of work in:

HIP anti-flood system (part of handshake/authentification)
Namecoin ‘s public chain block system
IPv6’s CGA mechanism

HIP

In Host Identity Protocol , puzzle is used for DoS protection. It seems that IETF take into account TCP SYN flooding attack.

In this context, the context and protocol is the following: this is a communication involving two peer (called “Initiator” and “Responder”). Initiator must provide proof-of-work. The puzzle consist in finding a number $J$ such that the $K$ lower bit of $h(I|id|J)$ are zeros (with $\begin{cases}h \qquad\text{a hash function} \\I\qquad\text{an element given by the responder for this exchange}\\ id \qquad\text{HIP identifiers (called HIT)}\\ \| \qquad\text{theconcatenation}\\\end{cases}$). The difficulty is given by $K$ and the puzzle cannot be precompute ( $I$ previously unknown).

IPv6

The first time I heard about cryptography in IPv6 was when I heard about SEND protocol. It is used for Cryptographically Generated Address ( CGA ). The goal is to bind an address and a public key . This way, messages in neighbor discovery can be signed and signature verified (authentication and integrity).

The CGA generation ( step 3 of the algorithm ) ensure proof-of-work.

Namecoin

Here is the commercial stuff. Namecoin is not yet widely used. It uses the same proof-of-work mechanisms as Bitcoin, namely public chain block. This mechanism lies on a peer to peer network and ensure that a transaction is verified by a huge proportion of computing power available in the network.

This chain is a space where anyone can write transaction. Anyone can verify the transaction. The chain is composed of blocks. Each block is cryptographically linked with the previous one. Forks are solved by readding leaf block into a longer chain.

(Non-)Related articles