¿Hay algún algoritmo de prueba de trabajo estocásticamente dependiente?

En bitcoin, la probabilidad de descubrir un bloque en el hash X-ésimo es el mismo 1 que en el hash Y-ésimo. Como tal, la probabilidad de descubrimiento es estocásticamente dependiente .

¿Existen algoritmos de prueba de trabajo que sean estocásticamente dependientes ? Los mineros que usan uno pueden no tener idea de qué tan cerca están de un descubrimiento, pero saben que se están "acercando".

Siga leyendo si desea una descripción rápida y sucia de por qué creo que tal algoritmo podría ser interesante:

Una consecuencia de la independencia estocástica de bitcoin es que cada vez que un minero descubre un bloque, ninguno de los otros mineros de la competencia está "más cerca" de redescubrir el mismo bloque (con un hash diferente pero válido que también resuelve la dificultad). Por supuesto, es natural entonces que Bitcoin no proporcione ningún incentivo/recompensa por redescubrir bloques, ya que es mejor gastar esa prueba de trabajo intentando descubrir el bloque más nuevo. Sin embargo, desafortunadamente, un atacante con suficiente poder de hashing y tiempo tiene buenas posibilidades de vencer a la competencia varias veces seguidas; por eso se dice que para estar seguro debe esperar 6 confirmaciones, lo que equivale a una hora de tiempo de espera de la transacción. Podríamos decir que en bitcoin las confirmaciones son seriales .

Por el contrario, la prueba de trabajo estocásticamente dependiente podría permitir la implementación eficiente de procesos paralelos .confirmaciones; lo que reduce en gran medida el tiempo de espera de la transacción, ya que se puede esperar que los redescubrimientos sigan poco después del primer descubrimiento de un bloque. Suponga que una criptomoneda usa tales pruebas para recompensar no solo el primer descubrimiento de un bloque, sino también la primera X de sus redescubrimientos. El receptor del pago solo necesita verificar que la transacción figura en todos los descubrimientos del bloque (o al menos en un porcentaje lo suficientemente alto). Idealmente, la cantidad de poder de hash que necesita un atacante para realizar redescubrimientos debería ser la misma que para el descubrimiento inicial (crecer linealmente). Estos hashes de redescubrimiento podrían registrarse de la misma manera que las transacciones, al incluirse por una tarifa/recompensa en un bloque secundario.

1 En realidad, la probabilidad aumenta ligeramente cuando aún no se han descubierto bloques, y solo se altera un mínimo fijo de bits, como cuando solo se aumenta el campo nonce; pero la diferencia es tan pequeña que no importa, dada la cantidad astronómica de posibles hashes que resuelven la dificultad actual.

No creo que su nota al pie sea correcta, porque no está garantizado que alguna vez encontrará una solución. Sin embargo, siéntase libre de explicar y demostrar que estoy equivocado.

Respuestas (2)

¿Existen algoritmos de prueba de trabajo que sean estocásticamente dependientes?

Sí. Otra idea similar a la que Nick describió:

Agregue 8 bytes adicionales al final de cada transacción al hacer el árbol Merkle, en un campo llamado nEffort. El nBitscampo del encabezado describe la cantidad total de trabajo que se debe realizar (en promedio) en el bloque. Dividir ese trabajo por el número de transacciones en el bloque, y luego puede minar cada transacción individualmente alterando nEfforthasta que la hoja del árbol merkle tenga un valor lo suficientemente bajo. Tenga en cuenta que esto no reemplaza los ID de transacciones, sería esencialmente solo un campo adicional de cada elemento de hoja del árbol merkle.

Para verificar el trabajo, asegúrese de que cada hoja del árbol Merkle cumpla con el parámetro dificultad/Número_de_transacciones.

Las desventajas de esto:

  • Un encabezado de bloque no se puede verificar sin tener todos los datos de la transacción, lo que obviamente es muy limitante para los nodos SPV donde la seguridad de sus transacciones se basa en cuántos bloques lo incluyen.
  • Esto también podría facilitar los gastos dobles. Simplemente extraiga una transacción que le dé monedas a usted mismo y libérela después de enviar monedas a otra persona.
  • Desincentivaría agregar nuevas transacciones a su bloque, ya que cada nueva transacción significaría que todas las transacciones previamente extraídas cuentan con menos trabajo.

