1 of 50

Aptos Keyless accounts

Your blockchain account = your Google account

Sign in with Google

Alin Tomescu

@alinush407

alin@aptoslabs.com

zkSummit’11 talk 📹 here

2 of 50

Sign in TXNs with Google

Alin Tomescu

@alinush407

alin@aptoslabs.com

Aptos Keyless accounts

Your blockchain account = your Google account

talk 📹 here

3 of 50

Collaborators & acknowledgements

The core Aptos Keyless team:

At the same time, this is a broader effort among many Aptos Labs employees.

Without their help this work would not be possible! 🙏

3

4 of 50

tl;dr: Your blockchain account = Your Google account

  1. Google = Facebook = GitHub = any OpenID Connect (OIDC) provider
  2. You can "sign" TXNs as long as you can sign in to your Google account
  3. No secret keys ⇒ hard to lose your blockchain account
  4. Your keyless blockchain address is a hash of:
    • your email address
    • the wallet's application ID (or the dapp's)
    • a privacy-preserving pepper
  5. Your TXN are signed via an OIDC signature from Google over:
    • your email address
    • the wallet's application ID (or the dapp's)
    • the TXN hash
  6. dapps can derive dapp-specific accounts for users; no need for installing wallet
  7. A splash of 🪄 ZKPs: hides email & app ID from chain (and TXNs from Google)

4

5 of 50

Pros and cons of OIDC-based blockchain accounts

5

​

  1. User onboarding
  2. No lost SKs
  3. Cross-device UX
  4. Wallets do not store long-term secrets
  5. Application-specific accounts ⇒ Walletless dapps

​

  • Complex cryptography (zkSNARKs)
  • MPC ceremony for Groth16 ZKPs
  • Extra infrastructure (ZK proving service, pepper service)
  • Consensus on PKs of OIDC providers
  • Application-specific accounts ⇒
    1. account management difficulties
    2. malicious/incompetent applications
  • Wallets may store short-term secrets

Advantages

Disadvantages

6 of 50

Outline

  1. Overview of OpenID Connect (OIDC)
  2. Overview of keyless accounts
  3. Challenges
    1. ZK proving service
    2. ZK pepper service
    3. Dealing with locked out users
    4. zkSNARK trusted setup
    5. Consensus on JWKs
    6. OIDC-related
    7. Application-specific accounts
    8. ZKP-related challenges

6

7 of 50

Overview of OpenID Connect (OIDC)

​

7

OIDC provider

(e.g., Google)

User

(e.g., you!)

Application

(e.g., Notion.so)

​

Wants to sign in to application using their existing account with OIDC provider

Checks signatures from OIDC provider to authenticate user. No leaky password databases!

Signs messages for application to prove user authenticated successfully.

8 of 50

Prerequisite: OIDC application ("client") registration

8

OIDC provider

User

client_id

Application

​

9 of 50

Step 1: Application redirects user to sign in via OIDC provider

9

OIDC provider

Application

(client_id)

User

&client_id=client_id

&nonce=any_data

May I sign in?

10 of 50

Step 2: Application receives OIDC signature

10

OIDC provider

SK, PK

Application

(client_id)

User

σ = SignSK({

uid: alice@gmail.com,

app: client_id,

nonce: any_data,

})

11 of 50

Step 3: Any 3rd party can verify this OIDC signature

​

11

OIDC provider

SK, PK

Application

(client_id)

User

3rd party

PK

VerifyPK(σ, {

uid: alice@gmail.com,

app: client_id,

nonce: any_data,

})

12 of 50

Outline

  • Overview of OpenID Connect (OIDC)
  • Overview of keyless accounts
  • Challenges
    • ZK proving service
    • ZK pepper service
    • Dealing with locked out users
    • zkSNARK trusted setup
    • Consensus on JWKs
    • OIDC-related
    • Application-specific accounts
    • ZKP-related challenges

12

13 of 50

Web 2: Application receives OIDC signature

13

OIDC provider

SK, PK

Application

(client_id)

User

3rd party

PK

σ = SignSK({

uid: alice@gmail.com,

app: client_id,

nonce: any_data,

})

14 of 50

Web 3: Wallet receives OIDC signature

14

OIDC provider

SK, PK

Petra wallet

(client_id)

Aptos user

Aptos blockchain

PK

