There are fixed bases in the Orchard protocol:
- , used in deriving the nullifier;
- , used in spend authorization;
- base for ;
- and bases for ; and
- base for .
We support fixed-base scalar multiplication with three types of scalars:
A -bit scalar from . We decompose a full-width scalar into -bit windows:
The scalar multiplication will be computed correctly for representing any integer in the range - that is, the scalar is allowed to be non-canonical.
We range-constrain each -bit word of the scalar decomposition using a polynomial range-check constraint: where
We support using a base field element as the scalar in fixed-base multiplication. This occurs, for example, in the scalar multiplication for the nullifier computation of the Action circuit : here, the scalar is the result of a base field addition.
Decompose the base field element into three-bit windows, and range-constrain each window, using the short range decomposition gadget in strict mode, with
If is witnessed directly then no issue of canonicity arises. However, because the scalar is given as a base field element here, care must be taken to ensure a canonical representation, since . That is, we must check that where the is Pallas base field modulus Note that
To do this, we decompose into three pieces:
We check the correctness of this decomposition by: If the MSB is not set, then However, in the case where , we must check:
To check that we make use of the three-bit running sum decomposition:
- Firstly, we constrain to be a -bit value by enforcing its high bits to be all-zero. We can get from the decomposition:
- Then, we constrain bits of to be zeroes; in other words, we constrain the three-bit word We make use of the running sum decomposition to obtain
Define . To check that we use 13 ten-bit lookups, where we constrain the running sum output of the lookup to be if
A short signed scalar is witnessed as a magnitude and sign such that
This is used for . We want to compute , where
and are each already constrained to bits (by their use as inputs to ).
Decompose the magnitude into three-bit windows, and range-constrain each window, using the short range decomposition gadget in strict mode, with
Then, we precompute multiples of the fixed base for each window. This takes the form of a window table: such that:
- for the first (W-1) rows :
- in the last row :
The additional term lets us avoid adding the point at infinity in the case . We offset these accumulated terms by subtracting them in the final window, i.e. we subtract .
Note: Although an offset of would naively suffice, it introduces an edge case when . In this case, the window table entries evaluate to the same point:
In fixed-base scalar multiplication, we sum the multiples of at each window (except the last) using incomplete addition. Since the point doubling case is not handled by incomplete addition, we avoid it by using an offset of
For each window of fixed-base multiples :
- Define a Lagrange interpolation polynomial that maps to the -coordinate of the multiple , i.e.
- Find a value such that is a square in the field, but the wrong-sign -coordinate does not produce a square.
Repeating this for all windows, we end up with:
- an table storing coefficients interpolating the coordinate for each window. Each -coordinate interpolation polynomial will be of the form where and 's are the coefficients for each power of ; and
- a length- array of 's.
We load these precomputed values into fixed columns whenever we do fixed-base scalar multiplication in the circuit.
Given a decomposed scalar and a fixed base , we compute as follows:
- For each in the scalar decomposition, witness the - and -coordinates
- Check that is on the curve: .
- Witness such that .
- For all windows but the last, use incomplete addition to sum the 's, resulting in .
- For the last window, use complete addition and return the final result.
Note: complete addition is required in the final step to correctly map to a representation of the point at infinity, ; and also to handle a corner case for which the last step is a doubling.
where (from the Pallas curve equation).
Recall that the signed short exponent is witnessed as a bit magnitude , and a sign Using the above algorithm, we compute . Then, to get the final result we conditionally negate using .
Note: this doesn't include the last row that uses complete addition. In the implementation this is allocated in a different region.