Much like ECDSA, (some variants of) Schnorr support pubkey recovery!

In fact, Schnorr's pubkey recovery is better than ECDSA's: no need for recovery IDs!

So, beyond the obvious backwards-compatibility reasons, why ever use ECDSA? 

(Plus, ECDSA has so many other shortcomings.)

For more details, see: https://alinush.github.io/2024/05/31/Schnorr-signatures.html#pubkey-recovery

Schnorr's pubkey recovery

How should a blockchain keep a secret? 🔑 

I recently spoke about this @ the Dagstuhl Seminar on Next-Generation Secure Distributed Computing organized by @cczurich, @aniketpkate, @julian_loss & @kartik1507 

(Why? On-chain randomness, encrypt-to-a-smart-contract & more.)

At the core of every blockchain that keeps a secret lies a *distributed key generation (DKG)* protocol, which helps the blockchain validators jointly establish a shared secret s.

The key property: *only* validators who jointly have >66% stake can reconstruct s (or some f(s)).

In turn, at the core of every DKG lies a *secret sharing (SS)* scheme. For the proof-of-stake setting, a *weighted secret sharing (WSS)* scheme!

Although, we know a couple of things about WSS (👇), the most efficient construction is still a black-box transformation from SS.

So, understanding how to build more efficient weighted secret sharing remains a very interesting question!

For example, recent work leverages the Chinese Remainder Theorem to reduce the share size (although sacrifices reconstruction linearity).

A very convenient building block for DKGs is *publicly-verifiable (weighted) secret sharing (PVSS)*

PVSS perfectly showcases why we should strive for elegance in cryptography! 🤌

Unless one has tried to implement a DKG before, its simplicity can be hard to appreciate.

Case in point: a *simple* t-out-of-n DKG from a t-out-of-n PVSS 👇 

There is (and should be) more & more attention given to PVSS schemes, especially schemes that deal a group element secret, which are *extremely* efficient!

