বিটকয়েন স্বার্থপর মাইনিং এবং ডাইক শব্দ: একটি কম্বিনেটোরিয়াল প্রমাণ

সূচিপত্র

1. ভূমিকা

স্বার্থপর মাইনিং (এসএম) হল বিটকয়েনে একটি ব্লক আটকে রাখার কৌশল যা প্রোটোকলের কঠোরতা সমন্বয় প্রক্রিয়ার একটি ত্রুটির সুযোগ নেয়। সৎ খননকারীরা সর্বদা সর্বজনীন দীর্ঘতম শৃঙ্খলকে প্রসারিত করে, কিন্তু একজন স্বার্থপর খননকারী আয় সর্বাধিক করার কৌশলে নতুন খননকৃত ব্লকগুলি গোপনে রেখে একটি গোপন ফর্ক তৈরি করে এবং সেগুলি কৌশলগতভাবে প্রকাশ করে। এই ধরনের কৌশল মূল্যায়নের মূল মেট্রিক হল দীর্ঘমেয়াদী আপাত হ্যাশরেট $\tilde{q}$, যা সময়ের সাথে সাথে সরকারী ব্লকচেইনে আক্রমণকারীর অবদানকৃত ব্লকের ভগ্নাংশকে উপস্থাপন করে।

পূর্ববর্তী বিশ্লেষণগুলি জটিল মার্কভ চেইন বা মার্টিংগেল কৌশলের উপর নির্ভর করত। এই গবেষণাটি ডাইক শব্দ এবং ক্যাটালান সংখ্যা ব্যবহার করে একটি সরল কম্বিনেটোরিয়াল প্রমাণ উপস্থাপন করে, যা উদ্ভাবনকে আরও সহজগম্য এবং মার্জিত করে তোলে।

2. আক্রমণ চক্র এবং ডাইক শব্দ

একটি আক্রমণ চক্রকে ঘটনাগুলির একটি ক্রম হিসাবে মডেল করা যেতে পারে যেখানে প্রতিটি ব্লক হয় স্বার্থপর খননকারী (এস) অথবা সৎ খননকারীরা (এইচ) দ্বারা খনন করা হয়।

2.1. ক্রমের উপস্থাপনা

উদাহরণ: SSSHSHH ক্রমটি নির্দেশ করে যে স্বার্থপর খননকারী তিনটি ব্লক খনন করে, তারপর সৎ খননকারীরা একটি খনন করে, তারপর স্বার্থপর খননকারী একটি, তারপর সৎ খননকারীরা দুটি। চক্রটি শেষ হয় যখন স্বার্থপর খননকারীর অগ্রগতি হ্রাস পায়, যা তাকে তার ফর্ক প্রকাশ করতে প্ররোচিত করে।

2.2. L-এর বিন্যাস

ধরা যাক $L$ হল প্রতি আক্রমণ চক্রে সরকারী ব্লকচেইনে যোগ হওয়া ব্লকের সংখ্যা।

উপপাদ্য 2.2: $P[L=1] = p$, $P[L=2] = pq + pq^2$, এবং $n \geq 3$ এর জন্য, $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$ যেখানে $C_n = \frac{(2n)!}{n!(n+1)!}$ হল $n$-তম ক্যাটালান সংখ্যা।

প্রমাণের রূপরেখা: $n \geq 3$ এর জন্য, ঘটনা ${L=n}$ সেই ক্রমগুলির সাথে সঙ্গতিপূর্ণ যা SS দিয়ে শুরু হয়, H দিয়ে শেষ হয় এবং যেখানে মধ্যবর্তী অংশ, এস→"(" এবং এইচ→")" ম্যাপিং করার সময়, দৈর্ঘ্য $2(n-2)$ এর একটি ডাইক শব্দ (একটি ভারসাম্যপূর্ণ বন্ধনী স্ট্রিং) গঠন করে। ক্যাটালান সংখ্যা $C_{n-2}$ এই ধরনের ডাইক শব্দ গণনা করে।

3. মূল গাণিতিক ফলাফল

3.1. L-এর প্রত্যাশিত মান

সিদ্ধান্ত 2.3: $E[L] = 1 + \frac{p^2 q}{p - q}$.

