Technical: How captchas secure the blockchain
CaptchaCoin introduces proof of human-work as a way to decentralise mining, but what purpose do the captchas actually serve?
Here we will outline how the captchas are created, where they sit within the CaptchaCoin system, and how solving them then shows proof of human-work to secure the blockchain.
Here we will outline how the captchas are created, where they sit within the CaptchaCoin system, and how solving them then shows proof of human-work to secure the blockchain.
Firstly, a random secp256k1 private key is generated. This produces a corresponding public key, which is then SHA256 hashed to give a captcha address. For example:
Private key:
a6 2b be 2e 78 70 75 f6 f9 5f 85 64 0e 87 2a 7d 8d 34 d1 cc 39 31 3c 29 5f ae 20 fc cf 68 e2 0b
Compressed public key:
02 f4 65 b8 17 57 ce 34 7f 89 37 45 42 6c b3 e3 cd 85 98 0b f1 cc 19 76 50 98 36 6d 55 a3 70 9d f4
Address:
ea 1b ac cc 86 87 bb 4c 99 37 32 c9 2d b7 59 9f 21 d3 f7 f4 76 de a2 f7 5b 97 58 8d df 81 a1 ce
The address is stored in the CaptchaCoin protocol. No other part of the captcha process, including the captcha itself, is directly stored within the protocol.
The private key is then used to generate the 4 elements of the captcha: the position of the correct captcha image, and each of the 3 letters.
In this example we will assume the captcha is for a 64 image difficulty.
A byte is randomly chosen to determine the position of the correct captcha image. If this were byte 7 (f6, 246) then we calculate 246 mod 64 to determine the correct captcha image will be located in position 54.
Another byte is randomly chosen for the first character. If this were byte 20 (39, 57) then calculating 57 mod 24 gives 9, which corresponds to letter K.
Note that only 24 characters are used in the captchas, and therefore the byte for a letter must be less than 240, else some letters will appear with a higher frequency than others.
This process is repeated for the remaining 2 characters. For this example, the second letter is from byte 4 (78, 120 - letter G) and the third letter is from byte 23 (29, 41 - letter T).
Lastly, a final byte is randomly chosen to prevent brute forcing the solution.
This gives the following distorted private key:
a6 2b be 2e 00 70 75 00 f9 5f 85 64 0e 87 2a 7d 8d 34 d1 cc 00 31 3c 00 5f ae 20 fc cd 68 e2 0b 07 14 04 17 1c
The final 5 bytes give the byte location of the correct image position, 3 characters and the random byte. The byte value for each of those characters in the private key has been set to 00, except for the final random byte.
A miner is given the captcha, as well as the distorted private key. Once the miner has determined the position of the image, they know the possible value of one of the unknown byte values. In our example, the correct image is located in position 54, which could correspond to one of four possible correct byte values.
Similarly, each letter correctly solved reduces the possible byte value to one of ten.
The final unknown byte value has been reduced by a random amount. This reduction will probably be a small number (0 to 5) but could potentially be up to 255. In our example, byte 28 been reduced by 2 from cf to cd.
The miner will then test all of the 4,000 possible partially known byte values (4 from the position, 10x10x10 from the characters) against the random byte to see if any combination produces the captcha address. If not, the random byte is increased by 1 and the process repeated until the address is found.
Testing each of the 4,000 possible values should take approximately 1 second, depending on the miner's device. Brute forcing the solution would instead require checking up to 900 billion possible different byte values, which would not be efficient. Note that this can be increased further by having the distorted private key be dependent on 2 or more captchas to further increase the number of bytes to test.
Once the correct byte value for each of the unknown elements of the private key is found this will produce the captcha address, which is stored in the protocol.
The miner can then use the private key to show their proof of human-work and contribute towards signing a block. This can be verified by other miners as the captcha addresses are known by everyone. Once used to sign a block, the captcha's address is removed from the protocol and cannot be used again.