A collection of functions written in Triton VM assembly (tasm)

Related tags

Utilities tasm-lib
Overview

tasm-lib

This repository contains a collection of functions written in Triton VM assembly (tasm).

There are two big projects to be written in tasm:

  • The consensus logic of Neptune
  • The recursive Triton VM STARK verifier (recufier)

This repository helps get an overview of the run times of the consensus code and the recufier code.

Please place code in the appropriate directories, or create them if non-existent.

The lists below keep track of improvements to individual algorithms. If the cycle count changes because Triton VM is updated, or you find a better way of solving a problem, then add a new line to the appropriate table, add a comment to the two relevant lines, and add a counter to the algorithm name, or update the TVM version when appropriate.

Consensus Code

Name Author(s) Last edited TVM version Tested and Rust-shadowed Notes Cycle Count Asymptotic Runtime

Recufi Code

Name Author(s) Last edited TVM version Tested and Rust-shadowed Notes Cycle Count Asymptotic Runtime

Other Code Snippets

Name Author(s) Last edited TVM version Notes Cycle Count Hash table height Asymptotic Runtime
bfe_add sword_smith 20221208 0.8.0 3 0
hash sshine, sword_smith 20221208 0.8.0 0 9

u32

Name Author(s) Last edited TVM version Notes Cycle Count common Cycle Count worst-case Hash table height Asymptotic Runtime
is_u32 sword_smith 20221208 0.8.0 68 68 0
log_2_floor sword_smith 20221223 0.9.0 180 354 0 $O(N)$

U32s, size 2

Name Author(s) Last edited TVM version Notes Cycle Count common Cycle Count worst-case Hash table height Asymptotic Runtime
incr sshine, sword_smith 20221208 0.8.0 8 20 0 $O(1)$
decr sword_smith 20221208 0.8.0 8 20 0 $O(1)$
add sword_smith 20221208 0.8.0 150 158 0 $O(1)$
sub sshine, sword_smith 20221208 0.9.0 84 92 0 $O(1)$
lt sshine, sword_smith 20221209 0.9.0 154 311 0 $O(1)$
powers_of_two_arithmetic_flat sword_smith 20221208 0.8.0 Adds 17 to cycle count for each increment of the exponent. Range: 11-1090 563 1090 0 $O(N)$
powers_of_two_memory sshine 20221208 0.8.0 Memory unsafe (assumes bounded input), exp >= 32 => +3 cycle count 12 (+ 165) 15 (+ 165) 0 $O(1)$
powers_of_two_static sshine, sword_smith 20221209 0.9.0 264 264 0 $O(1)$
log_2_floor sword_smith 20221223 0.9.0 193 369 0 $O(ln(N))$

Lists (max length: u32::MAX)

Name Author(s) Last edited TVM version Notes Cycle Count common Cycle Count worst-case Hash table height Asymptotic Runtime
length (long) sword_smith 20221220 0.9.0 6 6 0 $O(1)$
length (short) sword_smith 20221220 0.9.0 4 4 0 $O(1)$
push sword_smith 20221220 0.9.0 parameterized over length of list elements, $N$ , 1-16 B field elements 13 + $5\cdot N$ 13 + $N$ 0 $O(1)$
pop sword_smith 20221220 0.9.0 parameterized over length of list elements, $N$ , 1-16 B field elements 17 + $5\cdot N$ 13 + $N$ 0 $O(1)$

MMRA

An MMR is in this context always an MMR accumulator as used in the twenty-first. On the stack it is represented as _ leaf_count peaks where leaf_count is a u64 (two words of u32 values) and where peaks is a pointer into memory where the peaks list is stored.

Name Author(s) Last edited TVM version Notes Cycle Count common Cycle Count worst-case Hash table height Asymptotic Runtime
left_child sshine, sword_smith 20221209 0.9.0 Expensive because u32 arithmetic and no u32 table 354 354 0 $O(1)$
right_child sshine, sword_smith 20221209 0.9.0 You can call decr for U32<2> instead and save a few cycles 10 22 0 $O(1)$
leftmost_ancestor sshine, sword_smith 20221209 0.9.0 With a U32 table, a constant time snippet can be made 10953 21060 0 $O(ln(N))$
right_child_and_height sword_smith 20221216 0.9.0 Cycle count is dominated by leftmost_ancestor 11153 23000 0 $O(ln^2(N))$ ?
count_leaves sword_smith 20221216 0.9.0 Not really needed as leaf_count is a field in MMRA 3 3 0 $O(1)$
get_height_from_data_index sword_smith 20221223 0.9.0 Needed by append through non_leaf_nodes_left 210 379 $O(ln(N))$
non_leaf_nodes_left sword_smith 20221223 0.11.0 Needed by append through data_index_to_node_index 23845 46929 0 $O(ln(N))$
get_peak_heights
data_index_to_node_index sword_smith 20221223 0.11.0 Used by calculate_new_peaks_from_append 23845 46929 0 ?
leaf_index_to_peak_index Needed by append
calculate_new_peaks_from_append Main function for appending
parent Needed by mutating
calculate_new_peaks_from_leaf_mutation Main function for mutating
You might also like...
Rust Util Collection, a simple and friendly error-chain

RUC Rust Util Collection, a simple and friendly error-chain, with many useful utils as an addition. The painful experience of using error-chain gave b