এটি ক্যাটালান সংখ্যার জন্য পরিচিত জেনারেটিং ফাংশন সম্পর্ক থেকে অনুসরণ করে।

3.2. আপাত হ্যাশরেট সূত্র

ধরা যাক $Z$ হল প্রতি চক্রে আক্রমণকারী সরকারী শৃঙ্খলে যোগ করা ব্লকের সংখ্যা। দীর্ঘমেয়াদী আপাত হ্যাশরেট হল $\tilde{q} = E[Z] / E[L]$।

উপপাদ্য 2.4: বিটকয়েনের জন্য আপাত হ্যাশরেট হল: $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ যেখানে $p$ হল সৎ খননকারীদের হ্যাশরেট, $q$ হল আক্রমণকারীর হ্যাশরেট ($p+q=1$, $q<1/2$), এবং $\gamma$ হল ফর্ক চলাকালীন আক্রমণকারীর ব্লকে খননকারী সৎ খননকারীদের ভগ্নাংশ।

4. প্রযুক্তিগত বিশ্লেষণ ও কাঠামো

4.1. গাণিতিক কাঠামো

মূল উদ্ভাবন হল আক্রমণ ক্রমগুলিকে ডাইক পাথ (ভারসাম্যপূর্ণ বন্ধনী স্ট্রিং) এ ম্যাপ করা। এটি স্বার্থপর মাইনিংকে সুপ্রতিষ্ঠিত কম্বিনেটোরিক্সের সাথে সংযুক্ত করে, পূর্বে স্টোকাস্টিক প্রক্রিয়া প্রয়োজন এমন সম্ভাব্যতা গণনাকে সরল করে।

মূল সূত্র: $n\geq3$ এর জন্য সম্ভাব্যতা $P[L=n]$ সরাসরি ক্যাটালান সংখ্যা $C_{n-2}$ এর সমানুপাতিক, যা সম্ভাব্যতা ওজন $p$ এবং $q$ দ্বারা স্কেল করা: $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$।

4.2. বিশ্লেষণাত্মক কাঠামোর উদাহরণ

L=4 এর জন্য কেস বিশ্লেষণ:

1. ক্রমটি অবশ্যই SS দিয়ে শুরু এবং H দিয়ে শেষ হতে হবে।
2. মধ্যবর্তী দুটি অবস্থানে অবশ্যই দৈর্ঘ্য 2 এর একটি ডাইক শব্দ গঠন করতে হবে: শুধুমাত্র SH বা HS? আসুন পরীক্ষা করি: L=4 এর জন্য, n=4, তাই n-2=2। আমাদের মধ্যবর্তী অংশে 2*(2)=4 অক্ষরের একটি ডাইক শব্দ প্রয়োজন? অপেক্ষা করুন, সতর্কতা: উপপাদ্যটি বলে n≥3 এর জন্য, P[L=n] w = SS X1...X_{2(n-2)} H ফর্মের ক্রমগুলির সাথে সঙ্গতিপূর্ণ, যেখানে X-গুলি দৈর্ঘ্য 2(n-2) এর একটি ডাইক শব্দ গঠন করে। n=4 এর জন্য, দৈর্ঘ্য হল 2*(4-2)=4। সুতরাং মধ্যবর্তী অংশে 4টি অক্ষর রয়েছে যা একটি ডাইক শব্দ গঠন করে। উদাহরণ: SS(SHSH)H? এস→(, এইচ→) ম্যাপিং। মধ্যবর্তী "SHSH" হয়ে যায় "()()", যা একটি ডাইক শব্দ। সম্ভাব্যতা ওজন হল p^{#S} q^{#H} = p^3 q^3? আসুন w=SS S H S H H-তে S এবং H গণনা করি: S 4 বার উপস্থিত? প্রকৃতপক্ষে: SS S H S H H: অবস্থান: S,S,S,H,S,H,H। এটি হল 4টি S এবং 3টি H। সুতরাং p^4 q^3। সূত্রটি দেয় p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4। একটি অসঙ্গতি আছে। পিডিএফ বলে "w-তে 'S' (যথাক্রমে 'H') অক্ষরের সংখ্যা হল n (যথাক্রমে n-1)। সুতরাং, আমরা পাই P[L=n] = p^{n-1} q^n C_{n-2}"। n=4 এর জন্য, এটি হল p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4। এটি সূত্রের সাথে মেলে। সুতরাং উদাহরণ ক্রম SS S H S H H-তে 4টি S এবং 3টি H রয়েছে, যা p^4 q^3, p^3 q^4 নয়। সুতরাং SS S H S H H ডাইক শব্দ শর্তের অধীনে L=4 এর জন্য একটি বৈধ ক্রম নয়? এটি ভারসাম্যপূর্ণ নাও হতে পারে। আসুন ম্যাপ করি: S→(, H→)। SS S H S H H হয়ে যায় ((( ) ( ) )। এটি ভারসাম্যপূর্ণ নয় (তিনটি খোলা, দুটি বন্ধ)। সুতরাং প্রকৃতপক্ষে, বৈধ ক্রমগুলি হল যেখানে মোট S গণনা n এবং H গণনা n-1, এবং মধ্যবর্তী অংশ একটি ডাইক শব্দ। ডাইক শর্ত ভারসাম্য প্রয়োগ করে, নির্দিষ্ট গণনার দিকে নিয়ে যায়। সুতরাং কাঠামোটি সুন্দরভাবে বৈধ আক্রমণ পথগুলি ধারণ করে।

এই কাঠামোটি মার্কভ চেইন সিমুলেট না করেই পদ্ধতিগত গণনা এবং সম্ভাব্যতা গণনা করার অনুমতি দেয়।

5. ফলাফল ও প্রভাব

$\tilde{q}_B$ এর জন্য উদ্ভূত সূত্রটি স্বার্থপর মাইনিংয়ের জন্য লাভের সীমা পরিমাপ করে। উদাহরণস্বরূপ, $\gamma=0$ সহ, আক্রমণকারীর লাভের জন্য $q > \approx 0.25$ প্রয়োজন, যা সরল $q>0.5$ ধারণার চেয়ে কম। এটি একটি গুরুত্বপূর্ণ প্রোটোকল দুর্বলতা তুলে ধরে।

চার্ট বর্ণনা: বিভিন্ন $\gamma$ মানের জন্য $\tilde{q}_B$ বনাম $q$ এর একটি প্লট দেখাবে: 1) একটি সীমার উপরে $q$ এর জন্য $\tilde{q}_B > q$, যা লাভজনকতা নির্দেশ করে। 2) উচ্চতর $\gamma$ (আক্রমণকারীর জন্য ভাল সংযোগ) লাভজনকতার সীমা কমায় এবং আপাত হ্যাশরেট লাভ বৃদ্ধি করে।

6. শিল্প বিশ্লেষকের দৃষ্টিভঙ্গি

মূল অন্তর্দৃষ্টি: কাগজটির মার্জিততা হল এটি একটি জটিল, স্টেটফুল আক্রমণকে একটি পরিষ্কার কম্বিনেটোরিয়াল মডেলে হ্রাস করে। এটি প্রকাশ করে যে স্বার্থপর মাইনিংয়ের লাভজনকতা কেবল কাঁচা হ্যাশরেট সম্পর্কে নয়, বরং আক্রমণ ক্রম এবং ক্যানোনিকাল কম্বিনেটোরিয়াল অবজেক্ট (ডাইক শব্দ) এর মধ্যে গঠনমূলক যুগল সম্পর্কে। এটি কেবল একটি গণিতের কৌশল নয়; এটি বিটকয়েন প্রোটোকলের দুর্বলতাকে একটি ফর্মাল ল্যাঙ্গুয়েজ সমস্যা হিসাবে প্রকাশ করে—এর নিরাপত্তা ব্লক রেসে নির্দিষ্ট স্ট্রিং প্যাটার্নের সম্ভাব্যতা বন্টনের উপর নির্ভর করে।

