For any additional inquiries team can be contacted via [email protected] email or @alexander_slesarev:matrix.zymologia.fi on Matrix

Proponent: 12bFooBAK4hHUfiri7v2Eiz96v7TDoiLWdNKCFYmhWzGG1Tq, Alzymologist Oy, [email protected]

Date: 2023-07-06

Requested DOT: 110.693,7 DOT equivalent to €537.744 at date of the payment.

Summary

This project's goal is to create a new metadata protocol friendly to offline devices and implement it in the most critical tools available: Ledger and Kampela, as well as create tools to port it to other wallets and key management devices, including Polkadot Vault. This will involve changing the runtime code to support a new method of transaction signing that would include a proof of metadata used for transaction rendering to the user.

This was discussed across the ecosystem, mentioned in this github issue and Polkadot forum, posted in two discussion threads on Polkassembly (one, two), and gained traction reaching up to key representatives of the Polkadot Ecosystem.

Although this proposal is formally presented by Alzymologist Oy, the Laboratory behind Kampela, it will be a joint development between Alzymologist Oy and Zondax. More details can be found below.

Problem statement

Background

While all blockchain systems support (at least in some sense) offline signing used in air-gapped wallets and lightweight embedded devices, only few allow simultaneously complex upgradeable logic and full message decoding on the cold off-line signer side; Substrate is one of these heartening few, and therefore - we should build on this feature to greatly improve transaction security, and thus in general, network resilience.

As a starting point, it is important to recognise that prudence and due care are naturally required. As we build further reliance on this feature we should be very careful to make sure it works correctly every time so as not to create false sense of security.

In order to enable decoding that is small and optimized for chain storage transactions, a metadata entity is used, which is not at all small in itself (on the order of half-MB for most networks). This is a dynamic data chunk which completely describes chain interfaces and properties that could be made into a portable scale-encoded string for any given network version and passed along into an off-chain device to familiarize it with latest network updates. Of course, compromising this metadata anywhere in the path could result in differences between what user sees and signs, thus it is essential that we protect it.

Therefore, we have 2 problems to be solved:

Metadata is large, takes long time to be passed into a cold storage device.
Metadata authenticity should be ensured.

As of now, there is no working solution for (1), as the whole metadata has to be passed to the device. On top of this, the solution for (2) heavily relies on a trusted party managing keys and ensuring metadata is indeed authentic: creating poorly decentralized points of potential failure.

A Substrate Ledger app which is both generic and secure

We propose a secure hardware wallet (Ledger) application that can automatically handle all parachains and relay chains without being affected by runtime upgrades. This has been requested by the community for a long time. The objective is to provide a single application for the entire ecosystem, with the flexibility to allow new functionality without compromising security.

This is not a new problem and there have been strong attempts to solve it, however, it is apparent to us that in order to provide a secure solution that changes to the nodes themselves are required. This would provide the ecosystem with a resilient and secure, on-chain validated method which we believe the Polkadot ecosystem deserves.

We want a secure by design solution that can clear sign and support most relay chains and parachains without the need of frequent updates.

A solution should take into account that:

Until now, metadata is not verifiable and must be considered not trusted.
Metadata changes breaking Ledger apps and other air gapped solutions.
Substrate (used in Polkadot and all the Parachains) is a framework that evolves over time. This should not be constrained by artificial restrictions.
The ecosystem requires a secure long term generic solution.
A strong and long term solution requires the collaboration of multiple stakeholders, including Parity.

In addition to this:

It is important to minimize application updates to reduce auditing costs.
Ledger Nano S has only 4kB of RAM (Typically <3kB are available to apps). Implementation is not trivial, a team with a strong reputation would be required (several years building a large amount of apps).
There are aspects such as derivation paths that may require special treatment.
Metadata may need to be extended with some minor additional fields.

Project details

Proposed solution

Include metadata into signature

