Comments (9)
Yep, I remember that. So, for folding factor = 4, once we figure out optimal remainder length, we'll only have to implement 2 procedures. E.g., it could be for size 64 and 32, or for 128 and 64 etc.
That's correct.
I actually think this will be non-negligible because if we know the size, we don't need any conditional logic. But if we don't know the size we need to run a while loop and for each iteration we need to increment the counter and perform inequality comparison. This could add up.
I agree, a while loop is unavoidable. Then I am onboard.
Yep, makes sense. I assumed that would be constructed by evaluating individual queries, and it wouldn't come from the advice tape. Then, we'd compute sequential hash of the and compare it to the commitment in the proof. Would this work, or am I missing something?
Here is how I am thinking about it and let's forget about the hashing for this part. The calling procedure (of fri_verify
) would read ptr
. Then, for each query that we want to verify, at the last step of a query verification we would get an index
(i.e. the folded position) in the range ptr
, to compare the output of the last fold_4
with q[index]
.
This is equivalent to this part.
from miden-vm.
at the last step of a query verification we would get an
index
(i.e. the folded position) in the range [0,lā1] which we can use, together withptr
, to compare the output of the lastfold_4
withq[index]
.
As discussed offline, it may actually make sense to skip the initial reading from the advice tape and just put outputs of the last fold_4
steps at appropriate q[index]
. Then, we can hash them and compare with remainder commitment.
from miden-vm.
I wonder if we should simplify this a little. Specifically, instead of making length verify_remainder_64
. My thinking is that knowing size of the domain upfront will simplify procedure logic quite a bit. Once we have it working for one size, I think creating procedures for other sizes would not be too complicated and we could create verify_remainder_128
etc. (I don't think we'll need more than a handful of these once we find the optimal size).
So, for remainder of size 64, size of
Another thing I wonder is whether
Assuming the above works, the only parameter for verify_remainder_64
would be ptr
which holds the address of the first two coefficients of
- Non-deterministically get
$\tau$ from the advice provider. - Compute
$\beta$ using the formula described in the original description. - Get coefficients of
$p$ from the advice provider. - Compute
$\alpha$ using the formal described in the original description. - Verify that
$\alpha = \beta$ . - Verify that
$\tau$ was provided correctly. To confirm my understanding,$\tau$ is computed by sequentially hashing elements of$q$ and$p$ - right?
Assuming the above is correct, we'll need to add a new decorator the advice injector decorators. This decorator would take domain length
- Interpolate values in
mem[i], ..., mem[i + l - 1]
into polynomial coefficients. - Injected these coefficients into the advice tape.
- Compute
$\tau$ . - Inject
$\tau$ into the advice tape.
The name of decorator could be adv.invnttext2
- but I'm open to other suggestions.
Then, the first couple instructions of verify_remainder_64
would look like this:
export.verify_remainder_64
push.64 # put the size of domain on the stack to prepare for adv.invfft
adv.invnttext2 # set up the advice tape to contain tau and coefficients of p
...
end
from miden-vm.
I wonder if we should simplify this a little. Specifically, instead of making length an input parameter, let's fix the length at 64. So, the procedure could be verify_remainder_64. My thinking is that knowing size of the domain upfront will simplify procedure logic quite a bit. Once we have it working for one size, I think creating procedures for other sizes would not be too complicated and we could create verify_remainder_128 etc. (I don't think we'll need more than a handful of these once we find the optimal size).
Yes, I agree but then, if the initial domain size is not fixed, we would have to implement both versions. This is because of what we discussed some time ago which is that for folding factors higher than
So, for remainder of size 64, size of $q$ would be 64, and size of $p$ would be 8 - right?
That's is exactly right.
Another thing I wonder is whether $p$ should be already assumed to be in memory...
I am assuming that the calling procedure would read the
To confirm my understanding, $\tau$ is computed by sequentially hashing elements of $q$ and $p$ - right?
That is correct.
from miden-vm.
This is because of what we discussed some time ago which is that for folding factors higher than 2 the remainder length can take different values.
Yep, I remember that. So, for folding factor = 4, once we figure out optimal remainder length, we'll only have to implement 2 procedures. E.g., it could be for size 64 and 32, or for 128 and 64 etc.
My thinking is that, with the layout I have used for both and , the delta from a specific procedure to one that is generic is relatively small.
I actually think this will be non-negligible because if we know the size, we don't need any conditional logic. But if we don't know the size we need to run a while loop and for each iteration we need to increment the counter and perform inequality comparison. This could add up.
I am assuming that the calling procedure would read the q from the advice tape, followed by p (which is put on the advice tape by a decorator), and lastly Ļ, and then put these in the configuration I laid out above. My thinking is that this would make hashing, in order to get Ļ, more straight forward
Yep, makes sense. I assumed that
from miden-vm.
Sounds great, I have mentioned this in facebook/winterfell#126
from miden-vm.
I add advice provider for iNTT over qudratic extension field in #598
from miden-vm.
I implement verify_remainder_64
routine in #644
from miden-vm.
Closed by #644
from miden-vm.
Related Issues (20)
- Implement handling of the last tier of TSMT in MASM HOT 1
- RFC: Extend the behavior of load/store ops to allow addressing all elements of a word HOT 6
- Consider removing unreachable code HOT 5
- Enable compiling modules without library paths HOT 9
- Replace AdviceProvider with Host interface HOT 12
- Expand capabilities of the `debug` instruction HOT 1
- Remove `checked` variants of u32 MASM operations HOT 1
- Semantics of `ext2mul`
- Faster modular reduction for Falcon signature verification HOT 1
- Implement `procref` instruction HOT 1
- Consider refactoring the semantics of `DYN` operation
- Consider imposing restrictions on `DYN` operation
- Documentation link in the README is broken HOT 3
- Add `get_module(path)` method to the `Library` trait. HOT 1
- Testing Falcon signature HOT 10
- Modifying miden-lib/asm/sat/internal/asset.masm results in compilation failures HOT 1
- Serialize `ProgramAst` into files to allow compiling Note Scripts HOT 2
- Refactor `Process` struct
- Add `emit` assembly instruction HOT 2
- Add logging to the assembler HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
š Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. ššš
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ā¤ļø Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from miden-vm.