---
# System prepended metadata

title: Lasso presentation notes

---

# Lasso presentation notes

Notes on the Lasso presentation and further conversations

### Overall idea using an OR operation as an example:

![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FDU7DorkSE8.png?alt=media&token=ca28ec3a-ccdf-4ba4-883d-3f6819c103db)

Represent the operands as bit-vectors
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2Fn_2h6BlGei.png?alt=media&token=475285ad-2b3b-4085-8fb5-78d9b397d0f3)

Split them into eight 4-bit chunks
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FzefspOOzB7.png?alt=media&token=aaa1b751-cc69-41f5-ba79-fcf8036ebaa6)

Join each column into an 8-bit lookup table
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FnpKt0unDdO.png?alt=media&token=e6f867e9-ca1a-463c-8979-3364a6ba5d25)

Lasso springs from Spartan. Spartan uses Spark. The Polynomial Commitment Scheme of Lasso is Surge
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FAgelo7N-8P.png?alt=media&token=ff41bb78-be5b-42a8-9874-635f91875acd)

### Multilinear extensions

To make use of the Sum Check protocol, we transform each function into a multilinear extension. The domain becomes the boolean hypercube, that is, sequential integer indexes are represented as bit vectors
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FOosYLLzW4T.png?alt=media&token=bb76d9da-cb10-45e2-be0a-5787f9597fb3)

The boolean cube is the domain for the multilinear extension of this example
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2Fxw89VLicnp.png?alt=media&token=7832b06d-9307-4324-ae2a-65f3e9751cee)

As mentioned, EQ~ is defined for a bigger domain than EQ that we need for the Sum Check protocol
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FUr-8BbPUCN.png?alt=media&token=940a43df-b53f-472d-8ebc-1d543d7c8721)

### Jolt

While their Lasso implementation is ready to use, their Jolt implementation is under development in this branch github.com/a16z/lasso/tree/moodlezoup/jolt
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FEV8LJgtRdZ.png?alt=media&token=1f404bb9-c167-43be-9021-279f6a409e1f)

Understanding Surge (the Polynomial Commitment Scheme) is needed to build a Jolt VM, but apparently only that first paragraph in the Lasso paper
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FNF13Amu9fr.png?alt=media&token=13392305-351e-407c-a0a2-001a74d797b6)

#### Jolt API
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2F_xvf6jz7g5.png?alt=media&token=317b1b29-c620-4c57-9ee6-e05837412e9a)
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FN9A-Rw-fiO.png?alt=media&token=ecdf2b86-3e94-4bb1-8dd2-8b36da7c7f6c)
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FEuj3NjA5o9.png?alt=media&token=18c2d3fc-3144-47d5-86de-2ba6ba68e570)

`materialise` is the evaluation over the boolean hypercube. `evaluate_mle` is the evaluation over the extension function ~
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FXHb5XIN1u4.png?alt=media&token=70450110-3e13-4772-902a-e09d07ddb503)

### Example of an instruction VM:  8-bit EQ instruction Implementation
 
Convert to bit vectors and compare each bit. If all bits are equal, then 1 else 0
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FfeHEEcrC9I.png?alt=media&token=fe5e1c3b-a57a-4d00-b553-907edf69dcfc)
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FqFgL3posOt.png?alt=media&token=01b03413-528a-4b73-8521-4fe820a77db7)

A useful mental model is a lookup table. On 64 bit operands, this table becomes size 2^128. This is too big, so we need to do something else
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FLGYG--LGcd.png?alt=media&token=1a8a4c4a-d6a8-4f70-aa17-153e51712e90)

The solution is to split the input vectors into a series of 2-bit instructions. Bitwise operations are independent.

C is the subtable dimensionality (4 in this case). This creates a set of much smaller tables
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FKz2wX607b9.png?alt=media&token=2a0bd82a-0e10-425c-bc96-0ce5cc8d5dfc)

Splitting a lookup table into smaller lookup tables is efficient because the reduction is logarithmic. E.g.  The cost of looking up a matrix of size (2^128) becomes the cost of looking up 2^{128/C} * (cost of constructing a structured submatrix) where C is a parameter we can choose.
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2Fhmk6HbOcAC.png?alt=media&token=46fe2bf9-a7ff-4185-907e-0739cca210d7)
- k is the number of subtable types you need to define the big table instruction
- g is how you combine subtables into a big table evaluation. In this case, it is just the product
- M is the size of the small subtables
- C is the number of subtables
  
### Implementation of the 8-bit EQ instruction
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2F-4nuWggrZT.png?alt=media&token=28b28b32-fc22-406a-ba89-aeef42e0960c)
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FHephJ5vkGv.png?alt=media&token=12e0e994-101a-4ac8-bc50-c80d433ac85a)
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2F844GbOHDmw.png?alt=media&token=0ad8e767-5d48-4b8e-8398-49e26facb9aa)
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FWTJumm9JGH.png?alt=media&token=ef16cf8b-3412-44fb-b79d-9fafbaa5ef72)
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FoR6GcwT8Ta.png?alt=media&token=668226f5-7535-4301-a249-38b2fc82497b)
![](https://firebasestorage.googleapis.com/v0/b/firescript-577a2.appspot.com/o/imgs%2Fapp%2Facentelles%2FIOnD2XWqjD.png?alt=media&token=4493e9d9-7710-45e3-b1d5-658a1228c037)

### Other considerations
- Arithmetisation is not relevant here. It's only lookups that Lasso deals with. I believe Lasso uses Hyrax as a proving system right now but that is not important for us
- Many VMs can share instructions. This is great for auditing
