एल्गोरिदम जो चलाने के लिए समय लगता है लेकिन सत्यापित करने में आसान है?

Question

मैं प्रयोग के लिए एक वेबसाइट तैयार कर रहा हूं, वहां एक बटन होगा जो उपयोगकर्ता थोड़ी देर के लिए क्लिक करके रखें, फिर रिलीज़ करें, फिर क्लाइंट सर्वर पर AJAX ईवेंट सबमिट करता है।

हालांकि, ऑटोक्लिक बॉट्स और तेज़ स्पैम से रोकने के लिए, मैं चाहता हूं कि होल्ड टाइम बहुत वास्तविक हो और छोड़ने योग्य न हो, उदा। कुछ गणना कर रही है। बिंदु वास्तविक CPU समय को बर्बाद करना है, ताकि आप केवल AJAX कॉलबैक मान का अनुमान लगा सकें या इसे बाईपास करने के लिए तेज़ सिस्टम घड़ी को चालू न कर सकें।

कोई एल्गोरिथ्म है कि

1. तेजी & आसान एक सर्वर
2. पर एक चुनौती उत्पन्न करने के लिए कुछ समय के लिए, ग्राहक पक्ष पर अमल नहीं हंसोड़ या समय शॉर्टकट के लिए खर्च कर रहे हैं।
3. आसान & प्रतिक्रिया सत्यापित करने के लिए तेज़ी से सर्वर पर परिणाम?

Answer 1

आप Proof-of-work system खोज रहे हैं।

सबसे लोकप्रिय एल्गोरिदम Hashcash (Wikipedia पर भी) लगता है, जिसका उपयोग बिटकॉइन के लिए अन्य चीजों के साथ किया जाता है। बुनियादी विचार क्लाइंट प्रोग्राम से हैश को एक निश्चित संख्या में अग्रणी शून्य के साथ ढूंढना है, जो एक समस्या है जिसे उन्हें ब्रूट फोर्स के साथ हल करना है।

असल में, यह इस तरह काम करता है: क्लाइंट के पास कुछ प्रकार का टोकन है। ईमेल के लिए, यह आमतौर पर प्राप्तकर्ता का ईमेल पता और आज की तारीख है। तो यह ऐसा दिखाई दे सकता:

bob@example.com:04102011 

ग्राहक अब इस के सामने डाल करने के लिए एक यादृच्छिक स्ट्रिंग को खोजने के लिए है:

asdlkfjasdlbob@example.com:04202011 

ऐसी है कि इस बात का हैश प्रमुख 0s का एक समूह है। (मेरा उदाहरण काम नहीं करेगा क्योंकि मैंने अभी एक संख्या बनाई है।)

फिर, आपके पक्ष में, आपको बस इस यादृच्छिक इनपुट को लेना होगा और यह जांचने के लिए एकल हैश चलाएं, यह जांचने के लिए कि क्या यह शुरू होता है 0s का एक गुच्छा। यह बहुत तेज ऑपरेशन है।

कारण क्लाइंट सही हैश ढूंढने पर उचित मात्रा में CPU समय व्यतीत करना है कि यह एक क्रूर-बल समस्या है। केवल एक ही जानना है कि यह एक यादृच्छिक स्ट्रिंग चुनना है, इसका परीक्षण करना है, और यदि यह काम नहीं करता है, तो दूसरा चुनें।

बेशक, चूंकि आप ईमेल नहीं कर रहे हैं, तो आप शायद ईमेल पते और तारीख के बजाय किसी प्रकार के एक अलग टोकन का उपयोग करना चाहेंगे। हालांकि, आपके मामले में, यह आसान है: आप केवल एक यादृच्छिक स्ट्रिंग सर्वर-साइड बना सकते हैं और इसे क्लाइंट को पास कर सकते हैं।

इस विशेष एल्गोरिदम का एक लाभ यह है कि कठिनाई को समायोजित करना बहुत आसान है: बस बदलें कि आप कितने प्रमुख शून्य चाहते हैं। आपको जितनी अधिक ज़ीरो चाहिए, उतना ही वह ग्राहक ले जाएगा; हालांकि, सत्यापन अभी भी आपके अंत में एक ही समय लेता है।