mirror of
https://github.com/tonk-labs/dappicom.git
synced 2026-01-14 16:17:54 -05:00
73 lines
2.9 KiB
Markdown
73 lines
2.9 KiB
Markdown
# Recursion
|
|
|
|
The main idea here is to use a kind of map-reduce style approach to recursively aggregate sub-computations into a final proof which we can verify on-chain.
|
|
|
|
From the trace notes, we will be given the following:
|
|
- a segment of computation A, we can denote A_i
|
|
- address sorted tuples of memory
|
|
- opcode partitioned tuples of memory
|
|
- merkle memory tree of A_i_start, A_i_end
|
|
- vector of dirty page bits for the sequence ?? maybe the circuit itself can compute this
|
|
- pre-computed challenge r
|
|
|
|
## Procedure 1 (memory)
|
|
|
|
> THOUGHT? could we use commitment scheme to more efficiently test a subset of the trace was used in computing the challenge r?)
|
|
>(that would be, we make commitment to the full trace. The commitment is efficiently opened for those entries which make the subset. The challenge r is computed by hash of commitments)
|
|
> I don't know of a scheme like this off the top of my head. Maybe we make the challenge r the root of our merkle tree? Haven't thought about this too much, but for now just cracking on.
|
|
|
|
|
|
This procedure can be parallelized and aggregated
|
|
|
|
## Procedure 1.a (permutation checks)
|
|
1. check the address sorted for memory consistency
|
|
2. compute the partial challenge r for address sorted and opcode memory inputs
|
|
3. compute partial permutation check for address sorted and opcode memory inputs
|
|
4. return partial permutation checks and partial challenges
|
|
|
|
This procedure can be parallelized per page per (start / end) and aggregated
|
|
## Procedure 1.b (continutation checks)
|
|
1. compute the page hash(es) and check merkle inclusion proof(s)
|
|
1. for the beginning merkle tree
|
|
2. for the ending merkle tree
|
|
2. compute the (sub) permutation check for addr sorted
|
|
3. return sub permutation checks
|
|
|
|
## Procedure 2 (opcodes)
|
|
|
|
1. check opcode transitions are correct and consistent
|
|
2. compute sub permutation check, using challenge r
|
|
3. return sub permutation checks
|
|
|
|
## Procedure 3 (opcode aggregation)
|
|
|
|
1. verify opcode a and opcode b
|
|
2. combine sub permutation checks
|
|
3. return combined sub permutation check
|
|
|
|
|
|
## Procedure 4 (memory aggregation)
|
|
|
|
1. hash the partial challenges into intermediate aggregate challenges
|
|
2. verify the sub permutation and continuation checks
|
|
3. return combined sub permutation checks
|
|
|
|
|
|
## Procedure 5 (final memory aggregation)
|
|
1. hash the partial challenges into the final aggregate challenge and check challenge r advice arg
|
|
2. verify the last two memory aggregate circuits
|
|
3. return computed final permutation checks
|
|
|
|
## Procedure 6 (final opcode aggregation)
|
|
1. verify the last two opcodes
|
|
2. combine sub permutation checks into final permutation check
|
|
3. return final permutation check
|
|
|
|
## Procedure 5 (total aggregation)
|
|
|
|
1. verify the aggregation of opcodes
|
|
2. verify the aggregation of memory
|
|
3. verify complete product of memory permutation and opcode permutation are identical
|
|
4. verify the r used in memory and opcode aggregation is identical
|
|
|