(In fact, we at @Aptos_Network have built our own PVSS [DPTX24] and deployed it in production: https://www.youtube.com/watch?v=47TRNUTMAyo.)

The rest of the talk (https://alinush.github.io/2024/09/05/How-should-a-blockchain-keep-a-secret.html) touches on:

1. Silent setup (https://alinush.github.io/2024/05/02/what-in-the-smurf-is-a-silent-setup-multiverse-unpredictable-function.html)
2. Anti-collusion in secret sharing infras
3. Faster threshold crypto: e.g., https://eprint.iacr.org/2024/1575, https://eprint.iacr.org/2024/1516

(References to all cited papers are in the slides!)

How should a blockchain keep a secret?

Schnorr signatures: everything you wanted to know, but were afraid to ask!

1. History
2. Definitions
3. Batch verification
4. (R, s) vs. (e, s) formulation
5. EdDSA and Ed25519
6. (Mis)implementation

Blog post here: https://alinush.github.io/2024/05/31/Schnorr-signatures.html

ECDSA, coming for you next! 🔫

PS: What is a good reference for the *cleanest* EUF-CMA security proof for (single-signer) Schnorr? Hoping to integrate that soon in the post 🙏 

Schnorr signatures

Do *silent setup* threshold VUFs exist (i.e., no DKGs)? 

This would be nice for randomness beacons like @aptos Roll! 🎉 

In this blog post, we try to tackle this question, with much help from @lera_banda, @josephbonneau, @rex1fernando, @bennypinkas, @danboneh and @TrishaCDatta 🙏

In the blog post, we describe a BLS-like construction for silent-setup threshold VUFs from *multilinear maps*.

So theoretical; not efficient.

In fact, *efficient* silent-setup threshold VUFs would imply *efficient* multiparty non-interactive key exchange (NIKE). 

This was recently pointed out in a talk by @gvamsip in the 3rand workshop organized by @SUPRA_Labs.

But, AFAICT, only 1-out-of-n silent setup threshold VUFs would imply n-party NIKE.

As a result, maybe variants where the threshold must be *high* could actually be efficient? 🤔

In other words, there may be *efficient* n/2-out-of-n silent setup VUFs because they do not imply *efficient* n-party NIKE?

Food for thought! 🌮 

Silent-setup threshold VUFs

What is an @aptos keyless account? 🧵 

It's a blockchain account derived from (say) your Google account and an application (wallet, dapp, etc).

It's bound not just to you (e.g., you@gmail.com) but also to the application (e.g., @PetraWallet, or @ThalaLabs, or @VibrantXFinance)

An @aptos keyless account lets you sign TXNs using your Google (/Apple/Facebook/any OIDC provider) account.

There are no secret keys (SKs). No passphrases. No mnemonics. 🥳 

Just you, the dapp, Google & the blockchain (+ a *privacy guardian* and ZK prover service; TBD)

Your address is addr = H("uid-123", "dapp-xyz", r), where:

1️⃣ r = a random *pepper* from the privacy guardian (TBD)
2️⃣ "uid-123" = your Google-specific "sub" identifier. (Keyless also supports "email" identifiers.)

But then, how do you authorize a TXN from your keyless account?

Once you sign into the dapp (e.g., @ThalaLabs) via Google, the dapp obtains a signature from Google on a specially-crafted message called a JSON Web Token (JWT).

The JWT contains the same user & application ID as in your blockchain address, and an *ephemeral pubkey* (EPK).

Where did the EPK come from? You, the user!

You pre-generated an ephemeral secret key (ESK) & derived its EPK. 

*Ephemerality* is 🔑 here: if you lose the ESK, you won't lose access to your keyless account. (Unless the ESK gets in the hands of an attacker who also has your JWT.)

The JWT is a signed statement from Google saying "This EPK is authorized to sign on behalf of addr."

It is a digital certificate, delegating signing for addr to the EPK.

So, to authorize a TXN, could we include the signed JWT, the blinding factors and sign the TXN with the ESK?

We could... if we didn't care about privacy! 🚫

But we do. So, we perform the privacy-sensitive checks in a ZK relation (R_keyless) 👇.

i.e., we hide the user-identifying info inside the private inputs to the relation & prove that such private inputs exist and pass the checks!

Remember: A ZK proof for a relation R convinces a verifier that the prover knows a secret w such that R(x; w) = 1, given a public x 👇 

https://twitter.com/alinush407/status/1661461336797380611

So: you compute a ZK proof π (currently, via a ZK prover service) for the R_keyless relation above ☝️.

Unlike the JWT, π is a *privacy-preserving* certificate, binding your addr to your EPK.

=> until it expires, you can re-use π to authorize TXNs by signing them with the EPK!

Almost done: the blockchain validators are now able to verify your keyless TXNs ✅ :

1️⃣ Check that the ZKP π is valid: i.e., it delegates signing rights for addr to EPK.
2️⃣ Check that the TXN is signed by the EPK.

Importantly, π leaks nothing about the user and application IDs!

I did not yet explain a few things: 

❓Why is the nonce in the JWT set to an EPK commitment (blinded with randomness ρ), rather than the plain EPK?

Because if Google learns the EPK, it can identify TXNs signed by that EPK and figure out that addr is for you@gmail.com. Big no no.

❓Why the privacy guardian?

Your address addr must be a commitment too!

Otherwise, it can be brute-forced => everyone learns it is associated with "uid-123".

So, the guardian helps you derive a pepper r to blind addr. Otherwise,  remembering your own r would not be keyless.

(Although not depicted above, with a bit more ZK magic, the guardian can be *oblivious*: it can help you derive your pepper without even learning your user ID nor the application ID!)

More depth on @aptos keyless accounts? 🤿 

1️⃣ Watch our @zeroknowledgefm zkSummit'11 talk: https://youtube.com/watch?v=sKqeGR4BoI0

2️⃣ Read our dev guide: https://aptos.dev/aptos-keyless/how-keyless-works

3️⃣ Read our AIP: https://github.com/aptos-foundation/AIPs/blob/main/aips/aip-61.md

Ask us: @alinush407, @mstrakastrak, @AlyssaPonzo, @oliver_apt, @zjma2022!

Keyless accounts

Short blog post summarizing a recent strawman construction of a multiverse threshold signature scheme by @leemonbaird, @SanjamGarg, @sinharo, @mingyuanwang0 et al:

https://alinush.github.io/2024/05/01/baird-et-al-unique-threshold-signature-scheme.html

An interesting open Q: How _efficient_ is it to reveal those f(-1), ..., f(-(n-t)) points?

Threshold signature schemes are very useful in cryptocurrency applications.

For example, they can be faster to verify than naive multisignature schemes (e.g., BLS multisignatures don’t mix well with Ethereum's gas costs for G1 operations; https://geometry.xyz/notebook/Optimized-BLS-multisignatures-on-EVM; cc @kobigurk)

(Forgot the differences between threshold signatures and multisignatures? Look no further: https://docs.google.com/presentation/d/1G4XGqrBLwqMyDQce_xpPQUEMOK4lFrneuvGYU3MVDsI/edit?usp=sharing)

Furthermore, if the signatures are *unique*, they yield publicly-verifiable randomness (e.g., see https://aptoslabs.medium.com/roll-with-move-secure-instant-randomness-on-aptos-c0e219df3fb1)

If they avoid a DKG, or minimize its complexity, even better!

Will follow up with more thoughts! 📡 

Multiverse threshold signatures

When I fly 🛫 , my mind sometimes wanders to my favorite crypto tricks! 🤓 

Last week, it landed on Shamir secret *re*sharing via the "share your share" approach! What a *beautiful* technique! 🤩

Couldn't help myself, so I wrote a short blog post ✍️:
https://alinush.github.io/2024/04/26/How-to-reshare-a-secret.html

Oh, and remember: Crypto stands for cryptography.

Shamir Secret Resharing via "share your share"

Continuing the tweet hurricane 🌀 on the challenges of taking @aptos on-chain randomness from idea ✅ , to *academic paper* 📜, to production-ready implementation and, finally, to deployment (https://twitter.com/alinush407/status/1770797569947337099). 

Let's look at *the paper* part of the journey! 🛣️ 🏍️

It's often much easier to come up with a crypto[graphic] construction 👷 than to prove it secure ✍️. 

Our weighted PVSS and VUF were no exception...

So, @bennypinkas and @sourav1547 worked very hard on a security proof, which gave us extra confidence to eventually deploy.

But proving security is non-trivial ❌

In fact, even *defining* security can get quite hairy 🤔

Just glance at the security definition for a VUF, which is actually a very *simple* one 👇

(cc @capcap_max; "It's very simple!")

It's not even complete... there's another page! 😆 

For the actual security proof, things become subtle.

We first "warm up" by proving security of the single-signer VUF ☕. 

Then, we tackle the thresholdized VUF. (See 👇, but reading it is not for the faint of heart.)

Lastly, we prove the weighted VUF we actually use ✅ 

Luckily, the reduction for the weighted VUF variant turned out to be _not_ too different from the threshold case 😌

(See diffs in grey 👇 )

In the paper, we must also convince our academic peers 👩‍🏫 🎓 🧑‍🏫 that our approach is the best one when compared to alternatives.

(1/2) We first argue that *interactive* wDKGs ❌  do not really work in the PoS setting, which arises in most PoS chains, including @aptos.

Specifically, in an epoch-based BFT protocol, the wDKG would need to happen between the *new* committee members, who are _not even online yet_. 

An alternative is a non-interactive hand-off from the *old* committee to the *new* committee, but the overheads we got were too high.

Indeed, @sourav1547 investigated such a hand-off based approach in our "Simplified VSS" paper: https://eprint.iacr.org/2023/1196.pdf

See https://twitter.com/sourav1547/status/1688568306696126464

(Actually, @sourav1547, did that hand-off approach even make it into the paper? 🤭)

(2/2) We then argue that a PVSS-based wDKG for a naively-weighted BLS VUF ❌ is not efficient, because:

(a) The (field-element) wDKG would be too expensive (great avenue for future work! 🎓)

(b) BLS aggregation is slower than our wVUF due to its linear share size.

For me, the most fun part about writing a paper is carefully writing down algorithms in a precise & complete way (see 👇).

This is in service not just to our readers, but also to ourselves when we return to the paper years later & we find things easy-to-understand.

In the end, we drafted the paper 📜 and submitted it: https://eprint.iacr.org/2024/198

(Currently, we are writing rebuttals, yaaaay! 🥳)

Next, I'll talk about:

1. The implementation of `aptos-dkg`, a PVSS library that can be used to build wDKGs.
1. The randomness implementation in @aptos BFT.
2. Validating our paper's approach by obtaining performance numbers from a *real* system! 👇 (Very rare.)

Stay tuned 📡 !

The challenges of full-stack reasearch: the paper

🧵 @AptosLabs taught me the challenges of going from _idea_, to academic paper, to production-ready implementation and, finally, to deployment!

🎲 A perfect example is our *instant* on-chain randomness in Move, or @aptos Roll: https://aptoslabs.medium.com/roll-with-move-secure-instant-randomness-on-aptos-c0e219df3fb1

Let's look at the idea💡!

In 2023, we realized a large class of Move dapps need access to *instant* randomness 🎲.

e.g., a simple call to, say, `randomness::u8_integer()` should *instantly* return a random byte to the caller.

DevX is very important to us, so the *instant* part was 🔑.

Having worked on threshold crypto[graphy] before, @SashaSpiegelman, @XiangZhuolun, @bennypinkas and I were well-aware of the implementation complexities & inefficiencies of DKGs and VUFs, especially in the PoS/weighted setting.

This would be a fun challenge!

We suspected that PVSS-based aggregatable DKGs would be the cleanest to implement in the @aptos BFT protocol & should be efficient too.

The state-of-the-art was our EUROCRYPT'21 paper with @kobigurk, @Daeinar, Mary Maller, Sarah Meiklejohn & @Giladstern_: https://eprint.iacr.org/2021/005.pdf

Yet, the SCRAPE PVSS from EUROCRYPT'21 was slow-to-verify (high # of pairings).

In particular, for ~1000 (virtual) parties in the PoS/weighted setting, the verification time would have been 5.2 secs.

CPU cycles not spent on TXN execution = bad.

We needed something better... 🤔

To address this, @sourav1547 designed a faster, weighted, aggregatable PVSS, with a much smaller # of pairings 🧠.

Verification time was lowered by around 20x!

We were in business! 👊

Another challenge: the naively-weighted variant of the EUROCRYPT'21 VUF had share size *linear* in the weight (stake) of each player (validator) and was rather complex (e.g., Groth-Sahai proofs).

But @bennypinkas designed a simpler and more efficient weighted VUF, which had constant-share size, independent of the player's weight 🤯!

Since a weighted VUF is aggregated every block, the lower communication & faster aggregation of this new VUF was crucial for performance!

In reality, the road was much more winding & complicated 😄...

For example, we reinvented the ALBATROSS PVSS without realizing (https://eprint.iacr.org/2020/644) just to find out that making it aggregatable, although possible, would require two rounds of dealing.

The idea💡 was the 1st stage.

In the next 🧵, I'll discuss *the academic paper* and the gaps that had to be filled there! 

Stay tuned 📡 !

The challenges of full-stack reasearch: the idea

🧵 How do we provide instant on-chain randomness on @Aptos_Network?

One key ingredient is a fast Lagrange interpolation algorithm from our 2020 work (& my PhD thesis) with @bennypinkas, @ittaia et al (https://alinush.github.io/2020/03/12/scalable-bls-threshold-signatures.html)

So, if you're doing threshold BLS, read below...👇

Aggregating t-out-of-n threshold signatures typically involves (1) computing Lagrange coefficients and (2) doing a multi-exponentiation with them over the signature shares.

(1) is always done *naively* in O(t^2) time
(2) is (more-or-less) O(t) time

This does not scale well 😢👇

Why the inefficient O(t^2) time? Because of the difficulty of computing the denominators of each Lagrange coefficient L_i^P(0) below, which requires evaluating t different products of the form \prod_{j\in P, j\ne i} (i-j), where P is the set of signers that we aggregate from.

Our work (1) makes computing all Lagrange denominators efficient in O(t log^2 t) time via a polynomial multipoint evaluation, (2) implements it efficiently, and (3) applies to BLS.

Generally, it applies to any Lagrange-based threshold cryptosystem.

See https://ieeexplore.ieee.org/document/9152696

Why do we care? For @Aptos_Network randomness 🎲 , we must do a threshold signature in the PoS setting! This involves (1) rounding validator stakes down to small weights, (2) assigning each validator as many shares as they have weight & (3) doing a *weighted* threshold signature!

Even with careful rounding of stakes, the total weight (i.e., # of signers in the threshold scheme) can be anywhere from 1,000 to 10,000 (cc
@chelseakomlo), which will be rather slow.

So, our 2020 work allows us to get *much* better performance 👇

Improvement ranges anywhere from 2x to 10x at our scales.

See some concrete numbers below 👇

Fast Lagrange is just one of the ingredients we use to make instant randomness on @Aptos_Network possible!

And we hope you use it in your own Rust-based work (see https://github.com/aptos-labs/aptos-core/blob/9a45f0844a82a331f27bc692de8e81ed5c5b8c06/crates/aptos-dkg/src/algebra/lagrange.rs#L134)

Stay tuned to hear about the next ones! 📻 📡