Sobre la implementación DAA, algoritmos y especificaciones Por: @Fernando

0 67
Avatar for Spanish-translator-community
4 years ago

Articulo obtenido de Read.cash

Idioma: Inglés

Autor: @Fernando

Título original: On DAA implementation, algorithms and specifications

Quiero hablar sobre 2 cosas importantes que los programadores a veces pasan por alto: Algoritmos y especificaciones y utilizaré la implementación DAA como un ejemplo real.

Durante 4 años, he mantenido un nodo multidivisa (BCH, BTC y LTC) llamado  Knuth  (también conocido como Bitprim).
En noviembre de 2017,  Bitcoin Cash  realizó su primer cambio de protocolo después de su nacimiento en agosto del mismo año. Mi trabajo en ese momento era actualizar el código de nuestro nodo para admitir los cambios de protocolo.

El cambio más importante del HF de noviembre de 2017 fue el  Algoritmo de ajuste de dificultad , a partir de ahora  DAA .

El algoritmo

Aquí la descripción del algoritmo .

No quiero entrar en detalles sobre el concepto de dificultad ni verificar si DAA es el mejor algoritmo para ajustar la dificultad, pero quiero revisar cómo se implementó y se especificó.

Los principales intereses para mí son los puntos 2 y 3 de la descripción de la DAA:

2. Let B_last be chosen[2] from [B_n-2, B_n-1, B_n].
3. Let B_first be chosen[2] from [B_n-146, B_n-145, B_n-144].

Ambos apuntando a la nota al pie [2]:

2. A block is chosen via the following mechanism: 

Given a list: S = [B_n-2, B_n-1, B_n] 
a. If timestamp(S[0]) greater than timestamp(S[2]) then swap S[0] and S[2]. 
b. If timestamp(S[0]) greater than timestamp(S[1]) then swap S[0] and S[1]. 
c. If timestamp(S[1]) greater than timestamp(S[2]) then swap S[1] and S[2]. 
d. Return S[1]. 

See GetSuitableBlock

Implementación ABC

  • La especificación del algoritmo apunta a su implementación , en una función llamada  GetSuitableBlock . Aquí el código:

/**
 * To reduce the impact of timestamp manipulation, we select the block we are
 * basing our computation on via a median of 3.
 */
static const CBlockIndex *GetSuitableBlock(const CBlockIndex *pindex) {
    assert(pindex->nHeight >= 3);

    /**
    * In order to avoid a block is a very skewed timestamp to have too much
    * influence, we select the median of the 3 top most blocks as a starting
    * point.
    */
    const CBlockIndex *blocks[3];
    blocks[2] = pindex;
    blocks[1] = pindex->pprev;
    blocks[0] = blocks[1]->pprev;

    // Sorting network.
    if (blocks[0]->nTime > blocks[2]->nTime) {
        std::swap(blocks[0], blocks[2]);
    }

    if (blocks[0]->nTime > blocks[1]->nTime) {
        std::swap(blocks[0], blocks[1]);
    }

    if (blocks[1]->nTime > blocks[2]->nTime) {
        std::swap(blocks[1], blocks[2]);
    }

     // We should have our candidate in the middle now.
    return blocks[1];
}

El algoritmo básicamente crea una secuencia, luego ordena y devuelve el segundo elemento.

La complejidad en el tiempo de este algoritmo es:

  • Mejor caso: 0 intercambios, 3 comparaciones

  • Peor caso: 2 permutas, 3 comparaciones

  • Caso promedio: 7/6 swaps, 3 comparaciones; suponiendo una distribución uniforme de los datos de entrada. (*)

Ahora, mira nuevamente el algoritmo. Se está creando una matriz (utilizando los datos de entrada), luego se ordena y se devuelve el elemento central. Este es un algoritmo conocido y se llama  mediana , en particular, mediana de 3 elementos.

La mediana es un   algoritmo de selección . A diferencia de los algoritmos de clasificación (clasificación in situ), se supone que los algoritmos de selección no deberían modificar los datos de entrada, solo tienen que devolver uno de los elementos de la secuencia de entrada.

Mediana del algoritmo 3

