الجزء الثالث: أسس من أبحاث التشفير¶
نشتق نماذج التكلفة لمستويَي إثبات العمل في Sibuna، ونعرض إثبات العمل المتسلسل لـ Cohen-Pietrzak مع حجته الأمنية، ونبرر مصادقة التحديات والجلسات بتجزئة ذات مفتاح. يسجل SID 0006 الافتراضات والمراجع.
Hashcash: رياضيات المستوى الأول¶
التعريف والتكلفة¶
لغز المستوى الأول في Sibuna لسلسلة التحدي \(C\) والصعوبة \(b\) بت هو: أوجد \(N \in \mathbb{N}\) بحيث تبدأ \(\text{SHA-256}(C \parallel \text{":"} \parallel \mathrm{dec}(N))\) بـ \(b\) بتات صفرية. كتابة القيمة المؤقتة بالنظام العشري مقصودة؛ فهي تبقي تنسيق النقل متطابقًا بين برنامج الحل بـ WebAssembly، وبديل JavaScript، والمتحقق الأصلي، من دون خطوة ترميز ثنائي.
وحدة الصعوبة هي محاولة تجزئة متوقعة، وليست استدعاءً لدالة الضغط. قد يشغل المدخل عدة كتل SHA-256. وقد تغير الحوسبة المسبقة للبادئة العمل لكل قيمة مؤقتة. تظل قاعدة النقل هي شرط الملخص؛ ويجب أن تتفق التنفيذات على المسألة وترميز القيمة المؤقتة، لا على تكلفة CPU تقديرية.
للملخصات المثالية المستقلة، يتبع عدد المحاولات \(X\) توزيعًا هندسيًا مع \(p = 2^{-b}\). وسيطه \(\left\lceil \ln(1/2) / \ln(1-p) \right\rceil\)، ويقارب \(2^b \ln 2\) عندما تكون \(p\) صغيرة، وتباينه \((1-p)/p^2\). يفحص المتحقق ملخصًا مرشحًا واحدًا بدل إجراء البحث. أما التحليل، ومصادقة التحدي، وفحص البصمة، وتسجيل الحل في مجموعة الحلول المُنفَقة، والاستجابة، فعمل إضافي. ولا يمكن عكس توقيت عملية أولية لاستنتاج قدرة الخادم على تحمل الإغراق.
حدان للبحث¶
الحد الأول هو التباين: البحث الطويل لا يعني بالضرورة تعطل العامل. والثاني هو التوازي: يمكن إجراء محاولات مستقلة لقيم مؤقتة في آن واحد. تقلل النوى الإضافية زمن البحث المنقضي حتى عندما يظل العدد الإجمالي المتوقع للمحاولات ثابتًا. لذا تهم إنتاجية العتاد سياسة القبول. ولا يستطيع معدل تجزئة معلن ولا قياس أداء واحد أن يحد أفضلية كل صاحب طلب.
إثبات العمل المتسلسل: المستوى الثاني¶
لماذا العمل المتسلسل¶
يُدخل بناء العمل المتسلسل اعتماديات بين الحسابات: فالتسمية اللاحقة تحتاج إلى قيمة نتجت قبلها. ويعالج ذلك كمية مختلفة عن مجموع العمل، هي عمق الحساب. وتظل الألغاز المستقلة قابلة للتنفيذ بالتوازي، ويظل زمن التجزئة في العتاد مهمًا.
يتبع Sibuna البناء القائم على التجزئة الذي وصفه Cohen وPietrzak. يحتوي رسمه على \(2^{n+1}-1\) تسمية عند العمق \(n\)، لكن العدد الثابت من التسميات لا يعني زمنًا حتميًا في المتصفح: فقد تمتد التسمية على عدة كتل ضغط، وقد تعيد عمليات الفتح حساب أشجار فرعية، وتضيف الجدولة تفاوتًا. ولا يجوز أن تتحول العبارات الأمنية المستمدة من تحليلات نموذج الأوراكل إلى ادعاء مطلق بشأن كل تنفيذ ملموس أو كل خصم.
البناء¶
ليكن \(n\) هو العمق، ولننظر إلى الشجرة الثنائية الكاملة التي تُسمى عقدها بسلاسل ثنائية لا يتجاوز طولها \(n\) (الجذر \(\varepsilon\)، والابنان \(v0\) و\(v1\)، والأوراق بطول \(n\)). تحمل كل عقدة \(v\) تسمية من 32 بايت \(\ell_v = H(\chi, v, \mathrm{parents}(v))\)، حيث \(\chi\) هي مسألة التحدي و\(H\) هي SHA-256 بعد استيعاب \(\chi\) مرة واحدة (حيلة البادئة نفسها في برنامج حل Hashcash):
- تجزئ العقدة الداخلية ابنيها: \(\ell_v = H(\chi, v, \ell_{v0}, \ell_{v1})\)؛
- تجزئ الورقة \(u = u_1 \dots u_n\) الأشقاء اليساريين لأسلافها حيثما اتجه مسار الجذر إلى اليمين: \(\ell_u = H(\chi, u, \{\ell_{u_1 \dots u_{i-1} 0} : u_i = 1\})\).
حواف الأشقاء اليساريين هي ما يجعل الحساب متسلسلًا: لا يمكن إسناد تسمية إلى الورقة \(u\) قبل أن تكتمل كل شجرة فرعية على يسارها، فيُفرض اجتياز بالعمق أولًا بترتيب لاحق (post-order)، وتعتمد تسمية الجذر \(\varphi = \ell_\varepsilon\) على جميع التسميات البالغ عددها \(2^{n+1} - 1\) بالتسلسل.
عمليات الفتح. بعد حساب \(\varphi\)، يشتق المُبرهِن \(t\) ورقة بطريقة Fiat-Shamir، \(\gamma_i = H(\chi \parallel \varphi \parallel i) \bmod 2^n\)، ويرسل لكل منها تسمية الورقة وتسميات الأشقاء البالغ عددها \(n\) على مسارها إلى الجذر. يعيد المتحقق حساب الورقة من الأشقاء الذين هم آباؤها، ويجزئ صعودًا عبر المسار، ويتحقق من أنه يصل إلى \(\varphi\). تكلفة المتحقق \(O(tn)\) حساب تسمية بمساحة عمل محدودة. وقد يمتد حساب التسمية الواحدة على عدة كتل تجزئة؛ فعدّ التسميات ليس عدًّا لاستدعاءات دالة الضغط.
fn verify_opening(base: &Sha256, n: u8, phi: &Label, gamma: u32, opening: &[Label]) -> bool {
let Some((leaf, siblings)) = opening.split_first() else {
return false;
};
// تمتد `siblings` من العمق n صعودًا إلى العمق 1؛ وبعد عكسها تقترن بالأعماق 1..=n.
let mut hasher = node_hasher(base, n, gamma);
for (d, sibling) in (1..=n).zip(siblings.iter().rev()) {
if turns_right(gamma, n, d) {
hasher.update(sibling);
}
}
if hasher.finalize() != *leaf {
return false;
}
let mut current = *leaf;
for (d, sibling) in (1..=n).rev().zip(siblings) {
let mut parent = node_hasher(base, d - 1, gamma >> (n - d + 1));
if turns_right(gamma, n, d) {
parent.update(sibling);
parent.update(¤t);
} else {
parent.update(¤t);
parent.update(sibling);
}
current = parent.finalize();
}
current == *phi
}
أخذ العينات والسلامة وحدودهما¶
لننظر في التزام ثابت فيه نسبة سيئة \(\alpha\) يمكن كشفها كشفًا مستقلًا. إذا أخذت كل عملية فتح عينتها بتوزيع منتظم وباستقلال، فإن احتمال تفويت كل المواضع السيئة في \(t\) عملية فتح هو \((1-\alpha)^t\). يوضح هذا الحساب البسيط لماذا تفيد زيادة عمليات الفتح، لكنه وحده ليس برهانًا أمنيًا لبروتوكول عمل متسلسل.
لبناء العمل المتسلسل المشار إليه تحليل أمني في نموذج أوراكل. ومع ذلك يجب التحقق من أن فصل المجالات في Sibuna، وخريطة المعلمات، والاقتطاع، والتنفيذ تفي بافتراضات البناء. تجعل عينات Fiat-Shamir عمليات الفتح قابلة لإعادة الإنتاج من الالتزام؛ لكن قابلية إعادة الإنتاج وحدها لا تثبت مقاومة التجربة المتكررة (grinding). ولا ندعي دون قيد أن الغش لا يكون أرخص أبدًا.
ذاكرة المُبرهِن¶
يخزن مُبرهِن ساذج كل تسمية (وعددها \(2^{n+1} - 1\)). يحتفظ مُبرهِن Sibuna في المرور الأول بمكدس لتسميات الأشقاء اليساريين للمسار الحالي (\(n + 1\) تسمية)، ولا يبقي إلا أعلى \(m = \min(n, 10)\) مستوى (\(2^{m+1} - 1\) تسمية، وبحد أقصى 64 KB). لفتح ورقة، يعيد حساب الشجرة الفرعية لسلف الورقة عند العمق \(m\)، أي \(2^{n-m+1} - 1\) تجزئة، مع تهيئة المكدس من المستويات المحفوظة. التكلفة الإجمالية للمُبرهِن \(2^{n+1} - 1 + t\,(2^{n-m+1} - 1)\) تجزئة، ومساحة العمل كلها، بما فيها الإثبات الناتج، أقل من 100 KB: يشترك تبويب المتصفح والاختبار الأصلي في النوع Workspace نفسه (sibuna_pow::posw::Workspace).
المعلمات ليست أزمنة¶
يربط Sibuna بتات العمل بالعمق باستخدام \(n = b - 3\)، مع حصره في المجال المدعوم \([4, 24]\). وهذا اصطلاح لمقياس العمل، وليس ضمانًا لتساوي الزمن الفعلي بين الخوارزميتين. فالورقة قد تجزئ عدة تسميات آباء، بينما يختبر Hashcash قيمة مؤقتة مرة بعد مرة. وتؤثر خيارات المترجم والمتصفح والمعالج والمعلمات كلها في تكاليفهما النسبية. يقيس قياس أداء العمليات الأولية المودَع في المستودع التحقق؛ ولا يثبت زمن الحل في المتصفح.
حجم الإثبات \(32(1 + t(n+1))\) بايت. عند العمق 13 مع ست عشرة عملية فتح، يبلغ \(32(1 + 16 \times 14) = 7200\) بايت. وزيادة عدد عمليات الفتح تزيد حجم الإثبات وعمل المتحقق معًا، حتى إذا ظلت التكلفة الغالبة لبناء الشجرة ثابتة.
اختيار البناء¶
المقارنة المناسبة هي ميزانية الموارد، لا سمعة الخوارزمية. سجّل ذاكرة المُبرهِن، وعمل المتحقق في أسوأ الحالات، وبايتات الإثبات، والافتراضات اللازمة للخاصية المعلنة. قد يفيد البحث المستنزف للذاكرة (memory-hard)، لكن المتحقق الذي يضطر إلى تكرار عمل مكلف يمنح المهاجم موضعًا آخر لاستنزاف موارد الخادم. وتخدم بناءات التأخير القابلة للتحقق العلني نموذج ثقة مختلفًا عن نموذج بوابة تقوم على سر مشترك.
يحتفظ Sibuna بتحقق تجزئة قليل التكلفة، وبخيار عمل متسلسل قائم على التجزئة. يحتاج الأخير إلى بايتات إثبات أكثر وتحليل أدق للمعلمات. لا يلغي أي من الخيارين ضرورة رفض الإثباتات المشوهة قبل الدخول في تحقق مكلف.
المصادقة المتماثلة: التحديات والجلسات¶
المُصدر هو المتحقق¶
يتيح التوقيع الرقمي لأي أحد يحمل المفتاح العام أن يتحقق، وهو الأداة المناسبة عندما يجب ألا يتمكن المتحققون من إصدار الرموز. متحقق Sibuna هو المُصدر (أو عنقود يتشارك بذرة واحدة). يوفر رمز مصادقة الرسالة المبني من دالة شبه عشوائية المصادقة داخل مجال الثقة هذا. ولا يوفر التحقق العلني: كل من يحمل مفتاح MAC يستطيع أيضًا إصدار الرموز. يقارن فصل قياسات الأداء عمليات الرموز المنفذة.
ولنتيجة ثانية أهمية على المدى البعيد: يعتمد Ed25519 على اللوغاريتمات المتقطعة في زمرة منحنى إهليلجي، وتكسرها خوارزمية Shor؛ أما التجزئة ذات المفتاح فتعتمد على دالة التجزئة وحدها، ولا تعطي الخوارزميات الكمومية ضدها أكثر من تسارع تربيعي. يحتفظ Sibuna بـ Ed25519 خيارًا (--token-scheme ed25519) لعمليات النشر التي تحتاج إلى متحققين لا يستطيعون إصدار الرموز.
جدول اشتقاق المفاتيح¶
تُشتق من بذرة رئيسية واحدة من 32 بايت (من --secret-file أو SIBUNA_SECRET أو قيمة عشوائية جديدة) مفاتيح الأغراض كلها باستخدام BLAKE3 ذي مفتاح وسلسلة مجال: مفاتيح الرمز، والتحدي، وEd25519، والبصمة، ومفتاح المتطلبات الذي يختم تذاكر المتطلبات (الجزء الرابع).
pub fn derive(seed: &Seed) -> Keys {
Keys {
token: subkey(seed, "sibuna/token/v1"),
challenge: subkey(seed, "sibuna/challenge/v1"),
ed25519_seed: subkey(seed, "sibuna/ed25519/v1"),
fingerprint: subkey(seed, "sibuna/fingerprint/v1"),
requirement: subkey(seed, "sibuna/requirement/v1"),
}
}
fn subkey(seed: &Seed, purpose: &str) -> [u8; 32] {
blake3::keyed_hash(seed.as_bytes(), purpose.as_bytes())
}
في العنقود، يضع Keys::bind_node مكان مفتاح التحدي ناتجَ BLAKE3 ذي مفتاح، مفتاحه مفتاح التحدي نفسه، محسوبًا على sibuna/challenge-node/v1 ومعرّف العقدة؛ فيجب أن يعود التحدي إلى العقدة التي أصدرته، بينما تظل رموز الجلسة وتذاكر المتطلبات صالحة على كل عضو.
يمنع فصل المجالات إعادة الاستخدام العرضية بين الأغراض؛ واختراق البذرة الرئيسية يخترق كل مفتاح مشتق. لا يحتاج العنقود إلا إلى الاتفاق على بذرة واحدة.
تحديات عديمة الحالة¶
معرّف التحدي سجل ذاتي المصادقة: الإصدار، والخوارزمية، والصعوبة، وعدد عمليات الفتح، ووقت الإصدار، وبصمة العميل ذات المفتاح، وقيمة مؤقتة مشتقة من PRF، وتجزئة قاعدة السياسة التي طلبت التحدي، يتبعها وسم من 16 بايت بمفتاح التحدي. وإصداره لا يكتب شيئًا. يفك التحقق ترميز السجل، ويفحص الوسم في زمن ثابت، ويقارن العمر بمدة صلاحية التحدي، ويقارن البصمة بالعميل المرسل، وعندئذ فقط يفحص الإثبات.
مجموعة الحلول المُنفَقة 16 شريحة بعنونة Robin Hood المفتوحة على الوسوم ذات 16 بايت (الجزء الخامس). والبصمة تجزئة ذات مفتاح لعنوان العميل وUser-Agent، مع فصل الأطوال كي لا يتصادم مدخلان بالضمّ، ومع مفتاح كي لا يمكن حساب بصمات عملاء آخرين دون اتصال (offline).