σ = SignSK({

uid: alice@gmail.com,

app: client_id,

nonce: txn_hash,

})

15 of 50

Web 3: Blockchain verifies OIDC signature

15

OIDC provider

σ = SignSK({

uid: alice@gmail.com,

app: client_id,

nonce: txn_hash,

})

SK, PK

Petra wallet

(client_id)

Aptos user

Aptos blockchain

PK

addr = H({

uid: alice@gmail.com,

app: client_id,

})

​

Problem 1: For each TXN she wants signed, Alice must "Sign in with Google."

Solution: Layer of indirection via ephemeral pubkeys. [HMF+23]

VerifyPK(σ, {

uid: alice@gmail.com,

app: client_id,

nonce: txn_hash,

})

16 of 50

Fix 1: Google signs ephemeral pubkeys (EPKs), not TXNs

16

OIDC provider

&client_id=client_id

&nonce=epk

Petra wallet

(client_id)

Aptos user

esk, epk

17 of 50

Fix 1: Google signs ephemeral pubkeys (EPKs), not TXNs

17

OIDC provider

Petra wallet

(client_id)

Aptos user

esk, epk

Ensures the OIDC signature "expires" after exp_date

, r

&client_id=client_id

&nonce=epk|exp_date

18 of 50

Fix 1: Google signs ephemeral pubkeys (EPKs), not TXNs

18

OIDC provider

Petra wallet

(client_id)

Aptos user

esk, epk

σOIDC = SignSK({

uid: alice@gmail.com,

app: client_id,

nonce: epk,

})

19 of 50

Fix 1: Google signs ephemeral pubkeys (EPKs), not TXNs

19

esk, epk

OIDC provider

σOIDC = SignSK({

uid: alice@gmail.com,

app: client_id,

nonce: epk,

})

SK, PK

Petra wallet

(client_id)

Aptos user

Aptos blockchain

PK

Verifyepk(σeph, txn_hash)

σeph = Signesk(

txn_hash

)

VerifyPK(σOIDC, {

uid: alice@gmail.com,

app: client_id,

nonce: epk,

})

epk

Problem 2: addr, TXN and σOIDC each leak alice@gmail.com and client_id.

Problem 2': Google sees epk.

Solution: Zero-knowledge proofs!

20 of 50

Problem 2: Blockchain & Google get sensitive info

20

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: epk,

}) = 1

​

assert addr = H({

uid: email,

app: client_id,

})

Step 1

Step 2

such that:

Petra gives blockchain sensitive

(σOIDC, email, client_id, addr)

Petra gives Google epk.

Petra gives blockchain non-sensitive (epk)

21 of 50

Problem 2: Blockchain & Google get sensitive info

21

​

assert addr = H({

uid: email,

app: client_id,

})

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: epk,

}) = 1

Petra gives Google epk.

Petra gives blockchain non-sensitive (epk, addr)

such that:

Petra gives blockchain sensitive

(σOIDC, email, client_id)

Step 0: Make the address non-sensitive

Step 1

Step 2

22 of 50

Problem 2: Blockchain & Google get sensitive info

22

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: epk,

}) = 1

Petra gives Google epk.

Petra gives blockchain non-sensitive (epk, addr)

such that:

Petra gives blockchain sensitive

(σOIDC, email, client_id, pepper)

Step 0: Make the address non-sensitive

Step 1

Step 2

23 of 50

Problem 2: Blockchain & Google get sensitive info

23

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: epk,

}) = 1

Petra gives Google epk.

Petra gives blockchain non-sensitive (epk, addr)

such that:

Petra gives blockchain sensitive

(σOIDC, email, client_id, pepper)

User will rely on a 🌶️ ZK pepper service to recover their pepper.

Step 1

Step 2

24 of 50

Problem 2: Blockchain & Google get sensitive info

24

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: H(epk, r),

}) = 1

Petra gives Google H(epk, r).

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

Petra gives blockchain non-sensitive (epk, addr)

Petra gives blockchain sensitive

(σOIDC, email, client_id, pepper)

such that:

Step 1: Give Google an epk commitment

Step 1

Step 2

25 of 50

Problem 2: Blockchain & Google get sensitive info

25

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: H(epk, r),

}) = 1

Petra gives Google H(epk, r).

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

Petra gives blockchain non-sensitive (epk, addr)

Petra gives blockchain sensitive

