The bitcoin stack can be at most 1000 elements, which poses a significant limitation on our ability to move data into the script. Using binary Lamport signatures would limit us to at most 1000 bits of data which is too small to do much useful work. Using Winternitz (or even Lamport signatures with a larger base) lets us move more data into the script.

To do one round of the Miller loop we need at least 2 Fq12 elements, 1 E/Fq, and 2 E/Fq2 elements which is 30 Fq elements. This takes 30 * 254 = 7620 elements which means we probably need to use at least base 8.

Need to figure out, depending on how expensive the scripts are, what is the optimal trade off between base size for the signatures and script size. Increasing script size necessitates a large base (exponential in the script length) but uses fewer rounds (linear in script length).

For example, when Paul and Vicky find the disputed instruction is :

Add. add_A, add_B, add_C, val_A, val_B, val_C

Both Paul and Vicky could reveal this instruction and push these data on Bitcoin to execute Punish Equivocation.

Why do there need additional challenges for each element?

The following script should be valid

let script = script! {
    0x42
    { 0x42 } 
    OP_EQUALVERIFY
};

A fundamental limitation of Bitcoin Script is the maximum stack depth of 1000 items. Thus, we want our algorithms to be "shallow", i.e., they should operate over a minimal number of stack items.

For this reason, our tests should print the script's max stack depth along with the script length

I love the project and want to contribute to it is thea any contribution guide or documentation to help understand how the project works fully

MULH basically keeps the upper 4 bytes of the 64-bit result of a 32-bit multiplication

Generalize the environment introduced in blake3 to automatically track elements on the stack, allowing to address them with human-readable identifiers.

A possible syntax for the pointer system might be

OP_PUSH { xxx } as a
OP_PUSH { xxx } as b
...
...
...
OP_PICK a
OP_PICK b

where PUSH { xxx } as a is just an additional pseudo instruction that says "save the current position into a literal".

A key problem is that it is impossible to track stack items for many kinds of scripts. That is because the stack might depend on user input, which means we cannot know the state of the stack during compile time. In our blake3 implementation it wasn't very relevant because the code doesn't branch based on user input.

Currently, we support only one 40-byte or 64-byte inputs. We need an implementation for 512-byte and 1024-byte inputs.

Implement SHA256 and double SHA256 in Script (for up to 80 bytes)

Here is a JavaScript implementation of Winternitz signatures. Port this to Rust and also adapt it to our actor model as in u32_state.

The following code checks the bounds of each Winternitz digit:

This full check doesn't seem to be required. If the digit is negative, then OP_PICK will fail.

Therefore the following code could be replaced:

OP_DUP
 0
 { D + 1 }
 OP_WITHIN 
 OP_VERIFY

by

 OP_DUP
 { D + 1 }
 OP_LESSTHAN
 OP_VERIFY

If we don't care about digit uniqueness, we can reduce the size further and just limit it to D:

 { D }
 OP_MIN

3 opcodes are saved.
Am I missing something?

In the draft implementation we had a neat web-based interpreter for Tree++. We should have that again and improve it to make it easy to play around with scripts

The operator's trace commitment consists of many large Winternitz signatures.

Due to the max stack height, we can't fit many signatures into a single output. Thus, we will have to use a transaction with multiple outputs in parallel, overcoming that limit. However, that comes at the cost of the overhead for multiple outputs.

Let's implement a transaction and benchmark the number of bits we can sign per block.

Background on Pairings

The theory of pairings (and prerequisite number theory) is explained in detail elsewhere, so I will assume the reader either knows the background or will accept all pairing related claims as fact.

Elliptic curves are defined over a field Fq (also called base field) and can be multiplied from scalars in another field Fr (the scalar field). For BN254, both Fq and Fr are prime fields about 254 bits in length (q, r ~ 2^254). Pairing curves have two subgroups of points G1, G2 and produce a value in Gt. For BN254, G1 consists of curve points on a curve E/Fq (E over Fq), G2 consists of points on a curve E'/Fq2 (E' over Fq2) which is a "twist" of E, and Gt points are values in Fq12.

The Tate (Ate) pairing consists of two phases: the Miller loop and the final exponentiation. The miller loop involves taking a set of 256 lines in Fq2, twisting these lines into Fq12, and evaluating the lines at a point in Fq, and multiplying the result. The final exponentiation consists of clearing the Fq12 cofactor by raising to a ~3000 bit exponent. Both of these phases can be simplified by exploiting the structure of Frobenius, which is often called the Ate pairing.

In the Ate pairing case the Miller loop only uses ~64 rounds and the final exponentiation involves only ~768 bits (q^4 - q + 1 / r).

I denote a mult with (X, Y)M where X, Y are fields and an add with (X, Y)A.

Miller Loop

Each round of the Miller loop involves: (Fq12, Fq12)S + ( 2 (Fq, Fq2)M + 2 (Fq2, Fq12)M + (Fq12, Fq12)M + (Fq12, Fq12)A + (Fq12, Fq)A ) b to evaluate the line and multiply the accumulator where b is the current bit. The BN254 x = 4965661367192848881 which I think has about half the bits set and is about 64 bits. This gives 64 (Fq12, Fq12)S + 32 ( 2 (Fq, Fq2)M + 2 (Fq2, Fq12)M + (Fq12, Fq12)M + (Fq12, Fq12)A + (Fq12, Fq)A )

In the case of a variable second argument, we also need to add points in G2. As per https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html point addition and doubling are both like 10 mults. This gives 960 (Fq2, Fq2) M for the whole addition chain.

Final Exp

I think we can completely eliminate this so I won't go into it here. This will represent a substantial savings over existing implementations.

Field Arithmetic Costs

BN254 is implemented using a tower of fields, so (Fq2, Fq2)M = 3 (Fq, Fq)M using Karatsuba (Fq2, Fq12)M = 3 * (12/2) (Fq, Fq)M = 18 (Fq, Fq)M and (Fq12, Fq12)M = 3 * 3 * 5 (Fq, Fq)M = 45 (Fq, Fq)M using Karatsuba twice and Toom-Cook once for the degree 3. Not sure if this is optimal since there are a bunch of adds, but these are generally cheaper. Squaring saves about half, so call it 25.

For the Miller loop without point additions we find
64 * 25 (Fq, Fq)M + 32( 2 * 2 + 2 * 18 + 25) (Fq, Fq)M + 32 (13) (Fq, Fq)A = (3680 + C0) (Fq, Fq)M + (416 + C1) (Fq, Fq)A

Where C0 is fairly small and C1 is quite large. C0 comes from all the extra lines at the end. The line computation adds an additional 2880 (Fq, Fq)M. So roughly 7000 (Fq, Fq)M for the Miller loop.

In our JavaScript prototype we had automatic code optimizations for simple patters, e.g. replace 1 OP_ROLL with OP_SWAP.

We should implement that again.

I believe you guys can't use the latest rust-bitcoin. If you want, I can try help push that forward by:

• Upstreaming anything you need from Steven's fork
• Doing the upgrade

Please either close this and tell me to go away or throw some notes up for me and I'll get to it.

We'd like to use BitVM to help test release candidates of rust-bitcoin.