This is the simplest part - add some hash of metadata to signing inputs and sign. The size of data stored on chain does not change - except for a flag that would indicate whether this new feature is used or is data signed as before (so that cold signers could force "with metadata always" rule if they can or not force it if they cannot). This was discussed in github issues, now we suggest that the whole wallet/signer community comments on this part.

Reduce transferred metadata size

This is where things get tricky - and what would be addressed mostly within scope of this proposal. For small embedded devices like Kampela (64kBit internal RAM) and Ledger (4 kB RAM), shortening the metadata is essential. Only small part of metadata is really needed for decoding. The proposal by the Substrate team was to represent metadata hashes as Merkle tree and use it to securely and scalably generate the metadata validity proof on cold device.

For this, metadata should be abbreviated in some deterministic manner, similar to what native retain() operation from scale-info does, but more strictly. This procedure should have following properties:

Be deterministic across implementations and platforms.
Result in easily-merkelizeable data.
Be associative - we should be able to reduce metadata sequentially for optimized caching strategies or go directly to minimal.
Result in minimal size of metadata and require minimal RAM for its handling.

Implementation of a Substrate secure generic app by Zondax

A more succinct version of the metadata is specified in collaboration with other teams. Existing Runtime metadata already describes pallets, extrinsics and other typical elements but some elements that are not relevant could be removed.

A Merkle tree is used to process this succinct metadata; generating a root hash but at the same time allows accessing individual elements (leaves) in a verifiable fashion.
A new adapted version of Zondax’s existing Ledger apps can parse blobs informed by verifiable metadata leaves (VML). Depending on the device capabilities a several VML are ingested as a batch or they are on-demand transferred to the device.
Dynamic parsing is not trivial in embedded devices without dynamic memory. We have an internal prototype and we feel confident about it. Moreover, we have in the past already done something similar for another large project.
A new extended signature mode is used. When signing, the digest is calculated, however, a kind of domain separation is used where the root of the Merkle tree is prefixed. Moreover, this root does not need to be included in the tx as it is common knowledge. During verification, the corresponding runtime can apply a similar mechanism.
Other aspects such as chain name or params are also planned to be embedded as VML and handled automatically. This completely removes the requirement of an online registry and centralized repositories where entities need to submit parachain information and parameters without adequate identity verification.

Course of action

For this to succeed, a concerted effort from several teams is necessitated. Thus, this proposal is formulated and submitted jointly by several collaborativly aligned ecosystem teams and is closely coordinated in conjunction with the Substrate core development team.

There are also potential alternatives to Merkle tree indexing of metadata (for example, bilinear accumulators) that offer certain advantages, like slower growth at large runtime size increases, which might be expected. We should analyze these approaches and try to determine their feasibility, and if they are indeed better choice, replace all Merkle tree propositions of this project with corresponding more optimal tools.

Preliminary work

We have carried out some minimal analysis in advance of publishing this proposal in an initial effort to reliably shorten metadata using basic tools. The first attempt resulted in reduction from about 200kB to about 8kB with some outdated snapshot of metadata - modern result should look even more impressive as while metadata grew significantly, the individual call-related data substructures sizes changed little.

This demonstration is, however, far from refined solution. Decomposing certain calls would still result in enormous data structures (namely, popular batch_call instruction would require an enum with all other calls and their parameters included). Furthermore, even 8kB significantly too large for typical secure element RAM limitations. Thus, serious additional research is required to formulate the final standard.

With regards to the implementation of the Ledger app, the proposed solution is a progression on the current solution Zondax provides. Zondax has been involved in related works in other ecosystems but this approach is state-of-the-art in comparison to what others have been doing.

Ecosystem fit

Once defined and implemented in Substrate core, this feature would be available for all Substrate-based chains, across whole ecosystem. Any wallet or key management device would be able to implement it with use of documentation and libraries delivered within the scope of this project. Offline device security and useability would improve significantly, which would also increase their use in the community. All of this would culminate in a materially enhanced ecosystem resilience and remove severe UX issues that inhibit Polkadot ecosystem adoption.