(σOIDC, email, client_id, pepper, r)

such that:

Step 1: Give Google an epk commitment

Petra stores randomness r in ephemeral storage.

Step 1

Step 2

26 of 50

Problem 2: Blockchain & Google get sensitive info

26

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: H(epk, r),

}) = 1

Petra gives Google H(epk, r).

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

Step 1

Step 2

Petra gives blockchain non-sensitive (epk, addr)

Petra gives blockchain a ZKPoK of sensitive

(σOIDC, email, client_id, pepper, r)

such that:

i.e., ∃priv s.t. Rkeyless( pub = [PK, epk, addr], priv = [σOIDC, email, client_id, pepper, r] ) = 1

Step 3: Use a ZKP to hide sensitive fields

27 of 50

Problem 2’: OpenID signatures need to “expire” after a while

27

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: H(epk, exp, r),

}) = 1

Petra gives Google

H(epk, exp, r).

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

Step 1

Step 2

Petra gives blockchain non-sen. (epk, exp, addr)

Petra gives blockchain a ZKPoK of sensitive

(σOIDC, email, client_id, pepper, r)

such that:

i.e., ∃priv s.t. Rkeyless( pub = [PK, epk, exp, addr], priv = [σOIDC, email, client_id, pepper, r] ) = 1

28 of 50

Fix 2: ZKPs for Rkeyless and epk commitment

28

OIDC provider

&client_id=client_id

&nonce=H(epk; r)

Petra wallet

(client_id)

Aptos user

esk, epk

, r

29 of 50

Fix 2: ZKPs for Rkeyless and epk commitment

29

OIDC provider

Petra wallet

(client_id)

Aptos user

esk, epk

σOIDC = SignSK({

uid: alice@gmail.com,

app: client_id,

nonce: H(epk, r),

})

, r

Compute ZKP π for ∃priv s.t.

Rkeyless(

pub = [PK, epk, addr],

priv = [σOIDC, email, client_id, pepper, r]

) = 1

30 of 50

Fix 2: ZKPs for Rkeyless and epk commitment

30

, r

esk, epk

OIDC provider

SK, PK

Petra wallet

(client_id)

Aptos user

Aptos blockchain

Verifyepk(σeph,

txn_hash

)

π, epk, σeph = Signesk(txn_hash)

Verify ZKP π for Rkeyless(

pub = [PK, epk, addr]

)

σOIDC

Problem 3: Computing ZKPs is slow.

Solution: Outsource to a ZK proving service.

31 of 50

Outline

  • Overview of OpenID Connect (OIDC)
  • Overview of Keyless
  • Challenges
    • ZK proving service
    • ZK pepper service
    • Dealing with locked out users
    • zkSNARK trusted setup
    • Consensus on JWKs
    • OIDC-related
    • Application-specific accounts
    • ZKP-related challenges

31

32 of 50

🪄 ZK proving service

32

σOIDC = SignSK({

uid: email,

app: client_id,

nonce: H(epk, r),

}), epk, r, pepper

ZKP π for Rkeyless

Petra wallet

(client_id)

🪄ZK proving service

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: H(epk, r),

}) = 1

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

Step 1

Step 2

Rkeyless( pub = [PK, epk, addr],

priv = [σOIDC, email, client_id, pepper, r] ):

Advantages

​

  • Currently: Learns all users' transactions

Disadvantages

​

  • Helps (d)apps create proofs in <1s
  • If offline, users can still transact
  • Trivial horizontal scalability
  • Training wheels to mitigate circuit bugs
  • Future: Privacy via blind proving

33 of 50

🌶️ ZK pepper service

33

Petra wallet

(client_id)

🌶️ ZK pepper service

pepper = VRFPSK(

uid: email,

app: client_id,

})

PSK, PPK

σOIDC = SignSK({

uid: email,

app: client_id,

nonce: H(epk, r),

})

Advantages

Disadvantages

  • Only stores a secret PSK
  • Peppers are publicly-verifiable
  • Future: Privacy via ZKPs
  • Future: Decentralization (on-chain?)
  • If offline, users are locked out
  • Currently: Learns all users' keyless addresses
  • Currently: Learns when users log into (d)apps

34 of 50

Dealing with banned, gone or incompetent wallet or dapp

Problem: e.g., incompetent dapp deletes their client_id registration ⇒ users are locked out.

