Qyra

Qyra is a cutting-edge library designed for integrating a quantum-resistant Proof-of-Work (PoW) mechanism in cryptocurrency systems. Inspired by Directed Acyclic Graphs (DAGs), the Depth-First Search (DFS) for the longest path, and Kyber-768 cryptography, Qyra offers resistance against both ASIC and quantum attacks, making it a future-proof solution for blockchain security.

Features

• Quantum Resistance: The integration of the Kyber-768 cryptographic suite provides robust security against potential quantum computing vulnerabilities, ensuring that PoW mechanisms remain viable in a post-quantum era.

• ASIC Resistance: The design of Qyra employs a DAG structure and a longest path search algorithm to limit the efficiency of specialized ASIC devices, promoting a more decentralized mining environment.

• Efficient Path Search: Qyra utilizes advanced algorithms, specifically the Depth-First Search (DFS), for finding the longest path within the DAG. This is crucial for generating PoW solutions efficiently, ensuring that the computational burden is evenly distributed across available resources.

• Multithreading Capabilities: Qyra leverages multithreading both for generating solutions and for validating them. This design choice significantly improves the library's performance, allowing it to take full advantage of modern multi-core processors. By distributing tasks across multiple threads, Qyra enhances throughput and reduces the time required for both generation and validation of PoW solutions.

• Cryptographic Security: Modern cryptographic techniques are leveraged to enhance security without compromising performance, making Qyra suitable for high-demand cryptocurrency applications.

How It Works

Solution Generation

1. Directed Acyclic Graph (DAG): At the core of Qyra is a Directed Acyclic Graph (DAG) structure, which is used to generate and validate Proof-of-Work (PoW) solutions. The challenge consists of identifying the longest path in the DAG using Depth-First Search (DFS), a computationally intensive problem that adds significant security to the PoW mechanism. The generation of this graph and the entire solution is tightly coupled with advanced cryptographic processes to ensure quantum resistance.

2. Quantum-Safe Kyber-768: Qyra employs the Kyber-768 cryptographic suite to ensure security even against quantum computing attacks. This algorithm is used to generate a shared secret key and a ciphertext. Here is the detailed process:

   • Input Parameters - header and nonce: The PoW generation begins by concatenating two primary input vectors, the header (composed of values like the version, previous block hash, Merkle root, reserved hash, timestamp, and bits) and the nonce. Together, these form the seed for the cryptographic operations that follow.

   • Kyber-768 Encryption: Using the concatenated header and nonce, the Kyber-768 algorithm generates a 32-byte shared secret key and a ciphertext. This shared secret key plays a crucial role in the encryption process that follows.

   • AES-256-CBC Encryption: The shared secret key generated by Kyber-768 is then used as the key for AES-256-CBC encryption. The encryption process also makes use of a 16-byte Initialization Vector (IV). The result of this encryption is an encrypted value, which will be used to populate the DAG.

3. DAG Population and 12-Bit Indexing: The DAG, which has a size of 4096 x 4096 bits (2048 MiB), is populated using the encrypted value produced by AES-256-CBC. This encrypted data is read and partitioned into 12-bit chunks, which are used as indices to assign values to the nodes of the graph. This ensures that the graph is securely and pseudorandomly filled based on the cryptographic output.

4. Longest Path Search with DFS: Once the DAG is fully populated, Qyra performs a Depth-First Search (DFS) to identify the longest path in the graph. This search process is the heart of the computational workload required to find the valid PoW solution. The longer the path, the more secure and computationally expensive the solution becomes.

5. Blake3 Hashing: After the longest path is found, Qyra computes a hash of this path using the Blake3 hashing algorithm, generating a 256-bit (32-byte) hash. This hash serves as the final cryptographic proof of the computed solution.

6. Final Solution Components: The solution returned by Qyra is composed of the following elements:

   • encMessage: The AES-256-CBC encrypted message, which is derived from the shared secret generated by Kyber-768.
   • IV: The Initialization Vector used in the AES-256-CBC encryption.
   • ciphertext: The ciphertext produced during the Kyber-768 encryption phase.
   • hash: The 256-bit Blake3 hash calculated from the longest path found in the DAG.

7. Resistance to ASICs: Qyra's DAG structure, combined with the DFS path-finding algorithm, introduces a high computational complexity that limits the effectiveness of specialized hardware like ASICs. This design choice helps maintain decentralization by allowing general-purpose hardware, such as standard CPUs and GPUs, to compete effectively within the network.

Solution Validation

The validation process in Qyra ensures that a given solution is correct and was genuinely generated using the provided header and nonce. The steps of the validation are as follows:

