無上司拍賣
無上司拍賣是去中心化的拍賣，沒有拍賣師。它們解決了當一個參與者被允許在所有其他參與者之後采取行動時可能出現的“最後看”問題。
在無上司的拍賣中，所有參與者必須同時承諾他們的出價。任何違反這一承諾的行為都将導緻可歸因的過錯。出價是門檻值加密的，以避免資訊洩露。
拍賣可以通過将結果送出給區塊鍊來完成，在區塊鍊中，它們可以通過簽名聚合進行有效驗證。出于本文的目的，我們将使用以太坊。
該協定與拜占庭容錯共識協定類似，假設一個預先确定的參與者集，其中超過三分之二的參與者是誠實的。它還要求參與者能夠在一段固定的時間内(比如，兩秒鐘)可靠地互相傳遞消息。如果違反了後一種假設，例如網絡分區，一些誠實的各方可能會收到錯誤但是，假設此類違規行為很少見，我們可以設計故障懲罰，以便将此問題的影響降至最低。
這個設計沒有解決幾個問題。特别是，參與者仍然可以比其他人晚送出投标，因為他們的延遲較低。此外，在這個版本的協定中，為了簡單起見，來自公衆的出價是未加密的。這意味着不誠實的拍賣參與者與信任他們的公衆有最後的聯系。
動機
拍賣在加密貨币中無處不在。計時遊戲、最後檢查和短期審查開始出現，而這個協定至少是為了抵制其中的一些。
我們正在探索如何将其整合到Angstrom的頂部區塊和批量拍賣中，該拍賣通過以共同價格執行訂單，使用單獨的共識機制來保護MEV。
此拍賣的變體可能适用于其他設定，例如：
•如Mike Neuder和Justin Drake所提議的那樣，将PBS拍賣納入像以太坊這樣的L1
•強制執行 UniswapX 或 MEV-share 等訂單流拍賣的公平性
•強化鍊上批量拍賣，就像dYdX讨論的那樣
•去中心化排序器到像 Optimism 這樣的 L2 中
之前的工作
最近在加密拍賣方面有很多出色的工作。例如，請參閱：
• 鍊上拍賣中的審查阻力(2023)，作者：Elijah Fox, Mallesh M. Pai和Max Resnick
• 通過區塊鍊進行可信、最優的拍賣(2023)，作者：Tarun Chitra, Matheus V. X. Ferreira和Kshitij Kulkarni
• 緩解 MEV 的新架構 （2023）作者：dYdX
• 多重性 （2023）作者：二進制性
• 蟬 （2024） 作者：Noemi Glaeser、István András Seres、Loránd Eötvös、Michael Zhu 和 Joseph Bonneau
雖然這方面的大部分工作都解決了審查問題——上司者排除他人交易或出價的能力——但我們還沒有發現任何工作直接解決了最後一次審查的問題——提議者比其他參與者晚很長一段時間插入或取消自己出價的能力。
問題
背景
Zed想每12秒拍賣一個ETH。他成立了一個由他的朋友Alice, Bob, Charlie, 和Dan組成的委員會來管理拍賣。這些參與者将從公衆中收集出價，然後，他們将一起決定他們所見過的最高出價。Zed相信整個團隊，但他認為他們中最多有一個人可能不誠實。
第一次嘗試
一種可能性是在像Tendermint這樣的去中心化共識協定中使用單區塊拍賣。每個參與者将從公衆中收集出價，并送出最高的出價以納入該區塊。然而，Tendermint的特點是一個對區塊内容有完全控制權的區塊提議者。這意味着一個不誠實的投标者可以簡單地審查其他人的出價，并以0的出價赢得拍賣。
為了解決這個問題，我們可以将每次拍賣的持續時間從一個區塊改為兩個區塊。然後，兩個不同的提議者會一個接一個地提出一個包含他們見過的最高出價的區塊。拍賣的最終赢家将是這兩個街區中出價最高者。因為最多有一個提議者是不誠實的，是以這些區塊中至少有一個包含誠實的出價。這是一個很大的進步!
“最後檢視”問題
然而，想象一下，假設不誠實的提議者，比如Bob，是第二個區塊的提議者。
第一個提議者Alice在她的第一個區塊中送出了1萬美元的以太币出價。鮑勃現在有幾秒鐘的時間來決定他想做什麼。他檢視了以太币的價格，發現它剛剛飙升至1.1萬美元。他自己出價10,001美元，并赢得了拍賣，淨賺999美元。
作為一個不誠實的參與者，隻要有利可圖，Bob就會這樣做——也就是說，隻要以太币的價格大于Alice區塊中目前的中标價。這意味着任何向Alice發送出價的人，隻有在以太币的目前價格小于或等于他們的出價時才會得到成交——換句話說，如果交易對他們來說是無利可圖的。即使Bob無法看到其他競标者的出價，由于他能夠比其他人晚幾秒鐘送出自己的出價，他仍然具有資訊優勢。
如果他們是理性的，并且知道發生了什麼，當Bob是第二個提議者時，除了Bob以外的其他競标者将停止競标。在邊際上，這将壓低整體出價，導緻Zed的資金減少。
這就是所謂的“最後檢視”問題，它是MEV的一種形式。因為它與目前其他可容忍的MEV形式非常相似，甚至像Alice, Charlie和Dan這樣的“誠實”參與者也可能受到足夠的誘惑而參與其中，這使得Zed和任何誠實的投标人都處于不利地位。
我們想阻止這種事發生。
解決方案
問題總結
該協定專門用于解決去中心化拍賣中的“最後檢視”問題——即一個參與者可以比其他人有意義地晚點出價或取消他們的出價，而不需要他們自己付出任何代價，進而給他們帶來不公平的優勢。
特别是，我們希望確定所有出價都是在給定的挂鐘時間(例如，12：00 PM)送出的，而不管誰送出的。
大多數區塊鍊共識協定都有一個上司者或提議者提出一個區塊，供其他參與者同意。因為所有其他參與者必須及時将他們的報價發送給上司者，以便上司者将他們包括在内，是以上司者有更長的時間來決定他們自己的報價，給他們最後一次免費的機會。
協定概述
無上司拍賣分三輪得出拍賣結果，并在第四輪中建立一個易于驗證的聚合簽名來驗證它們。任何人都可以将這些簽名結果送出給以太坊以完成拍賣。
該協定還指定了一組易于證明的故障條件。任何人都可以在任何時候送出錯誤證明，并對負責的參與者進行處罰。
性能
正如我們将在下面證明的那樣，該協定通過滿足以下兩個屬性來解決最後一次檢視問題：
1.沒有遲到者：沒有參與者可以在第一輪結束的挂鐘時間之後進行出價。
2.沒有免費選項：任何保留在第一輪後取消選項的參與者都必須提前支付該選項的費用。有效的懲罰措施應該會使這種做法在經濟上不可行。
值得注意的是，一些參與者可能比其他人有更低的延遲，是以在第一輪中能夠比其他人晚采取行動。
假設
我們假設在3f+1個參與者中，2f+1是“誠實的”(與拜占庭容錯共識協定要求的門檻值相同)。
我們的同步假設是，所有誠實的參與者都能夠互相發送消息，這些消息保證在某個固定的時間内到達，比如 1 秒。這個假設不需要為了整體安全或活躍性而成立（確定我們不會産生互相沖突的拍賣結果，并且拍賣最終會發生），因為我們依賴以太坊來獲得這些屬性。我們将在下面讨論當違反此假設時會發生什麼。
我們還假設參與者有同步的時鐘，就像在以太坊中一樣。
拍賣
第一輪-發送出價
每個參與者發送一個簽名出價給其他參與者。
這些出價是門檻值加密的，這意味着它們是使用公鑰加密的，該公鑰可以由任何 f+1 或更多參與者的集合解密（這将在第 3 輪中發生）。這意味着沒有參與者能夠在送出自己的出價之前看到任何其他參與者的出價值，是以無法利用該出價的知識。有幾種方法可以實作這種加密，但細節超出了本文的範圍-參見例子vetKeys。
誠實的參與者必須送出他們從公衆那裡收到的最高出價。然而，由于來自公衆的出價在這種設計中沒有被加密，一個不誠實的參與者可以選擇出價比他們從公衆那裡收到的出價高出一小部分。公衆可以通過将他們的出價隻發送給一個他們信任的參與者來解決這個問題。加密解決方案是可行的，但會增加複雜性。
第2輪-發送出價集
每個參與者都将他們在第一輪收到的所有加密出價的簽名集(一個“出價集”)，包括他們自己的，傳給所有其他參與者。所有參與者現在都有一個“出價視圖”，或者從其他參與者那裡收到的一組出價集。
誠實的參與者隻有在第一輪出價結束之前到達時，才會将另一個參與者的出價包含在他們的出價集中，由參與者的同步時鐘決定。是以，如果一個出價包含在誠實參與者的出價集中，則它必須在第一輪結束時發送。由于最多有 f 個不誠實的參與者，如果一個出價出現在 f+1 個或多個出價集中，其中至少有一個來自誠實的參與者，并且該出價必須在第一輪結束時發出。
任何誠實的參與者都可以使用這些資訊來解決拍賣問題。但是，該協定無法知道哪些參與者是誠實的。是以，我們需要再來一輪。
第3輪-發送出價視圖和門檻值解密資訊
每個參與者都将他們在第二輪中收到的所有出價集(他們的“出價視圖”)，包括他們自己的出價集，告訴所有其他參與者。
除了它們的出價視圖外，它們還發送了它們在上面讨論的門檻值加密方案中使用的解密資訊。其中f+1的任何集合都足以解密所有加密的出價。
就帶寬而言，這是最昂貴的步驟：每個參與者必須向O(n)個參與者發送O(n)個出價集，其中包含O(n)個出價，在最壞的情況下，總帶寬為O(n^3)。然而，每個人都應該從其他參與者那裡獲得相同的實際出價(在沒有代價高昂的模棱兩可錯誤的情況下，下面将讨論)，并且給定集合中的存在或不存在或出價隻是單個位。此外，如果每個人都是誠實的，并且網絡正常運作，那麼所有參與者都應該在他們的出價集中擁有每個出價，并且每個參與者都應該擁有其他參與者的出價集。是以，如果參與者隻發送消息表明他們丢失了哪些出價或出價集，那麼在理想情況下，他們隻需發送一個 (“一切都在這裡”)或幾個bit (“集合3丢失了出價13，其他一切都好”)。
此時，每個參與者都應該從誠實的參與者那裡獲得 2f+1 的出價視圖，并能夠對其進行解密。如果有f+1個這樣的人，他們就可以證明他們至少有一個誠實參與者的出價視圖，足以解決競價問題。
理論上，該協定可以在此結束，任何參與者都可以向區塊鍊送出f+1出價視圖以進行最終确定。然而，由于空間複雜性和驗證成本，将2f+1出價視圖送出給以太坊并進行驗證是不切實際的(也許在自定義鍊上更可行)。
是以，我們需要再進行一輪，以便參與者能夠以一種易于在鍊上驗證的方式驗證拍賣結果。
第4輪-驗證出價視圖
為了保證我們想要的性能，我們想要輕松地驗證拍賣的中标價是至少一個有效出價視圖的中标價，并且它大于或等于至少一個誠實參與者視圖的中标價。第4輪的設計就是為了實作這一點。
每個參與者都會檢查其所有解密的出價視圖。如果出價至少存在于構成出價的出價集中的 f+1 個出價集中，則該出價_valid _in在出價視圖中是有效的。視圖的中标是該視圖中的最高有效出價。
如果給定出價視圖中的出價大于或等于該參與者自己的出價視圖中的出價，則該參與者提名該出價。
每個參與者為他們提名的每個出價建構一個門檻值簽名，并将所有這些出價和簽名的集合傳遞給其他參與者。注意，這在空間複雜度(每個視圖最多一個簽名)和帶寬複雜度上僅為O(n^2)。事實上，如果所有參與者都是誠實的，并且沒有網絡困難，相同的出價将赢得每個出價視圖，是以每個參與者将隻提名單個出價。
結算
任何至少有f+1個參與者以這種方式簽名的出價都被确認。請注意，在某些情況下，可能會确認兩個或更多不同的出價(盡管這意味着至少有一個參與者在第一輪中失敗，是以沒有獲得免費選項)。
任何确認的出價都可以送出到以太坊區塊鍊，在那裡可以通過簡單的簽名驗證進行驗證。送出者可能會從協定中收到一筆小額付款，以償還他們的gas費用。在以太坊上隻接受一個已确認的出價，如果存在多個已确認的出價，則允許所有參與者就中标達成共識。
以太坊區塊提議者可能會審查拍賣，而不将其包含在區塊中。這甚至可能連續發生幾個區塊。在這種情況下，送出目前區塊拍賣結果的參與者也必須送出所有缺失區塊的拍賣結果。我們将在下面讨論這如何改變錯誤懲罰。
錯誤
基本
隻要有證據，任何人都可以異步送出錯誤證明，這很可能導緻違規參與者的質押全部或部分被削減。報告錯誤證明的參與者可能會收到一部分被削減的質押，作為報告的獎勵。
當參與者在不同的出價集中出現沖突的出價或在不同的出價視圖中出現不同的出價集時，就會出現歧義錯誤。因為這種含糊其辭要麼是故意的，要麼至少是由于用戶端問題而不是網絡問題造成的，是以對它的懲罰可能相當嚴厲，包括全面削減。
當參與者的出價在某些 f+1 出價集集合中不存在時，就會發生缺席錯誤。這可能意味着參與者不誠實，試圖退出他們在第一輪發出的出價，或者，希望很少，參與者是誠實的，并且網絡被分區了。
缺席錯誤的處罰應設定為高于能夠取消出價的選擇權。這需要與真正的網絡故障頻率相平衡，并且最終是一個定量問題。在最壞的情況下，有一個不斷更新的懲罰系統可以限制重複犯罪的頻率，并将這種行為保持在最低限度。使用此協定的任何系統都可以監控這些類型的故障相對于已驗證的網絡故障發生的頻率，并相應地調整懲罰。
審查拍賣的缺陷
正如我們将在下面進一步讨論的那樣，拍賣參與者可以通過在第一輪中犯錯誤來保留在下一輪中取消出價的選擇權。
任何這樣做的參與者都可以通過賄賂以太坊區塊提議者來審查以太坊區塊拍賣的拍賣結果，進而為自己創造更多的可選性，可能會連續幾次，然後最終送出如上所述的“結算”。為了保持“無自由選擇權”的性質，我們在每次審查給定拍賣時線性增加錯誤懲罰，以便原始錯誤者必須為每個錯過的區塊的期權值付費。
如果一個誠實的參與者由于網絡問題而無意中犯了錯誤，有人可以使用這些不斷增加的懲罰來破壞他們，但破壞者必須支付審查區塊的費用。
減輕意外故障
如果任何參與者的出價集中缺少f+1個或更多的出價，我們通過假設知道他們至少缺少一個誠實參與者的出價，因為最多f個參與者是不誠實的。是以，為了計算缺席錯誤，我們可以忽略這個參與者的出價集，因為他們要麼是不誠實的，要麼是發生了網絡分區。這應該可以減少主要網絡分區産生的故障數量。
證明
i. 沒有遲到者：任何參與者都必須在第 1 輪中将他們的出價發送給至少一名誠實的參與者，以便它在任何出價視圖中都有效，進而有機會獲勝
假設在第一輪中，一些參與者沒有将他們的出價發送給任何誠實的參與者。因為有2f+1個誠實的參與者，這個出價在第二輪中最多出現在(3f+1)-(2f+1)=f個出價集合中，這不足以使它在任何出價視圖中都有效。
如果在任何出價視圖中無效，它就不能成為任何出價視圖中的中标，并且沒有誠實的參與者會提名它。由于f+1個參與者必須為它提名一個出價才能赢得拍賣，這些參與者中至少有一個必須是誠實的，并且這個出價無法獲勝。
ii. 在沒有網絡分區的情況下，在第一輪中向所有參與者發送出價的參與者不會産生錯誤
假設誠實的參與者是Alice。
她将她的出價發送給第一輪的所有3f+1參與者。因為其中2f+1人是誠實的，每個誠實的參與者都會把自己的出價發給其他誠實的參與者。這意味着每個誠實的參與者都會在他們收到的出價集（包括他們自己的出價集）中看到她的出價。
由于最多有3f+1個出價集，她的出價将在最多(3f+1)-(2f+1)=f個出價集中缺席，是以不會産生錯誤。
iii. 在沒有網絡分區的情況下，如果參與者在第 1 輪中向 f+1 或更多誠實的參與者發送出價，則該參與者将赢得拍賣，前提是這是在第 1 輪中送出給任何誠實參與者的最高出價
假設Alice在第1輪中向f+1個誠實的參與者發送了她的出價。然後，這些誠實的參與者将把她的出價包含在他們的出價集中，并将其發送給其他參與者。這意味着2f+1個誠實的參與者中的每一個都在f+1個出價集合中看到了Alice的出價，是以認為她的出價在他們的出價視圖中是有效的。
根據假設，Alice的出價是第1輪中所有誠實參與者的最高出價。是以她的出價在每個誠實的參與者眼中都是赢家，每個誠實的參與者都會提名她。此外，根據上述證明(i)，沒有更高的出價在任何出價視圖中都是有效的，是以沒有誠實的參與者會提名它。這意味着Alice的出價是唯一獲得至少f+1項提名的出價，并且必須赢得拍賣。
請注意，如果兩個這樣的投标人與最高出價并列，則存在邊緣情況。我們可以根據門檻值解密的随機性來判定。
iv. 任何參與者必須在第1輪中向至少f+1名誠實的參與者發送他們的出價，以避免産生錯誤
假設參與者将其出價發送給第1輪誠實參與者中的k
然後，這個出價将出現在誠實的參與者發送的k個出價集中。
每個誠實的參與者将從其他誠實的參與者(包括他們自己)那裡獲得2f+1個出價集，其中隻有k個包含有問題的出價，是以2f+1-k>=2f+1-f=f+1個出價集将不包含有問題的出價，這足以産生故障。
請注意，即使網絡被分割，如果誠實的參與者確定所有其他參與者都收到了他們的出價集，并重新發送出價集，直到收到确認，一旦網絡恢複，就會産生故障。
v. 沒有免費選項
通過(iii)，任何在第1輪中向f+1或更多誠實參與者發出出價的參與者将赢得拍賣，如果它是第1輪中向任何誠實參與者發出的最高出價，無論他們後來做了什麼。在第(iv)條中，任何在第1輪中向少于f+1個參與者發送出價的參與者将被判錯誤(是以将被處罰)。是以，任何希望保留取消選擇權的人都必須為此付費。
結論
去中心化拍賣直到最近才開始得到廣泛應用，帶來了許多新問題。本文針對的是一個我們在其他地方沒有看到解決的問題。我們希望并期待會出現更多更好的解決方案——理想情況下是那些更簡單，更少的回合，或者對同步或誠實參與者數量等問題的假設更少的解決方案。
盡管這種設計并不能解決所有問題，但它确實解決了去中心化拍賣中固有的一些常見的“最後檢視”問題。我們希望它本身可以有一些用處，幫助其他人解決類似的問題，甚至可以改進或重新混合成更好的東西。