# Boojum Gadgets
***
Gadgets in ZK programming are common arrangement of circuits abstracted for ease of use. Boojum gadgets are low-level implementations of tools for constraint systems. They consist of various types such as curves, hash functions, lookup tables, and different circuit types.
These gadgets are mostly a reference from [franklin-crypto](https://github.com/matter-labs/franklin-crypto), with additional hash functions added. These gadgets have been changed to use the Goldilocks field (order 2^64 - 2^32 + 1), which is much smaller than bn256. This allows us to reduce the proof system.
### Circuits types
We have next types with we use for circuits:
**Num (Number):**
```rust
pub struct Num {
pub(crate) variable: Variable,
pub(crate) _marker: std::marker::PhantomData,
}
```
**Boolean:**
```rust
pub struct Boolean {
pub(crate) variable: Variable,
pub(crate) _marker: std::marker::PhantomData,
}
```
**U8:**
```rust
pub struct UInt8 {
pub(crate) variable: Variable,
pub(crate) _marker: std::marker::PhantomData,
}
```
**U16:**
```rust
pub struct UInt16 {
pub(crate) variable: Variable,
pub(crate) _marker: std::marker::PhantomData,
}
```
**U32:**
```rust
pub struct UInt32 {
pub(crate) variable: Variable,
pub(crate) _marker: std::marker::PhantomData,
}
```
**U160:**
```rust
pub struct UInt160 {
pub inner: [UInt32; 5],
}
```
**U256:**
```rust
pub struct UInt256 {
pub inner: [UInt32; 8],
}
```
**U512:**
```rust
pub struct UInt512 {
pub inner: [UInt32; 16],
}
```
Every type consists of a Variable (the number inside Variable is just the index):
```rust
pub struct Variable(pub(crate) u64);
```
which is represented in the current Field. Variable is quite diverse. To have "good" alignment and size we manually do encoding management to be able to represent it as both a variable (that can be copied) or witness.
The implementation of this circuit type itself is similar. We can also divide them into classes as main and dependent: Such type like U8-U512 decoding inside functions to Num\ for using them in logical operations. As mentioned above, the property of these types is to perform logical operations and allocate witnesses.
Let's demonstrate this in a Boolean example:
```rust
impl CSAllocatable for Boolean {
type Witness = bool;
fn placeholder_witness() -> Self::Witness {
false
}
#[inline(always)]
fn allocate_without_value>(cs: &mut CS) -> Self {
let var = cs.alloc_variable_without_value();
Self::from_variable_checked(cs, var)
}
fn allocate>(cs: &mut CS, witness: Self::Witness) -> Self {
let var = cs.alloc_single_variable_from_witness(F::from_u64_unchecked(witness as u64));
Self::from_variable_checked(cs, var)
}
}
```
As you see, you can allocate both with and without witnesses.
### Hash function
In gadgets we have a lot of hast implementation:
* blake2s
* keccak256
* poseidon/poseidon2
* sha256
Each of them perform different functions in our proof system.
### Queues
One of the most important gadgets in our system is queue. It helps us to send data between circuits. Here is the quick explanation how it works:
```rust
Struct CircuitQueue{
head: HashState,
tail: HashState,
length: UInt32,
witness: VecDeque,
}
```
The structure consists of `head` and `tail` commitments that basically are rolling hashes. Also, it has a `length` of the queue. These three fields are allocated inside the constraint system. Also, there is a `witness`, that keeps actual values that are now stored in the queue.
And here is the main functions:
```rust
fn push(&mut self, value: Element) {
// increment length
// head - hash(head, value)
// witness.push_back(value.witness)
}
fn pop(&mut self) -> Element {
// check length > 0
// decrement length
// value = witness.pop_front()
// tail = hash(tail, value)
// return value
}
fn final_check(&self) -> Element {
// check that length == 0
// check that head == tail
}
```
So the key point, of how the queue proofs that popped elements are the same as pushed ones, is equality of rolling hashes that stored in fields `head` and `tail`.
Also, we check that we can’t pop an element before it was pushed. This is done by checking that `length >= 0`.
Very important is making the `final_check` that basically checks the equality of two hashes. So if the queue is never empty, and we haven’t checked the equality of `head` and `tail` in the end, we also haven’t proven that the elements we popped are correct.
For now, we use poseidon2 hash. Here is the link to queue implementations:
* [CircuitQueue](https://github.com/matter-labs/era-boojum/blob/main/src/gadgets/queue/mod.rs#L29)
* [FullStateCircuitQueue](https://github.com/matter-labs/era-boojum/blob/main/src/gadgets/queue/full_state_queue.rs#L20C12-L20C33)
The difference is that we actually compute and store a hash inside CircuitQueue during `push` and `pop` operations. But in FullStateCircuitQueue our `head` and `tail` are just states of sponges. So instead of computing a full hash, we just absorb a pushed (popped) element.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://validium.gitbook.io/docs/components/prover/boojum-gadgets.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.