Puzzle

Mon 20 January 2014
English: New Wikipedia's logo.

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

Enhanced by Zemanta

Related articles (or not):

Category: maths Tagged: Cryptographically Generated Address Domain Name System IPv6 Namecoin Proof-of-work system Protocols maths reflections