Components Programming

☰

Algoritmos y especificaciones

Feb 19, 2020

En este artículo quiero hablar sobre 2 temas en los que creo que la mayoría de los programadores solemos fallar: Algoritmos y Especificaciones.

Me voy a ayudar de una experiencia real, ocurrida ya hace un tiempo:

Desde hace ya 4 años mantengo un nodo multimoneda (Bitcoin, Bitcoin Cash y Litecoin) llamado Knuth (a.k.a. Bitprim). En noviembre de 2017 Bitcoin Cash hizo su primer cambio de protocolo luego de su nacimiento en agosto del mismo año. Mi trabajo en ese momento era actualizar el código de nuestro nodo para que soporte los cambios de protocolo. Desde aquel momento que quiero escribir este artículo, pero… por alguna o varias razones no lo hice en ese momento, lo estoy haciendo ahora.

El cambio más importante de fue en el Algoritmo de Ajuste de Dificultad, en adelante DAA (del inglés Difficulty Adjustment Algorithm).

Aquí la descripción del algoritmo.

No quiero entrar en detalles acerca del concepto de dificultad ni del DAA. Para ello puede referirse a: Difficulty.

Lo que me interesa son los puntos 2 y 3 de la descripción del 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 apuntan 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

La especificación del algoritmo apunta a su implementación, en una función llamada GetSuitableBlock. Aquí su 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];
}

Lo que hace el algoritmo es básicamente crear una secuencia de 3 elementos (array), la ordena de menor a mayor y retorna el segundo elemento.

La complejidad en tiempo de este algoritmo es:

Ahora, vuelva a observar con detenimiento el algoritmo. Se está creando un array (usando los datos de entrada), para luego ordenarlo ascendentemente y retornar el elemento del medio. 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 ordenamiento (inplace), los algoritmos de selección no deberían mutar los datos de entrada, sino, retornar uno de ellos.

Aquí les dejo un boceto del algoritmo mediana de 3, en C++:

template <TotallyOrdered T>
auto max(T const& a, U const& b) {
    return b < a ? a : b;
}

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);
}

O si prefiere la versión inline del algoritmo:

template <TotallyOrdered T>
auto median_3(T const& a, T const& b, T const& c) {
    if (b < a) {
        if (c >= a) return a;  // b, a, c are sorted
        return max(b, c);      // a is not the median
    } else {    // a <= b
        if (c >= b) return b;  // a, b, c are sorted
        return max(a, c);      // b is not the median
    }
}

Dejo el análisis del código para el lector, para el vago: lo que hace el algoritmo es simplemente seleccionar el elemento del medio entre a, b y c, haciendo de cuenta que los 3 estuviesen ordenados ascendentemente. Esto lo hace sin mutar ni reordenar los datos de entrada.

La complejidad en tiempo de median_3 es:

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

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

Mucho más breve y entendible, ¿no?.

Antes de seguir, tenemos que corregir un problema: no sabemos si el Ordenamiento Natural especificado en la clase CBlockIndex está dado por el timestamp del bloque (atributo nTime). Necesitamos una versión de median_3 que acepte una forma de comparar especificado por el usuario: necesitamos que acepte una relación de preorden total estricta (strict weak ordering relation, para más información consulte aquí).

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

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 sí, 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;
    });
}

Nos queda un último problema por resolver. Hagamos una pequeña prueba del algoritmo original y del nuevo:

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

int main() {
    CBlockIndex ba {1, 1558731500, nullptr};
    CBlockIndex bb {2, 1558731500, &ba};        //same nTime as previous
    CBlockIndex bc {3, 1558730000, &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

Lo que estamos intentando probar con el código anterior es la estabilidad de ambos algoritmos. Nuestro algoritmo median_3 es estable lo que quiere decir que el orden de los elementos equivalentes se preserva (para más información consulte aquí).

Para demostrarlo con datos, vamos a utilizar el ejemplo anterior, en el cual tenemos los siguientes datos de entrada para nuestros algoritmos:

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

Donde el primer elemento de cada par es el identificador del bloque nHeight y el segundo elemento es el timestamp nTime. Note que el nTime de los primeros 2 elementos es igual.

Si ordenamos la secuencia anterior por nTime usando un algoritmo de ordenamiento estable, como por ejemplo Merge sort nos quedaría algo así:

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

Note que el elemento del medio es el que tiene nHeight = 1. Lo cual indica que nuestro algoritmo se comportó de manera estable pero no así el algoritmo original usado en el DAA de Bitcoin Cash.

En mi primera implementación de DAA en el nodo Bitprim usé un código similar a median_3 el cual también era estable, dado que no había verificado el código de la especificación, yo había asumido erróneamente que también era estable. Luego esto provocó errores en tiempo de ejecución de nuestro nodo ante un ajuste de dificultad. No se daba siempre, pero hubo un caso en particular en el que lo pudimos detectar. Luego de varias horas de debugging pude detectar que el problema era que el algoritmo usado por mí no era compatible con el “especificado” en DAA.

Por lo tanto, tuve que “corregir” mi algoritmo para hacerlo no-estable de la misma forma que el de la especificación.

En realidad, si mal no recuerdo, en la primera versión de la especificación de DAA no se mencionaba al código de GetSuitableBlock, sino que decía que se calculaba la mediana de 3 elementos. Como la implementación de la mediana fue “incorrecta” tuvieron que adaptar la especificación para que se condiga con el código. Tenga en cuenta, que una vez que el código de un nodo Bitcoin o de cualquier criptomoneda está en funcionamiento, una modificación en su comportamiento introduce incompatibilidades con versiones anteriores y produce los denominados forks. Por lo que una vez que el código está corriendo, se trata de no cambiarlo. Por esta razón es por la que se tuvo que adaptar la especificación en vez de corregir el código.

Antes de terminar, hagamos una comparación de ambos algoritmos, GetSuitableBlock vs. median_3:

Y ahora sí, para finalizar, algunas conclusiones:

El autor de la especificación de DAA podría haber optado por usar un algoritmo conocido y “estándar”, pero no lo hizo. Es más, quizás lo peor de todo esto es que la especificación hace referencia al código. El código no debe ser nunca especificación. El código debe ser creado a partir de una especificación. Por lo que si una especificación hace referencia a código, no existe dicha especificación.

¡Saludos!