This repository includes Bitcoin script implementations of various cryptographic primitives for STARK.
x^2 + y^2 = 1
.coset_vanishing()
and pair_vanishing()
.OP_CAT + OP_SHA256
.OP_CAT + OP_SHA256
.OP_CAT + OP_SHA256
.The next step is to implement the FRI protocol, which reasons about the degree of a quotient polynomial.
These performance numbers are obtained from cargo test -- --nocapture
over commit 6e5c211.
The channel is used for Fiat-Shamir transform. It absorbs elements that are either prior knowledge of the verifier or provers' messages, and it can be squeezed to produce pseudorandom elements. There are five operations.
new(digest) -> channel
: initialize a new channel using an initial digest
channel := digest
mix_digest(channel, digest) -> channel'
: update the channel with a digest
channel' := SHA256(channel || commitment)
mix_felts(channel, [qm31]) -> channel'
: update the channel with QM31 elements
channel' := SHA256(channel || commit(qm31))
for each qm31squeeze(channel) -> (qm31, channel')
: squeeze a QM31 element out of the channel
hash := SHA256(channel || 0x00)
channel' := SHA256(channel)
qm31 := extract(hash)
squeeze(channel, logn) -> (q1, q2, q3, q4, q5, channel')
: squeeze five positions on a list of 2^logn elements
hash := SHA256(channel || 0x00)
channel' := SHA256(channel)
q1, q2, q3, q4, q5 := extract(hash, logn)
The constructions of commit and extract are as follows.
Commit. With OP_CAT + OP_SHA256
, we can commit QM31 elements with a few bytes.
QM31 requires 7 bytes: commit(qm31) := SHA256(qm31.0.0 || SHA256(qm31.0.1 || SHA256(qm31.1.0 || SHA256(qm31.1.1))))
OP_SHA256 OP_CAT OP_SHA256 OP_CAT OP_SHA256 OP_CAT OP_SHA256
Extract. Since we do not have OP_SUBSTR
, to extract a QM31 element or five positions from the hash, we need to use hints. The
idea is to peel off the first few bytes of the hash and recreate a normalized QM31 element out of it. If we want to extract
positions, the numbers are further adjusted to have only logn
bits.
hash[0..4]
in the minimal number encoding formhash[4..8]
in the minimal number encoding formhash[8..12]
in the minimal number encoding formhash[12..16]
in the minimal number encoding formhash[16..32]
as bytes, which is the tailhash[0..4]
in the minimal number encoding formhash[4..8]
in the minimal number encoding formhash[8..12]
in the minimal number encoding formhash[12..16]
in the minimal number encoding formhash[16..20]
in the minimal number encoding formhash[20..32]
as bytes, which is the tailDue to the minimal number encoding form, the hint element, which represents a signed 32-bit integer, does not necessarily
have four bytes. Our solution is to use OP_SIZE
to detect its length and then use OP_CAT
to pad it to four bytes.
A subtlety here is that negative numbers, which occur when the original hash's last byte's most significant bit is 1,
need to be handled differently, as it would first be padded with OP_LEFT (0x80)
and then OP_PUSHBYTES_0 (0x00)
.
OP_IF
OP_PUSHBYTES_1 OP_PUSHBYTES_0
OP_ELSE
OP_PUSHBYTES_1 OP_LEFT
OP_ENDIF
Note that OP_PUSHBYTES_0
and OP_LEFT
here are not opcodes but rather data that OP_PUSHBYTES_1
will push to the stack.
One cannot directly write 0x00
and 0x80
in the interpreter, as they would become an empty string and 0x80 0x00
,
respectively.
It first uses OP_CAT
to combine the hint elements together and compare it with the hash that is to be extracted from.
Each of the hint number, after peeling off the sign bit, becomes a non-negative 31-bit number, ranging from 0 to 2^31 - 1. However, in the rest of the computation, we want the number to be below 2^31 - 1. This is done by subtracting one from the resulting number unless the resulting number is zero.
OP_DUP OP_NOT
OP_NOTIF OP_1SUB OP_ENDIF
After such adjustment, one obtains an element.
The Proof-of-Work check accepts two inputs: channel
and nonce
, and checks whether the new channel state channel'=sha256(channel||nonce)
has sufficiently many security bits, namely, n_bits
.
Since we don't have OP_SUBSTR
, the check also requires hints that change depending on whether n_bis
is divisible by 8 or not.
If n_bits % 8==0
, there is a single hint suffix
, and the script checks that
0^(n_bits//8)||suffix==channel'
If n_bits % 8!=0
, together with suffix
, there is an additional byte-sized hint msb
. Consequently, the script checks that
0^(n_bits//8)||msb||suffix==channel'
and also that msb
starts with n_bits % 8
(which would be at least 1) zero bits.
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.
Below we reiterate the contributors to this repository.
victorkstarkware 💻 |
Abdel @ StarkWare 🚧 |
Dependabot 🛡️ |
PayneJoe 💻 |
janusz 👀 |
Deyan Dimitrov 💻 |