যুক্তিসঙ্গত প্রবাহ: লেখকরা আক্রমণ চক্রকে একটি স্ট্রিং (এস/এইচ ক্রম) হিসাবে ফ্রেম করে শুরু করেন। মূল পদক্ষেপ হল এই স্বীকৃতি যে সফল আক্রমণগুলি (যেখানে আক্রমণকারীর সমস্ত ব্লক গৃহীত হয়) সেই স্ট্রিংগুলির সাথে সঙ্গতিপূর্ণ যা মূলত নির্দিষ্ট স্টার্টার/ফিনিশার দ্বারা বন্ধনীকৃত ডাইক শব্দ। এটি তাদেরকে একটি মার্কভ চেইনের জন্য ভারসাম্য সমীকরণ সমাধানের প্রয়োজন ছাড়াই গণনা এবং সম্ভাব্যতা উৎপাদনের জন্য ক্যাটালান কম্বিনেটোরিক্সের বিশাল যন্ত্রপাতিতে সরাসরি ট্যাপ করার অনুমতি দেয়। চূড়ান্ত সূত্রটি L-এর প্রত্যাশিত মান (ক্যাটালান জেনারেটিং ফাংশনের মাধ্যমে) এবং Z-এর প্রত্যাশিত মান (L=1,2 এর মতো প্রান্তিক ক্ষেত্র বিবেচনা করে) সংযোগ করে উদ্ভূত হয়।

শক্তি ও ত্রুটি:
শক্তি: প্রমাণটি উল্লেখযোগ্যভাবে সংক্ষিপ্ত এবং সহজগম্য। এটি স্বার্থপর মাইনিং রাজস্ব সূত্রকে রহস্যমুক্ত করে। ডাইক শব্দের সাথে সংযোগ ফর্মাল ল্যাঙ্গুয়েজ তত্ত্ব ব্যবহার করে অন্যান্য ব্লকচেইন আক্রমণ (যেমন, ব্যালেন্সিং আক্রমণ, এক্লিপস আক্রমণ) এর নতুন বিশ্লেষণকে অনুপ্রাণিত করতে পারে। এটি আন্তঃশাস্ত্রীয় পদ্ধতির (ক্রিপ্টো + কম্বিনেটোরিক্স) মূল্যকে শক্তিশালী করে।
ত্রুটি: মডেলটি একটি স্থির, স্থায়ী আক্রমণকারীকে ধরে নেয় যার ধ্রুবক q রয়েছে। এটি গতিশীল অভিযোজন, খননকারীর প্রবেশ/প্রস্থান, বা একাধিক স্বার্থপর খননকারীর প্রভাব (একটি সম্ভাব্য অলিগোপলি সমস্যা) ধারণ করে না। $\gamma$ প্যারামিটারটি সরলীকৃত; বাস্তব-বিশ্বের নেটওয়ার্ক টপোলজি এবং প্রচার বিলম্ব আরও জটিল। "অপটিমাল সেলফিশ মাইনিং স্ট্র্যাটেজিজ ইন বিটকয়েন" (জার্ভাইস এট আল., ফাইন্যানশিয়াল ক্রিপ্টো ২০১৬) এর মতো অনুসরণ গবেষণায় উল্লিখিত হিসাবে, মূল স্বার্থপর মাইনিং কৌশল সর্বদা সর্বোত্তম নয়; আরও অভিযোজিত কৌশল বিদ্যমান। এই কাগজের অবদান হল মৌলিক, সম্পূর্ণ নয়।

কার্যকরী অন্তর্দৃষ্টি:

1. প্রোটোকল ডিজাইনারদের জন্য: মূল কারণ হল "প্রথম-দেখা" নিয়ম এবং ধীর ব্লক প্রচার। জার্ভাইসের "ফ্রেশনেস প্রেফার্ড" বা ডেকার এবং ওয়াটেনহোফারের "কম্প্যাক্ট ব্লক রিলে" (বিটকয়েন কোর-এ মোতায়েন করা হিসাবে) এর মতো সমাধানগুলি $\gamma$ এবং প্রচার বৈচিত্র্য কমাতে লক্ষ্য করে। এই কাগজের সূত্রটি এই ধরনের সংশোধন পরীক্ষা করার জন্য একটি পরিমাপযোগ্য মেট্রিক প্রদান করে।
2. মাইনিং পুলগুলির জন্য: সীমা গণনা ($q$ ~0.25) একটি লাল রেখা। এই আকারের কাছাকাছি পুলগুলিকে যাচাই করা উচিত। বিকেন্দ্রীকরণ কেবল আদর্শিক নয়; এটি $\tilde{q}$ সূত্রে একটি নিরাপত্তা প্যারামিটার।
3. বিশ্লেষকদের জন্য: ডাইক শব্দ ম্যাপিং একটি শক্তিশালী টেমপ্লেট। অন্যান্য কনসেনসাস মেকানিজম সন্ধান করুন যেখানে অংশগ্রহণকারীদের ক্রিয়াগুলি ফর্মাল ল্যাঙ্গুয়েজ ক্লাস (নিয়মিত, কনটেক্সট-ফ্রি) দ্বারা বিশ্লেষণযোগ্য ক্রম তৈরি করে। প্রুফ-অফ-স্টেক সিস্টেমগুলি, তাদের স্পষ্ট ভোটিং ক্রম সহ, অনুরূপ বিশ্লেষণের জন্য প্রস্তুত হতে পারে।

