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 GetSuitableBlockImplementació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: 2Con 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_3no realiza ningún intercambio,GetSuitableBlockpuede realizar 0, 7/6 o 2 intercambios, innecesariamente. (Eficiencia)GetSuitableBlockcrea una matriz innecesariamente. (Eficiencia)median_3realiza 2, 8/3 o 3 comparaciones,GetSuitableBlocksiempre realiza 3 comparaciones. (Eficiencia)median_3Es estable,GetSuitableBlockno lo es.
median_3es 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í.