-
Notifications
You must be signed in to change notification settings - Fork 2
Consensus
Tensority alogrithm utilizes seed and block header hash as input and generate work correspondingly. Seed is a byte array of 32 determined by a period of blockchain history. In other word, seed can be considered as a snapshot of historical network consensus. To get a validated block, miners should keep operating Tensority with different nonce until matching the requirement of difficulty.
There are mainly five procedures of Tensority:
- cache calculation
- matrix construction
- matrix operation
- work generation
- work validation
Cache is generated by seed. Compared with block rate, seed renewal is slower. So, cache generated from seed can be reused for a period of time. Furthermore, cache is the intermediary of constructing cache matrix. The main steps are listed as follow:
1. Seed Extention
Set seed_0 as seed, calculate sha256 hash of seed_0 and then we get seed_1. Similarly, We can get seedi one after another by calculating sha256 hash of seed_i−1. Finally, we string seed_0, . . . , seed_extround together and get extseed.
2. Scrypt Extseed
We recursively call Scrypt function to obtain the cache, an unint32 array of 32x1024x128. Scrypt is a kind of KDF alogrithm mainly used as key generation method aimed at preventing low-cost password collision. It is worth to mentioned that Scrypt is used in Litecoin since 2011. So, it has been proved as a reliable seed extension algorithm.
Algorithm: calcSeedCache
------------------------------------------------
Input: seed
Output: cache
------------------------------------------------
1 Initialize extround = 3, scryptround = 128;
2 extseed = seed;
3 tmphash = seed;
4 for i = 1; i <= extround; i++ do
5 tmphash = SHA256(tmphash);
6 extseed = append(extseed, tmphash);
7 end
8 cache = null;
9 tmpv = null;
10 for j = 1; j <= scryptround; j++ do
11 tmpv = Scrypt.smix(extseed, tmpv);
12 cache = append(cache, tmpv);
13 end
14 return cache
------------------------------------------------Technical innovation of Tensority is based on tensor and matrix operations. In this procedure, we construct matrices which are ready for matrix operations in the next procedure. The main steps are listed as follow:
1. Cache Recomposition
The design of recomposition method is aimed at improving efficiency of ASCI mining machines, such as faster memory accession. Considering data alignment and memory access of miners, we design following recomposition of cache.
At the begining, we partition cache into 128 groups. Each group includes 32x1024 elements. In each group, we cluster 32 elements as a unit. So, we obtain an uint32 matrix tmpmatrix of 32x1024x128. The size of recomposedmatrix is also 32x1024x128. Tmpmatrix elements with odd dimension 2 index equal recomposedmatrix to elements with dimension2 index from 1 to 1024/2 correspondingly. Similarly, tmpmatrix elements with even index are corespondent to recomposedmatrix elements with index from 1024/2+1 to 1024.
2. Cache Matrix Construction
Spread matrix recomposedmatrix and set it as a int8 array of 256x256x256. Then we get a float64 array of 256x256x256 by type casting. Finally, we obtain a float64 matrix cachematrix of 256x256x256.
Algorithm: constructCacheMatrix
------------------------------------------------------------------------------
Input: cache
Output: cachematrix
------------------------------------------------------------------------------
1 Initialize dim1 = 32; dim2 = 1024; dim3 = 128; dim = 256;
2 tmpmatrix = Matrix(cache, dim1, dim2, dim3);
3 recomposedmatrix = NewMatrix(dim1, dim2, dim3);
4 cachematrix = NewMatrix(dim, dim, dim);
5 recomposedmatrix[:][1:dim2/2][:] = tmpmatrix[:][all odd index][:];
6 recomposedmatrix[:][dim2/2+1:dim2][:] = tmpmatrix[:][all even index][:];
7 cachematrix = Float64(Matrix(Int8Array(recomposedmatrix), dim, dim, dim)));
8 return cachematrix;
------------------------------------------------------------------------------The rate of matrix operation mainly depends on the computing power of miner. In addition, float64 matrix multiplication instead of integer multiplication is adopted because we should enable miners supporting AI algorithms which mainly run under float type environment.The procedure of matrix operation utilizes block header hash headerhash as a index to slice cachematrix, an float64 matrix of 256x256x256. After calculating matrix multiplication with slices iteratively for several round, we finally obtain the work matrix workmatrix. Note that there are total 256 rounds of multiplication between matrices of 256x256. The main steps are listed as follow:
1. Generate Index of Matrix Slices
We divide block header hash into 4 group first. Then we operate SHA256 to each group and obtain corresponding sequence of 32 bytes. Each byte in sequence is casted to integer as the index of the matrix slice. Obviously, 4x32 matrix slices are generated during this procedure.
2. Matrix Caculation
We can obtain the corresponding 256x256 cachematrix matrix slice mb according to the slice index. Matrix mc is the result of multiplication of ma and mbT. Note that ma is initialized to identity matrix in the first round. Then we cast elements of mc to int32.
Here we define a operation called Compress32to8. It converts the data type int32 of data b = (b_1, b_2, b_3, b_4) (big endian) into uint8 via the formula (b_3 + b_4) mod (2^8). Compress32to8 is introduced to ensure better randomness of multiplication result.
After that, we set mc elements as their corresponding Compress32to8 results. Then we cast mc elements to float64 and assign the result to ma until sequence run out eventually. Previous steps should be iterated for 2 times.
Finally, we utilize ma to renew hashmatrix. We will get Integer32 sum of ma and hashmatrix. Renew hashmatrix element with low 8 bits value in that position and cast the element to float64.
Algorithm: constructHashMatrix
------------------------------------------------------------------------------
Input: cachematrix, headerhash
Output: hashmatrix
------------------------------------------------------------------------------
1 Initialize drawround = 4; mulround = 2; dim = 256;
2 hashmatrix = Matrix(dim, dim);
3 drawmatrix = Matrix(headerhash, drawround, sizeof(headerhash)/drawround);
4 for i = 1; i <= drawround; i++ do
5 ma = I;
6 mc = Matrix(dim, dim);
7 sequence = SHA256(drawmatrix[i]);
8 for j = 1; j <= mulround; j++ do
9 for k = 1; k <= sizeof(sequence); k++ do
10 index = uint8(sequence[k])+1;
11 mb = srcmatrix[index][:][:];
12 mc = ma * mb.T();
13 for element ∈ mc do
14 element = Float64(Compress32to8(Int32(element)));
15 end
16 ma = mc
17 end
18 end
19 for row = 1; row <= dim; row++ do
20 for col = 1; col <= dim; col++ do
21 i32vhashmatrix = Int32(hashmatrix[row][col]);
22 i32vma = Int32(ma[row][col]);
23 i8v = Int8(i32vhashmatrix+i32vma);
24 hashmatrix[row][col] = Float64(i8v);
25 end
26 end
27 end
28 return hashmatrix;
------------------------------------------------------------------------------Work generation algorithm use hashmatrix as input and generation 32 bytes hash representing work. The key of that procedure is improving computational efficiency under the premise of randomness. So, we utilize FNV enabling faster hash to hash matrix instead of SH2 or SH3 because it is a non-cryptographic hash algorithm. FNV has also been adopted in Ethereum Ethash for a while. So, its reliability has been proved. In addition, We choose 0x01000193 as parameter FNV prime. Finally, we apply SHA256 to the result of FNV to assure solid randomness.
1. Resize Matrix Hashmatrix
Hashmatrix is an uint8 matrix of 256x256. For each row, extract elements with same remainder from dividing 64 by the position as a group. Combine elements in each group into an unint32 element. Then we get an unint32 matrix of 256x64 called mat32.
2. Binary Forwarded FNV
Binary Forwarded FNV is essentially a method to hash matrix. First, we initiate n to dim1 of mat32. For row 1 to row n, operate FNV function to two element in same column with same remainder from dividing n/2 by the row position and set that element with lower row index as FNV result. Then we half n and execute that step unit n equals to 1. Finally, we take the first row of mat32 and convert it to byte array. After operate SHA256 to that byte array, we obtain work.
Algorithm: Binary Forwarded FNV
---------------------------------------------------------------
Input: mat32
Output: hash
---------------------------------------------------------------
1 Initialize dim1 = 256; dim2 = 64;
2 for k = dim1; k > 1; k = k/2 do
3 for i = 1; i <= k; i++ do
4 for j = 1; j <= dim2; j++ do
5 mat32[i][j] = FNV(mat32[i][j], mat32[i+k][j]);
6 end
7 end
8 end
9 hash = SHA256(ToByteArray(mat32[0][:]);
10 return hash;
---------------------------------------------------------------In this procedure, we compare work value with block difficulty. If the work have lower value, it can be seen as a validated work and miners will broadcast that block before receiving a validated block from others. Otherwise, miners will keep changing nonce value to execute Tensority before receiving a validated block.
Tensority White Paper is a good reference.