漢 8 Dec 8, 2022
Artifact collection tool for *nix systems
Artifact collection tool for *nix systems

fennec is an artifact collection tool written in Rust to be used during incident response on *nix based systems. fennec allows you to write a configuration file that contains how to collect artifacts.

AbdulRhman Alfaifi 147 Dec 19, 2022
Rust Util Collection, a simple and friendly error-chain, with many useful utils as an addition.

RUC Rust Util Collection, a simple and friendly error-chain, with many useful utils as an addition. The painful experience of using error-chain gave b

漢 6 Mar 27, 2022
A lightning fast version of tmux-fingers written in Rust, copy/pasting tmux like vimium/vimperator
A lightning fast version of tmux-fingers written in Rust, copy/pasting tmux like vimium/vimperator

tmux-thumbs A lightning fast version of tmux-fingers written in Rust for copy pasting with vimium/vimperator like hints. Usage Press ( prefix + Space

Ferran Basora 598 Jan 2, 2023
Simple ray tracer written in Rust
Simple ray tracer written in Rust

Simple ray tracer written in Rust from scratch I've just finished my first semester at the Faculty of Applied Mathematics and Computer Science at the

Vladislav 190 Dec 21, 2022
BSV stdlib written in Rust and runs in WASM environments

BSV.WASM A Rust/WASM Library to interact with Bitcoin SV Installation NodeJS: npm i bsv-wasm --save Web: npm i bsv-wasm-web --save Rust: https://crate

null 56 Dec 15, 2022
Basically a KrabsETW rip-off written in Rust

FerrisETW 🦀 Basically a KrabsETW rip-off written in Rust, hence the name Ferris 🦀 All credits go to the team at Microsoft who develop KrabsEtw, with

n4r1B 25 Dec 21, 2022
A wasm interpreter written by rust

A wasm interpreter written by rust

nasa 69 Dec 6, 2022
Rustymind is a driver and parser for NeuroSky MindWave EEG headset written in pure Rust.
Rustymind is a driver and parser for NeuroSky MindWave EEG headset written in pure Rust.

Rustymind is a driver and parser for NeuroSky MindWave EEG headset written in pure Rust. You can use it to connect, interact, and plot real time data from the headset.

Junjun Dong 34 Sep 13, 2022
Comments
  • occasionally prove the correct execution of the TASM snippets

    occasionally prove the correct execution of the TASM snippets

    Writing a bunch of TASM gives us the opportunity to test Triton VM more rigorously. I suggest to write tests that are

    • ignored by default, but
    • run occassionally where all TASM snippets are thrown into Triton VM and their correct execution proven.
    enhancement good first issue 
    opened by jan-ferdinand 0
  • Change name from `U32<2>` to `u64`?

    Change name from `U32<2>` to `u64`?

    Our u64 support is made by stringing two u32 values together and we call this construction U32s<2> after a convention in twenty-first. But maybe u64 would be a more descriptive and familiar name?

    opened by Sword-Smith 0
Owner
Triton VM
Recursively verifiable STARKs for Triton VM.
Triton VM
GitHub
A command-line tool collection to assist development written in RUST

dtool dtool is a command-line tool collection to assist development Table of Contents Description Usage Tips Installation Description Now dtool suppor

GB 314 Dec 18, 2022
Provides utility functions to perform a graceful shutdown on an tokio-rs based service

tokio-graceful-shutdown IMPORTANT: This crate is in an early stage and not ready for production. This crate provides utility functions to perform a gr

null 61 Jan 8, 2023
📦 🚀 a smooth-talking smuggler of Rust HTTP functions into AWS lambda

lando ?? maintenance mode ahead ?? As of this announcement AWS not officialy supports Rust through this project. As mentioned below this projects goal

Doug Tangren 68 Dec 7, 2021
Tons of extension utility functions for Rust

LazyExt Tons of extension utility functions for Rust. English | 简体中文 Status Name Status Crate Documents Introduction lazyext-slice Alpha Thousands of

Al Liu 2 Dec 5, 2022
Simple and fast git helper functions

Simple and fast git helper functions

LongYinan 126 Dec 11, 2022
Various extention traits for providing asynchronous higher-order functions

async-hofs Various extention traits for providing asynchronous higher-order functions. // This won't make any name conflicts since all imports inside

かわえもん 5 Jun 28, 2022
The lambda-chaos-extension allows you to inject faults into Lambda functions without modifying the function code.

Chaos Extension - Seamless, Universal & Lightning-Fast The lambda-chaos-extension allows you to inject faults into Lambda functions without modifying

AWS CLI Tools 5 Aug 2, 2023
Crate of GitHub’s collection of gitignores, embedded, automatically updated

Gitignores GitHub’s collection of gitignores, embedded, automatically updated. API documentation. Public Domain via CC0-1.0 (same as source data). MSR

null 3 May 3, 2022
mollusc is a collection of pure-Rust libraries for parsing, interpreting, and analyzing LLVM.

mollusc is a collection of pure-Rust libraries for parsing, interpreting, and analyzing LLVM.

William Woodruff 50 Dec 2, 2022
A Rust library containing a collection of small well-tested primitives.

Gazebo - a library of Rust utilities This library contains a collection of well-tested utilities. Most modules stand alone, but taking a few represent

Meta Incubator 168 Dec 29, 2022