Skip to content

Latest commit

 

History

History
138 lines (93 loc) · 7.27 KB

Lamport 签名.md

File metadata and controls

138 lines (93 loc) · 7.27 KB
Raw

Lamport 签名

Lamport 签名是一种基于哈希函数的单次使用签名方案，由计算机科学家 Leslie Lamport 在 1979 年提出。它被设计为一种抗量子计算攻击的数字签名方案，意味着即使在未来量子计算机能够破解当前常用的公钥加密算法（如 RSA 和 ECC），Lamport 签名依然是安全的。

原理概述

Lamport 签名利用单向哈希函数（如 SHA-256）来生成一组密钥对。它通过生成多个不同的密钥来保证签名的唯一性，每次签名只能使用一次。

步骤

  1. 密钥生成：
    • 生成一个由两部分组成的私钥：对于每一个消息位（假设消息为二进制表示），生成两组随机数，分别作为0和1的密钥（即每一位有两个可能的密钥）。
    • 对每个私钥进行哈希运算，生成公钥。
  2. 签名过程：
    • 要对消息进行签名时，将消息转换为二进制。
    • 根据消息的每一位是0还是1，选择相应的私钥部分并暴露出来，作为该位的签名。
  3. 验证过程：
    • 验证者使用暴露出来的签名部分，通过哈希函数得到相应的哈希值。
    • 然后将其与发布的公钥进行比较。如果全部匹配，签名即被验证为有效。

例子

假设我想要签署一个 2 位二进制消息 10，步骤如下：

  • 生成密钥：我生成4个随机数，分别为：

    • 第一位的0密钥：A0
    • 第一位的1密钥：A1
    • 第二位的0密钥：B0
    • 第二位的1密钥：B1

    我对这些密钥做哈希运算，生成公钥（假设分别是h(A0)，h(A1)，h(B0)，h(B1)）。

  • 签名：要签署消息 10，我会：

    • 选择第一位的 1 对应的密钥，暴露 A1
    • 选择第二位的 0 对应的密钥，暴露 B0

  • 验证：验证者拿到 A1 和 B0，计算它们的哈希值 h(A1) 和 h(B0)，并检查是否与公钥中的 h(A1) 和 h(B0) 匹配。如果匹配，签名就有效。

优缺点

优点：

  • 抗量子攻击：由于仅依赖于哈希函数，量子计算机无法有效破解这种签名方案。
  • 简单性：Lamport 签名方案的数学基础相对简单，安全性基于哈希函数的安全性。

缺点：

  • 一次性使用：每个密钥对只能用于签名一次，这使得在大多数实际应用中其不便于重复使用。
  • 公钥和私钥的体积较大：每个密钥对需要多组哈希值，公钥和私钥体积较大，导致存储需求增加。

尽管 Lamport 签名本身的效率较低，现代抗量子密码系统依然可以从中借鉴关键思想，并且它也是许多后续抗量子签名方案的基础。

应用场景

虽然比特币脚本语言是无状态的，但通过巧妙地使用一次性数字签名方案（例如，Lamport 签名），可以在不同的比特币交易中保持状态。假设在比特币网络中有一系列相关联的交易，每个交易依赖于前一个交易的输出（例如多步的智能合约或状态机），Lamport签名可以确保某些状态在不同交易之间传递，而不会被篡改。 要详细展示如何使用 Lamport 签名 实现比特币网络中不同交易间的状态转换（即“状态切换”），我们需要结合比特币的 UTXO 模型 和 Lamport 签名 的特性来构造一个例子。这个例子将展示如何通过状态承诺机制来确保每次交易状态的切换过程在区块链上得以实现。

例子：使用 Lamport 签名的状态切换过程

假设我们构造一个系统，Alice 想通过连续的比特币交易来记录和切换某个账户上的“余额”状态。每笔交易会消耗之前的 UTXO，生成新的 UTXO，且每笔交易都会使用 Lamport 签名来对当前的状态进行签名，以确保状态切换是可信和验证的。