As shown above, there is significant amount of attention from various ecosystem players to this project; we are closely working with community and relevant teams to make this happen for some time already.

Deliveries of this project are a blocker for proper fulfillment of Milestone 5 for Kampela project, where transaction protocol specification should be defined. Sending whole metadata over NFC would take noticeable amount of time thus making UX uncomfortable enough to severely reduce adoption of device. If this project gains community support and passes, only a small delay in Kampela development would be present as the NFC transfer protocol specification would follow soon after this project's standard is published.

This solution would enable teams to keep innovating and developing new features. This would benefit:

Relay chain
Parachains
Current and future users
Overall network security

Roadmap and delivery milestones

After each milestone, a brief summary report of progress will be submitted for the community to review.

Milestone 1 - Requirements specifications and latest metadata review (2 weeks)

Publish refined requirements for protocol, aligned with existing offline devices capabilities, current state of metadata, and runtime implementation requirements
Publish first draft of mock shortened metadata for parallel development
Estimate shortened metadata size frames based on information theory
Coordination with all stakeholders on a working Group for Verifiable Metadata Spec
Analyze alternative hashing/storage strategies to Merkle tree, to potentially replace the latter in following steps with a more optimal solution.

Milestone 2 - Offline metadata prototype (6 weeks)

Basic algorithm to generate a shortened metadata and associated Merkle tree as proof-of-concept code example
Refined draft for mock shortened metadata
Feasibility analysis and possible caveats/solutions for offline devices implementations
Early implementation of a generic app with metadata support

Milestone 3 - Offline metadata specifications (8 weeks)

Exhaustive documentation on new protocol
substrate-parser reference implementation
Ledger App integration tests and javascript library

Milestone 4 - Offline devices implementation (8 weeks)

Implement offline metadata in Kampela device
Implemention with final offline metadata spec in Ledger device
External security audit of the Ledger App
At least propose solution package for Polkadot Vault app

Required roles and associated costs


Role	Milestone 1	Milestone 2	Milestone 3	Milestone 4
Alzymologist Oy (Finland)
Rust developer	€9.400	€28.200	€37.600	€37.600
Embedded Rust developer	€9.400	€28.200	€37.600	€37.600
Project/communication manager	€5.100	€15.300	€20.400	€20.400
Zondax AG	100h	400h	500h	600h
Technical Lead	€5.100	€15.300	€20.400	€20.400
Embedded C developer	€5.760	€23.040	€28.800	€34.560
Project/communication manager	€2.880	€11.520	€14.400	€17.280
External audit				€10.000
Total	€38.300	€129.300	€167.600	€192.000

Note: Alzymologist Oy costs represent 54,5% of the offer Zondax costs represent 45,5% of the offer

Payment details

To forsee potential price volatility, this proposal includes a 2% aditional DOT request.

Total cost of development: €527.200. With the aditional 2% for volatility this is €537.744, which translates to 110.693,7 DOT using Subscan EMA7 price.

The total cost of development would be requested as single deposit.

The funds would be deposited to Alzymologist Oy account 12bFooBAK4hHUfiri7v2Eiz96v7TDoiLWdNKCFYmhWzGG1Tq. Upon commencement of the call, Alzymologist Oy takes obligation to subcontract Zondax AG for the 45,5% of the total amount of DOTs paid by the treasury to cover their costs (this statement effectively legally constitutes unilateral written contract in our magnificent blockchain-friendly Finnish justidiction). We have tried to showcase a multisignature setup, but are doing this Finland-centered operation instead due to non-crypto world regulations being in the way.

Risks

Substrate core inclusion

There is a possibility that the changes proposed within this project are not included in Substrate codebase due to technical or other limitations. If this happens, the whole initiative fails.

