Loading...
السلسلة: Zcash from First Principles . المقال 1 . الحقول المنتهية الجمهور: المبتدئون. نفترض فقط الحساب المدرسي العادي (الجمع، الضرب، القسمة). لا حاجة إلى معرفة مسبقة بالتشفير أو بالرياضيات العليا. ما ستخرج به: فهم حدسي وصحيح للحقول المنتهية، ولماذا يستخدمها علماء التشفير، وأين تظهر داخل Zcash.
في المقال 0 تعرّفنا إلى خمس شخصيات: الملاحظة، والالتزام، وشجرة التزامات الملاحظات، والمُبطِل، وبرهان انعدام المعرفة. وتركنا سؤالًا مفتوحًا معلّقًا: من أين تأتي فعليًا كل المفاتيح والوصفات السرية؟ إنها تأتي من الأعداد. ولكن ليس من الأعداد العادية التي نشأت عليها. بل تأتي من نظام أعداد خاص ومكتفٍ بذاته يُسمّى حقلًا منتهيًا، ويكاد كل جزء من التشفير في Zcash يكون مبنيًا فوقه.
هذا المقال يرسّخ هذه الفكرة بالتدرج. وكما وعدنا، الحدس أولًا. لا صيغ حتى تستحق وجودها.
الأعداد العادية لديها مشكلة بالنسبة إلى التشفير: فهي لا نهائية، وتسرّب المعلومات.
فكّر فيما يحدث عندما يصبح العدد أكبر. إذا أخبرتك أن عملية حسابية سرية أنتجت 8,142,067، فأنت تعرف بالفعل كثيرًا: إنه عدد مكوّن من سبعة أرقام، وهو فردي، وهو "كبير إلى حد ما". الحجم قرينة. والقرائن هي بالضبط ما لا يستطيع نظام الخصوصية تحمّل كشفه.
يريد التشفير نظام أعداد بحيث:
لهذه القائمة الأمنية اسم. إنها حقل منتهٍ. دعنا نبني الحدس له قبل أن نكتب رمزًا واحدًا.
أنت تستخدم حقلًا منتهيًا كل يوم بالفعل. إنها الساعة على جدارك.
على ساعة بنظام 12 ساعة، الأعداد تلتف. ابدأ من الساعة العاشرة، وأضف 5 ساعات، فلن تصل إلى "الساعة الخامسة عشرة"، بل ستصل إلى الساعة الثالثة. الساعة لا تملك إلا اثني عشر موضعًا، والعد بعد القمة يعيدك ببساطة إلى البداية.
لقد حدثت للتو ثلاثة أمور هي جوهر هذا المقال كله:
هذا الحساب القائم على الالتفاف له اسم رسمي: الحساب المعياري. تعمل الساعة "بترديد 12"، ويُكتب ذلك mod 12. يفضّل الرياضيون عدّ المواضع بدءًا من 0، لذا فإن "ساعة mod 12" تحتوي فعليًا على المواضع 0, 1, 2, ..., 11. أما الساعة mod 7 فستحتوي على المواضع من 0 إلى 6.
القاعدة الوحيدة: لحساب أي شيء "mod p"، أجرِ الحساب العادي، ثم اقسم على
pواحتفظ بالباقي فقط. مثال mod 7:5 + 4 = 9، و9يترك باقيًا مقداره2بعد القسمة على7، إذن5 + 4 = 2 (mod 7).
الساعة تسمح لنا بالجمع. أما الحقل فهو الترقية: نظام أعداد تعمل فيه العمليات الأربع كلها، بما فيها العملية الأصعب، وهي القسمة.
بصورة غير رسمية، الحقل هو أي مجموعة من "الأعداد" يمكنك فيها الجمع والطرح والضرب والقسمة (على أي شيء عدا الصفر)، مع بقاء كل القواعد المألوفة صحيحة: لا يهم الترتيب في الجمع أو الضرب، ويمكن إعادة تجميع الأقواس، وهناك 0 و1، ولكل عدد سالب، ولكل عدد (عدا 0) مقلوب.
الأعداد النسبية حقل. والأعداد الحقيقية حقل. وما نريده نحن هو حقل منتهٍ.
إليك النتيجة الأساسية، وهي جميلة:
خذ الأعداد الصحيحة
0, 1, ..., p-1وأجرِ كل الحسابات modp. إذا كانpعددًا أوليًا، فالنتيجة تكون حقلًا منتهيًا. ونكتب ذلكF_p(وتُقرأ "F تحتية p").
إذن F_7 = {0, 1, 2, 3, 4, 5, 6} مع حساب على طريقة الساعة بترديد 7 هو فعلًا حقل منتهٍ حقيقي. دعنا نراه ينبض.
كل خانة هي (row x column) mod 7:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 0 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 0 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 0 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 0 | 5 | 3 | 1 | 6 |
انظر إلى الصفوف الخاصة بـ 1 حتى 6: كل واحد منها يحتوي كل قيمة غير صفرية من 1..6 مرة واحدة بالضبط. هذا النمط، "لا تكرار ولا نقص"، هو البصمة المرئية للحقل.
القسمة ليست إلا "الضرب في المقلوب". في F_7، مقلوب (أو معكوس) العدد a هو القيمة a^(-1) التي تحقق a x a^(-1) = 1. ويمكن قراءتها مباشرة من الجدول:
a | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
a⁻¹ | 1 | 4 | 5 | 2 | 3 | 6 |
تحقق من واحدة: 2 x 4 = 8 = 1 (mod 7). إذن "القسمة على 2" في F_7 تعني "الضرب في 4". لكل عنصر غير صفري شريك. وهذا هو ما يجعل F_7 حقلًا.
هذه هي الفكرة الأهم في المقال، لذا فلنجعلها ملموسة بدلًا من أن تكون مجردة.
راقب ما الذي ينكسر إذا حاولنا بسذاجة بناء "حقل" mod 6 (و6 ليس عددًا أوليًا):
هل توجد أي قيمة
xتحقق2 x x = 1 (mod 6)؟ إذا فحصناها كلها:2x0=0, 2x1=2, 2x2=4, 2x3=0, 2x4=2, 2x5=4. القيمة1لا تظهر أبدًا. إذن ليس لـ2مقلوب mod 6. والأسوأ من ذلك أن2 x 3 = 6 = 0 (mod 6): عددان غير صفريين ضُربا فأنتجا صفرًا.
هذه الجملة الثانية كارثة بالنسبة إلى الحساب. وجود شيئين غير صفريين يضربان فيعطيان صفرًا (ويُسمّى ذلك قسّامًا صفريًا) يعني أن القسمة معطوبة، والنظام الذي تتعطل فيه القسمة ليس حقلًا. ويحدث ذلك تحديدًا لأن 6 تتحلل إلى 2 x 3.
أما العدد الأولي، فبحكم التعريف، لا يملك مثل هذه العوامل. لذلك، عند العمل mod عدد أولي، لا يمكن أن تظهر قواسم صفرية، ويحصل كل عنصر غير صفري على مقلوب نظيف، وتصبح البنية حقلًا صحيحًا.
جملة موجزة قابلة لإعادة الاستخدام لمقالاتك: إذا كان المقياس أوليًا، خرجت القسمة سليمة.
قرأنا المقلوبات من جدول في F_7، لكن أولي Zcash يضم مئات الأرقام؛ ولا يمكن إنشاء جدول له. توجد حيلة كلاسيكية، وهي الصيغة الوحيدة في هذا المقال.
مبرهنة Fermat الصغرى تقول إنه إذا كان p أوليًا وكان a غير صفري، فإن:
a^(p-1) = 1 (mod p)
أعد ترتيبها (انزع عاملًا واحدًا من a) فتحصل على المقلوب مجانًا:
a^(-1) = a^(p-2) (mod p)
اختبر ذلك في F_7 (p = 7، لذا p - 2 = 5): ينبغي أن يكون مقلوب 2 هو 2^5 = 32 = 4 (mod 7). وبالفعل قال جدولنا إن 2^(-1) = 4. تستطيع الحواسيب الرفع إلى قوى كبيرة بسرعة شديدة، لذا يحوّل هذا "إيجاد المقلوب" إلى عملية حسابية سريعة ودقيقة حتى مع الأعداد الأولية الضخمة جدًا.
لا تحتاج إلى حفظ هذا. ما تحتاج إلى معرفته هو أن القسمة في الحقل المنتهي عملية سريعة ودقيقة، وهذا هو بالضبط سبب سعادة علماء التشفير في البناء فوقها.
إذا جمعنا هذا الحدس كله معًا، فإليك القضية كاملة في صفحة واحدة.
خاصية F_p | لماذا يريدها نظام خصوصية |
|---|---|
| منتهٍ | يستطيع الحاسوب تخزين أي عنصر بدقة تامة؛ بلا تقريب، وبلا تجاوز، وبلا ضبابية الفاصلة العائمة |
| الالتفاف | يمحو "الحجم"، لذلك لا تسرّب القيمة شيئًا عن كيفية إنتاجها |
| العمليات الأربع كلها تعمل | الوصفات التشفيرية (المفاتيح، والالتزامات، والبراهين) تحتاج إلى جبر حقيقي، لا مجرد عد |
| حجم قابل للاختيار | اختر عددًا أوليًا بطول 255 بت أو 381 بت، وسيصبح للحقل عناصر أكثر من عدد الذرات في الكون المرصود؛ ويصبح التخمين ميؤوسًا منه |
| دقيق وحتمي | إذا حسب طرفان صادقان الشيء نفسه فسيحصلان دائمًا على نتائج متطابقة، وهو ما تعتمد عليه البراهين |
الحقل المنتهي، في عبارة واحدة، هو ساحة لعب مغلقة تمامًا، دقيقة تمامًا، وهائلة تمامًا للحساب. وكل شيء آخر في Zcash يُبنى باللعب داخله.
لا يلزمك أن تأخذ عبارة "Zcash يستخدم الحقول المنتهية" على سبيل الإيمان. إليك الخريطة الملموسة (أما الآلية الأعمق فسنؤجلها إلى مقالات لاحقة؛ الغرض هنا فقط إظهار أن البصمات حقيقية).
إذن فالإجابة عن السؤال المفتوح في المقال 0، "من أين تأتي الوصفات السرية؟"، تبدأ هنا: كل شيء يبدأ كحساب داخل حقل منتهٍ. في المقال القادم سنأخذ هذا الحقل ونبني منه الكائنات الفعلية، أي النقاط على منحنى إهليلجي، التي تصبح مفاتيح والتزامات.
حتى يبقى النص مناسبًا للمبتدئين، قمنا بتبسيط بعض الأمور الصحيحة. فالحقول المنتهية لا تأتي فقط بصيغة F_p؛ بل يمكنك أيضًا بناء حقول فيها p^n عنصرًا (وتُسمّى حقول الامتداد)، وهذه مهمة من أجل "الاقترانات" التي يعتمد عليها نظام البراهين في Sapling. كما أننا تجاوزنا القائمة الكاملة لمسلمات الحقل، ولم نتوسع في كيفية اختيار الأعداد الأولية بهذه الأحجام والتحقق منها. لا شيء من ذلك يغيّر الحدس الذي تملكه الآن؛ بل يضيف إليه مزيدًا من الضبط. وسنعيد هذه الدقة لاحقًا، مع إشارات واضحة، عندما يحتاجها مقال تالٍ.
0..p-1 mod عدد أولي p يعطي حقلًا حقيقيًا F_p، يمكنك فيه أيضًا القسمة لأن لكل عنصر غير صفري معكوسًا.2 x 3 = 0 mod 6) ويكسر القسمة.a^(-1) = a^(p-2)).| المصطلح | المعنى المبسّط |
|---|---|
| Modular arithmetic | حساب يلتف بعد الوصول إلى قيمة ثابتة، مثل الساعة |
| mod p | "اقسم على p واحتفظ بالباقي" |
| Field | نظام أعداد تعمل فيه عمليات الجمع والطرح والضرب والقسمة كلها |
Finite field F_p | الأعداد 0..p-1 مع إجراء الحساب mod عدد أولي p |
| Inverse (reciprocal) | العنصر a^(-1) الذي يحقق a x a^(-1) = 1; و"القسمة على a" تعني الضرب فيه |
| Zero divisor | قيمتان غير صفريتين حاصل ضربهما صفر؛ وهو الشيء الذي يفسد المقاييس المركبة |
| Prime | عدد صحيح أكبر من 1 لا عوامل له إلا 1 ونفسه |
لماذا لا نستخدم الأعداد الصحيحة العادية أو الأعداد العشرية؟ الأعداد العشرية تُقرّب وتنحرف؛ والأعداد الصحيحة تنمو بلا حد وتسرّب الحجم. أما الحقول المنتهية فهي دقيقة، ومحدودة، وعمياء عن الحجم، وهو ما يتطلبه التشفير.
هل "الالتفاف" يفقد المعلومات؟ نعم، عن قصد. إن محو حجم القيم الوسيطة ميزة، لا عيبًا، في أنظمة الخصوصية.
هل العدد الأولي الأكبر أكثر أمانًا دائمًا؟ بصورة عامة، الحقل الأكبر يعني قيمًا ممكنة أكثر وتخمينًا أصعب، لكن الأمان يعتمد على البنية كلها، لا على حجم الحقل وحده. وستجعل المقالات اللاحقة هذا الأمر أكثر دقة.
لماذا هذه الأعداد الأولية تحديدًا (255 بت، 381 بت) في Zcash؟ اختيرت بحيث تكون للمنحنيات المبنية عليها البنية والكفاءة المناسبتان لنظام البراهين. وهذه "البنية المناسبة" هي موضوع المقالين التاليين.
في F_7، ما قيمة 5 - 6؟ (تذكّر: ابقَ داخل {0,...,6} عن طريق الالتفاف.) (الإجابة أدناه.)
5 - 6 = -1، و-1 بعد لفّه داخل F_7 يصبح 6 (لأن 6 + 1 = 7 = 0). إذن 5 - 6 = 6 (mod 7). الطرح لا يغادر الحقل أبدًا؛ بل يلتف فقط في الاتجاه الآخر.
المقال 2 . المنحنيات الإهليلجية: سنأخذ الحقل المنتهي الذي بنيناه للتو ونستخدمه لرسم نوع غريب من المنحنيات يمكن "جمع" نقاطه معًا. تصبح تلك النقاط مفاتيح Zcash والتزاماته، وتخفي بابًا أحادي الاتجاه يجعل نظام الخصوصية كله ممكنًا. الحدس أولًا، كما هي العادة.
جزء من سلسلة Zcash from First Principles لـ ZecHub. مرخّص بموجب CC BY-SA 4.0.
| 4 |
| 2 |
| 6 | 0 | 6 | 5 | 4 | 3 | 2 | 1 |