Aquí un bosquejo de cómo la mediana del algoritmo 3 debe implementarse correctamente en C ++:

template <TotallyOrdered T>
auto median_3_ab(T const& a, T const& b, T const& c) {
    // precondition: a <= b
    
    return ! (c < b) ? b :        // a, b, c are sorted
                       max(a, c); // b is not the median
}

template <TotallyOrdered T>
auto median_3(T const& a, T const& b, T const& c) {
    return b < a ? median_3_ab(b, a, c) 
                 : median_3_ab(a, b, c);
}

(Uso PascalCase para nombrar conceptos de C ++ , como TotallyOrdered, la misma convención que en EoP )

Dejo el análisis del código para el lector, para los vagos: lo que hace el algoritmo es simplemente seleccionar el elemento intermedio entre  a,  b y  c, simulando que los 3 se ordenaron en orden ascendente. Hace esto sin mutar o reordenar los datos de entrada.

La complejidad temporal de  median_3 es:

  • Mejor caso: 0 intercambios, 2 comparaciones

  • Peor caso: 0 intercambios, 3 comparaciones

  • Caso promedio: 0 permutas, 8/3 comparaciones; suponiendo una distribución uniforme de los datos de entrada.

Ahora, podríamos usar nuestro nuevo algoritmo en la GetSuitableBlock función original  :

static 
CBlockIndex const* GetSuitableBlockNewVersion(CBlockIndex const* pindex) {
    assert(pindex->nHeight >= 3);
    return &median_3(*pindex->pprev->pprev, 
                     *pindex->pprev, 
                     *pindex);
}

Antes de continuar, tenemos que arreglar algo:
no sabemos cómo se especifica el orden natural en la  CBlockIndex clase, por lo que debemos ordenar por la marca de tiempo del bloque ( nTime atributo).
Necesitamos una versión  median_3 que acepte una forma de comparación especificada por el usuario: necesitamos una función para aceptar una  relación de orden débil estricta  ( para más información, consulte aquí ). Entonces:

template <Regular T, StrictWeakOrdering R>
auto median_3_ab(T const& a, T const& b, T const& c, R r) {
    // precondition: a <= b
    
    return ! r(c, b) ? b :           // a, b, c are sorted
                       max(a, c, r); // b is not the median
}

template <Regular T, StrictWeakOrdering R>
auto median_3(T const& a, T const& b, T const& c, R r) {
    return r(b, a) ? median_3_ab(b, a, c, r) 
                   : median_3_ab(a, b, c, r);
}

Ahora, podemos implementar correctamente  GetSuitableBlockNewVersion, comparando por  nTime:

static 
CBlockIndex const* GetSuitableBlockNewVersion(CBlockIndex const* pindex) {
    assert(pindex->nHeight >= 3);
    return &median_3(*pindex->pprev->pprev, 
                     *pindex->pprev, 
                     *pindex, 
                     [](auto const& a, auto const& b){
                         return a.nTime < b.nTime;
                     });
}

Bueno, creo que estamos listos! hmm ... espera ...
Veamos una cosa más:

Prueba de estabilidad

struct CBlockIndex {
    size_t nHeight;
    size_t nTime;
    CBlockIndex* pprev;
};

int main() {
    CBlockIndex ba {1, 1558731501, nullptr};
    CBlockIndex bb {2, 1558731501, &ba}; //note, same nTime as previous one
    CBlockIndex bc {3, 1558731500, &bb};

    auto r = GetSuitableBlockNewVersion(&bc);
    cout << "GetSuitableBlockNewVersion: " << r->nHeight << endl;

    r = GetSuitableBlock(&bc);
    cout << "GetSuitableBlock:           " << r->nHeight << endl;
}

El código anterior imprime:

GetSuitableBlockNewVersion: 1
GetSuitableBlock:           2

Con el ejemplo anterior, estoy tratando de demostrar la estabilidad de ambos algoritmos. Nuestro  median_3 algoritmo es  estable, lo  que significa que se preserva el orden relativo de los elementos equivalentes ( para más información, consulte aquí ).

Veámoslo de otra manera, dada la siguiente secuencia, llamada s:

