Comments (6)
I got some numbers. For Poseidon, it seems that:
3 * a hash function with input size L
is likely MORE EXPENSIVE than
1 * a hash function with input size 5L
both when we consider the # number of constraints and when we consider the # number of constraint system weight.
e.g., for the case of constraints, alpha = 5, ~298-bit prime number,
a 2-input sponge needs 240 constraints => multiplied by 3 = 720
a 10-input sponge needs 435 constraints
This is because Poseidon of state size L + 1
- only do
x^\alpha
for the first L elements in FULL rounds, which are considerably few - do
x^\alpha
for the last element in PARTIAL rounds
That is to say, Poseidon has been intentionally optimized to scale well with a larger state size.
So, for Poseidon, using the transformation of 2021/373 may not be better than using a fatter sponge.
Yet, the result here is also instructive---when we do the Merkle tree, there might be some benefits to use a 4-arity tree compared with a binary tree. (Needs more investigation).
Note that this result might not apply to Rescue. Rescue examines each element in each round (no separation between full rounds and partial rounds).
@burdges What do you think?
from sponge.
Yes. I think the next step is to estimate the cost.
Because sponge parameters can also be selected to be suitable for 5-to-1 compression, and it is unknown which of the following is better:
- a naturally 5-to-1 compression function via sponge
- a 5-to-1 compression function via three invocations of sponges targeted at 2-to-1 cases
from sponge.
Interesting! I thought Poseidon rarely if ever made sense as a binary tree, like mostly using arities divisible by 3?
from sponge.
I think a lot of the time when people use binary trees it is due to convenience, but probably not the best choice after some careful calculation.
It seems that using a high arity is generally beneficial for Poseidon.
from sponge.
If you're simply including the copath elements then binary hashing should handle dense trees better, and works well with skipping logic for sparse cases. In this case, it's simply that zk avoids the space concerns in the first place, and then happens to reduce computation at somewhat higher arities.
We can close this it sounds like..
from sponge.
Good points.
A common concern for the k-arity tree is that the Merkle tree path proofs (i.e., paths and copaths) would be much longer. However, in ZK, they are often witnesses, whose lengths are not a big issue in bilinear-style SNARK.
(Though, it might be a problem for QuickSilver---the state-of-the-art fast interactive ZK proof---where the communication overhead is high, aka non-succinct, in the length of witness.)
from sponge.
Related Issues (4)
- Design sponge API HOT 8
- ark_merlin HOT 2
- API Meeting notes HOT 4
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 sponge.