Алгоритм, который требует времени для запуска, но его легко проверить?

Question

Я создаю веб-сайт для эксперимента, появится кнопка, которую пользователь должен щелкнуть и удерживать некоторое время, затем отпустить, затем клиент отправит событие AJAX на сервер.

Однако, чтобы избежать ботов автоклика и быстрого спама, я хочу, чтобы время удержания было очень реальным и не пропускало, например. делая некоторые вычисления. Дело в том, чтобы тратить фактическое время процессора, так что вы не можете просто угадать значение обратного вызова AJAX или ускорить работу системных часов, чтобы обойти его.

Есть ли алгоритм, который

1. быстро & легко генерировать вызов на сервере
2. стоит некоторое время, чтобы выполнить на стороне клиента, не пародия или ярлык времени.
3. легко & быстро проверить ответ результат на сервере?

Answer 1

Вы ищете Proof-of-work system.

Самый популярный алгоритм, как представляется, Hashcash (также на Wikipedia), который используется, в частности, для биткойнов. Основная идея заключается в том, чтобы попросить клиентскую программу найти хэш с определенным количеством ведущих нулей, что является проблемой, которую они должны решить с помощью грубой силы.

В принципе, он работает следующим образом: у клиента есть своего рода токен. Для электронной почты это обычно адрес электронной почты получателя и сегодняшняя дата. Так может выглядеть следующим образом:

bob@example.com:04102011 

Теперь клиент должен найти случайную строку, чтобы поставить перед этим:

asdlkfjasdlbob@example.com:04202011 

таким образом, что хэш это имеет кучу ведущих 0s. (Мой пример не будет работать, потому что я только что составил номер.)

Затем, на вашей стороне, вам просто нужно взять этот случайный ввод и занести сингл, чтобы проверить, начинается ли он с куча 0s. Это очень быстро работает .

Причина, по которой клиент должен потратить значительное количество процессорного времени на поиск правильного хеша, заключается в том, что это проблема грубой силы. Единственное, что нужно знать, это выбрать случайную строку, проверить ее, и если она не работает, выберите другую.

Конечно, поскольку вы не занимаетесь электронной почтой, вы, вероятно, захотите использовать другой токен какого-то типа, а не адрес электронной почты и дату. Однако в вашем случае это легко: вы можете просто создать случайную строку на стороне сервера и передать ее клиенту.

Одним из преимуществ данного конкретного алгоритма является то, что очень легко настроить сложность: просто измените количество нужных нулей. Чем больше нулей вам нужно, тем дольше это займет клиент; тем не менее, проверка по-прежнему занимает столько же времени на вашем конце.