Alex Johnson Subspace Coding Assignment

Prerequisites

Rust and Cargo

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Installation

Clone the repository and build (debug).

git clone https://github.com/aljo242/subspace_assignment.git
cd subspace_assignment
cargo build

Release Build

cargo build --release

Run

This performs a basic run through: Block -> encoding -> cipher text -> decoding -> Block. Results are printed to the command line.

cargo run

Testing

Tests can be found in ./src/lib.rs.

cargo test

Benchmarking

cargo bench

Description

In Subspace, we adapt the underlying modular square root permutation to create a block cipher. This ensures farmers expend some minimum wall-clock time T (and proportional computation) while encoding each piece, while verifiers only have to expend time T/C to decode each piece, where C is a constant speed-up proportional to the size of the Prime used.

Assignment:

Port the underlying square root permutation to Rust using the C implementation as a guide. Please note that you are not being asked to port Sloth or create a block cipher, only the underlying square root permutation.

For a prime size of 256 bits, derive the largest prime and resulting exponent.
For a given input block of 256 bits (akin to the plain text), compute the modular square root (akin to the cipher text).
For a given output block of 256 btis (akin to the cipher text) compute the inverse square root (which would result in the original plain text).
Provide appropriate unit tests and integration tests.
Provide appropriate comments and inline documentation
Provide an appropriate readme with setup and installation instructions.

Bonus

Create benchmarks using criterion for and determine the constant verification speedup for a 256 bit prime.

Plan:

Set up project skeleton with criterion benchmarking and unit testing
Learn how to use the rug crate to create 256 bit blocks
Translate the equivalent functions from the pysloth C implementation.

License

MIT

aljo242/subspace_assignment