Path ORAM: إخفاء عمليات الوصول إلى الذاكرة

يُعد Path ORAM، الذي اقترحه Stefanov وvan Dijk وShi وFletcher وRen وYu وDevadas عام 2013، بنية ORAM الأكثر تأثيرًا من الناحية العملية. وينظم تخزين الخادم على شكل شجرة ثنائية من الحاويات، بحيث تقابل كل ورقة موضعًا لكتلة بيانات. ويحقق Path ORAM في صورته الأساسية كلفة اتصال قدرها O(log^2 N) لكل عملية وصول، كما أنه بسيط بما يكفي لتنفيذه في بضع مئات من أسطر التعليمات البرمجية.

خريطة المواضع هي بنية بيانات لدى العميل تربط عنوان كل كتلة منطقية بعقدة ورقية في الشجرة الثنائية. وبالنسبة إلى قاعدة بيانات تتكون من N كتلة وشجرة ارتفاعها L = log N، تكون خريطة المواضع مصفوفة من فهارس الأوراق وعددها N. قبل الوصول إلى الكتلة b، يبحث العميل عن الورقة المعيّنة لها حاليًا في خريطة المواضع، ثم يعيّن لها ورقة عشوائية جديدة. وسيُقرأ مسار الورقة القديمة من الخادم ثم يُكتب إليه مجددًا.

المخبأ هو ذاكرة مؤقتة صغيرة لدى العميل، وتتسع عادةً لـ 20-40 كتلة، وتحتفظ مؤقتًا بالكتل التي قُرئت من الخادم ولم تُكتب إليه بعد. عند قراءة كتلة، تُزال من مسارها وتوضع في المخبأ. وبعد الوصول إليها وربما تعديلها، تُكتب مجددًا جميع الكتل الموجودة في المخبأ والتي يمكن وضعها على المسار الجديد. أما الكتل التي لا يمكن أن تتسع لها أي مسار، فتبقى في المخبأ.

يتكون تخزين الخادم من شجرة ثنائية كاملة ذات L+1 مستوى (L = log N). وتحتوي كل عقدة (حاوية) على Z كتلة، وعادةً ما يكون Z = 5. وتمثل الأوراق مواضع لكتل البيانات. وهناك N عقدة ورقية، ولذلك يبلغ العدد الإجمالي للعقد 2N-1، ويبلغ إجمالي تخزين الخادم O(NZ). ويضم كل مسار من ورقة إلى الجذر log N عقد، ويمكنه استيعاب Z*log N كتلة، مما يوفر السعة اللازمة لاستراتيجية إخلاء المسار.

لقراءة الكتلة b: (1) ابحث في خريطة المواضع عن الورقة الحالية l الخاصة بالكتلة b؛ (2) عيّن للكتلة b ورقة عشوائية جديدة l' وحدّث خريطة المواضع؛ (3) اقرأ جميع الحاويات الموجودة في المسار من الورقة l إلى الجذر (أي log N حاوية)؛ (4) اعثر على الكتلة b في المسار المقروء أو في المخبأ؛ (5) اكتب مجددًا جميع الكتل التي يمكن تعيينها إلى المسار الجديد l'، واملأ خانات الحاويات المتبقية بكتل وهمية. وهكذا يرى الخادم في كل مرة قراءة لمسار عشوائي.

يحافظ Path ORAM على إخفاء نمط الوصول لأن كل عملية وصول تقرأ وتكتب مسارًا واحدًا بالضبط من الجذر إلى الورقة، بصرف النظر عن الكتلة التي يجري الوصول إليها. ويتحدد المسار من خلال تعيين ورقة عشوائية موزعة توزيعًا منتظمًا، لا من خلال محتوى الكتلة أو عنوانها. وتملأ الكتل الوهمية خانات الحاويات الفارغة، بحيث يضم كل مسار العدد نفسه من الخانات المشغولة. ولا يرى الخصم الذي يراقب الخادم سوى عمليات وصول إلى مسارات عشوائية.

