Abstract as per original application
(English/Chinese): |
This project will investigate distributed protocols that securely realize mechanisms for various allocation and selection problems among self-serving agents. In blockchain applications, an assignment protocol enables fair distribution of goods or chores among agents without any trusted central authority, and a selection protocol lets investors with conflicting interests decide which combination of crowdfunding projects to sponsor.
In the literature, deterministic notions of fairness have been considered, but sometimes randomness is necessary. For instance, in the lottery problem, which is a special case of both assignment and selection problems, one prize is given to exactly one agent. The only reasonable mechanism is to select one agent uniformly at random as the winner. However, without a trusted authority, the agents themselves are responsible for generating the randomness in a distributed protocol. Unfortunately, standard cryptographic approaches such as secure multi-party computation require a majority of the agents to be honest, which is not a realistic assumption, because every agent might deviate from the protocol to increase its utility.
Nevertheless, the lottery problem can be solved by the tournament tree protocol, which employs a commitment scheme based on standard assumptions such as one-way functions. Even though one cannot prove security in the strongest sense that the winner is unbiased, the tournament tree satisfies some game theoretic notions of security. For example, an honest agent following the protocol will be guaranteed at least the same probability of winning, even if all other agents conspire against it. Moreover, agents forming a coalition also cannot increase their combined chance of winning.
Inspired by this framework, we will extend the game theoretic notions of security to protocols solving more general assignment and selection problems. However, unlike the lottery problem in which all agents have the same preference, it is known that the more complicated problem structure implies some impossibility results. For instance, even with a trusted authority, there is no mechanism for a general assignment problem that can achieve all the following properties simultaneously: truthfulness, Pareto optimality, equal treatment. Hence, even formulating the right security notions for protocols realizing the mechanisms for such problems is a challenging task.
Finally, to have practical impacts, our protocols will also achieve communication efficiency. Since our preliminary work shows that the tournament tree protocol has optimal round complexity under some security requirement, we will explore approximate notions of security, and design protocols that have desirable tradeoffs between security and communication efficiency.
本課題將會進行關於自利性代理分配與選擇問題之安全實現機制的分佈式協議研究。在區塊鏈應用場景中，一個分配協議能夠在不依賴可信中央機構的情況下將物品或工作任務公平地分配予每一位代理，而選擇協議使得有利益衝突的投資者們作出對哪一眾籌組合進行贊助的決定。在文獻中，關乎公平的確定性概念已有所研究，不過，隨機性在一些情況下仍屬必要。例如，彩票問題作為一個結合分配與選擇問題的特殊例子，其規定一份獎品只能分配予僅一名代理。唯一公平並且合理的機制便是以同等機率隨機地抽選一名代理作為其得獎者。而在可信中央機構缺失的情況下，則需要由這些代理在分佈式協議中擔任生成該隨機性的角色。然而，標準的密碼學方法（如安全多方計算）要求參與協議的代理中有絕大部分代理會如實地執行協議。這個假設並不切合實際，因為每一名代理都有可能會為了增加自己的利益而背離協議。然而，彩票問題可以通過採用基於標准假設（例如單向函數）的承諾方案的競賽樹協議解決。儘管競賽樹協議不能證明獲勝者是無偏的這一事件在最強意義上的安全性，但它可以滿足博弈論中的一些安全性概念。例如，即使所有其他代理都密謀反對遵守協議的誠實代理，誠實代理都將至少有與協議保障的相同獲勝概率。此外，代理們組成聯盟也不能增加他們獲勝的總概率。受這個框架啟發，我們將把博弈論中的安全性概念擴展到解決更一般的分配和選擇問題的協議上。然而，與所有代理都具有相同偏好的彩票問題不同的是，更複雜的問題結構意味著一些不可能的結果。例如，即使有受信任的機構，也沒有機制可以為普通的分配問題同時實現以下的所有屬性：真實性，帕累托最優，平等對待。因此，即使為實現此類問題的機制的協議制定正確的安全性概念都是一項具有挑戰性的任務。最後，為了產生實際影響，我們的協議還將實現通信效率。由於我們的初步工作已經表明競賽樹協議在某些安全性要求下具有最佳的輪次復雜度，我們將探索近似的安全性概念，並且設計在安全性和通信效率之間具有理想平衡的協議。
|