Solution: Deploy an untrusted recovery service that authenticates users via OIDC. A [ZKPoK of an] OIDC signature from the recovery service can be used to rotate the key of an account associated with a missing application.

34

35 of 50

Rkeyless-specific trusted setup

  1. We use a general-purpose zkSNARK scheme called Groth16.
    1. i.e., for any relation R(x, w), Groth16 can prove ∃w s.t. R(x, w) = 1 without leaking w
  2. In order to compute such a proof, Groth16 requires a trusted setup phase, which:
    • publicly-outputs a proving key prk and a verification key vrk.
      1. The prover (e.g., ZK proving service) needs prk, which is large
      2. The verifier (e.g., blockchain) needs vrk, which can be made constant-sized
    • privately-outputs "toxic" secret information that must be discarded.
  3. If not discarded, this "toxic waste" can be used to forge invalid proofs.
  4. Therefore, a single participant is not enough to run the phase, since that participant could be malicious.
  5. Instead, we use a multi-party computation (MPC) protocol run by many participants to produce a prk without any toxic waste

35

Makes upgrades to Rkeyless operationally- difficult.

Future: Consider switching to universal SNARKs.

36 of 50

Necessity of consensus on OIDC providers' PKs

Problem:

  • Every OIDC provider's PK is changing periodically (every 2 weeks) and must be fetched from a URL.
  • If not fetched quickly & agreed-upon by validators, users are locked out.

Solution:

  • Implement an HTTP oracle that allows the validators to agree on the contents of any URL.
  • Use this to periodically update our views of Google's PK.

36

37 of 50

Other OIDC-related assumptions

  1. Trust that OIDC providers "play ball"
    1. e.g., OIDC provider could ban users of blockchain applications; users would be locked out.
    2. addressable via 1-out-of-2 w/ passkeys, or via alternative recovery paths
  2. Trust that OIDC providers are not compromised
    • Nonetheless, keyless accounts remain more likely to be secure compared to normal SK-based accounts, where too many users lose their keys.

37

38 of 50

Challenges around application-specific accounts

  • Application-specific accounts; not just user-specific.
    • Implication: Your Petra wallet keyless account ≠ Your Pontem wallet keyless account (can be addressed using 1-out-of-2 accounts).
  • Dapp-specific accounts: users can sign in to dapps directly via OIDC.
    • Good UX: No need to set up a wallet; dapp effectively controls the account
    • Dapp website is down/disappears ⇒ users are locked out (addressed via recovery service)
  • Managing all your application-specific accounts

38

39 of 50

Training wheels via 🪄 ZK proving service signatures

39

  • There could be flaws in the implementation of Rkeyless that could lead to stolen funds
  • To mitigate against this, ZK prover service includes a training wheels signature over the ZKP
  • After having verified the relation holds & before computing the proofs
  • As a result, a break in our Rkeyless implementation will not result in a catastrophic loss of funds for our users
  • At the same time, assuming no bugs in Rkeyless, a compromised proving service on its own cannot steal funds
  • Liveness consideration: if the proving service is down, users will not be able to access their accounts temporarily

40 of 50

Other ZKP-related challenges

  • Future: Keyless TXNs need not leak OIDC provider.
    • Addressable by extending our Rkeyless
  • Future: OIDC provider could change their OIDC signature algorithm
    • Quickly-addressable by turning on the ZK-less path via feature flag
    • Ultimately-addressable via circuit upgrade
  • Bug in Rkeyless implementation
    • Quickly-addressable by turning on the ZK-less path via feature flag
    • Ultimately-addressable via circuit upgrade

40

41 of 50

Did not get to discuss yet

  • In-depth solutions to the account management problem
  • ZK-less path: Disabling ZKPs in case of bugs in our zkSNARK circuit (see AIP-61)
  • OIDC for desktop apps (no redirect URI in Google Cloud)

41

42 of 50

Useful references

[Groth16] On the Size of Pairing-based Non-interactive Arguments; by Jens Groth; 2016; https://eprint.iacr.org/2016/260

[HMF+23] OpenPubkey: Augmenting OpenID Connect with User held Signing Keys; by Ethan Heilman and Lucie Mugnier and Athanasios Filippidis and Sharon Goldberg and Sebastien Lipman and Yuval Marcus and Mike Milano and Sidhartha Premkumar and Chad Unrein; 2023; https://eprint.iacr.org/2023/296