1. Solution Decomposition: The solution passed as input is decomposed into its constituent parts:

   • encMessage: The encrypted message produced by AES-256-CBC during the solution generation.
   • IV: The Initialization Vector used in the AES-256-CBC encryption.
   • ciphertext: The ciphertext produced during the Kyber-768 encryption.
   • hash: The final Blake3 hash computed from the Depth-First Search (DFS) of the DAG during the solution generation.

2. Kyber-768 and AES-256-CBC Decryption:

   • First, the Kyber-768 encryption is reversed using the provided ciphertext, recovering the original shared secret key.

   • Then, using the shared secret key and the provided IV, the validation process decrypts the encMessage by reversing the AES-256-CBC encryption. This decryption step recovers the original values that were used to populate the DAG, specifically the header and nonce.

   • If the decrypted values match the header and nonce, this confirms that the DAG was genuinely generated using the correct input data. This ensures that the graph used for the DFS computation is valid and corresponds to the expected block.

3. Graph Regeneration and Validation: Using the decrypted encMessage, the DAG is repopulated exactly as it was during the original solution generation. The validation process then:

   • Performs a Depth-First Search (DFS) on the regenerated DAG to find the longest path, just as in the generation phase.
   • Computes a Blake3 hash on the longest path found in this new DFS.

4. Hash Comparison: The final step is to compare the newly computed Blake3 hash from the DFS with the hash provided in the solution. If the two hashes match, this means:

   • The longest path found in the graph is correct.
   • The entire solution is valid and was generated correctly using the specified header, nonce, and cryptographic processes.

This process ensures that both the structure of the DAG and the DFS-based solution are fully validated before a solution is accepted. By leveraging quantum-safe cryptographic algorithms (Kyber-768 and AES-256-CBC) and a robust hashing mechanism (Blake3), Qyra maintains a high level of security throughout the validation process.

Getting Started

To use Qyra in your cryptocurrency or blockchain project, follow these instructions:

Prerequisites

Ensure you have the following libraries and tools installed:

• Boost: Required only for running the test suite, providing additional utility libraries.
• OpenSSL: Qyra requires OpenSSL for secure hashing and cryptographic functions, including AES-256 encryption.
• Blake3: Qyra uses Blake3 for fast and secure hashing with the BLAKE3 algorithm.
• Liboqs: Qyra utilizes Liboqs for quantum-resistant cryptography (Kyber-768).
• Pkg-config: A helper tool used for configuring compiler and linker flags for libraries.
• Make: Build tool for managing the build process.
• GCC/G++: The GNU Compiler Collection for compiling C and C++ code.
• Autoconf: A tool for automatically configuring source code packages.
• Automake: A tool for generating Makefile.in files from Makefile.am files.
• Doxygen: Required for generating project documentation.

For Ubuntu/Debian based systems, you can install the prerequisites using:

sudo apt-get install autoconf autoconf-archive autotools-dev automake build-essential cmake doxygen git libtool pkg-config libboost-dev libssl-dev

git clone https://github.com/BLAKE3-team/BLAKE3.git
pushd BLAKE3
git checkout tags/1.5.4
cd c
mkdir build
cd build
cmake ..
make
sudo make install
popd

git clone --recurse-submodules https://github.com/open-quantum-safe/liboqs.git
pushd liboqs
git checkout tags/0.11.0
mkdir build
cd build
cmake ..
make
sudo make install
popd

For Fedora based systems, use:

sudo dnf install autoconf automake doxygen gcc-c++ git libtool make blake3-devel boost-devel liboqs-devel openssl-devel

Installation

1. Clone the repository:

   git clone https://github.com/marcofortina/qyra.git
   cd qyra

2. Build the project using the provided Makefile:

   ./autogen.sh
   ./configure
   make # use "-j N" for N parallel jobs

Testing

To ensure the correctness and reliability of the Qyra library, a comprehensive suite of tests has been implemented. The tests cover various aspects of the system, including graph generation, solution validation, cryptographic functions, and performance under different conditions.

To run the full test suite:

src/test/qyra-test

Benchmarking

To benchmark the performance of the Qyra library:

src/bench/qyra-bench

Debugging

To enable debug mode during compilation, use:

./configure --enable-debug
make

Additional Configure Flags

A list of additional configure flags can be displayed with:

./configure --help

API

For detailed information on how to use Qyra in your projects, refer to the API documentation.

Donations

If you find Qyra useful and would like to support its development, consider making a donation to the following Bitcoin address:

1N2rQimKbeUQA8N2LU5vGopYQJmZsBM2d6

Your support is greatly appreciated!

License

Qyra is distributed under the MIT License. See the accompanying LICENSE file for more details.

Contributing

Contributions to Qyra are welcome! Feel free to open issues or submit pull requests on the GitHub repository.

Acknowledgements

Qyra is inspired by the cryptographic advancements in quantum-safe algorithms and PoW research. Special thanks to the teams behind Kyber and liboqs for their groundbreaking work in post-quantum cryptography.