回想一下，多對映是多個標籤/值元組的集合。在這種結構中，我們將與每個標籤相關聯的值儲存到區塊鏈上單獨的邏輯連結串列中。但是為了保證機密性，我們在將每個與前一個地址連線的值新增到右連結列表之前對其進行加密。精確地，給定要新增到標籤l的元組（v1，…，vn），對於每個i∈[1，n]，我們將EncK（vi || ri-1）新增到區塊鏈。對於第一個值，ri-1是l的連結串列的當前頭的地址。為了實現動態性，我們使用了延遲刪除，即所有新增和刪除的值都標記為新增（+）或刪除（-），並且僅在查詢時透過從輸出中刪除標記為刪除的值來執行刪除。有關LSX的說明，請參見圖1 –為清楚起見，我們省略了圖中的值和地址的加密。
效率：很容易看出LSX具有最佳的新增和刪除時間複雜度：對於每個操作，我們只寫入與元組大小一樣多的值。然而，它的查詢複雜度在更新次數上是線性的。特別是，在每個查詢中，我們讀取所有新增或刪除的值。如果所有更新操作都是加法操作，則此方案具有最佳的查詢複雜性，但是如果大多數更新是刪除操作，則該方案將產生不小的查詢開銷。該方案還有另一個缺點：新增和刪除操作都需要在使用者和區塊鏈之間進行線性數量的寫入輪數（以元組的大小為單位）。這是由於以下事實：在計算出vi-1的地址之前，無法寫入值vi，因此必須在單獨的寫入輪數中寫入每個值。
計算寫輪數很重要，因為由於挖掘和穩定，區塊鏈的寫操作要比區塊鏈的讀操作花費更長的時間。因此，儘可能多地並行化寫入變得很重要。我們稱此指標為穩定的複雜性，因為寫入所需的時間取決於交易穩定所需的時間–例如，對於比特幣，寫入時間最多可為60分鐘（一個區塊必須在鏈的最長鏈至少要達到6個區塊才能變得不可變）。
接下來，我們描述一種基於樹的方案，該方案將穩定複雜度從線性提高到對數。
基於樹的方案A Tree-Based Scheme（TRX）
在此方案中，我們修改了值的組織方式，目的是減少儲存值之前所需的地址數量。給定要新增/刪除的元組，我們將完整的二叉樹疊加，而不是在鏈上疊加連結串列。這使我們能夠並行化在樹的相同深度處的所有值的插入。此外，我們還連結了跨多個新增/刪除操作構建的樹的根。注意，這種簡單的結構更改將穩定複雜度從線性降低到了對數。
由於上述兩種方案的查詢複雜度與新增/刪除值的數量呈線性關係（當大多數更新都是刪除操作時，這可能很糟糕），因此我們現在描述一種方案，該方案將查詢複雜度提高到最佳，但刪除的代價有點昂貴。
基於區塊的方案A Patch-Based Scheme（PAX）
注意，LSX的查詢複雜度不是最優的，因為我們不知道遍歷連結列表1時刪除的值，因此我們最終讀取所有值，而不管它們是否被刪除。為了解決這個問題，我們將額外的資料結構（稱為區塊）附加到連結列表的頂部。塊程式是地址對，它將允許查詢演算法跳過已刪除的值。例如假設我們有以下連結列表：
刪除v2時，我們建立一個塊（addr（v3）→addr（v1）），刪除v4時，我們建立另一個塊（addr（v5）→addr（v3））。目前，我們無需擔心塊的儲存位置和儲存方式。但是給定了這些塊，查詢演算法可以輕鬆跳過已刪除的值v2和v4：從v5起，它將使用第二個塊跳轉到v3，從v3起，它將使用第一個塊跳轉到v1。
現在假設v3也被刪除了。在這種情況下，我們將建立一個新塊（addr（v5）→addr（v1）），該塊可幫助查詢演算法跳過所有值v2，v3和v4。
這有兩個問題：
1. v5中有兩個塊：一個進入v3，一個進入v1。為了使查詢正確跳過已刪除的值，應使用（v5→v1）而不是（v5→v3）。
2. 塊的數量等於已刪除值的數量，這意味著搜尋塊的成本與使用延遲刪除一樣昂貴。
為了解決這個問題，我們需要確保我們清理（或刪除）舊塊。準確地說，刪除v3後，我們應該同時刪除（v5→v3）和（v3→v1）。（v5→v3）的刪除保證了正確性，而（v3→v1）的刪除則保證了效率，因為剩下的色塊數量最多為未刪除值的數量。
塊資料結構：由於塊的數量可能很大，它們不能儲存在本地，也必須儲存在區塊鏈上。我們可以在連結串列或樹中組織塊。無論我們決定如何，我們都將其稱為塊結構。請注意，無論我們如何在區塊鏈上組織塊結構，從中刪除塊的要求都會帶來雞與蛋的問題：從連結列表中刪除多圖值需要從塊結構中刪除塊。那麼我們應該修補塊結構嗎？
我們使用另一種稱為“寫入即複製”的技術來解決這個難題。在高層次上，該技術複製“節點”，並對副本進行修改，而不是修改原始節點。我們用一個例子來解釋。假設我們將塊結構表示為連結串列。此外，假設塊結構中有100個塊是從P1…P100。
要刪除P2，我們需要使P3指向P1。但是由於P3儲存在區塊鏈上，因此不能將其更改為指向P1。因此，我們建立了P3的複製P′3，這樣它儲存的塊資料與P3相同，指向P1。但是，這要求P4指向副本P′3，由於它也儲存在區塊鏈上，因此無法做到這一點。因此，建立了P4的副本P′4。這個過程會傳播到連結串列的頭部，從P3到P100的每個節點都會被它的副本所取代。
顯然，這是非常昂貴的：刪除塊結構連結列表中很深的塊會觸發所有後續塊的重寫。因此，我們將塊結構表示為一個平衡的二叉樹，在這種情況下，一個塊的刪除只會觸發與樹高度相同數量的塊的建立。
效率：令| MM [l] | 是當前與多對映中的標籤l相關聯的值的數量。換句話說，| MM [l] | 表示l的未刪除值的數量。我們不會在這裡爭論，但是不難發現，塊結構中的塊數量最多為| MM [l] |。由於查詢演算法現在可以使用塊跳過已刪除的值，並且搜尋塊的成本不高，因此查詢的時間複雜度為O（| MM [l] |），這是最佳的。加法運算的複雜度與以前相同，因此也是最佳的。刪除複雜度為O（| v | log | MM [l] |），其中| v | 是要刪除的值的數量。這是因為對於每個刪除的值，新的塊會插入到塊樹中和/或刪除舊的塊會花費（log | MM [l] |）時間。
穩定的複雜性：由於相加操作將值作為連結列表相加（與LSX中相同），所以相加的穩定複雜度為O（| v |）。但是，刪除的穩定複雜度為O（log | MM [l] |），因為可以並行進行在塊樹的同一級別進行的所有修改。
結論
我們討論瞭如何將端到端加密整合到區塊鏈資料庫中，更確切地說，討論了將端到端加密多對映儲存在區塊鏈上的方法。由於多對映具有足夠的表現力來表示鍵值儲存，因此這提供了一種將鍵值儲存儲存在區塊鏈上的方法。我們討論了三種在查詢，新增和刪除效率之間實現不同權衡的EMM構造。但是還有一些有趣的開放問題。
我們發現，當TRX具有最佳的新增/刪除時間複雜度時，TRX具有較差的查詢複雜度。另一方面，PAX實現了良好的查詢複雜性，但穩定化新增/刪除複雜性較差。這引起了以下自然問題：我們能不能設計一個既能做到兩全其美的方案？
我們還在論文中表明LSX和TRX都可以使用打包，這允許將多個元組值儲存在單個事務中。對於允許進行大筆交易的區塊鏈，打包可以提高效能。不幸的是，我們的PAX構造不支援包裝，因此一個自然的問題是：我們可以在PAX中加入打包嗎？
