Circle STARK Verifier in Bitcoin Script

This repository includes Bitcoin script implements a Circle Plonk verifier in Bitcoin script, consisting of reusable components.

Building Blocks

M31, CM31, QM31, Circle Point: implementation of add, sub, mul of Mersenne-31 (M31) and its complex extension (CM31) and its degree-4 extension (QM31), and specifically table-based mul and non-table-based mul, and implementation of add, sub, mul of circle points, which are over the circle curve x^2 + y^2 = 1.
Fiat-Shamir Transcript: aka "channel", which is the name used in Starkware's stwo library, which supports absorbing and squeezing elements for Fiat-Shamir transform using hints and OP_CAT + OP_SHA256.
Proof-of-Work Check: verifying the proof-of-work used in FRI-based protocols.
FRI: implementation of the FRI quotient polynomial and the protocol for FRI low-degree testing.
Merkle Tree: implementation of Merkle path verification using hints and OP_CAT + OP_SHA256.

License and contributors

This repository is intended to be public good. It is under the MIT license.

A portion of the code is contributed by L2 Iterative (L2IV), a crypto VC based in San Francisco and Hong Kong. The work receives support from Starkware, who is a limited partner in L2IV. For disclosure, L2IV has also invested into numerous companies active in the Bitcoin ecosystem, but this work is open-source and nonprofit, and is not intended for competition. The code is not investment advice.

Starkware contributes a portion of the code, including the original Rust FRI implementation (from stwo) and some Bitcoin scripts.

There are also community members contributing to the code and contributing to the ideas. Bitcoin Wildlife Sanctuary is a public-good project supported by many people.