Skip to content

Latest commit

 

History

History
149 lines (119 loc) · 10.9 KB

README.md

File metadata and controls

149 lines (119 loc) · 10.9 KB

TapSTARK

TapSTARK is a Bitcoin-friendly proof system enabling on-chain verification through BitVM2 paradigm and Taptree commitment scheme. Built upon Plonky3, it operates independently of OP_CAT.

Core Components

  • Polynomial Commitment: Combines Taptree commitment with bit commitment
  • Cryptographic Hash: Uses Blake3 for permutation hashing
  • Low Degree Testing: Implements FRI protocol
  • STARK Protocol: Follows Plonky3's uni-stark approach
  • Verification DSL: Custom domain-specific language for Bitcoin script generation

Documentation

Domain Specific Language (DSL)

Our DSL facilitates rapid development of Bitcoin verifiers for TapStark. It serves two key purposes:

  1. Streamlines verifier script development
  2. Automates constraint script generation via ScriptAirBuilder

Supported Operations

The DSL supports the following operations over babybear field and its extension:

pub(crate) enum StandardOpcodeId {
    Add,
    Mul,
    Sub,
    Neg,
    Equal,
    EqualVerify,
    NumToField,
    Constant,
    ExpConst,
    IndexToRou,
    Lookup,
    InputVarMove,
    InputVarCopy,
    Table,
    Square,
    Double,
    Blake3Perm,
    ToSample,
    SampleBase,
    SampleExt,
    ReverseBitslen,
}

Usage Example

// Initialize field elements
let vec = vec![
    BabyBear::from_canonical_u32(1),
    BabyBear::from_canonical_u32(2),
    BabyBear::from_canonical_u32(3),
    BabyBear::from_canonical_u32(4),
    BabyBear::from_canonical_u32(5),
];

// Setup environment
let mut stack = StackTracker::new();
let bmap = BTreeMap::new();

// Demonstrate table lookup and arithmetic
let table = Dsl::from_table(&vec);
let index = 4;
let m = table.lookup(index, vec.len());

let a = Dsl::constant_f(BabyBear::one());
let b = Dsl::constant_f(BabyBear::two());
let c = a + b + m;

// Verify computation
let equal = h.equal_for_f(Babybear::from_canonical_u32(7));
let res = equal.express_with_optimize();
println!("Optimized script length: {:?}", res.0.get_script().len());
let res = res.0.run();
assert!(res.success);

Data

You can run this command cargo test --package uni-stark --test fib_air -- test_generate_script_expr --exact --show-output to obtain the below Fibonacci-data.

The data for Recursive RISC0-STARK is an approximate estimate. We have rewritten the recursive constraints of RISC0 using the Plonky3 circuit. Although there are still some minor issues, the data scale can essentially be determined.

bit security(conjectured soundness with 36 pow bits) log blowup factor query_num trace table height(degree) table width public inputs total u32 num(intermediate states) fri u32 num(intermediate states) total script len script len for fri query verify trace constraint script len compute quotient poly challenge script size
91 2 28 Fibonacci 1 << 3 2 3 360 341 12177kb 28 x 428 = 11984 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 3 2 3 300 284 7041kb 16 x 428 = 6848 kb 120kb 73 kb nan
99 4 16 Fibonacci 1 << 3 2 3 300 284 7041 kb 16 x 428 = 6848 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 4 2 3 424 408 8113 kb 16 x 495 = 7920 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 5 2 3 490 471 9185 kb 16 x 562 = 8992 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 10 2 3 829 810 14593kb 16 x 900 = 14400 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 11 2 3 956 937 15681 kb 16 x 968 = 15488 kb 120kb 73kb nan
99 4 16 Recursive R0 1 << 18 163 nan 2904 1600 129.44 MB 16 x 1444 = 23104 kb 100.878mb 6mb (s=5) 2.2 mb

Data

bit security(conjectured soundness with 36 pow bits) log blowup factor query_num trace table height(degree) table width public inputs total u32 num(intermediate states) fri u32 num(intermediate states) total script len script len for fri query verify trace constraint script len compute quotient poly challenge script size
91 2 28 Fibonacci 1 << 3 2 3 360 341 12177kb 28 x 428 = 11984 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 3 2 3 300 284 7041kb 16 x 428 = 6848 kb 120kb 73 kb nan
99 4 16 Fibonacci 1 << 3 2 3 300 284 7041 kb 16 x 428 = 6848 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 4 2 3 424 408 8113 kb 16 x 495 = 7920 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 5 2 3 490 471 9185 kb 16 x 562 = 8992 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 10 2 3 829 810 14593kb 16 x 900 = 14400 kb 120kb 73kb nan
67 2 16 Fibonacci 1 << 11 2 3 956 937 15681 kb 16 x 968 = 15488 kb 120kb 73kb nan
99 4 16 Recursive R0 1 << 18 163 nan 2904 1600 129.44 MB 16 x 1444 = 23104 kb 100.878mb 6mb (s=5) 2.2 mb

TODO List

Taptree Commitmtment

  • support taptree commmitment
  • intergate into fri
    • genereate new taptree for per-query
  • intergate into pcs
  • intergate into uni-stark

ScriptExpr Verifier

  • uni-stark script_expr
    • compute selector script_expr
    • compute quotient script_expr
    • compute constraints script_expr
  • two-adic-pcs script_expr
  • fri script_expr
  • challenge script_expr

ScriptExpr

  • support input variable
  • automatic management of input variables
    • automatic computation of the number of inputs
  • implement copy variable to optimize the compiler
  • Implementing automatic segmentation tool
    • bitcommitment assign
    • extract intermidiate value
  • add verify hint gadget

LICENSE

This repository is under the MIT license. See LICENSE.txt for more information.