Social recovery using address book merkle proofs

Not sure if this has been discussed before but the idea is that the contract-based account owner (Alice) can generate a merkle root based on her address book list so when Alice loses her management keys to the account contract, she can have n of m address book peer signatures submitted to set a new management key owned by Alice.

The merkle root is stored in the account contract and no other information about the address book list is required or stored on-chain. Alice selects a subset of trusted peers from her address book, generates the merkle root with the addresses as tree leaves, and sets the root on-chain. The address list used can be encrypted and emailed to her since she’ll need it when it’s time to recover the account.

Let’s say the address book list she used has the addresses of Bob, Charlie, Dave, Eve, and Frank, and requirs 2 of n signatures to set a new management key.

  1. Alice loses her management keys and asks Eve to help her recover her account.
  2. Alice gives Eve a newly generated address she controls and Eve takes a hash of the public address and signs the hash with her private key corresponding to the public address that Alice has stored for Eve in Alice’s address book.
  3. Alice takes Eve’s signature and generates a merkle proof using her trusted peer address book list and Eve’s address as the leaf.
  4. Alice submits the signature, data, and proof to her contract. The contract verifies that Eve is indeed part of the stored merkle proof and the submission is recorded in a mapping.
  5. Alice then asks Bob to help her recover the account. Bob signs the hash of the new address and Alice submits the same pieces of data to the contract.
  6. The contract verifies that Bob is part of the stored merkle proof, and then checks if the threshold has been met.
  7. If the signatures required threshold has been met, then it verifies that all the signers agreed on the same new management key address.
  8. If that succeeds, then the new management key is set and Alice can access her contract-based account again.

To demonstrate, here’s a rough proof-of-concept contract in Solidity:

pragma solidity ^0.5.2;

import './ECDSA.sol';
import './MerkleProof.sol';

contract Account {
  using ECDSA for *;
  using MerkleProof for *;

  address public owner;
  bytes32 public recoveryRoot;
  uint256 public sigsRequired;
  uint256 public seq;
  mapping (uint256 => address) sigs;

  modifier isOwner {
    require(msg.sender == owner, "Invalid sender");
    _;
  }

  constructor() public {
    owner = msg.sender;
    sigsRequired = 1;
  }

  function setOwner(address newOwner) external isOwner {
    owner = newOwner;
  }

  function setRecoveryRoot(bytes32 root) external isOwner {
    recoveryRoot = root;
  }

  function setSigsRequired(uint256 num) external isOwner {
    sigsRequired = num;
  }

  function recover(bytes32[] memory proof, bytes memory signature, address newOwner) public {
    bytes32 hash = keccak256(abi.encodePacked(newOwner));

    address recoveryKey = hash.toEthSignedMessageHash().recover(signature);
    bytes32 leaf = keccak256(abi.encodePacked(recoveryKey));
    require(proof.verify(recoveryRoot, leaf), "Invalid proof");
    sigs[seq] = newOwner;
    seq++;

    if (seq == sigsRequired) {
      address proposedOwner;
      for (uint8 i = 0; i < seq; i++) {
        if (i > 0 && proposedOwner != sigs[i]) {
          revert("Invalid new owner");
        }

        proposedOwner = sigs[i];
      }

      owner = proposedOwner;
      seq = 0;
    }
  }
}

The test would go as follows (pseudocode):

const addressBook = [Bob, Charlie, Dave, Eve, Frank]

const leaves = addressBook.map(x => keccak256(x)).sort()
const tree = new MerkleTree(leaves, keccak256)

const root = tree.getRoot()
await contract.setRecoveryRoot(root)
await contract.setSigsRequired(2)

const hash = keccak256(AliceNewKey)

const EveSig = web3.eth.sign(hash, Eve)
const EveProof = tree.getProof(keccak256(Eve))
await contract.recover(EveProof, EveSig, AliceNewKey)

const BobSig = web3.eth.sign(hash, Bob)
const BobProof = tree.getProof(keccak256(Bob))
await contract.recover(BobProof, BobSig, AliceNewKey)

assert.equal(await contract.owner.call(), AliceNewKey)

Working example code is on github.

Things to note:

  1. A benefit of this method is that it doesn’t require pre-approval of your address list beforehand, so there is no awkward UX issues, and recovery is as simple as asking the peers to sign a hash of a public address, which then you or a relayer can submit onchain.
  2. Address book list is never exposed until it’s time for recovery, then the senders will of course be exposed.
  3. Verifying merkle proof on-chain is expensive but recovery is something that should happen infrequently so this is fine.
  4. To make it more secure, a timelock period can be initiated after the threshold is met to allow the owner to cancel the recovery and set a new merkle root in the case the peers collude which prevents them from immediately setting the new management. A recommended number would be to require at least 2 peers and 1 hardware device so in the case the peers collude they still need the hardware device signature, and in the case the hardware device is compromised then the peer signatures are still required. The contract can maintain two merkle roots, one consisting of friends and family and one consisting of hardware device keys, both with their own thresholds.
  5. The address book can be maintained in decentralized fashion, such as using 3Box’s private storage, making the user’s address book be portable.
  6. Instead of addreses, using ENS names can also work by resolving the name onchain when checking the recovered signer.

Would like to open up the discussion and hear what you guys think about all this. Thanks!

5 Likes

great summary.

how would you make sure that the address that you used to create the merkle tree does not become outdated? (my friend lost his wallet, or got hacked)

little remark:

Verifying merkle proof on-chain is expensive but recovery is something that should happen infrequently so this is fine.

actually very cheap, and will become very cheap with latest gas schedule changes in Ethereum.