s = [{1, 1558731501}, {2, 1558731501}, {3, 1558731500}]

Donde está el primer elemento de cada par  nHeight, y el segundo es el  nTime. Tenga en cuenta, nuevamente, que el  nTime de los primeros 2 elementos es el mismo.

Si clasificamos el spor  nTime el uso de un algoritmo de clasificación estables , tales como  ordenamiento por mezcla  obtendremos el siguiente resultado:

s = [{3, 1558731500}, {1, 1558731501}, {2, 1558731501}]

Tenga en cuenta que el elemento del medio es el que tiene  nHeight = 1. Esto indica que la implementación de nuestro algoritmo GetSuitableBlockNewVersion, se comportó de manera estable, mientras que el algoritmo incluido en la descripción de DAA GetSuitableBlock, es inestable.

Especificación DAA

Cuando estaba implementando DAA en mi nodo, utilicé la mediana estable del algoritmo 3, similar al median_3anterior, ya que no había verificado completamente el GetSuitableBlockcódigo, asumí erróneamente que era un algoritmo estable.

Entonces, nuestro nodo dejó de ser compatible con las reglas de consenso de Bitcoin ABC. Afortunadamente, pude detectar la divergencia entre ambos algoritmos, luego, tuve que cambiar mi algoritmo para hacerlo inestable, de la misma manera que la implementación de Bitcoin ABC

En realidad, si no recuerdo mal, la primera versión de la descripción de DAA (en la que me basé para implementarla en mi nodo, publicado solo unos días antes de la HF) no mencionó el  GetSuitableBlock código, pero dijo que la mediana de 3 elementos era calculado. Dado que la implementación de Bitcoin ABC del algoritmo mediano era "incorrecta", tuvieron que adaptar la "especificación" para que fuera coherente con el código.

Entonces, el autor del código DAA podría haber elegido un algoritmo conocido y "estándar", pero no lo hizo. Y quizás lo peor de todo es que tuvieron que arreglar la especificación DAA apuntando al código. 


El código nunca debe ser la especificación. El código debe escribirse a partir de una especificación.  Entonces, si una especificación se refiere al código, no puede considerarse como tal.


Para concluir una comparación de ambos algoritmos,  GetSuitableBlock frente a  median_3:

  • median_3 no realiza ningún intercambio,  GetSuitableBlock puede realizar 0, 7/6 o 2 intercambios, innecesariamente. (Eficiencia)

  • GetSuitableBlock crea una matriz innecesariamente. (Eficiencia)

  • median_3 realiza 2, 8/3 o 3 comparaciones,  GetSuitableBlock siempre realiza 3 comparaciones. (Eficiencia)

  • median_3 Es estable,  GetSuitableBlock no lo es. 
    median_3 es lo que cualquiera espera de un algoritmo que calcula la mediana de 3 elementos. (Exactitud)

Entonces, chicos, los dioses de programación no existen.
¡Adiós!


PD: ¿optimización prematura?

Solo una aclaración:

Cuando comparo ambos algoritmos, no estoy tratando de optimizar prematuramente, sino de evitar usar código feo cuando se puede usar un código mucho más hermoso, y también estoy tratando de evitar que me pesen prematuramente.

Evitar la optimización prematura no implica perjudicar de forma gratuita la eficiencia o la belleza del código.


¿Que sigue?

En los siguientes artículos lo haremos:

- Analice cómo los otros nodos han implementado el DAA.

- (*) Cuente el número de comparaciones e intercambios utilizando datos reales (BCH Blockchain).


Bibliografía

AA Stepanov y P. McJones. Elementos de programación. Addison-Wesley Professional, 2009.

DE Knuth. The Art of Computer Programming Volume 3: Sorting and Searching, 1998.

Amigo @Fernando nos encantó tu trabajo eres un grandioso programador y desarrollador, nos encanta tenerte en bitcoin Cash Node esperamos puedas plasmar todas tus habilidades en pro de este proyecto, creemos en ti!! Esperamos tus próximas publicaciones para ser traducidas también a la comunidad habla hispana. Eres genial continúa así.

1
$ 0.00
Avatar for Spanish-translator-community
4 years ago

Comments