场景：

  • 初始状态：Alice 持有 5 BTC，她想通过比特币交易来管理这个余额状态，使得在每次交易后，新的 UTXO 记录的余额是可信的。
  • 状态转换：Alice 每次交易后会更新余额状态，且用 Lamport 签名对这个新的状态进行签名，以确保在区块链上能够验证状态的更新。

1. 初始状态：Alice 生成 Lamport 密钥对

  • 私钥：sk_1, sk_2, sk_3, sk_4
  • 公钥：pk_1=HASH(sk_1), pk_2=HASH(sk_2), pk_3=HASH(sk_3), pk_4=HASH(sk_4)

Alice 通过一个交易将 5 BTC 存入自己的地址，同时生成一个状态承诺 Commit_0，表示初始的 5 BTC 状态，并将其关联到 Lamport 公钥。

初始交易的锁定脚本：
    OP_DUP 
    OP_HASH160 
    <Alice 公钥哈希>
    OP_EQUALVERIFY 
    OP_CHECKSIG 
    CheckLampCommpkM_0

这个交易输出将状态 Commit_0 与 Alice 的 Lamport 公钥关联起来，承诺了她当前持有的 5 BTC 状态。

2. 生成下一个状态并进行签名

假设 Alice 想通过下一笔交易将 2 BTC 转给 Bob，并更新她的余额状态到 3 BTC。这个过程包括以下步骤：

  1. 生成新状态承诺：Commit_1，记录新的状态，即 Alice 现在有 3 BTC。

  2. 使用 Lamport 签名对 Commit_1 进行签名：

    • 假设 Commit_1 的哈希值为 H(Commit_1) = 1101，那么 Alice 将使用 sk_1, sk_2, sk_3, sk_4 中与消息哈希相匹配的私钥来签名。

  3. 生成新交易：该交易消耗之前的 UTXO（锁定的 5 BTC 状态），并生成两个新的 UTXO：

    • 一个 UTXO 转给 Bob，包含 2 BTC；
    • 另一个 UTXO 继续记录 Alice 的 3 BTC 状态，并更新到新的状态承诺 Commit_1。
解锁脚本：
    <Alice 的比特币签名>
    <Lamport 签名: sk_1, sk_2, sk_3, sk_4>
    <Commit_1>
    
锁定脚本（新的 UTXO，3 BTC）：
    OP_DUP 
    OP_HASH160 
    <Alice 公钥哈希>
    OP_EQUALVERIFY 
    OP_CHECKSIG 
    CheckLampCommpkM_1

3. 下一笔交易的状态切换

假设 Alice 又想发送 1 BTC 给 Carol，并再次更新她的余额状态到 2 BTC。

  1. 生成新的状态承诺：Commit_2，记录她的新余额 2 BTC。

  2. 使用 Lamport 签名对 Commit_2 进行签名：

    • 同样，根据 Commit_2 的哈希值，Alice 选择相应的私钥对状态进行签名。

  3. 生成新交易：

    • 消耗之前的 UTXO（记录 3 BTC 状态），生成两个新的 UTXO：
      • 一个 UTXO 转给 Carol，包含 1 BTC；
      • 另一个 UTXO 记录 Alice 的 2 BTC 状态，并关联新的状态承诺 Commit_2。

4. 验证过程

  • 每次新交易产生时，区块链验证者会检查 Alice 的 Lamport 签名是否正确：

    • 解锁脚本提供的私钥是否与之前的状态承诺 Commit_1 相符；
    • 新生成的状态承诺是否有效。

  • 通过这种机制，Alice 的账户状态（余额）在不同的交易间得到了安全的切换，且每次状态更新都是通过 Lamport 签名承诺和验证的。

总结

这个例子展示了如何通过 Lamport 签名 结合比特币交易来实现跨交易的 状态承诺和切换。每次交易后，Alice 都会生成一个新的状态承诺，并通过 Lamport 签名对其进行签名，确保状态的切换是可信和可验证的。每个 Lamport 密钥对只能使用一次，这种特性使得它非常适合用于一次性状态更新的场景。