¿Existe un sistema de prueba de trabajo que requiera significativamente más memoria para generar que para verificar?

Litecoin resiste la aceleración de la GPU mediante el uso de una función hash basada en scrypt que requiere cierta cantidad de memoria para generar y verificar. El problema con esto es que el rparámetro debe configurarse lo suficientemente alto como para que sea difícil usar una GPU, pero lo suficientemente bajo como para que los clientes con poca memoria (es decir, los teléfonos inteligentes) aún puedan verificar bloques de manera eficiente.

¿Existe una prueba de trabajo que requiera significativamente más memoria para generar una prueba de trabajo para un bloque que para verificar que un bloque contiene suficiente prueba de trabajo?

He oído hablar de dos enfoques posibles: compensación de tiempo-memoria con scrypt y un algoritmo hash de teoría de grafos que requiere mucha memoria para encontrar soluciones.

¿Qué quiere decir con la función hash "verificar"? ¿Regenerarlo y comparar?
@amaclin ¿Algo así? He reducido mi pregunta. ¿Es más claro?
No existe tal cosa como "verificar la función hash". PoW verifica que el resultado sea menor que el objetivo. Pero para comprobarlo debemos calcular el valor
@amaclin There is no such thing as "verify hash function" Claro que lo hay. But to verify it we should calculate the valueDi la compensación de memoria de tiempo con scrypt como ejemplo, por lo que es claramente posible.
Litecoin no 'resiste' la GPU. Ni siquiera los ASIC. "Intenté resistir..." tal vez, pero hay rumores de que el creador ya estaba usando una GPU en la presentación. Además: encontrar y verificar un hash es lo mismo, la única diferencia es que al verificar solo necesita hacer el cálculo una vez en lugar de miles de millones de veces.
@Jannes Litecoin doesn't 'resist' GPU. Not even ASICs.Es mejor que Bitcoin, al menos. Si tiene una redacción alternativa, siéntase libre de editar mi pregunta. Also: finding and verifying a hash are the same thing, only difference is that when verifying you only need to do the calculation once instead of billions of times.Soy consciente de que SHA256 es así. ¿Podría haber algún sistema de prueba de trabajo que no sea SHA256 o que no esté basado en hashcash que cumpla con los requisitos que establecí?
@NickODell No hay absolutamente nada "mejor" al respecto... el objetivo de la prueba de trabajo es ser lo más simple posible porque reduce la barrera de entrada a nuevos jugadores (fabricantes de ASIC). Lo que significa menos personas en una posición privilegiada de tener una ventaja injusta sobre los demás (como los propios creadores de la moneda, por ejemplo). No tiene sentido hacer que PoW sea artificialmente más difícil. Por supuesto, los creadores de scamcoin intentan que suene como una ventaja, pero en realidad es todo lo contrario.
@Jannes La barrera de entrada para la minería ASIC no se reduce, dado que las granjas mineras chinas no divulgarán su hardware (y teniendo en cuenta los problemas de suministro con BFL), me inclino a pensar que hay una barrera de entrada extremadamente dispar. a la minería asitica
@Jannes Estás entrando en el ámbito de especular sobre los motivos de los creadores de altcoin, lo cual es increíblemente fuera de tema.
@WizardOfOzzie SI hay una barrera de entrada dispar, solo empeorará si hace que los diseños y los chips sean más complejos. Si hace eso, necesita más personas más inteligentes para diseñarlos, máquinas más caras para fabricarlos, etc.
Relacionado: Lists.randombit.net/pipermail/cryptography/2013-January/… pero probablemente no sea adecuado para el uso de altcoin.

Respuestas (3)

Creo que un proceso de minería que hiciera uso de muestreo estocástico de un gran conjunto de datos cumpliría con los requisitos que ha establecido. La cadena de bloques incluso proporciona un gran conjunto de datos para esto. Por ejemplo, digamos que cada nonce requiere que muestree aleatoriamente la cadena de bloques para seleccionar algunos bytes. Dado que usa muchos nonces durante la minería y no puede predecir qué datos necesitaría de la cadena de bloques, básicamente necesitaría tener toda la cadena de bloques (cualquier conjunto de datos acordado públicamente, en realidad) disponible durante la minería. Luego, la solución se puede verificar con una pequeña muestra de ese conjunto de datos y alguna prueba de que los datos están en el conjunto. Al usar el ejemplo de blockchain, probablemente necesite una cadena de encabezados de bloque y una rama Merkle para los datos de transacción seleccionados.

Otra forma de hacer esto sería usar un gran árbol merkle aleatorio . Digamos que alguien creó un árbol merkle de 2^31 valores aleatorios de 32 bytes. Al tener en cuenta que las ramas de merkle también deben almacenarse, esto es (1 + 2 + 2^2 + 2^3 + ... + 2^31) * 32 bytes, o (2^32-1)*32 ~= 137.4 GBde datos en total. Estos datos están disponibles públicamente para cualquier persona que realmente quisiera descargarlos y verificar la raíz de Merkle. La raíz de merkle se conocería como la raíz de merkle minera, y es una constante bien conocida y acordada. La minería implica muestrear este árbol merkle aleatorio y hashing, y al encontrar una solución exitosa, se proporciona la rama del árbol merkle, lo que demuestra que los datos que se muestrearon están realmente en el árbol merkle acordado públicamente.

En este esquema, se necesitan ~137,4 GB de memoria para minar, pero solo ~1 kB de datos para verificar una solución contra la raíz de merkle acordada públicamente.

Y los números obviamente podrían modificarse aquí para permitir que las personas extraigan sin renunciar a 137,4 GB de su disco duro. Habría que llegar a un equilibrio.