[QQQ+90] How to Explain Zero-Knowledge Protocols to Your Children; by Quisquater, Jean-Jacques and Quisquater, Myriam and Quisquater, Muriel and Quisquater, Michaël and Guillou, Louis and Guillou, Marie Annick and Guillou, Gaïd and Guillou, Anna and Guillou, Gwenolé and Guillou, Soazig; in CRYPTO' 89

[Tome23] What is a zero-knowledge proof system; by Alin Tomescu; 2023; slides

​

42

43 of 50

Appendix

43

44 of 50

Problem: The bulk of the Keyless relation

44

​

assert VerifyPK(σOIDC, h) = 1

​

assert addr = Poseidon({

uid: email,

app: client_id,

})

Step 2

Step 3

Rkeyless(

pub = [PK, addr],

priv = [σOIDC, email, client_id, prefix, mid, suffix]

) = 1

​

let h = SHA2-256({

prefix: prefix,

uid: email,

mid: mid,

app: client_id,

suffix: suffix,

}) = 1

Step 1

45 of 50

Alternative recovery paths

For email-based OIDC providers, leverage DKIM email signatures:

  • e.g., validators can accept an epk from a Google-signed email

For non-email-based OIDC providers, it depends:

  • e.g., for Twitter, I can prove I own my account by tweeting my epk publicly
  • e.g., for GitHub, I can prove I own my account by posting my epk in a gist
  • Assuming an HTTP oracle, validators can verify this epk and let me rotate my account's key
  • Possibility: We only allow OIDC providers that support such alternative recovery paths

Alternatively, all keyless accounts must be 1-out-of-2 with a recovery passkey sub-account

45

46 of 50

Zero-knowledge proofs

∃w, s.t. R(x, w) = 1

46

Public statement:

Both prover and verifier have this.

Private witness:

Only prover has it.

Must remain hidden from verifier.

Polynomial-time computable relation R(⋅,⋅) Known to prover & verifier

A ZKP convinces the verifier that the prover knows a (secret) witness w such that R(x, w) = 1

47 of 50

Example: A ZKP for the Sudoku relation

Sudoku(puzzle, sol) = 1

47

A ZKP convinces the verifier that the prover knows a (secret) sol such that Sudoku(puzzle, sol) = 1

The solution to the puzzle

The Sudoku puzzle

48 of 50

Normal keyless validation path

48

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: H(epk, r),

}) = 1

app gives Google H(epk, r).

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

Step 1

Step 2

app gives blockchain non-sensitive (epk, addr)

app gives blockchain a ZKPoK of sensitive

(σOIDC, email, client_id, pepper, r)

such that:

i.e., ∃priv s.t. Rkeyless( pub = [PK, epk, addr], priv = [σOIDC, email, client_id, pepper, r] ) = 1

Step 3: Use a ZKP to hide sensitive fields

49 of 50

Supporting audless mode

49

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: H(epk, r),

}) = 1

​

assert addr = H({

uid: email,

app: skip_aud_check ? "" : client_id

pepper: pepper

})

such that:

Step 1

Step 2

app gives Google H(epk, r).

app gives blockchain non-sensitive (epk, addr)

app gives blockchain a ZKPoK of sensitive

(σOIDC, email, client_id, pepper, r)

Step 3: Use a ZKP to hide sensitive fields

i.e., ∃priv s.t. Rkeyless( pub = [PK, epk, addr],

priv = [σOIDC, email, client_id, pepper, r, skip_aud_check] ) = 1

50 of 50

Supporting audless mode

50

​

assert VerifyPK(σOIDC, {

uid: email,

app: client_id,

nonce: H(epk, r),

}) = 1

app gives Google H(epk, r)

​

assert addr = H({

uid: email,

app: client_id,

pepper: pepper

})

Verify signature

Then

app gives blockchain non-sen. (epk, addr)

app gives blockchain a ZKPoK of sensitive

(σOIDC, email, client_id, pepper, r)

such that:

i.e., ∃priv s.t. Rkeyless( pub = [PK, epk, addr],

priv = [σOIDC, email, client_id, pepper, r, skip_aud_check] ) = 1

​

assert addr = H({

uid: email,

app: "",

pepper: pepper

})

If skip_aud_check = true:

Else