تتطلب كل عملية وصول في Path ORAM قراءة مسار واحد من الجذر إلى الورقة وكتابته: أي O(log N) حاوية، تحتوي كل منها على Z كتلة. ومع حجم كتلة B وحجم حاوية Z، تنقل كل عملية وصول O(Z * log N * B) بت. وبالنسبة إلى المعاملات المعتادة (N = 2^20، Z = 5، B = 4KB)، يبلغ ذلك نحو 400KB لكل عملية وصول، مقارنةً بـ 4KB للوصول إلى نص صريح، أي كلفة إضافية قدرها 100x. وتخفض خرائط المواضع التكرارية كلفة الاتصال هذه إلى O(log^2 N) عند قياسها بعدد الكتل.

تتطلب خريطة المواضع الساذجة N مدخلة مخزنة لدى العميل، أي تخزينًا لدى العميل قدره O(N)، وهو بحجم قاعدة البيانات بأكملها. وتخفض خريطة المواضع التكرارية مساحة تخزين العميل إلى O(log^2 N) من خلال تخزين خريطة المواضع نفسها في ORAM أصغر بصورة تكرارية. وتنتهي عملية التكرار عندما يصبح ORAM صغيرًا بما يكفي ليتسع له المخبأ. وهذه هي التقنية القياسية لجعل Path ORAM عمليًا مع مجموعات البيانات الكبيرة.

يزداد حجم المخبأ في Path ORAM إذا تعذر إخلاء الكتل إلى المسارات المعيّنة لها بسبب تعارضات المسارات. وقد أثبت Stefanov وآخرون أن احتمال امتلاء المخبأ (أي تجاوزه R كتلة) يتناقص أسيًا مع R، وتحديدًا لا يتجاوز 14 * (0.6002)^R في التحليل القياسي. ويؤدي ضبط R = 40 إلى احتمال فشل يبلغ نحو 2^{-38}، وينطبق ذلك على جميع تسلسلات الوصول، بما فيها التسلسلات التي يختارها خصم.

قبل Path ORAM، كانت أفضل بنيات ORAM العملية تفرض كلفة قدرها O(log^3 N) (Shi وآخرون، 2011، "Oblivious RAM with O((log N)^3) Worst-Case Cost"). وقد خفض Path ORAM هذه الكلفة إلى O(log^2 N) مع بنية أبسط بكثير. وحسّنت الأعمال اللاحقة (Circuit ORAM وOptORAMa) الثوابت والحدود التقاربية بدرجة أكبر، لكن Path ORAM لا يزال البنية الأكثر تطبيقًا على نطاق واسع بفضل بساطته.

نُفّذ Path ORAM في عشرات الأنظمة البحثية وأنظمة الإنتاج. ومن التطبيقات البارزة ZeroTrace (Intel SGX + Path ORAM)، وObladi (Path ORAM فوق التخزين السحابي)، وOpaque (Path ORAM فوق Apache Spark). وتحافظ مجموعة Stanford للحوسبة الآمنة على تنفيذ مفتوح المصدر لـ Path ORAM بلغة C++. وتوفر AWS تقنية Path ORAM ضمن نماذجها البحثية الأولية لـ Nitro Enclaves المخصصة لتحليلات البيانات التي تحافظ على الخصوصية.

ما دور خريطة المواضع في Path ORAM؟

ينظم Path ORAM تخزين الخادم على شكل شجرة ثنائية، بحيث تقرأ كل عملية وصول مسارًا واحدًا من الجذر إلى الورقة وتكتبه. وتتتبع خريطة المواضع تعيين الورقة الحالية لكل كتلة، بينما يحتفظ المخبأ بالكتل التي جرى الوصول إليها مؤخرًا. وتُعشّى كل عملية وصول من خلال تعيين مواضع ورقية عشوائية جديدة، مما يجعل جميع عمليات الوصول التي يراها الخادم موزعةً بالتوزيع نفسه. وتبلغ كلفة الاتصال O(Z * log N) لكل عملية وصول. وتخفض خرائط المواضع التكرارية مساحة تخزين العميل إلى O(log^2 N). ويُعد Path ORAM بنية ORAM الأكثر تطبيقًا على نطاق واسع.