Por qué su mecanismo de subasta podría ser susceptible a la colusión

Tabla de enlaces

Resumen y 1. Introducción

1.1 Nuestras contribuciones

1.2 TFM Incentive-compatibilidad Notiones: una hoja de trucos

2. Definiciones

   2.1 Mecanismo de tarifas de transacción

   2.2 nociones de compatibilidad de incentivos

3. Preliminar: el lema de Myerson

4. Calentamiento: imposibilidad de UIC + MIC + SCP world para mecanismos deterministas

5. Imposibilidad de UIC + MIC + SCP world para mecanismos aleatorios y 5.1 Hoja de ruta de prueba

   5.2 Pruebas formales

6. Viabilidad e imposibilidad de UIC + MIC + OCA a prueba de

   6.1 Un mecanismo no tradicional con UIC + MIC + OCA a prueba de

   6.2 Imposibilidad de UIC + MIC + OCA a prueba de mecanismos veraz

7. Cómo eludir las imposibilidades y 7.1 permitiendo que la estrategia globalmente óptima coordine

   7.2 Permitir que la estrategia globalmente óptima genere múltiples ofertas

   7.3 Respinación de reglas de inclusión y 7.4 discusiones y preguntas abiertas sobre el uso de la criptografía

8. Principio de revelación estática para mecanismos de tarifas de transacción

   8.1 Principio de revelación estática: reglas de licitación que producen una sola oferta

   8.2 Principio de revelación estática: permitiendo reglas de licitación que generan múltiples ofertas

A. Comparación de nociones de resiliencia de colusión

Referencias

Una comparación de nociones de resiliencia de colusión

Lema A.1. La subasta incluso anterior satisface SCP world pero no a prueba de OCA.

Observe que si la estrategia de licitación racional individualmente σ genera una sola oferta o múltiples ofertas es importante. Si requerimos que σ solo genere un solo actual como definimos en la definición 6, no existe TFM no trivial que pueda satisfacer la resistencia de la UIC, MIC y OCA como lo demostramos en el Teorema 6.9. Sin embargo, si permitimos que σ genere múltiples ofertas, obtenemos una viabilidad en la Sección 7.2.

Cuando analizamos si un TFM satisface C-SCP para algunos C, 1-SCP es el requisito más débil, ya que C ‘-Scp siempre implica C-SCP para cualquier C’> C por definición. Curiosamente, aun así, 1-SCP es incomparable con SCP world y a prueba de OCA. Las relaciones entre 1-SCP, SCP world y a prueba de OCA se representan en la Figura 1.

Explicamos la Figura 1 con más detalle a continuación:

A continuación, presentamos las subastas (algo artificiales) para construir las contraejemplos.

Lema A.2. La subasta de pago anterior satisface la prueba world de SCP y OCA. Sin embargo, no satisface 1-SCP.

Lema A.3. La subasta de descuento anterior satisface 1-SCP. Sin embargo, no satisface SCP world o a prueba de OCA.

Ahora, mostramos que el mecanismo no satisface la prueba de OCA. Think about un escenario en el que haya 10 usuarios cada uno con el valor verdadero r. Sin inyectar ninguna oferta falsa, el pago más bajo posible para cada usuario es f (10) = R, por lo que el bienestar social es como máximo 0. Sin embargo, si la coalición world inyecta una oferta falsa, el pago de todos más bajará a F (11) = R/2. En este caso, el bienestar social se convierte en 10R-11R/2 = 9R/2> 0. Por lo tanto, el mecanismo no satisface la prueba de OCA.

El mecanismo tampoco satisface SCP world ya que la regla de licitación solo genera un solo actual. Si el mecanismo satisfizo el SCP world, la coalición world podría elegir la regla de licitación sugerida como la estrategia de licitación racional individualmente σ para maximizar el bienestar social. Dado que el mecanismo no satisface la prueba de OCA, tampoco puede satisfacer el SCP world.

Referencias

[ACH11] Gilad Asharov, Ran Canetti y Carmit Hazay. Hacia una vista teórica del juego de la computación segura. En Eurocrypt, 2011.

[ADGH06] Ittai Abraham, Danny Dolev, Rica Gonen y Joseph Halpern. La informática distribuida se encuentra con la teoría del juego: mecanismos robustos para el intercambio secreto racional y el cálculo multipartidista. En Podc, 2006.