how would you make sure that the address that you used to create the merkle tree does not become outdated? (my friend lost his wallet, or got hacked)

Great question. If you know your friends wallet got compromised, you can remove him from the address book list and recompute the merkle root and store the new root in the account contract to prevent the attacker from starting the recovery process with the compromised account.

To prevent outdated addresses from being utilized, you can periodically recompute and submit an updated merkle root using up-to-date addresses or use ENS names instead of hard coded address as the merkle leaves and resolve ENS to addresses in the recovery method.

actually very cheap, and will become very cheap with latest gas schedule changes in Ethereum.

Nice, that’s very cool

1 Like

if the ENS can be resolved on chain, maybe encoding the ENS name into the tree would suffice.

There is a follow-on problem using ENS thought:

what if the address is not an key, but a contract? like an identity contract?

what if the address is not an key, but a contract? like an identity contract?

Since contracts can’t generate signatures therefore ecrecover won’t work if the address is a contract, then the contract-based account needs to use the EIP1271 standard to verify contract signatures. During the recovery process, the account contract checks if there’s bytecode stored at the leaf address. If there is, then it is a contract and not an externally owned account so it verifies the signature using isValidSignature( data, signature) on the friend’s contract. Authereum, Dapper wallet, 0x, and a few others are already using EIP1271 to verify signatures where the "recovered addres"s is a contract address.

Hey @miguelmota, very nice.

I have also a working solution with the same concept, but I also introduced user data hash and other important (but optional) security features.

It’s fully documented here in the sol:

This is a WIP/Research repository, which I am working to build account contracts for Status.im, and for future interoperability between I am writing an ERC to standardize the social recovery feature.

The contract features a Secret Multisig system, which is self contained and should be used as a recovery actor in a account contract, instead of extending this into user account contract, so it’s behavior would be always consistent.

After merkle tree (or part of it) is revealed, a new merkle root needs to be defined, so every recovery requires a new recovery setup.

The user datahash is a hash of hash of user private data, which could be bio-metrics or derived from user profile data, and will be used to secure the recovery process and obfuscate the threshold.

1 Like

Hi @3esmit,

There is another reason for this beside privacy?

Yes, the point of using a merkle tree was initially privacy, and when a recovery is done some of this privacy is lost, so it should change the list.

However I see that I should instead disable recovery after user successfully recovered, and after that suggest a new recovery in the wallet UI.

1 Like

I think suggesting is a good option, but changing the Merkle tree should not be mandatory.

Thanks

I think that security should be mandatory, especially if possible.
It’s possible to reuse the same exact list of friends as before, but it would change the merkle root because the way I designed it is that the userDataHash is used also in the merkle tree to obfuscate the leafs.

The semi secret stores the friend list and the user private secret, and the same seeds can be reused as many times as wanted by salting the user private secret, thats why its hashed multiple times. Therefore the UI can do all this on behind without the user even have to know.

This is great! Yes a bare-bones simple standard around this social recovery method would be very beneficial to anyone implementing contract-based accounts.

1 Like

Do agree that it should be optional, though I could see a scenario where a malicious person might be less incentivized to attempt to steal a known peer’s device if it’s not certain that they are part of the same recovery merkle root again, so setting up a new root would be advantageous.

Thanks for the context.

I don’t think that changing the addresses that allow recovery will improve directly the security. The userDataHash computed in the Merkle Tree will bring some obfuscation but fundamentally the security will have to be the security of the base addresses.

From what i saw in the code, you are defining the userDataHash as some kind of question / answer, and this will make it more transparent to UX, but can have a great utility for recovery. If is strong enough, as an seed phrase, maybe the addresses can be discarded. But in this setting there is no social recovery, just a personal one.

I’m talking about not change the addresses in the tree just for the potential functionality of a smart wallet (not a EOA) to help recovery a account. As is, a user smart wallet cannot be another user backup.

I see that is better for privacy, but i fear that making mandatory is too opinionated, maybe this decision should be left to the wallet implementation.
But as @3esmit said, the wallet only have to change the userDataHash to get the same privacy in merkle tree.

1 Like

Using the secret alone is unsafe - as it should be easy to guess then its also easy to discover, and a totally different approach using a special commit-reveal scheme would be essential for protecting overruns, or if you suggest a seed phrase, then ECDSA should be used, in this case the recovery address can simply be hashed once, however this does not solve the problem of dealing with seed phrases or a single trusted party.

My main concerns in interoperability would be in the messaging of the recovery requests, I think that most wallets could have their own service/protocol for that, but that would break interoperability and decentralization, so it would be important for a common ground between wallets to exchange these requests.
We could leave this bridge open for now (everyone uses its own), and standardize as sub ERC-681 arecovery request URI and a recovery authorization URI, so if user is not reachable (using different bridge) within same wallet software, a recovery request URI could be sent by email (or whatever) and understood by other wallet, and produce a recovery authorization URI.

We can improve the common bridge later or seek for integration with other solutions such as wallet connect or universal logins, that are also solving the “device bridge problem”, which could be used for this purpose as well.

I am writing a detailed specification on this concept, including UX and interoperability mentioned above, and once I get all thats in my mind sorted out I’ll share here and we can have a call and start a EIP process.

1 Like

Submitted the EIP 2429: Secret Multisig Recovery
First draft is here: https://github.com/ethereum/EIPs/pull/2429

There is still a lot to do, and my own solidity file is not compatible with this standard, as while I was specifying it, I matured it.

I used this thread as discussion because we were already discussing this problem-solution here, or maybe what I specified dont fits here, if thats the case let me know and I create a dedicated topic to discussing the solution of using merkle trees + user secret and here would be other thing.