AlbaDsl & albaVm: Haskell based DSL and VM for Bitcoin Cash 2025 contract programming

albaDsl · August 19, 2025, 7:27am

The EC multiply code is now 600 bytes. The function table can be seen below. Note that some functions are quite small but called frequently.

Module                                   Line  Function                  Slot  Ops   Sites
------------------------------------------------------------------------------------------
DslDemo.EllipticCurve.Field              27    feMul                     0     4     36   
DslDemo.EllipticCurve.Field              24    feSub                     1     20    9    
DslDemo.EllipticCurve.Field              33    feCube                    2     6     5    
DslDemo.EllipticCurve.JacobianPoint      44    makeIdentity              3     15    4    
DslDemo.EllipticCurve.JacobianPoint      61    getX                      4     5     4    
DslDemo.EllipticCurve.JacobianPoint      66    getY                      5     5     4    
DslDemo.EllipticCurve.JacobianPoint      71    getZ                      6     4     4    
DslDemo.EllipticCurve.Field              45    primeModulus              7     1     3    
DslDemo.EllipticCurve.JacobianPoint      25    makePoint                 8     18    3    
DslDemo.EllipticCurve.JacobianPoint      58    getTag                    9     4     3    
DslDemo.EllipticCurve.Field              39    feInv                     10    41    2    
DslDemo.EllipticCurve.JacobianAdd        19    ecDoubleJ                 11    75    2    
DslDemo.EllipticCurve.JacobianPoint      76    getField                  12    7     2    
DslDemo.EllipticCurve.Jacobian           38    ecMul                     13    48    1    
DslDemo.EllipticCurve.Jacobian           70    toJacobian                14    29    1    
DslDemo.EllipticCurve.Jacobian           81    fromJacobian              15    57    1    
DslDemo.EllipticCurve.JacobianAdd        40    ecAddJ                    16    183   1    
Functions total: 17

albaDsl · August 19, 2025, 7:41am

A feature was added to albaVm to export execution logs to HTML. And a feature to albaDsl for sharing information about the function table with albaVm. This way, the function definitions & calls in the HTML can be decorated/annotated. This can be used to illustrate what I think is the key feature of the Functions CHIP: functions provide a means of abstraction.

As an example we will evaluate this albaDsl program which uses a mini-language of functions (‘feMul’, ‘feAdd’, ‘feSub’, and ‘feCube’) to perform modular arithmetic on field elements (integers):

progAbstraction :: FN s (s > TBool)
progAbstraction =
  begin
    # int 3 # int 7 # feMul # int 1 # feAdd # int 12 # feSub # feCube
    # int 1000 # opNumEqual

The functions definitions are not shown here. In this example, the integer arguments are much smaller than the modulus so the results of the function applications are the same as the corresponding arithmetic operators.

Log #1 shows the execution for when functions are not used. I.e. ‘feMul’ etc. are defined as macros. Execution log #2 shows the result when they are defined as functions and the logs have been annotated with the function names.

log #1 (without functions)
- https://albadsl.github.io/alba-dsl/log-1-macros.html
log #2 (with functions and annotations)
- https://albadsl.github.io/alba-dsl/log-2-functions.html

In log #1 it is hard to see the overall structure of the program and how it ties back to the source code. There is lots of repeated code which one has to continually re-read while trying to grasp what is going on. With functions, the repetition is factored out (log #2). We can read the code at a higher abstraction level and not worry about the underlying details. If we are interested in the details we can expand the function calls by clicking on the respective row. The logging annotation framework hides the OP_INVOKES so that the functions can be read as higher-level opcodes (user defined words in Forth lingo).

I think it is a strength of Bitcoin that the opcode language is readable and not just seen as a compilation target. The functions CHIP greatly improves readability by adding structure and removing repetition. And with functions there can be a one-to-one correspondence between source language constructs and opcode level constructs.

Note how functions in some cases are just a few opcodes long. It is important that the function mechanism is very lightweight for this to be feasible.

albaDsl · August 29, 2025, 7:57am

I implemented a simple windowed version of Elliptic Curve point multiplication. It improves performance and also shows how OP_DEFINE/OP_INVOKE can be used to implement dynamically computed lookup tables.

My previous changes to reduce the code size using functions came with a performance regression to ~38 ms. But the windowed version of EC multiply brings that down to 26 ms (a ~30% improvement). The code size for table setup and multiply comes to 723 bytes.

The following code shows how to use the windowed EC multiply:

test :: FN s (s > TPoint > TPoint)
test =
  begin
    # gTable # g # setupTable
    # gTable # nat 100_000_000_000 # ecMul
    # gTable # nat 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 # ecMul
  where
    gTable = nat 100

    g = <generator point>

In this case we will calculate n*G where G is the generator point. But we could have used any other point on the curve. We first initialize a table for G. It starts at function slot 100 and will stretch to slot 115. The table contains entries for n’*G where n’ goes from 0…15. Each entry is 100 bytes long. We then use the precomputed table in two point multiplications. First with a small scalar and then with a large scalar.

The algorithm works by first breaking down ‘n’ into a string of nibbles. To store these a bytestring on the stack is used: each nibble is stored in a byte and then OP_CATed together. I refer to these as vectors. The algorithm then OP_SPLITs off one nibble at a time from the vector, and uses it as an index into the lookup table to get a point value that is then used in the rest of the computation.

The lookup table could have been stored in a vector too, but OP_INVOKE based lookups are more efficient (especially for random access as here). Vectors have the benefit that they don’t consume the limited slot resource. So this is a trade-off. A combination of vectors and OP_DEFINE/OP_INVOKE probably gives best results.