Chia vdf verification (wraps C++)
Project description
Chia VDF
Building a wheel
Compiling chiavdf requires cmake, boost and GMP/MPIR.
python3 m venv venv
source venv/bin/activate
pip install wheel setuptools_scm pybind11
pip wheel .
The primary build process for this repository is to use GitHub Actions to
build binary wheels for MacOS, Linux (x64 and aarch64), and Windows and
publish them with a source wheel on PyPi. See .github/workflows/build.yml
.
CMake uses
FetchContent
to download pybind11.
Building is then managed by
cibuildwheel. Further installation
is then available via pip install chiavdf
e.g.
Building Timelord and related binaries
In addition to building the required binary and source wheels for Windows,
MacOS and Linux, chiavdf can be used to compile vdf_client and vdf_bench.
vdf_client is the core VDF process that completes the Proof of Time submitted
to it by the Timelord. The repo also includes a benchmarking tool to get a
sense of the iterations per second of a given CPU called vdf_bench. Try
./vdf_bench square_asm 250000
for an ips estimate.
To build vdf_client set the environment variable BUILD_VDF_CLIENT to "Y".
export BUILD_VDF_CLIENT=Y
.
Similarly, to build vdf_bench set the environment variable BUILD_VDF_BENCH to
"Y". export BUILD_VDF_BENCH=Y
.
This is currently automated via pip in the installtimelord.sh script in the chiablockchain repository which depends on this repository.
If you're running a timelord, the following tests are available, depending of which type of timelord you are running:
./1weso_test
, in case you're running in sanitizer_mode.
./2weso_test
, in case you're running a timelord that extends the chain and you're running the slow algorithm.
./prover_test
, in case you're running a timelord that extends the chain and you're running the fast algorithm.
Those tests will simulate the vdf_client and verify for correctness the produced proofs.
Contributing and workflow
Contributions are welcome and more details are available in chiablockchain's CONTRIBUTING.md.
The master branch is the currently released latest version on PyPI. Note that at times chiavdf will be ahead of the release version that chiablockchain requires in it's master/release version in preparation for a new chiablockchain release. Please branch or fork master and then create a pull request to the master branch. Linear merging is enforced on master and merging requires a completed review. PRs will kick off a ci build and analysis of chiavdf at lgtm.com. Please make sure your build is passing and that it does not increase alerts at lgtm.
Background from prior VDF competitions
Copyright 2018 Ilya Gorodetskov generic@sundersoft.com
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
Our VDF construction is described in classgroup.pdf. The implementation details about squaring and proving phrases are described below.
Main VDF Loop
The main VDF loop produces repeated squarings of the generator form (i.e. calculates y(n) = g^(2^n)) as fast as possible, until the program is interrupted. Sundersoft's entry from Chia's 2nd VDF contest is used, together with the fast reducer used in Pulmark's entry. This approach is described below:
The NUDUPL algorithm is used. The equations are based on cryptoslava's equations from the 1st contest. They were modified slightly to increase the level of parallelism.
The GCD is a custom implementation with scalar integers. There are two base cases: one uses a lookup table with continued fractions and the other uses the euclidean algorithm with a division table. The division table algorithm is slightly faster even though it has about 2x as many iterations.
After the base case, there is a 128 bit GCD that generates 64 bit cofactor matricies with Lehmer's algorithm. This is required to make the long integer multiplications efficient (Flint's implementation doesn't do this).
The GCD also implements Flint's partial xgcd function, but the output is slightly different. This implementation will always return an A value which is > the threshold and a B value which is <= the threshold. For a normal GCD, the threshold is 0, B is 0, and A is the GCD. Also the interfaces are slightly different.
Scalar integers are used for the GCD. I don't expect any speedup for the SIMD integers that were used in the last implementation since the GCD only uses 64x1024 multiplications, which are too small and have too high of a carry overhead for the SIMD version to be faster. In either case, most of the time seems to be spent in the base case so it shouldn't matter too much.
If SIMD integers are used with AVX512, doubles have to be used because the multiplier sizes for doubles are significantly larger than for integers. There is an AVX512 extension to support larger integer multiplications but no processor implements it yet. It should be possible to do a 50 bit multiplyadd into a 100 bit accumulator with 4 fused multiplyadds if the accumulators have a special nonzero initial value and the inputs are scaled before the multiplication. This would make AVX512 about 2.5x faster than scalar code for 1024x1024 integer multiplications (assuming the scalar code is unrolled and uses ADOX/ADCX/MULX properly, and the CPU can execute this at 1 cycle per iteration which it probably can't).
The GCD is parallelized by calculating the cofactors in a separate slave thread. The master thread will calculate the cofactor matricies and send them to the slave thread. Other calculations are also parallelized.
The VDF implementation from the first contest is still used as a fallback and is called about once every 5000 iterations. The GCD will encounter large quotients about this often and these are not implemented. This has a negligible effect on performance. Also, the NUDUPL case where A<=L is not implemented; it will fall back to the old implementation in this case (this never happens outside of the first 20 or so iterations).
There is also corruption detection by calculating C with a nonexact division and making sure the remainder is 0. This detected all injected random corruptions that I tested. No corruptions caused by bugs were observed during testing. This cannot correct for the sign of B being wrong.
GCD continued fraction lookup table
The is implemented in gcd_base_continued_fractions.h and asm_gcd_base_continued_fractions.h. The division table implementation is the same as the previous entry and was discussed there. Currently the division table is only used if AVX2 is enabled but it could be ported to SSE or scalar code easily. Both implementations have about the same performance.
The initial quotient sequence of gcd(a,b) is the same as the initial quotient sequence of gcd(a*2^n/b, 2^n) for any n. This is because the GCD quotients are the same as the continued fraction quotients of a/b, and the initial continued fraction quotients only depend on the initial bits of a/b. This makes it feasible to have a lookup table since it now only has one input.
a*2^n/b is calculated by doing a double precision division of a/b, and then truncating the lower bits. Some of the exponent bits are used in the table in addition to the fraction bits; this makes each slot of the table vary in size depending on what the exponent is. If the result is outside the table bounds, then the division result is floored to fall back to the euclidean algorithm (this is very rare).
The table is calculated by iterating all of the possible continued fractions that have a certain initial quotient sequence. Iteration ends when all of these fractions are either outside the table or they don't fully contain at least one slot of the table. Each slot that is fully contained by such a fraction is updated so that its quotient sequence equals the fraction's initial quotient sequence. Once this is complete, the cofactor matricies are calculated from the quotient sequences. Each cofactor matrix is 4 doubles.
The resulting code seems to have too many instructions so it doesn't perform very well. There might be some way to optimize it. It was written for SSE so that it would run on both processors.
This might work better on an FPGA possibly with low latency DRAM or SRAM (compared to the euclidean algorithm with a division table). There is no limit to the size of the table but doubling the latency would require the number of bits in the table to also be doubled to have the same performance.
Other GCD code
The gcd_128 function calculates a 128 bit GCD using Lehmer's algorithm. It is pretty straightforward and uses only unsigned arithmetic. Each cofactor matrix can only have two possible signs: [+ ;  +] or [ +; + ]. The gcd_unsigned function uses unsigned arithmetic and a jump table to apply the 64bit cofactor matricies to the A and B values. It uses ADOX/ADCX/MULX if they are available and falls back to ADC/MUL otherwise. It will track the last known size of A to speed up the bit shifts required to get the top 128 bits of A.
No attempt was made to try to do the A and B long integer multiplications on a separate thread; I wouldn't expect any performance improvement from this.
Threads
There is a master thread and a slave thread. The slave thread only exists for each batch of 5000 or so squarings and is then destroyed and recreated for the next batch (this has no measurable overhead). If the original VDF is used as a fallback, the batch ends and the slave thread is destroyed.
Each thread has a 64bit counter that only it can write to. Also, during a squaring iteration, it will not overwrite any value that it has previously written and transmitted to the other thread. Each squaring is split up into phases. Each thread will update its counter at the start of the phase (the counter can only be increased, not decreased). It can then wait on the other thread's counter to reach a certain value as part of a spin loop. If the spin loop takes too long, an error condition is raised and the batch ends; this should prevent any deadlocks from happening.
No CPU fences or atomics are required since each value can only be written to by one thread and since x86 enforces acquire/release ordering on all memory operations. Compiler memory fences are still required to prevent the compiler from caching or reordering memory operations.
The GCD master thread will increment the counter when a new cofactor matrix has been outputted. The slave thread will spin on this counter and then apply the cofactor matrix to the U or V vector to get a new U or V vector.
It was attempted to use modular arithmetic to calculate k directly but this slowed down the program due to GMP's modulo or integer multiply operations not having enough performance. This also makes the integer multiplications bigger.
The speedup isn't very high since most of the time is spent in the GCD base case and these can't be parallelized.
Generating proofs
The nested wesolowski proofs (nwesolowski) are used to check the correctness of a VDF result. (Simple) Wesolowski proofs are described in A Survey of Two Verifiable Delay Functions. In order to prove h = g^(2^T), a nwesolowski proof uses n intermediate simple wesolowski proofs. Given h, g, T, t1, t2, ..., tn, h1, h2, ..., hn, a correct nwesolowski proof will verify the following:
h1 = g^(2^t1) h2 = h1^(2^t2) h3 = h2^(2^t3) ... hn = h(n1)^(2^tn)
Additionally, we must have:
t1 + t2 + ... + tn = T hn = h
The algorithm will generate at most 64wesolowski proofs. Some intermediates wesolowski proofs are stored in parallel with the main VDF loop. The goal is to have a nwesolowski proof almost ready as soon as the main VDF loop finishes computing h = g^(2^T), for a T that we're interested in. We'll call a segment a tuple (y, x, T) for which we're interested in a simple wesolowski proof that y = x^(2^T). We'll call a segment finished when we've finished computing its proof.
Segmenets stored
We'll store finished segments of length 2^x for x being multiples of 2 greater than or equal to 16. The current implementation limits the maximum segment size to 2^30, but this can be increased if needed. Let P = 16+2*l. After each 2^P steps calculated by the main VDF loop, we'll store a segment proving that we've correctly done the 2^P steps. Formally, let x be the form after k*2^P steps, y be the form after (k+1)*2^P steps, for each k >= 0, for each P = 16+2*l. Then, we'll store a segment (y, x, 2^P), together with a simple wesolowski proof.
Segment threads
In order to finish a segment of length T=2^P, the number of iterations to run for is T/k + l*2^(k+1) and the intermediate storage required is T/(k*l), for some parameters k and l, as described in the paper. The squarings used to finish a segment are about 2 times as slow as the ones used by the main VDF loop. Even so, finishing a segment is much faster than producing its y value by the main VDF loop. This allows, by the time the main VDF loop finishes 2^16 more steps, to perform work on finishing multiple segments.
The parameters used in finishing segments, for T=2^16, are k=10 and l=1. Above that, parameters are k=12 and l=2^(P18). Note that, for P >= 18, the intermediate storage needed for a segment is constant (i.e. 2^18/12 forms stored in memory).
Prover class is responsible to finish a segment. It implements pause/resume functionality, so its work can be paused, and later resumed from the point it stopped. For each unfinished segment generated by the main VDF loop, a Prover instance is created, which will eventually finish the segment.
Segment threads are responsible for deciding which Prover instance is currently running. In the current implementation, there are 3 segment threads (however the number is configurable), so at most 3 Prover instances will run at once, at different threads (other Provers will be paused). The segment threads will always pick the segments with the shortest length to run. In case of a tie, the segments received the earliest will have priority. Every time a new segment arrives, or a segment gets finished, some pausing/resuming of Provers is done, if needed. Pausing is done to have at most 3 Provers running at any time, whilst resuming is done if less than 3 Provers are working, but some Provers are paused.
All the segments of lengths 2^16, 2^18 and 2^20 will be finished relatively soon after the main VDF worker produced them, while the segments of length 2^22 and upwards will lag behind the main VDF worker a little. Eventually, all the higher size segments will be finished, the work on them being done repeatedly via pausing (when a smaller size segment arrives) and resuming (when all smaller size segments are finished).
Currently, 4 more segment threads are added after the main VDF loop finishes 500 million iterations (after about 1 hour of running). This is done to be completely sure even the very big sized segments will be finished. This optimisation is only allowed on machines supporting at least 16 concurrent threads.
Generating nwesolowski proof
Let T an iteration we are interested in. Firstly, the main VDF Loop will need to calculate at least T iterations. Then, in order to get fast a nwesolowski proof, we'll concatenate finished segments. We want the proof to be as short as possible, so we'll always pick finished segments of the maximum length possible. If such segments aren't finished, we'll choose lower length segments. A segment of length 2^(16 + 2*p) can always be replaced with 4 segments of length 2^(16 + 2*p  2). The proof will be created shortly after the main VDF loop produced the result, as the 2^16 length segments will always be up to date with the main VDF loop (and, at worst case, we can always concatenate 2^16 length segments, if bigger sizes are not finished yet). It's possible after the concatenation that we'll still need to prove up to 2^16 iterations (no segment is able to cover anything less than 2^16). This last work is done in parallel with the main VDF loop, as an optimisation.
The program limits the proof size to 64wesolowski. If number of iterations is very large, it's possible the concatenation won't fit into this. In this case, the program will attempt again to prove every minute, until there are enough large segments to fit the 64wesolowski limit. However, almost in all cases, the concatenation will fit the 64wesolowski limit in the first try.
Since the maximum segment size is 2^30 and we can use at most 64 segments in a concatenation, the program will prove at most 2^36 iterations. This can be increased if needed.
Intermediates storage
In order to finish segments, some intermediate values need to be stored for each segment. For each different possible segment length, we use a sliding window of length 20 to store those. Hence, for each segment length, we'll store only the intermediates values needed for the last 20 segments produced by the main VDF loop. Since finishing segments is faster than producing them by the main VDF loop, we assume the segment threads won't be behind by more than 20 segments from the main VDF loop, for each segment length. Thanks to the sliding window technique, the memory used will always be constant.
Generally, the main VDF loop performs all the storing, after computing a form we're interested in. However, since storing is very frequent and expensive (GMP operations), this will slow down the main VDF loop.
For the machines having at least 16 concurrent threads, an optimization is provided: the main VDF loop does only repeated squaring, without storing any form. After each 2^15 steps are performed, a new thread starts redoing the work for 2^15 more steps, this time storing the intermediate values as well. All the intermediates threads and the main VDF loop will work in parallel. The only purpose of the main VDF loop becomes now to produce the starting values for the intermediate threads, as fast as possible. The squarings used in the intermediates threads will be 2 times slower than the ones used in the main VDF loop. It's expected the intermediates will only lag behind the main VDF loop by 2^15 iterations, at any point: after 2^16 iterations are done by the main VDF loop, the first thread doing the first 2^15 intermediate values is already finished. Also, at that point, half of the work of the second thread doing the last 2^15 intermediates values should be already done.
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size chiavdf1.0.1cp37cp37mmacosx_10_14_x86_64.whl (318.6 kB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp37cp37mmanylinux2010_x86_64.whl (453.5 kB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp37cp37mmanylinux2014_aarch64.whl (384.0 kB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp37cp37mwin_amd64.whl (1.9 MB)  File type Wheel  Python version cp37  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp38cp38macosx_10_14_x86_64.whl (318.7 kB)  File type Wheel  Python version cp38  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp38cp38manylinux2010_x86_64.whl (452.2 kB)  File type Wheel  Python version cp38  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp38cp38manylinux2014_aarch64.whl (381.9 kB)  File type Wheel  Python version cp38  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp38cp38win_amd64.whl (1.9 MB)  File type Wheel  Python version cp38  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp39cp39macosx_10_14_x86_64.whl (318.7 kB)  File type Wheel  Python version cp39  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp39cp39macosx_11_0_arm64.whl (305.5 kB)  File type Wheel  Python version cp39  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp39cp39manylinux2010_x86_64.whl (452.3 kB)  File type Wheel  Python version cp39  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp39cp39manylinux2014_aarch64.whl (382.5 kB)  File type Wheel  Python version cp39  Upload date  Hashes View 
Filename, size chiavdf1.0.1cp39cp39win_amd64.whl (1.9 MB)  File type Wheel  Python version cp39  Upload date  Hashes View 
Filename, size chiavdf1.0.1.tar.gz (639.5 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for chiavdf1.0.1cp37cp37mmacosx_10_14_x86_64.whl
Algorithm  Hash digest  

SHA256  6169a26957cc5e73d86522b282c0a278f807d00bb7dde1d8402932c113dfe955 

MD5  67c5214385dad3a15fe19df9328a8f13 

BLAKE2256  94499adc2b2caaaffdfa0e371267070141248e4268acd89a64c14374ec806953 
Hashes for chiavdf1.0.1cp37cp37mmanylinux2010_x86_64.whl
Algorithm  Hash digest  

SHA256  064c5fcd98d07b7255bf3193655feab9df488ebe9812798d8bc188fe990353fa 

MD5  d853afb8c88ea25f0f67472ce93742d2 

BLAKE2256  4137e50556e0d83656b2057b8e653a9f84b6203cc333c3c99fc85ef7ab3e0f74 
Hashes for chiavdf1.0.1cp37cp37mmanylinux2014_aarch64.whl
Algorithm  Hash digest  

SHA256  728c5278726b1f60bd7f60a39233d2bec7c5a3fabe64ff89dd6f3baaf3407e67 

MD5  c08d2781d31e98870aabe2bab0f8d9b2 

BLAKE2256  96cd4fe05fdc73269413d8e016023c7aa973bc471fbc81fde47317506106d6c6 
Hashes for chiavdf1.0.1cp37cp37mwin_amd64.whl
Algorithm  Hash digest  

SHA256  fe15450f745eedab90a9f5c13db254886e65d7be3697fc46b43e96060ee61840 

MD5  c9f0738575fe7640a7c57341a6d6b717 

BLAKE2256  673f56a4548aa6f334a4801541536f10ed844282dacdbb1deffa6ccbc7dbbb26 
Hashes for chiavdf1.0.1cp38cp38macosx_10_14_x86_64.whl
Algorithm  Hash digest  

SHA256  8791739d6dfc7ba18134ad2a1de0089fbe52399f1da253f59b36460ff4b57163 

MD5  e4498cf8692dce8ca77bec0627766276 

BLAKE2256  e65cabbc95a6ebeb553334b4dd8821901a1fe58b23d4c1fb050127b85c2137bc 
Hashes for chiavdf1.0.1cp38cp38manylinux2010_x86_64.whl
Algorithm  Hash digest  

SHA256  c72c971446e68e195d4c4be7775467ee8f088d58913c44920c5e743b336277f9 

MD5  9438f35e2e49ccd99bd97c607fc535c9 

BLAKE2256  299fd817e7817e1565d53f1de5e16599a8592cd2b6da7f79c963c3291e94c33f 
Hashes for chiavdf1.0.1cp38cp38manylinux2014_aarch64.whl
Algorithm  Hash digest  

SHA256  045d38697c8d07892c1d254d0c2a1dea0d1ad1a22c89141d4294d650e088e003 

MD5  7a2b1a00f24a26d69ed0f8d9a7b220dc 

BLAKE2256  5f2361b765fe8a59e61a436d29a6dd418b75566d82fb4b14fb9eabb3d8697d78 
Hashes for chiavdf1.0.1cp38cp38win_amd64.whl
Algorithm  Hash digest  

SHA256  935070f6be8956dec3c9b4d15e14cb1213d7fef28202e056b491b63a68b6603f 

MD5  44be13fa9ca6c991b5c2bfecf70016e3 

BLAKE2256  5f28490be38edf5023478b86044a75de9aeae86332408426517a9fe997770a7c 
Hashes for chiavdf1.0.1cp39cp39macosx_10_14_x86_64.whl
Algorithm  Hash digest  

SHA256  c3dfb9e4caeb8ec8c767ee7ebab9214d71b465d75bf46d5ee79958ebf28f7473 

MD5  7181371fc8b7605b7096b4c7d4bfca83 

BLAKE2256  280c78b93fe5d74c176dd9157ced3ac0dc4b6962360dc20bd6d451d0eb57ef9c 
Hashes for chiavdf1.0.1cp39cp39macosx_11_0_arm64.whl
Algorithm  Hash digest  

SHA256  4a70495a6f2eefa80e5adcc5ba8cb34bd516525b6d327fd91d78fd03e1ba1e1c 

MD5  97b3ef0a62e4506a3d52b691938ea40e 

BLAKE2256  1f138da69abb323aeebc0517e9d525637bc2e9e4bc1629cfaf1542fb2e0249be 
Hashes for chiavdf1.0.1cp39cp39manylinux2010_x86_64.whl
Algorithm  Hash digest  

SHA256  cb882ff2680d27e2ee1211cb3e29a506591ce5fc1a8aebd70554ebd2451c6aca 

MD5  267a849ed7ea66c10c79649b24c18cfc 

BLAKE2256  cfa4e376908ee0de0c2ccfae4c59fbab771cc971225ff99f9155bb989a7c2d37 
Hashes for chiavdf1.0.1cp39cp39manylinux2014_aarch64.whl
Algorithm  Hash digest  

SHA256  f8447ae719dc9fd15006458c945d5e5f9512fc42ed19b26bc61e56424d06817c 

MD5  5d0bd1148732bb7c47baab1c68208243 

BLAKE2256  37dfa9ca062c703a522b4572bbce25f6e915b9f570d3e7dcae32cf0b5311bd94 
Hashes for chiavdf1.0.1cp39cp39win_amd64.whl
Algorithm  Hash digest  

SHA256  0ae29f80a763771f63c032b70b769b71898da4bd120fcc808c5db11985adcd51 

MD5  beea0623fb87a32ce971dd9e633f498d 

BLAKE2256  7b31b3bbefc27563b7119e68727f49f292b83402d37c09bd677990ae156e2175 