De hecho, me gusta más de esta manera, ahora que lo pienso, porque no tiene el efecto secundario de que la minería puede llevar más tiempo a medida que crece la cadena de bloques. Probablemente podría incluso tomar una instantánea de la cadena de bloques de bitcoin y usarla como un conjunto de datos verificable públicamente. Pero el método de la cadena de bloques esencialmente obliga a los nodos a ser nodos completos también, lo cual es interesante, por lo que es una compensación.

Editar: con una búsqueda rápida, encontré este documento que resuelve esencialmente el mismo problema con un método de muestreo estocástico diferente que involucra la paradoja del cumpleaños. Su solución es interesante porque implica crear su propio conjunto de datos cada vez. Pero esto puede no ser realmente algo bueno, ya que desalienta la reconstrucción de bloques cuando ingresan nuevas transacciones.

http://www.hashcash.org/papers/momentum.pdf

Una discusión relevante de bitcointalk sobre el algoritmo Momentum:

https://bitcointalk.org/index.php?topic=313479.0

Creo que es divertido cómo el aspecto de "impulso" (no poder actualizar Merkle después de que se crea por primera vez) se promociona como la característica definitoria del algoritmo, aunque en realidad es una desventaja bastante significativa, ya que retrasa la confirmación de todas las transacciones por 1 bloque. . También puede exacerbar el problema en el que los mineros no quieren extraer grandes bloques porque tardan mucho en propagarse. es decir, puede ser más rentable continuar minando con su pequeño bloque incluso después de haber oído hablar de un nuevo bloque en la red porque el impulso que ya tiene lo hace más fácil. Creo que el hecho de que el algoritmo PoW de bitcoin no tenga ningún impulso es en realidad una gran característica, ya que permite que las transacciones se confirmen rápidamente.

El uso de un conjunto de datos que no cambia, como en la solución que proporcioné anteriormente, proporciona los requisitos de memoria asimétrica deseados en el trabajo de trabajo/verificación, al mismo tiempo que evita el problema del impulso.

Si la minería se basara en datos en la cadena de bloques, alguien podría insertar datos que parecían aleatorios, pero que en realidad eran altamente comprimibles si conocía alguna clave secreta. Sin embargo, el segundo enfoque parece sólido.
@NickODell, gracias. He editado mi publicación, es posible que también te interese el algoritmo Momentum.
Usar la cadena de bloques para datos al menos obliga a los mineros a ser un nodo completo, eso es al menos una ventaja, supongo. Usar 137 GB de datos aleatorios significa que solo estás esperando que alguien construya un ASIC con 137 GB de RAM y todos los demás están jodidos (toda la resistencia...).
@Jannes Si está construyendo un ASIC con 137 GB de RAM, ¿por qué no hacer que la RAM sea externa, para que pueda obtenerla por menos? Y si el algoritmo depende en gran medida de la memoria RAM, ¿por qué no sustituir el ASIC por una CPU?
@NickODell porque la RAM local siempre es más rápida que la RAM externa y el ASIC siempre es más rápido que la CPU. Ese es todo el punto. No tiene sentido hacer que PoW CPU/GPU sea resistente porque si vale la pena, alguien hará un ASIC para ello. Porque un ASIC es básicamente solo una CPU + RAM con todas las cosas innecesarias (propósito general) recortadas. Para hacerlo más rápido. Al final estás quemando Watts... ese es el punto. La velocidad absoluta no importa (los mismos vatios), ¡pero la velocidad relativa a los demás sí importa! Si necesita ser rico para invertir en una planta ASIC, obtiene una ventaja injusta -> centralización.
@NickODell, el algoritmo ziftrCOIN también usa un algoritmo que requiere más memoria para calcular que para verificar, mediante el uso del árbol merkle justo en el bloque como el árbol merkle que describí en mi respuesta. La ventaja es que puede probar el conocimiento de todos los datos que está extrayendo mientras solo requiere una de las transacciones para probar que un encabezado es válido para un nodo SPV.
@NickODell, mi respuesta ha mostrado 3 formas diferentes de hacer esto, ¿no cumplen con sus requisitos?
@ StephenM347 Los tres tienen problemas diferentes 1) Alguien podría insertar datos de aspecto aleatorio 2) Alguien podría ejecutar varios mineros en paralelo en el mismo conjunto de datos, 3) Tiene los problemas que anotó. Todos son buenos intentos de resolver el problema, pero fracasan por una u otra razón.
¿Una simple búsqueda de ciclos o una búsqueda de colisiones basada en puntos distinguidos no reduciría mucho el costo de memoria del impulso mientras aumenta el costo computacional solo por un pequeño factor?

Dagger está destinado a requerir mucha memoria para crear, pero poca para verificar.

Mi "Ciclo Cuckoo" https://github.com/tromp/cuckoo es una prueba de trabajo teórica de gráfico vinculada a la memoria que es trivial de verificar y, AFAIK, es la única cuyo tiempo de ejecución está dominado por la latencia de la memoria.

¿Pensé que este algoritmo estaba obsoleto? github.com/tromp/cuckoo/issues/2
No; solo el algoritmo de minería original está obsoleto. El nuevo, que utiliza el recorte de bordes como lo sugiere Dave Andersen, ha resistido el ataque hasta ahora. Consulte el LÉAME y el documento técnico para obtener todos los detalles, incluida una comparación con Momentum.
¿Existe un sistema de prueba de trabajo que requiera significativamente más memoria para generar que para verificar?
RespuestasAquíPolítica de privacidad1y, 0v