Protokol, bir istemci grubu arasında paylaşılan sırları türetmek için "ratchet ağaçları" kullanır. Ratchet ağacı, bir grubun üyeleri arasında sırların ve anahtar çiftlerinin, gruptaki değişiklikleri yansıtacak şekilde verimli biçimde güncellenebilmesini sağlayan bir düzenlemedir.
Ratchet ağaçları, gruba ait bir alt kümeye yeni entropi şifreleyerek grubun herhangi bir üyesinin verimli biçimde çıkarılmasına olanak tanır. Ratchet ağacı, grubun alt gruplarına paylaşılan anahtarlar atar; böylece örneğin, grup üyelerinden biri hariç hepsine şifreleme yapmak, her katılımcıya ayrı ayrı şifreleme için gereken N-1 şifreleme yerine (burada N, gruptaki üye sayısıdır), alt ağaçlara yalnızca log(N) şifreleme gerektirir.
Bu çıkarma işlemi, MLS'nin ele geçirilme sonrası güvenliği verimli biçimde sağlamasına olanak tanır. Bir Update teklifi veya tam bir Commit mesajı içinde, bir üyenin eski (muhtemelen ele geçirilmiş) temsili gruptan verimli biçimde çıkarılır ve yerine yeni oluşturulmuş bir örnek konur.
4.1 Ratchet Ağacı Terminolojisi
Ağaçlar düğümlerden oluşur. Bir düğümün çocuğu yoksa bu düğüm bir yaprak; aksi halde bir ebeveyn düğümdür. Ağaçlarımızdaki tüm ebeveyn düğümlerin tam olarak iki çocuğu vardır: bir sol çocuk ve bir sağ çocuk. Bir düğümün ebeveyni yoksa o düğüm ağacın köküdür; hem çocukları hem de ebeveyni varsa o düğüm bir ara düğüm sayılır. Bir düğümün soyundan gelenleri, o düğümün çocukları ile bu çocukların soyundan gelenlerdir. Bir düğüm, ağacın kökünden aşağı doğru inildiğinde ulaşılabilen bir düğümse veya düğümün kendisi kökse, ağacın o düğümü içerdiğini söyleriz. Aynı ebeveyni paylaşan düğümler kardeş düğümlerdir.
Bir ağacın alt ağacı, herhangi bir düğümün (alt ağacın başı) ve bu düğümün soyundan gelenlerin oluşturduğu ağaçtır. Bir ağaç ya da alt ağacın boyutu, içerdiği yaprak düğümlerin sayısıdır. Belirli bir ebeveyn düğüm için, sol alt ağaç sol çocuğu baş kabul eden alt ağaçtır; sağ alt ağaç ise sağ çocuğu baş kabul eden alt ağaçtır.
Bu protokolde kullanılan her ağaç, kusursuz ikili ağaçtır (perfect binary tree); yani, tüm yaprakları aynı d derinliğinde bulunan ve 2^d yaprak içeren tam dengeli bir ikili ağaçtır. Bu yapı, verilen bir d derinliği için tektir.
Bir uygulama, ratchet ağacını bellekte birden fazla şekilde temsil edebilir. Sol dengeli ikili ağaçların (burada kullanılan tam ağaçlar da buna dahildir) kullanışlı bir özelliği, düğümlerin dizideki indislerinden düğüm ilişkileri hesaplanarak, bunların bir düğüm dizisi olarak temsil edilebilmesidir. Bağlantılı düğüm nesnelerine dayanan daha geleneksel bir gösterim de kullanılabilir. Ek C ve Ek D, MLS için gerekli ağaç işlemlerinin bu gösterimlerde nasıl uygulanacağına dair bazı ayrıntılar sunar. MLS, ratchet ağaçlarının iç gösterimi konusunda uygulamalara herhangi bir zorunluluk getirmez. Bir uygulama, doğru protokol mesajları ürettiği sürece, herhangi bir ağaç gösterimini ve buna bağlı algoritmaları kullanabilir.
4.1.1 Ratchet Ağacı Düğümleri
Bir ratchet ağacındaki her yaprak düğüme, soldan başlayarak 0'dan sağda 2^d - 1'e kadar bir indis (veya yaprak indisi) verilir (2^d yapraklı bir ağaç için). 2^d yapraklı bir ağaç, ebeveyn düğümler dahil olmak üzere 2^(d+1) - 1 düğüme sahiptir.
Bir ratchet ağacındaki her düğüm ya boş durumdadır (hiçbir değer içermez) ya da ilişkili bazı verilerle birlikte bir HPKE açık anahtarı tutar:
Bir açık anahtar (kullanımdaki HPKE düzeni için bkz. Bölüm 5.1)
Bir kimlik bilgisi (yalnızca yaprak düğümler için; bkz. Bölüm 5.3)
Sıralı bir "birleştirilmemiş" yaprak listesi (bkz. Bölüm 4.2)
Düğüm en son değiştirildiği andaki ebeveyn düğümü hakkında belirli bilgilerin hash'i (bkz. Bölüm 7.9)
Bölüm 4.2'de açıklandığı gibi, farklı üyeler ağaçtaki düğümlerde yer alan açık anahtarlara karşılık gelen özel anahtarlar kümesinin farklı alt kümelerini bilir. Bir ebeveyn düğüme karşılık gelen özel anahtar, yalnızca o düğümün soyundan gelen yaprak düğümlerde bulunan üyelerce bilinir. Bir yaprak düğüme karşılık gelen özel anahtar ise yalnızca o yaprak düğümdeki üye tarafından bilinir. Yaprak düğümdeki üye, atası olan düğüme karşılık gelen özel anahtarı bilmiyorsa, yaprak düğüm, atası olan düğümlerden biri açısından birleştirilmemiş sayılır.
Bir düğüm, boş ya da dolu olmasından bağımsız olarak, o düğümün altındaki alt ağacın içeriğini özetleyen bir hash'e sahiptir. Bu hash'lerin hesaplanmasına ilişkin kurallar Bölüm 7.8'de açıklanmıştır.
Bir düğümün çözümlemesi (resolution), birlikte ele alındığında o düğümün boş olmayan tüm soyundan gelenlerini kapsayan, boş olmayan düğümlerden oluşan sıralı bir listedir. Kök düğümün çözümlemesi, gruptaki her düğüme topluca şifreleme yapmak için gerekli olan anahtar kümesini içerir. Bir düğümün çözümlemesi, özünde, düğümün altındaki en yakın boş olmayan düğümlerin derinlik öncelikli ve soldan başlayan sıralı listesidir:
Boş olmayan bir düğümün çözümlemesi, düğümün kendisinden ve varsa birleştirilmemiş yapraklar listesinden oluşur.
Boş bir yaprak düğümün çözümlemesi boş listedir.
Boş bir ara düğümün çözümlemesi, önce sol çocuğunun çözümlemesiyle, ardından sağ çocuğunun çözümlemesinin bu sırayla birleştirilmesinin sonucudur.
Örneğin, _ karakterinin boş düğümü temsil ettiği ve
birleştirilmemiş yaprakların köşeli parantez içinde gösterildiği
aşağıdaki alt ağacı ele alalım:
...
/
_
______|______
/ \
X[B] _
__|__ __|__
/ \ / \
_ _ Y _
/ \ / \ / \ / \
A B _ D E F _ H
0 1 2 3 4 5 6 7
Şekil 10: Boş Düğümler ve Birleştirilmemiş Yapraklar İçeren Bir Ağaç
Bu ağaçta yukarıdaki kuralların tamamının nasıl işlediğini görebiliriz:
X düğümünün çözümlemesi
[X, B]listesidir.2 numaralı yaprağın veya 6 numaralı yaprağın çözümlemesi boş liste
[]'dir.En üst düğümün çözümlemesi
[X, B, Y, H]listesidir.
4.1.2 Ratchet Ağacı İçindeki Yollar
Kök düğümün doğrudan yolu boş listedir. Diğer herhangi bir düğümün doğrudan yolu ise, o düğümün ebeveyni ile ebeveynin doğrudan yolunun birleştirilmesidir.
Bir düğümün eş yolu (copath), düğümün kardeşi ile doğrudan yolundaki tüm düğümlerin kardeşlerinden oluşan listenin, kök hariç olacak şekilde, birleştirilmesidir.
Bir yaprak düğüm L'nin filtrelenmiş doğrudan yolu, düğümün doğrudan yolunun; L'nin eş yolu üzerindeki çocuğu boş çözümlemeye sahip olan her düğüm çıkarılmış halidir (eş yol üzerindeki çocuğun birleştirilmemiş yapraklarının da çözümlemesine dahil olduğunu akılda tutarak). Çıkarılan düğümlerin kendi anahtar çiftlerine ihtiyacı yoktur; çünkü düğümün anahtar çiftine şifreleme yapmak, eş yol üzerinde olmayan çocuğuna şifreleme yapmakla eşdeğer olurdu.
Örneğin, boş düğümlerin _ ile gösterildiği, ancak ayrıca başvuru
amacıyla etiketlendiği aşağıdaki ağacı ele alalım:
W = kök
|
.-----+-----.
/ \
_=U Y
| |
.-+-. .-+-.
/ \ / \
T _=V X _=Z
/ \ / \ / \ / \
A B _ _ E F G _=H
0 1 2 3 4 5 6 7
Şekil 11: Beş Üyeli Tam Bir Ağaç ve Boş Ebeveyn Düğümleri İçin Etiketler
Bu ağaçta yaprak düğümlere ait doğrudan yollar, eş yollar ve filtrelenmiş doğrudan yollar aşağıdaki gibidir:
| Düğüm | Doğrudan yol | Eş Yol | Filtrelenmiş Doğrudan Yol |
|---|---|---|---|
| A | T, U, W | B, V, Y | T, W |
| B | T, U, W | A, V, Y | T, W |
| E | X, Y, W | F, Z, U | X, Y, W |
| F | X, Y, W | E, Z, U | X, Y, W |
| G | Z, Y, W | H, X, U | Y, W |
Tablo 2
4.2 Ratchet Ağacına Dair Görünümler
Genel olarak, her katılımcının grubun ratchet ağacının açık durumuna ilişkin tam ve güncel bir görünümü koruduğunu varsayarız; buna tüm düğümlere ait açık anahtarlar ve yaprak düğümlerle ilişkili kimlik bilgileri de dahildir.
Bir MLS grubundaki hiçbir katılımcı, ağaçtaki her düğüme karşılık gelen özel anahtarı bilmez. Bunun yerine, her üye ağacın bir yaprağına atanır ve bu da hangi özel anahtarlar alt kümesini bildiğini belirler. Bu yaprakta saklanan kimlik bilgisi, ilgili üye tarafından sağlanmıştır.
Özellikle MLS, üyelerin ağaca ilişkin görünümlerini ağaç değişmezi (tree invariant) korunacak şekilde tutar:
Ağaçtaki bir düğüme ait özel anahtar, grubun bir üyesi tarafından yalnızca o düğümün alt ağacı bu üyenin yaprağını içeriyorsa bilinir.
Başka bir deyişle, bir düğüm boş değilse bir açık anahtar tutar. Karşılık gelen özel anahtar yalnızca o düğümün altındaki yapraklarda yer alan üyeler tarafından bilinir.
Tersi doğru değildir: Bir üye, kendi üzerinde yer alan bir ara düğümün özel anahtarını bilmiyor olabilir. Böyle bir üyenin bu ara düğümde birleştirilmemiş bir yaprağı vardır. Bir ara düğüme şifreleme yapmak, o düğümün açık anahtarına ve onun altındaki birleştirilmemiş tüm yaprakların açık anahtarlarına şifreleme yapmayı gerektirir. Bir yaprak ilk eklendiğinde tüm ataları bakımından birleştirilmemiştir; çünkü yaprağı ekleme işlemi, ona ağaçta üzerinde yer alan tüm düğümlerin özel anahtarlarına erişim vermez. Yapraklar, Bölüm 7.4'te açıklandığı gibi, düğümlere ait özel anahtarları aldıkça "birleştirilir".
Örneğin, sağdaki iki üyenin üzerindeki düğümün boş olduğu dört üyeli
bir grubu (A, B, C, D) ele alalım. (A, B, C ve D ile bir grup
oluşturduğunda görünüm bu şekilde olurdu.) Buna göre ağacın açık
durumu ve her katılımcının elindeki özel anahtar görünümü aşağıdaki
gibi olur; burada _ boş düğümü, ? bilinmeyen özel anahtarı ve
pk(X) ise X özel anahtarına karşılık gelen açık anahtarı temsil eder:
Açık Ağaç
============================
pk(ABCD)
/ \
pk(AB) _
/ \ / \
pk(A) pk(B) pk(C) pk(D)
A'daki Özel B'deki Özel C'deki Özel D'deki Özel
============= ============= ============= =============
ABCD ABCD ABCD ABCD
/ \ / \ / \ / \
AB _ AB _ ? _ ? _
/ \ / \ / \ / \ / \ / \ / \ / \
A ? ? ? ? B ? ? ? ? C ? ? ? ? D
Ağaç değişmezinin nasıl uygulandığına dikkat edin: Her üye yalnızca kendi yaprağını bilir; AB özel anahtarı yalnızca A ve B tarafından bilinir; ABCD özel anahtarı ise dört üyenin tamamı tarafından bilinir. Bu aynı zamanda başka önemli bir noktayı da gösterir: Bir üyenin yaprağından köke giden yol üzerinde, üyenin belirli bir düğümün hem üstündeki hem altındaki anahtarı bildiği, fakat o düğümünki anahtarı bilmediği "boşluklar" bulunabilir; D örneğinde olduğu gibi.