[AL11] Gilad Asharov y Yehuda Lindell. Dependencia de la utilidad en el intercambio secreto racional correcto y justo. Journal of Cryptology, 24 (1), 2011.

[BCD+] Vitalik Buterin, Eric Conner, Rick Dudley, Matthew Slipper e Ian Norden. Propuesta de mejora de Ethereum 1559: Cambio del mercado de tarifas para la cadena ETH 1.0. https://github.com/ethereum/eips/blob/grasp/eips/eip-1559.md.

[BEOS19] Soumya Basu, David A. Easley, Maureen O’Hara y Emin G¨un Sirer. Hacia un mercado de tarifas funcionales para criptomonedas. Corr, ABS/1901.06830, 2019.

[BGR23] Maryam Bahrani, Pranav Garimidi y Tim Roughgarden. Diseño del mecanismo de tarifa de transacción con productores de bloques activos. Preimpresión ARXIV ARXIV: 2307.01686, 2023.

[CCWS21] Kai-Min Chung, Th. Hubert Chan, Ting Wen y Elaine Shi. La justicia teórica del juego cumple con los protocolos de varias partes: el caso de la elección del líder. En cripto. Springer-Verlag, 2021.

[CGL+18] Kai-Min Chung, Yue Guo, Wei-Kai Lin, Rafael Cross y Elaine Shi. Notas teóricas del juego de equidad en el lanzamiento de monedas de varias partes. En TCC, volumen 11239, páginas 563–596, 2018.

[CMW23] Davide Crapis, Ciamac C Moallemi y Shouqiao Wang. Tarifas dinámicas óptimas para los recursos blockchain. Preimpresión ARXIV ARXIV: 2309.12735, 2023.

[CS23] Hao Chung y Elaine Shi. Fundamentos del diseño del mecanismo de tarifas de transacción. En Actas del Simposio ACM-SIAM anual 2023 sobre algoritmos discretos (SODA), páginas 3856–3899. Siam, 2023.

[DR07] Yevgeniy Dodis y Tal Rabin. Criptografía y teoría de juegos. En AGT, 2007.

[EFW22] Meryem Essaidi, Matheus vx Ferreira y S. Matthew Weinberg. Subastas creíbles, a prueba de estrategias, óptimas y limitadas de ítems de ronda esperada para todas las distribuciones. En Mark Braverman, editor, 13º Innovaciones en la Conferencia Teórica de Ciencias de la Computación, ITCS 2022, 31 de enero – 3 de febrero de 2022, Berkeley, CA, EE. UU., Volumen 215 de Lipics, páginas 66: 1–66: 19, 2022.

[FMPS21] Matheus vx Ferreira, Daniel J. Moroz, David C. Parkes y Mitchell Stern. Mecanismos dinámicos de precio postal para el mercado de tareas de transacción blockchain. Corr, ABS/2103.14144, 2021.

[FW20] Matheus vx Ferreira y S. Matthew Weinberg. Subastas creíbles, veraces y de dos rondas (óptimas) a través de compromisos criptográficos. En Peter Biro, Jason D. Hartline, Michael Ostrovsky y Ariel D. Procaccia, Editores, EC ’20: La 21ª Conferencia de ACM sobre Economía y Computación, Digital Occasion, Hungría, 13-17 de julio, 2020, Páginas 683–712. ACM, 2020.

[GKM+13] Juan A. Garay, Jonathan Katz, Ueli Maurer, Björn Tackmann y Vassilis Zikas. Diseño de protocolo racional: criptografía contra adversarios impulsados por incentivos. En FOCS, 2013.

[GKTZ15] Juan Garay, Jonathan Katz, Björn Tackmann y Vassilis Zikas. ¿Qué tan justo es tu protocolo? Un enfoque basado en utilidad para la optimización del protocolo. En Podc, 2015.

[GLR10] Ronen Gradwohl, Noam Livne y Alon Rosen. Racionalidad secuencial en protocolos criptográficos. En FOCS, 2010.

[GTZ15] Juan A. Garay, Björn Tackmann y Vassilis Zikas. Cálculo distribuido justo de funciones reactivas. En disco, volumen 9363, páginas 497–512, 2015.

[GY22] Yotam Gafni y Aviv Yaish. Mecanismos de tarifas de transacción codiciosas para mineros (no) miopes. Preimpresión ARXIV ARXIV: 2210.07793, 2022.