To mitigate this, we have ensured that Substrate core developers are interested in this improvement and, furthermore, are ready to review it and include it in forthcoming Substrate updates. See above communications for details of these negotiations.

Ledger audit/approval

Review Process: Ledger’s review queue is sometimes unpredictable and depends on Ledger's workload and other factors that are out of Zondax control. We have experience in their process and have a streamlined workflow to simplify this. However, the effective time may vary depending on Ledger's resource availability, app/blockchain complexity, etc. The review process does not imply Ledger Live integration and is typically limited to the publication of the app in the Ledger Live Store allowing final users to install directly from Ledger.

To mitigate these risks, an external audit, will be coordinated and any relevant fixes will be applied. The external auditor will be selected from a list provided by Ledger SAS. Ledger SAS claims and it is public knowledge that when provided with a satisfactory auditor report from an auditor in that list, apps will be published in a much shorter period of time.

Fundamental limitations

There is a slim chance that metadata could not be reduced to size manageable within given space limitation (worst case is Ledger device), or that it could not be reduced to that size in general but could in some cases. This would limit usability of low-memory devices for Substrate-based networks to some extent; we see this probability as very slim and in worst reasonably-probable scenario we see that limitations would be minor, like limit on number of calls in a batch. This kind of limitations would marginally degrade user experience and would not harm security, so this risk seems acceptable. Future models of secure elements with larger memory spaces would probably come to market in near future to bring further relief to these limitations.

Future plans

After delivering the last milestone, we plan to maintain the project and spread its implementation into the whole ecosystem where its usage is relevant. Alzymologist Oy has further commercial embedded projects where advanced metadata management would be beneficial; probably there are other upcoming projects as well.

Project team

Alzymologist Oy

Alzymologist Oy is a laboratory, research, and consulting company based in Finland. We have a multidisciplinary team of specialists across many fields, from IT and security to chemistry and biology. Alzymologist team develops Kampela project a working prototype of which was demonstrated at Polkadot Decoded event. Alzymologist team was developing Parity Signer (later renamed to Polkadot Vault) at times of 5.0.1 release and introduced several important standards and protocols still used there. Our extensive expertise on low footprint devices also includes wearable electronics phase radars and civilian science environmental sensors that are currently sending live radiation monitoring data fron Chernobyl region in Ukraine.

Business ID: 3162030-9

Zondax AG

Zondax is a growing and distributed team with experience and projects for more than 50 blockchains. Zondax has been contributing to the Substrate ecosystem since 2018-2019. The team has received and completed a large number of W3F grants and currently maintains most Ledger apps for the ecosystem. Apart from the substrate ecosystem, Zondax participates and contributes to other large ecosystems such as Cosmos, Avalanche, Algorand, Filecoin, ICP, etc. Our team includes experts in most blockchain aspects, cryptography and programming languages.

Legal structure

Zondax AG Dammstrasse 16 Zug 6300 Switzerland UID CHE-491.796.576

Most of our contributions to the blockchain ecosystem can be found in our GitHub organization: https://github.com/zondax

Over the last few years, Zondax has been involved in a large number of projects for most of the key players in the blockchain industry. For this reason, we are confident that we can provide a long term commitment.

Submission

Zondax implements changes under the Apache 2.0 license. Zondax is building upon apps that the W3F has already submitted to Ledger. We will submit PRs to Ledger with the corresponding improvements. We assume that as part of the payment, the Foundation and Treasury authorizes us to submit changes of the upgrades to Ledger.

Liability and warranty

Zondax shall develop the solution according to the present proposal under the Open Source Apache 2.0 license. Accordingly, any warranty and liability is limited to what is expressed in the Apache 2.0 license. In general, Zondax disclaims any liability and warranty to the extent permitted by law arising from the present proposal and the resulting agreement.

Edit 2023-07-06T20:27 Helsinki: restore whole post removed by "link discussion" button

Edit 2023-07-06T20:43 Helsinki: remake table from markdown to polkassembly format