সারসংক্ষেপ: ব্লকচেইন নিরাপত্তা ক্রমবর্ধমানভাবে প্রয়োগিত গণিতবিদ এবং ভাষাবিদদের জন্য একটি ক্ষেত্র, কেবল ক্রিপ্টোগ্রাফারদের জন্য নয়। এই কাগজটি সেই পরিবর্তনের একটি প্রধান উদাহরণ।

7. ভবিষ্যতের প্রয়োগ ও দিকনির্দেশনা

1. বর্ধিত আক্রমণ মডেল: ডাইক শব্দ কাঠামোটি জেদি মাইনিং বা ট্রেইল মাইনিং বৈকল্পিক বিশ্লেষণ করতে অভিযোজিত হতে পারে, যেখানে আক্রমণকারীর প্রকাশ কৌশল ভিন্ন।

2. অন্যান্য কনসেনসাস প্রোটোকল: অনুরূপ কম্বিনেটোরিয়াল পদ্ধতিগুলি প্রুফ-অফ-স্টেক (যেমন, ইথেরিয়ামের ক্যাস্পার) বা ডিএজি-ভিত্তিক প্রোটোকল (যেমন, আইওটিএ, অ্যাভালাঞ্চ) এ প্রয়োগ করা তাদের আটকে রাখা আক্রমণের বিরুদ্ধে স্থিতিস্থাপকতা সম্পর্কে নতুন অন্তর্দৃষ্টি দিতে পারে।

3. স্বয়ংক্রিয় নিরাপত্তা যাচাইকরণ: একটি কনসেনসাস প্রোটোকলের নিয়মগুলিকে স্বয়ংক্রিয়ভাবে একটি ফর্মাল গ্রামারে অনুবাদ করার এবং এখানে পাওয়া ডাইক কাঠামোর অনুরূপ "লাভজনক আক্রমণ ব্যাকরণ" এর অস্তিত্ব পরীক্ষা করার জন্য সরঞ্জামগুলি তৈরি করা যেতে পারে।

4. নেটওয়ার্ক গতিবিদ্যা সংহতকরণ: ভবিষ্যতের কাজটি আরও বাস্তবসম্মত নেটওয়ার্ক মডেল (যেমন, ব্লক প্রচারের জন্য মহামারী মডেল ব্যবহার) কে কম্বিনেটোরিয়াল সম্ভাব্যতা ওজনে অন্তর্ভুক্ত করতে পারে, সরল $\gamma$ প্যারামিটারের বাইরে যাওয়া।

8. তথ্যসূত্র

1. Eyal, I., & Sirer, E. G. (2014). Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security (pp. 436-454). Springer.
2. Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.
3. Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system.
4. Grunspan, C., & Pérez-Marco, R. (2018). On profitability of selfish mining. arXiv preprint arXiv:1805.08281.
5. Gervais, A., Karame, G. O., Wüst, K., Glykantzis, V., Ritzdorf, H., & Capkun, S. (2016). On the security and performance of proof of work blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (pp. 3-16).
6. Bitcoin Wiki. Difficulty. https://en.bitcoin.it/wiki/Difficulty.
7. Decker, C., & Wattenhofer, R. (2013). Information propagation in the Bitcoin network. In IEEE P2P 2013 Proceedings (pp. 1-10). IEEE.