Releases: semaphore-protocol/semaphore
v4.0.1
🐞 Bug Fixes
- @semaphore-protocol/proof: Replace root public signal with actual root - by cedoor in #843 (b2da0)
♻️ Refactoring
View changes on GitHub
v4.0.0
da2fae6
vplasencia
Vivian Plasencia
Changelog
TLDR;
Semaphore V4 introduces two significant protocol updates:
- Replaces the old Incremental Merkle Tree with the optimized Lean Incremental Merkle Tree for groups.
- Updates the identity schema from Poseidon to EdDSA.
The main protocol components, libraries, and contracts remain largely unchanged, with some adjustments to parameters and functions. However, the new version is not backward compatible with the previous ones.
LeanIMT
The new data structure improves over the old one in terms of efficiency and storage with two major changes.
-
Zero Hashes:
In the Incremental Merkle tree used in version 3, when a node has only one child (always the left one), a zero hash is used instead of the missing right node to compute the hash of the parent node.
In the new data structure when the right node is missing the parent node simply takes the value of the left child node. This means that zero hashes are no longer needed, so it is no longer necessary to pass the tree an initial value to calculate the list of zero hashes to be used for each level of the tree. And the number of hashes to be calculated to insert or update a new leaf is smaller, as there can be nodes with only one child in the path.
-
Dynamic Depth:
In the Incremental Merkle tree used in version 3, the depth of the tree is defined at the time of initialization, and when a node is inserted, a number of hashes equal to the depth of the tree is always computed.
In the new data structure, the tree depth is updated as leaves are inserted. This means that when a node is inserted the number of hashes to be computed grows as the tree grows.
Suppose in the old data structure the tree depth is 16. In that case, it means that from the first to the last leaf, the number of hashes to be computed for insertion is always 16. In contrast, in the new data structure, the first leaf will be the root itself and the tree depth will be 0, the second leaf will be used together with the first one to compute the parent node which will become the new root of the tree with depth 1, and so on.
These two changes together make adding new members to the group much more efficient, reducing both off-chain processing time and on-chain gas costs.
A paper on the LeanIMT will be published soon!
EdDSA Identity
In Semaphore V3, the identity scheme is straightforward. First, the Poseidon hash of two secret values (trapdoor and nullifier) is computed to create the identity secret. The hash of the identity secret then forms the identity commitment, which serves as the public representation of the identity used in groups.
However, a major limitation of this configuration is that it is only possible to prove that you are the owner of a Semaphore identity by using another zero-knowledge proof (the most trivial solution is to prove that you own the pre-image of the Poseidon hash in another circuit). In other words, although the scheme is simple and efficient, it becomes limiting in use cases where the identity assumes a crucial role and needs to operate beyond Semaphore.
Therefore, given the numerous use cases for Semaphore identity beyond generating Semaphore proofs, such as integrating with other systems or protocols, we opted for an EdDSA key pair. This choice enables efficient message signing and signature verification both within and outside zero-knowledge circuits, while also ensuring compatibility with a wider range of existing protocols.
Benchmarks
Solidity
The cost of inserting leaves into the tree has been drastically reduced. Let’s consider the following data to consider the differences in terms of money as well:
- Gas price: 5 Gwei
- ETH/USD price: 3,485.03 $
IMT - Insert
| Leaves | Three Depth | Gas units (avg per tx) | Gas costs (avg per tx) | Total gas costs |
|---|---|---|---|---|
| 16 | 4 | 220825 | 3,82 $ | 61,12 $ |
| 32 | 5 | 257968 | 4,50 $ | 144 $ |
| 64 | 6 | 296167 | 5,16 $ | 330,24 $ |
| 256 | 8 | 374687 | 6,53 $ | 1671,68 $ |
| 1024 | 10 | 454612 | 7,92 $ | 8110,08 $ |
The depth of the IMT is static and must be defined before inserting leaves, so the insertion costs are always the same for the same depth (regardless of the number of leaves in the tree), and the costs to initialize the tree must also be considered. In addition, there is a maximum limit of leaves that can be included. So if a Semaphore group exceeds that limit it is necessary to create another IMT from scratch with a higher depth, further raising costs.
LeanIMT - Insert
| Leaves | Gas units (avg per tx) | Gas costs (avg per tx) | Total gas costs | Costs diffs (IMT) |
|---|---|---|---|---|
| 16 | 143434 | 2,48 $ | 39,68 $ | - 35% |
| 32 | 159358 | 2,76 $ | 88,32 $ | - 39% |
| 64 | 176746 | 3,06 $ | 195,84 $ | - 41% |
| 256 | 213820 | 3,70 $ | 947,2 $ | - 43 % |
| 1024 | 252195 | 4,37 $ | 4474,88 $ | - 45 % |
In the new data structure, there's no need to initialize the tree. The leaves can simply be inserted, and the depth will dynamically adjust based on the number of leaves added. This also means there is no maximum number of members a group can have. If the planned group size needs to be increased, simply add the new members without any additional steps/costs.
LeanIMT - InsertMany
| Leaves | Gas units | Total gas costs | Costs diffs (LeanIMT) |
|---|---|---|---|
| 16 | 1047927 | 18.14 $ | - 54% |
| 32 | 1963410 | 33.96 $ | - 62% |
| 64 | 3771141 | 65.34 $ | - 67% |
| 256 | 14526471 | 251.64 $ | - 73% |
| 1000 | 56337852 | 975.53 $ | - 78% |
A function to add multiple members at once has been implemented in the new data structure to further save gas and reduce costs.
If, for example, you have an off-chain group with 1000 members and you want to transfer it on-chain to the mainnet, considering the costs above, with V3 it costs you ~8000 $, while with V4 it costs <1000 $ (a savings of ~7000 $).
JavaScript
In the Javascript implementation, the new data structure is almost twice as fast in inserting new leaves.
| Leaves | Time (IMT - insert) | Time (LeanIMT - insert) | Time (LeanIMT - insertMany) |
|---|---|---|---|
| 16 | 12 ms | 7 ms | 4 ms |
| 32 | 32 ms | 19 ms | 7 ms |
| 64 | 69 ms | 35 ms | 18 ms |
| 256 | 360 ms | 175 ms | 52 ms |
| 1000 | 1,8 s | 0,8 s | 175 ms |
In addition, a function to add multiple members has also been implemented in JS.
Benchmarks were run on an Intel Core i7-1165G7, 16 GB RAM machine.
More benchmarks will be published soon in the documentation.
Migration
JavaScript
You can now import all core functions from the @semaphore-protocol/core package. See the documentation of the individual libraries for more details.
@semaphore-protocol/identity
- const identity = new Identity(secret)
+ const identity = new Identity(edDSAprivateKey)@semaphore-protocol/group
- const group = new Group(id, depth)
+ const group = new Group()@semaphore-protocol/proof
- const proof = await generateProof(identity, group, externalNullifier, signal, {
- wasmFilePath: "./semaphore.wasm",
- zkeyFilePath: "./semaphore.zkey"
- })
+ const proof = await generateProof(identity, group, message, scope)- await verifyProof(proof, depth)
+ await verifyProof(proof)A complete guide to migrating from Semaphore V3 to V4 will be published soon.
v4.0.0-beta.19
44ad964
vplasencia
Vivian Plasencia
🐞 Bug Fixes
- Update cli ethers and subgraph templates - by @vplasencia in #835 (d54d6)
♻️ Refactoring
- Support groups with tree depth 0 in cli templates - by @vplasencia in #832 (b5f8e)
View changes on GitHub
Contributors
Assets 2
v4.0.0-beta.18
🚨 Breaking Changes
- @semaphore-protocol/proof: Set tree depth = 1 when a group has 1 member - by @cedoor in #831 (af4ae)
🐞 Bug Fixes
- Cli templates - by @vplasencia and @cedoor in #830 (af4fe)
♻️ Refactoring
- @semaphore-protocol/cli: Create an empty yarn.lock file when generating a semahore project with the cli - by @vplasencia in #828 (90caa)
View changes on GitHub
Contributors
Assets 2
v4.0.0-beta.17
Contributors
Assets 2
v4.0.0-beta.16
No significant changes
View changes on GitHub
v4.0.0-beta.15
No significant changes
View changes on GitHub
v4.0.0-beta.14
No significant changes
View changes on GitHub
v4.0.0-beta.13
🚨 Breaking Changes
- @semaphore-protocol/identity: Update type of private key - by @cedoor and Andrew Twyman in #803 (3572f)
View changes on GitHub
Contributors
Assets 2
v4.0.0-beta.12
No significant changes