[GY24] Yotam Gafni y Aviv Yaish. Barreras a los mecanismos de tarifas de transacción resistentes a la colusión. Preimpresión ARXIV ARXIV: 2402.08564, 2024.

[HT04] Joseph Halpern y Vanessa Teague. Compartir en secreto racional y cálculo multipartidista. En Stoc, 2004.

[Kat08] Jonathan Katz. Teoría de juegos y criptografía de puente: resultados recientes y direcciones futuras. En la Conferencia de la Teoría de la Criptografía, páginas 251–272. Springer, 2008.

[KKLP23] Aggelos Kiayias, Elias Koutsoupias, Philip Lazos y Giorgos Panagiotakos. Mecanismos escalonados para tarifas de transacción blockchain. Preimpresión ARXIV ARXIV: 2304.06014, 2023.

[KMSW22] Ilan Komargodski, Shin’ichiro Matsuo, Elaine Shi y Ke Wu. log*-Spherical gameoréticamente la elección del líder de truthful. En Crypto, 2022.

[KN08] Gillat Kol y Moni Naor. Criptografía y teoría de juegos: diseño de protocolos para intercambiar información. En TCC, 2008.

[LRMP23] Stefanos Leonardos, Daniel Reijsbergen, Barnabe Monnot y Georgios Piliouras. Optimización a pesar del caos en los mercados de tarifas. En la Conferencia Internacional sobre Criptografía Financiera y Seguridad de Datos, páginas 346–362. Springer, 2023.

[LSZ19] Ron Lavi, o Sattath, y Aviv Zohar. Rediseñando el mercado de tarifas de Bitcoin. En la Conferencia World Large Net, WWW 2019, páginas 2950–2956, 2019. [Mye81] Roger B. Myerson. Diseño de subasta óptimo. Matemáticas. Operación Res., 6 (1), 1981.

[Ndi23] Abdoulaye ndiaye. PRECIO DE BLOCKchain versus controles de cantidad. Controles de cantidad (27 de julio de 2023), 2023.

[OPRV09] Shien Jin Ong, David C. Parkes, Alon Rosen y Salil P. Vadhan. Justicia con una minoría honesta y una mayoría racional. En TCC, 2009.

[PS17] Rafael Cross y Elaine Shi. Fruitchains: una blockchain justa. En Podc, 2017.

[Rou20] Tim Roughgarden. Diseño del mecanismo de tarifa de transacción para la cadena de bloques Ethereum: un análisis económico de EIP-1559. Manuscrito, 2020.

[Rou21] Tim Roughgarden. Diseño del mecanismo de tarifa de transacción. En EC, 2021.

[SCW23] Elaine Shi, Hao Chung y Ke Wu. ¿Qué puede hacer la criptografía para el diseño del mecanismo descentralizado? En ITCS, volumen 251 de Lipics, páginas 97: 1–97: 22. Schloss Dagstuhl – Leibniz -Zentrum Fur Informatik, 2023.

[TY23] Wenpin Tang y David D Yao. Mecanismo de tarifa de transacción para el protocolo de prueba de estaca. Preimpresión ARXIV ARXIV: 2308.13881, 2023.

[WAS22] Ke Wu, Gilad Asharov y Elaine Shi. Una caracterización completa del lanzamiento de monedas múltiples gametheoréticamente justas. En Eurocrypt, 2022.

[WSC24] Ke Wu, Elaine Shi y Hao Chung. Maximizar los ingresos del minero en el diseño del mecanismo de tarifas de transacción. En Venkatesan Guruswami, editor, 15º Innovaciones en la Conferencia Teórica de Ciencias de la Computación (ITCS 2024), 2024.

[XFP23] Matheus Venturyne Xavier Ferreira y David C Parkes. Diseño de intercambio descentralizado creíble a través de reglas de secuenciación verificable. En Actas del 55º Simposio ACM anual sobre la teoría de la computación, páginas 723–736, 2023.

[Yao] Andrew Chi-Chih Yao. Un análisis de incentivos de algunos diseños de tarifas de bitcoin (charlas invitadas). En ICALP 2020.

[ZCZ22] Zishuo Zhao, Xi Chen y Yuan Zhou. Mecanismo bayesiano-incentivo-incentivo para la asignación de tarifas de transacción blockchain. 2022.