Probablemente no sea una buena idea, pero es otra forma de hacer una prueba de trabajo estocásticamente dependiente.

Entonces el bloque no cumpliría con la prueba de trabajo. Al igual que en Bitcoin, podría retransmitir un bloque y reemplazar una transacción, pero todos la rechazarían... Creo que el problema del que hablas es el reemplazo. En el método que propuse, podría reemplazar una transacción en un bloque con otra transacción minada, y aún así se validaría. Por lo tanto, no es un método PoW viable.
¡No viste nada! Pensé en un mejor ataque: si veo su bloque en la red, ¿no podría reemplazar la base de monedas de su bloque con mi propia base de monedas, suponiendo que tuviera suficiente trabajo adjunto?
@NickODell Jaja, eso es mejor. Pensé en una solución, y luego en una forma de romper mi solución, así que voy a dejarlo ahora, obviamente esto nunca funcionaría. :PAG

Los mineros que usan uno pueden no tener idea de qué tan cerca están de un descubrimiento, pero saben que se están "acercando".

Sí, esto es posible.

En lugar de requerir un encabezado de bloque con dificultad A, podría requerir 16 encabezados de bloque con dificultad A/16. Esto haría posible averiguar qué tan avanzado está en el proceso.

Por el contrario, la prueba de trabajo estocásticamente dependiente podría permitir la implementación eficiente de confirmaciones paralelas; lo que reduce en gran medida el tiempo de espera de la transacción, ya que se puede esperar que los redescubrimientos sigan poco después del primer descubrimiento de un bloque. Suponga que una criptomoneda usa tales pruebas para recompensar no solo el primer descubrimiento de un bloque, sino también la primera X de sus redescubrimientos.

Eso es posible también. Puede hacer esto haciendo que cada bloque en Bitcoin tenga 1 o más padres. Necesitaría algún tipo de regla de vía para decidir qué transacciones mantener en un bloque de combinación (ya que algunas inevitablemente entrarían en conflicto).

Inconvenientes de los dos cambios anteriores:

  • Normalmente, un minero incluye transacciones tan pronto como se entera de ellas. Incluir una transacción no significa que pierda ningún progreso. Pero si te estuvieras acercando, no querrías abandonar eso.
  • Solo los X mineros y pools de minería más fuertes permanecerían en el negocio. Es mejor que todos los demás no se molesten con la minería.
  • Los nodos completos necesitarían X veces más ancho de banda para verificar bloques. Una vez que se verificaron los bloques, también se necesitaría almacenamiento adicional. Si los bloques fueran muy diferentes, podría ocupar X veces más espacio de almacenamiento. Si los bloques fueran idénticos, serían solo ~ 350 bytes adicionales por bloque (coinbase y encabezado de bloque).
En el último punto, ¿no te refieres a los nodos SPV? Además, no sería exactamente X veces, ya que algunos de los datos del encabezado se pueden reutilizar.
Esto podría funcionar si el conjunto de TX extraído fuera solo para agregar. Y estoy de acuerdo con @MeniRosenfeld, parece que solo sería X veces el almacenamiento para los nodos SPV, pero marginalmente más almacenamiento para los nodos completos. Un aspecto interesante de esta propuesta es que se incentivaría a los pools para averiguar qué tan avanzados están otros pools. es decir, si otro grupo tiene 13/16 encabezados resueltos pero su grupo (mismo poder de hash) tuvo mala suerte y solo resolvió 2/16, entonces el otro grupo tendría muchas más probabilidades de ganar, por lo que probablemente no sería rentable para su grupo para continuar con la mina hasta que la otra piscina resuelva el bloque.
¿Hay algún algoritmo de prueba de trabajo estocásticamente dependiente?
RespuestasAquíPolítica de privacidad1y, 0v